akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h> 
using namespace std;
#define For(i,n) for(int i=1;i<=n;i++)
#define Fork(i,k,n) for(int i=k;i<=n;i++)
#define ForkD(i,k,n) for(int i=n;i>=k;i--)
#define Rep(i,n) for(int i=0;i<n;i++)
#define ForD(i,n) for(int i=n;i;i--)
#define RepD(i,n) for(int i=n;i>=0;i--)
#define Forp(x) for(int p=pre[x];p;p=next[p])
#define Forpiter(x) for(int &p=iter[x];p;p=next[p])  
#define Lson (o<<1)
#define Rson ((o<<1)+1)
#define MEM(a) memset(a,0,sizeof(a));
#define MEMI(a) memset(a,0x3f,sizeof(a));
#define MEMi(a) memset(a,128,sizeof(a));
#define MEMx(a,b) memset(a,b,sizeof(a));
#define INF (0x3f3f3f3f)
#define F (1000000007)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define vi vector<int> 
#define pi pair<int,int>
#define SI(a) ((a).size())
#define Pr(kcase,ans) printf("Case #%d: %lld\n",kcase,ans);
#define PRi(a,n) For(i,n-1) cout<<a[i]<<' '; cout<<a[n]<<endl;
#define PRi2D(a,n,m) For(i,n) { \
						For(j,m-1) cout<<a[i][j]<<' ';\
						cout<<a[i][m]<<endl; \
						} 
#pragma comment(linker, "/STACK:102400000,102400000")
#define ALL(x) (x).begin(),(x).end()
#define gmax(a,b) a=max(a,b);
#define gmin(a,b) a=min(a,b);
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
ll mul(ll a,ll b){return (a*b)%F;}
ll add(ll a,ll b){return (a+b)%F;}
ll sub(ll a,ll b){return ((a-b)%F+F)%F;}
void upd(ll &a,ll b){a=(a%F+b%F)%F;}
inline int read()
{
	int x=0,f=1; char ch=getchar();
	while(!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();}
	while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar();}
	return x*f;
} 
#define	MAXN (3000)
int a[MAXN];
bitset<4000001>f,g;
int main()
{
//	freopen("C.in","r",stdin);
//	freopen(".out","w",stdout);
	int n=read();
	For(i,n) a[i]=read();
	f.reset();g.reset();
	f[0]=1;
	For(i,n){
		f=f|(f<<a[i]);
		f.set(a[i]);
	}
	int p=f.count();
//	cout<<p<<endl;
//	p=(p+1)/2;
	vi v;
	for(int i=0;i<=4000000;i++) if (f[i]) v.pb(i);
//	for(auto p:v)cout<<p<<' ';

	cout<<v[p/2]<<endl;
	exit(0);
	for(int i=0,l=-1;;i++) {
		if(f[i]) {
			++l;
			if(l==p/2) {
				cout<<i<<endl;return 0;
			}
		} 
	}
	
	return 0;
}


Measured memory_bytes: 11948
s = gets.chomp.split(//)

ans = 0
(2**(s.size-1)).times do |i|
  switchs = i.to_s(2).split(//)
  (s.size - switchs.length - 1).times{switchs.unshift('0')}

  nums = []
  current = 0
  len = 0
  # p ['switch', switchs]
  switchs.each_with_index do |switch, i|
    len += 1
    if switch == '1'
      # p [s.join('').to_i, current, len]
      nums.push s.slice(current, len).join('').to_i
      current = i + 1
      len = 0
    end
  end
  nums.push s.slice(current, s.size-current).join('').to_i

  # p ['nums', nums]
  ans += nums.inject(:+)
end

puts ans

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

int main() {
	int N;
	cin >> N;
	vector<int> H(N);

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

	int count = 0;
	int max_count = 0;

	for (int i = 0; i < N-1; i++) {
		if (H.at(i) >= H.at(i + 1)) {
			count++;
		}
		else {
			count = 0;
		}
		max_count = max(count, max_count);
	}

	cout << max_count << endl;
}

Measured memory_bytes: 640
import sys
import itertools
# import numpy as np
import time
import math
from heapq import heappop, heappush
from collections import defaultdict
from collections import Counter
from collections import deque
from itertools import permutations
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())
S = input()
K = int(input())

ans = []
for i, c in enumerate(S):
    if c == 'a':
        ans.append(c)
        continue
    num = ord('z') - ord(c) + 1
    if K >= num:
        K -= num
        ans.append('a')
    else:
        ans.append(c)
if K > 0:
    ans[-1] = chr((ord(ans[-1]) - ord('a') + K % 26) % 26 + ord('a'))
print("".join(ans))
    


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

using namespace std;

int main()
{
	int i, j, k;
	int n, m;

	cin >> n >> m;

	vector<int> x;
	x.resize(m);

	for (i = 0; i < m; i++)
	{
		cin >> x[i];
	}

	sort(x.begin(), x.end(), [](const int& o1, const int& o2) { return o1 < o2; });

	vector<int> y;
	y.resize(m - 1);

	for (i = 0; i < m - 1; i++)
	{
		y[i] = x[i + 1] - x[i];
	}

	sort(y.begin(), y.end(), [](const int& o1, const int& o2) { return o1 > o2; });

	int result = 0;

	for (i = n - 1; i < m - 1; i++)
	{
		result += y[i];
	}

	printf("%d", result);

	return 0;
}


Measured memory_bytes: 1024
//============================================================================
// Name        : JOI.cpp
// Author      :
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <math.h>
#include <stdio.h>
#include <vector>
using namespace std;
typedef long long ll;
string S;
int main() {
	cin>>S;

	int D=0,E=0,F=0;
	int ans=0;
	int A,B,C;
	for(int i=0;i<S.size();i=C){
		for(A=i;S[A]=='J';A++);
		for(B=A;S[B]=='O';B++);
		for(C=B;S[C]=='I';C++);
		D=A-i;
		E=B-A;
		F=C-B;
		if(D>=E&&E<=F)ans=max(ans,E);
	}

	cout<<ans<<endl;
	return 0;
}



Measured memory_bytes: 3992
#include <bits/stdc++.h>
using namespace std;
#ifndef ONLINE_JUDGE
#include "debug.h"
#else
#define debug(x...)
#endif
#define int long long
#define all(c) (c).begin(),(c).end()
#define rall(c) (c).rbegin(),(c).rend()
#define rep(i,a,b) for(int i=a;i<b;i++)
#define loop(i,c) for(auto i=(c).begin();i!=(c).end();i++)
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define F first
#define S second
const int mod =  1000000007;

void solving() {
	int n;
	cin >> n;
	int a[n], freq[100001] {}, sum = 0;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
		freq[a[i]]++;
		sum += a[i];
	}
	int q;
	cin >> q;
	while (q--) {
		int b1, c1;
		cin >> b1 >> c1;
		int x = freq[b1];
		int tmp = x * (c1 - b1);
		sum += tmp;
		freq[b1] = 0;
		freq[c1] += x;
		cout << sum << endl;
	}
}

