akhauriyash/Code-Regression huggingface dataset:
#include <algorithm>
#include <array>
#include <cstddef>
#include <cstdint>
#include <iomanip>
#include <iostream>
#include <map>
#include <set>
#include <vector>

using namespace std;

int main()
{
    uint64_t n;
    cin >> n;
    map<uint64_t, uint64_t> count;
    for (int i = 0; i < n; i++)
    {
        uint64_t a;
        cin >> a;
        count[a]++;
    }

    auto check = [](uint64_t n, map<uint64_t, uint64_t> count) -> bool {
        if (count[0] == n)
        {
            return true;
        }
        if (n % 3 != 0)
        {
            return false;
        }
        vector<uint64_t> buf;
        for (auto elem : count)
        {
            for (int i = 0; i < elem.second / (n / 3); i++)
            {
                buf.push_back(elem.first);
            }
        }
        if (buf.size() != 3)
        {
            return false;
        }
        return (buf[0] ^ buf[1] ^ buf[2]) == 0;
    };

    cout << (check(n, count) ? "Yes" : "No") << endl;
}


Measured memory_bytes: 9856
MOD = 10 ** 9 + 7
L = input()
N = len(L)
total = 0
one_count = 0
pow2, pow3 = [1], [1]
p2, p3 = 1, 1
for i in range(N):
    p2 = p2 * 2 % MOD
    p3 = p3 * 3 % MOD
    pow2.append(p2)
    pow3.append(p3)
for i in range(N):
    if L[i] == "1":
        total = (total + pow2[one_count] * pow3[N - i - 1]) % MOD
        one_count += 1
print((total + pow2[one_count] * pow3[N - i - 1]) % MOD)


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

int main(){
    int x,y,s;
    while(cin >> x >> y >> s &&x!=0&&y!=0&&s!=0){
        int ans = 0;
        for(int i=1;i<1000;i++){
            for(int j=1;j<1000;j++){
                if((i*(100+x))/100 + (j*(100+x))/100 == s){
                    ans = max(i*(100+y)/100 + j*(100+y)/100,ans);
                }
            }
        }

        cout << ans << endl;
    }



    return 0;
}


Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define pb push_back
using namespace std;

