akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <numeric>

#define REP(i, a, b) for (int i = int(a); i < int(b); i++)
using namespace std;
typedef long long int ll;

// clang-format off
#ifdef _DEBUG_
#define dump(...) do{ cerr << __LINE__ << ":\t" << #__VA_ARGS__ << " = "; PPPPP(__VA_ARGS__); cerr << endl; } while(false)
template<typename T> void PPPPP(T t) { cerr << t; }
template<typename T, typename... S> void PPPPP(T t, S... s) { cerr << t << ", "; PPPPP(s...); }
#else
#define dump(...)
#endif
template<typename T> vector<T> make_v(size_t a, T b) { return vector<T>(a, b); }
template<typename... Ts> auto make_v(size_t a, Ts... ts) { return vector<decltype(make_v(ts...))>(a, make_v(ts...)); }
template<typename T>
bool chmin(T &a, T b) { if (a > b) {a = b; return true; } return false;}
template<typename T>
bool chmax(T &a, T b) { if (a < b) {a = b; return true; } return false;}
// clang-format on

#include <queue>
#include <utility>
using P = pair<int, int>;

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    auto S = make_v(n, n, ' ');
    REP(i, 0, n) {
        REP(j, 0, n) {
            cin >> S[i][j];
        }
    }

    auto solve = [&](int start) {
        queue<P> q;
        q.emplace(start, -1);
        vector<int> used(n, -1);
        int ans = 0;
        while (q.size()) {
            queue<P> qq;
            dump(ans);
            while (q.size()) {
                int v = q.front().first;
                int prev = q.front().second;
                q.pop();
                dump(v);
                if (used[v] != -1) continue;
                used[v] = ans;
                REP(i, 0, n) {
                    if (S[v][i] == '1' && prev != i) {
                        if (used[i] != -1 && used[i] + 1 != ans) {
                            return -1;
                        }
                        if (used[i] != -1) continue;
                        dump(i, v);
                        qq.emplace(i, v);
                    }
                }
            }
            ans++;
            q = qq;
        }
        return ans;
    };

    int ans = -1;
    REP(i, 0, n) {
        chmax(ans, solve(i));
    }
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 532
N=int(input())
T=list(map(int,input().split()))
M=int(input())
total=0
for i in range(N):
    total+=T[i]
for i in range(M):
    K=total
    P,X=map(int,input().split())
    K=K-T[P-1]
    K+=X
    print(K)

Measured memory_bytes: 3060
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<tuple>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<deque>
#define rep(i,n) for(int i = 0;i<n;i++)
#define _GLIBCXX_DEBUG
using ll = long long; 
using namespace std;

int main() {
    int n,m;
    cin >> n ;
    vector<string>a(n);
    
    for(int i = 0; i < n; i++){
        cin >> a[i];
    }
    cin >> m;
    vector<string>b(m);
    for(int i = 0; i < m; i++) {
        cin >> b[i];
    }
    int ans = 0;
    for(int i = 0; i < n; i++) {
        int score = 0;
        for(int j = 0; j < n; j++) if(a[i] == a[j]) score++;
        for(int j = 0; j < m; j++) if(a[i] == b[j])score--;
        ans = max(score, ans);
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include<stdio.h>

int main(void){
    int N;
    //数の上限
    scanf("%d",&N);
    int num[N];
    for(int i = 0;i < N;i++){
        scanf("%d",&num[i]);
    }
    int minv = num[0];
    int maxv = num[1] - num[0];
    for(int j = 1;j < N;j++){
      maxv = maxv > (num[j] - minv)?maxv:num[j] - minv;
      minv = minv < num[j]?minv:num[j];
    }
    printf("%d\n",maxv);
}



Measured memory_bytes: 2548
#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;
inline ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
inline ll lcm(ll a, ll b) { return a / gcd(a, b)*b; }
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; }
template<typename T>vector<T> make_v(size_t a){return vector<T>(a);}
template<typename T,typename... Ts>auto make_v(size_t a,Ts... ts){return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));}
template<typename T,typename V> typename enable_if<is_class<T>::value==0>::type fill_v(T &t,const V &v){t=v;}
template<typename T,typename V> typename enable_if<is_class<T>::value!=0>::type fill_v(T &t,const V &v){for(auto &e:t) fill_v(e,v);}
/*
 <url:>
 問題文============================================================
 =================================================================
 解説=============================================================
 ================================================================
 */

template<class Type>
Type solve(Type res = Type()){
    int N; cin >> N;
    vector<int> b(N); for(auto& in:b) cin >> in;

    vector<int> ans;

    while(b.size()){
        bool ok = false;
        for(int j = (int)b.size()-1; j >= 0; j--){
            if(b[j] == (j+1)){
                ok = true;

                b.erase(b.begin()+j);
                ans.emplace_back(j+1);
                break;
            }
        }
        if(!ok){
            cout << -1 << endl;
            return res;
        }
    }
    reverse(ans.begin(),ans.end());
    for(auto v:ans){
        cout << v << endl;
    }
    return res;
}
int main(void) {
    cin.tie(0); ios::sync_with_stdio(false);
    solve<ll>(0);
    // cout << fixed << setprecision(12) << solve<ll>() << endl;
    return 0;
}

Measured memory_bytes: 3640
#include <stdio.h>
char a[20];
int main(void){
    int n;
    scanf("%d",&n);
    for(int i=0;i<20;i++){
        if((n+3)%3==0){
            a[19-i]='0';
        }
        if((n+3)%3==1){
            a[19-i]='+';
            n--;
        }
        if((n+3)%3==2){
            a[19-i]='-';
            n++;
        }
        n/=3;
    }
    int f=0;
    for(int i=0;i<20;i++){
        if(f==i&&a[i]=='0')f++;
    }
    for(int i=f;i<20;i++){
        printf("%c",a[i]);
    }
    printf("\n");
}


Measured memory_bytes: 2680
using System;
using System.Collections;
using System.Collections.Generic;
using System.Text;


public class C
{
	public static void Main()
	{	
		int N = Int32.Parse(Console.ReadLine());
		string[] args = Console.ReadLine().Split(' ');
		int[] A = new int[N];
		for(int i = 0; i < N; i++)
			A[i] = Int32.Parse(args[i]);

		int[] L = new int[N];
		L[0] = A[0];
		for(int i = 1; i < N; i++)
			L[i] = gcd(L[i-1],A[i]);

		int[] R = new int[N];
		R[N-1] = A[N-1];
		for(int i = N-2; i >= 0; i--)
			R[i] = gcd(R[i+1], A[i]);

		int ans = R[1];
		for(int i = 1; i <= N-2; i++)
			ans = Math.Max(ans, gcd(L[i-1],R[i+1]));
		ans = Math.Max(ans, L[N-2]);

		Console.WriteLine(ans);
	}	

