akhauriyash/Code-Regression huggingface dataset:
using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Linq;
using System.Linq.Expressions;
using System.Text;
class Simple {
    int N;
    int[] A;
    void Solve() {
        //input
        N = io.Int;
        A = new int[N];
        for (int i = 0; i < N; ++i)
            A[i] = io.Int;
        //cal
        var x4 = A.Where(v => v % 4 == 0).Count();
        var x2 = A.Where(v => v % 2 == 0).Count()-x4;
        var ans = N <= (2 * x4 + 1) + Math.Max(0,(x2 - 1));
        //ret
        Console.WriteLine(ans ? "Yes" : "No");
    }

    SimpleIO io = new SimpleIO();
    public static void Main(string[] args) { new Simple().Stream(); }
    void Stream() {
        Solve();
        io.writeFlush();
    }
}

class SimpleIO {
    string[] nextBuffer;
    int BufferCnt;
    char[] cs = new char[] { ' ' };
    StreamWriter sw = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
    public SimpleIO() {
        nextBuffer = new string[0];
        BufferCnt = 0;
        Console.SetOut(sw);
    }
    public string Next() {
        if (BufferCnt < nextBuffer.Length)
            return nextBuffer[BufferCnt++];
        string st = Console.ReadLine();
        while (st == "")
            st = Console.ReadLine();
        nextBuffer = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
        BufferCnt = 0;
        return nextBuffer[BufferCnt++];
    }
    public string String => Next();
    public char Char => char.Parse(String);
    public int Int => int.Parse(String);
    public long Long => long.Parse(String);
    public double Double => double.Parse(String);
    public void writeFlush() { Console.Out.Flush(); }
}

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

#define ll long long
#define Fi first
#define Se second
#define Pb push_back
#define vi vector<int>
#define vp vector<pair<int,int>>
#define vvi vector<vector<int>>
#define vvp vector<vector<pair<int,int>>>

const int INF = 1e9;
const int MOD = 1e9+7;
using Graph = vector<vector<int>>; //Caution!! Segmentation Fault!! Don't forget to add +1!

#define all(v) v.begin(),v.end()
#define output_s(a) printf("%s\n",(a).c_str())

#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define Rep(i,n,m) for(int i=(int)(n);i<(int)(m);i++)
#define RepS(i,n,m) for(int i=(int)(n);i<=(int)(m);i++)
#define RRepS(i,n,m) for(int i=(int)(n);i>=(int)(m);i--)
#define RepA(x) for(auto &item:(x))

void CINT(){}
template <class Head,class... Tail>
void CINT(Head&& head,Tail&&... tail){
    cin>>head;
    CINT(move(tail)...);
}    
#define CIN(...) int __VA_ARGS__;CINT(__VA_ARGS__)
#define LCIN(...) ll __VA_ARGS__;CINT(__VA_ARGS__)
#define SCIN(...) string __VA_ARGS__;CINT(__VA_ARGS__)

template<typename TypeInt> //最大公約数
TypeInt GCD(TypeInt a,TypeInt b){
    if(a%b==0) return b;
    else return GCD(b,a%b);
}
template<typename TypeInt> //最小公倍数
TypeInt LCM(TypeInt a,TypeInt b){
    return a*b/GCD(a,b);
}

int IN_int(){
    int x;
    scanf("%d",&x);
    return x;
}

//library----------------------------------------------

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

const int NMAX = 25;
bool flag;


