akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int,int>;

int main() {
  string s; cin>>s;
  s[3] = '8';
  cout << s << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#include <math.h>
#include <iomanip>
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const int INF=1001001001;
const int mod=998244353;

int main() {
  int N;
  cin>>N;
  vector<int>a(N);
  map<int,int>k;
  for(int i=0;i<N;i++){
    cin>>a[i];
    k[a[i]]++;
  }
  long long cnt=0;
  for(auto c:k){
    if(c.second<c.first){cnt+=c.second;}
    else{cnt+=c.second-c.first;}
  }
  cout<<cnt<<endl;
  return 0;
}


Measured memory_bytes: 8092
#include <iostream>
//#include <algorithm>
using namespace std;
int main(){
  long int n, k, q, a[100000];
  signed long int p[100000];
  cin >> n >> k >> q;
  for(int i=0; i<q; i++){
      cin >> a[i];
  }
  for(int i=0; i<n; i++){
      p[i]=k;
  }
  k=0;
  for(int i=0; i<q; i++){
    p[a[i]-1]++;
  }
  for(int i=0; i<n; i++){
    p[i] -= q;
    if(p[i]<=0){ cout << "No" << endl;}
    else{ cout << "Yes" << endl;}
  }

    return 0;
}

Measured memory_bytes: 2176
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cassert>
#include <cctype>
#include <vector>
using namespace std;
typedef long long lint;
#define cout cerr
#define ni (next_num<int>())
template<class T>inline T next_num(){
	T i=0;char c;
	while(!isdigit(c=getchar())&&c!='-');
	bool flag=c=='-';
	flag?c=getchar():0;
	while(i=i*10-'0'+c,isdigit(c=getchar()));
	return flag?-i:i;
}
template<class T1,class T2>inline void apmax(T1 &a,const T2 &b){if(a<b)a=b;}
template<class T1,class T2>inline void apmin(T1 &a,const T2 &b){if(b<a)a=b;}
const int N=300010;
namespace B{
	int c[N],n;
	inline void init(int _n){
		memset(c+1,0,(n=_n)<<2);
	}
	inline void add(int x,int v){
		for(;x<=n;c[x]+=v,x+=x&-x);
	}
	inline int sum(int x){
		int ans=0;
		for(;x;ans+=c[x],x^=x&-x);
		return ans;
	}
}
vector<int>fact[N],ev[N];
int ans[N];
int main(){
	int tot=ni,n=ni;
	B::init(n);
	memset(ans,0,sizeof(ans));
	while(tot--){
		int l=ni,r=ni;
		ans[1]++,ans[r-l+2]--;
		ev[l].push_back(r-l+2);
		ev[r+1].push_back(-(r-l+2));
	}
	for(int i=1;i<=n;i++){
		ans[i]+=ans[i-1];
		for(int j=i;j<=n;j+=i){
			fact[j].push_back(i);
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=0,tj=ev[i].size();j<tj;j++){
			if(ev[i][j]>0){
				B::add(ev[i][j],1);
			}else{
				B::add(-ev[i][j],-1);
			}
		}
		for(int j=0,tj=fact[i].size();j<tj;j++){
			ans[fact[i][j]]+=B::sum(fact[i][j]);
		}
	}
	for(int i=1;i<=n;i++){
		printf("%d\n",ans[i]);
	}
	return 0;
}

Measured memory_bytes: 30208
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ll  long long
#define FASTINOUT ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
int main()
{
    FASTINOUT;
    int k;
    string s;
    cin>>k>>s;
    int ls=s.length();
    if (ls<=k)
        cout<<s<<endl;
    else
        cout<<s.substr(0,k)+"...";
    return 0;
}


Measured memory_bytes: 3648
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <algorithm>
#include <cctype>
#include <cmath>
#include <queue>
#include <map>
#include <numeric>
#include <unordered_map>
#include <iomanip>
#include <functional>
#include <bitset>
#include <complex>
#include <stack>



#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define rrep(i, n) for(int i = (int)(n-1); i >= 0; i--)
#define repi(i,a,b) for(int i=int(a);i<int(b);i++)
#define all(x) (x).begin(),(x).end()

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

typedef long long ll;

using namespace std;


int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  vector<ll>a(2),b(2),t(2);
  rep(i,2)cin>>t[i];
  rep(i,2)cin>>a[i];
  rep(i,2)cin>>b[i];
  vector<ll>ta(2),tb(2);
  rep(i,2){
    ta[i]=t[i]*a[i];
    tb[i]=t[i]*b[i];
  }
  if(ta[0]+ta[1]==tb[0]+tb[1]){
    cout<<"infinity"<<endl;
    return 0;
  }
  if(ta[0]+ta[1]<tb[0]+tb[1]){
    swap(ta,tb);
  }
  ll res=0;
  if(tb[0]-ta[0]<0){
    cout<<0<<endl;
    return 0;
  }
  res=(tb[0]-ta[0])/(ta[0]+ta[1]-(tb[0]+tb[1]));
  //cout<<tb[0]-ta[0]<<" "<<(ta[0]+ta[1]-(tb[0]+tb[1]))<<endl;
  res=res*2+1;
  if((tb[0]-ta[0])%(ta[0]+ta[1]-(tb[0]+tb[1]))==0)res--;
  cout<<res<<endl;

  return 0;

}


Measured memory_bytes: 256
fun main(args: Array<String>) {
    val n = readLine()!!.toInt()
    val h = readLine()!!.split(" ").map(String::toLong)

    var count = 0
    var maxCount = 0

    for (i in 1 until h.size) {
        if (h[i - 1] >= h[i]) {
            count += 1
        } else {
            if(maxCount < count) maxCount = count
            count = 0
        }
    }

  	if(maxCount < count) maxCount = count

    println(maxCount)
}

Measured memory_bytes: 61856
def combi(x):
    return x * (x-1) //2

n = int(input())
a = list(map(int,input().split()))

#print(a)    #思い出すときに使おう　動きが分かるよ

for i in range(len(a)):
    a[i] -= 1

#print(a)

cnt = [0] * n

for i in range(len(a)):
    cnt[a[i]] += 1

#print(cnt)

total = 0

for i in cnt:
    total += combi(i)

for i in range(n):
    ans = total
    ans -= combi(cnt[a[i]])
    ans += combi(cnt[a[i]]-1)
    print(ans)

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

#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define lg long long
#define db double
#define lb(x) ((x)&-(x))
#define ft first
#define sd second

#define HII cerr<<"HI"<<endl
#define LLLINE cerr<<"@@@@@@@@@@@@@@@@@@@@"<<endl