	public static int gcd(int x, int y)
	{
		return (y == 0) ? x : gcd(y, x % y);
	}
}





Measured memory_bytes: 25820
from fractions import gcd 
a, b, c, d = list(map(int, input().split()))

def lcm(x, y):
    return (x * y) // gcd(x, y)

can_c_under_a = (a-1)//c
can_d_under_a = (a-1)//d
can_cd_under_a = (a-1)//lcm(c, d)
cant_under_a = (a-1) + can_cd_under_a - can_c_under_a - can_d_under_a

can_c_all = b//c
can_d_all = b//d
can_cd_all = b//lcm(c, d)
cant_all = b + can_cd_all - can_c_all - can_d_all

print(cant_all - cant_under_a)

Measured memory_bytes: 5048
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <stdlib.h>
#include <stdio.h>
#include <bitset>
using namespace std;
#define FOR(I,A,B) for(int I = (A); I < (B); ++I)
typedef long long ll;

int main()
{
  ll K; cin >> K;
  ll N = 50;
  cout << N << endl;
  FOR(i,1,N+1) {
    if(i <= K % N) printf("%lld", K / N + 2 * N - 1 - K % N + 1);
    else printf("%lld", K / N + N - 1 - K % N);
    if(i<N) cout << " ";
  }
  cout << endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<(n); i++)
#define reps(i,s,n) for(int i=(s); i<(n); i++)
#define all(v) v.begin(),v.end()
#define outve(v) for(auto i : v) cout << i << " ";cout << endl
#define outmat(v) for(auto i : v){for(auto j : i) cout << j << " ";cout << endl;}
#define in(n,v) for(int i=0; i<(n); i++){cin >> v[i];}
#define out(n) cout << (n) << endl
#define fi first
#define se second
#define pb push_back
#define mod 1000000007
#define infi 1900000000
#define infl 1100000000000000000
#define cyes cout << "Yes" << endl
#define cno cout << "No" << endl
#define csp << " " <<
#define outset(n) cout << fixed << setprecision(n);
using namespace std;
using ll = long long;
using ld = long double;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vl = vector<ll>;
using vvl = vector<vector<ll>>;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
template<typename T> using ve = vector<T>;
template<typename T> using pq2 = priority_queue<T>;
template<typename T> using pq1 = priority_queue<T,vector<T>,greater<T>>;
template<typename T> bool chmax(T &a, T b) {if(a < b) {a = b;return 1;}return 0;}
template<typename T> bool chmin(T &a, T b) {if(a > b) {a = b;return 1;}return 0;}

int N,M;
vvi G;
vi color;

bool dfs(int u, int v, int c){
    color[u] = c;
    for (int p : G[u]) {
        
        
        if(color[p] != -1){
            if(color[p] == c) return false;
            continue;
        }
        
        if(!dfs(p,u,1-c)) return false;
        
    }
    
    return true;
    
}

int main(){

    cin >> N >> M;
    G.resize(N);
    color.assign(N,-1);
    rep(i,M){
        int a,b;
        cin >> a >> b;
        a--,b--;
        G[a].pb(b);
        G[b].pb(a);
    }
    
    
    if(dfs(0,-1,0)){
        int o = 0;
        rep(i,N){
            if(color[i]) o++;
        }

        cout << (ll)o*(ll)(N-o)-(ll)M << endl;
    }else{
        cout << (ll)(N)*(ll)(N-1)/2-(ll)(M) << endl;
    }
    
    

    return 0;
}


Measured memory_bytes: 6528
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
    vector<int> nr = {1, 0};
    int k;
    cin >> k;
    if (k < 10)
        cout << k;
    else
    {
        k -= 10;
        while (k--)
        {
            int i = nr.size() - 1;
            while (i >= 1 && (nr[i] == nr[i - 1] + 1 || nr[i] == 9)) i--;
            if (i == 0)
            {
                if (nr[0] == 9)
                {
                    nr[0] = 1;
                    for (int it = 1; it < nr.size(); it++)
                        nr[it] = 0;
                    nr.push_back(0);
                }
                else
                {
                    nr[i]++;
                    for (int it = i + 1; it < nr.size(); it++)
                    {
                        if (nr[it - 1] > 0)
                            nr[it] = nr[it - 1] - 1;
                        else
                            nr[it] = 0;
                    }
                }
            }
            else
            {
                nr[i]++;
                for (int it = i + 1; it < nr.size(); it++)
                {
                    if (nr[it - 1] > 0)
                        nr[it] = nr[it - 1] - 1;
                    else
                        nr[it] = 0;
                }
            }
        }
        for (auto x : nr)
            cout << x;
    }
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<string>
#include<queue>
#include<stack>
#include <numeric>
using namespace std;
#define INF (1 << 30) - 1
#define LINF 1LL << 60
const int MOD = 1000000007;
using ll = long long;
using P = pair<int, int>;

int A[4010][4010];

ll dp[4010][4010];

int main(){
  int n;
  cin >> n; 
  vector<ll> w(n);
  vector<ll> sum(n + 1);
  for(int i = 0; i < n; ++i){
  	cin >> w[i];
  	sum[i + 1] += sum[i] + w[i];
  }
  for(int i = 0; i < n; ++i){
  	A[i][i] = i;
  }

  for(int l = 1; l < n; ++l){
  	for(int i = 0; i < n - l; ++i){
  		int j = i + l;
  		int a = A[i][j - 1];
  		int b = A[i + 1][j];
  		ll m = LINF;
  		ll at = -1;
  		for(int k = a; k <= b; ++k){
  			if(k < i || j <= k)continue;
  			ll tm = dp[i][k] + dp[k + 1][j];
  			if(tm <= m){
  				at = k;
  				m = tm;
  			}
  		}
  		dp[i][j] = m + sum[j + 1] - sum[i];
  		A[i][j] = at;
  	}
  }

  cout << dp[0][n - 1] << endl;

  return 0;
}



Measured memory_bytes: 125840
#include <iostream>
#include <cstring>
#include <map>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <set>
#include <vector>
#include <queue>
#include <list>
#include <numeric>
#include <stdio.h>
#include <string>
#include <cstdlib>
#include <math.h>
#include <stack>
#include <climits>
#include <bitset>
#include <utility>


using namespace std;
typedef long long ll;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
// const ll INF = 1LL <<60;
const int INF = 10000;

//最小公倍数
ll gcd(ll x, ll y) {
  ll tmp = 0;
  if (x < y){
    tmp=x;
    x=y;
    y=tmp;
  }
  while (y > 0) {
    ll r = x % y;
    x = y;
    y = r;
  }
  return x;
}

//最大公倍数
ll lcm(ll x,ll y){
  return x/gcd(x,y)*y;
}

