akhauriyash/Code-Regression huggingface dataset:
#include<stdio.h>

int main(void){
    int x[4],y[4];
    scanf("%d%d%d%d",&x[0],&y[0],&x[1],&y[1]);
    x[2]=x[1]-y[1]+y[0];
    y[2]=y[1]+x[1]-x[0];
    x[3]=x[2]-x[1]+x[0];
    y[3]=y[2]-y[1]+y[0];
    printf("%d %d %d %d",x[2],y[2],x[3],y[3]);
    return 0;
}

Measured memory_bytes: 128
def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    limit = sum(A) / (4 * M)
    count = 0
    for i in range(N):
        if A[i] >= limit:
            count += 1
    if count >= M:
        print("Yes")
    else:
        print("No")

if __name__ == '__main__':
    main()

Measured memory_bytes: 38256
#include <iostream>
#include <vector>
using namespace std;
int main(){
  int n,fs,ts,os;
  cin >>n;
  long long int a;
  vector <long long int> f,t,o;
  for(int i=0;i<n;i++) {
    cin >> a;
    if(a%4==0) f.push_back(a);
    else if(a%2==0) t.push_back(a);
    else o.push_back(a);
  }
  fs=f.size();ts=t.size();os=o.size();
  if(fs==0){
    if(os==0) cout << "Yes"<<endl;
    else cout <<"No"<<endl;
  }
  else{
     if(os==0) cout <<"Yes"<<endl;
     else if(ts==0){
       if((fs+1)>=os) cout <<"Yes"<<endl;
       else cout <<"No"<<endl;
     }
     else{
       if(fs>=os) cout <<"Yes"<<endl;
       else cout <<"No"<<endl;
       }
     }
}


Measured memory_bytes: 1528
a,b,k = map(int, input().split())

l = []

greatest = a

if(b > a):
  greatest = b
  
for i in range(1, (greatest + 1)):
  if(a % i == 0 and b % i == 0):
    l.append(i)
    
print(str(l[len(l) - int(k)]))

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

const int moder = 998244353;
const int N = 200010;

char s[N];
int ans[N];