int32_t main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	// int t{}; cin >> t; while (t--)
	solving();

	return 0;
}

Measured memory_bytes: 5156
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
#define endl "\n"

int main()
{
  i64 X;
  cin >> X;
  i64 now = 100;
  for (i64 i = 1;; i++)
  {
    now = now * 1.01;
    if (X <= now)
    {
      cout << i << endl;
      return 0;
    }
  }
  return 0;
}


Measured memory_bytes: 3640
#include "bits/stdc++.h"
#define hhh cerr<<"hhh"<<endl
#define see(x) cerr<<(#x)<<'='<<(x)<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int> pr;
inline int read() {int x=0,f=1;char c=getchar();while(c!='-'&&(c<'0'||c>'9'))c=getchar();if(c=='-')f=-1,c=getchar();while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();return f*x;}

const int maxn = 4e5+7;
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;



int main() {
    int n, k, s; cin>>n>>k>>s;
    for(int i=1; i<=k; ++i) printf("%d ", s);
    for(int i=k+1; i<=n; ++i) {
        if(s!=int(1e9)) printf("%d ", s+1);
        else printf("%d ", s-1);
    }
    puts("");
}

Measured memory_bytes: 1280
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int k = sc.nextInt();
		String s = sc.next();

		if(k < s.length()) {
			s = s.substring(0, k);
			System.out.println(s + "...");
		}else {
			System.out.println(s);
		}
	}

}

Measured memory_bytes: 38588
#include <bits/stdc++.h>
#include <vector>
#include <cmath>
#define REP(i, n) for (int i = 0; i < (int)(n); ++i)
#define REP2(i, m, n) for (int i = (m); i < (int)(n); ++i)
#define REPR(i, n) for (int i = (n)-1; i >= 0; --i)
#define REPR2(i, m, n) for (int i = (n)-1; i >= (m); --i)
#define REPx(x, a) for(auto x : a)
#define ALL(a) a.begin(), a.end()
#define SORT(a) sort(ALL(a))
#define SORTR(a) sort(ALL(a), greater<int>())
#define REVERSE(a) reverse(ALL(a))
#define bit_search(bit, n) REP(bit, 1<<(n))
#define bit_check(bit, i) (bit>>(i)) & 1
#define setpre(n) fixed << setprecision((n))
#define UNIQUE(a) do {SORT(a); (a).erase(unique(ALL(a)), (a).end());} while(0)
#define MAX(a) *max_element(ALL(a))
#define MIN(a) *min_element(ALL(a))
#define bisect_left(a, x) lower_bound(ALL(a), (x)) - a.begin()
#define bisect_right(a, x) upper_bound(ALL(a), (x)) - a.begin()
#define INPUT(a) REP(i, a.size()) cin >> a[i];
#define INPUTP(a) REP(i, a.size()) cin >> a[i].first >> a[i].second;
#define ENDL cout << endl;
using namespace std;
using ll = long long;
using ld = long double;
using PII = pair<int, int>;
using VPII = vector<PII>;
using VI = vector<int>;
using VVI = vector<VI>;
using Vll = vector<ll>;
using VVll = vector<Vll>;
using VC = vector<char>;
using VS = vector<string>;
using VB = vector<bool>;
const int INF = 1e9;
const ll MOD = 1e9 + 7;

struct ModCalc
{
  ll n;
  ll mod;
  int MAX;
  Vll fac;
  Vll invfac;

  ModCalc(auto _mod, auto _MAX)
  {
    mod = _mod; MAX = _MAX;
    Vll _fac(MAX);
    Vll _invfac(MAX);
    fac = _fac;
    invfac = _invfac;
    REP(i, MAX+1)
    {
      if (i == 0) fac[i] = 1;
      else fac[i] = i * fac[i-1] % mod;
    }
    invfac[MAX] = modpow(fac[MAX], mod-2, mod);
    REPR(i, MAX) invfac[i] = invfac[i+1] * (i+1) % mod;
  }

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

  ll modnCk(auto _n, auto _k)
  {
    ll res = fac[_n];
    res *= invfac[_k];
    res %= mod;
    res *= invfac[_n-_k];
    return res % mod;
  }

};