template <class _T_>
void read(_T_& d){
	d=0;int f=1;char c=getchar();
	for(;c<'0'||c>'9';c=getchar())if(c=='-')f*=-1;
	for(;c>='0'&&c<='9';c=getchar())d=d*10+c-'0';
	d*=f;
}

/************************************************/
#define MN 500005
int a[MN];
int n;
bool Ass(int x){
//	cerr<<x<<endl;
//	LLLINE;
	static int zro[MN],v[MN];int tk=0;
	for(int i=2;i<=n;++i){
		if(a[i]<=a[i-1]){
			int gg=a[i];
			F:
			if(!gg)return 0;
			while(zro[tk]>gg)--tk;
			//cerr<<gg<<' '<<i<<' '<<zro[tk]<<' '<<v[tk]<<' '<<tk<<endl;
			if(zro[tk]==gg){
				if(v[tk]==x){--tk,--gg;goto F;}else ++v[tk];
			}else zro[++tk]=gg,v[tk]=2;
		}
	}return 1;
}
int main(){
	read(n);
	for(int i=1;i<=n;++i)read(a[i]);
	for(int i=1;i<=n;++i){
		if(a[i]<=a[i-1])goto A;
	}
	return puts("1"),0;
	A:
	int L=2,R=n;
	while(L<R){
		int mid=L+R>>1;
		if(Ass(mid))R=mid;else L=mid+1;
	}
	cout<<L<<endl;
	return 0;
}


Measured memory_bytes: 3072
using System;

namespace AtCoder.Abc
{
    class QuestionB
    {
        public static void Main(string[] args)
        {
            var sw = new System.IO.StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
            Console.SetOut(sw);

            var sp = Console.ReadLine().Split(' ');
            var x = int.Parse(sp[0]);
            var d = int.Parse(sp[1]);
            var ds = (long)d * (long)d;
            int cnt = 0;

            for (int i = 0; i < x; i++)
            {
                sp = Console.ReadLine().Split(' ');
                var xi = long.Parse(sp[0]);
                var yi = long.Parse(sp[1]);
                if (ds >= (xi*xi+yi*yi))
                {
                    cnt++;
                }
            }
            Console.WriteLine(cnt);

            Console.Out.Flush();
        }
    }
}


Measured memory_bytes: 40548
#include <iostream>
#include <stdio.h>  //printf

using namespace std;

#define N_MAX 100000
#define NIL -1

struct Node{int p, l, r;};

Node T[N_MAX];

int main()
{
    int n, i, j, v, d, x, y;
    cin >> n;

    //??¨????????????
    for (i = 0; i < N_MAX; i++) {
        T[i].p = -1;
        T[i].r = T[i].l = NIL;
    }

    //??¨?????\???
    for (i = 0; i < n; i++) {
         cin >> v >> d; // value, degree

             for (j = 0; j < d; j++) {
                 cin >> x;
                 if (j == 0) {
                     T[v].l = x;
                     T[x].p = v;
                 } else {
                     T[y].r = x;
                     T[x].p = v;
                 }
                 y = x;
             }

    }

    //??¨?????????
    for (i = 0; i < n; i++) {
        v = i;
        j = 0;
        while (T[v]. p != -1) {
            v = T[v].p;
            j++;
        }
        printf("node %d: parent = %d, depth = %d, ", i, T[i].p, j);

        if (T[i].p == -1) {
            printf("root, ");
        } else if (T[i].l == NIL) {
            printf("leaf, ");
        } else {
            printf("internal node, ");
        }

        printf("[");
        if (T[i].l == NIL) {
            printf("]\n");
            continue;
        } else {
            printf("%d", T[i].l);
            v = T[i].l;
        }

        while (T[v].r != NIL) {
            printf(", %d", T[v].r);
            v = T[v].r;
        }
        printf("]\n");
    }

    return 0;
}

Measured memory_bytes: 4368
// 1_7_B
#include <iostream>
using namespace std;

int main(){
  int n, x, count, i, j;
  while(true){
    cin >> n >> x;
    if(n == 0 && x == 0) return 0;
    count = 0;
    for(i = 1; i < n; i++){
      for(j = i+1; j < n; j++){
        if(x-i-j > j && x-i-j <= n) count++;
      }
    }
    cout << count << endl;
  }
}

Measured memory_bytes: 3088
#include <iostream>
#include <iomanip>
#include <math.h>
#include <cmath>

int main()
{
  double a, b, x;
  std::cin >> a >> b >> x;

  double rad = 0;
  if(x/a < 0.5 * a * b) {
    rad = atan((a*b*b)/(2*x));
  } else {
    rad = atan(2*(a*b - x/a)/(a*a));
  }

  if(rad < 0) {
    rad += M_PI;
  }

  double theta = rad * 180 / M_PI;

  std::cout << std::fixed << std::setprecision(15) << theta << std::endl;
  return 0;
}


Measured memory_bytes: 4092
N = int(input())
Ds = [(*map(int, input().split()),) for _ in range(N)]

s = 0
for d in Ds:
    if d[0] != d[1]:
        s = 0
        continue
    s += 1
    if s == 3:
        print('Yes')
        break
else:
    print('No')


Measured memory_bytes: 9172
# 愚直に配列に1, 2の操作をやると時間がかかる

def input():
    import sys
    return sys.stdin.readline().rstrip()


def main():
    import math
    import collections
    import itertools

    n = int(input())
    as_ = list(map(int, input().split()))
    b = [0] * n

    odd_a = as_[::2]
    even_a = as_[1::2]
    if n % 2 == 0:
        ans = even_a[::-1] + odd_a
    else:
        ans = odd_a[::-1] + even_a
    print(*ans)

if __name__ == '__main__':
    main()

Measured memory_bytes: 25532
import sys

read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7


def main():
    N = int(readline())
    SN = 0
    for n in str(N):
        SN += int(n)
    if N%SN==0:
        print('Yes')
    else:
        print('No')


if __name__ == '__main__':
    main()