int main(){
    CIN(N,D);
    vvi x(N,vi(D));
    rep(i,N){
        rep(j,D) cin>>x[i][j];
    }
    int ans=0;
    rep(i,N-1){
        Rep(j,i+1,N){
            int check=0;
            rep(k,D){
                check+=pow((x[i][k]-x[j][k]),2);
            }
            if(sqrt(check)==floor(sqrt(check))) ans++;
        }
    }
    printf("%d\n",ans);
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fr(i,j,k) for(int i=j;i<k;i++)
#define f(n) fr(i,0,n)
#define f1(n) fr(i,1,n+1)
#define ms(i) memset(i,0,sizeof(i));
#define pb push_back
const int mod=1e9+7;
 
int main(){
	int n;
	while(cin >> n){
		int cont[n+5] = {};
		f(n)cin >> cont[i];
		multiset<int>st;
		for(int i = n - 1 ; i >= 0 ; i-- ){
			if(st.upper_bound(cont[i])==st.end()){
				st.insert(cont[i]);
			}
			else{
				st.erase(st.upper_bound(cont[i]));
				st.insert(cont[i]);
			}
		}
		cout << st.size() << endl;
	}
 
}

Measured memory_bytes: 5376
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
 
#define BIG 2000000007
 
#define MOD 1000000007
typedef unsigned long long ull;
typedef   signed long long sll;
 
typedef struct {
	int a;
	int b;
} hw;
 
#define N_MAX 100000
#define M_MAX 100000
 
ull n, m, k;
ull h, w;
// ull a[N_MAX];
// ull b[N_MAX];
// ull dp[N_MAX][M_MAX + 1];
// char s[N_MAX + 1];
// char t[N_MAX + 1];
hw arr[N_MAX];
 
void swap_adj(ull *a, ull *b){
	ull tmp = *b;
	*b = *a;
	*a = tmp;
	return;
}

ull divide(ull a, ull b){
	ull x = MOD - 2;
	ull ans = 1;
	while (x) {
		if (x & 1) ans = (ans * b) % MOD;
		b = (b * b) % MOD;
		x /= 2;
	}
	return (a * ans) % MOD;
}
 
int digits(ull x){
	int i = 1;
	while (x >= 10) {
		x /= 10;
		i++;
	}
	return i;
}
 
int min(ull x, ull y){
	return (x < y) ? x : y;
}
 
ull gcd(ull x, ull y){
	if (x < y) {
		return gcd(y, x);
	} else if (y == 0) {
		return x;
	} else {
		return gcd(y, x % y);
	}
}
 
ull bitpow(ull a, ull x){
	ull result = 1;
	while (x) {
		if (x & 1) {
			result *= a;
			result %= MOD;
		}
		x /= 2;
		a = (a * a) % MOD;
	}
	return result;
}

int comp(const void *left, const void *right){
	if ((*(int*)left) < (*(int*)right)) {
		return -1;
	} else if ((*(int*)left) > (*(int*)right)) {
		return +1;
	} else {
		return 0;
	}
}

int nextroute(int arr[]){
	int i = n - 1;
	int j, x;
	while (arr[i - 1] > arr[i]) i--;

	x = n;
	for (j = i; j < n; j++) {
		if (arr[j] < arr[i - 1]) continue;
		if (x == n || arr[x] > arr[j]) x = j;
	}
	arr[i - 1] ^= arr[x];
	arr[x] ^= arr[i - 1];
	arr[i - 1] ^= arr[x];

	qsort(&arr[i], n - i, sizeof(int), comp);
	return 0;
}

ull solve(){
	int i, j;
	int path[8][8];
	int a[8];
	ull routes = 0;

	for (i = 0; i < n; i++) {
		for (j = 0; j < n; j++) {
			path[i][j] = 0;
		}
	}
	for (i = 0; i < m; i++) {
		int a, b;
		scanf("%d%d", &a, &b);
		path[a - 1][b - 1] = path[b - 1][a - 1] = 1;
	}
	for (i = 0; i < n; i++) {
		a[i] = i;
	}
	while (a[0] == 0) {
		// for (i = 0; i < n; i++) printf("%d ", a[i]);
			// puts("");
		for (i = 1; i < n; i++) {
			if (path[a[i - 1]][a[i]] == 0) break;
		}
		if (i == n) routes++;
		// printf("%llu\n", routes);
		nextroute(a);
	}

	printf("%d\n", routes);
 
	return 0;
}
 
int main(void){
	int i, j;
	int x = 0;
 
	scanf("%llu%llu", &n, &m);

	solve();
 
	return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
#define all(v) v.begin(), v.end()
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
const double PI=3.14159265358979323846;
const int64_t waru = 1000000007;
using in = int64_t;

int main(){
  in n;
  cin>>n;
  vector<in> a(n+1);
  vector<in> b(n);
  rep(i,n+1) cin>>a.at(i);
  rep(i,n) cin>>b.at(i);
  in ans =0ll;
  
  for(in i=0;i<n;i++){
     if(a.at(i)>b.at(i)){
       ans += b.at(i);
     }
    
    else if(a.at(i+1)+a.at(i)<=b.at(i)){
      ans += a.at(i+1)+a.at(i);
      a.at(i+1) =0;
    }
    
    else{
       ans += b.at(i);
      a.at(i+1) -= (b.at(i)-a.at(i));
    }
  }
  
  
  cout<<ans;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define INF 2e9
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;

    int ans = pow(n,3);

    cout << ans << endl;

}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const int N=200005,M=6000005;
int n,a[N],val[N],suf[N],pos[N][2],mx[2],mn[2][2],le[2][2];
char ans[N];
struct BIT{
	int t[N],tg[M],vl[M],cnt;
	inline void ad(int x,int vv){
		for (;x<=n;x+=(x&(-x))){
			tg[++cnt]=x;vl[cnt]=t[x];
			t[x]=max(t[x],vv);
		}
	}
	inline int get(int x){
		int ans=-1e9;
		for (x=min(x,n);x;x-=(x&(-x)))ans=max(ans,t[x]);
		return ans;
	}
	inline void reback(int x){
		for (;cnt>x;t[tg[cnt]]=vl[cnt--]);
	}
}bit[2];
int main(){
	scanf("%d",&n);
	int cur=n+1,ptr,nq=0;
	for (int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		a[i]=n+1-a[i];
		if (cur>a[i]){
			cur=a[i];
			val[i]=2;
		} 
		else val[i]=1;
	}
	memset(bit[1].t,0x8f,sizeof(bit[1].t));
	for (int i=n;i;i--)suf[i]=suf[i+1]+(val[i]==2);
	for (int i=n;i>1;i--){
		for (int j=0;j<2;j++)mx[j]=max(0,bit[j].get(a[i]));
		for (int j=0;j<2;j++){
			int x=mx[j]+val[i];
			bit[x&1].ad(a[i],x);
		}
		for (int j=0;j<2;j++)pos[i][j]=bit[j].cnt;
	}
	mn[0][0]=mn[0][1]=n+1;
	for (int i=1;i<=n;i++){
		nq^=1;
		if (i<n)
			for (int j=0;j<2;j++)bit[j].reback(pos[i+1][j]);
		for (int j=0;j<2;j++){
			for (int k=0;k<2;k++)mn[nq][k]=mn[nq^1][k],le[nq][k]=le[nq^1][k];
			if (a[i]<mn[nq^1][j]){
				mn[nq][j]=a[i];
				le[nq][j]=le[nq^1][j]+1;
			}
			ptr=i==n?(le[nq][0]==le[nq][1]):0;
			if (i<n){
				for (int k=0;k<2;k++){
					int x=le[nq][k]-le[nq][k^1]+suf[i+1];
					if (x>=0&&x<=bit[x&1].get(mn[nq][k^1])){
						ptr=1;
						break;
					}
				}
			}
			if (ptr){
				ans[i]='0'+j;
				break;
			}
		}
		if (!ans[i]){
			puts("-1");
			return 0;
		}
	}
	for (int i=1;i<=n;i++)putchar(ans[i]);
	return 0;
}


Measured memory_bytes: 44544
#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
#include<cstdio>
#include<climits>
#include<cmath>
#include<cstring>
#include<string>

#define f first
#define s second
#define mp make_pair

#define REP(i,n) for(int i=0; i<(int)(n); i++)
#define FOR(i,c) for(__typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define ALL(c) (c).begin(), (c).end()

using namespace std;

typedef unsigned int uint;
typedef long long ll;

const int coin[] = {
  1, 5, 10, 50, 100, 500
};

int num[6];
int mm;
int p;
bool f[1000*1000];

int change(int sum){
  int ret = 0;
  for(int i=5; i>=0; i--){
    ret += sum / coin[i];
    sum %= coin[i];
  }
  return ret;
}

#define MAX (10000000)

void search(int sum, int i, int cc){
  //printf("search(%d,%d,%d), mm=%d\n",sum,i,cc,mm);
  if(sum >= 0){
    int tmp = cc + change(sum);
    mm = min(tmp, mm);
  }

  if(i<0) return;
  if(mm < cc) return;

  int cnt;
  if(sum < 0){
    cnt = (-sum)/coin[i];
    if(cnt >= num[i]) cnt = num[i];
  }else{
    cnt = 0;
  }
  for(int j=0; j<=6; j++)
    if(cnt+j <= num[i]) search(sum+(cnt+j)*coin[i], i-1, cc+cnt+j);
}

int main(){
  while(scanf("%d",&p), p){
    int ans = 0;
    
    REP(i,6) scanf("%d",&num[i]);
    mm = 0;
    memset(f,0,sizeof(f));

    int sum = 0;
    for(int i=5; i>=0; i--){
      int cnt = 0;
      while(sum < p && cnt < num[i]){
	cnt++; sum+=coin[i];
      }
      mm+=cnt;
      if(sum >= p) break;
    }
    mm += change(sum-p);
    search(-p,5,0);
    printf("%d\n", mm);
  }
  return 0;
}

Measured memory_bytes: 0
#include<bits/stdc++.h>
using namespace std;
#define int long long
//BEGIN CUT HERE
template<typename T> 
struct BIT{
  vector<T> bit;
  int n;
  //1-indexed
  BIT(){init(-1,(T)0);}
  BIT(int n_,T d){init(n_,d);}
  void init(int n_,T d){
    n=n_;
    bit.clear();
    bit.resize(n+1,d);
  }
  T sum(int i){
    T s=0;
    for(int x=i;x>0;x-=(x&-x))
      s+=bit[x];
    return s;
  }
  void add(int i,T a){
    if(i==0) return;
    for(int x=i;x<=n;x+=(x&-x))
      bit[x]+=a;
  }
  T sum0(int i){
    return sum(i+1);
  }
  void add0(int i,T a){
    add(i+1,a);
  }
};
//END CUT HERE

signed main(){
  int n,q;
  cin>>n>>q;
  BIT<int> bit(n+100,0);
  for(int i=0;i<q;i++){
    int c,x,y;
    cin>>c>>x>>y;
    if(c) cout<<bit.sum(y)-bit.sum(x-1)<<endl;
    else bit.add(x,y);
  }
  return 0;
}
/*
verified on 2017/09/22
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_B&lang=jp
 */

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

///Author:Refat(BSMRSTU)///

#define ll long long
#define ull unsigned long long
#define ff first
#define ss second
#define pb push_back
#define vi vector<int>
#define pii pair<int,int>
#define pil pair<int,ll>
const int N = 1e5 + 5;
const int M = 1e9 + 7;
const double pi=2*acos(0.0);
const double esp=1e-9;
int Set(int N,int pos) {
    return N=N | (1<<pos);
}
int reset(int N,int pos) {
    return N= N & ~(1<<pos);
}
bool check(int N,int pos) {
    return (bool)(N & (1<<pos));
}
int main() {
    /// freopen("input.txt","r",stdin);
    /// freopen("output.txt","w",stdout);
    int test=1;
    ll cnt,sum,ans=0ll,st=0ll;
    string s;
    ///scanf("%d",&test);
    for(int cs=1; cs<=test; cs++) {
        cin>>s;
        for(int i=0; i<(int)s.length();) {
            cnt=0;
            if(s[i]=='<') {
                while(s[i]=='<') {
                    cnt++;
                    i++;
                }
                cnt-=1;
                sum=(cnt*(cnt+1))/2ll;
                ans+=sum;
                if(i-1==(int)s.length()-1) {
                    ans+=(cnt+1);
                }
                st=cnt;
                //cout<<st<<endl;
            } else {
                while(s[i]=='>') {
                    cnt++;
                    i++;
                }
                sum=(cnt*(cnt+1))/2ll;
                //cout<<ans<<" "<<i-1<<endl;
                ans+=sum;
                if(st>=cnt) {
                    //cout<<ans<<endl;
                    ans+=(st-cnt+1);
                    //cout<<ans<<" "<<i-1<<endl;
                    //cout<<ans;
                    //break;
                }
            }

        }
        printf("%lld\n",ans);
    }
    return 0;
}



Measured memory_bytes: 900
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<math.h>
#include<iomanip>
#include<set>
#include<numeric>
#include<cstring>
#include<cstdio>
#include<functional>
#include<bitset>

#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define REVERSE(v,n) reverse(v,v+n);
#define VREVERSE(v) reverse(v.begin(), v.end());
#define ll long long
#define pb(a) push_back(a)
#define m0(x) memset(x,0,sizeof(x))
#define print(x) cout<<x<<endl;
#define pe(x) cout<<x<<" ";
#define lb(v,n) lower_bound(v.begin(), v.end(), n);
#define ub(v,n) upper_bound(v.begin(), v.end(), n);
#define int long long
#define all(x) (x).begin(), (x).end()

using namespace std;

const int MAX = 500010;
const int MOD = (ll)1e9 + 7;
const ll INF = 1e17;
const double pi = acos(-1);
const double EPS = 1e-10;

typedef pair<int, int>P;

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


int num[8];
signed main() {
	REP(i, 7) {
		cin >> num[i];
	}
	//print(-1 / 2 * 2);
	int ans = 0;
	ans += num[1];
	if (num[3] % 2 == 1 && num[4] % 2 == 1) {
		if (num[0] > 0) {
			ans += 3;
			num[0]--; num[3]--; num[4]--;
		}
	}
	int B = (num[0] / 2) * 2;
	ans += B;
	num[0] -= B;
	int ans2 = ans;
	if (num[0] == 1) {
		if (num[3] % 2 == 1 || num[4] % 2 == 1) {
			if (num[3] > 0 && num[4] > 0) {
				ans2 += 3;
				ans2 += (num[3] - 1) / 2 * 2 + (num[4] - 1) / 2 * 2;
				print(ans2);
				return 0;
			}
			ans2 += num[3] / 2 * 2 + num[4] / 2 * 2;
			print(ans2); return 0;
		}
		else {
			ans2 += num[3] + num[4];
			print(ans2); return 0;
		}
	}
	else {
		ans2 += num[3] / 2 * 2 + num[4] / 2 * 2;
		print(ans2);
		return 0;
	}
	int A = min(num[0], min(num[3], num[4]));
	ans += A*3;
	num[0] -= A; num[3] -= A; num[4] -= A;
	ans += min(num[3], num[4])*2;
	print(ans);
	//print(-1 / 2 * 2);
}	


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> pi;
#define f first
#define s second
#define FAST ios_base::sync_with_stdio(0); cin.tie(0);
const int maxn = 100010;
const int INF = INT_MAX/2;

int A[maxn];
int32_t main(){
	int n,k;
	cin >> n >> k;
	
	for (int i =0;i<n;i++) cin >> A[i];
	sort(A,A+n);
	
	int ans = 0;
	for (int i =0;i<k;i++) {
		ans += A[i];
	}
	cout << ans;
}









Measured memory_bytes: 3556
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define _GLIBCXX_DEBUG
#define all(x) x.begin(), x.end()
using namespace std;
typedef long long ll;
typedef pair<int, int> pair;
const int inf = 1000000000; //10^9
const ll inff = 1000000000000000000; //10^18

int main(){
    string s;
    cin >> s;
    ll ans = 0;
    int n = s.size();
    rep(bit, (1<<(n-1))){
        ll tmp=0;
        rep(i, n-1){
            tmp *= 10;
            tmp += s[i] - '0';
            if (bit & (1<<i)) {
                ans += tmp;
                tmp = 0;
            }
        }
        tmp *= 10;
        tmp += s.back() - '0';
        ans += tmp;
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 3608
from typing import List


def g(elements: List[int], l: int, m: int, r: int) -> None:
    global inversion_num
    sentinel = 1000000000
    L, R = elements[l:m] + [sentinel], elements[m:r] + [sentinel]
    i = j = 0
    for k in range(l, r):
        if L[i] < R[j]:
            elements[k] = L[i]
            i += 1
            inversion_num += j
        else:
            elements[k] = R[j]
            j += 1


def s(elements: List[int], l: int, r: int) -> None:
    if l + 1 < r:
        m = (l + r) // 2
        s(elements, l, m)
        s(elements, m, r)
        g(elements, l, m, r)
    else:
        return


if __name__ == "__main__":
    n = int(input())
    elements = list(map(lambda x: int(x), input().split()))
    inversion_num = 0

    s(elements, 0, n)

    print(f"{inversion_num}")



Measured memory_bytes: 29848
#include <cstdio>
#include <cstring>

const int N = 1e5 + 1;

char s[N];

int main() {
    scanf("%s", s);
    int i = 0;
    for (; s[2 * i] != '\0'; ++i) {
        s[i] = s[2 * i];
    }
    s[i] = '\0';
    printf("%s\n", s);
    return 0;
}


Measured memory_bytes: 256
/**
 * Dont raise your voice, improve your argument.
 * --Desmond Tutu
 */

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

const bool ready = []() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(12);
    return true;
}();

const double PI = acos(-1);
using ll= long long;
#define int ll
#define all(v) (v).begin(), (v).end()
#define fori(n) for(int i=0; i<int(n); i++)

#define cini(i) int i; cin>>i;
#define cins(s) string s; cin>>s;
#define cind(d) double d; cin>>d;
#define cinai(a,n) vi a(n); fori(n) { cin>>a[i]; }
#define cinas(s,n) vs s(n); fori(n) { cin>>s[i]; }
#define cinad(a,n) vd a(n); fori(n) { cin>>a[i]; }

using pii= pair<int, int>;
using pdd= pair<double, double>;
using vd= vector<double>;
using vb= vector<bool>;
using vi= vector<int>;
using vvi= vector<vi>;
using vs= vector<string>;


/* see https://cp-algorithms.com/data_structures/sqrt_decomposition.html#toc-tgt-4
 * Queries are inclusive l and inclusive r.
 **/

//const int BLOCK_SIZE=(int)sqrt(5e5+5)+1;
const int BLOCK_SIZE=512;

bool mo_cmp(int pfirst, int psecond, int qfirst, int qsecond) {
    if (pfirst / BLOCK_SIZE != qfirst / BLOCK_SIZE)
        return pfirst < qfirst || (pfirst==qfirst && psecond<qsecond);
    return ((pfirst / BLOCK_SIZE) & 1) ? (psecond < qsecond) : (psecond > qsecond);
}

struct Query {
    int l, r, idx;

    bool operator<(Query other) const {
        return mo_cmp(l, r, other.l, other.r);
    }
};

const int N=5e5+5;
int gans=0;
vi f(N);
vi a(N);

inline void moremove(int idx) {
    if(--f[a[idx]]==0)
        gans--;
}

inline void moadd(int idx) {
    if(++f[a[idx]]==1)
        gans++;
}

inline int moget_answer() {
    return gans;
}

vector<int> mo(vector<Query>& queries) {
    vector<int> answers(queries.size());
    sort(queries.begin(), queries.end());
    int cur_l = 0;
    int cur_r = -1;

    /* invariant: data structure will always reflect the range [cur_l, cur_r] */
    for (Query &q : queries) {
        while (cur_l > q.l) {
            cur_l--;
            moadd(cur_l);
        }
        while (cur_r < q.r) {
            cur_r++;
            moadd(cur_r);
        }
        while (cur_l < q.l) {
            moremove(cur_l);
            cur_l++;
        }
        while (cur_r > q.r) {
            moremove(cur_r);
            cur_r--;
        }
        answers[q.idx] = moget_answer();
    }
    return answers;
}

/* example impl of the three functions
 * for finding number of numbers in
 * interval where freq==number */


void solve() {
    cini(n);
    cini(q);
    for(int i=0; i<n; i++)
        cin>>a[i];

    vector<Query> que(q);
    for(int i=0; i<q; i++) {
        cin>>que[i].l>>que[i].r;
        que[i].l--;
        que[i].r--;
        que[i].idx=i;
    }

    vi ans=mo(que);

    for(int i=0; i<q; i++) {
        cout<<ans[i]<<"\n";
    }
}

signed main() {
    solve();
}



Measured memory_bytes: 27252
using System;

class Country_Road
{
    static void Main(string[] args)
    {
        int t = int.Parse(Console.ReadLine()); //t???????????????
        
        for(int i = 0; i<t; i++)
        {
            int n, k;
            string[] str = Console.ReadLine().Split(' '); //n??¨k???????????????
            n = int.Parse(str[0]);
            k = int.Parse(str[1]);

            int[] house = new int[n];
            str = Console.ReadLine().Split(' '); //??¶?????§?¨??????????????????§???????????????
            for(int j = 0; j < n; j++)
            {
                house[j] = int.Parse(str[j]); //??????????????£???
            }

            if (k >= n)
            {
                Console.WriteLine("0"); // ??????????????¶??????????????¨???????????????????????????
                continue;
            }

            /*?????????????????????1??°??????????????????????????????1???????????¶??????n???????????¶?????§???????????????
             * ?¬?????????????????????¨????¢?????????¨????????????????????????
             * ????????¨????????¶?????¨????????????1??°???????????¶????????????????????¨
             * 1~2,2~3,,,,,,n-1~n???????????¶???n-1?????????????????????
             * ????????????????????????????????????????????????
             * ??????????????°???????????§???????????°1??°??????????????????????????¶?????¨????????????????????????
             * n-1?????????????????????2?????\???????????????????????????????????????????????°????????????2?????§????¶??????????????????§?????????
             * 
             * ??¨????????§??????1?????????????????????????????????????????§???????????????????????¨???????????????????????????n-1??????????????????
             * ????????????????????§???????????¨????????????
             * (???????????°???????????????????????????????????????)
             */

            int[] distance = new int[n - 1]; //?????¢?????????????????????
            for(int l = 0; l < n - 1; l++)
            {
                distance[l] = house[l + 1] - house[l];
            }

            Array.Sort(distance); //??????distance???sort

            /*????????????k??????????????§(distance???????????????????´????????¨?)-(distance?????§????????????1????????????k???????????§??????)
             * ????±???????
             */

            int sum = 0;
            for (int m = 0; m < n-k; m++)
            {
                sum += distance[m]; //??????????±??????????
            }
            Console.WriteLine(sum); //??????


        }
    }
}

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

int cnt[100001];
int main(void)
{
	cin.tie(0);
	ios::sync_with_stdio(false);

	string s;
	int n,q,l,r;

	cin >> n >> q;
	cin >> s;

	memset(cnt,0,sizeof(cnt));
	for(int i=2;i<=n;i++)
	{
		if(s[i-2]=='A' && s[i-1]=='C')
		{
			cnt[i] = cnt[i-1] + 1;
		}
		else
		{
			cnt[i] = cnt[i-1];
		}
	}

	for(int i=0;i<q;i++)
	{
		cin >> l >> r;
		cout << cnt[r] - cnt[l] << '\n';
	}

	return 0;
}

Measured memory_bytes: 1488
#include<bits/stdc++.h>
using namespace std;
long long a,b,c,d,e,f[500009];
string s;
int main(){
    ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>s;
    if(s.size()%2==1){
        cout<<"No";
        return 0;
    }
    for(b=0; b<s.size(); b+=2){
        if(s[b]=='h'&&s[b+1]=='i'){
            
        }else{
            cout<<"No";
            return 0;
        }
    }
    cout<<"Yes";
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
 
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 (a>b) { a=b; return 1; } return 0; }
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)

int main(){
    int n,z,w;
    cin>>n>>z>>w;
    int a[n];
    rep(i,n)cin>>a[i];
    if(n==1)cout<<abs(w-a[n-1])<<endl;
    else if(abs(w-a[n-1])>abs(a[n-2]-a[n-1]))cout<<abs(w-a[n-1])<<endl;
    else cout<<abs(a[n-2]-a[n-1])<<endl;
}


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

using namespace std;

typedef long long int64;

const int MAXN = 300;
const int64 INF = (1ll << 63) - 1;

vector <vector <pair <int64, int64> > > g;

vector <vector <int64> > d;

void dijkstra(int s, vector <int64> & dist){
    int n = g.size();
    dist.resize(n, INF);
    set <pair <int64, int>> v;
    for (int i = 0; i < n; i++)
        dist[i] = INF;
    dist[s] = 0;
    for (int i = 0; i < n; i++){
        v.insert({dist[i], i});
    }
    while(!v.empty()){
        auto it = v.begin();
        int cur_v = it->second;
        int64 cur_v_w = it->first;
        for (int i = 0; i < g[cur_v].size(); i++){
            int nw = g[cur_v][i].first;
            int64 e = g[cur_v][i].second;
            int64 nw_w = cur_v_w + e;
            int64 o_w = dist[nw];
            if (o_w > nw_w){
                v.erase({o_w, nw});
                v.insert({nw_w, nw});
                dist[nw] = nw_w;
            }
        }
        v.erase(v.begin());
    }
}
int main()
{
    #ifdef HOME
    freopen("input.txt", "rt", stdin);
    #endif // HOME
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, m, r;
    cin >> n >> m >> r;
    g.resize(n);
    d.resize(n, vector <int64> (n));
    vector <int> p(r);
    for (int i = 0; i < r; i++){
        cin >> p[i];
        p[i]--;
    }
    for (int i = 0; i < m; i++){
        int a, b;
        int64 c;
        cin >> a >> b >> c;
        a--;
        b--;
        g[a].push_back({b, c});
        g[b].push_back({a, c});
    }
    for (int i = 0; i < n; i++){
        dijkstra(i, d[i]);
    }/*
    for (int i = 0; i < n; i++){
        for (int j = 0; j < n; j++)
            cout << d[i][j] << ' ';
        cout << endl;
    }*/
    int fact = 1;
    for (int i = 2; i <= r; i++)
        fact *= i;
    long long ans = INF;
    for (int i = 0; i < fact; i++){
        long long cur = 0;
        for (int j = 0; j < r - 1; j++){
            cur += d[p[j]][p[j + 1]];
        }
        ans = min(ans, cur);
        next_permutation(p.begin(), p.end());
    }
    cout << ans;
    return 0;
}


Measured memory_bytes: 1536
#[allow(unused_macros)]
macro_rules! input {
    ( source = $ s : expr , $ ( $ r : tt ) * ) => { let mut iter = $ s . split_whitespace ( ) ; let mut next = || { iter . next ( ) . unwrap ( ) } ; input_inner ! { next , $ ( $ r ) * } };
    ( $ ( $ r : tt ) * ) => { let stdin = std :: io :: stdin ( ) ; let mut bytes = std :: io :: Read :: bytes ( std :: io :: BufReader :: new ( stdin . lock ( ) ) ) ; let mut next = move || -> String { bytes . by_ref ( ) . map ( | r | r . unwrap ( ) as char ) . skip_while ( | c | c . is_whitespace ( ) ) . take_while ( | c |! c . is_whitespace ( ) ) . collect ( ) } ; input_inner ! { next , $ ( $ r ) * } };
}
#[allow(unused_macros)]
macro_rules! input_inner {
    ( $ next : expr ) => { };
    ( $ next : expr , ) => { };
    ( $ next : expr , $ var : ident : $ t : tt $ ( $ r : tt ) * ) => { let $ var = read_value ! ( $ next , $ t ) ; input_inner ! { $ next $ ( $ r ) * } };
}
#[allow(unused_macros)]
macro_rules! read_value {
    ( $ next : expr , ( $ ( $ t : tt ) ,* ) ) => { ( $ ( read_value ! ( $ next , $ t ) ) ,* ) };
    ( $ next : expr , [ $ t : tt ; $ len : expr ] ) => { ( 0 ..$ len ) . map ( | _ | read_value ! ( $ next , $ t ) ) . collect ::< Vec < _ >> ( ) };
    ( $ next : expr , chars ) => { read_value ! ( $ next , String ) . chars ( ) . collect ::< Vec < char >> ( ) };
    ( $ next : expr , usize1 ) => { read_value ! ( $ next , usize ) - 1 };
    ( $ next : expr , $ t : ty ) => { $ next ( ) . parse ::<$ t > ( ) . expect ( "Parse error" ) };
}

#[allow(unused_macros)]
macro_rules! vec_md {
    ( $ init : expr ; $ ( $ dim : expr ) ;* ) => { vec_md ! ( $ ( $ dim ) ;* => $ init ) };
    ( $ head : expr ; $ ( $ tail : expr ) ;* => $ init : expr ) => { vec ! [ vec_md ! ( $ ( $ tail ) ;* => $ init ) ; $ head ] };
    ( $ head : expr => $ init : expr ) => { vec ! [ $ init ; $ head ] };
}

#[allow(dead_code)]
pub const M: u64 = 1_000_000_007;

fn main() {
    input! {
        n: usize,
        xy: [(usize1, usize1); n-1]
    }

    let mut g = vec![vec![];n];
    for i in 0..n-1 {
        let (x, y) = xy[i];
        g[x].push(y);
        g[y].push(x);
    }

    let mut dp = vec_md![0u64;n;2];
    rec(&g,&mut dp,0,None);
    println!("{}", (dp[0][0] + dp[0][1]) % M);
}

fn rec(g: &[Vec<usize>], dp: &mut [Vec<u64>], cur: usize, pre: Option<usize>) {
    dp[cur][0] = 1;
    dp[cur][1] = 1;
    for &v in &g[cur] {
        if pre.map(|src| src != v).unwrap_or(true) {
            rec(g,dp,v,Some(cur));
            dp[cur][0] *= dp[v][0] + dp[v][1];
            dp[cur][1] *= dp[v][0];
            dp[cur][0] %= M;
            dp[cur][1] %= M;
        }
    }
}

Measured memory_bytes: 31100
// AOJ 2449: Connect
// 2018.2.2 bal4u

#include <stdio.h>
#include <string.h>

char s[129][20]; int w[129];
int dp[2][65536], bc[65536];

int bitcount16(int x)
{
	x = ((x & 0xAAAAAA) >>  1) + (x & 0x555555);
	x = ((x & 0xCCCCCC) >>  2) + (x & 0x333333);
	x = ((x & 0xF0F0F0) >>  4) + (x & 0x0F0F0F);
	x = ((x & 0x00FF00) >>  8) + (x & 0xFF00FF);
	return x;
}

int main()
{
	int R, C, r, c, i, k, k1, k2, lim, p, q, x, ans;
	char buf[10], *t;

	fgets(buf, 10, stdin), sscanf(buf, "%d%d", &R, &C);
	for (r = 0; r < R; r++) {
		fgets(t=s[r], 20, stdin);
		while (*t > ' ') t++;
		w[r] = t - s[r];
	}
	lim = 1 << C;
	for (i = 0; i < lim; i++) bc[i] = bitcount16(i);
	
	memset(dp, -1, sizeof(dp));
	dp[0][0] = 0;
	
	k1 = 0, k2 = 1;
	for (r = 0; r < R; r++) for (c = 0; c < C; c++) {
		memset(dp[k2], -1, sizeof(dp[k2]));
		for (k = 0; k < lim; k++) if (dp[k1][k] >= 0) {
			p = bc[k & (1 << c) - 1];
			if (p < w[r]) {
				q = dp[k1][k];
				if (c && (k & (1 << (c-1))) && s[r][p-1] == s[r][p]) q++;
				if (r && (k & (1 << c))     && s[r][p  ] == s[r-1][w[r-1] - bc[k>>c]]) q++;
				x = k | (1 << c);
				if (q > dp[k2][x]) dp[k2][x] = q;
			}
			if (p + C - c > w[r]) {
				x = k & ~(1 << c);
				if (dp[k1][k] > dp[k2][x]) dp[k2][x] = dp[k1][k];
			}
		}
		k1 = k2, k2 = !k2;
	}

	ans = 0;
	for (c = 0; c < lim; c++) if (dp[k1][c] > ans) ans = dp[k1][c];
	printf("%d\n", ans << 1);
	return 0;
}


Measured memory_bytes: 2568
//2017-7-28 21:13
//2017-7-28 21:38
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdlib>
#include<queue>
using namespace std;
typedef long long LL;
const int MaxN = 1e5;
 
struct node{
	LL a, b, c;
	bool operator <(const node &A) const{
		return (a-b) < A.a - A.b;
	}
}box[MaxN + 5];
 
int n, x, y, z;
LL tot, ans;
priority_queue<LL, vector<LL>, greater<LL> > q;
LL lef[MaxN + 5];
 
int main(){
	scanf("%d %d %d", &x, &y, &z);
	n = x + y + z;
	for(int i = 1; i <= n; i++){
		scanf("%lld %lld %lld", &box[i].a, &box[i].b, &box[i].c);
		tot += box[i].c;
	}
	sort(box + 1, box + 1 + n);
	LL ans = 0, sum = 0;
	for(int i = 1; i <= y; i++){
		sum += box[i].b - box[i].c;
		q.push(box[i].b - box[i].c);
	}
	for(int i = y + 1; i <= n - x + 1; i++){
		lef[i] = sum;
		sum += box[i].b - box[i].c;
		q.push(box[i].b - box[i].c);
		sum -= q.top();
		q.pop();
	}
	while(!q.empty()) q.pop(); sum = 0;
	for(int i = n; i > n - x; i--){
		sum += box[i].a - box[i].c;
		q.push(box[i].a - box[i].c);
	}
	for(int i = n - x; i >= y; i--){
		ans = max(ans, tot + lef[i + 1] + sum);
		sum += box[i].a - box[i].c;
		q.push(box[i].a - box[i].c);
		sum -= q.top();
		q.pop();
	}
	printf("%lld\n", ans);
	return 0;
}

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

#define rep(i,n) for(ll i=0;i<(n);++i)
using ll = long long;
using pll = pair<ll,ll>;
constexpr ll INF = (1LL<<60);
constexpr ll MOD = (1e9+7);
//constexpr ll MOD = (998244353);
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(a>b){a=b;return 1;}return 0;}
void dump(){cout<<endl;}
template<class T,class... Ts> void dump(T&& h, Ts&&... t){cout<<h<<", ";dump(forward<Ts>(t)...);}
template<class T> istream &operator>>(istream&is,vector<T>&v){for(auto &elemnt:v)is>>elemnt;return is;}
template<class T,class U> istream &operator>>(istream&is,pair<T,U>&p){is>>p.first>>p.second;return is;}
template<class T>vector<T> make_vector(size_t a){return vector<T>(a);}
template<class T, class... Ts>auto make_vector(size_t a, Ts... ts){return vector<decltype(make_vector<T>(ts...))>(a, make_vector<T>(ts...));}

void solve1();void solve2();
int main(){
  solve1();
  return 0;
}

struct doubling{
  ll n,log_n;
  vector<vector<ll>> table;
  doubling(){}
  doubling(vector<ll>const& a,ll l){
    n = a.size();
    log_n = floor(log2(n));
    table = vector<vector<ll>>(log_n,vector<ll>(n,-1));

    rep(i,n){
      ll key = a[i]+l;
      auto itr = upper_bound(a.begin(),a.end(),key);
      itr--;
      ll idx = itr-a.begin();
      table[0][i] = idx;
    }
    for(ll i=1;i<log_n;++i){
      for(ll j=0;j<n;++j){
        //if(a[j]<((1LL<<i)*l))table[i][j]=-1;
        table[i][j] = table[i-1][table[i-1][j]];
      }
    }
  }
  void dump(){
    for(auto y:table){
      for(auto x:y)cout<<x<<" ";
      cout<<endl;
    }
  }
  ll search(ll j,ll val){
    ll low=0,high=log_n;
    while(high-low>1){
      ll mid = (high+low)>>1;
      if(table[mid][j]<val)low=mid;
      else high=mid;
    }
    return low;
  }
  ll calc(ll a,ll b){
    if(a>b)swap(a,b);
    ll res = 0;
    while(a<b){
      ll k = search(a,b);
      res += (1LL<<k);
      a = table[k][a];
    }
    return res;
  }
};

void solve1(){

  ll n;
  cin>>n;
  vector<ll> a(n);
  cin>>a;
  ll l,q;
  cin>>l>>q;
  vector<pll>ab(q);
  cin>>ab;

  doubling d(a,l);
  //d.dump();
  for(auto& x:ab){
    ll a,b;tie(a,b)=x;
    a--;b--;
    ll res = d.calc(a,b);
    cout<<(res)<<endl;
  }

}

Measured memory_bytes: 15872
import bisect

N = int(input())
L = sorted(map(int, input().split()))

counter = 0

for i in range(N):
    a = L[i]
    for j in range(i+1, N):
        b = L[j]
        k = bisect.bisect_left(L, a + b)
        counter += max(0, k - (j + 1))

print(counter)

Measured memory_bytes: 3188
class Game
  def initialize
    @out = 0
    @point = 0
    @runner = 0
  end

  def out
    @out += 1
  end

  def hit
    if @runner == 3
      @point += 1
    else
      @runner += 1
    end
  end

  def homerun
    @point += @runner + 1
    @runner = 0
  end

  def continue?
    @out != 3
  end

  def score
    return @point
  end
  
end

def main
  gets.to_i.times do
    game = Game.new
    while game.continue?
      game.send(gets.downcase.chomp)
    end
    puts game.score
  end
end
main

Measured memory_bytes: 6096
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <math.h>
#include <vector>
#include <map>
#include <queue>
#include <utility>
#include <algorithm>
#include <string>
#include <set>
#include <random>
using namespace std;
int main() {
  int N;
  cin >> N;
  if (N == 0) {
	  cout << 0 << endl;
	  return 0;
	}
  string ans = "";
  while (N != 0) {
	  if (N % 2 != 0) {
		  N--;
		  ans = '1' + ans;
		} else {
		  ans = '0' + ans;
		}
	  N /= -2;
	}
  cout << ans << endl;
  return 0;
}


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

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

    sort(x, x+n);

    int L = n / 2;
    int mx1 = x[L-1];
    int mx2 = x[L];
    double mx = (mx1+mx2) / 2.0;
    for(int i = 0; i < n; i++)
    {
        if(double(xsub[i]) <= mx) cout << mx2 << endl;
        else if(double(xsub[i]) > mx) cout << mx1 << endl;
    }

    return 0;
}