int main()
{
  cin.tie(0);
  ios::sync_with_stdio(false);
  ll H, W, A, B;
  cin >> H >> W >> A >> B;
  ll ans = 0;
  ModCalc m(MOD, 200005);
  ans += m.modnCk(B+H-A-1, B) * m.modnCk(A+W-B-1, A);
  ans %= MOD;
  if (B == W-1)
  {
    cout << ans << endl;
    return 0;
  }
  REP(i, H-A-1)
  {
    ans += m.modnCk(i+B, i) * m.modnCk(W-B-2+H-i-1, W-B-2);
    ans %= MOD;
  }
  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 6528
#include <stdio.h>

int main()
{
  int a,sum;
  scanf("%d",&a);
  if(a>=1 && a<=10)
  {
    sum = a+a*a+a*a*a;
   
   printf("%d\n",sum);
   }
  else 
  {
    printf("wrong input\n");
  }
  return 0;
}

Measured memory_bytes: 1732
class prime_factorize_by_osa_k():
    def __init__(self, max_val):
        '''
        割ることが出来る最小の値を格納したリストを返す
        :param max_val:
        :return:
        '''
        self.minFactor = [-1] * (max_val + 1)
        for i in range(2, max_val + 1):
            if self.minFactor[i] == -1:
                self.minFactor[i] = i
                # エラトステネスの篩と同様の処理を行う
                for j in range(i * i, max_val + 1, i):
                    if self.minFactor[j] == -1:
                        self.minFactor[j] = i

    def osa_k(self, n):
        '''
        preprocessをしたあと、O(logN)で素因数分解を行う。nの最大値をn_maxとする。
        :param n:
        :return:
        '''
        from collections import defaultdict
        d = defaultdict(int)
        now = n
        while now > 1:
            d[self.minFactor[now]] += 1
            now //= self.minFactor[now]
        return d
def gcd(a, b):
    while b: a, b = b, a % b
    return a

N = int(input())
A = list(map(int, input().split()))
# N = 10 ** 6
# A = [10 ** 6] * N
ob = prime_factorize_by_osa_k(10 ** 6)
pairwise = False
prime_key = set(ob.osa_k(A[-1]).keys())
break_flag = False
prime_flags = [False] * (10 ** 6 + 1)
for i in range(N):
    for key in ob.osa_k(A[i]).keys():
        if prime_flags[key]:
            break_flag = True
            break
        else:
            prime_flags[key] = True
    if break_flag:
        break
else:
    pairwise = True
if pairwise:
    print('pairwise coprime')
    exit()
work = gcd(A[0], A[1])
for i in range(2, N):
    work = gcd(work, A[i])
if work != 1:
    print('not coprime')
else:
    print('setwise coprime')

Measured memory_bytes: 126768
#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  int a, b, c;
  cin >> a >> b >> c;
  cout << (b - a == c - b ? "YES" : "NO") << '\n';
  return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <cmath>
#include <stdlib.h>


int main()
{
	int a, b;
	int realtest = 0;
	int minus = 300;
	int realminus;
	int first;
	int i;
	scanf("%d %d", &a, &b);
	first = b;
	for (i = 0; i < a; i++) {
		if (minus > abs(first + i)) {
			minus = abs(first + i);
			realminus = first + i;
		}
	}

	for (i = 0; i < a; i++) {
		realtest += (first + i);
	}

	realtest = realtest - realminus;
	printf("%d\n", realtest);
	return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <cmath>
#include <vector>
#include <string>
#include <map>
#include <algorithm>
#include <numeric>
#include <fstream>
#include <iomanip>

typedef long double ld;
typedef long long ll;
const ll INF = (ll)1e18 + 1;
const ll MOD = 1e9 + 7;

// Split
namespace util {

std::vector< std::string > split(std::string s, char delimiter)
{
  std::vector< std::string > vs;
  std::string sub;
  for (auto c : s) {
    if (c == delimiter) vs.push_back(sub), sub.clear();
    else sub += c;
  }
  vs.push_back(sub);
  return vs;
}

} // namespace util

// Minimum, Maximum
template<class T> T minimum(T head, T tail) { return std::min(head, tail); }
template<class H, class... T> H minimum(H head, T... tail) { return std::min(head, minimum(tail...)); }
template<class T> T maximum(T head, T tail) { return std::max(head, tail); }
template<class H, class... T> H maximum(H head, T... tail) { return std::max(head, maximum(tail...)); }

// Output
template<class T, class S> std::ostream& operator << (std::ostream& os, std::pair<T, S> p)
{
  return os << p.first << " " << p.second;
}

template<class T> std::ostream& operator << (std::ostream& os, std::vector< T > v)
{
  for (ll i = 0; i < (ll)v.size(); i++){ os << " [" << i << "]" << v[i]; if (i % 10 == 9) os << std::endl; }
  return os;
}

template<class T, class S> std::ostream& operator << (std::ostream& os, std::vector< std::pair<T, S> > vp)
{
  ll i = 0;
  for (auto p : vp){os << " [" << i++ << "]" << p.first << " " << p.second; if (i % 10 == 0) os << std::endl;}
  return os;
}

void print(){ std::cout << std::endl; }
template<typename H> void print(H head) { std::cout << head << std::endl; }
template<typename H, typename... T> void print(H head, T... tail){ std::cout << head << " ", print(tail...); }

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

//  ll MAX_N = 3;
//  for (ll N = 1; N < MAX_N; N++) {
//    print("=========");
//    print(N);
//    for (ll m = 1; m < N; m++) {
//      if (N / m == N % m) {
//	print(m, N / m, N % m);
//      }
//    }
//  }

  ll N;
  std::cin >> N;

  if (N == 1) {
    print(0);
    return 0;
  }

  ll ans = 0LL;
  for (ll i = 1; i * i <= N; i++) {
    if (N % i == 0) {
      ll m = (N / i) - 1;
      if (N / m == N % m) {
	ans += m;
	//print(m, N/m, N%m);
      }
    }
  }

  print(ans);
  return 0;
}


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


int main()
{
 

    long n;
    cin>>n;
    
    bool flag=false;
    for(long i=1;i<=9;i++){
        if(n%i==0&&n/i>=1&&n/i<=9){
          flag=true;
          break;
        }
    }

    if(flag)
      cout<<"Yes"<<endl;
    else
      cout<<"No"<<endl;
    
    return 0;
}

Measured memory_bytes: 256
#union-findの練習だと思ってやる。
n,m=map(int,input().split())
A=[list(map(int,input().split()))for i in range(m)]

#union_find
#find, sunite, same, sizeを実装する。
def find(x):
    #findはrootを返す
    if par[x]<0:
        return x
    else:
        par[x]=find(par[x])
        return par[x]
def unite(x,y):
    #xとyの属する集合を合体
    #まずは根をとってくる
    x=find(x)
    y=find(y)
    if x==y:
        return False
    else:
        if par[x]>par[y]:
            x,y=y,x
        par[x]+=par[y]
        par[y]=x
def same(x,y):
    #xとyが同じ集合かどうか判定
    return find(x)==find(y)
def size(x):
    return -par[x]
#初期化

c=0
for i in range(m):
    par=[-1]*n
    for j in range(m):
        if i==j:
            r,s=A[j]
            r-=1
            s-=1
        else:
            p,q=A[j]
            p-=1
            q-=1
            unite(p,q)
    if same(r,s)==False:
        c+=1
print(c)

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

int main() {
    int n, m; cin >> n >> m;
    int A[n][m] = {};
    int b[m][1] = {};
    
    for (int row = 0; row < n; ++row) {
        for (int col = 0; col < m; ++col) {
            cin >> A[row][col];
        }
    }
    
    for (int row = 0; row < m; ++row) {
        cin >> b[row][1];
    }
    
    for (int row = 0; row < n; ++row) {
        int result = 0;
        for (int col = 0; col < m; ++col) {
            result += A[row][col] * b[col][1];
        }
        cout << result << endl;
    }
    
    return 0;
}


Measured memory_bytes: 3140
#include <cmath>
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <iomanip>

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

using namespace std;

typedef pair<int, int> P;


signed main(){
        int n, m;
        cin >> n >> m;
        vector<P> c;
        rep(i, m){
                int a, b;
                cin >> a >> b;
                c.emplace_back(a, b);
        }
        sort(c.begin(), c.end());

        vector<P> ans;
        int cc = 0;
        rep(i, m){
                if(i == 0) {
                        ans.push_back(c[i]);
                        cc++;
                        continue;
                }

                if(ans[cc-1].second > c[i].first) {
                        ans[cc-1].first = max(ans[cc-1].first, c[i].first);
                        ans[cc-1].second = min(ans[cc-1].second, c[i].second);
                        continue;
                }
                ans.push_back(c[i]);
                cc++;
        }
        cout << cc << endl;

        return 0;
}


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

int main(){
  int i,j,cnt;
  int x;
  cin>>x;
  for(i=(int)sqrt(2*x)-1;;i++){
    if(0<=x-i*(i+1)/2 && x-i*(i+1)/2 < i+1){
      cnt=x-i*(i+1)/2;
      break;
    }
  }
  if(cnt==0)cout<<i;
  else cout<<i+1;
}

Measured memory_bytes: 256
#include<stdio.h>

int main()
{
  int arr[5];             //int w, h, x, y, r;
  for(int i =0; i<5; i++)
    {
      scanf("%d", &arr[i]);
    }
  if(arr[2]<0||arr[3]<0)
    {
      printf("No\n");
    }
  else if(arr[2]+arr[4]>arr[0])
    {
      printf("No\n");
    }
  else if(arr[3]+arr[4]>arr[1])
    {
      printf("No\n");
    }
    else
      {
	printf("Yes\n");
      }
    return 0;
}


Measured memory_bytes: 2140
#include<algorithm>
#include<iostream>
#include<functional>
#include<cmath>
#include<iomanip>
using namespace std;
int main(){
  long long int n,x,ans=0;
  cin>>n>>x;
  for(int i=0;i<n;i++){
    n*=2;
    ans+=1;
    if(n>x){
      cout<<ans<<endl;
      break;
    }
  }
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define MOD 1000000007
#define md 998244353
#define INF LLONG_MAX
#define F first
#define S second
#define sz(x) (long long)x.size()
#define vi vector<int>
#define vll vector<long long>
#define vpl vector<pair<long long,long long> >
#define vpi vector<pair<int,int> >
#define pb push_back
#define debug(x) cerr<<#x<<"= "<<x<<endl
#define all(v) v.begin(),v.end()
#define TT ll test;cin>>test; while(test--)
#define rep(i,a,n) for(ll i=a;i<(long long)n;++i)
#define repr(i,n,a) for(ll i=n;i>(long long)a;--i)
#define endl '\n'
#define MAXN 200005
typedef long long ll;
typedef long double ld;
using namespace std;
bitset<100005> bit;
int main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);

    ll n,k;
    cin >> n >> k;
    vll a(n);
    for (int i = 0; i < n; ++i)
    {
    	cin >> a[i];
    }
    for (int i = 1; i <= k; ++i)
    {
    	for (int j = 0; j < n; ++j)
    	{
    		if(i >= a[j] && (!bit[i - a[j]])){
    			bit[i] = 1;
    		}
    	}
    }
    cout << (bit[k]?"First":"Second");

    return 0;
}

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