//階乗
ll kaijo(ll k){
    ll sum = 1;
    for (ll i = 1; i <= k; ++i)
    {
        sum *= i;
        sum%=1000000000+7;
    }
    return sum;
}

//for(int i = ; i < ; i++){}

ll lmax(ll s,ll t){
  if(s>t){
    return s;
  }
  else{
    return t;
  }
}

ll lmin(ll s,ll t){
  if(s<t){
    return s;
  }
  else{
    return t;
  }
}
// ここから開始

int main(){
  int n,k;
  cin>>n>>k;
  if(k==1) cout<<0<<endl;
  else cout<<n-k<<endl;
  return 0;
}


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

int main(void){
   int H,W;
   cin>>H>>W;
   vector<vector<char>> a(H,vector<char>(W));
   for(int i=0;i<H;i++){
      for(int j=0;j<W;j++){
         cin>>a[i][j];
      }
   }
   vector<vector<char>> result(H+2,vector<char>(W+2));
   for(int i=0;i<H+2;i++){
      for(int j=0;j<W+2;j++){
         if(i==0||i==H+1){
            result[i][j]='#';
         }else{
            if(j==0||j==W+1){
               result[i][j]='#';
            }else{
               result[i][j]=a[i-1][j-1];
            }
         }
      }
   }
   for(int i=0;i<H+2;i++){
      for(int j=0;j<W+2;j++){
         cout<<result[i][j];
      }
      cout<<endl;
   }
   return 0;
}



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

using ll = long long;
using pii = pair<int, int>;

int main() {
    ll K;
    cin >> K;
    const ll MAX = 1e16 + 1000;
    for(int N = 2; N <= 50; ++N) {
        ll mod = K % N;
        ll ma = N - 1 + (K / N) - mod + N;
        if(ma < 0 || MAX < ma) {
            continue;
        }
        cout << N << endl;
        for(int i = 0 ; i < N; ++i) {
            if(i != 0) {
                cout << ' ';
            }
            if(i < mod) {
                cout << ma;
            } else {
                cout << ma - N;
            }
        }
        cout << endl;
        return 0;
    }
}


Measured memory_bytes: 256
number = gets.to_i
args = gets.strip.split.map(&:to_i)
count = 0


def check_even(args)
  args.each do | target |
    unless target.even?
      return false
    end
  end

  true
end

while check_even(args) do
  count += 1
  args = args.map{ |target| target / 2 }
end

puts count

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

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

    int frag = 0;

    for (int i = 1; i < 10; i++)
    {
        for (int j = 1; j < 10; j++)
        {
            if (n == i * j)
            {
                cout << "Yes" << endl;
                frag = 1;
            }
            if (frag == 1)
            {
                break;
            }
        }
        if (frag == 1)
        {
            break;
        }
    }
    if (frag == 0)
    {
        cout << "No" << endl;
    }
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define X first
#define Y second
#define pb emplace_back
#define FOR(i,a,b) for(int (i)=(a);i<(b);++(i))
#define EFOR(i,a,b) for(int (i)=(a);i<=(b);++(i))
#define rep(X,Y) for (int (X) = 0;(X) < (Y);++(X))
#define REP rep
#define rrep(X,Y) for (int (X) = (Y)-1;(X) >=0;--(X))
#define all(X) (X).begin(),(X).end()
#define eb emplace_back

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef ll LL;
typedef pii PII;
typedef pll PLL;
const ll MOD=1e9+7;

#define rall(X) (X).rbegin(),(X).rend()
#define UNIQUE(X) (X).erase(unique(all(X)),(X).end())
#define reps(X,S,Y) for (int (X) = S;(X) < (Y);++(X))
#define rreps(X,S,Y) for (int (X) = (Y)-1;(X) >= (S);--(X))
template<class T> inline bool MX(T &l,const T &r){return l<r?l=r,1:0;}
template<class T> inline bool MN(T &l,const T &r){return l>r?l=r,1:0;}

int N;
LL L;
LL X[214514];
LL ans = 0;

void Process() {
  sort(X, X+N);

  int R = (N+1)/2;
  LL cand = 0;
  rep(i, R) {
    cand += X[i] * 2;
  }
  reps(i, R, N) {
    cand += (L-X[i]) * 2;
  }

  if (N%2) {
    cand -= X[R-1];
  } else {
    cand -= L - X[R];
  }
  MX(ans, cand);

  LL ini = cand;
  int pR = R;
  int idx = 0;
  int rem = N;
  while (rem > 0) {
    if (rem%2) {
      cand -= X[idx] * 2;
      cand += X[R-1];
      cand -= L - X[R];
    } else {
      cand -= X[idx] * 2;
      cand -= L - X[R];
      cand += X[R];
      R += 1;
    }
    MX(ans, cand);
    idx++;
    rem--;
  }
  assert(idx == N);
  assert(R == N);
  
  cand = ini;
  R = pR-1;
  rem = N;
  idx = N-1;
  while (rem > 0) {
    if (rem%2 == 0) {
      cand -= (L - X[idx]) * 2;
      cand += L - X[R+1];
      cand -= X[R];
    } else {
      cand -= (L - X[idx]) * 2;
      cand -= X[R];
      cand += L - X[R];
      R--;
    }
    MX(ans, cand);
    idx--;
    rem--;
  }
  assert(R == -1);
  assert(idx == -1);
}

signed main(){
  ios_base::sync_with_stdio(false);
  cout<<fixed<<setprecision(0);

  cin >> L >> N;
  deque<LL> deq;
  rep(i, N) {
    cin >> X[i];
  }
  
  Process();
  rep(i, N) {
    X[i] = L - X[i];
  }
  Process();
  cout << ans << endl;
}


Measured memory_bytes: 1792
#include <algorithm>
#include <climits>
#include <iostream>
#include <string>
#include <utility>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <iomanip>
#include <cmath>
#include <stack>

using namespace std;
using ll = long long int;

template <class T> ostream &operator<<(ostream &os, vector<T> &v) {
  for (auto i = v.begin(); i != v.end(); i++) {
    os << *i << " ";
  }
  return os;
}
ll dp[110][2][4];
void solve(string N, long long K){
  ll n = N.size();
  dp[0][0][0] = 1;
  for(ll i=0; i<n; i++) {
    ll D = N[i]-'0';
    for(ll j=0; j<2; j++) {
      for(ll k=0; k<=K; k++) {
	for(ll d=0; d <= (j ? 9 : D); d++) {
	  if(k==K and d!=0) continue;
	  dp[i+1][j || (d < D)][k + (k<K and d!=0)] += dp[i][j][k];
	}
      }
    }
  }
  std::cout << dp[n][0][K]+dp[n][1][K] << std::endl;
}

int main(){
  string N;
  cin >> N;
  long long K;
  scanf("%lld",&K);
  solve(N, K);
  return 0;
}