Measured memory_bytes: 9036
#include<bits/stdc++.h>
using namespace std;
#define rep(i,j,n) for(int i=(int)(j);i<(int)(n);i++)
#define REP(i,j,n) for(int i=(int)(j);i<=(int)(n);i++)
#define MOD 1000000007
#define int long long
#define ALL(a) (a).begin(),(a).end()
#define vi vector<int>
#define vii vector<vi>
#define pii pair<int,int>
#define priq priority_queue<int>
#define disup(A,key) distance(A.begin(),upper_bound(ALL(A),(int)(key)))
#define dislow(A,key) distance(A.begin(),lower_bound(ALL(A),(int)(key)))
#define tii tuple<int,int,int>
#define mp make_pair
signed main(){
  int H,W; cin>>H>>W;
  vector<string> S(H);
  rep(i,0,H) cin>>S[i];
  int ans=0;
  vi X={0,1,0,-1},Y={1,0,-1,0};
  rep(i,0,H){
    rep(j,0,W){
      if(S[i][j]=='.'){
        queue<pii> Q;
        Q.push(mp(i,j));
        Q.push(mp(-1,-1));
        int count=-1;
        vector<vector<bool>> F(H,vector<bool>(W,1));
        F[i][j]=0;
        while(1){
          int x=Q.front().first,y=Q.front().second;
          Q.pop();
          if(x==-1){
            count++;
            if(Q.size()==0)
              break;
            Q.push(mp(-1,-1));
          }
          else{
            rep(k,0,4){
              int p=X[k]+x,q=Y[k]+y;
              if(0<=p&&p<H&&0<=q&&q<W){
                if(S[p][q]=='.'){
                  if(F[p][q]){
                    F[p][q]=0;
                    Q.push(mp(p,q));
                  }
                }
              }
            }
          }
        }
        ans=max(ans,count);
      }
    }
  }
  cout<<ans<<endl;
  }



Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
    int a, b, C;
    cin >> a >> b >> C;

    double pi = acos(-1);
    double rad = (double)C/180*pi;
    double c = sqrt(pow(a,2) + pow(b,2) - (double)2*a*b*cos(rad));

    double h = b * sin(rad);
    double S = h/2*a;
    double L = a + b + c;

    cout << fixed << setprecision(10) << S << endl << L << endl << h << endl;
  
}


Measured memory_bytes: 3556
import math

N,D=map(int,input().split())

x=[]
s=0
cnt=0
for i in range(N):
  X=list(map(int,input().split()))
  x.append(X)

for i in range(N-1):
  for j in range(i+1,N):
    for k in range(D):
      s+=(x[i][k]-x[j][k])*(x[i][k]-x[j][k])
    s=math.sqrt(s)
    #print(s)
    if s==int(s):
      cnt+=1
    s=0
print(cnt)

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

using namespace std;
using ll = long long;

//container util
#define SORT(c) sort((c).begin(),(c).end())
#define all(a) (a).begin(), (a).end()

//repetition
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

//print
#define pv(val) cerr << #val << '=' << (val) << endl

const int INF = 1e9;

int main(void){

	int N, M; cin >> N >> M;
	vector<vector<int>> graph(N);

	REP(i,M){
		int A, B; cin >> A >> B;
		A--; B--;
		graph[A].push_back(B);
		graph[B].push_back(A);
	}

	vector<bool> was(N, false);
	vector<int> prev(N, -1);
	queue<int> q;
	was[0] = true;
	prev[0] = 0;
	q.push(0);
	while(!q.empty()){
		int v = q.front();
		q.pop();
		for(int i:graph[v]){
			if(was[i]) continue;
			q.push(i);
			prev[i] = v+1;
			was[i] = true;
		}
	}


	bool flag = true;
	REP(i,N) if(!was[i]) flag = false;

	if(flag){
		cout << "Yes" << endl;
		FOR(i,1,N) cout << prev[i] << endl;

	}else{
		cout << "No" << endl;
	}


	return 0;

}


Measured memory_bytes: 10060
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define rrep(i,n) for(int (i)=((n)-1);(i)>=0;(i)--)
#define itn int
#define all(x) (x).begin(),(x).end()
#define F first
#define S second
const long long INF = 1LL << 60;
const int MOD = 1000000007;
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
signed main(void){
    int x,y; cin>>x>>y;
    int ans = 0;
    if(x == 1&&y == 1) ans += 400000;
    if(x == 1) ans += 300000;
    if(x == 2) ans += 200000;
    if(x == 3) ans += 100000;
    x = y;
    if(x == 1) ans += 300000;
    if(x == 2) ans += 200000;
    if(x == 3) ans += 100000;
    cout<<ans<<endl;
}


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

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

    // all the code goes here
    string a,b;cin>>a>>b;

    vector<vector<tuple<int,int,int>>> dp(a.length()+1,vector<tuple<int,int,int>>(b.length()+1,make_tuple(0,-1,-1)));

    int n = a.length(),m = b.length();
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < m; j++)
        {
            if(a[i] == b[j])
            {
                if(get<0>(dp[i+1][j+1]) < get<0>(dp[i][j])+1)
                {
                    dp[i+1][j+1] = make_tuple(get<0>(dp[i][j])+1,i,j);
                }
            }
            if(get<0>(dp[i+1][j]) < get<0>(dp[i][j]))
            {
                dp[i+1][j] = dp[i][j];
            }
            if(get<0>(dp[i][j+1]) < get<0>(dp[i][j]))
            {
                dp[i][j+1] = dp[i][j];
            }
        }
    }

    pair<int,int> in = {-1,-1};
    int mv = 0;
    for(int i = 0; i <= n; i++)
    {
        for(int j = 0; j <= m; j++)
        {
            if(mv < get<0>(dp[i][j]))
            {
                mv = get<0>(dp[i][j]);
                in = make_pair(get<1>(dp[i][j]),get<2>(dp[i][j]));
            }
        }
    }

    string res = "";
    while(in.first != -1 && in.second != -1)
    {
        res+=a[in.first];
        in = make_pair(get<1>(dp[in.first][in.second]),get<2>(dp[in.first][in.second]));
    }

    reverse(res.begin(),res.end());
    cout<<res<<"\n";

    return 0;
}

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

int main() {
  int N,K;
  string S;
  cin >>N >>K >>S;
  if(S.at(K-1)=='A'){
    S.at(K-1)='a';
  }
  else if(S.at(K-1)=='B'){
    S.at(K-1)='b';
  }
  else{
    S.at(K-1)='c';
  }
  cout <<S <<endl;
}


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

int main()
{
    int n;
    cin>>n;
    vector<int> ans(3,0);

    for(int i=0; i<n; i++)
    {
        vector<int> a(3);
        vector<int> temp(3,INT_MIN);
        for(int j=0; j<3; j++)
        {
            cin>>a[j];
            for(int k=0; k<3; k++)
            {
                if(j==k)continue;
                temp[j] = max(temp[j], ans[k]+a[j]);
            }
        }
        ans = temp;
    }
    int final=0;
    for(int i=0; i<3; i++)
        final = max(final,ans[i]);

    cout<<final;
    return 0;
} 