typedef long long ll;

using namespace std;

int main() {
    ll n, p = 0, q = 0, r = 0, s = 0;
    cin >> n;
    vector<ll> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a.at(i);
        if ((r + a.at(i)) * (i % 2 * 2 - 1) < 1) {
            p += 1 - (r + a.at(i)) * (i % 2 * 2 - 1);
            r = i % 2 * 2 - 1;
        } else r += a.at(i);
        if ((s + a.at(i)) * (i % 2 * -2 + 1) < 1) {
            q += 1 - (s + a.at(i)) * (i % 2 * -2 + 1);
            s = i % 2 * -2 + 1;
        } else s += a.at(i);
    }
    cout << min(p, q) << endl;
    return 0;
}


Measured memory_bytes: 1024
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#define rep(i, n) for(int i=0; i<n; ++i)
using namespace std;
using ll = int64_t;
using vi = vector<int>;
using vvi = vector<vi>;


int main() {
    int n;
    cin >> n;
    vi A(n);
    rep(i, n-1) {
        int a;
        cin >> a;
        A[a-1]++;
    }
    rep(i, n) {
        cout << A[i] << '\n';
    }
}

Measured memory_bytes: 4056
#include<stdio.h>
const int maxn=1e5+7;
int pre[maxn];
bool you[maxn];
int Find(int x)
{
    if(pre[x] == x) return x;
    else return pre[x] = Find(pre[x]);
}
void join(int x,int y)
{
    int fx=Find(x);
    int fy=Find(y);
    if(fx!=fy)pre[fx]=fy;
}
int main()
{
    int n,m,sum=0,jian=0;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)pre[i]=i;
    for(int i=1;i<=m;i++)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        if(a==b&&you[a]==false)
		{
			jian++;
			you[a]=true;
		}
        join(a,b);
    }
    for(int i=1;i<=n;i++)if(pre[i]==i)sum++;
    printf("%d\n",sum-jian);
    printf("\n");
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
using ll = long long;
using namespace std;
int main() {
    string s;
    cin >> s;
    
    bool ok = true;
    if (s.size() % 2 == 1)
        ok = false;
    for (int i = 0; i < s.size() - 1; i+=2) {
        if (!(s[i] == 'h' && s[i+1] == 'i'))
            ok = false;            
    }

    if (ok)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
    
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#define rep(x, l, r) for(int x = l; x <= r; x++)
#define repd(x, r, l) for(int x = r; x >= l; x--)
#define clr(x, y) memset(x, y, sizeof(x))
#define all(x) x.begin(), x.end()
#define pb push_back
#define mp make_pair
#define MAXN
#define fi first
#define se second
#define SZ(x) ((int)x.size())
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
const int INF = 1 << 30;
const int p = 1000000007;
int lowbit(int x){ return x & (-x);}
int fast_power(int a, int b){ int x; for(x = 1; b; b >>= 1){ if(b & 1) x = 1ll * x * a % p; a = 1ll * a * a % p;} return x % p;}

int main(){
	int a, b, c;
	scanf("%d%d%d", &a, &b, &c);
	if(a > b) swap(a, b);
	int ans = 0;
	rep(i, 1, a){
		ans = i;
		if(i * b >= c) break;
	}
	printf("%d\n", ans);
    return 0;
}

Measured memory_bytes: 256
using System;
using System.Linq;
using System.Collections.Generic;
using static System.Console;
using System.Text;
using System.IO;
using static System.Math;
namespace AtCoder
{
    class Program
    {
        static public long[] Sarray() { return ReadLine().Split().Select(long.Parse).ToArray(); }
        static public List<long> Slist() { return ReadLine().Split().Select(long.Parse).ToList(); }

        static long Mod = (long)1e9 + 7;
        static long[] primes = new long[1001];
        static void Main(string[] args)
        {
            //SetOut(new StreamWriter(OpenStandardOutput()) { AutoFlush = false });
            var S = Sarray()[0];
            var ax = 0L;
            var ay = 0L;
            ay = (S + (long)1e9 - 1) / (long)1e9;
            ax = (long)1e9 * ay - S;

            WriteLine($"{0} {0} {(long)1e9} {1} {ax} {ay}");
            //Out.Flush();
        }
    }
}

Measured memory_bytes: 13396
#include<bits/stdc++.h>
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define srep(i,n,m) for(int i=n;i<m;i++)
#define elif else if
#define INF 1000000007
using namespace std;
int gcd(int a,int b){
    if(b==0) return a;
    return gcd(b,a%b);
}
int n,m,cnt=0,o,p,aa[220000],cntl=0,ab[220000];
pair<int,int> pp[220000];
string s,ss[220000];
char c,cc[220000];
queue<int> que;
signed main(){
    cin>>n;
    rep(i,n){
        rep(j,n){
            rep(k,n){
                cnt+=gcd(i+1,gcd(j+1,k+1));
            }
        }
    }
    cout<<cnt;
}

Measured memory_bytes: 10524
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
using namespace std;
using ll = long long ;
using P = pair<int,int> ;
using pll = pair<long long,long long>;
constexpr int INF = 1e9;
constexpr long long LINF = 1e17;
constexpr int MOD = 1000000007;
constexpr double PI = 3.14159265358979323846;


struct Unionfind{
    vector<int> parents;
    int n;
    Unionfind(int n):n(n),parents(n,-1){ }

    int find(int x){
        if(parents[x] < 0) return x;
        else return parents[x] = find(parents[x]);
    }

    void unite(int x,int y){
        x = find(x);
        y =  find(y);

        if(x==y) return;
        if(parents[x] > parents[y]) swap(x,y);
        parents[x] += parents[y];
        parents[y] = x;
    }  

   int size(int x){
       return -parents[find(x)];
   }

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

   vector<int> members(int x){
       int root = find(x);
       vector<int> member;
       for(int i=0;i<n;i++){
           if(find(i)==root ){
               member.push_back(i);
           }
       }
      return member;
  }

  int group_cnt(){
      int c = 0;
      rep(i,n){
          if(parents[i] < 0) ++c;
      }
      return c;
  }

  vector<vector<int>> group_by(){
      map<int,int> par_to_idx;
      vector<vector<int>> res;
      rep(i,n){
          int p = find(i);
          if(par_to_idx.count(p)>0){ res[par_to_idx[p]].push_back(i);}
          else{
              int k = (int)par_to_idx.size();
              par_to_idx[p] = k;
              res.push_back({});
              res[k].push_back(i);
          }
      }
      return res;
  }
};

vector<int> xx[100005];
vector<int> yy[100005];

int main(){
    int n;
    cin >> n;
    vector<int> x(n),y(n);
    rep(i,n){
        cin >> x[i] >> y[i];
        xx[x[i]].push_back(i);
        yy[y[i]].push_back(i);
    }
    Unionfind uf(n);

    rep(i,100005){
        rep(j,xx[i].size()-1){
            uf.unite(xx[i][j],xx[i][j+1]);
        }
        rep(j,yy[i].size()-1){
            uf.unite(yy[i][j],yy[i][j+1]);
        }
    }

    ll ans = 0;

    vector<vector<int>> res = uf.group_by();

    rep(i,res.size()){
        set<int> x_,y_;
        rep(j,res[i].size()){
            x_.insert(x[res[i][j]]);
            y_.insert(y[res[i][j]]);
        }
        ans += (ll)x_.size() * (ll)y_.size() - (ll)res[i].size();
    }

    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 17196
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
#define rep(i,N) for(ll (i)=0;(i)<(N);(i)++)
const int mod = 1000000007;

int main(){
    double l;cin>>l;
    double ll=l/3;
    cout<<setprecision(10)<<ll*ll*ll;
}

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

int main(){
  int N;
  cin >> N;
  vector<int> h(N+1);
  h[0]=0;
  for(int k=1; k<=N; k++) cin >> h[k];
  
  int ans=0;
  int dif=0;
  for(int k=1; k<=N; k++){
    dif=h[k]-h[k-1];
    if(dif>0){
      ans+=dif;
    }
  }
  cout << ans;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main
{
	public static void main(String[] args)
	{
		Scanner sc = new Scanner(System.in);
		for(;;)
		{
			int N = sc.nextInt(), M = sc.nextInt();
			if (N==0 && M==0) break;
			
			int[] c1 = new int[N], c2 = new int[M];
			int sum1 = 0, sum2 = 0;
			for (int i = 0; i < N; i++)
				sum1 += c1[i] = sc.nextInt();
			for (int i = 0; i < M; i++)
				sum2 += c2[i] = sc.nextInt();
			
			int min = Integer.MAX_VALUE, minA = -1, minB = -1;
			for (int i = 0; i < N; i++)
			{
				int a = c1[i];
				for (int j = 0; j < M; j++)
				{
					int b = c2[j];
					if (sum1 - a + b == sum2 - b + a && a + b < min)
					{
						min = a + b;
						minA = a;
						minB = b;
					}
				}
			}
			if (minA == -1)
				System.out.printf("-1\n");
			else
				System.out.printf("%d %d\n", minA, minB);
		}
	}
}

Measured memory_bytes: 12000
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<vector>
#include<map>
#include<queue>
#include<string>
#include<numeric>
#include<sstream>
#include<cmath>
using namespace std;
long long int mod = 1e9+7;

long long int func(int p, int q, int r) {

  func(p-1, q, r);
  func(p, q-1, r);
  func(p, q, r-1);
  return 0;
}

int main(){
  int x, y, z; cin >> x >> y >> z;
  int k; cin >> k;
  vector<long long int> a(x);
  vector<long long int> b(y);
  vector<long long int> c(z);
  for(int i=0; i<x; i++) cin >> a[i];
  for(int i=0; i<y; i++) cin >> b[i];
  for(int i=0; i<z; i++) cin >> c[i];
  sort(a.begin(), a.end());
  sort(b.begin(), b.end());
  sort(c.begin(), c.end());
  priority_queue< pair<long long int, vector<long long int>> > pq;
  x--; y--; z--;
  map<vector<long long int>, int> mp;
  pq.push({a[x] + b[y] + c[z], {x, y, z}});
  while(k--) {
    pair<long long int, vector<long long int>> p = pq.top();
    pq.pop();
    long long int tx = p.second[0];
    long long int ty = p.second[1];
    long long int tz = p.second[2];
    if(mp[{tx, ty, tz}] == 1){ k++; continue;}
    cout << p.first << endl;
    mp[{tx, ty, tz}] = 1;
    // cerr << tx << " " << ty << " " << tz << endl;
    if(tx >= 1) pq.push({a[tx-1] + b[ty] + c[tz], {tx-1, ty, tz}});
    if(ty >= 1) pq.push({a[tx] + b[ty-1] + c[tz], {tx, ty-1, tz}});
    if(tz >= 1) pq.push({a[tx] + b[ty] + c[tz-1], {tx, ty, tz-1}});
  }

  return 0;
}


// EOF


Measured memory_bytes: 896
#include<iostream>
#include<string>
#include<stdio.h>
#include<cctype>
#include<algorithm>
#include<climits>
#include<cmath>
#include<map>
#include<vector>
#define INF INT_MAX
using namespace std;

int N, M, K;
long long A[200010], B[200010];
int cnt;
int ans;

int main(){
	cin >> N >> M >> K;
	for (int i = 1; i <= N; i++){
		cin >> A[i];
		A[i] += A[i - 1];
	}
	for (int i = 1; i <= M; i++){
		cin >> B[i];
		B[i] += B[i - 1];
	}
	int j = M;
	for (int i = 0; i <= N; i++){
		if (A[i] > K)break;
		while (B[j] > K - A[i])j--;
		ans = max(ans, i + j);
	}
	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 6728
A, B, C = map(int, input().split())

import numpy as np
ABC = np.array([A, B, C])
#min_ = min(ABC)
cnt = 0

while True:
    #min_ = min(ABC)
    if np.sum(ABC == np.min(ABC)) == 3:#ABC.count(min_) == 3:
        print(cnt)
        break
    elif np.sum(ABC == np.min(ABC)) == 2:
        index = np.where(ABC == min(ABC))
        ABC[index] += 1
        cnt += 1
    else: #ABC.count(min_) == 1:
        ABC[np.argmin(ABC)] += 2
        cnt += 1



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

using namespace std;

#define REPI(x) for(int i=0;i<x;i++)

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

  cin >> a >> b >> c >> d;
  
  if (abs(c-a) <= d || (abs(b-a) <= d && abs(b-c) <= d))
    {
      cout << "Yes" << endl;
      return 0;
    }

  cout << "No" << endl;
  return 0;
  
}


Measured memory_bytes: 256
#include <algorithm>
#include <cmath>
#include <iostream>
#include <iomanip>
#include <map>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <list>
#include <cstdio>
#define INF 1LL<<60
#define MOD 1000000007ll
#define EPS 1e-10
#define REP(i,m) for(long long i=0; i<m; i++)
#define FOR(i,n,m) for(long long i=n; i<m; i++)
#define pb push_back
using namespace std;
typedef long long int ll;
typedef pair<ll, ll> P;
typedef long double ld;

int main(){
  int n;
  cin >> n;
  int a[n];
  REP(i, n) cin >> a[i];
  ll ans = 0;
  REP(i, n-1){
    if(a[i]%2 == 1 && a[i+1] > 0){
      ans++;
      a[i]--;
      a[i+1]--;
    }
  }
  REP(i, n){
    ans += a[i]/2;
    a[i] %= 2;
  }
  cout << ans << endl;
	return 0;
}


Measured memory_bytes: 640
#pragma comment(linker, "/STACK:10240000")
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 100010;

map <pair <int, int>, bool> p;

int xx[9][9] = {{0, 0, 0, 1, 1, 1, 2, 2, 2},
                {0, 0, 0, 1, 1, 1, 2, 2, 2},
                {0, 0, 0, 1, 1, 1, 2, 2, 2},
                {-1, -1, -1, 0, 0, 0, 1, 1, 1},
                {-1, -1, -1, 0, 0, 0, 1, 1, 1},
                {-1, -1, -1, 0, 0, 0, 1, 1, 1},
                {-2, -2, -2, -1, -1, -1, 0, 0, 0},
                {-2, -2, -2, -1, -1, -1, 0, 0, 0},
                {-2, -2, -2, -1, -1, -1, 0, 0, 0}};
int yy[9][9] = {{0, 1, 2, 0, 1, 2, 0, 1, 2},
                {-1, 0, 1, -1, 0, 1, -1, 0, 1},
                {-2, -1, 0, -2, -1, 0, -2, -1, 0},
                {0, 1, 2, 0, 1, 2, 0, 1, 2},
                {-1, 0, 1, -1, 0, 1, -1, 0, 1},
                {-2, -1, 0, -2, -1, 0, -2, -1, 0},
                {0, 1, 2, 0, 1, 2, 0, 1, 2},
                {-1, 0, 1, -1, 0, 1, -1, 0, 1},
                {-2, -1, 0, -2, -1, 0, -2, -1, 0}};

int x[MAXN], y[MAXN];
long long ans[10];

int main()
{
    int n, m, k;
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 1; i <= k; i ++)
    {
        scanf("%d%d", &x[i], &y[i]);
        p[make_pair(x[i], y[i])] = true;
    }
    memset (ans, 0, sizeof (ans));
    for (int i = 1; i <= k; i ++)
    {
        for (int s = 0; s < 9; s ++)
        {
            int count = 0;
            bool flag = true;
            for (int t = 0; t < 9; t ++)
            {
                int xm = x[i] + xx[s][t], ym = y[i] + yy[s][t];
                if ((xm < 1) || (xm > n) || (ym < 1) || (ym > m))
                {
                    flag = false;
                    break;
                }
                if (p[make_pair(xm, ym)] == true)
                {
                    count ++;
                }
            }
            if (flag)
            {
                ans[count] ++;
            }
        }
    }
    long long all = (long long)(n - 2) * (long long)(m - 2);
    long long total = 0;
    for (int i = 1; i <= 9; i ++)
    {
        ans[i] /= i;
        total += ans[i];
    }
    ans[0] = all - total;
    for (int i = 0; i <= 9; i ++)
    {
        printf("%lld\n", ans[i]);
    }
    return 0;
}


Measured memory_bytes: 157312
use std::str::FromStr;

fn get_one<T : FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    return s.trim().parse().ok().unwrap();
}

fn get_vec<T : FromStr>() -> Vec<T> {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    return s.trim().split_whitespace().map(|e| e.parse().ok().unwrap()).collect();
}

fn main() {
    let s : String = get_one();
    println!("{}", s.replace(","," "));
}


Measured memory_bytes: 4352
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
//#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a = b; return 1; } return 0; }
//------------------------------------------------------------------------------
//------------------------------------------------------------------------------
void _main()
{
    int X, Y;
    cin >> X >> Y;
    cout << X + Y / 2 << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <stdio.h>
#include <cmath>
using namespace std;

typedef long long LL;

const LL mod = 1e9 +7;

int main () {
	int a,b;
	cin >>a >> b;
	if (abs(a-b)>=2) puts("0");
	else {
		LL ans=1;
		for (int i=1;a>=i;i++) {
			ans *= i;
			ans%=mod;
		}
		for (int i=1;b>=i;i++) {
			ans *=i;
			ans%=mod;
		}
		if (a==b) ans*=2;
		cout<<ans%mod<<endl;
	}
}


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

#define REP(i, m, n) for (int i = (m); i < (int)(n); i++)
#define REPS(i, m, n) for (int i = (m); i <= (int)(n); i++)
#define rep(i, n) REP(i, 0, n)
#define reps(i, n) for (int i = 0; i <= (int)(n); i++)
#define rrep(i, x) for (int i = ((int)(x)-1); i >= 0; i--)
#define rreps(i, x) for (int i = (int)(x); i >= 0; i--)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pb push_back
#define fi first
#define se second
typedef long long ll;
typedef pair<int, int> P;
const int inf = INT_MAX;
const ll INF = 1LL << 60;
const ll mod = 1e9 + 7;
const double EPS = 1e-10;
const double PI = acos(-1.0);
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; }
template<typename A, size_t N, typename T> void Fill(A (&array)[N], const T &val) { fill( (T*)array, (T*)(array+N), val ); }
template <class T1, class T2, class Pred = std::less<T2> >
struct sort_pair_second {
    bool operator()(const std::pair<T1,T2>&left, const std::pair<T1,T2>&right) {
        Pred p;
        return p(left.second, right.second);
    }
};

ll modpow(ll a, ll p)
{
  if (p == 0)
    return 1;
  if (!(p % 2))
  {
    ll halfP = p / 2;
    ll half = modpow(a, halfP);
    return half * half % mod;
  }
  else
  {
    return a * modpow(a, p - 1) % mod;
  }
}

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

    ll X, Y;
    cin >> X >> Y;

    int num = 2000100;
    vector<ll> fact(num), ifact(num);
    fact[0] = 1;
    fact[1] = 1;
    for (int i = 2; i < num; i++)
    {
      fact[i] = fact[i - 1] * i;
      fact[i] %= mod;
    }
    for (int i = 0; i < num; i++)
    {
      ifact[i] = modpow(fact[i], mod - 2);
      ifact[i] %= mod;
    }

    auto comb = [&] (ll a, ll b) {
      return fact[a] * ifact[a-b] % mod * ifact[b] % mod;
    };

    ll m = (2 * X - Y) / 3;
    ll n = (2 * Y - X) / 3;
    if (m < 0 || n < 0 || (X + Y) % 3) {
      cout << 0 << endl;
      return 0;
    }
    cout << comb(m+n, n) << endl;
    return 0;
}