Measured memory_bytes: 256
//http://abc058.contest.atcoder.jp/tasks/arc071_a
#include <iostream>
using namespace std;
 
int n = 0;
string S[50] = {};
 
void readInput(){
    cin >> n;
    for(int i=0; i<n; i++){
        cin >> S[i];
    }
}
 
int main(void){
    readInput();
    int count[50][26] = {};
    const int a = int('a');
    for(int i=0; i<n; i++){
        int size = S[i].size();
        for(int j=0; j<size; j++){
            int c = int(S[i][j])-a;
            count[i][c]++;
        }
    }
    int min;
    for(int i=0; i<26; i++){
        min = 100;
        for(int j=0; j<n; j++){
            if(min > count[j][i]){
                min = count[j][i];
            }
        }
        for(int j=0; j<min; j++){
            cout << char(i+a);
        }
    }
    cout << endl;
    return 0;
}


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

int f(int n) {
  if (n % 2 == 0)
    return n / 2;
  else
    return 3 * n + 1;
}

int main() {
  int s;
  cin >> s;
  vector<bool> key(1000001, false);
  int x, a;
  for (int i = 1;; i++) {
    a = f(x);
    if (i == 1) a = s;
    if (key[a] == true) {
      cout << i << endl;
      return 0;
    } else {
      key[a] = true;
    }
    x = a;
  }
}

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


class SegmentTree():
    def __init__(self, S):
        self.size = 19
        self.array = [set()] * (2**(self.size + 1) - 1)
        for i, c in enumerate(S):
            self.array[i + 2**self.size - 1] = {c}
        for i in range(2**self.size - 1)[::-1]:
            self.array[i] = self.array[2 * i + 1] | self.array[2 * i + 2]

    def subquery(self, l, r, k, i, j):
        # 区間[i,j)の中で区間[l,r)の文字列の集合を返す
        if j <= l or r <= i:
            return set()
        elif l <= i and j <= r:
            return self.array[k]
        else:
            l_set = self.subquery(l, r, 2 * k + 1, i, (i + j) // 2)
            r_set = self.subquery(l, r, 2 * k + 2, (i + j) // 2, j)
            return l_set | r_set

    def query(self, l, r):
        # [l,r)に含まれる文字の種類数
        return len(self.subquery(l, r, 0, 0, 2**self.size))

    def update(self, i, c):
        tmp = i + 2**self.size - 1
        self.array[tmp] = {c}
        while tmp > 0:
            tmp = (tmp - 1) // 2
            self.array[tmp] = self.array[2 * tmp + 1] | self.array[2 * tmp + 2]


N = int(input())
S = [ord(_) - 97 for _ in list(input())]
Q = int(input())
tree = SegmentTree(S)
for q in range(Q):
    t, i, c = input().split()
    if t == '1':
        i = int(i) - 1
        tree.update(i, ord(c) - 97)
    else:
        l, r = int(i) - 1, int(c)
        print(tree.query(l, r))

Measured memory_bytes: 471752
// Shift-JIS（シフトジス）

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int P, Q, R, sumT = 0, maxT = 0;
    cin >> P >> Q >> R;
    sumT += P + Q + R;
    if (maxT < P)
    {
        maxT = P;
    }
    if (maxT < Q)
    {
        maxT = Q;
    }
    if (maxT < R)
    {
        maxT = R;
    }
    cout << sumT - maxT << endl;
}

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

const int MAXN = 1e5+5;
const int INF = 1e9+7;
int a[MAXN],dp[MAXN];
// The minimum we can get from i to 0 house
int main()
{
    for(int i=0;i<MAXN;++i) dp[i] = INF;

    int n;cin >> n;
    for(int i=0;i<n;++i){
        cin >> a[i];
    }

    dp[0] = 0;
    for(int i=1;i<n;++i){
        // We can jump in dp[i-1] or dp[i-2]
        for(int j : {i-1,i-2}){
            if(j>=0) dp[i] = min(dp[i],dp[j] + abs(a[i]-a[j]));
        }
    }
    cout << dp[n-1];
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define ll long long
template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b;return true;}return false;}
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

int main() {
    int X, Y;
    cin >> X >> Y;
    cout << X + Y/2 << endl;
}

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

namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            StringBuilder sb = new StringBuilder();

            while (true)
            {
                int n = int.Parse(Console.ReadLine());

                if (n == 0) break;

                int m = 32;

                int[] nums = Array.ConvertAll(Console.ReadLine().Split(' '), int.Parse);

                for (int i = 0; m > 0; i++)
                {
                    m -= (m - 1) % 5;
                    sb.AppendLine(m.ToString());
                    m -= nums[i % n];
                    sb.AppendLine((m > 0 ? m : 0).ToString());
                }
            }
            Console.Write(sb);
        }
    }
}

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

int64_t comb2(int64_t n){
  return n*(n-1)/2;
}

int main(){
  
  int n; cin >> n;
  vector<vector<char>> character(n, vector<char>(10));
  for(int i=0; i<n; ++i){
    for(int j=0; j<10; ++j){
      cin >> character.at(i).at(j);
    }
    sort(character.at(i).begin(), character.at(i).end());
  }
  
  sort(character.begin(), character.end());
  int64_t sum = 0;
  
  for(int i=0; i<n-1; ++i){
    static int64_t count = 1;
    if(character.at(i) == character.at(i+1)){
      ++ count;
      if(i == n-2){
        sum += comb2(count);
      }
    }
    else{
      sum += comb2(count);
      count = 1;
    }
  }
  
  cout << sum << endl;
  return 0;
}


Measured memory_bytes: 5760
#include<bits/stdc++.h>
/* Properties of modulo:Fermat's little theorem
	(a/b)%m ,where m is prime  = (a%m) * (b^(m-2))%m
*/
using namespace std;
#define IOS { ios :: sync_with_stdio(false); cin.tie(0); cout.tie(0); }
#define ll long long
#define pb push_back
#define gcd __gcd
#define nl cout<<"\n"
#define endl "\n"
#define rep(i,n) for(ll i = 0 ; i < n ; i++)
#define fo(i,a,b) for(ll i = a ; i <= b ; i++)
#define foi(i,a,b) for(ll i = a ; i >= b ; i--)
#define all(c) (c).begin(),(c).end()
#define trav(a,x) for(auto a = x.begin() ; a != x.end() ; a++)
#define lb lower_bound
#define ub upper_bound
//sorting in reverse order
bool compare(ll x, ll y){
    return x>y;
}
// checking whether a number is prime or not
ll isprime(ll n){
    if(n==1) return 0;
    else if(n==2) return 1;
    else{
        for(ll i=2;i<=sqrt(n);i++){
            if(n%i==0) return 0;
        }
    return 1;   
    }
}
// returning vector containing all prime numbers less than a given number
vector<ll> get_prime_factors_less_than(ll n){
    vector<ll> factor;
    vector<ll> prime(n,1);
    prime[0]=0,prime[1]=0;
    for(ll i = 2 ; i <= n ; i++){
        if(prime[i]==1){
            for(ll j=i*i;j<=n;j=j+i) prime[j]=0; 
            factor.push_back(i);
        }
    }
    return factor;
}
//returns x^y in order logn 
ll power(ll x, ll y) { 
    if (y == 0) return 1; 
    ll a = power(x,y/2);
    if (y % 2 == 0) return a * a; 
    else return x * a * a; 
} 
const float a =6.28318530717958623200;
int main(){
    IOS;
    ll test,i;
    test = 1;
   // cin>>test;
    while(test--){
        float r;
        cin>>r;
        cout<<setprecision(10)<<a*r<<endl;   
    }
    cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
}