Measured memory_bytes: 256
object Main {
  def main(args:Array[String]) = {
    val sc = new java.util.Scanner(System.in)
    val n = sc.nextInt
    for (i <- 0 until n){
      val ls = List.fill(3)(sc.nextInt).sorted
      if (ls(2)*ls(2) == ls(1)*ls(1) + ls(0)*ls(0)) println("YES") else println("NO")
    }
  }
}

Measured memory_bytes: 51156
n,y = map(int, input().split())

flg = 0
for i_a in range(n+1)[::-1]:
	for i_b in range(n+1-i_a)[::-1]:
		i_c = n - i_a - i_b
		if i_a*10000 + i_b*5000 + i_c*1000 == y:
			flg = 1
			print(i_a, i_b, i_c)
			break
	if flg == 1:
		break

if flg == 0:
	print("-1 -1 -1")


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

int main() {
  int n; cin >> n;
  vector<int> a(n);
  for (int i = 0; i < n; i ++) cin >> a[i];
  sort(a.begin(), a.end());

  int x = n / 2;
  if (a[x] == a[x - 1]) cout << 0 << endl;
  else cout << a[x] - a[x - 1] << endl;
}

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

vector<pair<int,int>> item;
long long dp[105][100005];

int n,w;

long long solve(int pos, int peso){
    
    if(peso > w) return -1000000000000000;
    if(pos > n) return -1000000000000000;
    
    if(dp[pos][peso]) return dp[pos][peso];
    
    if(pos == n){
        return 0;
    }
    
    dp[pos][peso] = max( solve(pos+1, peso), item[pos].second + solve(pos+1, peso + item[pos].first));     
    // cout << dp[pos][peso] << " " << peso << endl;
    return dp[pos][peso];
    
}

int main() {
    cin >> n >> w;
	for(int i = 0; i < n; i++){
        pair<int, int> p; cin >>p.first >> p.second;
        item.push_back(p);
    }

    cout << solve(0,0) << endl;
    return 0;
}

Measured memory_bytes: 78080
#include <iostream>
#include <algorithm>

using namespace std;

struct student
{
	int id;
	int order;

	bool operator<(const student& stu) const
	{
		return order < stu.order;
	}
};

student a[100005];

int main()
{
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		a[i].id = i;
		cin >> a[i].order;
	}

	sort(a + 1, a + 1 + n);
	for (int i = 1; i <= n; i++)
	{
		cout << a[i].id << " ";
	}
	return 0;

}

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

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

Node root;
int n;

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

Node treeMaximum(Node x){
  while(x->right != NIL){
    x = x->right;
  }
  return x;
}

Node treeSearch(Node u, int k){
  if(u == NIL || k == u->key){
    return u;
  }
  if(k < u->key){
    return treeSearch(u->left,k);
  }
  else{
    return treeSearch(u->right,k);
  }
}

Node treeSuccessor(Node x){
  Node y;
  if(x->right != NIL){
    return treeMinimum(x->right);
  }
  y = x->parent;
  while(y != NIL && x == y->right){
    x = y;
    y = y->parent;
  }
  return y;
}

void transplant(Node u,Node v){
  if(u->parent == NIL){
    root = v;
  }
  else if(u == u->parent->left){
    u->parent->left = v;
  }
  else{
    u->parent->right = v;
  }
  if(v != NIL){
    v->parent = u->parent;
  }
}

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

  if(z->left == NIL){
    transplant(z,z->right);
  }
  else if(z->right == NIL){
    transplant(z,z->left);
  }
  else{
    y = treeMinimum(z->right);
    if(y->parent != z){
      transplant(y,y->right);
      y->right = z->right;
      y->right->parent = y;
    }
    transplant(z,y);
    y->left = z->left;
    y->left->parent = y;
  }
}

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

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

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

void inorder(Node u){
 
  if(u != NIL){
    inorder(u->left);
    printf(" %d",u->key);
    inorder(u->right);
  }
}
void preorder(Node u){

  if(u != NIL){
    printf(" %d",u->key);
    preorder(u->left);
    preorder(u->right);
  }
}


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

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

  return 0;
}

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

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

    vector<ll> v = vector<ll>();

    ll threshold = static_cast<ll>(pow(10, 18));

    ll ans = 1;

    rep(i, N)
    {
        ll in;
        cin >> in;

        if (in == 0)
        {
            std::cout << 0 << endl;
            return 0;
        }
        if (in != 1)
        {
            v.push_back(in);
        }
    }

    int repCount = static_cast<int>(v.size());

    rep(i, repCount)
    {
        ll in = v.at(i);
        ll tmpAns = ans * in;

        // oveflow
        if (tmpAns / in != ans)
        {
            std::cout << -1 << endl;
            return 0;
        }

        if (tmpAns > threshold)
        {
            std::cout << -1 << endl;
            return 0;
        }
        ans = tmpAns;
    }

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


Measured memory_bytes: 4232
#![allow(
    non_snake_case,
    unused_variables,
    unused_assignments,
    unused_mut,
    unused_imports,
    dead_code
)]
//use permutohedron::LexicalPermutation as _;
use proconio::{fastout, input, marker::*};
//use std::collections::HashSet;
use std::collections::*;
//use std::collections::BTreeMap;
//use std::cmp::*;
//use std::num;
//use petgraph::unionfind::UnionFind;

#[fastout()]
fn main() {
    input! {
        N:usize, mut S:[String;N]
    }
    //S.sort();
    //println!("{:?}", S);
    let emptystring = "".to_string();
    let mut m = BTreeMap::new();
    for s in S {
        *m.entry(s).or_insert(0) += 1;
    }
    let max = *m.values().max().unwrap();
    for (s, v) in m.iter() {
        if *v == max {
            println!("{}", s.to_string());
        }
    }
}


Measured memory_bytes: 26108
#include"bits/stdc++.h"
using namespace std;
#define REP(k,m,n) for(int (k)=(m);(k)<(n);(k)++)
#define rep(i,n) REP((i),0,(n))
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using tp3 = tuple<int, int, int>;
using Mat = vector<vector<ll>>;
constexpr int INF = 1 << 28;
constexpr ll INFL = 1ll << 60;
constexpr int dh[4] = { 0,1,0,-1 };
constexpr int dw[4] = { -1,0,1,0 };
bool isin(const int H, const int W, const int h, const int w) {
    return 0 <= h && h < H && 0 <= w && w < W;
}
template<typename T>
T chmin(T& l, T r) {
    return l = min(l, r);
}
template<typename T>
T chmax(T& l, T r) {
    return l = max(l, r);
}
// ============ template finished ============
using pis = pair<int, string>;