Measured memory_bytes: 3712
import math
import collections
import itertools
import sys
import bisect
from heapq import heappop,heappush,heapify
sys.setrecursionlimit(10**6)
def MAP(): return list(map(int,input().split()))
def INT(): return int(input())
def FLOAT(): return float(input())
MOD = 10**9+7

a,b,x = MAP()

res = (2*x)/(a*b)
if res<=a:
    print(math.degrees(math.atan(b/res)))
else:
    tmp = b - ((b/a)*(res-a))
    print(math.degrees(math.atan(tmp/a)))

Measured memory_bytes: 3316
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define MOD(int)(1e9+7)

int foo(int a, int b, int c, int d){//cout<<a<<" "<<b<<" "<<c<<" "<<endl;
  vector<int> temp;
  temp.push_back(a);
  temp.push_back(b);
  temp.push_back(c);
  temp.push_back(d);
  sort(temp.begin(), temp.end());
  return (temp[1] - temp[0])* (temp[1] - temp[0])+(temp[2] - temp[1])* (temp[2] - temp[1]) + (temp[3] - temp[2])* (temp[3] - temp[2]);
}

signed main(){
  int a, b;

  while(true){
    int ans = 123456789123456;
    cin>>a>>b;

    if(!a&&!b) break;
    for(int i = 1; i * i <= a; i++){
      if(a%i)continue;
      for(int j = 1; j * j <= b; j++){
	if(b%j)continue;
	ans = min(ans, foo(i,j,a/i,b/j));
      }
    }
    cout<<ans<<endl;
  }

  return 0;
}



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

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