int main(){
    int n;
    scanf("%d%s", &n, s);
    std::vector <int> fact;
    for (int i = 1; i <= n; ++ i){
        if (n % i){
            continue;
        }
        if (n / i % 2 == 0){
            continue;
        }
        fact.push_back(i);
        int sum = 0;
        for (int j = 0; j < i; ++ j){
            sum = 2 * sum + s[j] - '0';
            sum -= sum >= moder ? moder : 0;
        }
        int sig = 0;
        for (int j = 0; j < n; ++ j){
            int real = (s[j % i] - '0') ^ ((j / i) & 1);
            if (sig == 0 && s[j] - '0' != real){
                sig = real > s[j] - '0' ? 1 : -1;
            }
        }
        if (sig <= 0){
            ++ sum;
            sum -= sum >= moder ? moder : 0;
        }
        ans[i] = sum;
    }
    for (auto u : fact){
        for (auto v : fact){
            if (v >= u){
                break;
            }
            if (u % v == 0){
                ans[u] -= ans[v];
                ans[u] += ans[u] < 0 ? moder : 0;
            }
        }
    }
    int ret = 0;
    for (int i = 1; i <= n; ++ i){
        ret = (ret + 2ll * i * ans[i]) % moder;
    }
    printf("%d\n", ret);
    return 0;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define repp(i,m,n) for(int (i)=(m);(i)<(n);(i)++)
#define repm(i,n) for(int (i)=(n-1);(i)>=0;(i)--)
#define INF (1ll<<60)
#define all(x) (x).begin(),(x).end()
typedef long long lint;
const lint MOD =1000000007;
const lint MAX = 10000000;
using Graph =vector<vector<lint>>;
typedef pair<lint,lint> P;

 
lint fac[MAX], finv[MAX], inv[MAX];

void COMinit() // 二項係数を求める時は前処理としてCOMinit()をする
{
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (lint i = 2; i < MAX; i++)
    {
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}
 
// 二項係数計算
long long COM(lint n, lint k)
{
    if (n < k)
        return 0;
    if (n < 0 || k < 0)
        return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

lint primary(lint num)
{
    if (num < 2) return 0;
    else if (num == 2) return 1;
    else if (num % 2 == 0) return 0; // 偶数はあらかじめ除く

    double sqrtNum = sqrt(num);
    for (int i = 3; i <= sqrtNum; i += 2)
    {
        if (num % i == 0)
        {
            // 素数ではない
            return 0;
        }
    }

    // 素数である
    return 1;
}
   long long modpow(long long a, long long n, long long mod) {
    long long res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}
    lint dp[105][100005];
  int main(){
       lint N,W;
       cin>>N>>W;
    lint w[N];
    lint v[N];
    rep(i,N){
        cin>>w[i]>>v[i];
    }
    rep(i,100005){
        dp[0][i]=INF;
    }
    dp[0][0]=0;
    rep(i,N){
        rep(j,100005){
            if(v[i]<=j)dp[i+1][j]=min(dp[i][j],dp[i][j-v[i]]+w[i]);
            else dp[i+1][j]=dp[i][j];
            
        }
    }
    lint ans=0;
        rep(j,100005){
            if(dp[N][j]<=W)ans=max(ans,(lint)j);
        }
    
    cout<<ans;
    }
     
  


Measured memory_bytes: 80128
//g++ -std=gnu++14 a.cpp

#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <iostream>
#include <istream>
#include <iterator>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#include <tuple>
#include <iomanip>
#include <random>
#include <math.h>

using namespace std;

#define ll long long
#define rep(i, n) for(ll i = 0; i < (n); i++)
ll MOD = 1e9 + 7;
int INF = 1 << 30;
ll INFL = 1LL << 60;

int main(){
  string S;
  cin >> S;
  bool hantei = false;
  rep(i,3){
    if(S.at(i) == '7'){
      hantei = true;
    }
  }
  if(hantei){
    cout << "Yes" << endl;
  }else{
    cout << "No" << endl;

  }

 }


Measured memory_bytes: 3628
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, N) for (int i = 0; i < (int)N; ++i)
#define all(a) (a).begin(), (a).end()

int N;

struct Statement {
  int x, y;
};

int main() {
  cin >> N;
  vector<int> A(N);
  vector<vector<Statement>> s(N);

  rep(i, N) {
    cin >> A[i];
    s[i].resize(A[i]);
    rep(j, A[i]) {
      cin >> s[i][j].x >> s[i][j].y;
      --s[i][j].x;
    }
  }

  int ans = 0;
  rep(i, (1 << N)) {
    bool valid = true;
    bitset<20> b(i);
    rep(j, N) {
      if (b[j]) rep(k, A[j]) {
          if (b[s[j][k].x] != s[j][k].y) {
            valid = false;
          }
        }
    }

    if (valid) ans = max(ans, (int)b.count());
  }

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
/***********************
*  Author: xuziyuan    * 
***********************/

#include <bits/stdc++.h>

#define rt0 return 0
#define rep(i,n) for(int i=0;i<n;i++)
#define repn(i,n) for(int i=1;i<=n;i++)
#define replet(c) for(char c='a';c<='z';c++)
#define LL long long
#define pii pair <int,int>
#define pb push_back
#define fi first
#define se second
#define mpr make_pair
#define sqr(a) ((a)*(a))

using namespace std;

const LL MOD=1e9+7;

int n,a,b,c,d;
string s;

int main()
{
	cin>>n>>a>>b>>c>>d>>s;
	a--;
	b--;
	c--;
	d--;
	for(int i=a;i<c;i++) if(s[i]=='#'&&s[i+1]=='#') puts("No"),exit(0);
	for(int i=b;i<d;i++) if(s[i]=='#'&&s[i+1]=='#') puts("No"),exit(0);
	if(d>c) puts("Yes"),exit(0);
	for(int i=b;i<=d;i++) if(s[i-1]=='.'&&s[i]=='.'&&s[i+1]=='.') puts("Yes"),exit(0);
	puts("No");
	rt0;
}

Measured memory_bytes: 640
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file 
#include <ext/pb_ds/tree_policy.hpp> 
#include <functional> // for less 
#define pb push_back
#define For(i,s,e) for (ll i=(s); i<(e); i++)
#define Debug_array(a,n) for (ll i=(0); i<(n); i++) cout<<a[i]<<" "
#define Foe(i,s,e) for (ll i=(s); i<=(e); i++)
#define Fod(i,s,e) for (ll i=(s)-1; i>=(e); i--)
#define Mod 1000000007
#define pii pair<ll,ll>
#define fi first
#define se second
#define endl "\n"
#define mp make_pair
#define big_prime 15486277
#define bigger_prime 179424697
#define biggest_prime 32416188691
//#define random_shuffle(indices.begin(), indices.end());
//std::random_device rd;
//std::mt19937 g(rd());
//std::shuffle(v.begin(), v.end(), g);
using namespace __gnu_pbds; 
using namespace std;

typedef long long ll;
typedef tree<ll, null_type, less<ll>, rb_tree_tag,tree_order_statistics_node_update> ordered_set; 

#define MAX 5002

int main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	ll f[26];
	memset(f,0,sizeof(f));
	string s;cin>>s;
	For(i,0,s.size()) f[s[i]-'A']++;

	ll count=0;
	For(i,0,26) if(f[i]>0) count++;

	if(count==2 && f[s[0]-'A']==2){
		cout<<"Yes"<<endl;
	}else{
		cout<<"No"<<endl;
	}










	
}

Measured memory_bytes: 764
package main

import "fmt"

func main() {
	// Code for B - Template Matching
	var N, M int
	fmt.Scanf("%d %d", &N, &M)

	A := make([]string, N)
	B := make([]string, M)

	for i := 0; i < N; i++ {
		fmt.Scanf("%s", &A[i])
	}

	for i := 0; i < M; i++ {
		fmt.Scanf("%s", &B[i])
	}

	var flag1, flag2 int
	for i := 0; i < (N - M + 1); i++ {
		for j := 0; j < (N - M + 1); j++ {
			flag1 = 0
			for k := 0; k < M; k++ {
				//fmt.Println(A[i][j:j+M], B[k][0:M])
				if A[i+k][j:j+M] != B[k][0:M] {
					flag1 = 1
				}
			}
			if flag1 == 0 {
				flag2 = 1
				break
			}
		}
	}

	if flag2 == 0 {
		fmt.Println("No")
	} else {
		fmt.Println("Yes")
	}
}


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

long long MOD = 1000000007;

int  main(){
    //input
    long long D;
    string S;
    cin >> S;
    cin >> D;
    long long keta=S.length();
    long long N[keta];
    long long i,k, digit;
    long long j;
    for(i=0; i<keta; i++){
        N[i]=(long long)(S[i]-'0');
    }

    //calc
    long long dp[keta][2][D];
    for(i=0; i<keta; i++){
        for(j=0; j<=1; j++){
            for(k=0; k<D; k++){
                dp[i][j][k]=0;
            }
        }
    }
    for(digit=0; digit<10; digit++){
        if(digit<N[0]){
            dp[0][1][digit%D]++; 
        }else if(digit==N[0]){
            dp[0][0][digit%D]++;
        }
    }
    for(i=0; i<keta-1; i++){
        for(j=0; j<=1; j++){
            for(k=0; k<D; k++){
                for(digit=0; digit<(j?10:N[i+1]+1); digit++){
                    dp[i+1][j||(digit<N[i+1])][(k+digit)%D]+=dp[i][j][k];
                    dp[i+1][j||(digit<N[i+1])][(k+digit)%D]%=MOD;
                }
            }
        }
    }

    cout << (dp[keta-1][0][0]+dp[keta-1][1][0]-1+MOD)%MOD << endl;
    system("pause");
    return 0;
}

Measured memory_bytes: 19324
import java.io.PrintStream;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) throws Exception{
		new Main(new Scanner(System.in), System.out, System.err).exec();
	}
	public final Scanner sc;
	public final PrintStream out, err;
	public Main(final Scanner sc, final PrintStream out, final PrintStream err) {
		this.sc = sc;this.out = out;this.err = err;
	}
	static public final long pair(int a, int b) {return (((long)a) << 32) + b;}
	static public final int getPair1(long v) {return (int)(v >> 32);}
	static public final int getPari2(long v) {return (int)(v & 0xFFFFFFFF);}

	static public final long quad(long a, long b, long c, long d) {
		return ((a&0xFFFF)<< 48) + ((b&0xFFFF)<< 32) + ((c&0xFFFF)<< 16) +(d&0xFFFF);}
	static public final int getQuad1(long v) {return (int)( v >> 48          );}
	static public final int getQuad2(long v) {return (int)((v >> 32) & 0xFFFF);}
	static public final int getQuad3(long v) {return (int)((v >> 16) & 0xFFFF);}
	static public final int getQuad4(long v) {return (int)( v        & 0xFFFF);}

	static public final long record(int e, int m, int i) {
		return quad(-1, e, m, i);
	}
	static public final int re(long record) {
		return getQuad2(record);
	}
	static public final int rm(long record) {
		return getQuad3(record);
	}
	static public final int ri(long record) {
		return getQuad4(record);
	}

	//------------------------------------------

	private int p;
	private int[] inv;
	private int[] fact;
	private int[] finv;
	public final int mod(long v) {
		v %= p;
		return (int)(v < 0 ? v+p : v);
	}
	public final int mul(long a, long b) {
		return mod(a*b);
	}
	public final void initFact(double limit, double p) {
		initFact((int)limit, (int)p);
	}
	public final void initFact(int limit, int p) {
		this.p = p;
		this.inv = new int[limit+1];
		this.fact = new int[limit+1];
		this.finv = new int[limit+1];
		fact[1] = finv[1] = inv[0] = inv[1] = 1;
		for(int i=2;i<=limit;i++) {
			int a = p / i;
			int b = p % i;
			inv[i]  = mul(-a, inv[b]);
			fact[i] = mul(fact[i-1], i);
			finv[i] = mul(finv[i-1], inv[i]);
		}
	}
	public final int comb(int m, int n) {
		return mul(mul(fact[m], finv[n]), finv[m-n]);
	}
	//------------------------------------------
	static long lcm (long a, long b) {
		long temp;
		long c = a;
		c *= b;
		while((temp = a%b)!=0) {
			a = b;
			b = temp;
		}
		return (long)(c/b);
	}

	//------------------------------------------



	public void exec() throws Exception{
		final int N = sc.nextInt();
		final int K = sc.nextInt();
		StringBuilder sb = new StringBuilder();

		int a = N;
		while(a > 0) {
			int b = a % K;
			a = a / K;
			sb.insert(0, b);
		}
		out.println(sb.toString().length());

	}
}