Measured memory_bytes: 31488
#include <bits/stdc++.h> 
using namespace std;
#define rep(i, N) for(int i=0; i<N; i++)
typedef long long ll;
#define dump(x) cerr<<#x<<"="<<x<<endl
using P = pair<int, int>;

int main() {
    vector<int> a(3);
    rep(i, 3) cin >> a.at(i);
    
    sort(a.begin(), a.end());
    cout << 10*a.at(2) + a.at(1) + a.at(0) << endl;

    return 0;
}


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

// 0-indexed
template <class T>
struct SegmentTree {
  // a,b,c: T, e:T(unit)
  // abc = (ab)c = a(bc)
  // ae = ea = a
  typedef function<T(T, T)> F;
  int n;
  F f;
  T unit;
  vector<T> dat;
  SegmentTree(){};
  SegmentTree(int newn, F f, T t) : f(f), unit(t) {
    init(newn);
  }
  SegmentTree(vector<T> v, F f, T t) : f(f), unit(t) {
    int _n = v.size();
    init(v.size());
    for(int i = 0; i < _n; ++i) dat[n + i] = v[i];
    for(int i = n - 1; i; --i)
      dat[i] = f(dat[i << 1], dat[(i << 1) | 1]);
  }
  void init(int newn) {
    n = 1;
    while(n < newn) n <<= 1;
    dat.assign(n << 1, unit);
  }

