akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define MP make_pair
#define PII pair<int, int>
#define PLL pair<ll, ll>
#define PLI pair<ll, int>
#define PIL pair<int, ll>
#define STR string
#define Fst first
#define Snd second
#define SHN 1e9
#define LSHN 1e18
using namespace std;
ll n,m;
ll a[200010];
map<ll, int> mp;
ll res;
int main()
{
	cin >>n>>m;
	for (int i=1;i<=n;i++) cin >>a[i],a[i]--;
	for (int i=1;i<=n;i++) a[i]=(a[i]+a[i-1])%m;
	for (int i=0;i<=n;i++)
	{
		if (i>=m) mp[a[i-m]]--;
		res+=mp[a[i]];
		mp[a[i]]++;
	}
	cout <<res;
	return 0;
} 

Measured memory_bytes: 14336
n,m = map(int,input().split())
li = []
for i in range(n):
    a,b = map(int,input().split())
    li.append((a,b))
li.sort()
ans = 0
for val,cnt in li:
    if m <= cnt:
        ans += m * val
        break
    else:
        ans += val * cnt
        m -= cnt
print(ans)


Measured memory_bytes: 16892
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define il inline
#define outy printf("Yes\n")
#define outn printf("No\n")
#define outf printf("First\n")
#define outs printf("Second\n")
#define FOR(a,b,c) for(int a=b;a<=c;a++)
#define FORD(a,b,c) for(int a=b;a>=c;a--)
#define FORL(a,b) for(int a=head[b];a;a=nxt[a])
#define in(a)  a=read()
#define in2(a,b)  a=read(),b=read()
#define in3(a,b,c)  a=read(),b=read(),c=read()
#define in4(a,b,c,d)  a=read(),b=read(),c=read(),d=read()
#define inl(a)  a=readl()
#define inl2(a,b)  a=readl(),b=readl()
#define inl3(a,b,c)  a=readl(),b=readl(),c=readl()
#define inl4(a,b,c,d)  a=readl(),b=readl(),c=readl(),d=readl()
#define out(a) printf("%d\n",a)
#define out2(a,b) printf("%d %d\n",a,b)
#define out3(a,b,c) printf("%d %d %d\n",a,b,c)
#define out4(a,b,c,d) printf("%d %d %d %d\n",a,b,c,d)
#define outl(a) printf("%lld\n",a)
#define outl2(a,b) printf("%lld %lld\n",a,b)
#define outl3(a,b,c) printf("%lld %lld %lld\n",a,b,c)
#define outl4(a,b,c,d) printf("%lld %lld %lld %lld\n",a,b,c,d)
#define clr(x) memset(x,0,sizeof(x))
inline int read(){
    char c;int s=0,t=1;
    while(!isdigit(c=getchar()))if(c=='-')t=-1;
    do{s=s*10+c-'0';}while(isdigit(c=getchar()));
    return s*t;
}
inline ll readl(){
    char c;ll s=0;int t=1;
    while(!isdigit(c=getchar()))if(c=='-')t=-1;
    do{s=s*10+c-'0';}while(isdigit(c=getchar()));
    return s*t;
}
/*------------------------------------------------------------*/
#define mod 1000000007
#define maxn 1
/*------------------------------------------------------------*/
int n,m;
int main(){
	in2(n,m);
	int ans=0;
	FOR(i,1,n){
		int c;
		in(c);
		ans+=min(c,m-c)*2;
	}
	out(ans);
	
}


































Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i < (n); i++)
#define lower(s) transform(s.begin(), s.end(), s.begin(), ::tolower)
using namespace std;
using ll = long long;
int INF = 1001001001;

int main() {
  int n;
  cin >> n;
  int ans = 1000 * ((n+1000-1)/1000) - n;
  cout << ans << endl;
  return 0;
}

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

using namespace std;

#define int long long

#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define repi(i, a, b) for (int i = (int)(a); i < (int)(b); ++i)

template <typename T> T gcd(T m, T n) { return n == 0 ? m : gcd(n, m % n); }
template <typename T> T lcm(T m, T n) { return n * m / gcd(n, m); }
template <typename T> T fact(T n) { return (n == 0 ? 1 : n * fact(n - 1)); }
template <typename T> T modpow(T a, T e, T m) { return (e == (T)0 ? 1 : ((a % m) * modpow((a % m), e - 1, m)) % m); }

constexpr int MOD = 1e9 + 7;