Measured memory_bytes: 21844
#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
#include<string>
#include<tuple>
#include<utility>
#include<stack>
#include<iomanip>
using namespace std;

using ll=long long int;


int main() {

	int n;
	cin >> n;

	vector <string> w(n);

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

	bool ans = true;

	for (int i = 0; i < n - 1; i++) {
		if (w[i].back() != w[i + 1].front()) {
			ans = false;
		}
	}

	for (int i = 0; i < n; i++) {
		for (int j = i + 1; j < n; j++) {
			if (w[i] == w[j]) {
				ans = false;
			}
		}


	}

	if (ans) {
		cout << "Yes" << endl;
	}

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





Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
void oj()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
	return;
}

int main()
{
	//oj();
	int n;string s;
	cin>>n>>s;
	for(int i=0;i<s.length();i++){
		if(i<n){
			cout<<s[i];
		}else{
			cout<<"...";
			break;
		}
	}
	return 0;
}

Measured memory_bytes: 3628
n = int(input())
h = list(map(int, input().split())) + [0]

ans, cnt = 0, sum(h)
while cnt > 0:
    l, r = -1, n
    for i, hi in enumerate(h):
        if l == -1 and hi > 0:
            l = i
        if l > -1 and hi == 0:
            r = i
            ans += 1
            cnt -= r - l
            for j in range(l, r):
                h[j] -= 1
            break
print(ans)


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

#define int long long
#define fi first
#define se second
#define rep(i,n) for(int i=0;i<(int)(n);++i)
#define rep1(i,n) for(int i=1;i<=(int)(n);++i)
#define rep11(i,n) for(int i=1;i<(int)(n);++i)
#define repo(i,o,n) for(int i=o;i<(int)(n);++i)
#define repm(i,n) for(int i=(int)(n)-1;i>=0;--i)
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define sperase(v,n) (v).erase(remove(all(v), n), (v).end())
#define vdelete(v) (v).erase(unique(all(v)), (v).end())
#define pb(n) push_back(n)
#define mp make_pair
#define MOD 1000000007
#define INF LONG_LONG_MAX

int n,a[20],b[20],c[20],ans;