  // "go up" process
  void update(int k, T newdata) {
    dat[k += n] = newdata;
    while(k >>= 1) {
      dat[k] = f(dat[k << 1], dat[(k << 1) | 1]);
    }
  }
  // [a,b)
  T query(int a, int b) {
    T vl = unit, vr = unit;
    for(int l = a + n, r = b + n; l < r; l >>= 1, r >>= 1) {
      if(l & 1) vl = f(vl, dat[l++]);
      if(r & 1) vr = f(dat[--r], vr);
    }
    return f(vl, vr);
  }
};

unsigned long long popcount(unsigned long long x) {
  x = ((x & 0xaaaaaaaaaaaaaaaaUL) >> 1) +
      (x & 0x5555555555555555UL);
  x = ((x & 0xccccccccccccccccUL) >> 2) +
      (x & 0x3333333333333333UL);
  x = ((x & 0xf0f0f0f0f0f0f0f0UL) >> 4) +
      (x & 0x0f0f0f0f0f0f0f0fUL);
  x = ((x & 0xff00ff00ff00ff00UL) >> 8) +
      (x & 0x00ff00ff00ff00ffUL);
  x = ((x & 0xffff0000ffff0000UL) >> 16) +
      (x & 0x0000ffff0000ffffUL);
  x = ((x & 0xffffffff00000000UL) >> 32) +
      (x & 0x00000000ffffffffUL);
  return x;
}