#define MAX 100005
#define INF INT_MAX

typedef long long ll;
typedef pair<int, int> P;

enum Kind
{
    ROOT,
    INT_NODE,
    LEAF
};

class Node
{
public:
    int id;
    int parent;
    int left;
    int right;
    int sibling;
    int degree;
    int depth;
    int height;
    Kind kind;
    Node(int id) {
        this->id = id;
        parent = -1;
        sibling = -1;
        degree = 0;
        depth = 0;
        height = 0;
        kind = ROOT;
    }
};

void dfs(int v, int p, vector<Node>& nodes)
{
    int l = nodes[v].left;
    int r = nodes[v].right;
    int h = 0;

    if (l != -1) {
        nodes[l].depth = nodes[v].depth + 1;
        dfs(l, v, nodes);
        h = max(h, nodes[l].height+1);
    }
    if (r != -1) {
        nodes[r].depth = nodes[v].depth + 1;
        dfs(r, v, nodes);
        h = max(h, nodes[r].height+1);
    }
    nodes[v].height = h;

    Kind k = INT_NODE;
    if (p == -1) k = ROOT;
    else if (r == -1 && l == -1) k = LEAF;
    nodes[v].kind = k;
}

int main(int, char**)
{
    int n;
    cin >> n;

    vector<Node> nodes;
    rep(i,n) nodes.push_back(Node(i));
    rep(i,n) {
        int id, left, right;
        cin >> id >> left >> right;
        nodes[id].left = left;
        nodes[id].right = right;
        if (left != -1) {
            nodes[left].parent = id;
            nodes[id].degree++;
            if (right != -1) nodes[left].sibling = right;
        }
        if (right != -1) {
            nodes[right].parent = id;
            nodes[id].degree++;
            if (left != -1) nodes[right].sibling = left;
        }
    }
    auto itr = find_if(nodes.begin(), nodes.end(), [] (Node& nd) { return nd.parent == -1; } );
    int root = distance(nodes.begin(), itr);
    dfs(root, -1, nodes);

    rep(i,n) {
        Node nd = nodes[i];
        cout << "node " << i << ": ";
        cout << "parent = " << nd.parent << ", ";
        cout << "sibling = " << nd.sibling << ", ";
        cout << "degree = " << nd.degree << ", ";
        cout << "depth = " << nd.depth << ", ";
        cout << "height = " << nd.height << ", ";
        
        if (nd.kind == ROOT) cout << "root";
        else if (nd.kind == LEAF) cout << "leaf";
        else cout << "internal node";
        cout << endl;
    }

    return 0;
}