pii analyzer(string s) {
    int acc = 0, minv = 0;
    for (char c : s) {
        if (c == '(') {
            acc++;
        }
        else {
            acc--;
        }
        minv = min(minv, acc);
    }
    int least = -minv;
    return { least,acc };
}

string join(vector<string> brackets) {
    vector<pis> parsed;
    for (auto bracket : brackets) {
        auto[least, acc] = analyzer(bracket);
        parsed.push_back({ least,bracket });
    }
    sort(parsed.begin(), parsed.end());
    string res;
    for (auto p : parsed)res += p.second;
    return res;
}

void bracket_reverse(string& brackets) {
    reverse(brackets.begin(), brackets.end());
    for (char&c : brackets)c = c == '(' ? ')' : '(';
}

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

    vector<string> S(N);
    rep(i, N) cin >> S[i];

    int debugsum = 0;
    {
        for (auto s : S)for (char c : s)debugsum += c == '(' ? 1 : -1;
    }

    vector<string> up, down;
    for (auto s : S) {
        auto[least, acc] = analyzer(s);
        if (acc >= 0) {
            up.push_back(s);
        }
        else {
            bracket_reverse(s);
            down.push_back(s);
        }
    }
    string front = join(up);
    string back = join(down);
    bracket_reverse(back);

    string res = front + back;
    auto[least, acc] = analyzer(res);
    if (least == 0 && acc == 0) {
        assert(debugsum == 0);
        cout << "Yes" << endl;
    }
    else {
        cout << "No" << endl;
    }
    return 0;
}


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

typedef long long   signed int LL;
typedef long long unsigned int LU;

#define incID(i, l, r) for(int i = (l)    ; i <  (r); i++)
#define incII(i, l, r) for(int i = (l)    ; i <= (r); i++)
#define decID(i, l, r) for(int i = (r) - 1; i >= (l); i--)
#define decII(i, l, r) for(int i = (r)    ; i >= (l); i--)
#define  inc(i, n) incID(i, 0, n)
#define inc1(i, n) incII(i, 1, n)
#define  dec(i, n) decID(i, 0, n)
#define dec1(i, n) decII(i, 1, n)

#define inII(v, l, r) ((l) <= (v) && (v) <= (r))
#define inID(v, l, r) ((l) <= (v) && (v) <  (r))

#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
#define UB upper_bound
#define LB lower_bound
#define PQ priority_queue

#define  ALL(v)  v.begin(),  v.end()
#define RALL(v) v.rbegin(), v.rend()
#define  FOR(it, v) for(auto it =  v.begin(); it !=  v.end(); ++it)
#define RFOR(it, v) for(auto it = v.rbegin(); it != v.rend(); ++it)

template<typename T> bool   setmin(T & a, T b) { if(b <  a) { a = b; return true; } else { return false; } }
template<typename T> bool   setmax(T & a, T b) { if(b >  a) { a = b; return true; } else { return false; } }
template<typename T> bool setmineq(T & a, T b) { if(b <= a) { a = b; return true; } else { return false; } }
template<typename T> bool setmaxeq(T & a, T b) { if(b >= a) { a = b; return true; } else { return false; } }
template<typename T> T gcd(T a, T b) { return (b == 0 ? a : gcd(b, a % b)); }
template<typename T> T lcm(T a, T b) { return a / gcd(a, b) * b; }

// ---- ----

LL n, c, k, t[100000];

int main() {
	cin >> n >> c >> k;
	inc(i, n) { cin >> t[i]; }
	
	sort(t, t + n);
	
	LL ans = 0, lim = -1, cc = 0;
	inc(i, n) {
		cc++;
		if(lim < t[i] || cc > c) { cc = 1; ans++; lim = t[i] + k; }
	}
	
	cout << ans << endl;
	
	return 0;
}


Measured memory_bytes: 1024
N, A, B, C, D = gets.split.map(&:to_i)
S = gets.chomp

dpa = Array.new(N + 4, false)
dpa[A - 1] = true

cond = C < D

((B - 1)..(D - 1)).each do |i|
  break if cond

  if S[i - 1] == '.' && S[i] == '.' && S[i + 1] == '.'
    cond = true
  end
end

((A - 1)..N).each do |i|
  next unless dpa[i]

  dpa[i + 1] = true if S[i + 1] == '.'
  dpa[i + 2] = true if S[i + 2] == '.'
end

dpb = Array.new(N + 4, false)
dpb[B - 1] = true

((B - 1)..N).each do |i|
  next unless dpb[i]

  dpb[i + 1] = true if S[i + 1] == '.'
  dpb[i + 2] = true if S[i + 2] == '.'
end

if dpa[C - 1] && dpb[D - 1] && cond
  puts 'Yes'
else
  puts 'No'
end


Measured memory_bytes: 5372
#include <iostream>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include <iomanip>
#include <cmath>
typedef long long ll;
using namespace std;

void solve(){
  int n, ans = 0; cin >> n;
  vector<int> p(n + 1);
  for(int i = 1; i <= n; i++){
    cin >> p[i];
  }
  for(int i = 1; i <= n; i++){
    if(p[i] == i){
      ans++;
      if(i <= n - 1) swap(p[i], p[i + 1]);
      else swap(p[i], p[i - 1]);
    }
  }
  cout << ans << endl;
  return;
}

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


Measured memory_bytes: 768
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <climits>
#include <ctime>
#include <queue>
#include <stack>
#include <algorithm>
#include <list>
#include <vector>
#include <set>
#include <map>
#include <iostream>
#include <deque>
#include <complex>
#include <string>
#include <iomanip>
#include <sstream>
#include <bitset>
#include <valarray>
#include <iterator>
#include <assert.h>
using namespace std;
typedef long long int ll;
typedef unsigned int uint;
typedef unsigned char uchar;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;

#define REP(i,x) for(int i=0;i<(int)(x);i++)
#define REPS(i,x) for(int i=1;i<=(int)(x);i++)
#define RREP(i,x) for(int i=((int)(x)-1);i>=0;i--)
#define RREPS(i,x) for(int i=((int)(x));i>0;i--)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();i++)
#define RFOR(i,c) for(__typeof((c).rbegin())i=(c).rbegin();i!=(c).rend();i++)
#define ALL(container) (container).begin(), (container).end()
#define RALL(container) (container).rbegin(), (container).rend()
#define SZ(container) ((int)container.size())
#define mp(a,b) make_pair(a, b)
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );

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; }
template<class T> ostream& operator<<(ostream &os, const vector<T> &t) {
os<<"["; FOR(it,t) {if(it!=t.begin()) os<<","; os<<*it;} os<<"]"; return os;
}
template<class T> ostream& operator<<(ostream &os, const set<T> &t) {
os<<"{"; FOR(it,t) {if(it!=t.begin()) os<<","; os<<*it;} os<<"}"; return os;
}
template<class S, class T> ostream& operator<<(ostream &os, const pair<S,T> &t) { return os<<"("<<t.first<<","<<t.second<<")";}
template<class S, class T> pair<S,T> operator+(const pair<S,T> &s, const pair<S,T> &t){ return pair<S,T>(s.first+t.first, s.second+t.second);}
template<class S, class T> pair<S,T> operator-(const pair<S,T> &s, const pair<S,T> &t){ return pair<S,T>(s.first-t.first, s.second-t.second);}

