akhauriyash/Code-Regression huggingface dataset:
def examA():
    L, R, D = LI()
    ans = R//D - (L-1)//D
    print(ans)
    return

def examB():
    N = I()
    A = LI()
    ans = 0
    for i,a in enumerate(A):
        if i%2==0:
            if a%2==1:
                ans += 1
    print(ans)
    return

def examC():
    ans = 0
    print(ans)
    return

def examD():
    ans = 0
    print(ans)
    return

def examE():
    ans = 0
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

from decimal import getcontext,Decimal as dec
import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def DI(): return dec(input())
def LDI(): return list(map(dec,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = dec("0.000000000001")
alphabet = [chr(ord('a') + i) for i in range(26)]
alphabet_convert = {chr(ord('a') + i): i for i in range(26)}

getcontext().prec = 28

sys.setrecursionlimit(2*10**6)

if __name__ == '__main__':
    examB()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
"""

Measured memory_bytes: 76884
import java.util.*;
 
public class Main {
	
    public static void main(String[] args) {
    	Scanner sc = new Scanner(System.in);
    	String S = sc.next();
    	List<Character> zero = new ArrayList<>();
    	List<Character> one = new ArrayList<>();
    	for (char c : S.toCharArray()) {
    		if (c == '0') {
    			zero.add(c);
    		} else {
    			one.add(c);
    		}
    	}
    	System.out.println(2*Math.min(zero.size(), one.size()));
    }
}

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

int main()
{
    int a, b, c, d, e;
    cin >> a >> b >> c >> d >> e;
    int N = 5;

    //注文してから届くまでの時間
    vector<int> Time = {a, b, c, d, e};
    //注文してから次に注文出来るまでの時間
    vector<int> nextTime(N);
    for (int i = 0; i < N; i++)
    {
        if (Time[i] % 10 == 0)
            nextTime[i] = Time[i];
        else
            nextTime[i] = Time[i] - Time[i] % 10 + 10;

        //nextTime[i] = (Time[i] + 9) / 10 * 10;
    }

    int BestTime = 999999999; //大きい値を適当に入れる
    //最後に注文するものを全通り計算
    for (int i = 0; i < N; i++)
    {
        int SumTime = 0;
        for (int j = 0; j < N; j++)
        {
            if (i == j)
            {
                //最後の処理
                SumTime += Time[j];
            }
            else
            {
                //最後以外の処理
                SumTime += nextTime[j];
            }
        }
        BestTime = min(BestTime, SumTime);
        //if (BestTime > SumTime) BestTime = SumTime;
    }

    cout << BestTime << endl;
}

Measured memory_bytes: 256
#include <stdio.h>

int main(){
	
	int test,i,j,k,l,m,width[305],height[305],space;

	i=0;
	do {
		scanf ("%d %d", &height[i], &width[i]);
		i++;
	} while (height[i-1] != 0 && width[i-1] != 0);
	
	for (j=0;j<i-1;j++){
		
			for (l=0;l<width[j];l++){
				printf ("#");
			}
			printf ("\n");
			for (k=0;k<height[j]-2;k++){
				printf ("#");
				for (m=0;m<width[j]-2;m++){
					printf (".");
				}
				printf ("#");
				printf ("\n");
			}
			for (l=0;l<width[j];l++){
				printf ("#");
			}	
			printf ("\n\n");	
	}

return 0;
}


Measured memory_bytes: 2000
#include <iostream>
#include <cmath>
#include <string>
#include <vector>

using namespace std;

int main() {
    int n;
    cin >> n;
    vector <int> p(n, 0);
    for(int i = 0;i < n; i++)
    {
        cin >> p[i];
    }

    int count = 0;
    for(int i = 1; i < n - 1; i++)
    {
        if(p[i - 1] < p[i] && p[i] < p[i + 1]) count++;
        if(p[i + 1] < p[i] && p[i] < p[i - 1]) count++;
    }

    cout << count << endl;
    return 0;
}



Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <numeric>

#define FOR(i, f, n) for(int (i) = (f); (i) < (n); (i)++)
#define RFOR(i, f, n) for(int (i) = (f); (i) >= (n); (i)--)
#define REP(i, n) for(int (i) = 0; (i) < (n); (i)++)
#define RREP(i, n) for(int (i) = (n); (i) >= 0; (i)--)
#define rep(i, n) for(int (i) = 0; (i) < (n); (i)++)
#define rrep(i, n) for(int (i) = (n); (i) >= 0; (i)++)
#define p(...) printf(__VA_ARGS__); cout << endl;
#define in(...) __VA_ARGS__; input__(__VA_ARGS__);
#define list_input(x, n) x[(n)]; for(int (i) = 0; (i) < (n); (i)++) cin >> x[i];
#define lambda(a, b, c) [](const a, const b){ return c ;}
#define key(t, x, compare) [](const t& a, const t& b){ return a x compare b x ;}

using namespace std;

using pii = pair<int, int>;

template <class... T>
void input__(T &...a) {
  for(auto v: {&a...}) {
    cin >> *v;
  }
}

template <class... T>
void out(T ...a) {
  for(auto v: {a...}) {
    cout << v << " ";
  }
  cout << endl;
}

int main(){
  int in(a, b, c, d);
  int ab = a + b, cd = c + d;
  out(ab > cd ? "Left" : (ab < cd ? "Right" : "Balanced"));
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define pi 3.141592653589793238
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define MOD 1000000007


void solve()
{
	ll n;
	cin>>n;
	vector<ll> a(n);
	for(ll i=0;i<n;i++)
	    cin>>a[i];
	ll cnt[64],ans=0,p=1;

    for(ll i=0;i<64;i++)
        cnt[i]=0;
    for(ll i=0;i<n;i++)
    {
        ll c=0;
        while(a[i]>0)
        {
            cnt[c]+=a[i]%2;
            a[i]/=2;
            c++;
        }
    }
  
    for(ll i=0;i<64;i++)
    {
        p=pow(2,i);
        p%=MOD;
        ans+=((((n-cnt[i])*cnt[i])%MOD)*p%MOD);
        ans%=MOD;
  }
  cout<<ans;
    return;
}

int main()
{
        fast;
        ll q;
        q=1;
        // cin>>q;
        while(q--)
        	solve();
        
        return 0;
}


Measured memory_bytes: 5488
#include <cstdio>

int main() {
  int A, B, C, X;
  scanf("%d %d %d %d", &A, &B, &C, &X);

  int res = 0;
  for (int i = 0; i <= A; ++i)
    for (int j = 0; j <= B; ++j)
      for (int k = 0; k <= C; ++k)
        if (500*i + 100*j + 50*k == X)
          ++res;

  printf("%d\n", res);
}

Measured memory_bytes: 256
#include <stdio.h>
#include <iostream>
#include <vector>
#include <string>
#include <cstdio>
#include <limits>
using namespace std;

static const int MAX = 200000;
int main(){
    int n;
    cin >> n;
    int r[MAX];
    for(int i=0;i<n;i++) cin >> r[i];
    
    int min_sofar = r[0];
    int max_diff = -2000000000;
    for (int i=1;i<n;i++){
        max_diff = max(max_diff, r[i] - min_sofar);
        min_sofar = min(min_sofar, r[i]);
    }
    cout << max_diff << endl;
}


Measured memory_bytes: 3872
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <functional>
#include <queue>
#include <stack>
#include <bitset>
#include <set>
#include <chrono>
#include <string>
#include <assert.h>

using namespace std;

#define endl '\n'

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

    int n;
    cin >> n;

    if (n == 3)
    {
        cout << 2 << " " << 3 << " " << 25 << endl;
        return 0;
    }

    cout << 2 << " " << 3 << " " << 4 << " " << 9 << " ";

    n -= 4;

    int x = 8;

    while (n >= 2)
    {
        if (x + 2 > 30000)
            break;
        cout << x << " " << x + 2 << " ";
        x += 6;
        n -= 2;
    }

    x = 15;

    while (n >= 2)
    {
        if (x + 6 > 30000)
            break;
        cout << x << " " << x + 6 << " ";
        x += 12;
        n -= 2;
    }

    x = 6;

    while (n)
    {
        cout << x << " ";
        x += 6;
        n--;
    }

    cout << endl;

    return 0;
}

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

#define FOR(x,to) for(int x=0;x<(to);x++)
#define F0R(x,in,to) for(int x=(in);x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))

typedef long long ll;
using namespace std;
ll MOD = 998244353;

typedef pair<int,int> ii;
typedef struct {int a,b,c;}iii;
typedef vector<int> vi;

void mosA(vector<ll> a){
	for(int i=0; i<a.size(); i++) printf("%lld ",a[i]);
	printf("\n");
}
void mosP(vector<ii> a){
	for(int i=0; i<a.size(); i++) printf("%d %d\n",a[i].first,a[i].second);
	printf("\n");
}

ll min_especial(ll a, ll b){
  if(a!=-1 && b!=-1) return min(a,b);
  else return max(a,b);
}
/*
bool ord(ii a, ii b){
	if(a.first == b.first){
		return a.second < b.second;
	}
	return a.first < b.first;
}*/

bool ord(ll a, ll b){
	return a>b;
}

ll ans = 0;
int a,n,w,t,k,m,z,q,l,r,x,b,y;
int A[200005];
char S[200005];



struct UnionFind {
  vector<int> parent; // parent[root] is the negative of the size.
  UnionFind(int n) : parent(n, -1) { };
  bool join(int u, int v) { 
    u = root(u); v = root(v);
    if (u == v) return false;
    if (parent[u] > parent[v]) swap(u, v);
    parent[u] += parent[v]; parent[v] = u;
    return true;
  }
  bool sameSet(int u, int v) { return root(u) == root(v); }
  int root(int u) { return parent[u] < 0 ? u : parent[u] = root(parent[u]); }
  int size(int u) { return -parent[root(u)]; }
};



int main(){
	scanf("%d%d",&n,&m);
	int cant = 0;
	struct UnionFind U(100005);
	FOR(i,m){
		scanf("%d%d%d",&x,&y,&z);
		U.join(x,y);
	}

	F0R(i,1,n+1) {
		int p = U.root(i);
		if(!A[p]){
			cant++;
			A[p] = 1;
		}
	}

	printf("%d\n",cant);
}




// REVISATE ESTO:
// - memset(A,-1,SIZEOF()*n)
// - (x-y+MOD)%MOD
// - int o ll?

Measured memory_bytes: 1024
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(){
  int N, C;
  cin >> N >> C;
  vector< vector< pair<int,int> > > V(C);
  int s, t, c;
  for(int i = 0; i < N; ++i){
    cin >> s >> t >> c;
    --c;
    V[c].emplace_back(s-1,t);
  }
  vector< pair<int,int> > T;
  for(int i = 0; i < C; ++i){
    sort(V[i].begin(),V[i].end());
    if(!V[i].empty()) T.push_back(V[i][0]);
    for(int j = 1; j < V[i].size(); ++j){
      if(T.back().second > V[i][j].first) T.back().second = V[i][j].second;
      else T.push_back(V[i][j]);
    }
  }
  int imos[100001] = {};
  for(int i = 0; i < T.size(); ++i){
    ++imos[T[i].first];
    --imos[T[i].second];
  }
  int ans = 0, k = 0;
  for(int i = 0; i < 100001; ++i){
    k += imos[i];
    ans = max(ans,k);
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 2676
n = int(input())
#n,k = map(int,input().split())
#a = list(map(int,input().split()))
#mod = pow(10,9) + 7

ac=wa=tle=re=0

for i in range(n):
    a = input()
    if(a=='AC'):
        ac +=1
    elif(a=='WA'):
        wa += 1
    elif(a=='TLE'):
        tle +=1
    elif(a=='RE'):
        re+=1
print("AC x",ac)
print("WA x",wa)
print("TLE x",tle)
print("RE x",re)



Measured memory_bytes: 9192
#include<cstdio>
#include<algorithm>
#include<functional>
#include<cstring>
#include<iostream>
using namespace std;
int main(void)
{
	long long int N,T,Q,house[100001],muki[100001];
	long long int X[1001];
	long long int list[100001];
	long long int i,j;
	cin>>N>>T>>Q;
	for(i=1;i<=N;i++) cin>>house[i]>>muki[i];
	for(i=1;i<=Q;i++) cin>>X[i];
	for(i=N;i>=1;i--) {
		if(muki[i]==2) continue;
		if(i==N) list[i]=house[i]+T;
		else if(muki[i+1]==2) list[i]=min(house[i]+T,(house[i]+house[i+1])/2);
		else list[i]=min(house[i]+T,list[i+1]);
	}
	for(i=1;i<=N;i++) {
		if(muki[i]==1) continue;
		if(i==1) list[i]=house[i]-T;
		else if(muki[i-1]==1) list[i]=max(house[i]-T,(house[i]+house[i-1])/2);
		else list[i]=max(house[i]-T,list[i-1]);
	}
	for(i=1;i<=Q;i++) {
		cout<<list[X[i]]<<endl;
	}
	return 0;
}

Measured memory_bytes: 5420
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
#define pb push_back
#define mp make_pair
#define PI 3.14159265358979323846
#define fi first
#define se second

ll mod = 1e9+7;

ll max(ll a, ll b ) {
	if(a>b)
		return a;
	else return b;
}
ll min(ll a, ll b ) {
	if(a<b)
		return a;
	else return b;
}

int main() {
	ll ttt;
	//cin>>ttt;
	ttt = 1;
	while(ttt--) {
		ll x,k,d; cin>>x>>k>>d;
		x = abs(x);
		ll y = x/d;
		ll ans = 0;
		if(y+1>k) ans = x - k*d;
		else {
			ll c = x - (y+1) * d;
			ll temp = k - (y+1);
			//cout<<y<<" ";
			if(temp%2==0) ans = abs(c);
			else ans = abs(c + d);
		}
		cout<<ans;
 	}	
	return 0;
}

Measured memory_bytes: 3632
#include <bits/stdc++.h>
#define fto(i,a,b) for(int i=a; i<=b;++i)
#define fdto(i,a,b) for(int i=a; i>=b;--i)
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pii pair<ll,ll>
#define ll long long
#define maxn 300009
#define maxm 100009
#define gb(i,j) ((i>>j)&1)
#define name "a"
#define endl '\n'

using namespace std;
int l[maxn],r[maxn];
int t[maxm],m,n;
void add(int x, int y){
    for(;x<=m; x+=x&-x)t[x]+=y;
}

int get(int x){
    int res=0;
    for(;x;x-=x&-x)res+=t[x];
    return res;
}
pii c[maxn];
main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    #ifndef ONLINE_JUDGE
    #endif // ONLINE_JUDGE
    cin >> n >> m;
    fto(i,1,n){
        cin >> l[i] >> r[i];
        c[i]=mp(r[i]-l[i]+1,i);
    }
    sort(c+1,c+n+1);
    int j=1;
    for(int i=1; i<=m; ++i){
        while(c[j].fi <i && j<=n){
            int t=c[j].se;
            add(l[t],1);
            add(r[t]+1,-1);
            ++j;
        }
        int res=n-j+1;
        for(int t=0; t<=m; t+=i)res+=get(t);
        cout << res<<endl;
    }
    return 0;
}


Measured memory_bytes: 8320
#include<bits/stdc++.h>
using namespace std;
char walk[10][10],point[100][2];
int sm;
bool jud=false;
int h,w;
void dfs(int x,int y,int all) {
//	cout<<all<<endl;
	if(x==h-1&&y==w-1) {
		if(all-1==0)jud=true;
		return ;
	}
	if(walk[x+1][y]=='.'&&walk[x][y+1]=='.')return; 
	if(walk[x+1][y]=='#')
		dfs(x+1,y,all-1);
	if(walk[x][y+1]=='#')
		dfs(x,y+1,all-1);
	return ;
}
int main() {
	scanf("%d%d",&h,&w);
	for(int i=0; i<h; i++)
		scanf("%s",walk[i]);
	int t=0;
	for(int i=0; i<h; i++)
		for(int j=0; j<w; j++) {
			if(walk[i][j]=='#') {
//				point[++t][1]=i;
//				point[t][2]=j;
				sm++;
			}
		}
	dfs(0,0,sm);
	if(jud) {
		printf("Possible");
		return 0;
	}
	printf("Impossible");
	return 0;
}


Measured memory_bytes: 256
#include<algorithm>//sort,二分探索,など
#include<bitset>//固定長bit集合
#include<cmath>//pow,logなど
#include<complex>//複素数
#include<deque>//両端アクセスのキュー
#include<functional>//sortのgreater
#include<iomanip>//setprecision(浮動小数点の出力の誤差)
#include<iostream>//入出力
#include<iterator>//集合演算(積集合,和集合,差集合など)
#include<map>//map(辞書)
#include<numeric>//iota(整数列の生成),gcdとlcm(c++17)
#include<queue>//キュー
#include<set>//集合
#include<stack>//スタック
#include<string>//文字列
#include<unordered_map>//イテレータあるけど順序保持しないmap
#include<unordered_set>//イテレータあるけど順序保持しないset
#include<utility>//pair
#include<vector>//可変長配列

using namespace std;
typedef long long ll;

//マクロ
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=(ll)(n)-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=(a);i<=(b);i++)
#define FORD(i,a,b) for(ll i=(a);i>=(b);i--)
#define ALL(x) (x).begin(),(x).end() //sortなどの引数を省略したい
#define SIZE(x) ((ll)(x).size()) //sizeをsize_tからllに直しておく
#define INF 1000000000000 //10^12
#define MOD 10000007 //10^9+7
#define PB push_back

template<typename T, typename U, typename Comp=less<>>
bool chmax(T& xmax, const U& x, Comp comp={}) {
    if(comp(xmax, x)) {
        xmax = x;
        return true;
    }
    return false;
}

template<typename T, typename U, typename Comp=less<>>
bool chmin(T& xmin, const U& x, Comp comp={}) {
    if(comp(x, xmin)) {
        xmin = x;
        return true;
    }
    return false;
}

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

//scanf("%lld", &);
//cin >> ;
//cout << ans << endl;

ll N, M, K, i, j, k, l, ans, cnt = 0;

int main(){
    ll a, first_a, sum = 0, tmp, a_max = 0;
    cin >> K >> N;

    scanf("%lld", &first_a); // １番の値を保持しておく。最後に値の差を求めるために。
    a = first_a;

    FOR(i, 1, N - 1){
        scanf("%lld", &tmp);
        chmax(a_max, tmp - a); // 差が一番大きいものを保持する
        sum += tmp - a;
        a = tmp; 
    }

    sum += (K - a) + first_a;
    chmax(a_max, (K - a) + first_a);

    ans = sum - a_max;

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
N = int(input())
s = [input()[0] for _ in range(N)]
t = []
ans = 0
for k in 'MARCH':
    t.append(s.count(k))
for i in range(32):
    u = []
    for j in range(5):
        if i&(1<<j):
            u.append(t[j])
    if len(u) == 3:
        ans += u[0]*u[1]*u[2]
print(ans)

Measured memory_bytes: 3864
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <unordered_map>
#include <queue>
#include <algorithm>

#include <bits/stdc++.h>
#include <cmath>
#include <limits>

using namespace std;
typedef long long LL;
using Graph = vector<vector<int>>;

static long long INF = (1LL<<62);

int main(int argc, char* argv[]){
	cin.tie(0);
	ios::sync_with_stdio(false);

	int A, B, C;
	cin >> A >> B >> C;

	if(A < B){
		if(A < C && C < B){
			printf("Yes\n");
		}
		else{
			printf("No\n");
		}
	}
	else{
		if(B < C && C < A){
			printf("Yes\n");
		}
		else{
			printf("No\n");
		}
	}
	return 0;
}

Measured memory_bytes: 3644
#include<iostream>
#include<vector>
using namespace std;
typedef unsigned int uint;
uint maxv;
void solve(uint now,uint m,uint *a,int n){
  int r=n-1,l=0,mid;
  while(l <=r){
    mid = (l+r)/2;
    if ( a[mid]+now>m)r=mid-1;
    else if ( a[mid]+now <=m){
      if ( a[mid]+now >maxv)maxv=a[mid]+now;
      l=mid+1;
    }
    //else break;
  }
  if ( now+a[mid]>maxv&& now+a[mid]<=m)maxv=now+a[mid];
}


main(){
  int n;
  uint m;
  while(scanf("%d%u",&n,&m) && n){
    uint one[n];
    uint two[n*n];
    int p=0;
    maxv=0;
    for(int i=0;i<n;i++)scanf("%u",&one[i]);
    for(int i=0;i<n;i++){
      if ( one[i]>maxv &&one[i] <=m)maxv=one[i];
      for(int j=i;j<n;j++){
	if ( one[i]+one[j]>m)continue;
	two[p++]=one[i]+one[j];
	if (two[p-1]>maxv)maxv=two[p-1];
      }
    }
    sort(one,one+n);
    sort(two,two+p);
    for(int i=0;i<p;i++){
      if ( two[i]+one[0]>m)break;
      if ( two[i]+two[0]<=m)solve(two[i],m,two,p);
      if ( two[i]+one[0]<=m)solve(two[i],m,one,n);
    }
    printf("%u\n",maxv);
  }
  return false;
}

Measured memory_bytes: 3056
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cassert>
#include <iostream>
#include <sstream>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <utility>
#include <numeric>
#include <algorithm>
#include <bitset>
#include <complex>
#include <array>
#include <list>
#include <stack>
#include <valarray>

using namespace std;

typedef unsigned uint;
typedef long long Int;
typedef unsigned long long UInt;

const int INF = 1001001001;
const Int INFLL = 1001001001001001001LL;

template<typename T> void pv(T a, T b) { for (T i = a; i != b; ++i) cout << *i << " "; cout << endl; }
template<typename T> void chmin(T& a, T b) { if (a > b) a = b; }
template<typename T> void chmax(T& a, T b) { if (a < b) a = b; }
int in() { int x; scanf("%d", &x); return x; }
double fin() { double x; scanf("%lf", &x); return x; }
Int lin() { Int x; scanf("%lld", &x); return x; }

int memo[100050], qd = 0;

int query(int u) {
  if (memo[u] >= 0) {
    return memo[u];
  }
  ++qd;
  char buf[16];
  printf("%d\n", u);
  fflush(stdout);
  scanf("%s", buf);
  if (buf[0] == 'V') {
    exit(0);
  }
  return memo[u] = (buf[0] == 'M' ? 0 : 1);
}

int main() {
  int N = in();

  fill(memo, memo + N, -1);
  
  int fr = 0, to = N;
  while (true) {
    if (to - fr <= 20 - qd) {
      for (int i = fr; i < to; ++i) {
        query(i);
      }
    }

    int hf = (to - fr) / 2;
    if (hf % 2 == 1) ++hf;
    int f = query(fr);
    int t = query(fr + hf);
    if (f != t) {
      to = fr + hf + 1;
    } else {
      fr = fr + hf;
    }
  }

  return 0;
}


Measured memory_bytes: 1236
#include <cstdio>
#include <iostream>
#include <array>
#include <vector>
#include <deque>
#include <string>
#include <algorithm>
#include <functional>
#include <tuple>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <stack>
#include <utility>
#include <memory>
#include <valarray>
#include <climits>

using namespace std;

using ll = long long int;

#define loop(i, N) for (int i = 0; i < N; ++i)
#define scanInt(x) int x; scanf("%d", &x); getchar();
#define scanLLInt(x) ll x; scanf("%lld", &x); getchar();
#define scanVecInt(A, N) vector<int> A(N); loop(i, N){scanf("%d", &(A[i])); getchar();}
#define scanVecLLInt(A, N) vector<ll> A(N); loop(i, N){scanf("%lld", &(A[i])); getchar();}

int main()
{
    scanInt(N);
    int result = 0;
    loop(i, N){
        scanInt(li);
        scanInt(ri);
        result += abs(ri - li) + 1;
    }
    printf("%d\n", result);
}


Measured memory_bytes: 256
io = STDIN
n,k=io.gets.split.map(&:to_i)
str=io.gets.chomp
pat=str.each_char.slice_when{|a,b|a!=b}.map(&:size)
break_cnt=pat.size-1
init_point= pat.select{|i|i>1}.map{|i|i-1}.inject(:+)||0
if n==1
  puts 0
elsif (break_cnt/2<k)
  puts str.size-1
else
  puts init_point+k*2
end


Measured memory_bytes: 7036
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include<queue>
using namespace std;
int gcd(int a,int b) {
    if(b == 0)
        return a;
    return gcd(b,a%b);
}
int main() {
    int x;
    while(cin>>x&&x>=1) {
        int sum=0;
        int i;
        for(i=1; sum<=x; i++) {
            sum+=i;
            if(sum>=x)
                break;
        }
        cout<<i<<endl;
    }
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<stdio.h>
#include<ctype.h>
#include<string>
#include<cmath>
#include<math.h>
#include<vector>
#include<stdlib.h>
#include<algorithm>
#include<functional>

using namespace std;

#define OUT cout <<
#define IN cin >>
#define E << endl;
#define FOR(i,a,b) for(int i = a;i < b;i++)

int n;

void input(){
	IN n;
}

class Dice{
	private:
		string temp;
	public:
		string c[6];
		Dice(){}
		void roll(int axis){
			switch(axis){
			case 0:
				temp = c[0];
				c[0] = c[1];
				c[1] = c[5];
				c[5] = c[4];
				c[4] = temp;
				break;
			case 1:
				temp = c[1];
				c[1] = c[3];
				c[3] = c[4];
				c[4] = c[2];
				c[2] = temp;
				break;
			case 2:
				temp = c[0];
				c[0] = c[2];
				c[2] = c[5];
				c[5] = c[3];
				c[3] = temp;
				break;
			default:
				OUT "switch error!!!!!!\n" E
				break;
			}
		}
		void getd(string& c1, string& c2, string& c3, string& c4, string& c5, string& c6){
			c1 = c[0];
			c2 = c[1];
			c3 = c[2];
			c4 = c[3];
			c5 = c[4];
			c6 = c[5];
		}

		void input(){
			FOR(i,0,6){
				IN c[i];
			}
		}

};

int main(){
	while(true){
		input();
		if(n == 0)break;
		int count = 0;
		bool match[n];
		FOR(i, 0, n){
			match[i] = false;
		}
		string str1[6];
		string str2[6];	

		vector<Dice> dice;
	
		dice.resize(n);
		FOR(i, 0, n){
			dice[i].input();
		}
			

		FOR(i, 0, n - 1){
			FOR(j, i + 1, n){
				bool flag2 = false;
				FOR(z, 0, 4){
				FOR(x, 0, 4){
					FOR(y, 0, 4){
						dice[i].getd(str1[0],str1[1],str1[2],str1[3],str1[4],str1[5]);
						dice[j].getd(str2[0],str2[1],str2[2],str2[3],str2[4],str2[5]);
						
						//printf("\n%s %s %s %s %s %s \n",str1[0].c_str(),str1[1].c_str(),str1[2].c_str(),str1[3].c_str(),str1[4].c_str(),str1[5].c_str());
						//printf("%s %s %s %s %s %s \n\n",str2[0].c_str(),str2[1].c_str(),str2[2].c_str(),str2[3].c_str(),str2[4].c_str(),str2[5].c_str());

						bool flag1 = true;
						FOR(d, 0, 6){					
							if(str1[d] != str2[d]){
								flag1 = false;
							}
						}

						if(flag1){
							if(match[i] == false){							
								flag2 = true;
								//printf("%s %s %s %s %s %s \n",str1[0].c_str(),str1[1].c_str(),str1[2].c_str(),str1[3].c_str(),str1[4].c_str(),str1[5].c_str());
								//printf("%s %s %s %s %s %s \n",str2[0].c_str(),str2[1].c_str(),str2[2].c_str(),str2[3].c_str(),str2[4].c_str(),str2[5].c_str());
							}
							match[j] = true;
						}
						flag1 = true;
					
						dice[i].roll(1);
					}
					dice[i].roll(0);
				}
				dice[i].roll(2);
				}
				//OUT i << " " << j << " " << flag2 E
				if(flag2){
					count++;
					//OUT "count++ " << i << " " << j  E
				}
			}
		}	

		OUT count E

	}
}

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

using namespace std;
using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;

#define INF LONG_MAX
#define MOD 1000000007
#define rng(a) a.begin(),a.end()
#define rrng(a) a.end(),a.begin()

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

  int K,X;
  cin>>K>>X;
  if(X<=500*K)cout<<"Yes"<<endl;
  else cout<<"No"<<endl;
  return 0;
}


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

#define LENGTH 1000000

int countDigit(char *s){
  int i;
  for(i=0;isdigit(s[i]);i++);
  return i;
}

int main()
{
  int n;
  int i;
  int j;
  int k;
  int l;
  int cnt;
  int tmp;
  
    char x[1000000]={0};
      char y[1000000]={0};
 
    while(scanf("%d",&n),n)
      {
        cnt=0;
        scanf("%s",x);
	
        while(n--)

	  {
            cnt=0;
            for(k=0;x[k]!='\0';k++)
	      {
		
                for(l=1;x[k]==x[k+l-1];l++);
                tmp=l-1;
                l--;
		
                if(l>99)
		  {
                    y[cnt++]=l/100+'0';
                    l%=100;
                    y[cnt++]=l/10+'0';
                    l%=10;
                    y[cnt++]=l+'0';
                    y[cnt++]=x[k];
                }
	
		else if(l<=9)

		  {
                    y[cnt++]=l+'0';
                    y[cnt++]=x[k];
                }
			else 

		  {
                    y[cnt++]=l/10+'0';
                    l%=10;
                    y[cnt++]=l+'0';
                    y[cnt++]=x[k];
                }
                k=k+tmp-1;
            }
            for(k=0;k<1000000;k++)

	      {
                x[k]=y[k];
                y[k]=0;
            }
        }
    printf("%s\n",x);
    }
    return 0;
}



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

int n, m, k, ans;

int main() {
	scanf("%d %d %d", &n, &m, &k);
	for (int i = 1; i <= n; i++) {
		int x;
		scanf("%d", &x);
		ans += (m - 1) / x + 1;
	}
	printf("%d", ans + k);
	return 0;
}

Measured memory_bytes: 256
#pragma GCC optimize ("O2")
#pragma GCC target ("avx2")
//#include<bits/stdc++.h>
#include<iostream>
#include<set>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define pb push_back
#define mp make_pair
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
#define Would
#define you
#define please

const int cm = 1 << 17;
char cn[cm], * ci = cn + cm, ct;
inline char getcha() {
	if (ci - cn == cm) { fread_unlocked(cn, 1, cm, stdin); ci = cn; }
	return *ci++;
}
inline int getint() {
	int A = 0;
	if (ci - cn + 16 > cm) while ((ct = getcha()) >= '0') A = A * 10 + ct - '0';
	else while ((ct = *ci++) >= '0') A = A * 10 + ct - '0';
	return A;
}
const int dm = 1 << 22;
char dn[dm], * di = dn;
inline void putint(int X) {
	int keta = 0;
	char C[10];
	while (X) {
		*(C + keta) = '0' + X % 10;
		X /= 10;
		keta++;
	}
	for (int i = keta - 1; i >= 0; i--)* di++ = (*(C + i));
	*di++ = '\n';
}

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


	int N = getint(), Q = getint();

	pair<int, int> to[500001];
	int ne[500001], he[710][710] = {};
	int cnt[710] = {};

	int C[500001];
	rep(i, N) {
		C[i] = getint();
	}

	int kotae[500001];
	rep1(i, Q) {
		int l, r;
		l = getint() - 1;
		r = getint() - 1;

		int L = l / 710;
		int R = r / 710;

		if (L == R) {
			set<int> ST;
			int kari = 0;
			for (int j = l; j <= r; j++) {
				if (ST.find(C[j]) == ST.end()) {
					kari++;
					ST.insert(C[j]);
				}
			}
			kotae[i] = kari;
		}
		else {
			cnt[L]++;
			to[i] = mp(l, r);
			ne[i] = he[L][R];
			he[L][R] = i;
		}
	}
	int tmp[1500];
	rep(i, 710) {
		if (cnt[i] == 0) continue;

		bool A[500001] = {};
		int kari = 0;
		for (int j = i + 1; j < 710; j++) {

			for (int t = he[i][j]; t; t = ne[t]) {
				int kt = 0;
				int kari2 = kari;
				int l = to[t].first;
				int r = to[t].second;
				for (int k = l; k < i * 710 + 710; k++) {
					if (!A[C[k]]) {
						A[C[k]] = 1;
						kari2++;
						tmp[kt++] = C[k];
					}
				}
				for (int k = j * 710; k <= r; k++) {
					if (!A[C[k]]) {
						A[C[k]] = 1;
						kari2++;
						tmp[kt++] = C[k];
					}
				}
				kotae[t] = kari2;
				rep(k, kt) {
					A[tmp[k]] = 0;
				}
			}

			for (int k = j * 710; k < j * 710 + 710; k++) {
				if (!A[C[k]]) {
					A[C[k]] = 1;
					kari++;
				}
			}
		}
	}

	rep1(i, Q) {
		putint(kotae[i]);
	}
	fwrite(dn, di - dn, 1, stdout);

	Would you please return 0;
}

Measured memory_bytes: 19396
use petgraph::unionfind::UnionFind;
use proconio::input;
use proconio::marker::Usize1;

fn main() {
    input! {
        n: usize,
        m: usize,
        e: [(Usize1, Usize1); m],
    }

    let mut count = 0;
    'outer: for i in 0..m {
        let mut uf = UnionFind::new(n);
        for j in 0..m {
            if i != j {
                uf.union(e[j].0, e[j].1);
            }
        }
        let representative = uf.find(0);
        for j in 1..n {
            if representative != uf.find(j) {
                count += 1;
                continue 'outer;
            }
        }
        //println!("i: {}", i);
    }
    println!("{}", count);
}


Measured memory_bytes: 2152
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<functional>
#include<iomanip>
#include<iostream>
#include<map>
#include<queue>
#include<set>
#include<string>
#include<utility>
#include<vector>

using namespace std;
typedef long long ll;
const ll mod = 1000000007;
#define rep(i,n) for(int i=0;i<n;i++)
#define repl(i,s,e) for(int i=s;i<e;i++)
#define reple(i,s,e) for(int i=s;i<=e;i++)
#define revrep(i,n) for(int i=n-1;i>=0;i--)

#define vll    vector<ll>
#define vvll   vector<vector<ll>>
#define all(x) (x).begin(),(x).end()

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

	vector<ll> r(K, N / K);

	reple(i, 1, N % K) r[i]++;

	ll count = 0;

	//組(a, b, c)の各数字をKで割ったあまりをi, j, kとすると、
	//
	//i + j = 0 (mod K)   (1)
	//j + k = 0 (mod K)   (2)
	//k + i = 0 (mod K)   (3)
	//
	//が成り立てば良い。特に(1) - (2) + (3)より
	//
	//2 * i = 0 (mod K)
	//
	//が成り立つ。
	rep(i, K)
	{
		if ((2 * i) % K != 0) continue;

		count += r[i] * r[i] * r[(K - i) % K];
	}

	cout << count << endl;

	return 0;
}

Measured memory_bytes: 1792
import java.util.*;
import java.lang.*;

class Main{
  public static void main(String[] args) {
      Scanner sc = new Scanner(System.in);
      int N = Integer.parseInt(sc.next());
      int[] a = new int[N+2];
      a[0] = 0;
      a[N+1] = 0;
      long sum = 0;
      for(int i = 1; i<N+1; i++){
        a[i] = Integer.parseInt(sc.next());
        sum += Math.abs(a[i] - a[i-1]);
        if(i == N) sum += Math.abs(a[i]);
      }
      long tmp  = sum;
      for(int i = 1; i<N+1; i++){
        tmp -= Math.abs(a[i]-a[i-1]);
        tmp -= Math.abs(a[i+1]-a[i]);
        tmp += Math.abs(a[i+1]-a[i-1]);
        System.out.println(tmp);
        tmp = sum;
      }
  }
}

Measured memory_bytes: 51396
#include <iostream>
#include <vector>
#include <set>

using namespace std;

long long D, G;
long long *p, *c;
set<int> st;


long long dfs(int i, long long sum, long long num) {
    
    if (i == D) {
        for (int j = D-1; j >= 0; j--) {
            if (st.find(j) == st.end()) {
                long long score = 100*(j+1);
                long long k = 0;
                while (k < p[j] && sum < G) {
                    k++;
                    sum += score;
                    num++;
                }
            }
        }
        
        if (sum >= G)
            return num;
        else 
            return 99999999;
    }

    long long ans = 99999999;
    st.insert(i);
    ans = min(ans, dfs(i+1, sum + 100*(i+1)*p[i] + c[i], num+p[i]));
    st.erase(i);


    ans = min(ans, dfs(i+1, sum, num));

    return ans;
}

int main() {
    cin >> D >> G;
    p = new long long[D], c = new long long[D];

    for (int i = 0; i < D; i++)
        cin >> p[i] >> c[i];

    cout << dfs(0, 0, 0) << endl;

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
const int maxx = 100001;

int main() 
{
	string s;
	cin>>s;
	long k;
	cin>>k;
	int ptr = 0;
	while(k>0 && ptr<s.length())
	{
		if( s[ptr] == 'a')
		{
			++ptr;
			continue;
		}
		int need = 123 - s[ptr];
		if( need <= k)
		{
			k-=need;
			s[ptr++]='a';
			continue;
		}
		++ptr;
	}
	if( k>0 )
	{
		k %= 26;
		int v = (s[s.length()-1]-97+k) %26;
		s[s.length()-1] = (char)(v+97);
	}
	cout<<s<<endl;
	return 0;
}

Measured memory_bytes: 512
def main():
    n = int(input())
    v = sorted(list(map(int,input().split())))
    ans = 0
    for i in range(n):
        if i==0 or i==1:
            ans += v[i]*(0.5)**(n-1)
        else:
            ans += v[i]*(0.5)**(n-i)
    print(ans)

if __name__ == "__main__":
    main()

Measured memory_bytes: 3060
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define all(v) v.begin(), v.end()
#define allr(v) v.rbegin(), v.rend()



int main() {
  int d, n, ans;
  cin >> d >> n;
  if (d == 0) ans = 1;
  else if (d == 1) ans = 100;
  else ans = 10000;
  if (n == 100) n++;
  cout << ans * n << endl;
  return 0;
}

Measured memory_bytes: 384
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <deque>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#define p(s) cout<<(s)<<endl
#define REP(i,n,N) for(int i=n;i<N;i++)
#define RREP(i,n,N) for(int i=N-1;i>=n;i--)
#define CK(n,a,b) ((a)<=(n)&&(n)<(b))
#define F first
#define S second
typedef long long ll;
using namespace std;
const ll mod = 1e9+7;

int N, K;
int A[100010];
int main(){
    cin>>N>>K;
    int mx=0;
    REP(i,0,N){
        cin>>A[i];
        mx=max(mx,A[i]);
    }
    int g=A[0];
    REP(i,1,N){
        g = __gcd(g,A[i]);
    }
    if(K%g==0&&K<=mx){
        p("POSSIBLE");
    }else{
        p("IMPOSSIBLE");
    }
    return 0;
}

Measured memory_bytes: 640
from collections import defaultdict
n = input()
first_n = n[0]
finish_n = n[-1]
digit = len(n)
cnt = defaultdict(lambda :0)

for i in range(1,int(n) + 1):
    temp = str(i)
    temp_tuple = (int(temp[0]), int(temp[-1]))
    cnt[temp_tuple] += 1

ans = 0
for i in range(1, 10):
    for j in range(1, 10):
        ans += cnt[(i, j)] * cnt[(j, i)]
print(ans)
#print(cnt)

Measured memory_bytes: 3316
from math import atan2, degrees

a, b, x = map(int, input().split())

# a * b * c / 2 >= x and 0 <= c <= a
c = 2 * x / (a * b)

# (b + d) * a * a / 2 >= x and 0 <= d <= b
d = 2 * x / (a * a) - b

if c <= a:
    deg = 90 - degrees(atan2(c, b))
else:
    deg = degrees(atan2(b - d, a))

print(deg)

Measured memory_bytes: 3060
(defun split (delimiter target-string)
  (let ((delimiter-position (search delimiter target-string))
        (delimiter-size (length delimiter)))
    (if delimiter-position
        (cons (subseq target-string 0 delimiter-position)
              (split delimiter (subseq target-string (+ delimiter-position delimiter-size))))
        (list target-string))))

(defun split-to-int (str)
  (mapcar #'parse-integer (split " " str)))

(defun min-time (l1 l2)
  (let ((x1 (car l1))
        (x2 (car l2))
        (y1 (cadr l1))
        (y2 (cadr l2)))
    (+ (abs (- x1 x2))
       (abs (- y1 y2)))))

(defun can-reach (mintime time)
  (and (<= mintime time)
       (evenp (- time mintime))))

(defun check-plan (l1 l2)
  (can-reach (min-time (cdr l1)
                       (cdr l2))
             (- (car l2) (car l1))))

(defun collect-plans (n)
  (loop :as i
        :below n
        :collect (split-to-int (read-line))))

(defun can-travel (now-condition plans)
  (if plans
      (if (check-plan now-condition (car plans))
          (can-travel (car plans) (cdr plans))
          "No")
      "Yes"))
  
(let* ((n (read))
       (plans (collect-plans n)))
  (princ (can-travel '(0 0 0) plans)))
  
  




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

int find(int X,vector<int> &P){
  if(P.at(X)<0){
    return X;
  }
  return P.at(X)=find(P.at(X),P);
}

void unite(int X,int Y,vector<int> &P){
  X=find(X,P);
  Y=find(Y,P);
  if(X==Y){
    return;
  }
  P.at(Y)+=P.at(X);
  P.at(X)=Y;
}

int main(){
  int N,Q;
  cin >> N >> Q;
  vector<int> P(N,-1);
  for(int i=0;i<Q;i++){
    int T,U,V;
    cin >> T >> U >> V;
    if(T==0){
      unite(U,V,P);
    }
    else{
      if(find(U,P)==find(V,P)){
        cout << 1 << endl;
      }
      else{
        cout << 0 << endl;
      }
    }
  }
}
    
    
  

Measured memory_bytes: 3944
#include<bits/stdc++.h>
#define REP(i,n) for(int i=0,i##_len=(n);i<i##_len;++i)
//#define int long long
using namespace std;
typedef pair<int,int> P;
signed main(){
    int N,M;
    vector<vector<int>> to(N);
    vector<int> p(N);
    cin>>N>>M;
    REP(i,M){
        int k;cin>>k;
        REP(j,k){
            int s;cin>>s;
            s--;
            to[s].push_back(i);
        }
    }
    REP(i,M) cin>>p[i];
    int ans=0;
    REP(i,1<<N){//2^nパターン列挙
        vector<int> bulb(M,0);
        REP(j,N){//スイッチjに対してビット走査
            int bit=(i>>j)&1;
            if(bit==1) REP(k,to[j].size()) bulb[to[j][k]]++;
        }
        bool ok=true;
        REP(j,M) if(bulb[j]%2!=p[j]) ok=false;
        if(ok) ans++;
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 172544
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define gcd(a,b) __gcd(a,b)
#define ff first
#define ss second
#define p pair<int,int>
#define pb push_back
#define endl '\n'
#define w(t) ll test;cin>>test;while(test--)
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(0);
#define pi acos(-1)

int main()
{
    fast;
    int a;
    cin>>a;
    int sum=a+pow(a,2)+pow(a,3);
    cout<<sum<<endl;
}



Measured memory_bytes: 4112
import java.util.Scanner;

class Main {
    public static void main(String[] args){
        Scanner stdIn = new Scanner(System.in);
        int a = stdIn.nextInt();
        int b = stdIn.nextInt();
        int c = stdIn.nextInt();
        int d = stdIn.nextInt();

        int ab = a - b;
        int bc = b - c;
        int ca = c - a;
        
        if(ab < 0)
            ab = b - a;
        if(bc < 0)
            bc = c - b;
        if(ca < 0)
            ca = a - c;
        
        if(ca <= d)
            System.out.println("Yes");
        else if(ab <= d && bc <= d)
            System.out.println("Yes");
        else
            System.out.println("No");
    }
}

Measured memory_bytes: 21972
import sys
inf = 10**15
mod = 10**9+7
n, y = map(int, input().split())
ans=0
A = y//10000
for i in range(A+1):
    restY = y-i*10000
    restN = n-i
    if restY >= 0 and restN >= 0:
        B = restY//5000
        for j in range(B+1):
            restYY = restY-j*5000
            restNN = restN-j
            if restNN>=0 and restYY == restNN*1000:
                print('{} {} {}'.format(i,j,restNN))
                sys.exit()
print('{} {} {}'.format(-1,-1,-1))

Measured memory_bytes: 40812
#include<bits/stdc++.h>
using namespace std;
#define int long long
struct starrysky{
  int n;
  starrysky(){}
  starrysky(int n_){init(n_);};
  vector<int> data,datm;
  void init(int n_){
    n=1;
    while(n<n_) n*=2;
    data.clear();
    datm.clear();
    data.resize(2*n-1,0);
    datm.resize(2*n-1,0);
  }
  void add(int a,int b,int x,int l,int r,int k){
    if(r<=a||b<=l) return;
    if(a<=l&&r<=b){
      data[k]+=x;
      return;
    }
    add(a,b,x,l,(l+r)/2,k*2+1);
    add(a,b,x,(l+r)/2,r,k*2+2);
    datm[k]=min(datm[k*2+1]+data[k*2+1],datm[k*2+2]+data[k*2+2]);
  }
  void add(int a,int b,int x){
    add(a,b,x,0,n,0);
  }
  int query(int a,int b,int l,int r,int k){
    if(r<=a||b<=l) return INT_MAX;
    if(a<=l&&r<=b){
      return data[k]+datm[k];
    }
    return min(query(a,b,l,(l+r)/2,k*2+1),query(a,b,(l+r)/2,r,k*2+2))+data[k];
  }
  int query(int a,int b){
    return query(a,b,0,n,0);
  }
};
#define MAX 333333
string buf;
int dp[MAX],imos[MAX];
signed main(){
  int n,q;
  cin>>n>>q;
  cin>>buf;
  set<int> s;
  for(int i=0;i<n;i++) {
    if(buf[i]=='(') dp[i]=1;
    else dp[i]=-1;
    if(buf[i]==')') s.insert(i);
  }
  imos[0]=dp[0];
  for(int i=1;i<n;i++) imos[i]=imos[i-1]+dp[i];
  starrysky ss(n);
  for(int i=0;i<n;i++) ss.add(i,i+1,imos[i]);
  for(int i=0;i<q;i++){
    int p;cin>>p;p--;
    if(dp[p]==1){
      dp[p]*=-1;
      s.insert(p);
      ss.add(p,n,-2);
      int k=*s.begin();
      s.erase(k);
      dp[k]*=-1;
      ss.add(k,n,2);
      cout<<k+1<<endl;
    }else{
      //cout<<p<<endl;
      dp[p]*=-1;
      s.erase(p);
      ss.add(p,n,2);
      int l=0,r=p;
      while(l+1<r){
	int m=(l+r)/2;
	//cout<<m<<":"<<ss.query(m,n)<<endl;
	if(ss.query(m,n)>=2) r=m;
	else l=m;
      }
      cout<<r+1<<endl;
      dp[r]*=-1;
      s.insert(r);
      ss.add(r,n,-2);
    }
  }
  return 0;
}

Measured memory_bytes: 31464
#include <algorithm>
#include <array>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <sstream>
#include <unordered_map>
#include <vector>


#define INF 1000000000
#define MOD 1000000007
#define ALL(x) std::begin(x), std::end(x)


int main(int argc, char** argv)
{
  std::cin.tie(0);
  std::ios_base::sync_with_stdio(0);

  std::cout << std::fixed << std::setprecision(15);

  int N, t[111], v[111], vp[22222];

  std::cin >> N;

  t[0] = 0;
  
  for (int i = 1; i <= N; i ++) {
    std::cin >> t[i];

    t[i] += t[i - 1];
  }

  for (int i = 0; i < N; i ++)
    std::cin >> v[i];
  
  v[N] = 0;

  int tp = t[N];

  N ++;

  for (int i = 0; i <= tp; i ++) {
    vp[i] = INF;
    
    for (int j = 0; j < N; j ++)
      if (t[j] >= i)
        vp[i] = std::min((t[j] - i) + v[j], vp[i]);
  }

  for (int i = N - 1; i >= 0; i --)
    v[i + 1] = v[i];

  v[0] = 0;

  for (int i = 0; i <= tp; i ++)
    for (int j = 0; j < N; j ++)
      if (i >= t[j])
        vp[i] = std::min((i - t[j]) + v[j], vp[i]);

  for (int i = 0; i < N - 1; i ++)
    for (int j = t[i]; j <= t[i + 1]; j ++)
      vp[j] = std::min(v[i + 1], vp[j]);

  int a = 0;

  for (int i = 0; i < N - 1; i ++) {
    for (int j = t[i]; j < t[i + 1]; j ++) {
      int v0 = vp[j], v1 = vp[j + 1];

      if (v0 != v1) {
        a += (v0 + v1) * 2;
      }
      else if (v0 < v[i + 1]) {
        a += (v0 + v1) * 2 + 1;
      }
      else {
        a += (v0 + v1) * 2;
      }
    }
  }

  std::cout << a / 4.0 << std::endl;

  return 0;
}


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

int main(){
    string s,s1;
    cin >> s;
    s1 = s;
    reverse(s1.begin(),s1.end());
    int ans=0;
    int p = s.size()/2;
    for(int i=0;i<p;i++){
        if(s.at(i)!=s1.at(i)){
            ans++;
            //cout << ans << endl;
        }
    }
    cout << ans << endl;
}

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

template <typename T,typename E>
struct SegmentTree{
  using F = function<T(T,T)>;
  using G = function<T(T,E)>;
  using H = function<E(E,E)>;
  using P = function<E(E,size_t)>;
  Int n;
  F f;
  G g;
  H h;
  T ti;
  E ei;
  P p;
  vector<T> dat;
  vector<E> laz;
  SegmentTree(Int n_,F f,G g,H h,T ti,E ei,
	      P p=[](E a,size_t b){b++;return a;}):
    f(f),g(g),h(h),ti(ti),ei(ei),p(p){
    init(n_);
  }
  void init(Int n_){
    n=1;
    while(n<n_) n*=2;
    dat.assign(2*n-1,ti);
    laz.assign(2*n-1,ei);
  }
  void build(Int n_, vector<T> v){
    for(Int i=0;i<n_;i++) dat[i+n-1]=v[i];
    for(Int i=n-2;i>=0;i--)
      dat[i]=f(dat[i*2+1],dat[i*2+2]);
  }
  inline void eval(Int len,Int k){
    if(laz[k]==ei) return;
    if(k*2+1<n*2-1){
      laz[k*2+1]=h(laz[k*2+1],laz[k]);
      laz[k*2+2]=h(laz[k*2+2],laz[k]);
    }
    dat[k]=g(dat[k],p(laz[k],len));
    laz[k]=ei;
  }
  T update(Int a,Int b,E x,Int k,Int l,Int r){
    eval(r-l,k);
    if(r<=a||b<=l) return dat[k];
    if(a<=l&&r<=b){
      laz[k]=h(laz[k],x);
      return g(dat[k],p(laz[k],r-l));
    }
    return dat[k]=f(update(a,b,x,k*2+1,l,(l+r)/2),
		    update(a,b,x,k*2+2,(l+r)/2,r));
  }
  T update(Int a,Int b,E x){
    return update(a,b,x,0,0,n);
  }
  T query(Int a,Int b,Int k,Int l,Int r){
    eval(r-l,k);
    if(r<=a||b<=l) return ti;
    if(a<=l&&r<=b) return dat[k];
    T vl=query(a,b,k*2+1,l,(l+r)/2);
    T vr=query(a,b,k*2+2,(l+r)/2,r);
    return f(vl,vr);
  }
  T query(Int a,Int b){
    return query(a,b,0,0,n);
  }
  void update(Int k,T x){
    query(k,k+1);//evaluate
    k+=n-1;
    dat[k]=x;
    while(k){
      k=(k-1)/2;
      dat[k]=f(dat[k*2+1],dat[k*2+2]);
    }
  }
};

//INSERT ABOVE HERE
signed main(){
  Int n,m,q;
  cin>>n>>m>>q;
  using T = tuple<Int, Int, Int, Int>;
  vector<T> v;
  for(Int i=0;i<m;i++){
    Int d,a,b;
    cin>>d>>a>>b;
    v.emplace_back(d,q,a,b);
  }
  for(Int i=0;i<q;i++){
    Int d,a,b;
    cin>>d>>a>>b;
    v.emplace_back(d,i,a,b);
  }
  sort(v.begin(),v.end());
  SegmentTree<Int, Int>::F f=[](Int a,Int b){return max(a,b);};
  SegmentTree<Int, Int> seg(n+1,f,f,f,-1,-1);
  for(Int i=0;i<n+1;i++) seg.update(i,i+1,i);
  
  vector<Int> ans(q);
  for(Int i=0;i<(Int)v.size();i++){
    Int d,x,a,b;
    tie(d,x,a,b)=v[i];
    if(x==q){
      Int k=seg.query(a,b+1);
      seg.update(a,b+1,k);
    }else{
      Int k=seg.query(a,a+1),p=a;
      while(p!=k){
	p=k;
	k=seg.query(a,k+1);
      }
      seg.update(a,k+1,k);
      ans[x]=k>=b;
    }
  }
  for(Int i=0;i<q;i++) cout<<(ans[i]?"Yes":"No")<<endl;
  return 0;
}





Measured memory_bytes: 14060
#include <algorithm>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <set>
#include <string>
#include <vector>

using namespace std;

typedef long long ll;
constexpr ll MOD = 1000000007;

// struct UnionFind {
//     vector<int> par;
    
//     UnionFind(int N): par(N) {
//         for (int i=0;i<N;i++) par[i] = i;
//     }

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

//     void unite(int x, int y) {
//         int rx = root(x);
//         int ry = root(y);
//         if (rx == ry) return;
//         par[rx] = ry;
//     }

//     bool same(int x, int y) {
//         int rx = root(x);
//         int ry = root(y);
//         return rx == ry;
//     }
// };

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

vector<ll> fact(200010), factinv(200010);
vector<ll> expa(100010), expb(100010), expabinv(200010);

ll exp(ll b, int e) {
    ll ans = 1;
    while (e) {
        if (e&1) ans *= b;
        ans %= MOD;
        e >>= 1;
        b *= b;
        b %= MOD;
    }
    return ans;
}

void pp(int i, int a, int b) {
// factorial
    fact[0] = 1;
    for (int k=1;k<2*i;k++) {
        fact[k] = fact[k-1] * k % MOD;
    }
// factorial inverse
    factinv[0] = 1;
    for (int k=1;k<2*i;k++) {
        factinv[k] = exp(fact[k],MOD-2);
    }
// exponential
    expa[0] = 1;
    for (int k=1;k<=i;k++){
        expa[k] = exp(a,k);
    }
    expb[0] = 1;
    for (int k=1;k<=i;k++){
        expb[k] = exp(b,k);
    }
    expabinv[0] = 1;
    for (int k=1;k<=2*i;k++) {
        expabinv[k] = exp(a+b,MOD-k-1);
    }
}

int main(void) {
    int N, A, B, C;
    cin >> N >> A >> B >> C;
    pp(N, A, B);
    ll ans = 0, denom, numer;
    for (int i=N;i<2*N;i++) {
        numer = expa[N]*expb[i-N] % MOD;
        numer = (numer + expa[i-N]*expb[N] % MOD) % MOD;
        numer = (numer * 100 % MOD) * fact[i] % MOD;
        denom = factinv[i-N] * factinv[N-1] % MOD;
        denom = denom * expabinv[i+1] % MOD;
        ans += numer * denom % MOD;
        ans %= MOD;
    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 6528