akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
#define ll long long
#define  f first
#define pii pair<int,int>
#define pll pair<ll,ll>
#define ull unsigned ll
#define pb push_back
#define mp make_pair
#define  s second

using namespace std;

ll mod=1e9+7;

int main(){
    ll n;cin>>n;
    ll ans1=1;
    for(ll i=1;i<=n;i++){
    	ans1*=10;
    	ans1%=mod;
	}
	ll ans2=1;
	for(ll i=1;i<=n;i++){
		ans2*=8;
		ans2%=mod;
	}
	ans1+=ans2;
	ans1%=mod;
	ans2=2;
	for(ll i=1;i<=n;i++){
		ans2*=9;
		ans2%=mod;
	}
	cout<<((ans1-ans2)%mod+mod)%mod;
	return 0;
}


Measured memory_bytes: 3632
#include <bits/stdc++.h>

#define rep(i, n) for(int i = 0; i<(n); i++)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
using namespace std;

const int MOD = 1000000007;

struct Edge {
    int from;
    int to;
    long long cost;
};

vector<Edge> ans;

void bypass(int add, int L) {
    if (L <= 0) return;

    for (int k = 19; k >= 0; --k) {
        if (L >= (1 << k)) {
            ans.push_back({k + 1, 20, add});
            bypass(add + (1 << k), L - (1 << k));
            break;
        }
    }
}

int main() {
    int L;
    cin >> L;

    for (int i = 1; i < 20; i++) ans.push_back({i, i + 1, 0});

    for (int k = 19; k >= 1; k--) {
        if (L >= (1 << k)) {
            for (int i = 1; i <= k; i++) {
                ans.push_back({i, i + 1, 1 << (i - 1)});
            }

            bypass(1 << k, L - (1 << k));
            break;
        }
    }

    cout << 20 << " " << ans.size() << endl;
    for (auto e : ans) {
        cout << e.from << " " << e.to << " " << e.cost << endl;
    }
}

Measured memory_bytes: 256
# from math import factorial,sqrt,ceil,gcd
# from itertools import permutations as permus
from collections import deque,Counter
# import re
# from functools import lru_cache # 簡単メモ化 @lru_cache(maxsize=1000)
# from decimal import Decimal, getcontext
# # getcontext().prec = 1000
# # eps = Decimal(10) ** (-100)

# import numpy as np
# import networkx as nx
# from scipy.sparse.csgraph import shortest_path, dijkstra, floyd_warshall, bellman_ford, johnson
# from scipy.sparse import csr_matrix
# from scipy.special import comb

# slist = "abcdefghijklmnopqrstuvwxyz"
X = int(input())

dp = {100:1,101:1,102:1,103:1,104:1,105:1}
lis = [100,101,102,103,104,105]
que = deque([100,101,102,103,104,105])
while len(que)>0:
    num = que.popleft()
    for i in lis:
        dp[num+i] = 1
        if num+i <= 100000 and not(num+i in que):
            que.append(num + i)

if X in dp:
    ans = 1
else:
    ans = 0

print(ans)
# print(*ans)   # unpackして出力。間にスペースが入る
# for row in board:
#     print(*row,sep="")    #unpackして間にスペース入れずに出力する
# print("{:.10f}".format(ans))
# print("{:0=10d}".format(ans))


Measured memory_bytes: 15388
import math
n,m = map(int,input().split())
Cpiece = m-m%2
ans = 0
if n*2 <= Cpiece:
    ans = math.floor(n+(Cpiece-n*2-(Cpiece-n*2)%4)/4)
else:
    ans = math.floor(Cpiece/2)
print(ans)


Measured memory_bytes: 2940
#define SUBMIT

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef SUBMIT
    auto& in = cin;
#else
    stringstream in(R"(atcoderbeginnercontest
atcoderregularcontest
)");
#endif
    string O, E;
    in >> O >> E;
    for (int i = 0; i < E.length(); ++i) {
        cout << O[i] << E[i];
    }
    if (O.length() > E.length()) cout << O[O.length() - 1];
    cout << endl;

    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
using ll = long long;