const int INF = 1<<28;
const double EPS = 1e-8;
const int MOD = 1000000007;

#define HIT(a,b) ((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)<(a.r+b.r)*(a.r+b.r))

struct DISK{
	int x,y,r,c,o;
	DISK():o(0){}
};
int n;

int main(){
	ios::sync_with_stdio(false);
	while(cin >> n, n){
		vector<DISK> D(n);
		REP(i, n) cin>>D[i].x>>D[i].y>>D[i].r>>D[i].c;
		REP(j, n)REP(i, j)if(HIT(D[i],D[j])) D[j].o |= 1<<i;
		int ans = 0;
		vector<char> dp(1<<n);
		dp[0] = 1;
		REP(b, 1<<n)if(dp[b]){
			REP(j, n)REP(i, j)if(!((b >> i) & 1)){
				if((b >> i) & 1 || (b>>j) & 1 || D[i].c != D[j].c || ~b & D[i].o || ~b & D[j].o) continue;
				dp[b|1<<i|1<<j] = 1;
			}
			ans = max(ans, __builtin_popcount(b));
		}
		cout << ans << endl;
	}
	return 0;
}

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

double distance(vector<int> x, vector<int> y, int i, int j){
    double pw = pow((x[i] - x[j]),2) + pow((y[i] - y[j]),2);
    return sqrt(pw);
}

int step(int n) {
    int tmp = 1;
    rep(i,n) tmp *= (i+1);
    return tmp;
}

int main() {
    int n;
    cin >> n;
    vector<int> x(n), y(n), p(n);
    rep(i,n) {
        cin >> x[i];
        cin >> y[i];
    }
    rep(i,n) p[i] = i ;

    double tmp = 0;
    do {rep(i,n-1) {
       tmp += distance(x, y, p[i], p[i+1]);
    }} while (next_permutation(p.begin(),p.end()));
    
    double ans = tmp / step(n);

    printf("%.10f\n", ans);
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll   long long int
#define T int t; cin>>t; while(t--)
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL)
#define PI 3.141592653589793238462643383

int main(){
   
    fast;
    
    ll n;
    ll mod = 1000000007;
	cin >> n;
	ll arr[n];
    ll sum = 0;
	for(int i=0;i<n;i++){
	    cin >> arr[i];
        sum = (sum + arr[i]);
	}
	ll ans = 0;
	
	
	for(int i=0;i<n;i++){
		sum = sum - arr[i];
		ans = (ans + ((sum%mod)*(arr[i]%mod))%mod)%mod;
	}
	cout << ans << endl;










}

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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;

#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define N 100000
#define MOD 1000000007
#define INF 1000000000

int main()
{
        int n;
        int p[20000] = {};
        cin >> n;
        for(int i = 0; i < n; i++){
                cin >> p[i];
                p[i]--;
        }
        int a[20000] = {};
        int b[20000] = {};
        int sum[20000] = {};
        int cnt = 0;
        for(int i = 0; i < n; i++){
                sum[ p[i] ] = i;
        }

        for(int i = 0; i < n; i++){
                int curSum = 500000000 + sum[i];
                if(i == 0){
                        a[i] = 1;
                        b[i] = curSum - 1;
                }
                else{
                        int prev = a[i - 1];
                        a[i] = a[i - 1] + 1;
                        b[i] = curSum - a[i];
                        while(b[i] >= b[i - 1]){
                                b[i]--;
                                a[i]++;
                        }
                }
        }

        for(int i = 0; i < n; i++){
                cout << a[i] << ' ';
        }
        cout << endl;
        for(int i = 0; i < n; i++){
                cout << b[i] << ' ';
        }


        return 0;
}


Measured memory_bytes: 896
#include <algorithm>
#include <bitset>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <functional>
#include <iostream>
#include <queue>
#include <set>
#include <map>
#include <unordered_map>
#include <stack>
#include <string>
#include <vector>
#include <iomanip>
 
using namespace std;
typedef long long ll;
using gra = vector<vector<ll>>;
using gram = vector<unordered_map<ll,ll>>;
 
typedef unsigned long long ull;
 
template <class T> inline bool chmin(T &a, T b) { if (a > b) { a = b; return true; } return false; }
template <class T> inline bool chmax(T &a, T b) { if (a < b) { a = b; return true; } return false; }
 
template <class T> T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }
template <class T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
template <class T> T dup(T a, T b) { return (a + b - 1) / b; }
template <class T> T modpow(T x, T p, T m) { T a=1; while(p){ if(p%2)a =a*x%m; x = x+x%m; p/=2; } return a; }
// template <class T> void prim(T a) { for(ll i=0;i<a.size();++i) { cout << a[i]; } cout << "\n"; }
//template< typename T >
//T mod_pow(T x, T n, const T &p) {
//  T ret = 1;
//  while(n > 0) {
//    if(n & 1) (ret *= x) %= p;
//    (x *= x) %= p;
//    n >>= 1;
//  }
//  return ret;
//}
/////////////////// 
//

#define mod 1000000007LL
#define INF 10000000000000000LL
 
#define rep(i, n) for (ll i = 0; i < n; ++i)
#define rep1(i, n) for (ll i = 1; i <= n; ++i)
#define rrep(i, n) for (int i = (n - 1); i >= 0; --i)
#define rrep1(i, n) for (int i = n; i > 0; --i)
 
#define pri(x) cout << (x) << "\n"
#define pri2(x, y) cout << (x) << " " << (y) << "\n"
#define pri3(x, y, z) cout << (x) << " " << (y) << " " << (z) << "\n"
//#define modpow(x, p, m) { ll a=1; while(p){ if(p%2)a =a*x%m; x = x+x%m; p/=2; } return a; }
 
#define m0(h) memset(h, 0, sizeof(h))
#define m1(h) memset(h, 1, sizeof(h))
#define m(h, n) memset(h, (n), sizeof(h))
#define all(n) (n).begin(),(n).end()
#define bit(n) (1LL << (n))
#define pb push_back
#define mp make_pair
 