Measured memory_bytes: 3832
#include <bits/stdc++.h>
#define f first
#define s second
#define fore(i,a,b) for(int i = (a), ThxMK = (b); i < ThxMK; ++i)
#define pb push_back
#define all(s) begin(s), end(s)
#define _ ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define sz(s) int(s.size())
#define ENDL '\n'
using namespace std;
typedef long double ld;
typedef long long lli;
typedef pair<lli,lli> ii;
typedef vector<int> vi;
typedef vector<lli> vl;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
#define deb(x) cout << #x": " << (x) << endl;

const int N = 3e3+5;
const lli INF = 1e18;
const lli MOD = 1e9+7;

vi m;
vi primes(1,2);
vector<vector<ld>>nk;
void sieve(){
	m = vi(N+1,0);
	for(int i = 4; i<N; i+=2)m[i]=1;
	for(int i = 3; i*i<=N; i+=2)if(!m[i])for(int j = i*i; j<N; j+=i)m[j]=1;
	for(int i = 3; i<N; i+=2)if(!m[i])primes.pb(i);
}

void pascal(){
	nk =vector<vector<ld>>(N,vector<ld>(N,0.0));
	fore(i,0,N)nk[i][0]=nk[i][i]=1.0;
	fore(i,1,N)fore(j,1,i)nk[i][j]=nk[i-1][j-1]+nk[i-1][j];
}

lli gcd(lli a, lli b){return (b?gcd(b,a%b):a);}

lli lcm(lli a, lli b){
	if(a<b)swap(a,b);
	lli c = gcd(a,b);
	a/=c;
	return a*b;
}

int popcount(lli x) { return __builtin_popcountll(x); }

lli poww(lli a, lli b){
	lli res =1;
	while(b){
		if(b&1) res = res * a;
		a = a*a;
		b/=2;
	}
	return res;
}

lli powm(lli a, lli b){
	lli res =1;
	while(b){
		if(b&1) res = (res * a)%MOD;
		a = (a*a)%MOD;
		b/=2;
	}
	return res;
}

bool isPrime(lli x){
	if(x==1)return 0;
	for(auto i:primes){
		if(i*i>x)return 1;
		if(x%i==0)return 0;
	}
	return 1;
}

lli SUM(lli a, lli b, lli mod=MOD){
	return (a+b+mod)%mod;
}

int dx[4]={-1,0,0,1}, dy[4]={0,1,-1,0};

// ---- コーディングはここから！ ('-')7

void solve(){
	int n,k; cin>>n>>k;
	vi v(n);
	fore(i,0,n)cin>>v[i];
	vl dp(k+1,0); dp[0]=1;
	fore(i,0,n){
		vl to(k+1);
		for(int j=k;j>=0;j--){
			int l = j+1;
			int r = j+min(k-j,v[i]);
			if(l<=r){
				to[l]=SUM(to[l],dp[j]);
				if(r<k)to[r+1]=SUM(to[r+1],-dp[j]);
			}
		}
		int sum = 0;
		fore(j,0,k+1)sum = SUM(sum,to[j]), dp[j]=SUM(dp[j],sum);
	}
	cout<<dp[k]<<ENDL;

}

int main(){_
	//int t; cin>>t; while(t--)
	solve();
}


Measured memory_bytes: 4712
/// Author: Yen-Jen Wang
#include <bits/stdc++.h>

using namespace std;

int main() {
	int a, b, c;
	cin >> a >> b >> c;
	vector<int> vs = {a, b, c};
	sort(vs.begin(), vs.end());
	if (vs[0] != vs[1]) cout << vs[0] << '\n';
	else cout << vs[2] << '\n';
	return 0;
}

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

#define _overload(_1,_2,_3,name,...) name
#define _rep(i,n) _range(i,0,n)
#define _range(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload(__VA_ARGS__,_range,_rep,)(__VA_ARGS__)

#define _rrep(i,n) _rrange(i,n,0)
#define _rrange(i,a,b) for(int i=int(a)-1;i>=int(b);--i)
#define rrep(...) _overload(__VA_ARGS__,_rrange,_rrep,)(__VA_ARGS__)

#define _all(arg) begin(arg),end(arg)
#define uniq(arg) sort(_all(arg)),(arg).erase(unique(_all(arg)),end(arg))
#define getidx(ary,key) lower_bound(_all(ary),key)-begin(ary)
#define clr(a,b) memset((a),(b),sizeof(a))
#define bit(n) (1LL<<(n))
#define popcount(n) (__builtin_popcountll(n))

using namespace std;

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

using ll = long long;
using R = long double;
const R EPS = 1e-9L; // [-1000,1000]->EPS=1e-8 [-10000,10000]->EPS=1e-7
inline int sgn(const R& r) {return (r > EPS) - (r < -EPS);}
inline R sq(R x) {return sqrt(max(x, 0.0L));}

const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};

// Problem Specific Parameter:

const int inf = 1 << 20;