Measured memory_bytes: 3100
from itertools import *
N,C = map(int,input().split())
D = [list(map(int,input().split())) for c in range(C)]
G = [list(map(int,input().split())) for n in range(N)]
H = [C*[0] for n in range(3)]

for i in range(N):
  for j,k in enumerate(G[i]):
    H[(i+j)%3][k-1]+=1

ans = float("inf")

for i in permutations(range(C),3):
  c = 0
  for j in range(3):
    for k in range(C):
      c+=D[k][i[j]]*H[j][k]
  ans = min(ans,c)

print(ans)

Measured memory_bytes: 11772
#include <bits/stdc++.h>
#define INF (1<<30)
#define MOD 1000000007
#define l_ength size
using ll = long long;
using namespace std;

int main(){
	ll n, k;
	cin >> n >> k;
	/*
	mod k で考えると，a+b ≡ b+c ≡ c+a より a ≡ b ≡ c
	かつ a+b ≡ b+c ≡ c+a ≡ 0 だから，条件を満たす組は
	(a, b, c) ≡ (0, 0, 0)
	また，k が偶数でかつ x ≡ k/2 となるような x が n 以下に存在する場合 (k/2, k/2, k/2) も候補に入る．
	以上より，n 以下で k の倍数である整数の個数 と，
	(k が偶数なら) n 以下で k/2 の倍数である整数の個数をカウントすればよい．
	*/
	ll a = n/k;
	ll b = 0;
	if( k % 2 == 0 && k/2 <= n ) b = ( n - k/2 ) / k + 1;
	cout << a*a*a + b*b*b << endl; 
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const int N=300005,M=1e9+7;
char s[N];
int t[8][2],f[N][8];
int main(){
	t[0][0]=2;t[0][1]=1;t[1][0]=3;t[1][1]=5;
	t[2][0]=4;t[2][1]=7;t[3][0]=6;t[3][1]=1;
	t[4][0]=2;t[4][1]=2;t[5][0]=5;t[5][1]=5;
	t[6][0]=3;t[6][1]=3;t[7][0]=2;t[7][1]=1;
	scanf("%s",s);
	int n=strlen(s);
	f[n][1]=1;
	f[n][5]=1;
	for (int i=n-1;i>=0;i--)
		for (int j=0;j<8;j++){
			if (s[i]!='1')f[i][j]+=f[i+1][t[j][0]];
			if (s[i]!='0')f[i][j]+=f[i+1][t[j][1]];
			f[i][j]%=M;
		}
	printf("%d\n",f[0][0]);
}

Measured memory_bytes: 9856
# coding: utf-8


def main():
    n, t = map(int, input().split())
    clist = []
    for _ in range(n):
        c, tt = map(int, input().split())
        if tt <= t:
            clist.append(c)

    if not clist:
        print('TLE')
    else:
        print(min(clist))


if __name__ == '__main__':
    main()


Measured memory_bytes: 2940
n = gets.to_i

points = [[0,0,0]]

n.times do
    points << gets.split("\s").map(&:to_i)
end

able = true

1.upto(n) do |i|
    t = points[i][0]
    x = points[i][1]
    y = points[i][2]
    
    prev_t = points[i-1][0]
    prev_x = points[i-1][1]
    prev_y = points[i-1][2]
    
    d = (prev_x - x).abs + (prev_y - y).abs
    t = t - prev_t

    a = t-d

    unless( t-d>=0 && (t-d)%2==0 )
        able = false
        break
    end
end

puts able ? 'Yes' : 'No'


Measured memory_bytes: 11516
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args)throws Exception {
        BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tokenizer = new StringTokenizer(input.readLine());
        int a = Integer.parseInt(tokenizer.nextToken());
        int b = Integer.parseInt(tokenizer.nextToken());
        String word = input.readLine();
        int size = 0;
        boolean correct = true;
        boolean foundMinuse = false;
        for (int i = 0; i < word.length(); i++) {
            if (Character.isDigit(word.charAt(i))){
                size++;
            }else{
                if (size != a){
                    correct = false;
                    break;
                }
                size = 0;
                foundMinuse = true;
            }
        }

        if (foundMinuse && size == b){
            System.out.println("Yes");
        }else {
            System.out.println("No");
        }
    }
}


