akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(v) v.begin(), v.end()
#define SP << " " 
#define LLi long long int

using namespace std;

int imax=2147483647;
long long int llimax=9223372036854775807;

//int型vectorを出力
void PV(vector<int> pvv) {
	rep(i, pvv.size()) cout << pvv[i] SP;
	cout << endl;
}

//LLi型vectorを出力
void PVL(vector<LLi> pvv) {
	rep(i, pvv.size()) cout << pvv[i] SP;
	cout << endl;
}

int main(){

	int n, tmp, t2, t5;
	LLi ind, ans=0;
	vector<int> d2, d5;
	vector< vector<int> > bo;
	string s;

	cin>> n;
	d2.resize(n);
	d5.resize(n);
	bo.resize(60);
	rep(i, 60) bo[i].resize(35, 0);

	rep(i, n){
		cin >> s;
		tmp=0;
		rep(j, s.size()){
			if(s[j]=='.'){
				tmp=s.size()-j-1;
				s.erase(s.begin() + j);
				break;
			}
		}
		ind=stoll(s);
		//cout<< ind <<" ";

		t2=-tmp;
		t5=-tmp;
		while(ind%2==0){
			t2++;
			ind/=2;
		}
		while(ind%5==0){
			t5++;
			ind/=5;
		}
		//cout<< t2 << " " << t5 <<endl;
		bo[10+t2][10+t5]++;
		d2[i]=t2;
		d5[i]=t5;
	}

	/*rep(i, 60){
		rep(j, 35){
			cout<< bo[i][j] << " ";
		}
		cout <<endl;
	}*/

	for(int i=0;i<94;i++){
		for(int j=0;j<=i;j++){
			if(0<=j && j<60 && 0<=i-j && i-j<35){
				if(bo[j][i-j]>0){
					rep(l, j+1){
						rep(m, i-j+1){
							bo[l][m]+=bo[j][i-j];
						}
					}
					bo[j][i-j]/=2;
				}
			}
		}
	}

	/*rep(i, 20){
		rep(j, 35){
			cout<< bo[i][j] << " ";
		}
		cout <<endl;
	}*/

	rep(i, n){
		ans+=bo[max(0, 10-d2[i])][max(0, 10-d5[i])];
		if(d2[i]>=0 && d5[i]>=0) ans--;
	}
	cout<< ans/2 <<endl;

	return 0;
}

Measured memory_bytes: 4844
package main

import "fmt"

func main() {
	var s string
	fmt.Scan(&s)

	for i := 1; i < len(s); i++ {
		t := s[0 : len(s)-i]
		if t[0:len(t)/2] == t[len(t)/2:] {
			fmt.Println(len(t))
			return
		}
	}
}


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

int main()
{
    int n, m, l;
    long *A;
    long *B;
    long *C;
    int i, j, k;
 
        cin >> n >> m >> l;

         if ((n >= 1 && n <= 100) && (m >= 1 && m <= 100) && (l >= 1 && l <= 100)) {
            try {
                A = new long[n*m];
                B = new long[m*l];
                C = new long[n*l];

                int num = 0;

                for (i = 0; i < n; i++) {
                    for (j = 0; j < m; j++) {
                        cin >> A[num];
                        num++;
                    }
                }

                num = 0;

                for (i = 0; i < m; i++) {
                    for (j = 0; j < l; j++) {
                        cin >> B[num];
                        num++;
                    }
                }

                memset(C, 0, sizeof(long)*n*l);
                num = 0;

                for (i = 0; i < n; i++) {
                    for (j = 0; j < l; j++) {
                        long res = 0;
                        for (k = 0; k < m; k++) {
                            res += A[i*m+k] * B[k*l+j];
                        }
                        C[num] += res;
                        num++;
                    }
                }

                num = 0;

                for (i = 0; i < n; i++) {
                    for (j = 0; j < l; j++) {
                        cout << C[num];
                        if (j+1 == l) {
                            cout << endl;
                        } else {
                            cout << " ";
                        }
                        num++;
                    }
                }
                delete [] A;
                delete [] B;
                delete [] C;
            }
            catch (...) {
                return -1;
            }
        }

     return 0;
}


Measured memory_bytes: 3240
//============================================================================
// Name        : r
// Date        : Tue Mar  5 14:46:32 CST 2019
// Author      : landcold7
// Description : Actions speak louder more than words
//============================================================================
#include "bits/stdc++.h"
using namespace std;

#define pb push_back
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define mst(x, y) memset(x, y, sizeof(x))
#define pvar(x) cout << #x << ": "
#define fora(e, c) for (auto &e : c)
#define fori(i, a, b) for (int i = a; i < b; ++i)
#define ford(i, a, b) for (int i = a; i > b; --i)
#define output(v) cout << (v) << '\n'
#define jam(x, n) cout << "Case #" << x << ": " << n << "\n"
#define prt(x, a, n) { cout << x[a]; if (a < n - 1) cout << " "; }
#define par(x, s, n, v) if(v) pvar(x); fori(y, s, n) prt(x, y, n) cout << "\n"

#ifndef __has_trace
#define trace(...)
#endif
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<string> vs;
typedef pair<int, int> pii;
typedef vector<pii> vpii;

const int mod = (int) 1e9 + 7;

void add(int& a, int b) {
    a += b;
    if (a >= mod) {
        a -= mod;
    }
}

int mul(int a, int b) {
    return (ll) a * b % mod;
}

template<class T> struct Matrix {
    typedef Matrix M;
    int N; vector<vector<T>> d;
    Matrix(int n) : N(n) {
        d = vector<vector<T>>(n, vector<T>(n, 0));
    }

    M operator* (const M& m) const {
        M a(N);
        fori(i, 0, N) {
            fori(j, 0, N) {
                fori(k, 0, N) {
                    add(a.d[i][j], mul(d[i][k], m.d[k][j]));
                }
            }
        }
        return a;
    }

    M operator^ (ll p) const {
        assert(p >= 0);
        M a(N), b(*this);
        fori(i, 0, N) {
            a.d[i][i] = 1;
        }
        while (p) {
            if (p & 1) {
                a = a * b;
            }
            b = b * b;
            p >>= 1;
        }
        return a;
    }

    // friend debugstream& operator<< (debugstream& os, Matrix<T>& m);
};

// debugstream& operator<< (debugstream& os, Matrix<int>& m) {
//     os << "Matirx(" << m.d << ")";
//     return os;
// }


void solve() {
    int n; ll k;
    cin >> n >> k;
    Matrix<int> m(n);
    fori (i, 0, n) fori (j, 0, n) {
        cin >> m.d[i][j];
    }

    m = m ^ k;

    int ret = 0;
    fori (i, 0, n) fori (j, 0, n) {
        add(ret, m.d[i][j]);
    }
    output(ret);
}

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