int main(void) {

	string tmp;
	cin >> tmp;

	const int n = tmp.size();
	vector<int> a, b;

	rep(i, n) a.push_back(tmp[i] - '0');

	cin >> tmp;
	rep(i, n) b.push_back(tmp[i] - '0');

	bool alls = true , allz = true;
	rep(i, n) {
		if (a[i] != b[i]) alls = false;
		if (b[i] != 0) allz = false;
	}

	if (alls) {
		cout << 0 << endl;
		return 0;
	}

	if (allz) {
		cout << -1 << endl;
		return 0;
	}

	int ans = inf;
	vector<int> toL(n),toR(n);

	toR[n - 1] = (b[n - 1] == 1 ? n - 1 : inf);

	rrep(i, n - 1) {
		toR[i] = toR[i + 1];
		if (b[i] == 1) toR[i] = i;
	}

	rrep(i, n) if (toR[i] == inf) toR[i] = toR[0] + n;

	toL[0] = (b[0] == 1 ? 0 : inf);

	rep(i, 1, n) {
		toL[i] = toL[i - 1];
		if (b[i] == 1) toL[i] = i;
	}

	rep(i, n) if (toL[i] == inf) toL[i] = toL[n - 1] - n;

	for (int sh = -n; sh <= n; ++sh) {
		int cur = abs(sh);
		using pii = pair<int, int>;
		vector<pii> ary; // Left Right

		rep(i, n) {
			const int j = (i + sh + n) % n;
			if (a[i] == b[j]) continue;
			cur++;
			pii in;
			if (sh <= 0) {
				in.first = j - toL[j];
				in.second = toR[i] - i;
				if (i - toL[i] > -sh) ary.push_back(in);
			} else {
				in.first = i - toL[i];
				in.second = toR[j] - j;
				if (toR[i] - i > sh)  ary.push_back(in);
			}
		}

		ary.push_back(pii(0, 0));
		sort(begin(ary), end(ary));

		const int m = ary.size();
		int cmax = 0, best = ary[m - 1].first;
		rrep(i, m, 1) {
			chmax(cmax, ary[i].second);
			chmin(best, ary[i - 1].first + cmax);
		}
		chmin(ans, cur + 2 * best);
	}

	cout << ans << endl;

	return 0;
}

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


using namespace std;


#ifdef zxc

#include "debug.h"

#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

using ll = int64_t;
using ld = long double;
const ld EPS = 1e-8;
const ll MOD = 1e9 + 7;
const ld PI = 3.141592653589793;
const int maxn = 10001;

void fast_io() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
}

int a[5000];

struct set_with_add {
    set<pair<int, int>> s;
    int add_ = 0;

    void add(int val) {
        add_ += val;
    }

    void insert(int pos, int x) {
        x -= add_;
        s.emplace(x, pos);
    }

    pair<int, int> max() {
        if (s.empty()) {
            return {-1, -1};
        }
        auto it = *s.rbegin();
        it.first += add_;
        return it;
    }
};

set_with_add sets[26];

signed main() {
#ifdef zxc
    mt19937 mt(228);
    freopen("../kolya_input.txt", "r", stdin);
//    freopen("../kolya_output.txt", "w", stdout);
#else
    mt19937 mt(std::chrono::high_resolution_clock::now().time_since_epoch().count());
//            freopen("", "r", stdin);
//        freopen("hack.out", "w", stdout);
#endif
    fast_io();
    cout.precision(10);
    cout << fixed;
    auto start = chrono::steady_clock::now();

    string s;
    cin >> s;
    int ind = -1;
    for (char c:s) {
        ++ind;
        int id = c - 'a';
        auto mx = sets[id].max();
        if (mx.first + 1 > 0) {
            cout << mx.second + 1 << " " << ind + 1;
            return 0;
        }
        sets[id].add(1);
        sets[id].insert(ind, 1);
        for (int i = 0; i < 26; ++i) {
            if (i != id) {
                sets[i].add(-1);
            }
        }
    }
    cout << -1 << " " << -1;
    auto end = chrono::steady_clock::now();
    debug("time", chrono::duration_cast<chrono::milliseconds>(end - start).count() / 1000.0);

}



Measured memory_bytes: 5072
S = [int(i) for i in input()]
K = int(input())

if sum(S)==len(S):
    print(1)
else:
    for i in range(len(S)):
        if S[i]!=1:
            print(S[i])
            break
        elif S[i]==1 and K-1<=i:
            print(1)
            break

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

using namespace std;

void solve()
{
	int N, Q;
	cin >> N >> Q;
	int yearPre = 0;
	string namePre = "kogakubu10gokan";
	vector<string> data(51);
	for (int i = 1; i <= N; ++i)
	{
		int year;
		string name;
		cin >> year >> name;
		for (int j = yearPre; j < year; ++j)
		{
			data[j] = namePre;
		}
		yearPre = year;
		namePre = name;
	}
	for (int i = yearPre; i < 51; ++i)
	{
		data[i] = namePre;
	}
	cout << data[Q] << endl;
}

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

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

int main() {
 int A,B,C,D;
 cin >> A >> B >> C >> D;
 for (int i=0; true; i++){
  C-=B;
  if(C<=0){
   cout << "Yes" << endl;
   break;
  }
  A-=D;
  if(A<=0){
   cout << "No" << endl;
   break;
  } 
 }
}  


Measured memory_bytes: 3632
<?php

list($n, $m) = explode(' ', trim(fgets(STDIN)));

$cor = 0;
$a = [];
$list = [];
for ($i=0; $i<$m; $i++) {
    list($p, $s) = explode(' ', trim(fgets(STDIN)));

    // AC済ならスキップ
    if (isset($a[$p])) {
        continue;
    }

    // ACを数える
    if ($s == 'AC') {
        $cor++;
        $a[$p] = 1; // flag on
    } else {
        if (!isset($list[$p])) {
            $list[$p] = [];
        }
        $list[$p][] = $s;
    }
}

// ACしている問題のみ、ACするまでのWAを足す
$pen = 0;
foreach ($list as $p => $li) {
    if ( !isset($a[$p]) ) { continue; }
    $pen += count($li);
}

echo "$cor $pen\n";

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

struct Node
{
	int a, b;
};
bool cmp(Node &n1, Node &n2)
{
	return n1.a < n2.a;
}

int main()
{
	int N;
	long long K;
	cin >> N >> K;
	vector<Node> vec(N);

	for (int i = 0; i < N; ++i)
	{
		cin >> vec[i].a >> vec[i].b;	
	}
	sort(vec.begin(), vec.end(), cmp);
	for (int i = 0; i < N; ++i)
	{
		if (K > vec[i].b)
		{
			K -= vec[i].b;
		}
		else {
			cout << vec[i].a << endl;
			break;
		}
	}
	return 0;
}

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


int main (){
    int N;
    cin>>N;
    vector<pair<int, int>> Vec;
    for(int i=0; i<N; i++){
        int a, b;
        cin>>a>>b;
        Vec.emplace_back(b, a);
    }
    sort(Vec.begin(), Vec.end());
    bool Check=true;
    long long Sum=0;
    for(int i=0; i<N; i++){
        Sum+= Vec.at(i).second;
        if(Sum>Vec.at(i).first){
            Check=false;
            break;
        }
    }
    cout<<(Check?"Yes":"No");
}