typedef long long int ll;
int main()
{
    int a,b,c,d;
    while(cin>>a>>b>>c>>d)
    {
        int s=a+b;
        int k=c+d;
        if(s==k)cout<<"Balanced"<<endl;
        else if(s<k)cout<<"Right"<<endl;
        else cout<<"Left"<<endl;
    }

    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
ll n;
ll num[10000005];
void init(){
	for(ll i=1;i<=10000005;i++){
		for(ll x=i;x<10000005;x+=i){
			num[x]++;
		}
	}
}
int main(){
	//freopen("in.txt","r",stdin);
	init();
	cin>>n;
	ll ans = 0;
	
	for(ll i=1;i<=n;i++){
		ans += i*num[i];
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 81736
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
using namespace std;
typedef long long unsigned int ll;

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))

const int MAXN = 1024;

int t[MAXN];
int p[MAXN];
int x[MAXN];

int main() {
    int n; cin>>n;
    for(int i = 0; i < n; ++i) {
        cin>>t[i];
    }
    int m; cin>>m;
    for(int i = 0; i < m; ++i) {
        cin>>p[i]>>x[i];
    }

    ll sum = 0;
    for(int i = 0; i < n; ++i) {
        sum += t[i];
    }

    for(int i = 0; i < m; ++i) {
        int ii = p[i] - 1;
        cout << sum - t[ii] + x[i] << endl;
    }

    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <assert.h>
#include <vector>
#include <cmath>

int main(){
  std::cin.tie(0);
  std::ios::sync_with_stdio(false);

  int32_t N, Y;
  std::cin >> N >> Y;
  int32_t one = 0, five = 0, ten = 0;
  Y /= 1000;
  while (Y - N - 9 * ten >= 0){
    if ((Y - N - 9 * ten) % 4 == 0) {
      five = (Y - N - 9 * ten) / 4;
      one = N - five - ten;
      if ( one >= 0 ) {
        std::cout << ten << " " << five << " " << one << std::endl; 
        return 0;
      }
    }
    ten++;
  }

  std::cout << -1 << " " << -1 << " " << -1 << std::endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
  using namespace std;
 
int main(){
 string s;
  cin>>s;
  bool canStep=true;
  for(int i=0;i<s.size();i++){
    if(i%2==0){
      if(s.at(i)=='L'){
        canStep=false;
        break;
      }
    }else{
      if(s.at(i)=='R'){
        canStep=false;
        break;
      }
    }
  }
  if(canStep){
   cout<<"Yes"<<endl; 
  }else{
    cout<<"No"<<endl;
  }
}

Measured memory_bytes: 256
#include <bits/stdc++.h> 
using namespace std; 
int main()
{
  int n;
  cin>>n;
  map<int,int> mp;
  for(int i=1;i<=100;i++)
  {
     for(int j=1;j<=100;j++)
     {
        for(int k=1;k<=100;k++)
         {
           mp[i*i+j*j+k*k+i*j+i*k+j*k]++;
         }
     }
  }
  for(int i=1;i<=n;i++)
     cout<<mp[i]<<endl;
  return 0;
} 

Measured memory_bytes: 5468
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int a, b, c;
  cin >> a >> b;
  c = a*b;
  if (c%2 ==0){
    cout << "Even" << endl;
  }
  else{
    cout << "Odd" << endl;
  }
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
using namespace std;
struct BIT{
    vector<long long> num;
    int N;
    BIT(int n){
        N = n;
        num.resize(N + 1, 0);
    }
    long long sum(long long t){
        long long res = 0;
        while(t > 0){
            res += num[t];
            t -= t & -t;
        }
        return res;
    }
    void add(int ind, long long t){
        while(ind <= N){
            num[ind] += t;
            ind += ind & -ind;
        }
    }
};
int main(){
    string S;
    cin >> S;
    int n = S.size();
    BIT bit(n);
    for(int i = 0; i < n; i++){
        if(S[i] == '0') bit.add(i + 1, 1);
    }
    for(int i = n; i >= (n + 1) / 2; i--){
        int l = n - i;
        int r = i;
        int t = bit.sum(r) - bit.sum(l);
        if(t == r - l || t == 0){
            cout << i << endl;
            return 0;
        }
    }
    cout << n / 2 << endl;
}

Measured memory_bytes: 4292
#include <iostream>
using namespace std;
 
int F[105][105];
int xg,yg;
 
 
void DFS(int Y,int X,int c){
  if(F[Y][X] != c){
    return;
  }
 
  F[Y][X] = -1;
  DFS(Y-1,X  ,c);
  DFS(Y  ,X+1,c);
  DFS(Y+1,X  ,c);
  DFS(Y  ,X-1,c);
}
 
 
int main(){
  int w,h,xs,ys,n;
  while(1){
    cin >> w >> h;
    if(w == 0 && h == 0)
      break;
for(int i=0; i<20; i++){
      for(int j=0; j<20; j++){
        F[i][j]=10;
      }
    }
     
    cin >> xs >> ys >> xg >> yg >> n;
 
 
    for(int i=0;i<n;i++){
      int c,d,x,y;
      cin >> c >> d >> x >> y;
      if(d == 0){
        for(int j=0;j<4;j++){
          F[x+j][y] = c;
          F[x+j][y+1] = c;
        }
      } else {
        for(int j=0;j<4;j++){
          F[x][y+j] = c;
          F[x+1][y+j] = c;
        }
      }
    }

  DFS(xs,ys,F[xs][ys]);
 
  if(F[xg][yg] == -1){
    cout << "OK" << endl;
  } else {
    cout << "NG" <<endl;
  }
  }
}


Measured memory_bytes: 3012
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <map>
#include <utility>
#include <algorithm>
#include <math.h>

using namespace std;

typedef long long ll;
const ll mod=1000000007;
#define rep(i,n) for(ll i=0;i<n;i++)

struct UnionFind{
    vector<ll> par;
    vector<ll> rank;
    vector<ll> num;

    UnionFind(ll N){
        for(ll i=0;i<N;i++){
            par.push_back(i);
            rank.push_back(0);
            num.push_back(1);
        }
    }

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

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

int main(){
    ll N,M;
    ll A[100000],B[100000];
    cin>>N>>M;
    rep(i,M) cin>>A[i]>>B[i];
    UnionFind T(N);
    vector<ll> ans;
    ans.push_back((N*(N-1))/2);
    ll last;
    rep(i,M){
        last=ans.back();
        if(T.same(A[M-i-1],B[M-i-1])) ans.push_back(last);
        else{
            ans.push_back(last-T.num[T.par[A[M-i-1]]]*T.num[T.par[B[M-i-1]]]);
            T.unite(A[M-i-1],B[M-i-1]);
        }
    }
    ans.pop_back();
    while(!ans.empty()){
        cout<<ans.back()<<endl;
        ans.pop_back();
    }

    return 0;
}


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

//#define int long long
#define ll long long
#define all(v) (v).begin(), (v).end()
#define rep(i,n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<n;++i)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define EPS (1e-7)
#define gearup ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
typedef pair<ll, ll> P;
typedef vector<ll> vl;
typedef vector<vector<ll> > vvl;
typedef vector<vector<vector<ll> > > vvvl;
ll MOD = 1000000007;
const long long L_INF = 1LL << 60;
const int INF = 2147483647; // 2^31-1
const double PI = acos(-1);
//cout<<fixed<<setprecision(10);

template<class T> inline bool chmin(T& a, T b) {if (a > b) {a = b;return true;}return false;}
template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b;return true;}return false;}
template<class T> void debug(T v){rep(i,v.size()) cout<<v[i]<<" ";cout<<endl;}
const ll dx[8] = {1, 1, 0, -1, -1, -1, 0, 1};
const ll dy[8] = {0, 1, 1, 1, 0, -1, -1, -1};

signed main()
{   
    gearup;
    int n,X; cin >> n >> X;
    vector<int> x(n);
    rep(i,n)cin >> x[i];
    int res = __gcd(0,abs(X-x[0]));
    rep1(i,n) res = __gcd(res,abs(X-x[i]));
    cout << res << endl;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
#define rep(i,n)  for(int i=0;i<(n);++i)
using namespace std;
typedef long long ll;

vector<int> to[2000005];
vector<int> ans;
void dfs(int v,int p=-1){
  for(int u : to[v]){
    if(u==p) continue;
    ans.at(u) += ans.at(v);
    dfs(u,v);
  }
}

int main(){
  int n,q;
  cin >> n >> q;
  rep(i,n-1){
    int a,b;
    cin >> a >> b;
    --a; --b;
    to[a].push_back(b);
    to[b].push_back(a);
  }
  ans.resize(n);
  rep(i,q){
    int p,x;
    cin >> p >> x;
    --p;
    ans.at(p)+=x;
  }
  dfs(0);
  rep(i,n){
    cout << ans.at(i) << endl;
  }
  return 0;
}


Measured memory_bytes: 68736
#include<bits/stdc++.h>
using namespace std;
int main()
{
    long long int r,c,m;
    cin>>r>>c>>m;
    map<long long int,long long int>mr;
    map<long long int,long long int>mc;
    map<pair<long long int,long long int>,int>mm;
    while(m--)
    {
        long long int a,b;
        cin>>a>>b;
        mm[{a,b}]=1;
        mr[a]++;
        mc[b]++;
    }
    long long int rmax=0;
    long long int cmax=0;
    for(auto x:mr)
    {
        rmax=max(rmax,x.second);
    }
    for(auto x:mc)
    {
        cmax=max(cmax,x.second);
    }
    vector<long long int>rr;
    vector<long long int >cc;

    for(auto x:mr)
    {
        if(x.second==rmax)
        {
            rr.push_back(x.first);
        }
    }

    for(auto x:mc)
    {
        if(x.second==cmax)
        {
            cc.push_back(x.first);
        }
    }
    int flag=0;
    for(long long int i=0;i<rr.size();i++)
    {
        for(long long int j=0;j<cc.size();j++)
        {
            if(mm.count({rr[i],cc[j]})==0)
            {
                flag=1;
                break;
            }
        }
    }
    if(flag==1)
    {
        cout<<rmax+cmax;
    }
    else
    {
        cout<<rmax+cmax-1;
    }
    return 0;
}

Measured memory_bytes: 67888
#include <iostream>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <algorithm>
#include <set>
#include <map>
#include <bitset>
#include <cmath>
#include <functional>
#include <iomanip>
#define vll vector<ll>
#define vvv vector<vvl>
#define vvi vector<vector<int> >
#define vvl vector<vector<ll> >
#define vv(a, b, c, d) vector<vector<d> >(a, vector<d>(b, c))
#define vvvl(a, b, c, d) vector<vvl>(a, vvl(b, vll (c, d)));
#define rep(c, a, b) for(ll c=a;c<b;c++)
#define re(c, b) for(ll c=0;c<b;c++)
#define all(obj) (obj).begin(), (obj).end()
typedef long long int ll;
typedef long double ld;
//typedef __int128_t lll;
using namespace std;

ll f(ll x, ll y, ll op){
  if(op==0) return x+y;
  else return x-y;
}
char g(ll op){
  if(op==0) return '+';
  return '-';
}
int main(int argc, char const *argv[]) {
  string s;std::cin >> s;
  ll a = s[0] - '0';
  ll b = s[1] - '0';
  ll c = s[2] - '0';
  ll d = s[3] - '0';

  re(i, 2){
    re(j, 2){
      re(k, 2){
        ll num = f(f(f(a, b, i), c, j), d, k);
        if(num==7){
          std::cout << a;
          std::cout << g(i);
          std::cout << b;
          std::cout << g(j);
          std::cout << c;
          std::cout << g(k);
          std::cout << d;
          std::cout << "=7" << '\n';
          return 0;
        }
      }
    }
  }
  return 0;
}


Measured memory_bytes: 256
fn main() {
    let (r, g, b): (i32, i32, i32) = io::readln();
    if (g * 10 + b) % 4 == 0 {
        println!("YES");
    }
    else {
        println!("NO");
    }
}

pub mod io {
    use std::io;

    pub fn read_line() -> String {
        let mut s = String::new();
        io::stdin().read_line(&mut s).unwrap();
        s.trim_right().to_owned()
    }

    pub fn readln<T: Read>() -> T {
        let mut s = String::new();
        io::stdin().read_line(&mut s).unwrap();
        T::read(s.trim())
    }

    pub trait Read {
        fn read(s: &str) -> Self;
    }

    impl Read for String {
        fn read(s: &str) -> Self {
            s.to_string()
        }
    }

    impl<T: Read> Read for Vec<T> {
        fn read(s: &str) -> Self {
            s.split_whitespace().map(|w| T::read(w)).collect()
        }
    }

    macro_rules !def_read {
        ($t : ty) => {
            impl Read for $t {
                fn read(s : &str)->$t { s.parse().unwrap() }
            }
        }
    }

    macro_rules !def_read_tuple {
        ($($t : ident), *) => {
            impl<$($t : Read + Default), *> Read for ($($t), *) {
                fn read(s : &str)->Self {
                    let mut iter = s.split_whitespace();
                    ($($t::read(iter.next().unwrap())), *)
                }
            }
        };
    }

    def_read!(i32);
    def_read!(i64);
    def_read!(isize);
    def_read!(usize);
    def_read!(f32);
    def_read!(f64);
    def_read_tuple!(T0, T1);
    def_read_tuple!(T0, T1, T2);
    def_read_tuple!(T0, T1, T2, T3);
    def_read_tuple!(T0, T1, T2, T3, T4);
}

Measured memory_bytes: 4352
#include <bits/stdc++.h>
#define _CRT_SECURE_NO_WARNINGS
#define ll long long
#define BUF 50
#define INF 1<<30
using namespace std;
ll MOD = 1e9 + 7;
ll A, B, C, D, G, H, N, M, L, K, P, Q, R, W, X, Y, Z;
string S;
ll ans = 0;
int main() {
	cin >> A >> B >> K;
	int i;
	for (i = min(A, B); i >=1; i--) {
		if (A%i == 0 && B%i == 0)ans++;
		if (ans == K)break;
	}
	cout << i << endl;
}

Measured memory_bytes: 384
n = input()
Rt = []
for i in range(int(n)):
    Rt.append(int(input()))   ####入力をinputで取得!!!!
R  = []
maxv = -10**9
minv = Rt[0]

for i in range(1,len(Rt)):
    if maxv < Rt[i]-minv:
        maxv = Rt[i]-minv
    if minv > Rt[i]:
        minv = Rt[i]
    #print(maxv,minv)
print(maxv)


Measured memory_bytes: 13588
#include <iostream>
using namespace std;
#define ll long long

ll dp[100001][101]={};

int main()
{
    int n,W; cin>>n>>W;
    ll w[n],v[n];
    for(int i=0;i<n;i++) cin>>w[i]>>v[i];

    for(int i=1;i<=W;i++)
    {
        for(int j=1;j<=n;j++)
        {
            dp[i][j]=dp[i][j-1];
            if(w[j-1]<=i){
                dp[i][j]= max(dp[i][j], v[j-1] + dp[i-w[j-1]][j-1] );
            }
        }
    }
    cout<<dp[W][n];

//    for(int i=1;i<=W;i++)
//    {
//        for(int j=1;j<=n;j++)
//        cout<<dp[i][j]<<" ";
//        cout<<endl;
//    }

    return 0;
}

Measured memory_bytes: 79104
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int N;
    cin >> N;
    string S;
    cin >> S;
    int count = 1;
    for(int i = 1;i < N;i++) {
        if(S.at(i - 1) != S.at(i)) {
            count++;
        }
    }
    cout << count << endl;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
const int Maxn=190;
int s[Maxn][Maxn],f[2][Maxn][Maxn][Maxn];
int check(int x1,int y1,int x2,int y2){
    int sum=s[x2][y2]-s[x2][y1-1]-s[x1-1][y2]+s[x1-1][y1-1];
    return sum==0||sum==(y2-y1+1)*(x2-x1+1);
}
int main(){
    int n,m;scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++){
            char c;scanf("\n%c",&c);
            s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+(c=='.');
        }
    for(int i=n;i>=1;i--)
        for(int l=1;l<=m;l++)
            for(int r=l;r<=m;r++)
                if(!check(i,l,i,r))f[0][i][l][r]=i-1;
                else{
                    f[0][i][l][r]=i==n?n:f[0][i+1][l][r];
                    if(!check(i,l,f[0][i][l][r],r))
                        f[0][i][l][r]=i;
                }
    for(int k=1;k<20;k++){
        int cur=k&1,pre=!cur;
        if(f[pre][1][1][m]==n){
            cout<<k-1<<"\n";
            return 0;
        }
        for(int i=1;i<=n;i++)
            for(int l=1;l<=m;l++)
                for(int r=l;r<=m;r++)
                    f[cur][i][l][r]=max(f[pre][i][l][r],f[pre][f[pre][i][l][r]+1][l][r]);
        for(int i=1;i<=n;i++)
            for(int l=1;l<=m;l++)
                for(int r=l;r<=m;r++){
                    // cout<<"#1i="<<i<<" l="<<l<<" r="<<r<<" k="<<k<<" maxj="<<f[i][l][r][k]<<"\n";
                    if(l==r)continue;
                    int L=l,R=r-1;
                    while(L<=R){
                        int mid=(L+R)/2;
                        if(f[pre][i][l][mid]>f[pre][i][mid+1][r])L=mid+1;
                        else R=mid-1;
                    }
                    for(int mid=max(l,L-2);mid<=min(r-1,L+2);mid++){
                        f[cur][i][l][r]=max(f[cur][i][l][r],min(f[pre][i][l][mid],f[pre][i][mid+1][r]));
                        // cout<<"\t=>"<<mid<<" val="<<f[i][l][r][k]<<"\n";
                    }
                    // cout<<"#2i="<<i<<" l="<<l<<" r="<<r<<" k="<<k<<" maxj="<<f[i][l][r][k]<<"\n";
                }
    }
    return 0;
}

Measured memory_bytes: 53632
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
int64_t MOD=1000000007;
const long long INF = 1LL<<60;

int main() {
  int64_t N,K,ans=-1*INF; cin>>N>>K;
  vector<int64_t> P(N);
  rep(i,N) cin>>P.at(i);
  rep(i,N) P.at(i)--;
  vector<int64_t> C(N);
  rep(i,N) cin>>C.at(i);
  rep(i,N) ans=max(ans,C[i]);

  rep(i,N){
    vector<bool> seen(N,true);
    vector<int64_t> S,T;
    int64_t k=i,sum=0;
    while(seen.at(k)){
      seen.at(k)=false;
      S.push_back(C.at(k));
      sum+=C.at(k);
      k=P.at(k);
    }
    int64_t t=S.size(),r=K/t,q=K%t,MAX=-1*INF,NMAX,MAX2=-1*INF;
    rep(i,t){
      T.push_back(S.at(i));
      if(i>0) T.at(i)+=T.at(i-1);
      if(T.at(i)>MAX){
        MAX=T.at(i);
        NMAX=i+1;
      }
    }
    if(q==0) ans=max(ans,MAX+sum*(r-1));
    else{
      if(q<NMAX){
        rep(i,q) MAX2=max(MAX2,T.at(i));
        if(r==0) ans=max(ans,MAX2);
        else if(sum<0) ans=max(ans,MAX);
        else{
          auto temp=max(MAX+sum*(r-1),max(MAX2+sum*r,sum*r));
          ans=max(ans,temp);
        }
      }
      else{
        if(sum<0) ans=max(ans,MAX);
        else ans=max(ans,MAX+sum*r);
      }
    }
  }
  cout<<ans;
}

Measured memory_bytes: 3820
#include<cstdio>
#include<bits/stdc++.h>
typedef long long int ll;
#define REP(i, n) for(int i = 0; i < (n); i++)
#define FOR_IN(i, a, b) for(int i = (a); i < (b); i++)
#define BETWEEN(x, a, b) ((x) >= (a) && (x) <= (b))
#define LOG_F 1
#define LOG(...) if(LOG_F) fprintf(stderr, __VA_ARGS__)

using namespace std;

/*

 */
int a,b,c,d;

int main(){
  cin>>a>>b>>c>>d;
  cout << max(a*b, c*d) << endl;

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
typedef long long ll;
#define rep(i,n) for(ll i=0;i<(n);i++)
#define repr(i,n) for(ll i=(n-1);i>=0;i--)
#define pb push_back
#define mp make_pair
#define all(x) x.begin(),x.end()
using namespace std;
ll inf = 1000000007;


long long modinv(long long a, long long m) {
    long long b = m, u = 1, v = 0;
    while (b) {
        long long t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m;
    if (u < 0) u += m;
    return u;
}



int main() {
    ll x, y;
    cin >> x >> y;

    if((x+y)%3 != 0){
        cout << 0 << endl;
        return 0;
    }

    ll idou_kaisu = (x+y) / 3;

    ll x_kaisu = x - idou_kaisu;
    ll y_kaisu = y - idou_kaisu;

    ll num = min(x_kaisu, y_kaisu);

    if(x_kaisu < 0 || y_kaisu < 0){
        cout << 0 << endl;
        return 0;
    }

    /*
    ll sa = 0;
    if((x-y) < 0){
        sa = -1 * (x-y);
    }else{
        sa = (x-y);
    }

    ll num = 0;
    num = (idou_kaisu / 2) - (sa/2);
    */

    /*
    if(idou_kaisu % 2 == 0){
        num = (idou_kaisu / 2) - (sa/2);
    }else{
        num = (idou_kaisu / 2) - (sa/2);
    }
    */



    ll bunshi = 1;
    ll bunbo = 1;
    rep(i,num){
        bunshi = (bunshi * (idou_kaisu - i)) % inf;
    }
    rep(i,num){
        bunbo = (bunbo * (i+1)) % inf;
    }

    bunshi %= inf;
    cout << bunshi * modinv(bunbo, inf) % inf << endl;

}


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

int main() {
  int s;
  cin >> s;
  int ans = 0;
  for(int i = 0; i < 6; i++) {
    if(s % 10 == 1) {
      ans++;
      s -= 1;
    }
    s /= 10;
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define int llint
#define rep(i, a, n) for(int (i) = (int)(a);(i) < (int)(n);++(i))
#define repe(i, a, n) for(int (i) = (int)(a);(i) <= (int)(n);++(i))
#define repif(i, a, x) for(int (i) = (int)(a);(x);++(i))
#define repr(i, a, n) for(int (i) = ((int)(a)-1);(i) >= (int)(n);--(i))
#define reper(i, a, n) for(int (i) = (int)(a);(i) >= (int)(n);--(i))
#define chmax(a, b) a = max(a, b)
#define chmin(a, b) a = min(a, b)
#define SIZE(x) ((int)(x).size())
#define ALL(x) (x).begin(), (x).end()
#define RNG(x, a, n) &((x)[a]), &((x)[n])
#define ADD(a, b) ((((a+MOD)%MOD)+((b+MOD)%MOD))%MOD)
#define MUL(a, b) ((((a)%MOD)*((b)%MOD))%MOD)
#define CEIL(x) ((int)ceil(((double)x)))
#define POW(x, y) ((int)pow(x, y))
#define UNIQUE(x) (x).erase(unique(ALL((x))), (x).end())
#define YES cout << "YES" << endl
#define NO cout << "NO" << endl
#define Yes cout << "Yes" << endl
#define No cout << "No" << endl
#define yes cout << "yes" << endl;
#define no cout << "no" << endl;
#define fcout cout << fixed << setprecision(10)
#define pb push_back
#define pf push_front
#define mp make_pair
#define mt make_tuple
#define lb lower_bound
#define ub upper_bound
#define fi first
#define se second
#define EPS (1e-20)
#define INF INT_MAX
#define INFLL LLONG_MAX
#define MOD 1000000007
using llint = long long;
using VI = std::vector<int>;
using PII = std::pair<int, int>;
using SI = std::set<int>;
using MII = std::map<int, int>;
using TIII = std::tuple<int, int, int>;
using MCI = std::map<char, int>;
using VPII = std::vector<PII>;
using namespace std;


int N, K;
int a[5010];


int solve(){
	int ans = N, sum = 0;
	sort(RNG(a, 0, N));
	repr(i, N, 0)
		if(sum+a[i] < K) sum += a[i];
		else chmin(ans, i);
	return ans;
}


signed main(){
	cin >> N >> K;
	rep(i, 0, N) cin >> a[i];

	cout << solve() << endl;

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, srt, end) for (long long i = (srt); i < (long long)(end); i++)
#define VL vector<ll>
#define VS vector<string>
#define VB vector<bool>
#define VP vector<pair<ll,ll>>
#define VVL vector<vector<ll>>
#define VVP vector<vector<pair<ll,ll>>>
#define PL pair<ll,ll>
#define ALL(v) (v).begin(), (v).end()
ll d1[4] = {1, -1, 0, 0};
ll d2[4] = {0, 0, 1, -1};

ll gcd(ll a, ll b){
    if(a < b) return gcd(b, a);
    ll r = a % b;
    while(r != 0){
        a = b;
        b = r;
        r = a % b;
    }
    return b;
}

ll lcm(ll a, ll b){
    ll ret = (a * b)/gcd(a,b);
    return ret;
}

int main(){
    ll N, X;
    cin >> N >> X;
    VL x(N+1);
    rep(i, 0, N) cin >> x[i];
    x[N] = X;
    sort(ALL(x));
    VL d(N);
    rep(i, 0, N) d[i] = x[i+1] - x[i];
    ll ans = d[0];
    rep(i, 1, N) ans = gcd(ans, d[i]);
    cout << ans << endl;
    return 0;
}

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

int main() {

	ll N; cin >> N;
	const ll u = 3500;
	ll ans1, ans2, ans3;
	for (ll h = 1; h <= u; h++) {
		for (ll n = 1; n <= u; n++) {
			double w = (double)(N * h * n) / (4 * h * n - N * n - N * h);
			if (w < 1) continue;
			if (1 <= w && floor(w) == w) {
				ans1 = h;
				ans2 = n;
				ans3 = w;
				break;
			}
		}
	}
	cout << ans1 << " " << ans2 << " " << ans3 << endl;
    return 0;
}

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

#define rep(i,n) for(int i=0;i<(n);i++)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define ROF(i,a,b) for(int i=(a)-1;i>=(b);i--)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend() //sortで大きい順
#define UNIQUE(v) v.erase(unique(all(v)),v.end())
#define SUM(a) accumlate(all(a),0)
#define pb push_back
#define fst first
#define snd second
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<string> vs;
typedef pair<int,int> pii;
typedef long long ll;

int n;

bool dfs(vvi adj){
  vi check(n);
  stack<int> st;
  st.push(0);
  check[0] = 1;

  while(!st.empty()){
    int tmp = st.top();
    st.pop();
    rep(i,n) if(adj[tmp][i] == 1 and check[i] == 0){
      check[i] = 1;
      st.push(i);
    }
  }
  rep(i,n) if(check[i] == 0) return true; // 不連結
  return false;
}

main(){
  int m; cin >> n >> m;
  vvi adj(n,vi(n));
  int a, b;
  rep(i,m){
    cin >> a >> b;
    adj[a-1][b-1] = adj[b-1][a-1] = 1;
  }
  int ans = 0;
  rep(i,n) rep(j,n) if(adj[i][j] == 1){
    adj[i][j] = 0;
    if(dfs(adj)) ans++;
    adj[i][j] = 1;
  }
  cout << ans << endl;
}


Measured memory_bytes: 256
from collections import Counter
from sys import exit
N, = list(map(int,input().split()))
d = list(map(int,input().split()))
c = Counter(d)
ks = list(c.keys())
ks.sort()
s = 0
for i,k in enumerate(ks[:N-1]):
  s += c[k]
  if s==N//2:
    print(ks[i+1]-k)
    exit(0)
print(0)

Measured memory_bytes: 14812
#include <iostream>
#include <cstdio>
#include <string>
#include <map>
#include <vector>
#include <algorithm>

using namespace std;

int n;
vector<int> a;
vector<long long int> b;
int maxx;

bool check(int m){
	if(b[m]>=maxx){return true;}

	long long int k=b[m];
	for(int i=m+1; i<n-1; i++){
		if(a[i]<=k){
			k += 2*a[i];
			if(k>=maxx){
				return true;
			}
		}
		else{
			return false;
		}
	}

	return false;
}


int main(){
	
	long long int t=0;

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

	sort(a.begin(), a.end());
	maxx = a[n-1];

	for(int i=0; i<n; i++){
		b.push_back(t+2*a[i]);
		t=b[i];
	}


	int low=0,high=n-1;
	while (low < high) {
		int mid = (low+high) / 2;
		if (check(mid) == false) {
			low = mid + 1;
		}
		else{
			high = mid;
		}
	}
	
	cout << n-low << endl;

	return 0;
}

Measured memory_bytes: 1784
#include<stdio.h>
#include<stdlib.h>

struct node{
  struct node *right;
  struct node *left;
  struct node *p;
  int key;
};
typedef struct node * Node;
#define NIL NULL

Node root;

Node treeMinimum(Node x){
  Node y;
  y=x;
  while(y->left!=NIL) y=y->left;

  return y;

}

Node treeMaximum(Node x){
 Node y;
  y=x;
  while(y->left!=NIL) y=y->right;

  return y;

}

Node treeSearch(Node u, int k){
  Node x;
  x=u;

  while(x!=NIL && k!=x->key){
    if(k < x->key)x=x->left;
    else x=x->right;
  }

  return x;

}

Node treeSuccessor(Node x){
  Node y;

  if(x->right!=NIL)return treeMinimum(x->right);

  y=x->p;
  while(y!=NIL && x==y->right){
    x=y;
    y=y->p;
  }
  return y;

}

void treeDelete(Node z){
  Node y; // node to be deleted
  Node x; // child of y

  if(z->left==NIL || z->right==NIL)y=z;
  else y=treeSuccessor(z);

  if(y->left!=NIL)x=y->left;
  else x=y->right;

  if(x!=NIL)x->p=y->p;
  if(y->p==root)root=x;
  else if(y == y->p->left)y->p->left=x;
  else y->p->right=x;

  if(y!=z) z->key=y->key;
  free(y);

}

void insert(int k){
  Node y = NIL;
  Node x = root;
  Node z;

  z = malloc(sizeof(struct node));
  z->key = k;
  z->left = NIL;
  z->right = NIL;

  while(x!=NIL){
    y=x;
    if(k < x->key)x=x->left;
    else x=x->right;
  }
  z->p=y;

  if(y==NIL)root=z;
  else if(z->key < y->key)y->left=z;
  else y->right=z;

}

void inorder(Node u){
  if (u==NIL)return;

  inorder(u->left);
  printf(" %d",u->key);
  inorder(u->right);

}
void preorder(Node u){
if (u==NIL)return;

 printf(" %d",u->key);
 preorder(u->left);
 preorder(u->right);

}


int main(){
  int n, i, x;
  char com[20];
  Node t;
  scanf("%d", &n);

  for ( i = 0; i < n; i++ ){
    scanf("%s", com);
    if ( com[0] == 'f' ){
      scanf("%d", &x);
       t = treeSearch(root, x);
      if ( t != NIL ) printf("yes\n");
      else printf("no\n");
    } else if ( com[0] == 'i' ){
      scanf("%d", &x);
      insert(x);
    } else if ( com[0] == 'p' ){
      inorder(root);
      printf("\n");
      preorder(root);
      printf("\n");
    } else if ( com[0] == 'd' ){
      scanf("%d", &x);
      treeDelete(treeSearch(root, x));
    }
  }

  return 0;
}

Measured memory_bytes: 19364
#include <algorithm>
#include <cmath>
#include <deque>
#include <iostream>
#include <numeric>
#include <queue>
#include <sstream>
#include <string>
#include <string.h>
#include <tuple>
#include <vector>

#define REP(i,x) for(int i{ 0 }; i < (int)(x); i++)
#define REPC(i,x) for(int i{ 0 }; i <= (int)(x); i++)
#define RREP(i,x) for(int i{ (int)(x) - 1 }; i >= 0 ;i--)
#define RREPC(i,x) for(int i{ (int)(x)}; i >= 0; i--)
#define REP1O(i,x) for(int i{ 1 }; i < (int)(x); i++)
#define REP1C(i,x) for(int i{ 1 }; i <= (int)(x); i++)

#define PB push_back
#define MP make_pair
#define F first
#define S second
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()

using namespace std;

typedef int64_t ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vector<int>> vvi;
typedef vector<vector<ll>> vvll;
typedef pair<int, int> pii;
typedef tuple<int, int, int> tupiii;
typedef tuple<ll, ll, ll> tuplll;

const int INTMAX = 2147483647;
const ll LLMAX = 9223372036854775807;
const int MOD = 1000000007;

template<class T> inline bool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; }
inline void swap(ll& a, ll& b) { a ^= b; b ^= a; a ^= b; }
inline void swap(int& a, int& b) { a ^= b; b ^= a; a ^= b; }



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

	cout << max(a * b, c * d) << endl;

}


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

int main(){
    int N;
    cin >> N;
    int a=0;
    if(N%1000 == 0){
        a = N/1000;
    }
    else{
        a = N/1000 + 1;
    }

    cout << a*1000 - N << endl;
}

Measured memory_bytes: 3612
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <stack>
#include <numeric>




typedef long long ll;
#define PI 3.14159265359
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define mp make_pair
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define decp(n) cout<<fixed<<setprecision((int)n)
#define _GLIBCXX_DEBAC
#include <functional>
/*map<Keyの型, Valueの型> 変数名;
queue<型> 変数名;
priority_queue<型> 変数名;
priority_queue<型, vector<型>, greater<型>> 変数名;*/
//copy(v1.begin(), v1.end(), back_inserter(v2));
using namespace std;

ll gcd(ll a, ll b) {
	ll c;
	if (a < b) {
		c = a; a = b; b = c;
	}
	while (b != 0) {
		c = a % b; a = b; b = c;
	}
	return a;
}

ll lcm(ll a, ll b) {
	ll c;
	c = a * b / gcd(a, b);
	return c;
}

int sort_greater(int m, int n) {
	vector<int> a(m);
	for (int i = 0; i < m; i++) {
		cin >> a[i];
	}
	sort(a.begin(), a.end(), greater<int>());
	for (int i = 0; i < n; i++) {
		cout << a[i];
	}
	return 0;
}

int bubblesort(int a[], int n) {
	int sw = 0;
	bool flag = 1;
	for (int i = 0; flag; i++) {
		flag = 0;
		for (int j = n - 1; j >= i + 1; j--) {
			if (a[j] < a[j - 1]) {
				swap(a[j], a[j - 1]);
				flag = 1;
				sw += 1;
			}
		}
	}
	return sw;
}

int a_z()
{
	for (int i = 0; i <= ('Z' - 'A'); i++) {
		cout << (char)('A' + i);
	}
	return 0;
}

int selecttionsort(int a[], int n) {
	int t, sw = 0, minj;
	for (int i = 0; i < n - 1; i++) {
		minj = i;
		for (int j = 0; j < n - 1; j++) {
			if (a[j] < a[minj]) {
				minj = j;
			}
		}
		t = a[i]; a[i] = a[minj]; a[minj] = t;
		if (i != minj) sw += 1;

	}
	return sw;
}

bool is_prime(int x) {
	if (x <= 1) return false;
	for (int i = 2; i * i <= x; i++) {
		if (x % i == 0) return false;
	}
	return true;
}

const ll mod = 1000000007;

map<string, int> memo;

using P=pair<int, int>;
/*void dfs(int v, int p = -1) {
	for (int u : to[v]) {
		if (u == p) continue;
		ans[u] += ans[v];
		dfs(u, v);
	}
}*/
ll findIndex(int value, vector<ll> a)
{

	for (ll i = 0; i < (ll)a.size(); i++) {
		if (a[i] == value) {
			return i;
		}
	}
	return -1;
}

ll nCr(ll n, ll r) {
	ll a = 1;
	for (ll i = n; i > n - r; --i) {
		a = a * i;
	}
	for (ll i = 1; i < r + 1; ++i) {
		a = a / i;
	}
	return a;
}

void comb(vector<vector <long long int> >& v) {
	for (ll i = 0; i < v.size(); i++) {
		v[i][0] = 1;
		v[i][i] = 1;
	}
	for (ll k = 1; k < v.size(); k++) {
		for (ll j = 1; j < k; j++) {
			v[k][j] = (v[k - 1][j - 1] + v[k - 1][j]);
		}
	}
}



int main() {
	int n,k;
	cin >> n>>k;
	vector<ll> a(n);
	rep(i, n)cin >> a[i];
	ll ans=1e9,cn=0;
	rep(i, n - k + 1) {
		cn += abs(a[i] - a[i + k - 1]);
		cn += min(abs(a[i]), abs(a[i + k - 1]));
		ans = min(cn, ans);
		cn = 0;
	}
	cout << ans;
	return 0;
}













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

int main(){
	int ans = 0;
	string w, s;
	cin >> w;
	for(char &c:w) if('A' <= c && c <= 'Z') c = 'a' + c - 'A';
	while(cin >> s && s != "END_OF_TEXT"){
		for(char &c:s) if('A' <= c && c <= 'Z') c = 'a' + c - 'A';
		if(s == w) ans++;
	}
	cout << ans << endl;
}

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

using namespace std;

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

    vector<tuple<string,int,int>> res(N);

    for(int i=0; i<N; i++){
        cin >> get<0>(res[i]) >> get<1>(res[i]);
        get<1>(res[i]) *= -1;
        get<2>(res[i]) = i+1;
    }
    
    sort(res.begin(),res.end());

    for(auto t: res) cout << get<2>(t) << endl;
}   

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
    #ifndef ONLINE_JUDGE
        freopen("input.txt","r",stdin);
        freopen("output.txt","w",stdout);
   	#endif
    int a,b,c;
    cin>>a>>b>>c;
    cout<<min(c,a*b);
   return 0;
}

Measured memory_bytes: 3632
#include <iostream>
#include <algorithm>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <vector>

using namespace std;


int main() {
	long A, B;
	cin >> A >> B; A--;
	long a = 1;
	while (a * 2 <= A) { a *= 2; }
	long b = 1;
	while (b * 2 <= B) { b *= 2; }

	long xa = 0;
	if (A <= 0) { goto Aend; }
	for (; a >= 1; a /= 2) {
		long k = A / a;
		long x = A % a;
		if (a == 1) {
			if (A % 4 ==1 || A % 4 == 2) { xa += a; }
		}
		else if (a == 2) {
			if (A % 4 == 2) { xa += a; }
		}
		else {
			if ((k % 2 == 1) && (x % 2 == 0)) { xa += a; }
		}
	}
Aend:
	long xb = 0;
	if (B <= 0) { goto Bend; }
	for (; b >= 1; b /= 2) {
		long k = B / b;
		long x = B % b;
		if (b == 1) {
			if (B % 4 == 1 ||  B % 4 == 2) { xb += b; }
		}
		else if (b == 2) {
			if (B % 4 == 2) { xb += b; }
		}
		else {
			if ((k % 2 == 1) && (x % 2 == 0)) { xb += b; }
		}
	}
Bend:
	cout << (xa ^ xb) << endl;


	return 0;
}

/*

  123456789 10 11 12 13 14
1 110011001  1  0  0  1  1
2 020002000  2  0  0  0  2
4 000404000  0  0  4  0  4
8 000000080  8  0  8  0  8


*/

Measured memory_bytes: 256
#include<bits/stdc++.h>
    #define ll long long
    #define ull unsigned ll
    #define uint unsigned
    #define db long double
    #define pii pair<int,int>
    #define pll pair<ll,ll>
    #define IT iterator
     
    #define PB push_back
    #define MK make_pair
    #define LB lower_bound
    #define UB upper_bound
    #define EB emplace_back
    #define fi first
    #define se second
     
    #define For(i,j,k) for (int i=(int)(j);i<=(int)(k);i++)
    #define Rep(i,j,k) for (int i=(int)(j);i>=(int)(k);i--)
    #define UPD(x,y) (((x)+=(y))>=mo?x-=mo:233)
    #define CLR(a,v) memset(a,v,sizeof(a));
    #define CPY(a,b) memcpy(a,b,sizeof(a));
     
    #define LS3 k*2,l,mid
    #define RS3 k*2+1,mid+1,r
    #define LS5 k*2,l,mid,x,y
    #define RS5 k*2+1,mid+1,r,x,y
    #define GET pushdown(k);int mid=(l+r)/2
     
    #define INF ((1ll<<60)-233)
    #define sqr(x) ((x)*(x))
    #define debug puts("wzpkking")
    using namespace std;
     
    const int N=5005,mo=1000000007;
    vector<int> e[N];
    int f[N][N],fac[N];
    int tmp[N],sz[N],n;
    void dfs(int x,int fa){
    	f[x][sz[x]=1]=1;
    	for (auto y:e[x]) if (y!=fa){
    		dfs(y,x);
    		For(i,1,sz[x]) For(j,0,sz[y])
    			UPD(tmp[i+j],1ll*f[x][i]*f[y][j]%mo);
    		For(i,1,sz[x]+sz[y]) f[x][i]=tmp[i],tmp[i]=0;
    		sz[x]+=sz[y];
    	}
    	for (int i=2;i<=sz[x];i+=2)
    		UPD(f[x][0],mo-1ll*f[x][i]*fac[i]%mo);
    }
    int main(){
    	scanf("%d",&n); fac[0]=1;
    	for (int i=2;i<=n;i+=2)
    		fac[i]=1ll*fac[i-2]*(i-1)%mo;
    	For(i,1,n-1){
    		int x,y; scanf("%d%d",&x,&y);
    		e[x].PB(y); e[y].PB(x);
    	}
    	dfs(1,0);
    	printf("%d\n",(mo-f[1][0])%mo);
    }

Measured memory_bytes: 97408
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)
using ll = long long;
using P = pair<int,int>;
int main(void) {
    string s; cin >> s;
    rep(i, s.size()) if(s[i]==',') s[i] = ' ';
    cout << s;
}


Measured memory_bytes: 256
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 998244353
dd = [(0,-1),(1,0),(0,1),(-1,0)]
ddn = [(0,-1),(1,-1),(1,0),(1,1),(0,1),(-1,-1),(-1,0),(-1,1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n,q = LI()
    qa = sorted([LI() for _ in range(q)])
    u = [0] * (n+2)
    d = [0] * (n+2)

    for x,i in qa:
        u[i+1] = u[i] + 1
        d[i] = d[i+1] + 1
    rr = []
    for i in range(1,n+1):
        rr.append(u[i]+d[i]+1)


    return ' '.join(map(str,rr))


print(main())




Measured memory_bytes: 43792
#include <bits/stdc++.h>
#define all(a) (a).begin(), (a).end()
#define REP(i, n) for(int (i)=0; (i)<(n); (i)++)
#define RREP(i, n) for(int (i)=(n)-1; (i)>=0; (i)--)
#define ios() cin.tie(0), ios::sync_with_stdio(false)
typedef long long ll;
typedef unsigned long long ull;
ll const MOD = 1e9+7;
ll const INF = 1e18;
using namespace std;

int main(){
    int n, c;
    cin >> n >> c;

    vector<vector<int>> diff(c, vector<int>(c)), count(3, vector<int>(c, 0));
    REP(i, c) REP(j, c) cin >> diff[i][j];
    REP(i, n){
        REP(j, n){
            int a;
            cin >> a;
            count[(i+j)%3][a-1]++;
        }
    }

    ll ans = INF;

    REP(i0, c){
        REP(i1, c){
            REP(i2, c){
                if(i0 == i1 || i1 == i2 || i2 == i0) continue;
                ll sum = 0;
                REP(j, c){
                    sum += diff[j][i0] * count[0][j]
                         + diff[j][i1] * count[1][j]
                         + diff[j][i2] * count[2][j];
                }
                ans = min(ans, sum);
            }
        }
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <iostream>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <random>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define repp(i,n,m) for (int i = m; i < (n); ++i)
#define repl(i,n) for (long long i = 0; i < (n); ++i)
#define reppl(i,n,m) for (long long i = m; i < (n); ++i)
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<int, int>;
using PL = pair<long long, long long>;
using Pxy = pair<double, double>;
using T = tuple<int, int, bool>;
const int INF = 1001001007;
const int mod = 1000000007;
const int MOD = 998244353;
const ll inf = 1e18;
template <typename AT>
void printvec(vector<AT> &ar){
    rep(i,ar.size()-1) cout << ar[i] << " ";
    cout << ar[ar.size()-1] << endl;
}
template <typename Q>
void printvvec(vector<vector<Q>> &ar){
    rep(i,ar.size()){
        rep(j,ar[0].size()-1) cout << ar[i][j] << " ";
        cout << ar[i][ar[0].size()-1] << endl;
    }
}
template <typename S>
bool range(S a, S b, S x){
    return (a <= x && x < b);
}

void yes(){
    cout << "Yes" << endl;
}

void no (){
    cout << "No" << endl;
}

ll cel (ll a, ll b){
    if (a % b == 0) return a / b;
    else return a / b + 1;
}

ll gcds(ll a, ll b){
    ll c = a % b;
    while (c != 0){
        a = b;
        b = c;
        c = a % b;
    }
    return b;
}

int main() {
    int a, b; cin >> a >> b;
    cout << a + 1 - b << endl;
}

Measured memory_bytes: 3632
import scala.math.sqrt
import scala.io.Source

object Main extends App {
  val src: Iterator[String] = Source.stdin.getLines

  def deviator(n: Double, li: List[Double]): Double = {
    def predicate(a: Double, b: Double): Double = {
      val avg = li.sum / n
      a + (b-avg)*(b-avg)
    }

    sqrt(li.foldLeft(0.0)(predicate) / n)
  }

  for (n <- src if src.hasNext) {
    val li = src.next.split(" ").map(_.toDouble).toList
    println(deviator(n.toDouble, li))
  }
}

Measured memory_bytes: 92300
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <cmath>
#include <map>
using namespace std;

string nex="abcdefghijklmnopqrstuvwxyza";
//string n(data);
string s;
int K;
vector <int> ord;
string a;
string b;

int main()
{
	cin >> s;
	cin >> K;
	for (int i=0; i<s.size(); i++){
		for (int j=0; j<26; j++){
			a = s[i];
			b = nex[j];
			if (a==b){
				ord.push_back(j);
				break;
			}
		}
	}
	for (int i=0; i<s.size(); i++){
		if (ord[i]==0 && i!=s.size()-1) continue;
		else if (26-ord[i] <= K && i!=s.size()-1){
			K -= 26-ord[i];
			ord[i] = 0;
		}
		else if (i==s.size()-1){
			ord[i] += K;
			ord[i] = ord[i]%26;
		}
	}
	for (int i=0; i<s.size(); i++){
		cout<< nex[ord[i]];
	}
	cout <<endl;
	return 0;
}

Measured memory_bytes: 1148
/**Bismillahir Rahmanir Rahim  *///{
#include <bits/stdc++.h>
using namespace std;
using ll = long long; using ull = unsigned long long; using ld = long double;
const ll llinf = (1ll<<61)-1;
const double eps = 1e-6, ldeps = 1e-9;
#define im(a, b) if (a>=b) a -= b; else if (a<0) a += b;
struct Dbg {
static constexpr auto &os = cout;   // replace by cerr in interactive.
template<class C> static auto dud(C *x)->decltype(os << *x, 0);
template<class C> static char dud(...);
template<class C> typename enable_if<sizeof dud<C>(0)!=1, Dbg&>::type operator<<(const C &x) { os << x; return *this; }
template<class C> typename enable_if<sizeof dud<C>(0)==1, Dbg&>::type operator<<(const C &x) {
    *this << "\n[";
    for (auto &elem : x) *this << elem << ", ";
    return *this << "]";
}
template<class B, class C> Dbg &operator <<(const pair<B, C> &x) {
    return *this << "{" << x.first << ", " << x.second << "}";
}
Dbg &operator<<(ostream&(*x)(std::ostream&)) { os << x; return *this; }
} dbg;
void err(istringstream *iss) { delete iss; }
template<class C, class... Args> void err(istringstream *iss, const C &val, const Args &... args) {
    string name; *iss >> name; if (name.back()==',') name.pop_back();
    dbg << name << " = " << val << "; ", err(iss, args ...);
}
#define bug(args...) dbg << __LINE__ << ": ", err(new istringstream(string(#args)), args), dbg << endl
#define sl(a) int(strlen(a))
#define sz(a) int(a.size())
int n, m, K, T, Q, cn;//}
const int inf = 1000000007, mxn = -1;

int main() { ios_base::sync_with_stdio(0); cin.tie(NULL); cout.precision(10);
    cin >> n;
    cout << n*ll(n-1)/2 << '\n';
}

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

using namespace std;

int main(){
    int n, w, h;
    cin >> n >> w >> h;
    vector<int> p(w+1,0),q(h+1,0);
    for(int i = 0; i < n; i++){
        int x, y, z;
        cin >> x >> y >> z;
        p[max(0,x-z)]++;
        p[min(w,x+z)]--;
        q[max(0,y-z)]++;
        q[min(h,y+z)]--;
    }
    for(int i = 0; i < w; i++){
        p[i+1] += p[i];
    }
    for(int i = 0; i < h; i++){
        q[i+1] += q[i];
    }

    bool a = true, b = true;
    for(int i = 0; i < w; i++){
        if(p[i] == 0) a = false;
    }
    for(int i = 0; i < h; i++){
        if(q[i] == 0) b = false;
    }

    if(a || b){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }
}



Measured memory_bytes: 3608
#include <iostream> 
#include <string> 
#include <vector> 
#include <cmath> 
#include <algorithm> 
#include <cstdlib> 
#include <ctime> 
#include <cstdio> 
#include <functional> 
#include <set> 
#include <sstream> 
#include <cctype>
#include <stack>
#include <queue>
#include <cstring>
#include <map>
 
using namespace std;

int main(){

	int n;
	cin>>n;

	map<int,int> cnt;
	for(int i=0;i<n;i++){
		int a;
		cin>>a;
		cnt[a-1]++;
		cnt[a]++;
		cnt[a+1]++;
	}

	int x,y=-1;
	for(auto it=cnt.begin();it!=cnt.end();it++){
		if(it->second > y){
			x=it->first;
			y=it->second;
		}
	}

	cout<<y<<endl;

	return 0;
}


Measured memory_bytes: 4736
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

int main() {
    ll N;
    string S;
    cin >> N >> S;
    vector<vector<ll>> pos(10, vector<ll>(0));
    rep(i, N) { pos[S[i] - '0'].push_back(i); }
    ll ans = 0;
    rep(l, 10) rep(c, 10) rep(r, 10) {
        if (pos[l].size() == 0 || pos[c].size() == 0 || pos[r].size() == 0)
            continue;
        ll left = pos[l][0];
        ll right = pos[r][pos[r].size() - 1];
        for (ll center : pos[c]) {
            if (left < center && center < right) {
                ans++;
                break;
            }
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 768
#include <iostream>
#include <map>
#include <vector>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <climits>
#include <stack>
#include <queue>
#include <set>
#include <cctype>
#include <bitset>
#include <type_traits>

#include <list>
using namespace std;

#define REP(i, n) for (int i = 0; i < (n); ++i)
#define rep(i, a, b) for (int i = a; i < (b); ++i)
#define YES(j) cout << (j ? "YES" : "NO") << endl;
#define Yes(j) std::cout << (j ? "Yes" : "No") << endl;
#define yes(j) std::cout << (j ? "yes" : "no") << endl;

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

long long lcm(long long a, long long b)
{
    return a * b / gcd(a, b);
}

int main(void)
{
    long long a, b, c, d;
    cin >> a >> b >> c >> d;
    long long x, y;
    a--;
    x = b - b / c - b / d + b / lcm(c, d);
    y = a - a / c - a / d + a / lcm(c, d);
    cout << x - y << endl;
}

Measured memory_bytes: 256