Measured memory_bytes: 23124
#include<bits/stdc++.h>
#define MAX 1000000
using namespace std;
int n;
string s;
int go(int stone,int prevcolor)
{
	if(stone==n)
		return 0;
	int a = INT_MAX;
	if(prevcolor)
		a = (s[stone]=='W'?1:0)+go(stone+1,1);
	return min(a,(s[stone]=='W'?0:1)+go(stone+1,0));
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);	
	cin>>n>>s;
	//cout<<min(go(0,0),go(0,1));
	int r = 0;
	for(int i=0;i<n;++i)
		if(s[i]=='R')
			r++;
	int ans = 0;
	for(int i=0;i<n;++i)
		if(s[i]=='R'&&i>r-1)
			ans++;
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 3736
# input
n = gets.chomp.to_i
v = gets.chomp.split.map(&:to_i)
c = gets.chomp.split.map(&:to_i)

# main
n.times do |i|
  v[i] -= c[i]
end

ans = 0
n.times do |i|
  if v[i] >= 0 then
    ans += v[i]
  end
end

# output
puts ans


Measured memory_bytes: 1916
#include <bits/stdc++.h>
using namespace std;
int  la(int n){
int s=0;
while(n){
    int t=n%10;
    s=s*10+t;
    n/=10;
}
return s;
}
int main()
{
    int n;
    cin>>n;
    printf("%s\n",n==la(n)?"Yes":"No");
    return 0;
}