long long n, q;
string s;
SegmentTree<long long> seg[26];

int main() {
  cin >> n >> s >> q;
  // prepair
  auto f = [](long long l, long long r) { return l + r; };
  for(int i = 0; i < 26; ++i) {
    seg[i] = SegmentTree<long long>(n, f, 0);
  }
  for(int i = 0; i < n; ++i) seg[s[i] - 'a'].update(i, 1);
  // query
  for(int i = 0; i < q; ++i) {
    int p;
    cin >> p;
    if(p == 1) {
      int k;
      char c;
      cin >> k >> c;
      seg[s[k - 1] - 'a'].update(k - 1, 0);
      seg[c - 'a'].update(k - 1, 1);
      s[k - 1] = c;
    }
    else {
      int l, r, cnt = 0;
      cin >> l >> r;
      for(int j = 0; j < 26; ++j)
        if(seg[j].query(l - 1, r) > 0) ++cnt;
      cout << cnt << endl;
    }
  }
  return 0;
}

Measured memory_bytes: 214020
#pragma GCC optimize ("Ofast")
#include<bits/stdc++.h>
using namespace std;
inline int my_getchar_unlocked(){
  static char buf[1048576];
  static int s = 1048576;
  static int e = 1048576;
  if(s == e && e == 1048576){
    e = fread_unlocked(buf, 1, 1048576, stdin);
    s = 0;
  }
  if(s == e){
    return EOF;
  }
  return buf[s++];
}
inline void rd(long long &x){
  int k;
  int m=0;
  x=0;
  for(;;){
    k = my_getchar_unlocked();
    if(k=='-'){
      m=1;
      break;
    }
    if('0'<=k&&k<='9'){
      x=k-'0';
      break;
    }
  }
  for(;;){
    k = my_getchar_unlocked();
    if(k<'0'||k>'9'){
      break;
    }
    x=x*10+k-'0';
  }
  if(m){
    x=-x;
  }
}
inline void rd(double &x){
  int k;
  int m=0;
  int p=0;
  double r = 1;
  x = 0;
  for(;;){
    k = my_getchar_unlocked();
    if(k=='-'){
      m = 1;
      break;
    }
    if(k=='.'){
      p = 1;
      break;
    }
    if('0'<=k&&k<='9'){
      x = k - '0';
      break;
    }
  }
  for(;;){
    k = my_getchar_unlocked();
    if(k=='.'){
      p = 1;
      continue;
    }
    if(k<'0'||k>'9'){
      break;
    }
    if(p){
      r *= 0.1;
      x += r * (k - '0');
    }
    else{
      x = x * 10 + k - '0';
    }
  }
  if(m){
    x = -x;
  }
}
struct MY_WRITER{
  char buf[1048576];
  int s;
  int e;
  MY_WRITER(){
    s = 0;
    e = 1048576;
  }
  ~MY_WRITER(){
    if(s){
      fwrite_unlocked(buf, 1, s, stdout);
    }
  }
}
;
MY_WRITER MY_WRITER_VAR;
void my_putchar_unlocked(int a){
  if(MY_WRITER_VAR.s == MY_WRITER_VAR.e){
    fwrite_unlocked(MY_WRITER_VAR.buf, 1, MY_WRITER_VAR.s, stdout);
    MY_WRITER_VAR.s = 0;
  }
  MY_WRITER_VAR.buf[MY_WRITER_VAR.s++] = a;
}
inline void wt_L(char a){
  my_putchar_unlocked(a);
}
inline void wt_L(long long x){
  int s=0;
  int m=0;
  char f[20];
  if(x<0){
    m=1;
    x=-x;
  }
  while(x){
    f[s++]=x%10;
    x/=10;
  }
  if(!s){
    f[s++]=0;
  }
  if(m){
    my_putchar_unlocked('-');
  }
  while(s--){
    my_putchar_unlocked(f[s]+'0');
  }
}
long long A;
long long B;
double tmp;
int main(){
  rd(A);
  rd(tmp);
  B = (long long)(tmp * 100 + 0.5);
  wt_L(A*B/100);
  wt_L('\n');
  return 0;
}
// cLay varsion 20200509-1