Measured memory_bytes: 2420
#include <bits/stdc++.h>
#define repr(i,from,to) for(int (i)=(from);(i)<(to);(i)++)
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
// const bool debug=true;
const bool debug=false;
#define DEBUG if(debug==true)
#define vprint(x) for(auto a:(x)) cout << x << endl;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll MOD =998244353;
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;
}
int main(void) {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n;cin>>n;
    vector<ll> d(n);rep(i,n)cin>>d[i];
    vector<bool> chk(n+10,false);
    if (d[0] != 0) {
        cout << 0 << endl;
        return 0;
    } 
    sort(begin(d), end(d));
    function<ll(ll,ll)> modpow = [&](ll a, ll b) {
        ll res = 1;
        rep(i,b) {
            res *= a;
            res %= MOD;
        }
        return res;
    };
    ll res = 1;
    ll cur=1,cnt = 0, now = 1,cnt_prev=1;
    while(cur<n) {
        cnt = 0;
        while(cur<n&&d[cur]==now) {
            cnt++;
            cur++;
        }
        res *= modpow(cnt_prev, cnt);
        res %= MOD;
        cnt_prev = cnt;
        now++;
        if (cur==n)break;
        if (now!=d[cur]) {
            cout << 0 << endl;
            return 0;
        }
    }
    cout << res << endl;
    return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using u32 = uint32_t;
using vi = vector<int>;    using vvi = vector<vi>;
using vb = vector<bool>;   using vvb = vector<vb>;
using vl = vector<ll>;     using vvl = vector<vl>;
using vd = vector<double>; using vvd = vector<vd>;

#define MAXC(c, x) (c = max(c, x))
#define MINC(c, x) (c = min(c, x))

#define REP(i,n) for(auto i = 0 * (n), i##_len = (n); i < i##_len; ++i)
#define ALL(c) (c).begin(), (c).end()
#define FOR(i,s,n) for(ll i=s, i##_len=(ll)(n); i<i##_len; ++i)
#define TEN(x) ((ll)1e##x)
const ll mod = TEN(9) + 7;

const ll INF = 1e9;

int main() {
	#ifdef INPUT_FROM_FILE
	ifstream cin("sample.in");
	ofstream cout("sample.out");
	#endif
	cin.tie(0);
	ios_base::sync_with_stdio(false);
	cout << fixed << setprecision(50);

	string s; cin >> s;
	ll n = s.size();

	vector<int> tbl(1 << 26, -2);
	tbl[0] = -1;

	ll alp = 0;
	vl dp(n + 1, TEN(10));
	dp[0] = 0;
	REP(i, n) {
		alp ^= 1 << (s[i] - 'a');
		if (__builtin_popcountll(alp) == 0) {
			dp[i + 1] = 1;
		} else {
			REP(j, 26) {
				ll c = 1 << j;
				if (c & alp == 0) continue;
				if(tbl[alp ^ c] != -2) MINC(dp[i + 1], 1 + dp[tbl[alp ^ c] + 1]);
			}
		}
		if (tbl[alp] == -2 || dp[tbl[alp] + 1] > dp[i + 1]) tbl[alp] = i;
	}
	//REP(i, n) cout << dp[i] << endl;
	//cout << endl;
	//REP(i, 26) cout << tbl[i] << endl;
	cout << dp[n] << endl;

	return 0;
}


Measured memory_bytes: 264340
n = int(input())
a = list(map(int,input().split()))
A = list(set(a))
flag = True
if n%2==0:
  if a.count(0)>0 or len(A)!=len(a)//2:
    flag=False
else:
  if a.count(0)!=1 or len(A)!=len(a)//2+1:
    flag=False
if flag==True:
    print((2**(n//2))%(10**9+7))
else:
  print(0)

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

int main() {
  int a,b;
  cin >> a >> b;
  if((a > b || a== 1) && !(b ==1)){
    cout << "Alice" <<endl;
  }
  else if(a < b || b == 1 && !(a == 1)){
    cout << "Bob" <<endl;
  }
  else if(a ==b){
    cout << "Draw" <<endl;
  }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define int long long
#define inf 200000000000000000
#define N 200050
using namespace std;

int n, q, S, T, A[N], bit[N], ans;

void upd(int l, int r, int x)
{
	if(1 <= l && l <= n + 1) for(int i = l; i < N; i += (i&-i)) bit[i] += x;

	if(1 <= r + 1&& r + 1 <= n + 1) for(int i = r + 1; i < N; i += (i&-i)) bit[i] -= x;
}

int query(int x)
{
	int aux = 0;

	if(x <= 0 || x > n + 1) return inf;

	for(int i = x; i > 0; i -= (i&-i)) aux += bit[i];

	return aux;
}

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

	cin>>n>>q>>S>>T;

	for(int i = 1; i <= n + 1; i++) cin>>A[i], upd(i, i, A[i]);

	for(int i = 1; i <= n; i++) ans += (A[i] <= A[i + 1] ? (- A[i + 1] + A[i])*S : (A[i] - A[i + 1])*T);

	for(int i = 1; i <= q; i++)
	{
		int li, ri, xi;

		cin>>li>>ri>>xi;

		li ++, ri ++;

		int Hl = query(li);

		int Hr = query(ri);

		int H_depois = query(ri + 1);

		int H_antes = query(li - 1);

		upd(li, ri, xi);

		int dl = 0, dr = 0;

		if(H_antes != inf && H_antes <= Hl) dl -= abs(Hl - H_antes)*S ;

		else if(H_antes  != inf) dl += abs(Hl - H_antes)*T;

		if(Hr <= H_depois && H_depois != inf) dr -= abs(H_depois - Hr)*S ;

		else if(H_depois != inf) dr += abs(H_depois - Hr)*T;

		ans = ans - dl - dr;

		Hl += xi, Hr += xi;

		dl = 0, dr = 0;

		if(H_antes <= Hl&& H_antes != inf) dl -= abs(Hl - H_antes)*S ;

		else if(H_antes != inf) dl += abs(Hl - H_antes)*T;

		if(Hr <= H_depois && H_depois != inf) dr -= abs(H_depois - Hr)*S ;

		else if(H_depois != inf) dr += abs(H_depois - Hr)*T;

		ans += dl + dr;

		cout<<ans<<"\n";
	}
}

Measured memory_bytes: 6324
// Created by ...Lusifer
#include<bits/stdc++.h>
using namespace std;
 
#define pb 		push_back
#define mp 		make_pair
#define prior   priority_queue
#define MOD 	1000000007
#define INF64 	(long long)1e18
#define INF 	(int)1e9
#define PI 		3.1415926535897932384626433832795 
#define ll      long long
#define ld		long double
#define ret     return
#define NUM 	1000001
const int SIZE = 2e5+4;
void fastio(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
}

void solveTest(){
	ll a,b,c,k;
	cin>>a>>b>>c>>k;
	ll d = a-b;
	if(k%2==0){
		cout<<d<<endl;
	}
	else {
		cout<<-d<<endl;
	}
	return ;
}
 
int main(){
	fastio();

	int t=1;
	//cin>>t;
	while(t--){
		solveTest();
 
	}
	return 0;
}

Measured memory_bytes: 256
import sys
write=sys.stdout.write

buildings=[[[],[],[]],[[],[],[]],[[],[],[]],[[],[],[]]]
for i in range(0,4):
    for j in range(0,3):
        for k in range(0,10):
            buildings[i][j].append(0)

informations=int(input())

for i in range(0,informations):
    information=[]
    information=input().split()
    information[0]=int(information[0])
    information[1]=int(information[1])
    information[2]=int(information[2])
    information[3]=int(information[3])
    buildings[information[0]-1][information[1]-1][information[2]-1]+=information[3]

for i in range(0,4):
    for j in range(0,3):
        for k in range(0,10):
            write(' ')
            write(str(buildings[i][j][k]))
        print()
    if i !=3:
        for j in range(0,20):
            write('#')
        print()

Measured memory_bytes: 7788
#include<stdio.h>

int main(void) {

	int a1, a2, a3;
	int sum;

	scanf("%d %d %d", &a1, &a2, &a3);
	sum = a1 + a2 + a3;

	if (sum >= 22) {
		printf("bust\n");
	}
	else {
		printf("win\n");
	}
	

	return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD=1e9+7;
const int INF=1e9;

bool M[10][10];

int main(){
    int n,m;
    cin>>n>>m;
    for(int i=0;i<m;i++){
        int a,b;
        cin>>a>>b;
        M[a][b]=true;
        M[b][a]=true;
    }
    int p[10];
    for(int i=0;i<n;i++){
        p[i]=i+1;
    }
    int ans=0;
    do{
        bool flag=true;
        for(int i=0;i<n-1;i++){
            if(!M[p[i]][p[i+1]]){
                flag=false;
                break;
            }
        }
        if(flag)ans++;
    }while(next_permutation(p+1,p+n));
    cout<<ans<<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
//useful 
#define rep(i,n) for(int i = 0; i < (n); i++)
int long long gcd(int long long a, int long long b){
    return b?gcd(b,a%b):a;
} //最大公約数
int long long lcm(int long long a, int long long b){
    return a/gcd(a,b)*b;
} //最小公倍数
int long long GetDigit(int long long num){
    int long long digit=0;
    while(num!=0){
        num /= 10;
        digit++;
    }
    return digit;
} //桁数
int long long GetDigitN(int long long num, int long long N){
    int long long digit=0;
    while(num!=0){
        num /= N;
        digit++;
    }
    return digit;
} //十進数でnumの際のN進数における桁数
int long long GetDigitSum(int long long n){
    if(n < 10){
       return n;
    }
    return GetDigitSum(n/10) + n%10;
} //十進数の桁和
unsigned int long long unsignedGetDigitSum(unsigned int long long n){
    if(n < 10){
       return n;
    }
    return unsignedGetDigitSum(n/10) + n%10;
} //十進数の桁和unsigned
int long long divisorcount(int long long n){
	int long long ans = 1;
	vector<int> x(n + 1);
	int long long num = n; // 素因数分解する変数num 
	for (int long long i = 2; i <= n; i++) {
		while (num%i == 0) { // 素数で割り切れなくなるまで割っていく
			x.at(i)++; //割った個数を配列に足す
			num /= i;
		}
	}
	for (int i = 2; i <= n; i++){
		ans *= x.at(i) + 1; //それぞれを+1して掛けていく
	}
    return ans;
} //約数カウント


int main(){
    int N;
    cin >> N;
    int ans = 0;
    for(int i = 1; i <= N; i++){
        for(int j = 1; (j < N) && (i*j < N); j++){
            if (i*j < N){
                ans = ans + 1;
            }
            
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3624
S = input().strip()
N = len(S)
MOD = 10**9+7
dp = [[0] * 13 for _ in range(N + 1)]
dp[0][0] = 1
mul = 1

for i in range(N):
    x = S[i]
    for j in range(13):
        if x == '?':
            for k in range(10):
                dp[i + 1][(j * 10 + k) % 13] += dp[i][j]
                dp[i + 1][(j * 10 + k) % 13] %= MOD
        else:
            n = int(x)
            dp[i + 1][(j * 10 + n) % 13] += dp[i][j]
            dp[i + 1][(j * 10 + n) % 13] %= MOD


print(dp[N][5] % MOD)



Measured memory_bytes: 61788
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)   FOR(i,0,n)
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<int,int> pint;

ll a[50];
int main(){
    ll k;
    cin>>k;
    if(k==1){
        cout<<2<<endl;
        cout<<0<<" "<<2<<endl;return 0;
    }
    else if(k==0){
        cout<<2<<endl;
        cout<<1<<" "<<1<<endl;return 0;
    }
    int n=min(50ll,k);
    ll r=k%n;
    rep(i,n){
        a[i]=(k/n)-1+n;
    }
    rep(i,r)a[i]+=1;
    FOR(i,r,n) a[i]-=r;
    cout<<n<<endl;
    rep(i,n) cout<<a[i]<<" ";
    cout<<endl;
    return 0;
}

Measured memory_bytes: 256
a = list(map(int, input().split()))
x = abs(a[0] - a[1]) + abs(a[1] - a[2])
y = abs(a[0] - a[2]) + abs(a[1] - a[2])
z = abs(a[0] - a[1]) + abs(a[0] - a[2])
print(min(x, y, z))

Measured memory_bytes: 3060
#include<iostream>
using namespace std;
#define MAX 500000
#define SENTINEL 2000000000
int L[MAX / 2 + 2], R[MAX / 2 + 2];
int cnt;

void merge(int A[], int n, int left, int mid, int right)
{
	int n1 = mid - left;
	int n2 = right - mid;
	for (int i = 0; i < n1; i++)
	{
		L[i] = A[left + i];
	}
	for (int i = 0; i < n2; i++)
	{
		R[i] = A[mid + i];
	}
	L[n1] = R[n2] = SENTINEL;
	int i = 0, j = 0;
	for (int k = left; k < right; k++)
	{
		cnt++;
		if (L[i] <= R[j])
		{
			A[k] = L[i++];
		}
		else
			A[k] = R[j++];
	}
}
void mergesort(int A[], int n, int left, int right)
{
	if (left + 1 < right)
	{
		int mid = (left + right) / 2;
		mergesort(A, n, left, mid);
		mergesort(A, n, mid, right);
		merge(A, n, left, mid, right);
	}
}
int main()
{
	int A[MAX], n, i;
	cnt = 0;
	cin >> n;
	for (i = 0; i < n; i ++) cin >> A[i];
	mergesort(A, n, 0, n);
	for (i = 0; i < n; i++)
	{
		if (i) cout << " ";
		cout << A[i];
	}
	cout << endl;
	cout << cnt << endl;
}


Measured memory_bytes: 7004