int main(void){
    ll N,M;
    cin>>N>>M;
    ll ans=0;
    if (N*2>=M){
        ans += M/2;

    }
    else {
        ans += N;
        ll d = M - N*2;
        ans += d/4;
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>

template <typename H>
H max(const H &head) {
	return head;
}
template <typename H, typename ...Tail>
H max(const H &head, const Tail&... tail) {
	auto tail_max = max(tail...);
	return head > tail_max ? head : tail_max;
}

int max_lcs(const std::string &str, int l, int r, int k, std::vector<std::vector<std::vector<int>>> &memo) {
	if (l > r) return 0;
	if (l == r) return 1;
	if (memo[l][r][k] > 0) return memo[l][r][k];
	int res{ 0 };
	if (str[l] == str[r]) {
		res = max_lcs(str, l + 1, r - 1, k, memo) + 2;
	}
	else if (k != 0) {
		res = max_lcs(str, l + 1, r - 1, k - 1, memo) + 2;
	}
	res = max(res, max_lcs(str, l + 1, r, k, memo), max_lcs(str, l, r - 1, k, memo));
	return memo[l][r][k] = res;
}
int max_lcs(const std::string &str, int k) {
	std::vector<std::vector<std::vector<int>>> memo(str.size() + 1, std::vector<std::vector<int>>(str.size() + 1, std::vector<int>(k + 1, -1)));
	return max_lcs(str, 0, str.size() - 1, k, memo);
}

int main() {
	std::string str;
	int k;
	std::cin >> str >> k;
	std::cout << max_lcs(str, k) << std::endl;
}

Measured memory_bytes: 110336
#include <bits/stdc++.h>
using namespace std;

int main() {
  int N, M;
  cin >> N >> M;

  vector<int> H(N);
  for (size_t i = 0; i < H.size(); ++i) {
    cin >> H.at(i);
  }

  vector<int> high(N, 0);
  for (int i = 0; i < M; ++i) {
    int a, b;
    cin >> a >> b;
    high.at(a - 1) = max(high.at(a - 1), H.at(b - 1));
    high.at(b - 1) = max(high.at(b - 1), H.at(a - 1));
  }

  int ans = 0;
  for (size_t i = 0; i < H.size(); ++i) {
    if (H.at(i) > high.at(i)) ans++;
  }
  cout << ans << endl;
}

Measured memory_bytes: 3928
# -*- coding: utf-8 -*-
"""
Created on Sun Apr 12 20:20:19 2020

@author: Kanaru Sato
"""

a, b = list(map(int, input().split()))
l = []

i = -(-1*a//0.08)

while 0.08*i < a+1:
    l.append(i)
    i += 1

flag = 0

for candidate in l:
    if 0.1*candidate < b+1 and 0.1*candidate >= b:
        print(int(candidate))
        flag = 1
        break

if flag != 1:
    print(-1)

Measured memory_bytes: 3064
#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define mk make_pair
#define fi first
#define se second
#define vll vector<ll>
#define pii pair<ll,ll>
#define vvll vector< vector<ll> >
#define pb push_back
#define sz(v) (v).size()
#define inf 1e18
#define md 1000000007
#define all(v) (v).begin(),(v).end()
#define rep(i,a,b) for(ll i=a;i<b;++i)
#define tel(a){cout<<a<<"\n";}
#define tell(a,b){cout<<a<<" | "<<b<<"\n";}
#define telll(a,b,c){cout<<a<<" | "<<b<<" | "<<c<<"\n";}
#define teln(v,n){cout<<"v- ";rep(i,0,n)cout<<v[i]<<" ";cout<<"\n";}
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
#define M 300010

int main(){
	ll n;cin>>n;
	string s;cin>>s;
	ll a[10][10]={0};
	ll cnt[n+1][10]={0};
	cnt[0][s[0]-'0']++;
	rep(i,1,n){
		rep(j,0,10)cnt[i][j]=cnt[i-1][j];
		cnt[i][s[i]-'0']++;
	}
	rep(i,0,10)cnt[n][i]=cnt[n-1][i];
	rep(i,0,n){
		for(ll j=i+1;j<n-1;++j){
			if(a[s[i]-'0'][s[j]-'0']>0)continue;
			ll ct=0;
			rep(k,0,10)if(cnt[n][k]>cnt[j][k])ct++;
			a[s[i]-'0'][s[j]-'0']=ct;
		}
	}
	ll ans=0;
	rep(i,0,10)rep(j,0,10)ans+=a[i][j];
	cout<<ans;
	return 0;
}



Measured memory_bytes: 2688
#include<iostream>
#include<vector>
using namespace std;

int main(){
  
  int n,q;
  string s;
  cin >> n >> q >> s;
  int a;
  int b;
  int cnt;
  int sum[n+10] = {0};
  
  for(int i=0; i<n; i++){
    if(s[i] == 'A' && s[i+1] == 'C'){
    	sum[i+1] = sum[i] + 1; 
    }else{
     	sum[i+1] = sum[i]; 
    }
    
  }
  for(int i=0; i<q; i++){
    cin >> a >> b;
    cout << sum[b-1] - sum[a-1] << endl;
  }
}

Measured memory_bytes: 1408
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//#include <boost/multiprecision/cpp_int.hpp>
//typedef boost::multiprecision::cpp_int ll;
typedef long double dd;
#define i_7 (ll)(1E9+7)
//#define i_7 998244353
#define i_5 i_7-2
ll mod(ll a){
    ll c=a%i_7;
    if(c>=0)return c;
    return c+i_7;
}
typedef pair<ll,ll> l_l;
ll inf=(ll)1E16;
#define rep(i,l,r) for(ll i=l;i<=r;i++)
#define pb push_back
ll max(ll a,ll b){if(a<b)return b;else return a;}
ll min(ll a,ll b){if(a>b)return b;else return a;}
void Max(ll &pos,ll val){pos=max(pos,val);}//Max(dp[n],dp[n-1]);
void Min(ll &pos,ll val){pos=min(pos,val);}
void Add(ll &pos,ll val){pos=mod(pos+val);}
dd EPS=1E-9;
#define fastio ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
////////////////////////////


int main(){fastio
    ll n,m;cin>>n>>m;
    cout<<n*m<<endl;
    
    return 0;
}



Measured memory_bytes: 3216
package main

import (
	"fmt"
	"strings"
)

func main(){
	var n int
	fmt.Scan(&n)
	var s string
	fmt.Scan(&s)
	var answer int

	for i := 0; i < n; i++ {
		var be, af string
		for c, r := range s {
			v := string(r)
			if c <= i {
				if !(strings.Contains(be, v)) {
					be = be + v
				}
			}else{
				if !(strings.Contains(af, v)) {
					af = af + v
				}
			}
		}

		num := 0
		for _, x := range be {
			y := string(x)
			if strings.Contains(af, y) {
				num++
			}
		}
		if num > answer{
			answer = num
		}
	}
	fmt.Print(answer)
}

Measured memory_bytes: 768
import sys
input = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    import bisect

    """
    各工事場所について，
    Dがどのレンジなら引っかかるかを記録しておく．
    最初全部のDに関して，infまで行けるものとして，
    Xが小さい順に工事区間を見て，引っかかるならば区間更新．
    一度値を決定した場所は飛ばしながら更新するようにすればO(Q)
    nxtを入れながら進めば各ノードを2回しか見ないからO(Q)
    事前のソートで NlogN
    """

    
    N,Q=MI()
    xst2=[]#x,ごとに，Dがどの範囲なら引っかかるか(s~t)
    xi=[[0,0]for _ in range(N)]
    for i in range(N):
        s,t,x=MI()
        xst2.append([x,s-x,t-x])
        xi[i]=[x,i]
    xi.sort()
    
    
    D=[0]*Q
    for i in range(Q):
        D[i]=I()
        
    inf=10**10
    ans=[inf]*(Q+4)#すこし多めにとっておく
    nxt=[0]*(Q+4)#次に見るべき番号
    for i in range(Q+4):
        nxt[i]=i+1
        
    """
    print(xi)
    print(xst2)"""
    
    
    for i in range(N):
        ii=xi[i][1]
        xx=xst2[ii][0]
        
        #0-index
        ss=bisect.bisect_left(D,xst2[ii][1])
        tt=bisect.bisect_left(D,xst2[ii][2])
        j=ss
        while j<tt:
            if ans[j]==inf:
                ans[j]=xx
            jj=j
            j=nxt[j]
            nxt[jj]=tt#次ここにきたら，ttのところまで移動するようにしておく
        """print(ii,xst2[ii][1],xst2[ii][2],xx,ss,tt)
        print(ans)
        print(nxt)"""

    
        
    for i in range(Q):
        res=ans[i]
        if res==inf:
            print(-1)
        else:
            print(res)
            
        
    
        

main()



Measured memory_bytes: 124404
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define PI 3.14159265358979323846264
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    long double h,m,a,b,x;
    cin>>a>>b>>h>>m;
    x = (h/12)*(2*PI) + (PI/6)*(m/60)- (m/60)*(2*PI);
    x = abs(x);
    //cout<<x<<'\n';
    x = min(x,2*PI-x);
    cout<<fixed<<setprecision(9)<<sqrt(a*a+b*b-2*a*b*cos(x))<<'\n';
}

Measured memory_bytes: 4180
#include<stdio.h>

int main() {
	int a, b,c,A,B;

	while (scanf("%d %d", &a, &b) != EOF) {
		A = a;
		B = b;
		while (b != 0) {
			c = a%b;
			a = b;
			b = c;
		}
		printf("%d %d\n", a, A / a*B);
	}
	return 0;
}


Measured memory_bytes: 1980
#include<bits/stdc++.h>
using namespace std;

typedef long long lint;
typedef long double louble;

const char lf = '\n';

template<typename T1,typename T2> inline T1 max(T1 a,T2 b){return a<b?b:a;}
template<typename T1,typename T2> inline T1 min(T1 a,T2 b){return a<b?a:b;}

namespace ae86
{
	const int bufl = 1<<15;
	
	char buf[bufl],*s=buf,*t=buf;
	
	inline int fetch()
	{
		if(s==t){t=(s=buf)+fread(buf,1,bufl,stdin);if(s==t)return EOF;}
		return *s++;
	}
	
	inline int ty()
	{
		int a=0,b=1,c=fetch();
		while(!isdigit(c))b^=c=='-',c=fetch();
		while(isdigit(c))a=a*10+c-48,c=fetch();
		return b?a:-a;
	}

	inline int ts(char *s)
	{
		int a=0,c=fetch();
		while(c<=32 && c!=EOF)c=fetch();
		while(c>32 && c!=EOF)s[a++]=c,c=fetch();
		s[a]=0;
		return a;
	}
}
using ae86::ty;
using ae86::ts;

const int _ = 2000007;

int na,nb,nn,tim;
char sa[_],sb[_];

void fuck(int now,int lef)
{
	for(int i=now+1;i<=now+lef;i++)
	{
		if(sa[i] || sb[i])
		{
			sa[now]=0,sb[now]=0,sa[i]++,sb[i]++;
			int a=i+1,b=a;
			if(sa[i]>1){while(sa[a])sa[a]=0,a++;sa[a]=1,sa[i]=0;}
			if(sb[i]>1){while(sb[b])sb[b]=0,b++;sb[b]=1,sb[i]=0;}
			if(sa[a] && sb[a])fuck(a,lef-i+now);
			if(sa[b] && sb[b])fuck(b,lef-i+now);
			return;
		}
	}
	sa[now]--,sb[now]--,sa[now+lef]++,sb[now+lef]++;
}

int main()
{
	ios::sync_with_stdio(0),cout.tie(nullptr);

	na=ty(),nb=ty(),tim=ty(),nn=max(na,nb);
	ts(sa),ts(sb);

	reverse(sa,sa+na),reverse(sb,sb+nb);
	for(int i=0;i<na;i++)sa[i]-='0';
	for(int i=0;i<nb;i++)sb[i]-='0';

	for(int i=nn-1;i>=0;i--)if(sa[i] && sb[i])fuck(i,tim);

	for(int i=nn+tim,a=0;i>=0;i--)if(a|=sa[i])cout<<char('0'+sa[i]);
	cout<<lf;
	for(int i=nn+tim,a=0;i>=0;i--)if(a|=sb[i])cout<<char('0'+sb[i]);
	cout<<lf;
	
	return 0;
}


Measured memory_bytes: 6144
mod = 998244353

SIZE = 2 * 10 ** 5 + 1
fact = [0] * SIZE
inv = [0] * SIZE
finv = [0] * SIZE
fact[0], fact[1] = 1, 1
inv[1] = 1
finv[0], finv[1] = 1, 1
for i in range(2, SIZE):
    fact[i] = fact[i - 1] * i % mod
    inv[i] = mod - inv[mod % i] * (mod // i) % mod
    finv[i] = finv[i - 1] * inv[i] % mod

def nCr(n, r):
    if n < 0 or r < 0 or n < r:
        return 0
    return fact[n] * (finv[r] * finv[n - r] % mod) % mod


n, m, k = map(int, input().split())

ans = 0
for x in range(k+1):
    pattern = nCr(n-1, x) * m * pow(m-1, n-x-1, mod) % mod
    ans = (ans + pattern) % mod

print(ans)


Measured memory_bytes: 32508
#include<stdio.h>
#include<algorithm>
using namespace std;
long long b[210000];
int main(){
	int a;scanf("%d",&a);
	long long at=0;
	for(int i=0;i<a;i++){
		int tmp;scanf("%d",&tmp);
		at+=tmp;
		b[i+1]=at;
	}
	for(int i=0;i<a;i++){
		b[a+i+1]=b[a]+b[i+1];
	}
	long long L=0;
	long long R=1000000000000000LL;
	while(L+1<R){
		long long M=(L+R)/2;
		bool ok=false;
		for(int i=0;i<a;i++){
			long long now=b[i];
			int nat=lower_bound(b,b+2*a,b[i]+M)-b;
			nat=lower_bound(b,b+2*a,b[nat]+M)-b;
			nat=lower_bound(b,b+2*a,b[nat]+M)-b;
			if(nat<=i+a){ok=true;break;}
		}
		if(ok)L=M;else R=M;
	}
	printf("%lld\n",L);
}

Measured memory_bytes: 2588
// WeirdBugsButOkay

# include <bits/stdc++.h>
 
# define ll long long
# define ld long double
# define pii pair <int,int>
# define pll pair <ll,ll>
# define mp make_pair
# define pb push_back
# define ff first
# define ss second
# define endl '\n'
 
using namespace std;

ll pow3(ll a, ll b, ll m = 1000000007)
{
    ll res = 1;
    while(b > 0)
    {
        if(b & 1)
            res = (res * a) % m;
        a = (a * a) % m;
        b >>= 1;
    }
    return res;
}

void solve()
{
    ll n;
    cin >> n;
    ll ans[n +  1] = {0};
    for(ll i = 2; i <= n; i++)
    {
        ll x;
        cin >> x;
        ans[x]++;
    }
    for(ll i = 1; i <= n; i++)
        cout << ans[i] << endl;
}

 
int main()
{
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    ll q = 1;
    //cin >> q;
    for(ll i = 0; i < q; i++)
    {
        solve();
    }
    return 0;
}

Measured memory_bytes: 5224
#include <bits/stdc++.h>
using namespace std;
const int N = 4005;
char s[3][N];
int ok[3][3][N], len[3]; // s[x].suffix = s[y].prefix 
int solve(int a,int b,int c) {
	int tot=len[a]+len[b]+len[c],ans=1e9;
	for(int x=0;x<=len[a];x++){
		if(ok[a][b][x]==0)continue;
		for(int y=0;y<=2000;y++){
			if(y<=len[b]&&ok[b][c][y]==0)continue;
			if(1+x+y<=len[a]&&ok[a][c][x+y]==0)continue;
			ans=min(ans, max(max(len[a],1+x+len[b]-1),1+x+y+len[c]-1));
			//printf("x=%d,y=%d\n", x,y);
			// [1, len[a]]
			// 	[1+x, x+len[b]]
			// 	 [1+x+y, x+y+len[c]]
		}
	}
	return ans;
}
int main() {
	for(int i=0;i<3;i++) {
		scanf("%s", s[i]+1);
		len[i] = strlen(s[i]+1);
	}
	for(int i=0;i<3;i++) {
		for(int j=0;j<3;j++){
			if (i==j) continue;
			int tmp=len[i];
			for(int x=0;x<=tmp;x++){
				bool flag=1;
				int p1=1+x, p2=1;
				while(1){
					if(p1>len[i]||p2>len[j])break;
					if(s[i][p1]!=s[j][p2]&&s[i][p1]!='?'&&s[j][p2]!='?'){
						flag=0; break;
					}
					p1++; p2++;
				}
				if(flag) ok[i][j][x]=1;
			}
		}
	}

	int ans=1e9;
	ans=min(ans,solve(0,1,2));
	ans=min(ans,solve(0,2,1));
	ans=min(ans,solve(1,0,2));
	ans=min(ans,solve(1,2,0));
	ans=min(ans,solve(2,0,1));
	ans=min(ans,solve(2,1,0));
	cout<<ans<<endl;
}

Measured memory_bytes: 384
#!/usr/bin/env python
# -*- coding: utf-8 -*-

def solve():
    n, d = map(int, input().split())
    xl = [[int(i) for i in input().split()] for _ in range(n)]
    ans = 0
    valid = set([i ** 2 for i in range(1, 200)])
    for i in range(n):
        for j in range(n):
            if i == j:
                continue
            s = 0
            for k in range(d):
                s += (xl[i][k] - xl[j][k]) ** 2
            if s in valid:
                ans += 1
    print(ans // 2)

if __name__=="__main__":
    solve()


Measured memory_bytes: 38384
#include <bits/stdc++.h>
using namespace std;

#define int long long
using ll = long long;
using ld = long double;
using intpair = pair<int, int>;
using intmap = map<int, int>;
using vi = vector<int>;
using vvi = vector<vector<int>>;
const int MOD = 1e9 + 7;
inline int mod (ll a, int m = MOD) { return (a % m + m) % m; }
inline bool bit (ll b, ll i) { return b & (1 << i); }
inline ll ceiv (ll a, ll b) { return (a + b - 1) / b; }
//struct Fast {Fast(){cin.tie(0);ios::sync_with_stdio(0);}} fast;

#define debug(x) cerr << #x << ": " << x << '\n'
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define reps(i, n, m) for (int i = (int)(n); i <= (int)(m); i++)
#define ALL(obj) (obj).begin(), (obj).end()
#define rALL(obj) (obj).rbegin(), (obj).rend()

template <class T, T (*operation)(T, T), T (*e)()>
class SegmentTree {
    vector<T> v;
    int n = 1;
    
public:
    SegmentTree(int size) {
        while(n < size) n <<= 1;
        v.resize(n << 1, e());
    }
    
    SegmentTree(const vector<T> &init_v) {
        n = 1;
        while(n < init_v.size()) n <<= 1;
        v.resize(n << 1, e());
        for(int i = 0; i < init_v.size(); i++) {
            v[n + i] = init_v[i];
        }
        for(int i = 2*n-2; i > 0; i -= 2) {
            v[i >> 1] = operation(v[i], v[i|1]);
        }
    }
    
    void update(int idx, int val) {
        idx += n;
        v[idx] = val;
        while(idx > 0) {
            idx >>= 1;
            v[idx] = operation(v[(idx << 1)|0], v[(idx << 1)|1]);
        }
    }
    
    T get(int l, int r) {
        T valL = e(), valR = e();
        for(l += n, r += n; l < r; l >>= 1, r >>= 1) {
            if(l & 1) valL = operation(valL, v[l++]);
            if(r & 1) valR = operation(v[--r], valR);
        }
        return operation(valL, valR);
    }
    
    T get_all() {
        return v[1];
    }
    
    T operator[](const int &i) const { return v[n + i]; }
};

int f(int a, int b) {
    return max(a, b);
}

int e() {
    return 0;
}

const int A_LIMIT = 300000;
SegmentTree<int, f, e> dp(A_LIMIT + 1);

signed main() {
    int n, k; cin >> n >> k;
    vi a(n);
    rep(i,n) cin >> a[i];
    
    for(int i = n-1; i >= 0; i--) {
        const int now = a[i];
        const int lower = max(0LL, now - k);
        const int upper = min(A_LIMIT + 1, now + k + 1);
        dp.update(now, dp.get(lower, upper) + 1);
    }
    
    cout << dp.get_all() << endl;
}

Measured memory_bytes: 13756
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>
#include <cmath>
#include <tuple>
#include <cstdio>
#include <bitset>
#include <sstream>
#include <iterator>
#include <numeric>
#include <map>
#include <cstring>
#include <set>
#include <functional>
#include <iomanip>

using namespace std;

#define DEBUG_ //!!提出時にコメントアウト!!
#ifdef DEBUG_
	#define dump(x)  cerr << #x << " = " << (x) << endl;
#else
	#define dump(x)  ;
#endif

#define equals(a,b) (fabs((a)-(b)) < EPS)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define SZ(x) ((int)(x).size())
#define pb push_back
#define eb emplace_back

//#define int long long

typedef long long LL;
typedef vector<int> VI;
typedef vector<LL> VL;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

template <typename T>
std::string printVector(const std::vector<T> &data)
{
    std::stringstream ss;
    std::ostream_iterator<T> out_it(ss, ", ");
    ss << "[";
    std::copy(data.begin(), data.end() - 1, out_it);
    ss << data.back() << "]";
    return ss.str();
}

template <typename T>
void print_array(const T &ary, int size){
    REP(i,size){
        cout << ary[i] << " ";
    }
    cout << endl;
}

const int MOD = 1e9+7;
const LL LINF = 1001002003004005006ll;
const int INF = 1001001001;
const double EPS = (1e-10);

signed main(int argc, char const *argv[])
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << setprecision(12);

    string S; cin >> S;
    int len = S.length();

    if(S=="hi" || S=="hihi" || S=="hihihi" || S=="hihihihi" || S=="hihihihihi"){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>

using namespace std;

const int MX = 51;

int a[MX], b[MX];

int main() {
	int n;
	ignore = scanf("%d", &n);
	for (int i = 0; i < n; i++) ignore = scanf("%d", a + i);
	for (int i = 0; i < n; i++) ignore = scanf("%d", b + i);
	
	for (int i = 0; i < n; i++)
		if (a[i] != b[i] && (b[i] > a[i] || b[i] >= a[i] - b[i])) {
			printf("%d\n", -1);
			return 0;
		}
	
	long long ans = 0;
	for (int k = 49; k > 0; k--) {
		bool ok = true;
		for (int i = 0; i < n; i++) {
			static bool f[MX];
			fill(f, f + MX, false);
			
			f[a[i]] = true;
			for (int x = 49; x > 0; x--)
				if (((ans >> x) & 1) == 1 || x < k)
					for (int i = x; i < MX; i++)
						f[i % x] = f[i % x] || f[i];
			
			ok = ok && f[b[i]];
		}
		
		if (ok == false) ans |= 1LL << k;
	}
	
	printf("%lld\n", ans);
	
	return 0;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

ll f(ll x){
    ll y;
    if(x&1){
        y = 0;
        if(!(x&(1<<1))) y |= 1;
    }
    else{
        y = x;
        if(x&(1<<1))
            y |= 1;
    }
    return y;
}

int main(){
    ll x, y=0;
    while(scanf("%lld%lld", &x, &y) != EOF){
        x--;
        x = f(x), y = f(y);
        printf("%lld\n", x^y);
    }

    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <inttypes.h>

int main(void) {
	int64_t N;
	int64_t le, greater;
	if (scanf("%" SCNd64, &N) != 1) return 1;
	le = 0; greater = N + 1;
	while (le + 1 < greater) {
		int64_t mid = le + (greater - le) / 2;
		if (mid * mid <= N) le = mid; else greater = mid;
	}
	printf("%" PRId64 "\n", le * le);
	return 0;
}


Measured memory_bytes: 128
#include<stdio.h>
int main(){
    int ss, h, m, s;
    scanf("%d",&ss);
    h = ss / 3600;
    m = (ss-h*3600) / 60;
    s = ss-h*3600-m*60;
    printf("%d:%d:%d\n", h, m, s);
    return 0;
}

Measured memory_bytes: 592
# 2019/08/14

s=set(input())

if ('N' in s and 'S' not in s) or ('S' in s and 'N' not in s)\
   or ('W' in s and 'E' not in s) or ('E' in s and 'W' not in s):
   print('No')
else:
    print('Yes')




Measured memory_bytes: 2940
#include <bits/stdc++.h>
#define rep(i,n) for(ll i=0;i<(n);++i)
#define all(a) (a).begin(),(a).end()
using namespace std;
using Graph = vector<vector<int>>;
typedef pair<int,int> P;
typedef long long ll;

int main(){
    ll a, b, c, d, k; cin >> a >> b >> c >> d >> k;

    ll h1 = a*60 + b;
    ll h2 = c * 60 + d;

    ll t = abs(h1 - h2);

    cout << max(t - k,0ll) << endl;

}

Measured memory_bytes: 3636
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		long sum = 0;
		for(int i = 1; i < n+1; i++) {
			if(i%3!=0 && i%5!=0) {
				sum += i;
			}
		}
		System.out.println(sum);
		
	}
	
}


Measured memory_bytes: 27224
#include <bits/stdc++.h>
#define syosu(x) fixed<<setprecision(x)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef pair<double,double> pdd;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<string> vs;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<pll> vpll;
typedef pair<int,P> pip;
typedef vector<pip> vip;
const int inf=1<<30;
const ll INF=1ll<<60;
const double pi=acos(-1);
const double eps=1e-9;
const ll mod=1e9+7;
const int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};

ll N;

class Set{
	public:
	vpll a;
	void Add(ll u,ll v){a.push_back({u,v});}
	vpll Fix(){
		vpll b,c;
		for(auto p:a){
			ll L=p.first,R=p.second;
			if(L>=N) b.push_back({L-N,R-N});
			else if(R>=N){
				b.push_back({L,N-1});
				b.push_back({0,R-N});
			}
			else b.push_back({L,R});
		}
		sort(b.begin(),b.end());
		ll L,R=-1;
		for(auto p:b){
			if(R<p.first){
				if(R>=0) c.push_back({L,R});
				L=p.first;R=p.second;
			}
			else R=max(R,p.second);
		}
		c.push_back({L,R});
		for(auto &p:c) p={p.first*2,p.second*2};
		return c;
	}
	bool Check(ll x){
		for(auto p:a) if(p.first<=x&&x<p.second) return 1;
		return 0;
	}
	void Open(){
		for(auto p:a) cout<<p.first<<' '<<p.second<<endl;
	}
};

const int M=1000005;
ll n,q,x,y;
Set st[M];

int main(){
	cin>>n>>q>>x>>y;
	x--;y--;
	N=n/2;
	st[q-1].Add(y,y+1);
	for(int i=q-1;i>0;i--){
		vpll tmp=st[i].Fix();
		for(auto p:tmp) st[i-1].Add(p.first,p.second);
	}
//for(int i=0;i<q;i++){st[i].Open();cout<<endl;}
	if(!st[0].Check(x/2)&&!st[0].Check(x/2+N)){
		cout<<-1<<endl;
		return 0;
	}
	for(int i=0;i<q;i++){
		if(st[i].Check(x/2)){
			cout<<x%2<<endl;
			x=x/2;
		}
		else{
			cout<<(x+1)%2<<endl;
			x=x/2+N;
		}
	}
}


Measured memory_bytes: 55100
#include <bits/stdc++.h>
#define int long long
#define MOD 1000000007
using namespace std;

int n,a[300010];

signed main()
{
	ios::sync_with_stdio(false);
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	int ans=0ll;
	for(int i=1;i<=60;i++){
		int cnt=0;
		for(int j=1;j<=n;j++) if(a[j]&(1ll<<(i-1))) cnt++;
		ans=ans+(((1ll<<(i-1))%MOD)*((cnt*(n-cnt))%MOD))%MOD;
		if(ans>=MOD) ans-=MOD;
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 2560
#include <iostream>
using namespace std;
typedef long long ll;
int main(void){
    int n,p,e=0;
    cin>>n>>p;
    for(int i=0;i<n;i++){
        int a;
        cin>>a;
        if(a%2==0)e++;
    }
    if(e==n&&p==1){
        cout<<0<<endl;
    }else{
        ll a=1;
        for(int i=0;i<n;i++){
            a*=2;
        }
        if(e<n)a/=2;
        cout<<a<<endl;
    }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define all(c) c.begin(),c.end()
#define init(c) memset(c,0,sizeof c)
#define S second
#define F first
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
const int N=20000005;
int n,k,x,t,a,b,m;
string s;
vi v;
 
void solve(){
	cin >> n;
	for(int i=1;i<=n;i++){
		int cnt = 0;
		for(int x=1;x*x<=i;x++){
			for(int y=1;y*y<=i;y++){
				for(int z=1;z*z<=i;z++){
					int cur = x*x+y*y+z*z+x*y+y*z+z*x;
					if(cur==i)cnt++;
					if(cur > i)break;
				}
			}
		}
		cout << cnt<<endl;
	}	
 
}
 
int main(){
	
	t=1;
	while(t--){
		solve();
	}
	
	return 0;
}

Measured memory_bytes: 3564
#include <bits/stdc++.h>
using namespace std;

int main(){
  int A, B, i, cnt = 0;
  string s;
  cin >> A >> B;

  for ( i = A; i < B + 1; i++)
  {
    s = to_string(i);
    if (s[0] == s[4] && s[1] == s[3])
    {
      cnt ++;
    }
  }

  cout << cnt << endl;
}

Measured memory_bytes: 3636
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
using namespace std;
int main()
{
	char N[20];
	int up[20],suf[20];
	scanf("%s",N);
	int sum=0,ans=0,l=strlen(N);
	suf[l]=0;
	for(int i=0;i<l;i++){
		sum+=N[i]-'0';
		ans=sum;
	}
	for(int i=l-1;i>=0;i--){
		suf[i]=suf[i+1]+'9'-N[i];
	}
	for(int i=0;i<strlen(N);i++){
		ans=max(ans,sum-1+suf[i+1]);
	}
	printf("%d\n",ans);
	
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
    int A, B, C, D, N, ans=0;
    vector<int> V(3);
    char tmp, tmp2;
    string S, S2;
    bool flag=true;
    
    cin >> N;
    
    ans = N/3;
    cout << ans << endl;

    // if(S[1]==S[2] &&(S[0]==S[1] | S[2]==S[3]))
    // 	cout << "Yes" <<endl;
    // else
    // 	cout << "No" <<endl;

    // string S;
    // cin >>S;
    // cout << S + "pp"<<endl;
    // if((N%500)-A>0)
    // 	puts("No");
    // else
    // 	puts("Yes");
}



Measured memory_bytes: 256
using static System.Math;
using static System.Console;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System;

namespace AtCoder
{
    class Program
    {
        private static long mod = 1000000007;
        static void Main(string[] args)
        {
            var n = long.Parse(ReadLine());
            var line = ReadLine().Split(' ').Select(value => long.Parse(value)).ToArray();

            var list = new LinkedList<long>();

            for(var i = 0; i < line.Length; i++)
            {
                if(i % 2 == 0)
                {
                    list.AddLast(line[i]);
                }
                else
                {
                    list.AddFirst(line[i]);
                }
            }

            List<long> answer = null;

            if(line.Length % 2 == 1)
            {
                answer = list.Reverse().ToList();
            }
            else
            {
                answer = list.ToList();
            }

            for(var i = 0; i < answer.Count; i++)
            {
                Write(answer[i]);
                if(i != answer.Count - 1)
                {
                    Write(" ");
                }
            }
            WriteLine();
        }
    }
}


Measured memory_bytes: 59008
// Problem : E - Tr/ee
// Contest : AtCoder Regular Contest 103
// URL : https://atcoder.jp/contests/arc103/tasks/arc103_c
// Memory Limit : 1024 MB
// Time Limit : 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

#include "bits/stdc++.h"
using ll = long long;
using namespace std;
#define size(x) (int)x.size()

const int N = 1e6 + 1, mod = 1e9 + 7;

string s, t;
int r = 1, sz[N];
vector<int> adj[N];
vector<pair<int, int>> v;

void dfs(int v, int p) {
	sz[v] = 1;
	for (auto u : adj[v]) {
		if (u == p) {
			continue;
		}
		dfs(u, v);
		sz[v] += sz[u];
	}
}

int main() { cin.tie(0)->sync_with_stdio(0);
	cin >> s;
	int n = size(s);
	for (int i = 2; i <= n; i++) {
		v.push_back({r, i});
		if (s[i - 2] == '1') {
			r = i;
		}
	}
	for (auto x : v) {
		int u = x.first, v = x.second;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	dfs(1, 0);
	for (auto x : s) {
		t += '0';
	}
	for (auto x : v) {
		int v = x.second;
		t[sz[v] - 1] = '1';
		t[n - sz[v] - 1] = '1';
	}
	if (s != t) {
		return cout << -1, 0;
	}
	for (auto x : v) {
		cout << x.first << ' ' << x.second << '\n';
	}
}


Measured memory_bytes: 36420
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define INFLL 0x3f3f3f3f3f3f3f3fLL
#define MOD 1000000007
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define eb emplace_back
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pint;
typedef pair<ll,ll> pll;
typedef tuple<int,int,int> tint;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef vector<ull> vull;
typedef vector<pint> vpint;
int dx[8]={0,0,-1,1,1,1,-1,-1};
int dy[8]={-1,1,0,0,1,-1,1,-1};
const int SIZE=100050;
int main(){
    //freopen("tst.txt","r",stdin);freopen("sans.txt","w",stdout);
	int N;
	cin>>N;
	vint X,Y,H;
	for(int i=0;i<N;i++){
		int x,y,h;
		cin>>x>>y>>h;
		X.pb(x);
		Y.pb(y);
		H.pb(h);
	}
	for(int x=0;x<=100;x++){
		for(int y=0;y<=100;y++){
			int height=-1;
			bool flag=0;
			for(int i=0;i<N;i++){
				if(H[i]==0)
					continue;
				if(height==-1)
					height=H[i]+abs(X[i]-x)+abs(Y[i]-y);
				else{
					if(height!=H[i]+abs(X[i]-x)+abs(Y[i]-y))
						flag=1;
				}
			}
			for(int i=0;i<N;i++){
				if(H[i]==0){
					if(height-abs(X[i]-x)-abs(Y[i]-y)>0)
						flag=1;
				}
			}
			if(flag)
				continue;
			else{
				cout<<x<<" "<<y<<" "<<height<<endl;
				return 0;
			}
		}
	}
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
	string res;
	res = "";
	for(int i = 0; i < 3; ++i){
		for(int j = 0; j < 3; ++j){
			char c;
			cin>>c;
			if(i == j){
				res += c;
			}
		}
	}
	cout<<res<<endl;
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
using namespace std;

const int MAX = 50;
int n, m;
int a[MAX], b[MAX];
bool graph[MAX][MAX];
bool visited[MAX];

void dfs(int v){
  visited[v] = 1;
  for (int v2 = 0; v2 < n; ++v2){
    if (!graph[v][v2]) continue;
    if (visited[v2]) continue;
    dfs(v2);
  }
}

int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  cin >> n >> m;
  
  for (int i = 0; i < m; ++i){
    cin >> a[i] >> b[i];
    --a[i]; --b[i];
    graph[a[i]][b[i]] = 1; graph[b[i]][a[i]] = 1;
  }
  
  int ans = 0;

  for (int i = 0; i < m; ++i){
    graph[a[i]][b[i]] = 0; graph[b[i]][a[i]] = 0;
    
    for (int j = 0; j < n; ++j) visited[j] = 0;
    dfs(0);
    
    bool bridge = 0;
    for (int j = 0; j < n; ++j){
      if (!visited[j]) bridge = 1;
    }
    if (bridge) ++ans;
    graph[a[i]][b[i]] = 1; graph[b[i]][a[i]] = 1;
  }
  cout << ans << '\n';

  return 0;
}

Measured memory_bytes: 256
# -*- coding: utf-8 -*-

def main():


    N, K = map(int, input().split())
    D = list(map(int, input().split()))

    numList = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

    num = set()
        
    for i in numList:
        if i not in D:
            num.add(i)
    

    for i in range(N, N * 10 + 1):
        setI = set(int(x) for x in list(str(i)))
        if len(num | setI) <= len(num):
            ans = i
            break
                
    print(ans)


if __name__ == "__main__":
    main()

Measured memory_bytes: 9076
#include<bits/stdc++.h>
using namespace std;
 
int N;
int A[100010];
long long ans = 1,mem = 1;
 
int main()
{
    scanf("%d",&N);
    for(int i = 0; i < N; i++)scanf("%d",A + i);
 
    for(int i = 0; i < N; i++)
    {
        ans *= 3;
        if(A[i] % 2 == 0)mem *= 2;
    }
    printf("%lld\n",ans - mem);
    return 0;
}

Measured memory_bytes: 256
#!/usr/bin/env python3
import sys

def divisor(n): #nの約数を全て求める
    i = 1
    table = []
    while i * i <= n:
        if n%i == 0:
            table.append(i)
            table.append(n//i)
        i += 1
    table = sorted(list(set(table)))
    return table
def keta(i):
    return len(str(i))

def solve(N: int):
    yakusuu = divisor(N)
    answer = 11
    LEN = len(yakusuu)
    for i in range(LEN):
        answer = min(answer,max(keta(yakusuu[i]),keta(yakusuu[LEN-1-i])))
    print(answer)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    solve(N)

if __name__ == '__main__':
    main()


Measured memory_bytes: 3188
n,a,b = map(int,input().split())
s = input()

for i in s:
    if i=='a':
        if a > 0:
            print('Yes')
            a-=1
        elif b > 0:
            print('Yes')
            b-=1
        else:
            print('No')
    elif i=='b':
        if b > 0:
            print('Yes')
            b-=1
        else:
            print('No')
    else:
        print('No')

Measured memory_bytes: 4016
n,k,q = gets.chomp.split(" ").map{|i|i = i.to_i}
arr=[]
q.times do|i|
  arr << gets.chomp.to_i
end
a = Array.new(n, 0)

arr.each do|elm|
  a[elm-1] += 1
end 
#m = a.max
#pp a
#pp arr
#puts m
a.each do|hito|
  if k+(hito-q) <= 0 then
    puts "No"
  else 
    puts "Yes"
  end
end


Measured memory_bytes: 3836
#include <stdio.h>

int main(void)
{
  int n, n_500, n_5, fun_500, fun_5;
  scanf("%d", &n);
  n_500 = (n / 500);
  n_5 = (n - n_500 * 500) / 5;
  fun_500 = n_500 * 1000;
  fun_5 = n_5 * 5;
  printf("%d", fun_500 + fun_5);
  return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int max_n=100005;
int n,a[max_n];
int main()
{
    scanf("%d",&n);
    bool zero=false;
    ll sum=0;
    int c=0;
    int mv=0x3f3f3f3f;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",a+i);
        sum+=abs(a[i]);
        mv=min(mv,abs(a[i]));
        if(a[i]<0)c++;
        if(a[i]==0)zero=true;
    }
    if(!zero&&c%2==1)sum-=mv*2;
    printf("%lld\n",sum);
    return 0;
}


Measured memory_bytes: 640
import sys

h, w, m = map(int, input().split())
row = [0]*h
col = [0]*w
bomb = set()
for x in sys.stdin.readlines():
    H, W = map(int, x.split())
    bomb.add((H-1, W-1))
    row[H-1] += 1
    col[W-1] += 1

maxrow = max(row)
maxcol = max(col)
ans = maxcol + maxrow - 1
p, q = [], []
for i in range(h):
    if row[i] == maxrow:
        p.append(i)
for i in range(w):
    if col[i] == maxcol:
        q.append(i)

for i in p:
    for j in q:
        if (i, j) not in bomb:
            print(ans + 1)
            exit()
print(ans)


Measured memory_bytes: 83492
#include <bits/stdc++.h>
#define ll long long int
#define yorn(f) cout<<((f)?"Yes":"No")<<endl;
#define YORN(f) cout<<((f)?"YES":"NO")<<endl;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(), (x).end()
#define put(x) cout << x << endl;
#define println(x) cout << x << endl;
using namespace std;
int main()
{
    int n;
    string s;
    cin >> n >> s;
    rep(i, s.size()) {
        int x = s[i] - 'A';
        x = (x + n) % ('Z' - 'A' + 1);
        char c = x + 'A';
        cout << c; 
    }
    cout << endl;
    return 0;
}

Measured memory_bytes: 3616
#include <bits/stdc++.h>
using namespace std;

template< typename T >
void divisor(T n, vector<T>& divisors) {
    T root_n = (T)sqrt(n);
    for (int i = 1; i <= root_n; ++i) {
        if (n % i == 0) {
            divisors.push_back(i);
            if (n / i != i) divisors.push_back(n / i);
        }
    }
}

int main() {
    long long n;
    cin >> n;
    vector<long long> divisors;
    divisor(n, divisors);
    int cnt = 0;
    for (auto k : divisors) {
        if (k == 1) continue;
        long long tempn = n;
        while (tempn % k == 0) tempn /= k;
        if (tempn % k == 1) cnt++;
    }
    divisors.clear();
    divisor(n-1, divisors);
    for (auto k : divisors) {
        if (k == 1) continue;
        if (n % k == 1) cnt++;
    }
    cout << cnt << endl;
}


Measured memory_bytes: 3560
//FINISH WHAT YOU START!
#include<bits/stdc++.h>

#define fileIO freopen("input.txt", "r", stdin); freopen("output1.txt", "w", stdout);
#define IOS ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
#define inf ((long long) 1e18 )
#define mod 1000000007
#define int long long
#define endl '\n'
#define pb push_back
#define eb emplace_back
#define all(x) (x).begin(),(x).end()
#define debug(x) cout << '>' << #x << ':' << x << '\n';
#define debug2(x,y) cout << '>' << #x << " = " << x << " & "<< #y <<" = "<< y << '\n';

using namespace std;

const int N = 2e5 + 7;
vector<int> a[N];
int vis[N];
int count1 = 0;

void dfs(int s) {
	vis[s] = 1;
	count1++;
	for (auto i : a[s]) {
		if (!vis[i])
			dfs(i);
	}
	return ;
}

int32_t main() {
	IOS
#ifndef ONLINE_JUDGE
	fileIO
#endif
	auto start = std::chrono::high_resolution_clock::now();
	int test;
	test = 1;
	// cin >> test;
	while (test--) {
		int n, m;
		cin >> n >> m;
		map<pair<int, int>, int> mp;
		for (int i = 0 ; i < m ; i++) {
			int x, y;
			cin >> x >> y;
			if (mp.find({x, y}) != mp.end() or mp.find({y, x}) != mp.end())
				continue;
			mp[ {x, y}]++;
			mp[ {y, x}]++;
			a[x - 1].eb(y - 1);
			a[y - 1].eb(x - 1);
		}
		memset(vis, 0, sizeof(vis));
		vector<int> v;
		for (int i = 0 ; i < n; i++) {
			if (!vis[i]) {
				count1 = 0;
				dfs(i);
				v.eb(count1);
			}
		}
		sort(all(v));
		int ans = 0;
		int mi = 0;
		for (int i = 0 ; i < v.size() ; i++) {
			ans += (v[i] - mi);
			mi = v[i];
		}
		cout << ans << endl;
	}

	auto stop = std::chrono::high_resolution_clock::now();
	auto duration = std::chrono::duration_cast<std::chrono::nanoseconds>(stop - start);

	cerr << "Time taken : " << ((long double)duration.count()) / ((long double) 1e9) << "s " << endl;

	return 0;
}


Measured memory_bytes: 47448
#include <bits/stdc++.h>

using namespace std;

#define FOR(i,a,b) for(int i = (a); i < (b); ++i)
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()

inline int toInt(string s) {int v; istringstream sin(s);sin>>v; return v;}

typedef long long ll;


 
int main(){

    ll N;
    cin >> N;

    vector<ll> X(N), Y(N);

    for(int i = 0; i < N; i++){
        cin >> X[i];
        Y[i] = X[i];
    }
    
    sort(X.begin(), X.end());

    int mid = N / 2 - 1;
    for(int i = 0; i < N; i++){

        if(Y[i] <= X[mid]) cout << X[mid+1] << endl;
        else cout << X[mid] << endl;
    }

    return 0;
}

Measured memory_bytes: 5376
#include <cstdio>
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <map>
#include <set>

#define ll long long
#define pll pair<ll, ll>

#define reps(i, f, n) for (int i = (f); i < (int)(n); i++)
#define rep(i, n) reps(i, 0, n)

const int INF = 1111111111;

using namespace std;

void init()
{
}

const ll N2 = 1111111;

bool isPrime[N2];

void solve()
{
	ll n;
	cin >> n;

	rep(i, N2)
	{
		isPrime[i] = true;
	}
	isPrime[0] = false;
	isPrime[1] = false;

	reps(i, 2, N2)
	{
		if (isPrime[i] == false)
		{
			continue;
		}
		for (int j = i * 2; j < N2; j += i)
		{
			isPrime[j] = false;
		}
	}

	ll ans = 0;

	rep(i, N2)
	{
		if (isPrime[i] == false)
		{
			continue;
		}

		ll div = i;
		for (int j = 0;; j++)
		{
			if (n % div == 0)
			{

				//cout << "div " << n << " " << div << " " << i << endl;
				ans += 1;
				n /= div;
				div *= i;
			}
			else
			{
				break;
			}
		}
	}

	if (n >= N2)
	{
		ans++;
	}

	cout << ans << endl;
}

int main()
{
	init();
	solve();
}


Measured memory_bytes: 4272
s=list(map(int,input()))
x=s[0]*10+s[1]
y=10*s[2]+s[3]
if x>12 and y>0 and y<=12:
  print("YYMM")
elif x>0 and x<=12 and y>12:
  print("MMYY")
elif x<=12 and x>0 and y>0 and y<=12:
  print("AMBIGUOUS")
elif x==0 and y<=12 and y>0:
  print("YYMM")
elif y==0 and x>0 and x<=12:
  print("MMYY")
else:
  print("NA")

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
int main(){
    ios::sync_with_stdio(false);
    int n;
    cin>>n;
    int AC=0,WA=0,TLE=0,RE=0;
    rep(i,n) {
        string s;
        cin >> s;
        if(s == "AC") AC++;
        else if(s == "WA") WA++;
        else if(s=="TLE") TLE++;
        else if(s=="RE") RE++;
    }
    cout << "AC x " << AC << endl;
    cout << "WA x " << WA << endl;
    cout << "TLE x " << TLE << endl;
    cout << "RE x " << RE << endl;
}


Measured memory_bytes: 3652
import java.util.Scanner;

public class Main {

    public static final int MOD = 1000000007;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int x = Integer.parseInt(sc.next());
        int y = Integer.parseInt(sc.next());
        if ((x + y) % 3 != 0) {
            System.out.println(0);
            return;
        }
        int n = (x + y) / 3;
        long ans = comb(x - n + y - n, x - n > y - n ? x - n : y - n);
        System.out.println(ans);

    }

    // 繰り返し２乗法
    private static long modPow(long n, int p) {
        long res = 1;
        long a = n;
        for (a %= MOD; p > 0; a = a * a % MOD, p >>= 1) {
            if ((p & 1) > 0) {
                res = res * a % MOD;
            }
        }
        return res;
    }

    // 逆元
    private static long modInv(long a) {
        return modPow(a, MOD - 2);
    }

    // 二項係数
    private static long comb(long n, long r) {
        long ret = 1;
        for (long i = 0; i < r; i++) {
            ret *= n - i;
            ret %= MOD;
            ret *= modInv(i + 1);
            ret %= MOD;
        }
        return ret;
    }
}

Measured memory_bytes: 23636
#include <algorithm>
#include <iostream>
#include <string>
#include <random>
#include <cassert>
#include <cstring>
#include <chrono>

using namespace std;

typedef long long ll;

int main()
{
  ll n, m;
  cin >> n >> m;

  vector<ll> coef(n - 1);
  coef[0] = 1;
  int l = 1, r = n - 2;
  while (l <= r) {
    coef[l] = coef[l - 1] + 1;
    coef[r] = coef[l];
    l++;
    r--;
  }

  vector<vector<ll>> dp(n, vector<ll>(n));

  dp[0][0] = 1;
  for (int count = 1; count <= n - 1; ++count) {
    for (int prevValue = 0; prevValue < n; ++prevValue) {
      for (int curValue = 0; curValue < n; ++curValue) {
        int newValue = prevValue + coef[count - 1] * curValue;
        if (newValue >= n) {
          break;
        }
        dp[count][newValue] += dp[count - 1][prevValue];
      }
    }
    for (int value = 0; value < n; ++value) {
      dp[count][value] %= m;
    }
  }

  ll result = 0;
  for (int value = 0; value < n; ++value) {
    result += (n - value) * dp[n - 1][value];
    result %= m;
  }

  cout << result << endl;

  return 0;
}


Measured memory_bytes: 197248
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<int, int>;
using vint = vector<int>;
using vvint = vector<vint>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vchar = vector<char>;
using vvchar = vector<vchar>;
using vp = vector<P>;
using vpp = vector<pair<P, P>>;
using vvp = vector<vp>;

#define rep(i, n) for (int i = 0; i < n; ++i)
#pragma region Debug
istream &operator>>(istream &is, P &a)
{
    return is >> a.first >> a.second;
}
ostream &operator<<(ostream &os, const P &a) { return os << "(" << a.first << "," << a.second << ")"; }

template <typename T>

void view(const std::vector<T> &v)
{
#ifndef ONLINE_JUDGE
    for (const auto &e : v)
    {
        std::cout << e << " ";
    }
    std::cout << std::endl;
#endif
}
template <typename T>
void view(const std::vector<std::vector<T>> &vv)
{
    for (const auto &v : vv)
    {
        view(v);
    }
}
#pragma endregion

long double z = 0;
int main()
{
    long double n, k;
    cin >> n >> k;
    long double p = max(z, (n - k) / n);
    cout.precision(15);
    // std::cout.setf(std::ios::fixed, std::ios::floatfield);

    long double q = 0.;
    for (ll i = 1; i <= min(k, n); i++)
    {
        long double now = 1.0;
        ll j = i;
        while (j < k)
        {
            j *= 2;
            now /= 2.0;
        }
        // cout << fixed << i << " " << now << endl;
        q += now;
    }
    q /= n;
    p += q;

    cout << fixed << p << endl;

    return 0;
}

Measured memory_bytes: 3748
#pragma GCC optimize("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define mod 1000000007
string s;
int d[100005][13];
signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> s;
	d[0][0] = 1;
	s = '~' + s;
	for(int i = 1 ; i < s.size() ; i ++){
		if(s[i] == '?'){
			for(int prev = 0 ; prev < 13 ; prev ++)
				for(int cur = 0 ; cur < 10 ; cur ++)
					d[i][(prev * 10 + cur)%13] = (d[i][(prev * 10 + cur)%13] + d[i - 1][prev])%mod;
		}
		else{
			for(int prev = 0 ; prev < 13 ; prev ++)
				d[i][(prev * 10 + (s[i] - '0'))%13] = (d[i][(prev * 10 + (s[i] - '0'))%13] + d[i - 1][prev])%mod;
		}
	}
	cout << d[s.size() - 1][5];
}


Measured memory_bytes: 10604
#include <iostream>
using namespace std;

int main(){

 int a, b;
 char op;

 while(1) {
  cin >> a >> op >> b;

  if (op == '+') cout << a + b << "\n";
  else if (op == '-') cout << a - b << "\n";
  else if (op == '*') cout << a * b << "\n";
  else if (op == '/') cout << a / b << "\n";
  else break;
 }

 return 0;
}

Measured memory_bytes: 1160
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,m,x,y;
    cin>>n>>m>>x>>y;
    int a[n];
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    int b[m];
    for(int i=0;i<m;i++){
        cin>>b[i];
    }
    bool flag=false;
    sort(a,a+n);
    sort(b,b+m);
    for(int i=a[n-1]+1;i<=b[0];i++){
        if(i>x && i<=y){flag=true;}
    }
    if(flag){cout<<"No War"<<endl;}
    else cout<<"War"<<endl;
}

Measured memory_bytes: 256