//#ifdef LOCAL
//
//#define dpri(...) fprintf(stderr, __VA_ARGS__)
//#define pria(g) rep(i,g.size()){ cout << i << "{"; rep(j,g[i].size()) cout << g[i][j] << " "; cout << "}" << "\n"; }
//#else
//#define dpri(...) 42
//#define pria(g) 42
//#endif
//
//
//

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  // ---------------------
  // コーディング開始
  // ---------------------
  ll n,m;
  ll s,c;
  cin >> n >> m;
  ll ok =pow(10,(n-1));
  if(ok==1)ok=0;
  string ans = to_string(ok);
  ll fla[n] ;
  rep(i,n){
    fla[i]=INF;
  }
  rep(i,m){
    cin >> s >> c;
    s--;
    if(s==0&&c==0&&n!=1){
      pri(-1);
      return 0;
    }
    if(fla[s]==INF||fla[s]==c){
      fla[s]=c;
      ans[s]=to_string(c)[0];
    }else{
      // フラグ死
      pri(-1);
      return 0;
    }
  }
  pri(ans);
}







Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i,n) for (int i = 0; i <(n); ++i)
#define REP2(i,x,n) for (int i = x; i <(n); ++i)
#define ALL(v) v.begin(), v.end()
#define RALL(v) v.rbegin(), v.rend()
using namespace std;
using ll = long long;
using P = pair<int,int>;
static const double PI = acos(-1);
static const int INF = 1e9+7;
//debug 
#ifdef _DEBUG
#define debug(var)  do{cout << #var << " :";view(var);}while(0)
#else
#define debug(...)
#endif
template<typename T> void view(T e){cout << e << endl;}
template<typename T> void view(const vector<T>& v){for(const auto& e : v){ cout << e << " "; } cout << endl;}
template<typename T> void view(const vector<vector<T> >& vv){ for(const auto& v : vv){ view(v); } }

struct UnionFind {
vector<int> d;
UnionFind(int n=0): d(n,-1) {}
int find(int x) {
  if (d[x] < 0) return x;
  return d[x] = find(d[x]);
}
bool unite(int x, int y) {
  x = find(x); y = find(y);
  if (x == y) return false;
  if (d[x] > d[y]) swap(x,y);
  d[x] += d[y];
  d[y] = x;
  return true;
}
bool same(int x, int y) { return find(x) == find(y);}
int size(int x) { return -d[find(x)];}
};

int main(){
  int n, m;
  cin >> n >> m;
  UnionFind uf(n);
  REP(i,m){
    int a, b;
    cin >> a >> b;
    --a, --b;
    uf.unite(a,b);
  }  

  int minx = 0;
  REP(i,n){
    minx = max(uf.size(i),minx);
  }

  cout << minx << endl;

  return 0;
}

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

int main (void) {
    long long h, w;
    scanf("%lld%lld", &h, &w);

    if ( h == 1 || w == 1 )
        printf("1\n");
    else
        printf("%lld\n", ((h+1)/2) * ((w+1)/2) + (h-(h+1)/2) * (w-(w+1)/2));
    return EXIT_SUCCESS;
}


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

int main()
{
    int n;
    vector<int> a;
    cin >> n;
    for (int i = 1; i <= 9; i++)
    {
        for (int j = 1; j <= 9; j++)
        {
            a.push_back(i * j);
        }
    }

    for (int i = 0; i < a.size(); i++)
    {
        if (n == a[i])
        {
            cout << "Yes\n";
            return 0;
        }
    }

    cout << "No\n";
}

Measured memory_bytes: 3632
#include <stdio.h>

int main(void)
{
  int n, x, i;
  scanf("%d", &n);

  if (n >= 3 && n <= 10000) {
    for (i = 1; i <= n; i++) {
      if (i % 3 == 0) {
        printf(" %d", i);
      } else {
        x = i;
        while(x != 0) {
          if (x % 10 == 3) {
            printf(" %d", i);
            break;
          }
          x /= 10;
        }
      }
    }
    putchar('\n');
  }
  return 0;
}

Measured memory_bytes: 600
#include<iostream>
#include<stdio.h>
#include<vector>
#include<cmath>
#include<queue>
#include<string.h>
#include<map>
#include<set>
#include<algorithm>
#define ll long long
#define pi pair < ll,ll >
#define mp(a,b) make_pair(a,b)
#define mid (low+high)/2
#define rep(i,a,b) for(int i = a;i < b;i++)
#define N 300004

using namespace std;

ll n,ar[N],a,b;
ll ans[N];
set < ll > s;
map < ll,ll > mapper;
ll seg[4*N];
multiset < ll > values[N];
vector < ll > graph[N];
ll realans[N];

void update(ll low,ll high,ll pos,ll slow,ll val)
{
    if(low==high&&low==slow)
    {
        seg[pos]=val;
        return;
    }
    if(low>slow||high<slow)
        return;

    update(low,mid,pos*2+1,slow,val);
    update(mid+1,high,pos*2+2,slow,val);

    seg[pos] = max(seg[pos*2+1],seg[pos*2+2]);

    return;
}

ll query(ll low,ll high,ll pos,ll shigh)
{
    if(high <= shigh)
        return seg[pos];
    if(low>shigh)
        return 0;

    return max(query(low,mid,pos*2+1,shigh),query(mid+1,high,pos*2+2,shigh));
}

void solve(ll cur,ll par)
{
    ans[cur] = query(0,n,0,ar[cur]-1)+1;
    realans[cur] = max(ans[cur],realans[par]);

    values[ar[cur]].insert(-ans[cur]);
    update(0,n,0,ar[cur],-*(values[ar[cur]].begin()));

    rep(i,0,graph[cur].size())
    {
        ll v = graph[cur][i];

        if(v==par)
            continue;

        solve(v,cur);
    }

    values[ar[cur]].erase(values[ar[cur]].lower_bound(-ans[cur]));
    update(0,n,0,ar[cur],-*(values[ar[cur]].begin()));

    return;
}

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

    cin >> n;

    rep(i,1,n+1)
    {
        cin >> ar[i];
        s.insert(ar[i]);
    }

    ll cnt = 0;

    for(set < ll >::iterator it = s.begin();it != s.end();it++)
    {
        mapper[(*it)] = cnt;
        cnt++;
    }

    rep(i,1,n+1)
        ar[i] = mapper[ar[i]];

    rep(i,0,n-1)
    {
        cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }

    solve(1,1);

    rep(i,1,n+1)
        cout << realans[i] << endl;

    return 0;
}



Measured memory_bytes: 76896
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define N 150
#define W (ll)2e5
ll n,k,memo[N][W],w[N],v[N];