signed main() {
    cin >> n;
    rep(i,n) cin >> a[i];
    rep(i,n) cin >> b[i], ans += b[i];
    rep(i,n-1) cin >> c[i];
    rep11(i,n) {
        if (a[i-1]+1 == a[i]) ans += c[a[i-1]-1];
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
// ABC064A - RGB Cards

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

int main() {
	int r, g, b;
	cin >> r >> g >> b;

	if ((g * 10 + b)% 4 == 0) {
		cout << "YES" << endl;
	} else {
		cout << "NO" << endl;
	}

	return 0;
}


Measured memory_bytes: 256
alist = list(map(int,input().split()))
alist.sort()
a = alist[2]
b = alist[1]
c = alist[0]

ans = 0

if b%2 == c%2:
    while c < b:
        c += 2
        ans += 1
    
    ans += a-b
    print(ans)
else:
    ans += 1
    a += 1
    b += 1
    while c < b:
        c += 2
        ans += 1
    
    ans += a-b
    print(ans)


Measured memory_bytes: 38384
#include <bits/stdc++.h>
#include <algorithm>
#include <queue>
using namespace std; 
int N; 
vector<int> V[100010] = {}; 
int Sn[100010] = {}, Fe[100010] = {}; 
int main(){
	cin >> N; 
	for(int i = 0; i < N-1; i++){
		int a, b; 
		cin >> a >> b; 
		V[a].push_back(b); 
		V[b].push_back(a); 
	}
	for(int i = 1; i <= N; i++){
		Sn[i] = 114514;
		Fe[i] = 114514; 
	}
  	Sn[N] = 0, Fe[1] = 0; 
	queue<int> que;
	que.push(1); 
	while(que.size()){
		int p = que.front(); que.pop(); 
		for(int i = 0; i < V[p].size(); i++){
			int n = V[p].at(i);  
			if(Fe[n] == 114514){
				que.push(n); 
				Fe[n] = Fe[p] + 1; 
			}
		}
	}
	que.push(N); 
	while(que.size()){
		int p = que.front(); que.pop(); 
		for(int i = 0; i < V[p].size(); i++){
			int n = V[p].at(i);  
			if(Sn[n] == 114514){
				que.push(n); 
				Sn[n] = Sn[p] + 1; 
			}
		}
	}
	int count = 0; 
	for(int i = 1; i <= N; i++){
		if(Sn[i] >= Fe[i]) count ++; 
		else count --; 
	}
	if(count > 0) cout << "Fennec" << endl; 
	else cout << "Snuke" << endl; 
}

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

int main(){
    int a, b, c, d;
    cin >> a>>b>>c>>d;
    int taka = a/d;
    if(a%d == 0) taka--;
    int ao = c/b;
    if(c%b == 0) ao--;

    if(taka >= ao) cout << "Yes" <<endl;
    else cout << "No" <<endl;

    return 0;
}

Measured memory_bytes: 3632
#include <iostream>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <string>
using namespace std;

int main() {
	string str;
	int n;
	cin >> str >> n;
	for(int i=0; i<n; i++){
		string cmd, w, tmp;
		int first, second;
		cin >> cmd >> first >> second;
		if(cmd == "replace"){
			cin >> w;
			str = str.replace(first, second-first+1, w);
		}else if(cmd == "reverse"){
			tmp = str.substr(first, second-first+1);
			for(int i=0; i<tmp.size();i++){
				str[second-i] = tmp[i];
			}
		}else{
			cout << str.substr(first,second-first+1) << endl;	
		}
	}
	//printf("%s\n", t);
	return 0;
}


Measured memory_bytes: 3200
n,m = map(int,input().split())
p = []
s = []

for i in range(m):
  p1,s1 = map(str,input().split())
  p.append(int(p1))
  s.append(s1)

#0が正答したかどうか（正答が1）、1がペナルティの数
ans = [[0,0] for i in range(n)]

for i in range(m) :
  if s[i] == 'AC' :
    ans[p[i]-1][0] = 1
  if s[i] == 'WA' and ans[p[i]-1][0] == 0 :
    ans[p[i]-1][1] += 1

ac = 0
pe = 0
for i in range(n) :
  ac += ans[i][0]
  if ans[i][0] == 1 :
    pe += ans[i][1]

print(ac,pe)

Measured memory_bytes: 23548
from sys import setrecursionlimit, exit
setrecursionlimit(1000000000)

def main():
    mod = 1000000007
    n, k = map(int, input().split())
    ans = 0
    for i in range(k, n + 2):
        ans += i * (2 * n - i + 1) // 2 - i * (i - 1) // 2 + 1
        ans %= mod
    print(ans)

main()

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

// template {{{
#define  range(i, l, r) for (int i = (int)(l); i < (int)(r); (i) += 1)
#define rrange(i, l, r) for (int i = (int)(r) - 1; i >= (int)(l); (i) -= 1)

#define  whole(f, x, ...) ([&](decltype((x)) container) { return (f)(  begin(container),  end(container), ## __VA_ARGS__); })(x)
#define rwhole(f, x, ...) ([&](decltype((x)) container) { return (f)( rbegin(container), rend(container), ## __VA_ARGS__); })(x)

#define debug(x) cerr << "(" << __LINE__ << ")" << #x << ": " << (x) << endl

using i32 = int;
using u32 = unsigned int;
using i64 = long long;
using u64 = unsigned long long;

// constexpr i32 mod   = 998244353;
constexpr i32 mod   = 1e9 + 7;
constexpr i32 inf   = 1001001001;
constexpr i64 infll = 1001001001001001001ll;

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

struct IoSetup { IoSetup(int x = 15){ cin.tie(0); ios::sync_with_stdio(0); cout << fixed << setprecision(x); cerr << fixed << setprecision(x); } } iosetup;

template <typename T = i64> T input() { T x; cin >> x; return x; }

template <typename T> ostream &operator<<(ostream &os, vector<T> &v) { range(i, 0, v.size()) { os << v[i] << (i + 1 != v.size() ? " " : ""); } return os; }
template <typename T> istream &operator>>(istream &is, vector<T> &v) { for (T &in : v) is >> in; return is; }

template <typename T1, typename T2> ostream &operator<<(ostream &os, pair<T1, T2> p) { os << "(" << p.first << ", " << p.second << ")"; return os; }
template <typename T1, typename T2> istream &operator>>(istream &is, pair<T1, T2> &p) { is >> p.first >> p.second; return is; }

template <typename T> vector<T> make_vector(size_t a, T b) { return vector<T>(a, b); }
template <typename... Ts> auto make_vector(size_t a, Ts... ts) { return vector<decltype(make_vector(ts...))>(a, make_vector(ts...)); }

template <typename T1, typename T2> inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }
template <typename T1, typename T2> inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); }
// }}}

void solver() {
    int n = input();
    vector< int > as(n);
    cin >> as;

    auto G = make_vector(n, 0, 0);
    range(i, 1, n) {
        int u = input() - 1, v = input() - 1;
        G[u].push_back(v);
        G[v].push_back(u);
    }

    vector< int > dp(n + 1, inf);
    vector< int > ans(n);

    function<void(int, int)> dfs = [&](int v, int p) {
        auto iter = whole(lower_bound, dp, as[v]);
        auto x = *iter;
        *iter = as[v];
        ans[v] = whole(lower_bound, dp, inf) - dp.begin();

        for (auto u: G[v]) {
            if (p == u) continue;
            dfs(u, v);
        }

        *iter = x;
    };

    dfs(0, -1);

    for (auto x: ans) cout << x << endl;
}

signed main(int argc, char *argv[]) {
    solver();
}


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

int comb(int N, int r){
  if (r == 1){
    return N;
  } else if (N == r){
    return 1;
  } else {
    return comb(N-1, r) + comb(N-1, r-1);
  }
}

int main(){
  int N, M;
  int ans = 0;

  cin >> N >> M;

  if (N >= 2){
    ans += comb(N, 2);
  }
  if (M >= 2){
    ans += comb(M, 2);
  }

  if (N + M == 2){
    if (N == 2 || M == 2){
      ans = 1;
    } else {
      ans = 0;
    }
  }

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
int main(){

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);


string s;
cin>>s;
ll i;

    if(s[2]==s[3]&&s[4]==s[5])
    {
cout<<"Yes";
    }
else
{
    cout<<"No";
}






return 0;}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <string>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define REP(i, n) for (int i = 0; i < (n); i++)
#define RREP(i, n) for (int i = (n) - 1; i >= 0; i--)
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define RFOR(i, a, b) for (int i = (a); i > (b); i--)
#define ALL(a) (a).begin(), (a).end()

int main() {
    string S;
    cin >> S;
    if (S[S.size() - 1] == 's') cout << S << "es" << endl;
    else cout << S << "s" << endl;
    return 0;
}

Measured memory_bytes: 3632
N = int(input())
S_n=[]
for i in range(N):
    S_n.append(input())
a,w,t,r= 0,0,0,0
for i in range(N):
    if S_n[i] =="AC":
        a+=1
    elif S_n[i] =="WA":
        w+=1
    elif S_n[i] =="TLE":
        t+=1
    elif S_n[i] =="RE":
        r+=1
print("AC x {}".format(a))
print("WA x {}".format(w))
print("TLE x {}".format(t))
print("RE x {}".format(r))

Measured memory_bytes: 16328
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<tuple>
#include<map>
#include<queue>
#include<math.h>
#include<numeric>
#include<iomanip>
#define rep(i, n) rep2(i,0,n)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
#define PI acos(-1);
typedef long long ll;
using namespace std;
const int MOD = 1000000007;
//scanf("%d", &a); '\n'; cout << fixed << setprecision(10);

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int a, b, c, d;
	cin >> a >> b >> c >> d;
	while (true) {
		c -= b;
		if (c < 1) { cout << "Yes"; return 0; }
		a -= d;
		if (a < 1) { cout << "No"; return 0; }
	}
}

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