Measured memory_bytes: 384
import copy

H, W, K = map(int, input().split())
c = [list(input()) for _ in range(H)]
k = sum([ci.count("#") for ci in c])
ans = 0

for i2 in range(2 ** H):
  for j2 in range(2 ** W):
    cr = copy.deepcopy(c)
    for k in range(H+1):
      if i2 & 2**k == 2**k:
        for j in range(W):
          cr[k][j] = "$"
    for l in range(W+1):
      if j2 & 2**l == 2**l:
        for i in range(H):
          cr[i][l] = "$"
    if K == sum([ci.count("#") for ci in cr]):
      ans += 1
    
print(ans)

Measured memory_bytes: 9280
def sub(N, M, As):

    d_cost = {
            "1": 2,
            "2": 5,
            "3": 5,
            "4": 4,
            "5": 5,
            "6": 6,
            "7": 3,
            "8": 7,
            "9": 6,
            }
    
    NINF = -10**6
    dp_table = [NINF for _ in range(N+1)]
    dp_table[0] = 0
    for i in range(N):
        if dp_table[i] < 0:
            continue
        for a in As:
            cost = i + d_cost[a]
            if cost <= N:
                dp_table[cost] = max(dp_table[cost], dp_table[i] + 1)

    Lmax = dp_table[N]

    life = N
    buf = []
    for i in range(Lmax):
        oks = []
        for a in As:
            if life - d_cost[a] < 0:
                continue
            if dp_table[life - d_cost[a]] == dp_table[life] - 1:
                oks.append(a)
        # oks = [a for a in As if dp_table[life - d_cost[a]] == dp_table[life] - 1 and life - d_cost[a] >= 0]
        a_selected = max(oks)
        buf.append(a_selected)
        life = life - d_cost[a_selected]
    print("".join(buf))
            

if __name__ == "__main__":
    N, M = [int(e) for e in input().split()]
    As = [e for e in input().split()]
    sub(N, M, As)
    





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

int main() {
  string N;
  cin >> N;
  if(N.at(1) != N.at(2))
    cout << "No" << endl;
  else if(N.at(0) == N.at(1) || N.at(2) == N.at(3))
    cout << "Yes" << endl;
  else
    cout << "No" << endl;
}

Measured memory_bytes: 256
#include <algorithm>
#include <bits/stdc++.h>
#include <unordered_map>
#define ull unsigned long long
#define int long long
#define ll long long
#define fr(i, n) for (int i = 0; i < n; i++)
#define frf(i, j, n) for (int i = j; i <= n; i++)
#define frd(i, n) for (int i = n; i >= 0; i--)
#define mp(i, j) make_pair(i, j)
#define pb(x) push_back(x)
using namespace std;
// const int MAX = 1e6 + 1;
// typedef vector<vector<ll>> matrix;
//  const ll PRIME = 1e9 + 7;
// typedef pair<int,pair<int,int> >  ppi;
// const ll MAX = 1e6 + 1;

void solve()
{
    int x;
    cin>>x;
    int temp= x^1;
    cout<<temp;

}

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    int t;
    // int k = 1;
    // cin >> t;
    t = 1;
    while (t--)
    {
        // cout << "Case #" << k++ << ": ";
        solve();
    }
}


Measured memory_bytes: 3636
def d_candidates_of_no_shortest_paths(N, M, E):
    from scipy.sparse import csgraph

    graph = [[float('inf') for j in range(N)] for i in range(N)]
    for k in range(N):
        graph[k][k] = 0
    for a, b, c in E:
        graph[a - 1][b - 1] = c
        graph[b - 1][a - 1] = c
    dist = csgraph.floyd_warshall(graph)

    ans = M  # 最短経路として使われない辺の数
    for a, b, c in E:
        for s in range(N):
            if dist[s][a - 1] + c == dist[s][b - 1]:
                ans -= 1  # 条件を満たした辺は最短経路に使われる
                break
    return ans

N, M = [int(i) for i in input().split()]
E = [[int(i) for i in input().split()] for j in range(M)]
print(d_candidates_of_no_shortest_paths(N, M, E))

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

int ctoi(const char c){
  if('0' <= c && c <= '9') return (c-'0');
  return -1;
}