ll dp(ll curr , ll rem) {
    if (curr > n) return 0;
    ll &sol = memo[curr][rem];
    if (sol != -1) return sol;
    sol = dp(curr + 1 , rem);
    if (rem >= w[curr])
        sol = max(
            dp(curr + 1 , rem - w[curr]) + v[curr] ,
            sol
        );
    return sol;
}

int main() {
    scanf("%lld%lld" , &n , &k);
    for (ll i = 1 ; i <= n ; i++)
        scanf("%lld%lld" , &w[i] , &v[i]);
    memset (memo , -1 , sizeof memo);
    printf("%lld\n" , dp(1 , k));
}


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


int main()
{
	int input[3] = {0};
	int i = 0;
	int j = 0;
	int result = 0;
	int bh = 0;
	int bw = 0;
	int ah = 0;
	int aw = 0;

	for(i = 0; i < 3; i++) {
		scanf("%d", &input[i]);
	}

	bh = input[0];
	bw = input[0];
	ah = input[1];
	aw = input[2];
    for(i = 0; i < bh; i++) {
        for(j = 0; j < bw; j++) {
        	if (((bh - i) >=  ah) && ((bw - j) >= aw)) {
                result++;
        	}
        }
    }
    printf("%d",result);

    return 0;
}


Measured memory_bytes: 128
import java.util.Scanner

object Main extends App {
  val sc = new Scanner(System.in)
  def next(): String = sc.next()
  def nextInt(): Int = next().toInt
  def nextLong(): Long = next().toLong

  def task(): Unit = {
    val d = nextInt()
    val ans = (Seq("Christmas") ++ Seq.fill(25 - d)("Eve")).mkString(" ")
    println(ans)
  }

  task()
}


Measured memory_bytes: 25428
import std.stdio, std.string, std.conv;
import std.range, std.algorithm, std.array;


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

    if (a + b < c + d) {
        writeln("Right");
    }
    else if (a + b > c + d) {
        writeln("Left");
    }
    else {
        writeln("Balanced");
    }
}



void scan(T...)(ref T args) {
    import std.stdio : readln;
    import std.algorithm : splitter;
    import std.conv : to;
    import std.range.primitives;

    auto line = readln().splitter();
    foreach (ref arg; args) {
        arg = line.front.to!(typeof(arg));
        line.popFront();
    }
    assert(line.empty);
}



void fillAll(R, T)(ref R arr, T value) {
    static if (is(typeof(arr[] = value))) {
        arr[] = value;
    }
    else {
        foreach (ref e; arr) {
            fillAll(e, value);
        }
    }
}


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

int cnt[4];
double dp[333][333][333];
int n , x;

double f(int i , int j , int k)
{
	if(i == 0 && j == 0 && k == 0)return 0.0;
	
	if(dp[i][j][k])return dp[i][j][k];;;
	
	double res = n;
	
	if(i)res += f(i-1 , j , k) * i;
	if(j)res += f(i+1 , j-1 , k) * j;
	if(k)res += f(i , j+1 , k-1) * k;
	
	return dp[i][j][k] = res / (i+j+k);
	
}

main()
{
	cin >> n;
	
	for(int i = 1; i <= n; i++)
	{
		cin >> x;
		cnt[x]++;
	}
	
	cout << setprecision(10) << fixed << f( cnt[1] , cnt[2] , cnt[3] );
	
}


Measured memory_bytes: 260224
n = int(input())
a = list(map(int, input().split()))
m = (10**9 + 7)

result = 0

sum_a = 0
for i in range(n):
    sum_a = (sum_a + a[i]) % m

result = 0
for i in range(n):
    x = a[i]
    sum_a -= x
    result = (result + x*sum_a) % m

if(result < 0):
    result += m
print(result)


Measured memory_bytes: 94052
#include<iostream>
#include<cmath>
#include<cstring>
using namespace std;
const int N=10010;
const double PI=3.1415926535;
int a,b,x,y;
int main()
{
    cin>>a>>b>>x>>y;
    double theta=((x*60+y)/720.0-y/60.0)*2*PI;
    double res=a*a+b*b-2*a*b*cos(theta);
    printf("%.10lf",sqrt(res));
    
    return 0;
    
}

Measured memory_bytes: 4148
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>
#include <iostream>
#include <set>
#include <map>
#include <string>
#include <algorithm>

using namespace std;

#define mod 1e9+7
#define ll long long int
#define epsilon 1e-7

ll mi(ll x, ll y){
    if(x<y)return x;
    return y;
}
char ap[50][51];
int main(void){
    int h, w;
    scanf("%d %d ", &h, &w);
    for(int i = 0;i < h;i++)scanf("%s", &ap[i]);
    for(int i = 0;i < h;i++)for(int j = 0;j < w;j++){
        if(ap[i][j] == '#'){
            if((i==0||ap[i-1][j]=='.')&&(i==h-1||ap[i+1][j]=='.')&&(j==0||ap[i][j-1]=='.')&&(j==w-1||ap[i][j+1]=='.')){
                printf("No\n");
                return 0;
            }
        }
    }
    printf("Yes\n");
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<stdio.h>
//#include <bits/stdc++.h>
#include<vector>
#include<float.h>
#include<iomanip>
#include<algorithm>
#include<string>
#include<cstring>
#include<math.h>
#include<cmath>
#include<sstream>
#include<set>
#include<map>
#include<queue>
#include<cassert>
#include<cmath>
#include<cstdint>


     
#define INF 1e9
#define LINF 1e19
#define rep(i,n)for(int i=0;(i)<(int)(n);i++)
#define REP(i,a,b)for(int i=(int)(a);(i)<=(int)(b);i++)
#define VEC(type, c, n) std::vector<type> c(n);for(auto& i:c)std::cin>>i;
#define vec(type,n) vector<type>(n)
#define vvec(m,n) vector<vector<int>> (int(m),vector<int>(n))
#define ALL(a)  (a).begin(),(a).end()
#define chmin(a, b) a = min(a, b)
#define chmax(a, b) a = max(a, b)
     
using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
using P = pair<ll, ll>;
     
const ll MOD = 1e9 + 7;
//最大公約数
ll gcd(ll a, ll b){
  if(b == 0)return a;
  else return gcd(b, a % b);
}



int main(){
    string s;
    cin >> s;
    int n = s.size();
    ll cnt = 0, res = 0;
    rep(i, n){
        if(s[i] == 'S')cnt++;
        else if(s[i] == 'T' && cnt > 0){
            res += 2;
            cnt--;
        }
    }
    cout << n - res << endl;
}





Measured memory_bytes: 3492