int N;
long long A[100000];

int main() {
  cin >> N;
  for(int i = 0; i < N; ++i) cin >> A[i];
  sort(A, A + N);
  long long acc = 0, leftmost = -1;
  for(int i = 0; i < N; ++i) {
    if(2 * acc < A[i]) leftmost = i;
    acc += A[i];
  }
  cout << N - leftmost << endl;
  return 0;
}


Measured memory_bytes: 1024
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)*}
    };
}

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)*}
    };
}

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")
    };
}

fn main(){

    input!{
        k: usize,
        s: chars,
    }

    let ss: String = s.into_iter().collect();
    
    let mut ans = "".to_string();

    if ss.len() <= k {
        println!("{}", ss);
    } else {
        for (i, c) in ss.chars().enumerate() {
            if i < k {
                ans.push(c);
            }
        }
        ans = ans + "...";
        println!("{}", ans);
    }

}

Measured memory_bytes: 2164
#include<iostream>
#include<map>
#include<cstdlib>

using namespace std;

char s[1234567];
char *p;

typedef map<map<char,int>,int> E;

E exp();

E mul(){
  while(*p==' '){
    p++;
  }
  if(isdigit(*p)){
    E e;
    e[map<char,int>()]=strtol(p,&p,10);
    return e;
  }else if(*p=='('){
    p++;
    auto r=exp();
    while(*p==' '){
      p++;
    }
    p++;
    return r;
  }else{
    char c=*p;
    p++;
    while(*p==' '){
      p++;
    }
    int pw;
    if(*p!='^'){
      pw=1;
    }else{
      p++;
      pw=strtol(p,&p,10);
    }
    map<char,int> v;
    v[c]=pw;
    E e;
    e[v]=1;
    return e;
  }
}

E term(){
  auto l=mul();
  for(;;){
    while(*p==' '){
      p++;
    }
    if(!isalnum(*p)&&*p!='(')break;
    auto lo=l;
    l.clear();
    auto r=mul();
    for(auto &e:lo){
      for(auto &f:r){
	map<char,int> v;
	for(auto &ee:e.first){
	  v[ee.first]+=ee.second;
	}
	for(auto &ff:f.first){
	  v[ff.first]+=ff.second;
	}
	l[v]+=e.second*f.second;
      }
    }
  }
  return l;
}

E exp(){
  auto l=term();
  for(;;){
    while(*p==' '){
      p++;
    }
    int f;
    if(*p=='+'){
      f=1;
    }else if(*p=='-'){
      f=-1;
    }else{
      break;
    }
    p++;
    auto r=term();
    for(auto &e:r){
      l[e.first]+=f*e.second;
    }
  }
  return l;
}

E startexp(){
  p=s;
  auto r=exp();
  for(auto it=r.begin();it!=r.end();){
    if(it->second==0){
      it=r.erase(it);
    }else{
      it++;
    }
  }
  // for(auto e:r){
  //   cout<<e.second;
  //   for(auto f:e.first){
  //     cout<<f.first<<f.second;
  //   }
  //   cout<<'*';
  // }
  // cout<<endl;
  return r;
}

int main(){
  while(cin.getline(s,sizeof s),s[0]!='.'){
    auto ans=startexp();
    while(cin.getline(s,sizeof s),s[0]!='.'){
      auto c=startexp();
      cout<<((ans==c)?"yes":"no")<<endl;
    }
    cout<<"."<<endl;
  }
}

Measured memory_bytes: 1684
#include <stdio.h>
#include <iostream>
#include <map>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

using ll = long long;
//constexpr ll N = 2e5;
//ll a[N];

//constexpr int max = 2147483647;



int main()
{
	
	string str;
	cin >> str;

	string rev = str;
	reverse(rev.begin(), rev.end());

	string p, q;
	p = str.substr(0, (str.length() - 1) / 2);
	q = str.substr((str.length() +3) / 2  -1 , str.length()  - 1);
		
	string rev_p = p, rev_q = q;
	reverse(rev_p.begin(), rev_p.end());
	reverse(rev_q.begin(), rev_q.end());
	/*cout << p;
	cout << q;*/

	if (rev == str && rev_p == p && rev_q == q) {
		cout << "Yes";
	}
	else {
		cout << "No";
	}
	
	
	return 0;
}

Measured memory_bytes: 256
/* Alohomora */
#include<bits/stdc++.h>
#define ll         long long
#define fl(i,n)    for(i=0;i<n;i++)
#define fld(i,a,b) for(i=a;i>b;i--)
#define fli(i,a,n) for(i=a;i<n;i++)
#define inp(i,a,n) for(i=0;i<n;i++) {cin>>a[i];}
#define op(i,a,n)  for(i=0;i<n;i++) {cout<<a[i]<<" ";}
#define pb         push_back
#define mp         make_pair
#define mod        1000000007 
#define speedup    ios_base::sync_with_stdio(false),cin.tie(0)
using namespace std;
ll fact(ll n){ if(n==0){return 1;}return (n*fact(n-1))%mod;}
ll power(ll x, ll y){ll out = 1;while (y > 0){if (y & 1) out=(out*x)%mod;y = y>>1;x = (x*x)%mod;}return out%mod;}
ll inverse(ll a){return power(a,mod-2);}
ll gcd(ll a,ll b){if(b==0){return a;}gcd(b,a%b);}
ll a[2000000];
void sieve(){ll i,j;fli(i,2,1000001){if(a[i]==0){for(j=i*i;j<1000001;j+=i){a[j]=1;}}}}
map<ll,vector<pair<ll,ll> > >m1;
vector<ll>v1;
bool compar(const pair<ll,ll> &a, const pair<ll,ll> &b) 
{ 
    return (a.second < b.second);
} 
ll ans=0;
vector<ll>root;
/*void calldfs(ll v,int visit[])
{
 visit[v]=1;
 for(int i=0;i<m1[v].size();i++)
 {
  if(visit[m1[v][i]]==0)
  {
   calldfs(m1[v][i],visit);
  }
 }
}
void dfs(ll n)
{
 ll i;
 int visit[1000000]={0};
 fli(i,1,n+1)
 {
  visit[i]=0;
 }
 fli(i,1,n+1)
 {
  if(visit[i]==0)
  {
   calldfs(i,visit);
   ans++;
  } 
 }
}*/
ll color[1000000];
void bfs(ll root)
{
 ll i;
 fli(i,1,1000000)
 color[i]=-1;
 queue<ll>q1;
 q1.push(root);
 color[root]=0;
 
 ll temp;
 while(!q1.empty())
 {
  temp=q1.front();
  for(int i=0;i<m1[temp].size();i++)
  {
   if(color[m1[temp][i].first]==-1)
   {
   if(m1[temp][i].second%2)
   {
    color[m1[temp][i].first]=color[temp]^1;
   }
   else
   {
    color[m1[temp][i].first]=color[temp];
   }
   q1.push(m1[temp][i].first);
   }
  }
  q1.pop();
 }
}
void comp()
{
 ll n,m,i;
 //int arr[1000000]={0};
 cin>>n;
 int arr[1000000]={0};
 ll u,v,z;
 fl(i,n-1)
 {
  cin>>u>>v>>z;
  m1[u].pb(mp(v,z));
  m1[v].pb(mp(u,z));
  arr[v]=1;
 }
 ll root;
 fli(i,1,n+1)
 {
  if(arr[i]==0)
  {
   root=i;
   break;
  }
 }
 bfs(root);
 fli(i,1,n+1)
 {
  cout<<color[i]<<"\n";
 }
} 
int main()
{
	speedup;
	ll i=0,t;
	ll n;
	//cin>>t;
	t=1;
	while(t--)
	{
	 comp();
	}
}