Measured memory_bytes: 256
n,a,b=map(int,input().split())
if (a-b)%2==0:
    print(abs(a-b)//2)
else:
    ans0=min(a,b)+abs(a-b)//2
    ans1=n-max(a,b)+1+abs(a-b)//2
    print(min(ans0,ans1))


Measured memory_bytes: 2940
from collections import Counter
n = int(input())
v = list(map(int,input().split()))
o = Counter(v[::2]).most_common()
o.append((0,0))
e = Counter(v[1::2]).most_common()
e.append((0,0))
if o[0][0] == e[0][0]:
    ans = min(n - o[0][1] - e[1][1], n - o[1][1] - e[0][1])
else:
    ans = n - o[0][1] - e[0][1]
print(ans)

Measured memory_bytes: 20572
N = int(input())
A = [int(x) for x in input().split(' ')]
maxA = max(A)
minA = min(A)

if maxA - minA > 1:
    print('No')
elif maxA == minA:
    if (N >= 2 * maxA) or maxA == N - 1:
        print('Yes')
    else:
        print('No')
else:
    sum = 0
    for i in A:
        if i == minA:
            sum += 1
    if sum >= maxA:
        print('No')
    elif 2 * (maxA - sum) <= N - sum:
        print('Yes')
    else:
        print('No')


Measured memory_bytes: 13964
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  signed long long int a, b, c, k; 

  cin >> a >> b >> c >> k;

  if ( k <= a ){
    cout << k;
  } else if ( k <= a + b ){
    cout << a;
  } else if ( k <= a + b + c ){
    cout << a - ( k - (a + b) );
  }

}