signed main(void) {
  string s, t;
  cin >> s >> t;
  cout << t << s << endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<set>
#define P pair<int, int>
#define MAX_N 100050

using namespace std;

class Unionfind{
    private:
    int par[MAX_N];
    int rank[MAX_N];
    set<int> size;
    public:
    Unionfind() {
        for(int i=0;i < MAX_N;i++){
            par[i] = i;
            rank[i] = 0;
        }
    };

    int find(int x){
        if(par[x] == x){
            return x;
        }else{
            return par[x] = find(par[x]);
        }
    };

    void unite(int x,int y){
        x = find(x);
        y = find(y);
        if(x == y) return;
        if(rank[x] < rank[y]){
            par[x] = y;
        }else{
            par[y] = x;
            if(rank[x] == rank[y]) rank[x]++;
        }
    };

    bool same(int x,int y){
        return find(x) == find(y);
    };

    int group(int n){
        for(int i=1;i <= n;i++){
            size.insert(find(i));
        }
        return size.size();
    }

    int Size(int x){
        return rank[find(x)]+1;
    }
};

int main(){
    int n,m;
    cin >> n >> m;
    int p[n+1];
    Unionfind u;
    for(int i=1;i <= n;i++){
        cin >> p[i];
    }
    int x[m+1],y[m+1];
    for(int i=1;i <= m;i++){
        cin >> x[i] >> y[i];
        u.unite(x[i],y[i]);
        
    }

    int ans = 0;

    for(int i=1;i <= n;i++){
        if(u.find(i) == u.find(p[i])) ans++;
    }
    
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 5416
#include<iostream>
#include<vector>

int main(){
	//標準入力
	size_t n;
	std::cin>>n;
	std::vector<int> A(n,0);
	for(size_t i=0;i<n;i++){
		std::cin>>A[i];
	}
	//処理
	//奇数が偶数個なら全て消せる。奇数を全て偶数にし、それからすべての偶数を１つずつ消していけばいい。
	//奇数が奇数個なら上と同様のアルゴリズムで消せない。そして対称律が成立するので、どんな方法でも消せない。
	size_t count=0;
	for(size_t i=0;i<n;i++){
		if(A[i]%2==1){
			count++;
		}
	}

	//出力
	std::cout<<((count%2==0)?"YES":"NO")<<std::endl;

	return 0;
}


Measured memory_bytes: 640
n=int(input())
a=list(map(int,input().split()))

ans1=1 #all
ans2=1 #odd
for i in range(n):
    j=3 #j:all
    k=0 #k:odd
    if (a[i]-1)%2==1:
        k+=1
    if a[i]%2==1:
        k+=1
    if (a[i]+1)%2==1:
        k+=1
    ans1*=j
    ans2*=k
print(ans1-ans2)


Measured memory_bytes: 9192
#include <bits/stdc++.h>
using namespace std;
typedef long long   signed int LL;
typedef long long unsigned int LU;
#define incID(i, l, r) for(LL i = (l)    ; i <  (r); ++i)
#define incII(i, l, r) for(LL i = (l)    ; i <= (r); ++i)
#define decID(i, l, r) for(LL i = (r) - 1; i >= (l); --i)
#define decII(i, l, r) for(LL i = (r)    ; i >= (l); --i)
#define inc(i, n)  incID(i, 0, n)
#define inc1(i, n) incII(i, 1, n)
#define dec(i, n)  decID(i, 0, n)
#define dec1(i, n) decII(i, 1, n)
#define inID(v, l, r) ((l) <= (v) && (v) <  (r))
#define inII(v, l, r) ((l) <= (v) && (v) <= (r))
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
#define  ALL(v)  v.begin(),  v.end()
#define RALL(v) v.rbegin(), v.rend()
template<typename T> bool setmin  (T & a, T b) { if(b <  a) { a = b; return true; } else { return false; } }
template<typename T> bool setmax  (T & a, T b) { if(b >  a) { a = b; return true; } else { return false; } }
template<typename T> bool setmineq(T & a, T b) { if(b <= a) { a = b; return true; } else { return false; } }
template<typename T> bool setmaxeq(T & a, T b) { if(b >= a) { a = b; return true; } else { return false; } }
LL mo(LL a, LL b) { assert(b > 0); a %= b; if(a < 0) { a += b; } return a; }
LL fl(LL a, LL b) { assert(b > 0); return (a > 0 ? a / b : (a - b + 1) / b); }
LL ce(LL a, LL b) { assert(b > 0); return (a < 0 ? a / b : (a + b - 1) / b); }
template<typename T> T gcd(T a, T b) { return (b == 0 ? a : gcd(b, a % b)); }
template<typename T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
#define bit(b, i) (((b) >> (i)) & 1)
#define BC __builtin_popcountll
#define SC static_cast
#define SI(v) SC<int>(v.size())
#define SL(v) SC<LL >(v.size())
#define RF(e, v) for(auto & e: v)
#define ef else if
#define UR assert(false)

// ---- ----

int a, b;

int main() {
	cin >> a >> b;
	
	cout << max({ a + b, a - b, a * b}) << endl;
	
	return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <vector>

using namespace std;

int a[100000];
int c[100000];
int d[100000][3];
vector <int> v[100000];

void dfs(int x, int y, int z) {
    int i;
    
    if (c[x] == 0) c[x] = z;
    
    if (y == 0 || y <= a[x]) return;
    
    a[x] = y;
    
    for (i = 0; i < v[x].size(); i++) dfs(v[x][i], y - 1, z);
}

int main() {
    int n, m, q, i;
    
    scanf("%d %d", &n, &m);
    
    for (i = 0; i < m; i++) {
        int x, y;
        
        scanf("%d %d", &x, &y);
        
        x--;
        y--;
        
        v[x].push_back(y);
        v[y].push_back(x);
    }
    
    scanf("%d", &q);
    
    for (i = 0; i < q; i++) scanf("%d %d %d", &d[i][0], &d[i][1], &d[i][2]);
    
    for (i = q - 1; i >= 0; i--) dfs(d[i][0] - 1, d[i][1], d[i][2]);
    
    for (i = 0; i < n; i++) printf("%d\n", c[i]);
    
    return 0;
}


Measured memory_bytes: 8440
code = input()

wc = {}
for i in code:
    if i in wc:
        wc[i] = wc[i] + 1
    else:
        wc[i] = 1

for key in wc.keys():
    if int(wc[key]) != 2:
        print("No")
        exit(0)
print("Yes")



Measured memory_bytes: 2940
#include<bits/stdc++.h>
#define mod 1000000007
using namespace std;
typedef long long int ll;
#define f(i, n) for(int i = 0; i < n; ++i)
#define pb push_back

void input(){
    ll n; cin >> n;
    vector<ll>a(n);
    f(i, n) cin >> a[i];
    multiset<int>s;
    int ans = 0;
    for(int i = 0; i < n; ++i){
       int x = a[i];
       auto it = s.find(x);
       if(it != s.end()){
        if(it != s.begin()){
           --it;
           s.erase(it);
           s.insert(x);
        }else{
            ++ans;s.insert(x);
        }
       }else{
            auto it = s.upper_bound(x);
            if(it == s.begin()){
                ++ans;s.insert(x);
            }else{
              --it;
              s.erase(it);
              s.insert(x);
            }
       }
    }
    cout << ans <<"\n";
}
int main()
{
 input();
 return 0;
}


Measured memory_bytes: 5760
#include <bits/stdc++.h>
using namespace std;
#define MOD 998244353
#define INF 0x3f3f3f3f3f3f3f3f
#define LL long long
#define MX 55
struct Node
{
    LL x, y;
}pt[MX];

int k, n;

bool check(LL xa ,LL xb ,LL ya, LL yb,int p)
{
    if (pt[p].x>=xa&&pt[p].x<=xb&&
        pt[p].y>=ya&&pt[p].y<=yb) return 1;
    return 0;
}

LL func(int u, int v)
{
    LL res = INF;
    for (int i=1;i<=n;i++)
    {
        for (int j=1;j<=n;j++)
        {
            LL minx = min( min( min(pt[u].x,pt[v].x), pt[i].x) ,pt[j].x);
            LL maxx = max( max( max(pt[u].x,pt[v].x), pt[i].x) ,pt[j].x);
            LL miny = min( min( min(pt[u].y,pt[v].y), pt[i].y) ,pt[j].y);
            LL maxy = max( max( max(pt[u].y,pt[v].y), pt[i].y) ,pt[j].y);
            int tot = 0;
            for (int z=1;z<=n;z++)
            {
                if (check(minx,maxx,miny,maxy,z)) tot++;
            }
            if (tot>=k)
                res = min(res, (maxy-miny)*(maxx-minx));
        }
    }
    return res;
}

int main()
{
    scanf("%d%d",&n,&k);
    for (int i=1;i<=n;i++)
        scanf("%lld%lld",&pt[i].x, &pt[i].y);
    LL area = INF;
    for (int i=1;i<=n;i++)
        for (int j=1;j<=n;j++)
        {
            //if (j==i) continue;
            area = min(area, func(i,j));
        }
    printf("%lld\n",area);
    return 0;
}


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

int main() {
	int n;
	cin >> n;
	if (n == 0) { // p(n) = 2
		cout << 1 << endl;
	} else if (n == 1) { // p(n) = 3
		cout << 2 << endl;
	} else if (n == 2) { // p(n) = 5
		cout << 1 << endl;
	} else {
		cout << 0 << endl;
	}
}


Measured memory_bytes: 3116
#include<iostream>
#include<cstdio>
#include<algorithm>
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define ROF(i,a,b) for(int i=a;i>=b;i--)
using namespace std;
typedef long long ll;
const int N=1010,M=500500;
const ll INF=1e18;
int n,m,fa[N],o[N];
ll ans,X,D,w[N],c[N],t[N],f[M];
bool cmp(int x,int y){return w[x]*c[y]>w[y]*c[x];}
int main(){
	//freopen("1.in","r",stdin);
	scanf("%d%lld%lld",&n,&X,&D);
	scanf("%lld",&c[1]);w[1]=1;t[1]=n;
	FOR(i,2,n) scanf("%lld%lld",&c[i],&fa[i]),w[i]=1,t[i]=min(D,(ll)n);
	ROF(i,n,2) w[fa[i]]+=w[i],c[fa[i]]+=c[i];
	FOR(i,1,n) m+=t[i]*w[i];
	FOR(j,1,m) f[j]=INF;
	FOR(i,1,n)ROF(j,m,0)FOR(k,1,min(t[i],j/w[i]))
		f[j]=min(f[j],f[j-k*w[i]]+1ll*k*c[i]);
	ROF(j,m,1) f[j-1]=min(f[j-1],f[j]);
	FOR(i,1,n) t[i]=i==1?INF:D-t[i],o[i]=i;
	sort(o+1,o+n+1,cmp);
	FOR(W,0,m){
		int Y=X-f[W];ll Z=0;
		if(Y<0) break;
		FOR(i,1,n){
			int u=o[i],s=min(t[u],Y/c[u]);
			Y-=s*c[u];Z+=1ll*s*w[u];
		}
		ans=max(ans,Z+W);
	}
	cout<<ans<<'\n';
} 

Measured memory_bytes: 768
#include <bits/stdc++.h>
#define all(a) a.begin(), a.end()
using namespace std;
 
int N;
vector<int> v;


int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cin >> N;
  v.resize(N+1, INT_MAX);
  vector<int> dup(N+1);
  v[0] = 0;
  for(int i=1; i<=N; ++i){ cin >> v[i];
     dup[i] = v[i];
  }
  sort(all(v));
//  for(int i=1; i<=N; ++i)
    // cout << "i: " << i << " v[i]: " << v[i] << "\n";
  int f = v[N/2 + 1];
  int s = v[N/2];
  //cout << " sefsofdi: " << f << " sfgs: " << s << "\n";
  for(int i=1; i<=N; ++i){
    if(dup[i] >= f){
      cout << s << "\n";
    }
    else
      cout << f << "\n";
  }
  return 0;
}



Measured memory_bytes: 3840
N,M=(int(x) for x in input().split())
a=[int(input()) for i in range(M)]

x=[0]*(N+1)
j=0
if N!=0:
    x[0]=1
if N>1 and M!= 0 and a[0]==1:
    j+=1
else:
    x[1]=1

for i in range(2,N+1): 
    if j==M or i!=a[j]:
        x[i]=x[i-1]+x[i-2]
    else:
        x[i]=0
        j+=1
print(int(x[N]%(1000000007)))


Measured memory_bytes: 460020
import fractions

n, s = map(int, input().split())
x = list(map(int, input().split()))
x.append(s)
m = min(x)
xr = [e - m for e in x]
ans = xr[0]
for i in range(1, n+1):
    ans = fractions.gcd(ans, xr[i])
print(ans)

Measured memory_bytes: 16280
#coding:utf-8

N = int(input())
result_list = []
'''
for i in range(N):
    i = str(i)
    if '1' in i or '2' in i or '4' in i or '6' in i or '8' in i or '9' in i or '0' in i:
        continue
    if '7' in i and '5' in i and '3' in i:
        result_list.append(i)
print(len(result_list))
'''
current = 3


def get_next(current_str):
    '''
    i:str
    '''
    if current_str[-1] == '3':
        current_str = current_str[:-1] + '5'
    elif current_str[-1] == '5':
        current_str = current_str[:-1] + '7'
    elif current_str[-1] == '7':
        if len(current_str) != 1:
            current_str = get_next(current_str[:-1]) + '3'
        else:
            current_str = '33'
    return current_str


count = 0
while current <= N:
    current_str = str(current)
    current = int(get_next(current_str))
    if '7' in current_str and '5' in current_str and '3' in current_str:
        count += 1

print(count)

Measured memory_bytes: 3064
#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
#include <math.h>
#include <algorithm>
#include <deque>
#include <queue>
#include <climits>
#include <set>
using namespace std;
#define ll long long
#define ull unsigned long long
#define ve vector
#define umap unordered_map
#define iter iterator

void solve() {
    string s;cin>>s;
    cout<<s[0]<<s.length()-2<<s[s.length()-1];
}

int main() {
    solve();
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
 
/*
#include <ext/pb_ds/assoc_container.hpp> // Common file 
#include <ext/pb_ds/tree_policy.hpp> 
#include <functional> // for less 
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag, 
		   tree_order_statistics_node_update> oset;
*/
 
void __print(int x) {cout << x;}
void __print(long x) {cout << x;}
void __print(long long x) {cout << x;}
void __print(unsigned x) {cout << x;}
void __print(unsigned long x) {cout << x;}
void __print(unsigned long long x) {cout << x;}
void __print(float x) {cout << x;}
void __print(double x) {cout << x;}
void __print(long double x) {cout << x;}
void __print(char x) {cout << '\'' << x << '\'';}
void __print(const char *x) {cout << '\"' << x << '\"';}
void __print(const string &x) {cout << '\"' << x << '\"';}
void __print(bool x) {cout << (x ? "true" : "false");}
 
template<typename T, typename V>
void __print(const pair<T, V> &x) { __print(x.first); cout << ','; __print(x.second); }
template<typename T>
void __print(const T &x) {int f = 0; for (auto &i: x) cout << (f++ ? "," : ""), __print(i); }
void _print() {cout << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cout << ", "; _print(v...);}
 
#ifndef ONLINE_JUDGE
#define d(x...) cout << "[" << #x << "] = ["; _print(x)
#else
#define d(x...)
#endif
 
#define IO            ios::sync_with_stdio(false);cin.tie(0);
//#define clock()       std::chrono::high_resolution_clock::now()
//#define duration(x,y) std::chrono::duration_cast<std::chrono::milliseconds>(y-x).count()
 
#define ll            long long
#define pi            pair<int,int>
#define pii           pair<pi,int>
#define pl            pair<ll,ll>
#define vi            vector<int>
#define vl            vector<ll>
#define vll           vector<vl>
#define vs            vector<string>
#define vb            vector<bool>
#define vii           vector<vector<int>>
#define vpi           vector<pi>
#define vpl           vector<pl>
#define pb            push_back
#define mp            make_pair
#define eb            emplace_back
#define ff            first
#define ss            second
#define fo(i,val,n)   for(int i=val;i<n;i++)
#define rfo(i,val,j)  for(int i=val;i>=j;i--)
#define all(x)        x.begin(),x.end()
#define inf           INT_MAX
#define endl          '\n'
	
const int N=2e5+7;
const int MOD=1e9+7;
//const int MOD=998244353;

int main(){
 	
	IO

	string s,t,a,b;
	cin>>s;
	int n = s.size();

	t = s;
	reverse(all(t));
	if(t!=s){
		cout<<"No";
		return 0;
	}

	a = s.substr(0,(n-1)/2);
	b = a;
	reverse(all(b));
	//d(a); d(b);
	if(a!=b){
		cout<<"No";
		return 0;
	}

	a = s.substr((n+3)/2 - 1);
	b = a;
	reverse(all(b));
	//d(a); d(b);
	if(a!=b){
		cout<<"No";
		return 0;
	}

	cout<<"Yes";
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#define foor for(int i=0;i<n;i++)
#define en endl;
#define el else
#define co cout
#define in int
#define yn co<<"Yes"<<en el co<<"No"<<en
#define ci cin
int s = 0;
using namespace std;
int main() {
	in a;
	ci >> a;
	co<<(a+1)/2<<en
}

Measured memory_bytes: 256
x, y = map(int, input().split())
a = [1, 3, 5, 7, 8, 10, 12]
b = [4, 6, 9, 11]
c = [2]
if (x in a and y in a) or (x in b and y in b) or (x in c and y in c):
    print('Yes')
else:
    print('No')


Measured memory_bytes: 3060
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define ll long long int
#define pb push_back
#define eb emplace_back
#define xx first
#define yy second
#define INF 0x3f3f3f3f

using namespace std;
using namespace __gnu_pbds;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef tree<int,null_type, less<int>,rb_tree_tag,tree_order_statistics_node_update>   ordered_set;
const int N=2e5+1, mod=1e9+7;

int main(){
	ios_base::sync_with_stdio(0);	cin.tie(0);
	int n,m;
	cin>>n>>m;
	int x;
	priority_queue<int> pq;
	for(int i=0;i<n;i++){
		cin>>x;
		pq.push(x);
	}
	while(m--){
		x=pq.top();
		pq.pop();
		pq.push(x/2);
	}	
	ll res=0;
	while(!pq.empty()){
		res+=pq.top();
		pq.pop();
	}
	cout<<res;	
}


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

using namespace std;
#define ll long long
#define ld long double

#define endl '\n'
#define FAST                      \
    ios_base::sync_with_stdio(0); \
    cin.tie(0);                   \
    cout.tie(0);
const ll mod = 1000000007;
const double PI = 3.141592653589793238463;
const int MAXN = 1e5 + 5;
ll fastPow(ll x, ll b)
{
    if (b == 0)
        return 1;
    else if (!(b & 1))
    {
        return fastPow(x * x, b / 2);
    }
    else
        return x * fastPow(x * x, (b - 1) / 2);
}
//__builtin_popcount ();
struct def
{
    string h = ">";
};
int main()
{
    FAST
       int x;
  cin>>x;
  if(x<1200)
    cout<<"ABC"<<endl;
  else
    cout<<"ARC"<<endl;

    return 0;
}

Measured memory_bytes: 256
n, m = map(int, input().split())
a, b = zip(*(map(int, input().split()) for _ in range(n)))
c = sorted(zip(a, b))
cost = 0
rest = m
for a, b in c:
    if rest >= b:  # bを足すだけの余裕があるとき
        cost += a * b
        rest -= b
    else:  # b本は買えないとき買えるのはm本
        cost += a * rest
        break
print(cost)


Measured memory_bytes: 58328
N, M = map(int, input().split())

L_list = []
R_list = []
for i in range(M):
  L, R = map(int, input().split())
  L_list.append(L)
  R_list.append(R)

L = max(L_list)
R = min(R_list)

if R < L:
  print(0)
else:
  print(R - L + 1)

Measured memory_bytes: 10996
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+7;
int q,t,f;
string se,s,con;
char c;
int main()
{
    cin>>s;
    cin>>q;
    
   for(int i=0;i<q;i++){
        cin>>t;
        if(t==1) swap(se,s);
        else{
            cin>>f>>c;
            if(f==1){
               se+=c;
            }
            else{
                s=s+c;
            }
        }
    }
    reverse(se.begin(),se.end());
    
    cout<<se<<s;
    
    return 0;
}


Measured memory_bytes: 1496
#include<bits/stdc++.h>
#define range(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,b) for(int i = 0; i < (b); i++)
#define all(a) (a).begin(), (a).end()
#define debug(x) cout << "debug " << x << endl;
const int INF = 100000000;
using namespace std;

int main(){
    int n;
    long long a[100][100];
    cin >> n;
    rep(i,n){
        rep(j,n){
            cin >> a[i][j];
        }
    }
    long long sum = 0;
    rep(i,n - 1){
        range(j,i + 1,n){
            sum+=min(a[i][j], a[j][i]);
        }
    }
    cout << sum << endl;
}

Measured memory_bytes: 3160
#include <stdio.h>
#include <math.h>

int main(void) {
    int pat[4], h, i, j, v, minv;
    char *r, buf[9];

    while (1) {
        for (i = 0, h = 0, minv = 255;
             i < 8 && (r = gets(buf)) != NULL; i++) {
            for (j = 0, v = 0; j < 8; j++) {
                v <<= 1;
                v += buf[j] == '1';
            }
            if (v > 0) {
                pat[h++] = v;
                if (v < minv) minv = v;
            }
        }
        if (r == NULL) return 0;
        gets(buf); // blank line;
        for (i = 0; i < h; i++) {
            pat[i] /= minv;
        }
        if (h == 1) {
            puts("C");
        }
        else if (h == 4) {
            puts("B");
        }
        else if (h == 2) {
            if (pat[0] == 2) {
                puts("E");
            }
            else if (pat[1] == 2) {
                puts("G");
            }
            else {
                puts("A");
            }
        }
        else {
            if (pat[0] == 1) {
                puts("D");
            }
            else {
                puts("F");
            }
        }
    }

    return 0;
}

Measured memory_bytes: 524
A = []
n, q = gets.chomp.split(" ").map &:to_i
n.times {
    A.push([])
}

q.to_i.times{
    choice,  t, x = gets.chomp.split(" ").map &:to_i
     case choice
     when 0
        A[t].push(x)
     when 1
        puts A[t].join(' ') 
     when 2
        A[t].clear
     end
}



Measured memory_bytes: 15492
def CountTriangles( A): 
  n = len(A); 
  A.sort();  
  count = 0; 
  for i in range(n - 1, 0, -1): 
        l = 0; 
        r = i - 1; 
        while(l < r): 
            if(A[l] + A[r] > A[i]): 
                count += r - l;  
                r -= 1;  
            else:  
                l += 1;  
  print(count)
n=int(input())
l=[int(x) for x in input().split()]
CountTriangles(l)
    
   
   
      



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

using namespace std;

int main()
{
    int n, a;
    set <int> s;

    cin >> n;

    for (int i = 0; i < n; i++)
    {
        cin >> a;
        
        s.insert(a);
    }

    if (s.size() == n)
        cout << "YES";
    else
        cout << "NO";

    cout << "\n";

    return 0;
}

Measured memory_bytes: 9600
#include <iostream>
#include <map>
#include <string>
#include <utility>
#include <list>
#include <math.h>
#include <vector>
#include <algorithm>
#include<iomanip>
#include <unordered_map> 
#include <queue>
 
using namespace std;
typedef long long ll;
typedef pair<int, int> pp;
 
#define MOD 1e9+7
 
 
int main() {
  int A, B, C, D;
  cin >> A >> B >> C >> D;
  
  for (int i = 0;; i++) {
    C = C - B;
    if (C <= 0) { cout << "Yes"; return 0; }
    A = A - D;
    if (A <= 0) { cout << "No"; return 0; }
  }

  //for float, double precision
  //cout << std::fixed << setprecision(15);
  return 0;
}



Measured memory_bytes: 3092
#include <bits/stdc++.h>
using namespace std;
 
int main()
{
int A;
cin >> A;
string N;
cin >> N;
int ans=0;
int chk=N.size();
int Rcountmin=0;
int Rcountmax=0;
int Wcountmin=0;
int Wcountmax=0;
for(int i=0; i<chk; i++)
{
    if(N.at(i)=='R') Rcountmin++;
    if(N.at(i)=='W') Wcountmin++;
}

for (int i=0; i<Rcountmin; i++)
{
    if(N.at(i)!='R')
    {
        ans++;
    }
}
for(int i=Rcountmin; i<chk; i++)
{
    if(N.at(i)!='W')
    {
        ans++;
    }
}

    cout << ans/2 << endl;
}

Measured memory_bytes: 3728
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <cmath>
using namespace std;

const double eps = 1e-9;
int N;
int a[20];
vector<double> v;

bool equals(double s, double t) {
  return fabs(s-t) < eps;
}

bool rec(int bx, int k, double lim) {
  if(k == N) return true;
  for(int b = bx; ; b += bx) {
    double newV = (double)abs(a[k]-b)/a[k];
    if(newV < lim || equals(newV, lim)) {
      if(rec(b, k+1, lim)) return true;
    } else {
      if(a[k] < b) break;
      else continue;
    }
  }
  return false;
}

double solve() {
  v.push_back(0.0);
  for(int m = 1; m <= 100000; ++m)
    for(int i = 0; i < N; ++i)
      v.push_back((double)m/a[i]);

  sort(v.begin(), v.end());

  int l = 0;
  int r = v.size();
  int ansi = 0;
  while(l < r) {
    int m = (l+r)/2;
    if(rec(1, 0, v[m])) ansi = r = m;
    else l = m+1;
  }
  return v[ansi];
}

int main() {
  cin >> N;
  for(int i = 0; i < N; ++i) cin >> a[i];
  printf("%.12f\n", solve());
  return 0;
}

Measured memory_bytes: 16000
#include <iostream>
#include <cstdio>
#include <cstring>
#include <list>
#include <vector>
#include <algorithm>
using namespace std;

void depthset(int node, int l[][2], int* depth, int* height, int current_depth)
{
    depth[node] = current_depth;
    current_depth++;
    int lheight = -1;
    int rheight = -1;
    if (l[node][0] != -1)
    {
        depthset(l[node][0], l, depth, height, current_depth);
        lheight = height[l[node][0]];
    }
    if (l[node][1] != -1)
    {
        depthset(l[node][1], l, depth, height, current_depth);
        rheight = height[l[node][1]];
    }
    height[node] = max(lheight, rheight) + 1;
    return;
}

int main(void)
{
    int n;
    cin >> n;
    int parent[n], sibling[n], degree[n], depth[n], height[n];
    int child[n][2];
    memset(parent, -1, sizeof(parent));
    memset(child, -1, sizeof(child));
    memset(height, 0, sizeof(height));
    memset(sibling, -1, sizeof(sibling));
    for (int i = 0; i < n; i++)
    {
        int id, left, right;
        cin >> id >> left >> right;
        child[id][0] = left;
        child[id][1] = right;
        int child_count = 0;
        if (left != -1)
        {
            parent[left] = id;
            sibling[left] = right;
            child_count++;
        }
        if (right != -1)
        {
            parent[right] = id;
            sibling[right] = left;
            child_count++;
        }
        degree[id] = child_count;
    }
    for (int i = 0; i < n; i++)
    {
        if (parent[i] == -1) depthset(i, child, depth, height, 0);
    }
    for (int i = 0; i < n; i++)
    {
        cout << "node " << i << ": parent = " << parent[i] << ", sibling = " << sibling[i] << ", degree = " << degree[i] << ", depth = " << depth[i] << ", height = " << height[i] << ", ";
        if (parent[i] == -1)
        {
            cout << "root\n";
        }
        else if (degree[i] == 0)
        {
            cout << "leaf\n";
        }
        else
        {
            cout << "internal node\n";
        }
    }
    return 0;
}


Measured memory_bytes: 3120
#include<bits/stdc++.h>
using namespace std;
 
#define all(a) a.begin(),a.end()
#define F first
#define S second
#define pb push_back
#define ll long long
#define vi vector<int>
#define pi pair<int,int>
#define mp make_pair
 
const int mod=1e9+7;
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
int mul(int a,int b){
	return ((a)*1ll*(b))%mod;
}
 
void add(int &a,int b){
	a+=b;
	if(a>=mod)a-=mod;
}
 
int sub(int a,int b){
	a-=b;
	if(a<0){
		a+=mod;
	}
	return a;
}
 
int powz(int a,int b){
	int res=1;
	while(b){
		if(b&1){
			res=mul(res,a);
		}
		b/=2;
		a=mul(a,a);
	}
	return res;
}
 
template <typename A, typename B>
istream& operator>>(istream& input,pair<A,B>& x) {
	input>>x.F>>x.S;
	return input;
}
 
template <typename A>
istream& operator>>(istream& input,vector<A>& x) {
	for(auto& i:x)
		input>>i;
	return input;
}
 
template<typename A>
ostream& operator<<(ostream& output,vector<A>& x) {
	for(auto& i:x)
		output<<i<<' ';
	return output;
}
 
const int N=1000002;

void solve(){
	int n,a,b;
	cin>>n>>a>>b;
	cout<<max((b-a)*1ll*(n-2)+1,0ll);
}
 
signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int tc=1;
	//~ cin>>tc;
	for(int _=0;_<tc;_++){
		//~ cout<<"Case #"<<_+1<<": ";
		solve();
		if(_!=tc-1)
		cout<<"\n";
	}
}


Measured memory_bytes: 256
#include<stdio.h>




int main(){
	
	
	int a,i,j,c,k,count,ans,ck;
	int d[150];
	int number[150]  ;
	int b[150][150];
	int bad[150];


	
	
	
	
	//  初期化	
	

	
			while(1){
	
	for(i = 0 ; i < 150 ; i++ ) d[i] = 0;
	for(i = 0 ; i < 150 ; i++ ) number[i] = 0;
	for(i = 0 ; i <  0  ;   i++  ){
		
		for(i = j ; i <  0  ;   j++  ){
			
			b[i][j] = 0;
		}
	}	
	for(i = 0 ; i < 150 ; i++ ) bad[i] = 0;
	
	count = 0;
	
	
	
	scanf("%d" , &a);
	if(a == 0) break;
	
	
	for(i = 0 ; i < a ; i++ ) bad[i] = 1;	
	
	for(i = 0 ; i <  a  ;   i++  ){
		
		 	scanf("%d" , &number[i]);
			for(j = 0 ; j < number[i] ; j++)  scanf("%d" , &b[i][j]);
	}
	
	
	
	scanf("%d" , &c);
	
	for(i = 0 ; i <  c  ;   i++  ) 	scanf("%d" , &d[i]);
	
	
		for(i = 0 ; i < 5 ; i++){
		
		for(j = 0 ; j < 5  ;   j++  ){
			
			
//			printf("b[%d][%d] = %d\n" ,i,j , b[i][j]);
			
		}
		}
	
			
			
	//
	
	
	for(i = 0 ; i < c ; i++){
		
		
		for(j = 0 ; j <  a  ;   j++  ){
			
			for(k = 0 ; k < number[j] ; k++){
				
				ck = 0;
				
				if(b[j][k]  == d[i]) {
					ck = 1;
					 break;
				}

				
				
			}
			
			if(ck == 0){
				 bad[j] = 0;
//				 printf("%d番目を0にします\n",j);
			}
			
		}
	}
	
//	printf("aの値は%d\n" , a);
	for(i = 0 ; i<a ; i++){
		
//		printf("%d\n" , bad[i]);
		if( bad[i] == 1){
			 count++;
			ans = i;
		}
		
			
	}
	
	if(count == 1 )  printf("%d\n" , ans+1);
	else printf("%d\n" , -1);
	
			
			
			
	
	
	
	}
	
	return 0;
	
}

Measured memory_bytes: 0
import sys
import math
input = sys.stdin.readline
MOD = 10**9 + 7

n, k = [int(item) for item in input().split()]
s = [int(item) for item in input().split()]
s.sort(reverse=True)
MAX_VAL = max(max(s), k)

dp = [[0] * (MAX_VAL + 1) for _ in range(n + 1)]
dp[0][k] = 1
for i, item in enumerate(s):
    for j in range(MAX_VAL + 1):
        if dp[i][j] == 0:
            continue
        # Apply item
        dp[i+1][j % item] += dp[i][j]
        dp[i+1][j % item] %= MOD
        # Put item afterwards
        dp[i+1][j] += dp[i][j] * (n - 1 - i)
        dp[i+1][j] %= MOD

ans = 0
for i, item in enumerate(dp[n]):
    ans += i * item
    ans %= MOD
print(ans)

Measured memory_bytes: 192024
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int INF = 1e9;
const ll LINF = 1e18;
template<class S,class T> ostream& operator << (ostream& out,const pair<S,T>& o){ out << "(" << o.first << "," << o.second << ")"; return out; }
template<class T> ostream& operator << (ostream& out,const vector<T> V){ for(int i = 0; i < V.size(); i++){ out << V[i]; if(i!=V.size()-1) out << " ";} return out; }
template<class T> ostream& operator << (ostream& out,const vector<vector<T> > Mat){ for(int i = 0; i < Mat.size(); i++) { if(i != 0) out << endl; out << Mat[i];} return out; }
template<class S,class T> ostream& operator << (ostream& out,const map<S,T> mp){ out << "{ "; for(auto it = mp.begin(); it != mp.end(); it++){ out << it->first << ":" << it->second; if(mp.size()-1 != distance(mp.begin(),it)) out << ", "; } out << " }"; return out; }

/*
 <url:http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2312>
 問題文============================================================
 =================================================================
 解説=============================================================
 ================================================================
 */

ll N,M,L;
ll Cost(ll a,ll b,vector<ll>& cusum){
    if(a > b) swap(a,b);
    return (cusum[b]-cusum[a-1])/L;
}
ll solve(){
    ll res = LINF;
    cin >> N >> M >> L;
    vector<ll> K(N),S(M);
    for(auto& in:K) {cin >> in;}
    for(auto& in:S) cin >> in;
    vector<ll> cusum(M+1,0);
    for(int i = 0; i < M;i++) cusum[i+1] += cusum[i] + S[i];
    sort(K.begin(),K.end());
    
    vector<vector<ll>> dp(N,vector<ll>(N,0));
    for(int j = 1; j < N;j++){
        for(int i = 0; i < j; i++){
            if(i == 0&& j == 1){
                dp[i][j] = Cost(K[i],K[j],cusum);
            }else if(i < j - 1){
                dp[i][j] = dp[i][j-1] + Cost(K[j-1],K[j],cusum);
            }else{
                dp[i][j] = LINF;
                for(int k = 0; k < i; k++){
                    dp[i][j] = min(dp[i][j],dp[k][i] + Cost(K[k],K[j],cusum));
                }
            }
        }
    }
    
    for(int k = 0; k < N-1;k++){
        res = min(res,dp[k][N-1]+Cost(K[k],K[N-1],cusum));
    }
    return res;
}
int main(void) {
    cin.tie(0); ios_base::sync_with_stdio(false);
    cout << solve() << endl;
    return 0;
}



Measured memory_bytes: 35856
# input
N = int(input())

# check
if N < 4:
    print("No")
else:
    for seven_n in range(0, N + 1, 7):
        if (N - seven_n) % 4 == 0 or N - seven_n == 0:
            print("Yes")
            exit(0)
    print("No")

Measured memory_bytes: 2940
import java.util.Scanner;

class Main {
    public static void main (String[] args) {
    Scanner sc = new Scanner (System.in);
    int a = sc.nextInt();
    int b = sc.nextInt();
    if (a < b) System.out.println("a < b");
    if (a > b) System.out.println("a > b");
    if (a == b) System.out.println("a == b");
}
}


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

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll N, K;
    cin >> N >> K;
    vector<ll> dices(N);
    for (int i = 0; i < N; i++)
    {
        cin >> dices.at(i);
    }
    ll diceSum = 0;
    for (int i = 0; i < K; i++)
    {
        diceSum += dices.at(i);
    }
    ll diceSumMax = diceSum;
    ll diceMaxLeftIndex = 0;
    for (int i = 1; i < N - K + 1; i++)
    {
        diceSum = diceSum + dices.at(i + K - 1) - dices.at(i - 1);
        if (diceSum > diceSumMax)
        {
            diceSumMax = diceSum;
            diceMaxLeftIndex = i;
        }
    }
    double answer = 0;
    for (int i = diceMaxLeftIndex; i < diceMaxLeftIndex + K; i++)
    {
        double dice = dices.at(i);
        answer += (dice + 1) / 2;
    }
    cout << fixed << setprecision(6) << answer << endl;
    return 0;
}


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

int main() {
    int N;
    cin>>N;
    int l=0, r=0;
    int ll=0, rr=0;
    string S;
    cin>>S;
    string ans="";
    for(int i=0;i<N;++i){
        if(S[i]=='('){
            l++;
        }
        else{
            if(l>0){
                l--;
            }
            else {
                r++;
            }
        }
    }
    for(int i=0;i<r;++i){
        ans += '(';
    }
    ans += S;
    for(int i=0;i<l;++i){
        ans += ')';
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 256
#include <algorithm>
#include <bitset>
#include <cassert>
#include <chrono>
#include <climits>
#include <cmath>
#include <complex>
#include <cstring>
#include <deque>
#include <functional>
#include <iostream>
#include <iomanip>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <cstdint>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
#define MP make_pair
#define PB push_back
#define inf 1000000007
#define rep(i,n) for(int i = 0; i < (int)(n); ++i)
#define all(x) (x).begin(),(x).end()

template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}
 
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;
}

ll dp[501][501][501];
ll cost[501][501];
int main(){
    ll n;
    cin >> n;
    rep(i,n){
        for(int j=0;j<n;j++){
            if(j==i)continue;
            cin >> cost[i][j];
        }
    }
    rep(i,n){
        rep(j,n){
            rep(k,n){
                dp[i][j][k] = (1LL<<60);
            }
        }
    }
    dp[0][0][0] = 0;
    for(int k=0;k<n-1;k++){
        vector<ll>g(n+1);
        vector<ll>f(n+1);
        for(int i=1;i<n;i++){
            g[i] = cost[k+1][i-1] + g[i-1];
        }
        for(int i=k;i>=0;i--){
            f[i] = cost[i][k+1] + f[i+1];
        }
        for(int s=0;s<=k;s++){
            for(int t=s;t<=k;t++){
                // ll tmp = 0;
                // for(int i=t+1;i<=k;i++){
                //     tmp += cost[i][k+1];
                // }
                // for(int i=0;i<s;i++){
                //     tmp += cost[k+1][i];
                // }
                chmin(dp[k+1][s][t],dp[k][s][t] + g[s]+f[t+1]);
                // chmin(dp[k+1][s][t],dp[k][s][t] + tmp);
                // tmp = 0;
                // for(int i=0;i<=t;i++){
                //     tmp += cost[k+1][i];
                // }
                // chmin(dp[k+1][t+1][k],dp[k][s][t] + tmp);
                chmin(dp[k+1][t+1][k],dp[k][s][t] + g[t+1]);
                if(t==k){
                    chmin(dp[k+1][s][k+1],dp[k][s][k] + f[s]);    
                }
            }
        }
    }
    ll res = (1LL<<60);
    rep(i,n){
        rep(j,n){
            chmin(res,dp[n-1][i][j]);
        }
    }
    cout << res << endl;
    return 0;
}

Measured memory_bytes: 984704
#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define SZ(x) ((int)x.size())
#define L(i,u) for (register int i=head[u]; i; i=nxt[i])
#define rep(i,a,b) for (register int i=(a); i<=(b); i++)
#define per(i,a,b) for (register int i=(a); i>=(b); i--)
using namespace std;
typedef long long ll;
typedef unsigned int ui;
typedef pair<int,int> Pii;
typedef vector<int> Vi;
template<class T> inline void read(T &x){
	x=0; char c=getchar(); int f=1;
	while (!isdigit(c)) {if (c=='-') f=-1; c=getchar();}
	while (isdigit(c)) {x=x*10+c-'0'; c=getchar();} x*=f;
}
template<class T> inline void umin(T &x, T y){x=x<y?x:y;}
template<class T> inline void umax(T &x, T y){x=x>y?x:y;}
inline ui R() {
	static ui seed=416;
	return seed^=seed>>5,seed^=seed<<17,seed^=seed>>13;
}
const int N = 202000,inf=0x3f3f3f3f;
int n,a[N],b[N],c[N],v[N],dp[N],tot;Vi mrk[N];bool vis[N];
void getid(int &x){x=lower_bound(c+1,c+n+1+1,x)-c;}
void add(int p, int x){while(p<=n+1)v[p]+=x,p+=p&-p;}
int query(int p){int res=0;while(p)res+=v[p],p-=p&-p;return res;}
int main() {
	read(n);rep(i,1,n)read(a[i]),read(b[i]);
	rep(i,1,n+1)read(c[i]);
	sort(c+1,c+n+1+1);
	rep(i,1,n)getid(a[i]),getid(b[i]);
//	rep(i,1,n)printf("%d:%d %d\n",i,a[i],b[i]);
	//suffix add
	rep(i,1,n+1)add(i,-1);
	rep(i,1,n)add(a[i],1);//b[i]+ a[i]- (b[i]<a[i]) [b..a-1]
	rep(i,1,n)if(a[i]>b[i])mrk[a[i]-1].pb(i);
	priority_queue<Pii,vector<Pii>,greater<Pii> >h1;
	multiset<Pii>Set;
	per(i,n+1,1){
		rep(j,0,SZ(mrk[i])-1)h1.push(Pii(b[mrk[i][j]],a[mrk[i][j]]-1));
		while(query(i)<-1){
			if(h1.empty()||h1.top().fi>i){tot=inf;break;}
			Set.insert(h1.top());add(h1.top().fi,1);add(h1.top().se+1,-1);h1.pop();tot++;
		}
	}
	rep(i,0,n+1)mrk[i].clear();rep(i,1,n)if(a[i]>b[i]){
		Pii qaq=Pii(b[i],a[i]-1);
		multiset<Pii>::iterator it=Set.find(qaq);
		if(it!=Set.end())Set.erase(it);
		else mrk[b[i]].pb(i);
	}
	priority_queue<Pii>h;
	rep(i,0,n+1){
		rep(j,0,SZ(mrk[i])-1)h.push(Pii(a[mrk[i][j]]-1,b[mrk[i][j]]));
		while(query(i)<0){
			if(h.empty()||h.top().fi<i){tot=inf,dp[i]=tot;break;}
			add(h.top().se,1);add(h.top().fi+1,-1);h.pop();tot++;
		}
		dp[i]=tot;
	}
//	rep(i,0,n+1)printf("%d:%d\n",i,dp[i]);
	int q;read(q);while(q--){
		int d,e;read(d);read(e);getid(d);getid(e);
		int res=-1;
		umax(res,1+n-dp[d-1]);
		umax(res,n-dp[e-1]);
		printf("%d\n",res);
	}
	return 0;
}


Measured memory_bytes: 16000
#include "bits/stdc++.h"

using namespace std;

int main()
{
   string w[7]={"thu", "fri", "sat", "sun" ,"mon","tue", "wed"};
   int x;
   cin >>x;
   int n=x%7;
   cout << w[n]<< endl;
    return 0;
}



Measured memory_bytes: 3176
#include <bits/stdc++.h>
#include <math.h>
#define _GLIBCXX_DEBUG
#define _LIBCPP_DEBUG 0

using namespace std;
#define ll long long
#define rep(i,n) for (int i = 0; i < n; i++)
#define rrep(i,n) for (int i = n-1; i >= 0; i--)
#define MOD (1000000007)
#define vi vector<int>
#define vl vector<ll>
#define vb vector<bool>
#define vvi vector<vi>
#define vvl vector<vl>
#define pii pair<int, int>
#define pli pair<ll, int>a
#define pb push_back

#define mp make_pair
#define all(a) (a).begin(),(a).end()

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; }

ll gcd(ll a, ll b) {
    if (b == 0) return a;
    else return gcd(b, a % b);
}

ll keta(ll n){
  string s = to_string(n);
  ll num = s.size();
  return num;
}

const ll INF = 1LL << 60;

const int dh[4] = {1,0,-1,0};
const int dw[4] = {0,1,0,-1};

struct Edge{
  int to;
  int weight;
  Edge(int t, int w) : to(t), weight(w){}
};
using Graph = vector<vector<Edge>>;
using P = pair<ll, int>;

class UnionFind{
public:
  vi Parent;
  UnionFind(int n){
    Parent = vi(n,-1);
  }

  int root(int a){
    if(Parent[a] < 0) return a;
    return Parent[a] = root(Parent[a]);
  }

  int size(int a){
    a = root(a);
    return -Parent[a];
  }

  bool merge(int a, int b){
    a = root(a);
    b = root(b);
    if(a == b) return false;

    if(a < b) swap(a,b);
    Parent[a] += Parent[b];
    Parent[b] = a;

    return true;
  }

  bool issame(int a, int b){
    return root(a) == root(b);
  }
};

int main(){
  string s; cin >> s;
  ll ans = 0;
  ll cnt = 0;
  rep(i,s.size()) {
    if(s[i] == 'B') cnt++;
    else ans += cnt;
  }
  cout << ans << endl;
}

Measured memory_bytes: 640
if __name__ == '__main__':
    N, K = map(int, input().split())
    H = [int(input()) for _ in range(N)]
    H.sort()
    dis_min = 10**9
    for i in range(N-K+1):
        dis_min = min(dis_min, H[i+K-1]-H[i])
        
    print(dis_min)

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

int main(void)
{
    int n, m;
    int l, r;
    int maxL = 1, minR = 100000;
    // int *l, *r;
    cin >> n >> m;
    // l = new int[m];
    // r = new int[m];
    for (int i = 0; i < m; i++) {
        cin >> l >> r;
        maxL = max(l, maxL);
        minR = min(r, minR);
    }
    int x = minR - maxL + 1;
    if (x < 0) x = 0;
    cout << x << endl;

    return 0;
}



Measured memory_bytes: 256
import java.util.Scanner;
 
public class Main {
 
	public static final MyScanner in = new MyScanner();
 
	public static void main(String[] args) {
 
		int N  = in.nextInt();
		int M = in.nextInt();
		int[] answer = new int[N];
		for(int i=0;i<N;i++) {
			answer[i] = -1;
		}

		for(int i=0;i<M;i++) {
			int s = in.nextInt();
			int c = in.nextInt();

			// 一桁目が0
			if (N != 1 && s == 1 && c == 0) {
				System.out.println(-1);
				return;
			}

			// 矛盾した定義
			int a = answer[s-1];
			if(a != -1) {
				if (a != c) {
					System.out.println(-1);
					return;
				}
			}

			answer[s-1] = c;
		}

		if (answer[0] == -1 && N != 1) answer[0] = 1;
		if (answer[0] == -1 && N == 1) answer[0] = 0;
		for(int i=1;i<N;i++) {
			if (answer[i] == -1) answer[i] = 0;
		}

		for(int i=0;i<N;i++) {
			System.out.print(answer[i]);
		}
		System.out.println();
	}
 
 
	public static class MyScanner{
		Scanner sc = new Scanner(System.in);
		String nextLine() {return sc.nextLine();}
		String next() {return sc.next();}
		int nextInt() {return Integer.valueOf(sc.next());}
		long nextLong() { return Long.valueOf(sc.next());}
	}

}

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

using namespace std;

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

typedef long long ll;

ll mod = 1000000007;

ll kai[200010];
ll inv[200010];
ll aa[100010], bb[100010];

ll beki(ll x, int y)
{
	if(y==0) return 1;
	if(y==1) return x;
	ll tmp=beki(x, y/2);
	if(y%2==0) return tmp*tmp%mod;
	else return tmp*tmp%mod*x%mod;
}

ll inverse(ll x)
{
	return beki(x, mod-2);
}

int main()
{
	ll n, a, b, c;
	cin >> n >> a >> b >> c;
	ll r = 100*inverse(100-c)%mod;
	ll tmp = inverse(a+b);
	b=b*tmp%mod;
	a=a*tmp%mod;
	aa[0]=1;
	bb[0]=1;
	rep(i, n+1)
	{
		aa[i+1]=aa[i]*a%mod;
		bb[i+1]=bb[i]*b%mod;
	}
	kai[0]=1;
	inv[0]=1;
	rep(i, 2*n+1)
	{
		kai[i+1]=kai[i]*((ll)i+1)%mod;
		inv[i+1]=inverse(kai[i+1]);
	}
	ll ans=0;
	rep(k, n)
	{
		ans+=kai[n+k]*inv[n-1]%mod*inv[k]%mod*aa[n]%mod*bb[k]%mod;
		ans%=mod;
		ans+=kai[n+k]*inv[n-1]%mod*inv[k]%mod*bb[n]%mod*aa[k]%mod;
		ans%=mod;
	}
	ans=ans*r%mod;
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 4992
#include<iostream>
#include<algorithm>

using namespace std;

int main(){
	int a,b,k;
	cin >> a >> b >> k;
	for(int i=0;i<k;){
	    if(a%2==1)
		    a--;
		b+=a/2;
		a/=2;
		i++;
		if(i>=k) break;
		if(b%2==1)
		    b--;
		a+=b/2;
		b/=2;
		i++;
	}
	cout << a << " " << b << endl;
}


Measured memory_bytes: 256
import math

cx1,cy1,r1 = map(int,input().split())
cx2,cy2,r2 = map(int,input().split())

xydistance = math.sqrt(pow(abs(cx1-cx2),2)+pow(abs(cy1-cy2),2)) 

if xydistance > r1+r2: 
    print(4) 
if xydistance == r1+r2: 
    print(3) 
if xydistance < r1+r2 and xydistance > abs(r1-r2) and xydistance != 0:
    print(2) 
if xydistance == abs(r1-r2): 
    print(1) 
if xydistance < abs(r1-r2): 
    print(0)




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

using namespace std;

#define db(...) ZZ(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1> void ZZ(const char* name, Arg1&& arg1){std::cerr << name << " = " << arg1 << endl;}
template <typename Arg1, typename... Args>void ZZ(const char* names, Arg1&& arg1, Args&&... args)
{
	const char* comma = strchr(names + 1, ',');
	std::cerr.write(names, comma - names) << " = " << arg1;
	ZZ(comma, args...);
}

#define IOS ios_base::sync_with_stdio(0); cin.tie(0);
#define endl '\n'

int a, b, c;

signed main()
{
	IOS;
	cin >> a >> b >> c;
	int cnt = 0;
	if (b >= a && b >= c)
		swap(a, b);
	else if (c >= a && c >= b)
		swap(a, c);
	while (b + 2 <= a) {
		b += 2;
		cnt++;
	}
	while (c + 2 <= a) {
		c += 2;
		cnt++;
	}
	if (a == b && b == c) cout << cnt << endl;
	else if (a > b && a > c) cout << cnt + 1 << endl;
	else cout << cnt + 2 << endl;
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<unistd.h>
using namespace std;
int main()
{
    int n,i,k=0;
    cin>>n;
    int a[n];
    for(i=0;i<n;i++)
    {
    cin>>a[i];
    k+=a[i];
}
cout<<k-n<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int k,a,b;
  string ans="";
  cin >> k >> a >> b;
  for(int i=a;i<=b;i++){
    if(i%k == 0){
      ans = "OK";
    }
  }
    if(ans == "OK"){
      cout << ans << endl;
    }else{
      cout << "NG" << endl;
  }
}

Measured memory_bytes: 3632
#include <iostream>
#include <algorithm>
using namespace std;
int main(){
    int n;
    cin >> n;
    long a[n];
    for(int i = 0;i<n;i++){
        cin >> a[i];
    }
    sort(a,a+n);
    long ans = 0;
    if(a[0]%2==1) ans^=n;
    for(int i = 0;i<n-1;i++){
        if((a[i+1]-a[i])%2==1) ans^=(n-1-i);
    }
    if(ans==0) cout << "second" << endl;
    else cout << "first" << endl;
}

Measured memory_bytes: 1024