Measured memory_bytes: 25472
#include <bits/stdc++.h>
#include <unordered_map>
#define ll long long int
#define pb push_back
#define mp make_pair
#define mod 1000000007
#define rep(i,n) for(ll i=0;i<n;i++)
#define all(c) (c).begin(),(c).end()
#define max3(a,b,c) max(max(a,b),c)
#define min3(a,b,c) min(min(a,b),c)
#define vi vector <int>
#define vs vector <string>
#define vc vector <char>
#define vl vector <ll>
using namespace std;
ll gcd(ll a, ll b) { if (a == 0) return b; return gcd(b % a, a); } 
ll power(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll modInverse(ll a){return power(a,mod-2);}
const int N=500023;
bool vis[N];
vector <int> adj[N];
ll max(ll a, ll b)
{
    if(a>b) return a;
    return b;
}
 
void solve()
{
    int n, m, k;
    cin>>n>>m>>k;
 
    vi a(n);
    rep(i, n) cin>>a[i];
 
    vi b(m);
 
    rep(i, m) cin>>b[i];
 
    vl pref_a(n+1);
    vl pref_b(m+1);
 
    pref_a[0] = pref_b[0] = 0;
 
    for(int i = 1; i <= n; i++)
    {
        pref_a[i] = pref_a[i-1] + a[i-1];
 
    }
 
    for(int i = 1; i <= m; i++)
    {
        pref_b[i] = pref_b[i-1] + b[i-1];
    }
 
    ll ans = 0;
 
    for(int i = 0; i <= n; i++)
    {
        ll rem = k - pref_a[i];
        if(rem < 0) break;
        auto it = upper_bound(all(pref_b), rem);
        ans = max(ans, i + (it - pref_b.begin() - 1));
 
    }
    cout<<ans<<endl;
}
 
int main()
{
    int T=1;
    // cin>>T;
    int t=0;
    while(t++<T)
    {
        // cout<<"Case #"<<t<<":"<<' ';
        solve();
        // cout<<'\n';
    }
    //cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
}

Measured memory_bytes: 19620
N = int(input())
co = [[int(i) for i in input().split()] for i in range(N)]
co = sorted(co)
d = {}
m = 0
for i in range(N):
    for j in range(i+1, N):
        a = co[i][0]-co[j][0]
        b = co[i][1]-co[j][1]
        if (a, b) in d:
            d[a,b] += 1
        else:
            d[a,b] = 1
for k in d.values():
    m = max(m, k)
print(N-m)

Measured memory_bytes: 39408
#include <iostream>
#include <queue>
using namespace std;
typedef pair<int, int> P;
const int MAX_HW = 1000;
int n, h, w, rat, s[2], g[2], flag[MAX_HW+1][MAX_HW+1][2];
int town[MAX_HW+1][MAX_HW+1];
char town2[MAX_HW+1][MAX_HW+1];
queue <P> que;
P p;
void bfs(int sy, int sx){
	que.push(P(sy, sx));
	flag[sy][sx][0]=rat;
	while (que.size()){
	RE:
		p = que.front();
		que.pop();
		for (int i = -1; i <= 1; i++){
			for (int j = -1; j <= 1; j++){
				if (i == 0 || j == 0){
					if (town2[p.first + i][p.second + j] != 'X'&&flag[p.first + i][p.second + j][0] != rat&&p.first + i < h&&p.first + i >= 0 && p.second + j < w&&p.second + j >= 0) {
							flag[p.first+i][p.second+j][0] = rat;
							flag[p.first + i][p.second + j][1] = flag[p.first][p.second][1] + 1;
							if (town[p.first + i][p.second + j] == rat){
							if (rat == n) return;
							rat++;
							flag[p.first+i][p.second+j][0] = rat;
							while (que.size()){
								que.pop();
							}
							que.push(P(p.first + i, p.second + j));
							goto RE;
						}
						else{
						que.push(P(p.first + i, p.second + j));
						}
					}
				}
			}
		}
	}
}
int main(){
	cin >> h >> w >> n;
	rat = 1;
	for (int i = 0; i < h; i++){
		for (int j = 0; j < w; j++){
			cin >> town2[i][j];
			town[i][j] = town2[i][j] - 48;
			if (town2[i][j] == 'S'){
				s[0] = i;
				s[1] = j;
			}
			if (town[i][j] == n){
				g[0] = i;
				g[1] = j;
			}
		}
	}
	bfs(s[0], s[1]);
	cout << flag[g[0]][g[1]][1] << endl;
	return 0;
}

Measured memory_bytes: 13932
using System;
using System.Linq;
using System.Collections.Generic;
using static System.Console;
using static System.Math;

class Solver {
    Scanner sc = new Scanner();

    public void Solve() {
        var N = sc.nextInt();
        var K = sc.nextInt();
        var S = sc.next();
        var lst = new List<int>();
        var cnt = 1;
        for (int i = 1; i < N; i++) {
            if (S[i] == S[i-1]) {
                cnt++;
            } else {
                lst.Add(cnt);
                cnt = 1;
            }
        }
        lst.Add(cnt);

        var len = 0;
        if (S[0] == '1') {
            len = (2 * K) + 1;
        } else {
            len = 2 * K;
        }

        if (len >= lst.Count) {
            WriteLine(lst.Sum());
            return;
        }

        var sum = lst.Take(len).Sum();
        var ans = sum;
        len = (2 * K) + 1;
        var first = 0;
        if (S[0] == '0') {
            first = 1;
        }
        sum = lst.Skip(first).Take(len).Sum();
        ans = Max(ans, sum);


        for (int i = first + len + 1; i < lst.Count; i += 2) {
            sum += lst[i] + lst[i - 1];
            sum -= lst[i - len] + lst[i - (len + 1)];
            ans = Max(ans, sum);
        }

        if (S[N-1] == '1') {
            len = (2 * K) + 1;
        } else {
            len = 2 * K;
        }
        lst.Reverse();
        sum = lst.Take(len).Sum();
        ans = Max(ans, sum);


        WriteLine(ans);
    }
}

class Scanner {
    string[] s;
    int i;

    char[] cs = new char[] { ' ' };

    public Scanner() {
        s = new string[0];
        i = 0;
    }

    public string next() {
        if (i < s.Length) return s[i++];
        string st = Console.ReadLine();
        while (st == "") st = Console.ReadLine();
        s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
        if (s.Length == 0) return next();
        i = 0;
        return s[i++];
    }

    public int nextInt() {
        return int.Parse(next());
    }
    public int[] ArrayInt(int N, int add = 0) {
        int[] Array = new int[N];
        for (int i = 0; i < N; i++) {
            Array[i] = nextInt() + add;
        }
        return Array;
    }

    public long nextLong() {
        return long.Parse(next());
    }

    public long[] ArrayLong(int N, long add = 0) {
        long[] Array = new long[N];
        for (int i = 0; i < N; i++) {
            Array[i] = nextLong() + add;
        }
        return Array;
    }

    public double nextDouble() {
        return double.Parse(next());
    }

    public double[] ArrayDouble(int N, double add = 0) {
        double[] Array = new double[N];
        for (int i = 0; i < N; i++) {
            Array[i] = nextDouble() + add;
        }
        return Array;
    }
}

class Program {
    static void Main(string[] args) {
        Solver s = new Solver();
        s.Solve();
    }
}


Measured memory_bytes: 13268
#include <bits/stdc++.h>
using namespace std;
using vec_int = vector<int>;
using P = pair<int,int>;
using T = tuple<int,int,int>;
using ll = long long;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)