Measured memory_bytes: 3624
import java.io.PrintWriter;
import java.util.*;
import java.util.stream.Collectors;

public class Main {

    private static Scanner in = new Scanner(System.in);
    private static PrintWriter out = new PrintWriter(System.out);

    private static final long MOD = (long) 1e9 + 7;

    public static void main(String[] args) {
        solve();
        out.flush();
    }

    private static void solve() {
        int n = in.nextInt();

        List<Double> v = new ArrayList<>();
        for (int i=0; i < n; i++)
            v.add((double) in.nextInt());

        while (v.size() > 1) {
            v.sort(((o1, o2) -> {
                if (o1 > o2) return 1;
                else if (o1 < o2) return -1;
                return 0;
            }));

            double v1 = v.get(0);
            double v2 = v.get(1);
            v.remove(0);
            v.remove(0);
            v.add((v1 + v2) / 2);
        }

        out.println(v.get(0));
    }

}


Measured memory_bytes: 27092
/*
    author: kartik8800
*/
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define fr(a,b) for(ll i = a; i < b; i++)
#define mod 1000000007
#define all(x) (x).begin(), (x).end()
#define prDouble(x) cout << fixed << setprecision(10) << x 
#define triplet pair<ll,pair<ll,ll>>
#define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL)
using namespace std;

ll dp[3001][3001][2];
ll solve(vector<int>& v, int i, int j, bool turn)
{
    if(i > j)
        return 0;
    
    if(dp[i][j][turn] != -1)
        return dp[i][j][turn];
    
    if(turn == 1)
        return dp[i][j][turn] = max(v[i] + solve(v, i+1,j,0), v[j] + solve(v, i,j-1, 0));
    else return dp[i][j][turn] = min(solve(v, i+1,j,1), solve(v, i,j-1, 1));
}

int main() {
   int n;
   cin >> n ;
   vector<int> v(n+1);
   memset(dp, -1, sizeof dp);
   ll sum = 0;
   for(int i = 1; i <= n; i++)
    {
        cin>>v[i];
        sum += v[i];
    }
   ll scoreX = solve(v, 1, n, 1);
   ll scoreY = (sum - scoreX);
   cout << scoreX - scoreY;
   return 0;
}


Measured memory_bytes: 141184
#include "bits/stdc++.h"
using namespace std;

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

    int n;
    cin >> n;

    vector<int>plus(n),minus(n);

    for(int i=0;i<n;i++){
        int x,y;
        cin >>x >> y;
        plus[i]=x+y;
        minus[i]=x-y;
    }

    sort(plus.begin(),plus.end());
    sort(minus.begin(),minus.end());
    cout<<max(plus[n-1]-plus[0],minus[n-1]-minus[0])<<endl;
}




Measured memory_bytes: 4768