// --- original code ---
// ll A, B;
// double tmp;
// {
//   rd(A,tmp);
//   B = (ll)(tmp * 100 + 0.5);
//   wt(A*B/100);
// }


Measured memory_bytes: 3640
/*

10種の山の高さが与えられる。高い順に3つ出力せよ。
山の高さは10000以下とする。

やり方：
	・データを配列に入力する。
		・高さが10000を超えていた場合はやり直す。
	・降順に並べ替える。
	・0番目〜2番目までの3つを出力する。
	
結果：正解。

*/
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <ctype.h>

int sort00(int data[],int n);
int maxindex00(int data[], int from, int to);

int main()
{
	int i;
	int data[1000];
	for(i=0; i<10; i++){
		scanf("%d",&data[i]);
		if(data[i]>10000){
			i--;
		}
	}
	sort00(data,10);
	for(i=0;i<3;i++){
		printf("%d\n",data[i]);
	}
	return 0;
}

int sort00(int data[],int n)
{
	int i,work,maxindex;
	for(i=0;i<n;i++){
		maxindex=maxindex00(data,i,n);
		work=data[i];
		data[i]=data[maxindex];
		data[maxindex]=work;
	}
	return;
}

int maxindex00(int data[], int from, int to)
{
	int i;
	int result=from;
	for(i=from;i<to;i++){
		if(data[result]<data[i]){
			result=i;
		}
	}
	return result;
}

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

int main()
{
ll n ;
cin >> n ;
cout << '?' ;
rep(i,n)cout << ' ' << i+1 ;
cout << endl;

auto input = []() { string st;cin >> st; if(st=="-1")assert(0); return st=="Blue"; };
bool f=input();


auto judge = [&](ll val) { 
  cout << '?' ;
  rep(i,n)cout << ' ' << i+val ;
  cout << endl;
  return f==input();
};
auto binarysearch = [&](ll lowerbound, ll upperbound) {
  ll lower = lowerbound, upper = upperbound;
  while (1){
    if (judge((lower + upper) / 2)) lower = (lower + upper) / 2;
    else upper = (lower + upper) / 2;
    if (abs(upper - lower) <= 1){
      if (judge(upper)) return upper;
      else return lower;
    }
  }
};
auto k=binarysearch(1,n+1);
vector<char> v(2*n+1,'a');
v[k]=(f ? 'B' : 'R');
v[k+n]=(!f ? 'B' : 'R');
for(ll i=1;i<k;i++){
  cout << '?' ;
  rep(j,n-1)cout << ' ' << j+k+1 ;
  cout << ' ' << i;
  cout << endl;
  v[i]=(input() ? 'B' : 'R');
}
for(ll i=k+n+1;i<=2*n;i++){
  cout << '?' ;
  rep(j,n-1)cout << ' ' << j+k+1 ;
  cout << ' ' << i;
  cout << endl;
  v[i]=(input() ? 'B' : 'R');
}
for(ll i=k+1;i<k+n;i++){
  cout << '?' ;
  rep(j,n-1)if(j+k+1!=i)cout << ' ' << j+k+1 ;
  cout << ' ' << k;
  cout << ' ' << k+n;
  cout << endl;
  v[i]=(!input() ? 'B' : 'R');
}
cout << "! " ;
rep(i,2*n)cout << v[i+1];
cout << endl;

return 0;
}

Measured memory_bytes: 724
import copy


def bubbleSort(a, n):
    for i in range(0, n):
        for j in range(n - 1, i, -1):
            if a[j][1] < a[j - 1][1]:
                a[j], a[j - 1] = a[j - 1], a[j]


def selectionSort(a, n):
    for i in range(n):
        minj = i
        for j in range(i, n):
            if a[j][1] < a[minj][1]:
                minj = j
        a[i], a[minj] = a[minj], a[i]


n = int(input())
a = list(input().split())
b = copy.deepcopy(a)

bubbleSort(a, n)
print(*a)
print('Stable')

selectionSort(b, n)
print(*b)
print('Stable') if a == b else print('Not stable')



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

using namespace std;

int main(){
    int N, M; cin >> N >> M;
    vector<vector<long long>> dp(3*N+1, vector<long long>(N+1, 0));
    dp[3*N][0] = 1;
    for(int i=3*N;i>0;i--){
        for(int j=0;j<=N;j++){
            long long m = 1;
            for(int k=1;k<=3;k++){
                if(i-k < 0) break;
                if(j+k/2 > N) break;
                dp[i-k][j+k/2] += dp[i][j] * m;
                dp[i-k][j+k/2] %= M;
                m = m * (i-k) % M;
            }
        }
    }
    long long res = 0;
    for(int i=0;i<=N;i++) res = (res + dp[0][i]) % M;
    cout << res << endl;
}

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

#define dlog(str) cout << "====" << str << endl;
#define INF 999999999
#define MOD 1000000007
#define REP(i, n) for(int i = 0, i##_l = (n); i < i##_l; i++)
#define FOR(i, s, e) for(int i = s; i <= e; i++)
#define LLI long long int
#define _min(a, b) ((a < b) ? a : b)
#define _max(a, b) ((a < b) ? b : a)
#define chmax(a, b) a = _max(a, b)
#define chmin(a, b) a = _min(a, b)
#define bit(a, shift) ((a>>shift)&1))
#define ALL(v) (v).begin(), (v).end()
#define SORT(v) sort(ALL(v))
#define RSORT(v) sort((v).rbegin(), (v).rend())
// int 2.14E±9    lli 9.2E±18    double 1.7E±380
const int MA = 100000;
LLI dp[101][MA];

int main() {
    LLI N, K;
    cin >> N >> K;

    set<LLI> s;
    s.insert(N + 1);
    FOR(i, 1, sqrt(N)) {
        s.insert(i);
        s.insert(N / i);
    }
    vector<LLI> v(s.rbegin(), s.rend());
    LLI size = v.size() - 1;
    REP(i, size) { dp[0][i] = v[i + 1] * (N / v[i + 1] - N / v[i]) % MOD; }
    dp[0][0] = v[1];

    REP(j, size) { (dp[0][j + 1] += dp[0][j]) %= MOD; }
    FOR(i, 1, K) {
        FOR(j, 1, size) {
            dp[i][j - 1] =
                (dp[i - 1][size - j] * (N / v[j] - N / v[j - 1])) % MOD;
        }
        REP(j, MA - 1) { (dp[i][j + 1] += dp[i][j] % MOD) %= MOD; }
    }

    cout << dp[K - 1][0];
    return 0;
}


Measured memory_bytes: 82304