int charToInt(char c){
    char zero_num = '0';
    return (int)c - (int)zero_num;
}

int main(){
    int H1, M1, H2, M2, K;  cin>>H1>>M1>>H2>>M2>>K;
    


    cout << (H2-H1)*60 + (M2-M1)-K<<endl;


    return 0;
}

Measured memory_bytes: 3624
#include<iostream>
#include<sstream>
#include<vector>
#include<algorithm>
#include<set>
#include<map>
#include<queue>
#include<complex>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cassert>
using namespace std;

#define rep(i,n) for(int i=0;i<(int)n;i++)
#define fr(i,c) for(__typeof(c.begin()) i=c.begin();i!=c.end();i++)
#define pb push_back
#define mp make_pair
#define all(c) c.begin(),c.end()
#define dbg(x) cerr<<#x<<" = "<<(x)<<endl

typedef vector<int> vi;
typedef pair<int,int> pi;
typedef long long ll;
const int inf=(int)1e9;
const double EPS=1e-9, INF=1e12;

ll C(int n,int k){
	ll res=1;
	rep(i,k)res*=n-i, res/=i+1;
	return res;
}
int main(){
	int n,cnt[26]={};
	string in;
	cin>>in;
	n=in.size();
	rep(i,n)cnt[in[i]-'a']++;
	if(n%2){
		int odd=0;
		rep(i,26)if(cnt[i]%2)odd++, cnt[i]--;
		if(odd!=1){
			cout<<0<<endl; return 0;
		}
	}
	n/=2;
	rep(i,26){
		if(cnt[i]%2){
			cout<<0<<endl; return 0;
		}
		cnt[i]/=2;
	}
	ll ans=1;
	rep(i,26)ans*=C(n,cnt[i]), n-=cnt[i];
	cout<<ans<<endl;
	return 0;
}

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

int main() {
  int64_t N,X,M,Z=0,A=0;
  cin>>N>>X>>M;
  vector<int64_t> p(M);
  vector<int64_t> q;
  for(int i=1;i<=N;i++){
    if(p[X]){
      A=p[X];
      break;
    }
    p[X]=i;
    q.push_back(X);
    Z+=X;
    X*=X;
    X%=M;
  }
  if(A){
    A--;
    int64_t L=q.size();
    int64_t R=(N-L)/(L-A),S=(N-L)%(L-A),K=0;
    for(int i=0;i<L-A;i++){
      if(i==S){
        Z+=K;
      }
      K+=q[A+i];
    }
    Z+=R*K;
  }
  cout<<Z<<endl;
}

Measured memory_bytes: 4524
#include <bits/stdc++.h>
using namespace std;
#ifdef tabr
#include "library/debug.cpp"
#else
#define debug(...)
#endif

struct dsu {
    vector<int> p;
    vector<int> sz;
    int n;

    dsu(int _n) : n(_n) {
        p.resize(n);
        iota(p.begin(), p.end(), 0);
        sz.assign(n, 1);
    }