int main(){
  char str[100];
  
  scanf("%s",str);
  int n = strlen(str);
  int i,j,k,min = 10000000;
  
  for(i=0;i<n-2;i++){
    k = ctoi(str[i])*100 + ctoi(str[i+1])*10 + ctoi(str[i+2]);
    int xx = k-753;
    if(abs(xx) < min)
      min = abs(xx);
  }
  
  printf("%d\n",min);
  
  return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
int main(){
  int y, m ,d;
  char c1, c2;
  cin >> y >> c1 >> m >> c2 >> d;
  if (m<=4){
    cout << "Heisei" << endl;
  }
  else {
    cout << "TBD" << endl;
  }
}

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

int main() {
  int N,Q;
  std::string S;
  std::cin >> N >> Q >> S;
  std::vector<std::pair<int,int>> LR(Q);
  for(auto &lr:LR)
    std::cin >> lr.first >> lr.second;
  std::vector<long long> integral(N,0);
  for(int i=1;i<N;i++){
    integral[i] = integral[i-1];
    if(S.substr(i-1,2) == "AC")
      integral[i]++;
  }
  for(auto &lr:LR){
    std::cout << integral[lr.second-1]-integral[lr.first-1] << std::endl;
  }
  return 0;
}


Measured memory_bytes: 2688
#include <bits/stdc++.h>
typedef long long int ll;
typedef long double ld;
using namespace std;
const long long int INF = 1e18;
const long long int mod = 1e9+7;

typedef pair<ll, ll> pairs;
typedef vector<pairs> p;

struct edge{
    ll to, cost;
};


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

ll lcm(ll a, ll b){
    return a / gcd(a, b) * b;
}

ll keta(ll N){
    int tmp{};
    while( N > 0 ){
        tmp += ( N % 10 );
        N /= 10;
    }
    N = tmp;
    return N;
}

// 回文
bool kai(string S){
    bool flag = true;
    for(ll i=0;i<S.size()/2;++i){
        if(S[i] != S[S.size()-i-1]){
            flag = false;
            break;
        }
    }
    return flag;
}

vector<bool> IsPrime;

void sieve(size_t max){
    if(max+1 > IsPrime.size()){     // resizeで要素数が減らないように
        IsPrime.resize(max+1,true); // IsPrimeに必要な要素数を確保
    } 
    IsPrime[0] = false; // 0は素数ではない
    IsPrime[1] = false; // 1は素数ではない

    for(size_t i=2; i*i<=max; ++i) // 0からsqrt(max)まで調べる
        if(IsPrime[i]) // iが素数ならば
            for(size_t j=2; i*j<=max; ++j) // (max以下の)iの倍数は
                IsPrime[i*j] = false;      // 素数ではない
}
// ---------------------------------------------


int main(){
    ll n;
    cin>>n;
    
    ll ans = 0;
    for(ll i=1;i<=n;++i){
        for(ll j=i;j<=n;j+=i){
            ans += j;
        }
    }
    cout<<ans<<endl;

    return 0;
}

Measured memory_bytes: 3640
#include <iostream>
#include <stdio.h>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
#include <set>
#include <map>
#include <deque>
#include <math.h>
#include <string>
#include <iomanip>
#include <locale>
#include <list>
#include <bitset>
#include <tuple>
using namespace std;
#define FORN(i,m,n) for(int i=(m); i<int(n); i++)
#define PRINTVEC(v) FORN(i,0,v.size()) cout<<v[i]<<" "; cout<<endl
#define PRINTMAT(m) FORN(j,0,m.size()) {PRINTVEC(m[j]);}
typedef long long ll;

int main(){
  ios_base::sync_with_stdio(false); cin.tie(NULL);
  ll n, ans; cin>>n;
  ans = (n * (n + 1)) >> 1;
  for(int i = 3; i <= n; i+=3) ans -= i;
  for(int i = 5; i <= n; i+=5) ans -= i;
  for(int i = 15; i <= n; i+=15) ans += i;
  cout<<ans<<endl;
}

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

using namespace std;

int main(void){
    int d;
    cin>>d;
    if(d == 22){
        cout<<"Christmas Eve Eve Eve"<<endl;
    }else if(d == 23){
        cout<<"Christmas Eve Eve"<<endl;
    }else if(d == 24){
        cout<<"Christmas Eve"<<endl;
    }else{
        cout<<"Christmas"<<endl;
    }
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define int lint
typedef long long lint;
typedef pair<int,int> P;
const int    INF=(int)1e9;
const int    MOD=(int)1e9+7;
const double EPS=(double)1e-10;
struct Accelerate_Cin{
    Accelerate_Cin(){
        cin.tie(0); ios::sync_with_stdio(0);cout<<fixed<<setprecision(20);
    };
};

int c[5][5];
int a[5],b[5];

bool check(){
  for(int i=1;i<=3;i++){
    for(int j=1;j<=3;j++){
      if(a[i]+b[j]!=c[i][j])return false;
    }
  }

  return true;
}

signed main(){
  for(int i=1;i<=3;i++){
    for(int j=1;j<=3;j++){
      cin>>c[i][j];
    }
  }

  b[1]=c[1][1],b[2]=c[1][2],b[3]=c[1][3];
  a[1]=0,a[2]=c[2][1]-b[1],a[3]=c[3][1]-b[1];

  if(check()){
    cout<<"Yes"<<endl;
  }else{
    cout<<"No"<<endl;
  }

  return 0;
}


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

int main(){

  int N, i, a, b;
  map<int, int> data;
  cin>>N;
  
  for(i=0; i<N; i++){
    cin>>a>>b;
    data[b]+=a;
  }
  
  long long Sum=0;
  for(auto p : data){
    Sum+=p.second;
    if(Sum>p.first){
      cout<<"No"<<endl;
      return 0;
    }
  }
  cout<<"Yes"<<endl;
  return 0;
}

Measured memory_bytes: 12948
import java.util.Scanner;

class Main {

	public static void main(String[] args) {

		int h,m,s;

		Scanner stdIn = new Scanner(System.in);
		s = Integer.parseInt(stdIn.nextLine());

		h = s / 3600;
		s %= 3600;

		m = s / 60;
		s %= 60;

		System.out.println(h + ":" + m + ":" + s);

	}

}

Measured memory_bytes: 26156
/*input

*/
#include<bits/stdc++.h>
//priority_queue<ll, vector<ll>, std::greater<ll> > q;
//gcc 1.cpp -lstdc++ -o main.o
#define ull                 unsigned long long
#define ll                         long long
#define M                         1000000007
#define pb                         emplace_back
#define p_q                 priority_queue
#define pii         pair<ll,ll>
#define vi          vector<ll>
#define vii         vector<pii>
#define mi          map<ll,ll>
#define all(a)      (a).begin(),(a).end()
#define gcd(a,b)    __gcd((a),(b))
#define lcm(a,b)    ((a)*(b))/gcd((a),(b))
#define ios                    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define mp                         make_pair
#define rep(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
#define F first
#define S second
#define N 200005
using namespace std;


int main(void)
{
        ios
        string s1;
        cin>>s1;
        ll n = s1.size();
        string s2 = "";
        rep(i,0,n){
                if (s1[i] >= 'a' && s1[i] <='z')
                        s2.push_back('a');
                else
                        s2.push_back('A');
        }
        cout<<s2;

}

Measured memory_bytes: 3656
h,w=map(int,input().split())
ans=[]
ans_2=[]
ans_3=[]
ans_4=[]
for i in range(1,w-1):
    a=h*i
    res=w-i
    if res%2==0:
        b=h*(res//2)
        c=h*(res//2)
    else:
        b=h*(res//2)
        c=h*(res//2+1)
    ans.append(max(a,b,c)-min(a,b,c))
for i in range(1,h-1):
    a_2=i*w
    res_2=h-i
    if res_2%2==0:
        b_2=w*(res_2//2)
        c_2=w*(res_2//2)
    else:
        b_2=w*(res_2//2)
        c_2=w*(res_2//2+1)
    ans_2.append(max(a_2,b_2,c_2)-min(a_2,b_2,c_2))
for i in range(1,w-1):
    a_3=i*h
    res_3=w-i
    if h%2==0:
        b_3=res_3*(h//2)
        c_3=res_3*(h//2)
    else:
        b_3=res_3*(h//2)
        c_3=res_3*(h//2+1)
    ans_3.append(max(a_3,b_3,c_3)-min(a_3,b_3,c_3))
for i in range(1,h-1):
    a_4=w*i
    res_4=h-i
    if w%2==0:
        b_4=res_4*(w//2)
        c_4=res_4*(w//2)
    else:
        b_4=res_4*(w//2)
        c_4=res_4*(w//2+1)
    ans_4.append(max(a_4,b_4,c_4)-min(a_4,b_4,c_4))
if len(ans)==0:
    v=float("inf")
else:
    v=min(ans)
if len(ans_2)==0:
    x=float("inf")
else:
    x=min(ans_2)
if len(ans_3)==0:
    y=float("inf")
else:
    y=min(ans_3)
if len(ans_4)==0:
    z=float("inf")
else:
    z=min(ans_4)
f=float("inf")
if min(v,x,y,z)==f:
    print(1)
else:
    print(min(v,x,y,z))


Measured memory_bytes: 19016
#include<iostream>
#include<stack>
using namespace std;
static const int N = 100;
static const int WHITE = 0;
static const int GRAY = 1;
static const int BLACK = 2;

int n,M[N][N];
int color[N],d[N],f[N],tt;
int nt[N];

int next(int u){
  for(int v=nt[u];v<n;v++){
    nt[u] = v+1;
    if(M[u][v]) return v;
  }
  return -1;
}

void dfs_visit(int r){
  for(int i=0;i<n;i++) nt[i] = 0;

  stack<int> S;
  S.push(r);
  color[r] = GRAY;
  d[r] = ++tt;

  while(!S.empty()){
    int u = S.top();
    int v = next(u);
    if(v != -1){
      if(color[v] == WHITE){
	color[v] = GRAY;
	d[v] = ++tt;
	S.push(v);
      }
    }else{
      S.pop();
      color[u] = BLACK;
      f[u] = ++tt;
    }
  }
}

void dfs(){
  for(int i=0;i<n;i++){
    color[i] = WHITE;
    nt[i] = 0;
  }
  tt = 0;
  
  for(int u=0;u<n;u++){
    if(color[u] == WHITE) dfs_visit(u);
  }
  for(int i=0;i<n;i++){
    cout << i+1 << " " <<d[i] << " " << f[i] << endl;
  }
}

int main(){
  int u,k,v;

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

  for(int i=0;i<n;i++){
    cin >> u >> k;
    u--;
    for(int j=0;j<k;j++){
      cin >> v;
      v--;
      M[u][v] = 1;
    }
  }

  dfs();

  return 0;
}



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

#define ll long long
#define endl '\n'
#define REP(i, a, n) for(int i=a; i<n; ++i)
#define pb push_back
#define sz(x) (int)((x).size())
#define all(x) (x).begin(), (x).end()

typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;

const double PI = 3.141592653589793238460;
const ll mod = 1e9 + 7;

void FAST(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
}

int main(){
  FAST();

  string sa, sb, sc;
  cin >> sa >> sb >> sc;

  int i = 0, j = 0, k = 0;
  char turn = 'a';

  while(true){
    if(turn == 'a'){
        if(i != sa.length())
            turn = sa[i++];
        else{
            cout << "A\n";
            break;
        }
    }
    else if(turn == 'b'){
        if(j != sb.length())
            turn = sb[j++];
        else{
            cout << "B\n";
            break;
        }
    }
    else if(turn == 'c'){
        if(k != sc.length())
            turn = sc[k++];
        else{
            cout << "C\n";
            break;
        }
    }
  }

  return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

void gcd(int,int);

int main(){
  int x,y;

  scanf("%d %d",&x,&y);
  gcd(x,y);
  
  return 0;
}

void gcd(int x,int y){
  int n,r;
  if(x>y){
    while(y>0){
    r = x%y;
    x = y;
    y = r;
  }
  printf("%d\n",x);
  }
  else{
    while (x>0){
    r = y%x;
    y = x;
    x = r;
    }
    printf("%d\n",y);
  }
}
 
  


Measured memory_bytes: 2104
#[allow(unused_imports)]
use std::cmp::*;
#[allow(unused_imports)]
use std::collections::*;

fn main(){
    let n = readln();
    let mut a: Vec<usize> = vec![0;max(10,n)+1];
    let mut acc = 0;
    let mut x = 0;
    let mut i = 1;
    while i <= n {
        if i <= acc {
            a[i] = x
        } else {
            x += 1;
            acc += x;
            a[i] = x;
        }
        i += 1;
    }
    a[1] = 1;
    a[2] = 2;
    a[3] = 2;
    a[4] = 3;

    let mut acc = n;
    let mut res = vec![a[n]];
    while acc != 1 && acc != 2 {
        acc = acc - a[acc];
        res.push(a[acc]);
    }

    for &x in &res {
        println!("{}",x);
    }
}


#[allow(dead_code)]
fn get_line() -> String{
    let mut buf = String::new();
    std::io::stdin().read_line(&mut buf).unwrap();
    buf.trim_right().to_string()
}

#[allow(dead_code)]
fn get_chars() -> Vec<char>{
    get_line().chars().collect()
}

#[allow(dead_code)]
fn readln<T: Read>() -> T{
    let mut buf = String::new();
    std::io::stdin().read_line(&mut buf).unwrap();
    T::read(buf.trim_right())
}

trait Read{
    fn read(s: &str) -> Self;
}

macro_rules! read_impl{
    ($($t:ty)*) => ($(
        impl Read for $t {
            fn read(s: &str) -> $t{
                s.parse().unwrap()
            }
        }
    )*)
}
read_impl! { usize u8 u16 u32 u64 isize i8 i16 i32 i64 f32 f64 }

impl<T: Read> Read for Vec<T>{
    fn read(s: &str) -> Self {
        s.split_whitespace().map(T::read).collect()
    }
}

impl<A: Read, B: Read> Read for (A, B){
    fn read(s: &str) -> Self {
        let tokens: Vec<_> = s.split_whitespace().collect();
        (A::read(tokens[0]), B::read(tokens[1]))
    }
}

impl<A: Read, B: Read, C: Read> Read for (A, B, C){
    fn read(s: &str) -> Self {
        let tokens: Vec<_> = s.split_whitespace().collect();
        (A::read(tokens[0]), B::read(tokens[1]), C::read(tokens[2]))
    }
}

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

#define ull unsigned long long
#define endl '\n'
#define ll int
const int N = 1e6 + 5;
bool cinc(pair<ll,ll> x, pair<ll,ll> y){
        return x.first > y.first;
}
bool cdes(pair<ll,ll> x, pair<ll,ll> y){
        return x.first > y.first;
}
int main(){
        ios_base::sync_with_stdio(false);
        cin.tie(0);
        cout.tie(0);
        if (fopen("VIETVODICH.INP", "r")){
                freopen("VIETVODICH.INP", "r", stdin);
                freopen("VIETVODICH.OUT", "w", stdout);
        }
        ll n;
        cin >> n;
        vector<pair<ll,ll>> inc;
        vector<pair<ll,ll>> des;
        for (int i = 1; i <= n; i++){
                string s;
                cin >> s;
                ll low = 0, now = 0;
                for (int j = 0; j < (int)s.length(); j++){
                        if (s[j] == '(') now++;
                        else now--, low = min(low, now);
                }
                if (now >= 0){
                        inc.push_back({low, now});
                } else {
                        des.push_back({now - low, low});
                }
        }
        sort(inc.begin(), inc.end(), cinc);
        sort(des.begin(), des.end(), cdes);
        ll now = 0;
        bool flag = true;
        for (pair<ll,ll> j : inc){
                if ((now + (j.first)) < 0){
                        flag = false;
                        now = -1e9;
                        break;
                } else {
                        now = now + j.second;
                }
        }
        for (pair<ll,ll> j : des){
                if ((now + j.second) < 0){
                        flag = false;
                        break;
                } else {
                        now = now + j.second + j.first;
                }
        }
        if (now == 0 && flag) cout << "Yes";
        else cout << "No";
}


Measured memory_bytes: 11300
import java.util.Arrays;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		int X = sc.nextInt();
		int N = sc.nextInt();
		Integer[] input = new Integer[N];
		for (int i = 0; i < N; i++) {
			input[i] = sc.nextInt();
		}
		for (int i = 0; i < 100; i++) {
			if (!Arrays.asList(input).contains(X - i)) {
				System.out.println(X - i);
				System.exit(0);
			}
			if (!Arrays.asList(input).contains(X + i)) {
				System.out.println(X + i);
				System.exit(0);
			}
		}
	}
}

Measured memory_bytes: 36064
n, m = map(int, input().split())
a = list(map(int, input().split()))
t = [0]
v = 0
b = {0:1}
for i in range(n):
    v = (v + a[i]) % m
    if v in b.keys():
        b[v] += 1
    else:
        b[v] = 1
ans = 0
for i in b.values():
    ans += i * (i-1) / 2
print(int(ans))


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

using namespace std;

#define DEBUG(x) cerr<<#x<<": "<<x<<endl;
#define DEBUG_VEC(v) cerr<<#v<<":";for(int i=0;i<v.size();i++) cerr<<" "<<v[i]; cerr<<endl

typedef long long ll;
#define vi vector<int>
#define vl vector<ll>
#define vii vector< vector<int> >
#define vll vector< vector<ll> >
#define vs vector<string>
#define pii pair<int,int>
#define pis pair<int,string>
#define psi pair<string,int>
#define pll pair<ll,ll>
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); }
template<class S, class T> ostream& operator<<(ostream& os, pair<S, T> p) { os << "(" << p.first << ", " << p.second << ")"; return os; }
#define X first
#define Y second
#define rep(i,n) for(int i=0;i<(n);i++)
#define rep1(i,n) for(int 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 REP(i,a,b) for(int i=a;i<b;i++)
#define in(x, a, b) (a <= x && x < b)
#define all(c) c.begin(),c.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; }
#define UNIQUE(v) v.erase(std::unique(v.begin(), v.end()), v.end());
const ll inf = 1000000001;
const ll INF = 1e18;
const ll MOD = 1000000007;
//const ll MOD = 998244353;
const double pi = 3.14159265358979323846;
#define Sp(p) cout<<setprecision(15)<< fixed<<p<<endl;
int dx[4] = { 1,0, -1,0 }, dy[4] = { 0,1,0,-1 };
int dx2[8] = { 1,1,0,-1,-1,-1,0,1 }, dy2[8] = { 0,1,1,1,0,-1,-1,-1 };
#define fio() cin.tie(0); ios::sync_with_stdio(false);
//#define mp make_pair

int main() {
  int n, k;
  cin >> n >> k;
  vector<pll> zen;
  rep (i, n) {
    ll t, d;
    cin >> t >> d;
    t--;
    zen.push_back(pll(d, t));
  }
  sort(all(zen));
  reverse(all(zen));
  vi num(n);
  ll score = 0;
  ll shu = 0;
  vector<pll> use;
  rep (i, k) {
    ll t = zen[i].second, d = zen[i].first;
    num[t]++;
    if (num[t] == 1) shu++;
    score += d;
    use.push_back(pll(d, t));
  }
  ll ma = score + shu*shu;
  sort(all(use));
  reverse(all(use));
  for (int i = k; i < n; i++) {
    ll t = zen[i].second, d = zen[i].first;
    if (num[t]) continue;
    while (use.size() > 0) {
      pll sute = use.back();
      use.pop_back();
      ll t2 = sute.second, d2 = sute.first;
      if (num[t2] == 1) continue;
      num[t2]--;
      score -= d2;
      score += d;
      num[t]++;
      shu++;
      break;
    }
    ma = max(ma, score + shu*shu);
  }
  cout << ma << endl;
}


Measured memory_bytes: 5232
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define mod 10e9+7
#define ll long long int


int main(void){
    int a, p;
    scanf("%d %d", &a, &p);
    p = 3 * a + p;
    printf("%d\n", p/2);
    return 0;
}

Measured memory_bytes: 128
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;


    class Program
    {
        static void Main(string[] args)
        {
            string[] Input = Console.ReadLine().Split(' ');
            for(int i = 0; i < Input.Length; i++){
                if(Input[i] == "0"){
                    Console.WriteLine(i + 1);
                    break;
                }
            }
        }
    }

Measured memory_bytes: 17768
#include <algorithm>
#include <cassert>
#include <climits>
#include <cmath>
#include <iostream>
#include <map>
#include <queue>
#include <string>
#include <vector>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef pair<int, int> ipair;
typedef tuple<int, int, int> ituple;

// const ll INF = LLONG_MAX;
// const int MOD = (int)1e9 + 7;
// const double EPS = 1e-10;
#define PI acosl(-1)
#define MAX_N 100000 + 2

void exec(){
  int n;
  int a[MAX_N];
  int m4 = 0, m2 = 0, mo = 0;

  cin >> n;
  for (int i = 0; i < n; i++){
    scanf("%d", &a[i]);
    if (a[i] % 4 == 0){
      m4++;
    }
    else if (a[i] % 2 == 0){
      m2++;
    }
    else {
      mo++;
    }
  }

  if (m2 == 0){
    if (m4 >= mo - 1){
      cout << "Yes" << endl;
    }
    else{
      cout << "No" << endl;
    }
  }
  else{
    if (m4 >= mo){
      cout << "Yes" << endl;
    }
    else{
      cout << "No" << endl;
    }
  }

}

void solve(){
  int t = 1;
  // scanf("%d", &t);
  for (int i = 0; i < t; i++){
    exec();
  }
}

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


Measured memory_bytes: 888
#include<bits/stdc++.h>                   // below comment for pbds
#include<ext/pb_ds/assoc_container.hpp>   // to use it make ordered_set
#include<ext/pb_ds/tree_policy.hpp>       // all set fnct + = 1. order_of_key(x); // number of 
#define ll long long                      //element strictly smaller than it;
#define ld long double                    // 2. find_by_order(x),pointer el at x pos after sort  use as s.f();
#define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update>
using namespace std;                     
using namespace __gnu_pbds;
// assert(a[i]<n ) // if we want to check for special cond , used for debug
// make less_equal in order to make a multiset pbds
const ll Mod = (int)1e9;
ll CaseN=1;



ll tst(string s,ll n)
{
ll ans =0;	

	
return ans;
}


void solve()
{
	ll ans=0;
ll h,w,k;
cin>>h>>w>>k;

vector<string> v(h+2);
ll total=0;
for(ll i=0;i<h;i++)
{
	string s;
	cin>>s;
	v[i]=s;
	
}
// w 
// lets stor count of white = 
vector<ll> c1(h+3,0);
vector<ll> c2(w+3,0);
// row col

for(ll i=0;i<h;i++)
{
ll ss=0;

for(ll j=0;j<w;j++)
{
if(v[i][j]=='#')
{
ss++;	
total++;
}	
}
c1[i+1]=ss;	
}

for(ll i=0;i<w;i++)
{
ll ss=0;
for(ll j=0;j<h;j++)
{
if(v[j][i]=='#')
{
ss++;	
}	
}
c2[i+1]=ss;	
}

//for(ll i=1;i<=h;i++)
//{
//cout<<c1[i]<<" + ";	
//}
//cout<<endl;
//for(ll i=1;i<=w;i++)
//{
//cout<<c2[i]<<" + ";	
//}
//cout<<endl;
//cout<<"Total: "<<total<<endl;

ll p1=pow(2,h);
ll p2 = pow(2,w);
for(ll i=0;i<p1;i++)
{
for(ll j=0 ;j<p2;j++)
{
	// i,j
	ll sum=0;	
	ll z1 = i;
	ll z2=j;
	ll p=1;
	vector<ll> s1;
	vector<ll> s2;
	while(z1>0)
	{
	if(z1&1)
	{
		sum+=c1[p];
		s1.push_back(p);
	}
	z1=z1>>1;
	p++;	
	}
	p=1;
	while(z2>0)
	{
	if(z2&1)
	{
		sum+=c2[p];
		s2.push_back(p);
	}
	z2=z2>>1;
	p++;	
	}
	// exclude common;
	//if(s1,s2) is zero add
	for(ll m=0;m<(ll)s1.size();m++)
	{
	for(ll n=0;n<(ll)s2.size();n++)
	{
	   if(v[s1[m]-1][s2[n]-1]=='#')
	   {
		 sum--; 
	   }	
	}	
	}
	
	if(total-sum==k)
	{
	ans++;	
	}
	//cout<<": "<<i<<" "<<j<<" "<<sum<<endl;
}		
}


// we want exactly k;

cout<<ans<<endl;
	//cerr<<"Case #"<<CaseN<<": ";
    CaseN++;	

return ;
}


signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int t=1;
	//cin>>t;
	while(t--)
	{
	solve();	
	}
}
/*
 if(ans)
  {
  cout<<"YES"<<endl; 
  }
  else
   {
  cout<<"NO"<<endl;
  }
 
 
*/


Measured memory_bytes: 4076
#include <bits/stdc++.h>
#include<math.h>
#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int main() {
  int N;
  cin>>N;
  vector<long>a(N);
  for(int i=0;i<N;++i){
    cin>>a.at(i);
  }
  long ans=1;
  for(int i=0;i<N;++i){
    ans=a.at(i)/__gcd(a.at(i),ans)*ans;
  }
  cout<<ans<<endl;

}

Measured memory_bytes: 256
N=int(input())
A=[]
B=[]

for i in range(N):
    a,b=map(int,input().split())
    A.append(a)
    B.append(b)
sum=0
for i in range(N-1,-1,-1):
    A[i]+=sum
    if A[i]%B[i]!=0:
        sum+=B[i]-A[i]%B[i]

print(sum)

Measured memory_bytes: 15016
import functools

import os

INF = float('inf')


def inp():
    return int(input())


def inpf():
    return float(input())


def inps():
    return input()


def inl():
    return list(map(int, input().split()))


def inlf():
    return list(map(float, input().split()))


def inls():
    return input().split()


def inpm(line):
    return [inp() for _ in range(line)]


def inpfm(line):
    return [inpf() for _ in range(line)]


def inpsm(line):
    return [inps() for _ in range(line)]


def inlm(line):
    return [inl() for _ in range(line)]


def inlfm(line):
    return [inlf() for _ in range(line)]


def inlsm(line):
    return [inls() for _ in range(line)]


def debug(fn):
    if not os.getenv('LOCAL'):
        return fn

    @functools.wraps(fn)
    def wrapper(*args, **kwargs):
        print('DEBUG: {}({}) -> '.format(
            fn.__name__,
            ', '.join(
                list(map(str, args)) +
                ['{}={}'.format(k, str(v)) for k, v in kwargs.items()]
            )
        ), end='')
        ret = fn(*args, **kwargs)
        print(ret)
        return ret

    return wrapper

a, b = inl()
print((a-1)*(b-1))

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

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

    for (int i = 1; i < 10; i++) {
        for (int j = 1; j < 10; j++) {
            if (N - i * j == 0) {
                cout << "Yes";
                return 0;
            }
        }
    }
    cout << "No";
    
    return 0;
}


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

#include <iostream>
//#include <algorithm>
// #include <iomanip>
#define ll long long
#define map unordered_map
#define set unordered_set

using namespace std;

const ll MOD = 1000000007;
const ll INF = (1LL << 62);

int main() {
  ll A, B, C, X, Y;
  scanf("%lld %lld %lld %lld %lld", &A, &B, &C, &X, &Y);

  ll price1 = A * X + B * Y;

  ll price2 = C * max(X, Y) * 2;

  ll price3 = 0;
  if (X < Y) {
    price3 += C * X * 2;
    price3 += B * (Y - X);
  } else {
    price3 += C * Y * 2;
    price3 += A * (X - Y);
  }
  cout << min(price3, min(price1, price2)) << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
    int n,m;
    cin>>n>>m;
    vector<int> k,p;
    vector<vector<int>> s(m);
    for(int i=0;i<m;i++){
        int tmpk;
        cin>>tmpk;
        k.push_back(tmpk);
        for(int j=0;j<k[i];j++){
            int tmps;
            cin>>tmps;
            s[i].push_back(tmps);
        }
    }
    for(int i=0;i<m;i++){
        int tmp;
        cin>>tmp;
        p.push_back(tmp);
    }

    int table[n];
    int ans = 0;
    for(int i=0;i<(1<<n);i++){
        int tmp = i;
        for(int j=0;j<n;j++){
            table[j] = ((tmp>>j)&1);
        }

        //switchの状態と電球を比較して、スイッチの個数をそれぞれ把握する
        int sw_cnt[m]={};
        for(int j=0;j<m;j++){
            for(int l=0;l<k[j];l++){
                if(table[s[j][l]-1]==1){
                    sw_cnt[j]++;
                }
            }
        }
        bool flag = true;
        for(int j=0;j<m;j++){
            if(sw_cnt[j]%2 != p[j]){
                flag = false;
                break;
            }
        }
        if(flag){
            ans++;
        }
    }
    cout << ans << endl;
}


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

int main(int argc, char *argv[])
{
    int N, M, X;
    int sumcount = 0;
    int count = 0;

    if (scanf("%d %d %d", &N, &M, &X) < 3)
    {
        exit(1);
    }

    int A[M];

    for (int i = 0; i < M; i++)
    {
        scanf("%d", &A[i]);
    }

    for (int i = 0; i < M; i++)
    {
        if (A[i] < X)
        {
            count++;
        }
        else
        {
            sumcount++;
        }
    }

    if (sumcount > count)
    {
        printf("%d\n", count);
    }
    else
    {
        printf("%d\n", sumcount);
    }
    return 0;
}

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

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

using namespace std;

int main(){
    int n; cin >> n;
    set<int> s;
    REPI(i, n){
        int x; cin >> x;
        s.insert(x);
    }cout << s.size();
}


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

ll solve(ll a, ll b, ll c, ll d) {
  return max(a * c, max(a*d, max(b*c, b*d)));
}

int main() {
  ll a, b, c, d;
  cin >> a >> b >> c >> d;
  cout << solve(a, b, c, d);
}


Measured memory_bytes: 3636
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

n, m = map(int, input().split())

ans1 = 0
ans2 = 0
if n > 1:
    ans1 = cmb(n, 2)
if m > 1:
    ans2 = cmb(m, 2)

print(ans1+ans2)

Measured memory_bytes: 3188
#include<iostream>
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#include <iomanip>//setprecision
#include<math.h>
#include <functional>
#include<climits>
using namespace std;
#define rep(i, n)        for(int i=0; i<(int)(n); ++i)
int main(){ 
  int a,b,e,d=0;cin>>a;
  vector<int>c(9);
  rep(i,9)c[i]=0;
  rep(i,a){
cin>>b;
e=b/400;
if(e>=9)c[8]++;
else c[e]++;
  }
  rep(i,8){
    if(c[i]!=0)d++;
  }
  if(d==0)  cout<<d+1<<" "<<d+c[8];
 else  cout<<d<<" "<<d+c[8];
}


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

int main() {
	int n;
	
	cin >> n;
	
	ull lm = 0, rm = 0;
	vector<ull> v, v2;
	for(int i=0;i<n;i++){
		ull tmp;
		cin >> tmp;
		v.push_back(tmp);
	}
	v2 = v;
	sort(v.begin(), v.end());
	lm = v[n/2-1];
	rm = v[n/2];
	for(int i=0;i<n;i++){
		cout << ((v2[i]<=lm)?rm:lm) << endl;
	}
	
	return 0;
}

Measured memory_bytes: 5488
#include <bits/stdc++.h>
#define rep(i,n) for (int (i) = 0; (i) < (n); i++)
#define ll long long
using namespace std;
int main() {
  ll N = 0,ans = 0;
  cin >> N;
  ll m = N+1;
  vector<ll>A(N);
  rep(i,N){
    cin >> A[i];
  }
  rep(i,N){
    if(m > A[i]){
      ans++;
      m = A[i];
    }
  }
  cout << ans;
}

Measured memory_bytes: 4844
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<(n); i++)
#define int long long
#define double long double
#define mod 1000000007
#define F first
#define S second
#define P pair<long long,long long>
#define all(a) a.begin(),a.end()
#define INF 10000000000000000
#define endl '\n'
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; }
using namespace std;

class LazyRMQ{
private:
    int n;
    vector<int> node,lazy;
    vector<bool> islazy;
    bool ismax;
    int pick(int x, int y){
        if(ismax)return max<int>(x,y);
        else return min<int>(x,y);
    }
    void update2(int a, int b, int v, int k, int l, int r){
        eval(k,l,r);
        if(a==l and b==r){
            islazy[k]=true;
            lazy[k]=v;
            eval(k,l,r);
            return;
        }
        int m=(l+r)/2;
        if(b<=m)update2(a,b,v,k*2+1,l,m);
        else if(a>=m)update2(a,b,v,k*2+2,m,r);
        else{update2(a,m,v,k*2+1,l,m); update2(m,b,v,k*2+2,m,r);}  
        node[k]=pick(node[k*2+1],node[k*2+2]);
    }
    int get2(int a, int b, int k, int l, int r){
        eval(k,l,r);
        if(a==l and r==b)return node[k];
        int m=(l+r)/2;
        if(b<=m)return get2(a,b,k*2+1,l,m);
        else if(a>=m)return get2(a,b,k*2+2,m,r);
        else return pick(get2(a,m,k+2+1,l,m),get2(m,b,k+2+2,m,r));
    }
public:
    LazyRMQ(vector<int> vec, bool is_max){
        ismax=is_max; int tmp_size=vec.size();
        n=1; while(n<tmp_size)n*=2;
        if(ismax)node.resize(n*2-1,-INF);
        else node.resize(n*2-1,INF);
        for(int i=0; i<tmp_size; i++)node[i+n-1]=vec[i];
        for(int i=n-2; i>=0; i--)node[i]=pick(node[i*2+1],node[i*2+2]);
        if(ismax)lazy.resize(n*2-1,-INF);
        else lazy.resize(n*2-1,INF);
        islazy.resize(n*2-1,false);
    }
    void eval(int k, int l, int r){
        if(islazy[k]){
            node[k]=pick(node[k],lazy[k]);
            if(r-l>1){
                lazy[k*2+2]=lazy[k*2+1]=lazy[k];
                islazy[k*2+2]=islazy[k*2+1]=true;
            }
            islazy[k]=false;
            if(ismax)lazy[k]=-INF;
            else lazy[k]=INF;
        }
    }
    void update(int a, int b, int v){
        update2(a,b,v,0,0,n);
    }
    int get(int a, int b){
        return get2(a,b,0,0,n);
    }
};

signed main(void){
    cin.tie(0); cout.tie(0);
    ios::sync_with_stdio(false);

    int n,q; cin>>n>>q;
    LazyRMQ sg(vector<int>(q,INF),false);
    vector<int> d(q);
    vector<pair<int,P>> vec(n);

    rep(i,n){
        cin>>vec.at(i).S.F>>vec.at(i).S.S>>vec.at(i).F;
    }
    rep(i,q){
        cin>>d.at(i);
    }
    sort(all(vec),greater<pair<int,P>>());

    rep(i,n){
        int S=vec.at(i).S.F,T=vec.at(i).S.S,X=vec.at(i).F;
        int lf=lower_bound(all(d),S-X)-d.begin();
        int ri=lower_bound(all(d),T-X)-d.begin();
        if(lf==ri)continue;
        sg.update(lf,ri,X);
    }

    rep(i,q){
        int ans=sg.get(i,i+1);
        if(ans==INF)cout<<-1<<endl;
        else cout<<ans<<endl;
    }

}

Measured memory_bytes: 16484
#include<bits/stdc++.h>
using namespace std;
typedef long long int lli;
int main(){
	lli N;
  	cin>>N;
  	lli A[N];
  	for(lli i = 0; i<N; i++)
      A[i] = 0;
  	for(lli i = 1; i<N; i++){
      lli x;
      cin>>x;
      A[x-1]++;
    }
  for(lli i = 0; i<N; i++){
    cout<<A[i]<<endl;
  }
  return 0;
}

Measured memory_bytes: 5148
package main

import (
	"bufio"
	"fmt"
	"os"
)

var sc = bufio.NewScanner(os.Stdin)

func read() string {
	sc.Scan()
	return sc.Text()
}

func main() {
	sc.Split(bufio.ScanWords)
	s := read()
	if s[3] == s[2] && s[5] == s[4] {
		fmt.Println("Yes")
	} else {
		fmt.Println("No")
	}
}


Measured memory_bytes: 640
#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

struct pkt
{
    int x, y;
};

int main()
{
    ios_base::sync_with_stdio(0);
    int n, m, d;
    cin >> n >> m >> d;
    vector<pkt> p(n * m);
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < m; ++j)
        {
            int x;
            cin >> x;
            --x;
            p[x] = {i, j};
        }
    }
    vector< vector<pkt> > r(d);
    for (int i = 0; i < d; ++i)
        for (int j = i; j < n * m; j += d)
            r[i].push_back(p[j]);
    vector< vector<int> > pref(d);
    for (int i = 0; i < d; ++i)
    {
        pref[i].push_back(0);
        for (int j = 1; j < r[i].size(); ++j)
            pref[i].push_back(abs(r[i][j].x - r[i][j - 1].x) + abs(r[i][j].y - r[i][j - 1].y) + pref[i].back());
    }
    int q;
    cin >> q;
    for (int i = 0; i < q; ++i)
    {
        int l, r;
        cin >> l >> r;
        --l;
        --r;
        cout << pref[l % d][r / d] - pref[l % d][l / d] << endl;
    }
    return 0;
}


Measured memory_bytes: 11008
#include <cstdio>
#include <vector>
#include <stack>
#include <iostream>
#include <string>
#include <tuple>
#include <random>
#include <map>
#include <queue>
#include <set>
#include <complex>
#include <algorithm>
#include <cassert>
#include <iterator>
#include <numeric>
#include <chrono>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> P;
typedef tuple<ll, ll, ll> T;

const ll INF = 1e15;

int main() {
	ll N;
	cin >> N;
	vector<P> v(N);
	for (int i = 0;i < N;i++) {
		ll h, p;
		cin >> h >> p;
		v[i] = P(p, -h);
	}
	sort(v.begin(), v.end());
	vector<P> now;
	ll yoyuu = INF;
	for (int i = 0;i < N;i++) {
		ll h, p;
		tie(p, h) = v[i];
		h = -h;

		vector<ll> imos(now.size()+1);
		for (int i = 0;i < now.size();i++) {
			imos[i + 1] = imos[i] + now[i].first;
		}
		vector<ll> yoyuu(now.size() + 1, INF);
		for (int i = now.size()-1;i >= 0;i--) {
			yoyuu[i] = now[i].second - imos[i];
			yoyuu[i] = min(yoyuu[i], yoyuu[i+1]);
		}
		ll iti = 0;
		while (yoyuu[iti] < p)
			iti++;
		if (imos[iti] <= h) {
			ll point = min(yoyuu[iti] - p, h - imos[iti]);
			for (int k = iti+1; k < now.size() + 1; k++)
				if (min(yoyuu[k] - p, h - imos[k]) > point) {
					iti = k;
					point = min(yoyuu[k] - p, h - imos[k]);
				}
			now.insert(now.begin() + iti, P(p, h));
		}
	}
	cout << now.size() << endl;
	return 0;
}


Measured memory_bytes: 512
#include<iostream>
#include<vector>
#include<algorithm>
#include<set>
#include<queue>
#include<string>
#include<cstdio>
#include<stack>
#include<memory.h>
#include<cmath>
#include<bitset>
#include<functional>
#include<memory>
#include<utility>
using namespace std;
#define FOR(i,m,n) for(i=m;i<n;i++)
#define MIN(x,y) (x>y?y:x)
#define ab(x,y) (x>y ?(x-y):(y-x))
#define CLR(a,b) memset(a,b,sizeof(a))
#define ROF(i,m,n) for(i=m;i>=n;i--)
#define BUG cout<<"debug"<<endl;
#define RT return
#define BK break
#define HEAP priority_queue
#define SP " "
#define lowf(a,b,c) lower_bound(a,b,c)
#define upf(a,b,c) upper_bound(a,b,c)
#define CP bool cmp(node A,node B)
typedef long long LL;
typedef vector<int> VI;
const int INF = 2147483647;
const int NEN = -INF - 1;
const LL LINF = 9223372036854775807;
int fa[100005];
int N, Q;
int main()
{
	while (1)
	{
		scanf("%d%d", &N, &Q);
		if (N == 0 && Q == 0)break;
		int i;
		unsigned long long sum = 0;
		char ope;
		int  a;
		FOR(i, 1, N)
		{
			scanf("%d", &fa[i + 1]);
		}
		fa[1] = 1;
		while (Q--)
		{
			scanf("%c", &ope);
			scanf("%c", &ope);
			scanf("%d", &a);
			if (ope == 'M')fa[a] = a;
			else
			{
				while (fa[a] != a)
				{
					a = fa[a];
				}
				sum += a;
			}
		}
		printf("%lld\n", sum);
	}
}


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

struct UnionFind{
    vector<int> par;
    vector<int> siz;

    UnionFind(int n): par(n), siz(n){
        for(int i=0; i<n; i++){
            par[i] = i;
            siz[i] = 1;
        }
    }

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

    int size(int x){
        if(par[x] == x) return siz[x];
        else return siz[x] = size(par[x]);
    }

    void unite(int x, int y){
        int rx = root(x);
        int ry = root(y);
        if(rx != ry){
            par[ry] = rx;
            siz[rx] += siz[ry];
        }
    }

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

signed main(){
    // cout << fixed << setprecision(10) << flush;

    int n, m;
    cin >> n >> m;

    UnionFind uf(n);
    for(int i=0; i<m; i++){
        int a, b;
        cin >> a >> b;
        uf.unite(a-1, b-1);
    }

    int maxsize = 0;
    for(int i=0; i<n; i++){
        maxsize = max(maxsize, uf.siz[i]);
    }
    cout << maxsize << endl;

    return 0;
}

Measured memory_bytes: 6420