    inline int get(int x) {
        if (p[x] == x) {
            return x;
        } else {
            return p[x] = get(p[x]);
        }
    }
    inline bool unite(int x, int y) {
        x = get(x);
        y = get(y);
        if (x == y) {
            return false;
        }
        if (sz[x] > sz[y]) {
            swap(x, y);
        }
        p[x] = y;
        sz[y] += sz[x];
        return true;
    }
    inline bool same(int x, int y) {
        return (get(x) == get(y));
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    dsu uf(n);
    vector<int> x(n), y(n);
    for (int i = 0; i < n; i++) {
        cin >> x[i] >> y[i];
    }
    vector<int> order(n);
    iota(order.begin(), order.end(), 0);
    sort(order.begin(), order.end(), [&](int i, int j) {
        return x[i] < x[j];
    });
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    for (int i : order) {
        int nxt = y[i];
        while (!pq.empty() && pq.top().first < y[i]) {
            nxt = min(nxt, pq.top().first);
            uf.unite(i, pq.top().second);
            pq.pop();
        }
        pq.emplace(nxt, i);
    }
    for (int i = 0; i < n; i++) {
        cout << uf.sz[uf.get(i)] << '\n';
    }
    return 0;
}

Measured memory_bytes: 7464
#include <bits/stdc++.h>
#define int long long
using namespace std;

int dp[2000+100][2000+100];

signed main(){
	int N; cin>>N;
	vector<pair<int,int>> A(N);
	for(int i=0;i<N;i++){
		cin>>A[i].first;
		A[i].second=i;
	}
	sort(A.begin(),A.end());
	reverse(A.begin(),A.end());
	for(int x=0;x<N;x++){
		for(int y=0;y<N;y++){
			if(x+y>=N)continue;
			int a=A[x+y].first,i=A[x+y].second;
			dp[x+1][y]=max(dp[x+1][y],dp[x][y]+a*(i-x));
			dp[x][y+1]=max(dp[x][y+1],dp[x][y]+a*(N-1-y-i));
		}
	}
	int ans=0;
	for(int x=0;x<=N;x++){
		ans=max(ans,dp[x][N-x]);
	}
	cout<<ans<<endl;
}

Measured memory_bytes: 26608
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using static System.Console;

namespace AtCoder
{
    class Program
    {
        static void Main()
        {
            var X = int.Parse(ReadLine());
            WriteLine(X / 500 * 1000 + X % 500 / 5 * 5);
        }
    }
}

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

ll H, W;
vector<string> S;

bool check() {
  vector<bool> ok(W, false);
  ll cnt = 0;
  REP(i, 0, W) if(!ok[i]) {
    REP(j, i + 1, W) if(!ok[j]) {
      bool f = true;
      REP(k, 0, H) f = f && S[k][i] == S[H - 1 - k][j];
      if(f) {
        ok[i] = ok[j] = true;
        cnt += 2;
        break;
      }
    }
  }

  if(W % 2 == 1) {
    bool x = true;
    REP(i, 0, W) if(!ok[i]) {
      REP(j, 0, H) x = x && S[j][i] == S[H - 1 - j][i];
    }
    return cnt == W - 1 && x;
  }
  return cnt == W;
}

bool dfs(ll l, ll r) {
  if(r - l <= 1) return check();

  bool ret = false;
  REP(i, l + 1, r) {
    swap(S[i], S[r - 1]);
    ret = dfs(l + 1, r - 1) || ret;
    swap(S[i], S[r - 1]);
  }
  return ret;
}

int main(void) {
  cin >> H >> W;
  S.resize(H);
  REP(i, 0, H) cin >> S[i];

  bool ans = false;
  REP(i, 0, H) {
    swap(S[H / 2], S[i]);
    ans = ans || dfs(0, H);
    swap(S[H / 2], S[i]);
  }
  cout << (ans ? "YES" : "NO") << endl;;
}


Measured memory_bytes: 256
import sys
from sys import exit
from collections import deque
from copy import deepcopy
from bisect import bisect_left, bisect_right, insort_left, insort_right
from heapq import heapify, heappop, heappush
from itertools import product, permutations, combinations, combinations_with_replacement
from functools import reduce
from math import gcd, sin, cos, tan, asin, acos, atan, degrees, radians

sys.setrecursionlimit(10**6)
INF = 10**20
eps = 1.0e-20
MOD = 10**9+7

def lcm(x,y):
    return x*y//gcd(x,y)
def lgcd(l):
    return reduce(gcd,l)
def llcm(l):
    return reduce(lcm,l)
def powmod(n,i,mod=MOD):
    return pow(n,mod-1+i,mod) if i<0 else pow(n,i,mod)
def div2(x):
    return x.bit_length()
def div10(x):
    return len(str(x))-(x==0)
def intput():
    return int(input())
def mint():
    return map(int,input().split())
def lint():
    return list(map(int,input().split()))
def ilint():
    return int(input()), list(map(int,input().split()))
def judge(x, l=['Yes', 'No']):
    print(l[0] if x else l[1])
def lprint(l, sep='\n'):
    for x in l:
        print(x, end=sep)
def ston(c, c0='a'):
    return ord(c)-ord(c0)
def ntos(x, c0='a'):
    return chr(x+ord(c0))
class counter(dict):
    def __init__(self, *args):
        super().__init__(args)
    def add(self,x,d=1):
        self.setdefault(x,0)
        self[x] += d
    def list(self):
        l = []
        for k in self:
            l.extend([k]*self[k])
        return l
class comb():
    def __init__(self, n, mod=None):
        self.l = [1]
        self.n = n
        self.mod = mod
    def get(self,k):
        l,n,mod = self.l, self.n, self.mod
        k = n-k if k>n//2 else k
        while len(l)<=k:
            i = len(l)
            l.append(l[i-1]*(n+1-i)//i if mod==None else (l[i-1]*(n+1-i)*powmod(i,-1,mod))%mod)
        return l[k]
def pf(x,mode='counter'):
    C = counter()
    p = 2
    while x>1:
        k = 0
        while x%p==0:
            x //= p
            k += 1
        if k>0:
            C.add(p,k)
        p = p+2-(p==2) if p*p<x else x
    if mode=='counter':
        return C
    S = set([1])
    for k in C:
        T = deepcopy(S)
        for x in T:
            for i in range(1,C[k]+1):
                S.add(x*(k**i))
    if mode=='set':
        return S
    if mode=='list':
        return sorted(list(S))

######################################################

N,K=mint()
S=input()
j=0
tmp='1'
while j<N:
    if tmp=='1' and S[j]=='0':
        if K==0:
            j-=1
            break
        else:
            K-=1
    tmp=S[j]
    j+=1
if j==N:
    print(j)
    exit()
ans=j+1
i=-1
while True:
    if j==N-1:
        print(ans)
        exit()
    i+=1
    while True:
        if i==N-1 or (S[i]=='0' and S[i+1]=='1'):
            break
        i+=1
    j+=1
    while True:
        if j==N-1 or (S[j]=='1' and S[j+1]=='0'):
            break
        j+=1
    ans=max(ans,j-i)

Measured memory_bytes: 74380
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        int A = scanner.nextInt();

        int rem = N % 500;
        String judge = A >= rem ? "Yes" : "No";
        System.out.println(judge);
    }
}

Measured memory_bytes: 22868
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

int N;
int A[505];
int K;

int main() {
    ios_base::sync_with_stdio(false);
    cin >> N >> K;
    for(int i = 1; i <= N; i++)
        cin >> A[i];

    int sum = 0;
    for(int i = 1; i <= N; i++)
        sum += A[i];
    int ans = 1;
    for(int x = sum; x >= 1; x--) {
        if(sum % x != 0)
            continue;
        vector <int> rests;
        for(int i = 1; i <= N; i++) {
            rests.push_back(A[i] % x);
        }
        sort(rests.begin(), rests.end());
        int balance = 0;
        int r = N - 1;
        int rest = 0;
        for(int i = 0; i < N && i <= r; i++) {
            while(i <= r && balance > 0) {
                rest += x - rests[r];
                balance -= (x - rests[r--]);
            }
            if(i > r)
                break;
            rest += rests[i];
            balance += rests[i];
        }

        if(rest <= K * 2) {
            ans = x;
            break;
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int main() {
    double x1,y1,x2,y2,lx,ly,lxy;
    cin>>x1>>y1>>x2>>y2;
    lx=fabs(x2-x1);
    ly=fabs(y2-y1);
    lxy=sqrt(lx*lx+ly*ly);
    printf("%lf",lxy);
    return 0;
}


Measured memory_bytes: 3196