akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>
#include <string.h>
#include <stack>
#include <queue>
#include <algorithm>
#include <climits>
#include <cmath>
#include <map>
#include <set>
#include <assert.h>
#include <numeric>
#define REP(i,n) for(ll i=0;i<(n);i++)
#define MOD 1000000007
#define int long long
#ifdef int
const long long INF = LLONG_MAX / 10;
#else
const int INF = 1010101010;
#endif
using namespace std;
typedef long long ll;
typedef vector<vector<ll> > mat;
typedef pair<int, int> P;
//typedef pair<double, double> P;
const int dx[9] = {-1, 0, 0, 1, -1, -1, 1, 1, 0};
const int dy[9] = {0, -1, 1, 0, -1, 1, -1, 1, 0};

int N;
int A, B;

vector<int> graph[101010];
int X[101010];
int low[101010], hi[101010];
int dep[101010];

void dfs(int p, int rt, int d) {
  dep[p] = d;
  for (int q : graph[p]) if (q != rt) {
    dfs(q, p, d + 1);
    low[p] = max(low[p], low[q] - 1);
    hi[p] = min(hi[p], hi[q] + 1);
  }
}

void dfs2(int p, int rt) {
  for (int q : graph[p]) if (q != rt) {
    low[q] = max(low[q], low[p] - 1);
    // hi[q] = min(hi[q], hi[p] + 1);
    dfs2(q, p);
  }
}

signed main()
{
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  cin >> N;
  REP(i,N-1) {
    cin >> A >> B;
    A--; B--;
    graph[A].push_back(B);
    graph[B].push_back(A);
  }
  REP(i,N) {
    X[i] = -INF;
    low[i] = -INF;
    hi[i] = INF;
  }
  int K;
  cin >> K;
  while (K--) {
    int v, p;
    cin >> v >> p;
    v--;
    X[v] = low[v] = hi[v] = p;
  }

  dfs(0, -1, 0);
  dfs2(0, -1);

  int par = -1;
  REP(i,N) {
    if (X[i] != -INF) {
      int myp = (X[i] ^ dep[i]) & 1;
      if (par == -1) par = myp;
      if (par != myp) {
        puts("No");
        return 0;
      }
    }
    if (low[i] > hi[i]) {
      puts("No");
      return 0;
    }
  }

  puts("Yes");
  // REP(i,N) cout << low[i] << endl;
  REP(i,N) printf("%lld\n", low[i]);
}

Measured memory_bytes: 15872
import sys
sys.setrecursionlimit(10**9)
input = lambda: sys.stdin.readline().rstrip()
inpl = lambda: list(map(int,input().split()))
N, M, L = inpl()
road = [[] for _ in range(N)]
ABC = []
for i in range(M):
    A, B, C = inpl()
    if C <= L:
        road[A-1].append((B-1,C))
        road[B-1].append((A-1,C))
        ABC.append((A-1,B-1,C))

INF = 10**12
cur1 = [[INF]*N for _ in range(N)]
for a, b, c in ABC:
    cur1[a][b] = cur1[b][a] = c
for k in range(N):
    prev1 = cur1
    cur1 = [[INF]*N for _ in range(N)] 
    for j in range(N):
        for i in range(N):
            cur1[j][i] = min(prev1[j][i], prev1[k][i]+prev1[j][k])

cur2 = [[INF]*N for j in range(N)]
for j in range(N):
    for i in range(N):
        if cur1[j][i] <= L:
            cur2[j][i] = 1
for k in range(N):
    prev2 = cur2
    cur2 = [[INF]*N for _ in range(N)]
    for j in range(N):
        for i in range(N):
            cur2[j][i] = min(prev2[j][i], prev2[k][i]+prev2[j][k])

Q = int(input())
ST = [inpl() for _ in range(Q)]
for s,t in ST:
    if cur2[s-1][t-1] >= INF:
        print(-1)
    else:
        print(cur2[s-1][t-1]-1)

Measured memory_bytes: 137820
#include "bits/stdc++.h"
typedef long long ll;
using namespace std;

int main() {
    vector<int> a(3);
    cin >> a[0] >> a[1] >> a[2];
    sort(a.begin(), a.end());
    int sum = 0;
    for (int i = 1; i < 3; ++i) {
        sum += a[i] - a[i - 1];
    }
    cout << sum;
    return 0;
}


Measured memory_bytes: 256
a, b, c = 0, 0, 0
s = input()

for i in s:
    if i == "a":
        a += 1
    elif i == "b":
        b += 1
    else:
        c += 1
if max(a,b,c) -  min(a,b,c) <= 1:
    print("YES")
else:
    print("NO")

Measured memory_bytes: 39536
#include <stdio.h>
#include <string.h>

int gcd(int a,int b){
	return b ? gcd(b,a%b) : a;
}

int change(char str[257],int a,int b){
	int i;
	for(i = 0;str[i] != '\0';i++){
		str[i] = str[i] == ' ' ? ' ' : (a*(str[i]-'a')+b)%26+'a';
	}
	for(i = 0;str[i+3] != '\0';i++){
		if(!strncmp(str+i,"that",4) || !strncmp(str+i,"this",4)){
			return 1;
		}
	}
	
	return 0;
}

int main(void) {
	int i,n,a,b;
	char str[257],str2[257];
	
	scanf("%d",&n);
	gets(str);
	for(i = 0;i < n;i++){
		gets(str);
		for(a = 1;a < 512;a+=2){
			for(b = 1;b < 512;b++){
				if(gcd(a,26) != 1) continue;
				strcpy(str2,str);
				if(change(str2,a,b)){
					goto end;
				}
			}
		}
end:
		printf("%s\n",str2);
	}
	
	return 0;
}

Measured memory_bytes: 1020
import java.util.BitSet;
import java.util.Scanner;

public class Main{
	public static void main(String[] args){
		Scanner in = new Scanner(System.in);
		while(true){
			int m = in.nextInt();
			int n = in.nextInt();
			if(n == 0) break;
			Point[] table = new Point[m+1];
			int[][] map = new int[1001][1001];
			int x = 500;
			int y = 500;
			int[] dx = {1, 0, -1, 0};
			int[] dy = {0, -1, 0, 1};
			int dir = 3;
			BitSet p = prime(m);
			for(int i=1; i<=m; i++){
				map[y][x] = i;
				table[i] = new Point(x, y);
				if(map[y+dy[(dir+1)%4]][x+dx[(dir+1)%4]] == 0){
					dir = (dir+1)%4;
				}
				x += dx[dir];
				y += dy[dir];
			}
			int[][] dp = new int[1001][1001];
			for(int i=0; i<=1000; i++){
				for(int j=0; j<=1000; j++){
					dp[i][j] = -1;
				}
			}
			dp[table[n].y][table[n].x] = p.get(map[table[n].y][table[n].x])?1:0;
			for(int i=table[n].y; i<1000; i++){
				for(int j=0; j<=1000; j++){
					int max = -1;
					for(int k=-1; k<=1; k++){
						if(j+k < 0 || j+k > 1000 || map[i][j+k] == -1) continue;
						max = Math.max(max, dp[i][j+k]);
					}
					if(max == -1) continue;
					dp[i+1][j] = max + (p.get(map[i+1][j])?1:0);
				}
			}
			int res = 0;
			int resId = 0;
			for(int i=0; i<=1000; i++){
				for(int j=0; j<=1000; j++){
					if((dp[i][j] > res || dp[i][j] == res && resId < map[i][j]) && p.get(map[i][j])){
						res = dp[i][j];
						resId = map[i][j];
					}
				}
			}
			System.out.println(res+" "+resId);
		}
	}
	
	public static String dump(int[][] map, int s, int t){
		StringBuilder sb = new StringBuilder();
		for(int i=s; i<=t; i++){
			for(int j=s; j<=t; j++){
				sb.append(map[i][j]+"\t");
			}
			sb.append("\n");
		}
		return sb.toString();
	}
	
	public static BitSet prime(int max){
		// 10^7: 93ms
		// 4*10^7: 687ms
		// 5*10^7: 922ms
		// 10^8: 2016ms
		BitSet isPrime = new BitSet(max+1);
		isPrime.set(2, max+1);
		for(long i=2; i*i<=max; i=isPrime.nextSetBit((int)i+1)){
//			if(i==-1) break; // iが小さいとき必要?
			for(int j=(int)(i<<1); j<=max; j+=i){
				isPrime.clear(j);
			}
		}
		return isPrime;
	}
}

class Point{
	int x, y;
	public Point(int x, int y){
		this.x = x;
		this.y = y;
	}
}

Measured memory_bytes: 165772
//-- In the name of ALLAH --
// We're nothing and you're everything.
// Ya Ali!
#include<bits/stdc++.h>
using namespace std;

#define      pai              acos(-1)
#define      ff               first
#define      ss               second
#define      ll               long long
#define      pb               push_back
#define      mp               make_pair
#define      pll              pair<ll,ll>
#define      sz(a)            (ll)a.size()
#define      endl             "\n"
#define      gcd(a, b)        __gcd(a, b)
#define      lcm(a, b)        ((a)*((b)/gcd(a,b))
#define      all(vec)         vec.begin(),vec.end()
#define      ms(a, b)         memset(a,b,sizeof(a))
#define      TEST_CASE(t)     for(int zz=1;zz<=t;zz++)
#define      PRINT_CASE       printf("Case %d: ",zz)
#define      fii              freopen("input.txt","r",stdin);
#define      foo              freopen("output.txt","w",stdout);
#define      FAST             ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);

const ll M   = 1e9+7;
const ll mxn = 1e5+7;

ll dp[2020];

ll rec(ll n)
{
    if(n==0)
    {
        return 1;
    }
    else if(n<=2)
    {
        return 0;
    }
    if(dp[n]!=-1)
    {
        return dp[n];
    }
    ll ans=0;
    for(ll i=3;i<=n;i++)
    {
        ans=(ans+rec(n-i))%M;
    }
    return dp[n]=ans;
}
int  main()
{
    ll i,j,k,a,b,c,d,n,m,t,x,y,z,u,v,s;
    cin>>s;
    if(s<=2)
    {
        cout<<0<<endl;
    }
    else
    {
        ms(dp,-1);
        ll ans=rec(s);
        cout<<ans<<endl;
    }
    return 0;
}


Measured memory_bytes: 3560
//                             In The Name Of Allah
#include <bits/stdc++.h>
#define	ss second
#define ff first
#define use_fast ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define ret(n) return cout << n, 0
#define se(n) cout << setprecision(n) << fixed
#define pb push_back
#define int long long
#define ld long double
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops")
#pragma GCC optimize("no-stack-protector,fast-math")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std; 
 
const int N = 1e6 + 100, OO = 1e9 + 7, T = 410, M = 998244353, P = 6151, SQ = 800, lg = 32;
typedef pair <int, int> pii;
int a[N], num[N];

int get(int x) {
	if(x <= 1)
		return 0;
	x = (x * (x - 1)) / 2;
	return x;
}

int32_t main() {
	use_fast;
	int n;
	cin >> n;
	int ans = 0;
	for(int i = 0; i < n; i++) {
		cin >> a[i];
		ans -= get(num[a[i]]);
		num[a[i]]++;
		ans += get(num[a[i]]);
	}
	for(int i = 0; i < n; i++) {
		ans -= get(num[a[i]]);
		num[a[i]]--;
		ans += get(num[a[i]]);
		cout << ans << endl;
		ans -= get(num[a[i]]);
		num[a[i]]++;
		ans += get(num[a[i]]);		
	}
	return 0; 
} 
/*
be carefull :
1- if not solve after 20 min, read again twice
2- after submit read the code again
3- fun with contest
4- ... 
*/

Measured memory_bytes: 7296
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const ll MOD = 1000000007;
const ld PI = acos(-1);  
const ld EPS = 0.0000000001;
#define REP(i, n) for(ll i=0; i<(ll)(n); i++)
#define REPD(i, n) for(ll i=n-1; 0<=i; i--)
#define FOR(i, a, b) for(ll i=a; i<(ll)(b); i++)
#define FORD(i, a, b) for(ll i=a; (ll)(b)<=i; i--)
#define ALL(x) x.begin(), x.end()
#define MAX(x) *max_element(ALL(x))
#define MIN(x) *min_element(ALL(x))


int main(){
    int n;  cin >> n;
    vector<ll> a(n);
    REP(i, n) cin >> a.at(i);
    sort(ALL(a));

    deque<ll> ori, out;

    REP(i, n) ori.push_back(a[i]);
    out.push_back(ori.front());
    ori.pop_front();
 
    while(!ori.empty()){
        ll fv=out.front(), bv=out.back();
        ll frontx = max(abs(fv-ori.front()), abs(bv-ori.front()));
        ll backx = max(abs(fv-ori.back()), abs(bv-ori.back()));
        if(backx<frontx){
            if(abs(bv-ori.front())<abs(fv-ori.front())) out.push_front(ori.front());
            else out.push_back(ori.front());
            ori.pop_front();
        }else{
            if(abs(bv-ori.back())<abs(fv-ori.back())) out.push_front(ori.back());
            else out.push_back(ori.back());
            ori.pop_back();
        }
        
    }
    ll ans=0, x=out.front();
    out.pop_front();
    if(out.empty()) ans=x;
    while(!out.empty()){
        ans += abs(x-out.front());
        x = out.front();
        out.pop_front();
    }
    

    cout << ans << endl;


}

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


int main(){
  int a;
  cin>>a;
  for(int i=1;i<=a;i++){
    int x,y,w,h,q,e;
    cin>>x>>y>>w>>h;
    q=x+w;
    e=y+h;
    int catn,catin=0;
    cin>>catn;
    int catx[catn],caty[catn];
    for(int j=0;j<catn;j++){
      cin>>catx[j]>>caty[j];
      if(x<=catx[j] && catx[j]<=q && y<=caty[j] && caty[j]<=e){
	  catin=catin+1;
      }
    }
    cout<<catin<<endl;
  }
  
  return 0;
}

Measured memory_bytes: 1160
#include <iostream>
#include <iomanip>
#include <utility>
#include <cmath>
#include <random>
#include <vector>
#include <tuple>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <string>
#include <algorithm>
using namespace std;

#define rep(i,n) for(int i = 0; i<n; ++i)
#define REP(i,n) for(int i = 1; i<n; ++i)
#define all(x) begin(perm),end(perm)
#define showall(obj) for(auto x:obj)cout<<x<<endl;
typedef long long ll;
typedef pair<int,int> ip;
typedef pair<ll,ll> lp;
typedef vector<int> vint;
typedef vector<ll> vll;
const int inf = 100100100;
const ll INF = 1LL<<60;
const int MOD = (int)1e9 + 7;

int main(){
    int n; cin>>n;
    vint d(n); rep(i,n)cin>>d[i];
    sort(d.begin(),d.end());
    if(d[n/2] == d[n/2-1]){cout<<0<<endl; return 0;}
    else{cout<<d[n/2]-d[n/2-1]<<endl; return 0;}
}

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

using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;

const int N = 100010, mod = 1e9 + 7;

LL n, m;

LL solve(LL n, LL m)
{
    if(n % 3 == 0) return 0;
    LL res = (LL)m;
    for(int i = 1; i < n; i++)
    {
        LL v[] = {i * m, m / 2 * (n - i), (n - i) * (m - m / 2)};
        sort(v, v + 3);

        res = min(res, v[2] - v[0]);
    }
    return res;
}

int main()
{
    cin >> n >> m;

    cout << min(solve(n, m), solve(m, n)) << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <iomanip>
using namespace std;
#define reps(i,s,n) for(int i = s; i < n; i++)
#define rep(i,n) reps(i,0,n)
#define Rreps(i,n,e) for(int i = n - 1; i >= e; --i)
#define Rrep(i,n) Rreps(i,n,0)
#define ALL(a) a.begin(), a.end()
#define fi first
#define se second
#define mp make_pair
typedef long long ll;
typedef vector<ll> vec;
typedef vector<vec> mat;

ll N,M,H,W,K,Q,A,B,L,R;
string S, T;
const ll MOD = (1e+9) + 7;
const ll INF = 1LL << 60;
typedef pair<ll,ll> P;

int main() {
    cin>>N;
    vec l(N), r(N);
    ll maxL = -1, minR = INF, Lid, Rid, max_range = 0;
    rep(i,N){
        cin>>l[i]>>r[i];
        ++r[i]; //半開区間
        if(maxL < l[i]){
            maxL = l[i];
            Lid = i;
        }
        if(minR > r[i]){
            minR = r[i];
            Rid = i;
        }
        if(max_range < r[i] - l[i]) max_range = r[i] - l[i];
    }
    ll ans = max_range + max(0LL, minR - maxL);
    ll left = l[Rid];
    vec ord(N);
    rep(i,N) ord[i] = i;
    sort(ALL(ord), [&](ll x, ll y){
        return r[x] < r[y];
    });
    rep(i,N){
        ll id = ord[i];
        if(id == Rid) continue;
        ll r1 = max(0LL, minR - left), r2 = max(0LL, r[id] - maxL);
        ans = max(ans, r1 + r2);
        left = max(left, l[id]);
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 2560
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;
signed main() { 
  ios::sync_with_stdio(false); cin.tie(0); 
  int n;
  cin >> n;
  vector<vector<int>> in(n, vector<int>(n));
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      cin >> in[i][j];
    }
  }
  long long ans = 0;
  for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
      ans += min(in[i][j], in[j][i]);
    }
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 3220
#include <bits/stdc++.h>
#define fastio std::ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;

int main() {
	fastio;
	int n;  cin>>n;
	vector<int> dp(3);
	// dp[i] - the total cost such that we did activity i on the last considered day
	for(int day=0;day<n;day++){
	    vector<int> new_dp(3,0);
	    vector<int> c(3);       // c -cost
	    for(int i=0;i<3;i++)
	        cin>>c[i];
	    for(int i=0;i<3;i++)
	        for(int j=0;j<3;j++)
	            if(i!=j)
	                new_dp[j]=max(new_dp[j], dp[i]+c[j]);
	    dp=new_dp;
	}
	cout<<max({dp[0],dp[1],dp[2]});
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
    priority_queue<pair<long long,long long>> q;
    long long x,y,a,b,c,color,apple,ans=0;
    long long red=0,green=0,nocolor=0;
    cin>>x>>y>>a>>b>>c;
    color = 0;//red
    for(int i=0;i<a;i++)
    {
        cin>>apple;
        q.push(make_pair(apple,color));
    }
    color = 1;//green
    for(int i=0;i<b;i++)
    {
        cin>>apple;
        q.push(make_pair(apple,color));
    }
    color = 2;//no color
    for(int i=0;i<c;i++)
    {
        cin>>apple;
        q.push(make_pair(apple,color));
    }
    while(q.size()>0)
    {
        color = q.top().second;
        if(color == 0)
        {
            if(red<x)
            {
                red++;
                ans+=q.top().first;
            }
        }
        else if(color == 1)
        {
            if(green<y)
            {
                green++;
                ans+=q.top().first;
            }

        }
        else
        {
            nocolor++;
            ans+=q.top().first;
        }
        if((red+green+nocolor)==(x+y))
        {
            cout<<ans<<'\n';
            break;
        }
        q.pop();
    }




}


Measured memory_bytes: 10604
#include<cstdio>
#include<cstring>
#include<algorithm>
int n,a[200010];
long long sum1[200010],sum2[200010],ans=1e18;
template<class T>
inline void read(T&a){
	char c=getchar();
	for(a=0;(c<'0'||c>'9')&&c!='-';c=getchar());
	bool f=0;
	if(c=='-')f=1,c=getchar();
	for(;c>='0'&&c<='9';c=getchar())a=a*10+c-'0';
	if(f)a=-a;
}
int main(){
	read(n);
	for(int i=1;i<=n;i++)read(a[i]),sum1[i]=sum1[i-1]+a[i];
	for(int i=n;i;i--)sum2[i]=sum2[i+1]+a[i];
	for(int i=1;i<n;i++)
		if(std::abs(sum1[i]-sum2[i+1])<ans)ans=std::abs(sum1[i]-sum2[i+1]);
	printf("%lld\n",ans);return 0;
}

Measured memory_bytes: 4096
import sys

N = int(input())
H = list(map(int,input().split()))

count = 0
ans = 0

for i in range(N-1) :
	if H[i]>=H[i+1] :
		count+=1
	else :
		if ans<=count:
			ans= count
		count=0
	#print(ans)
	#print(count)
if ans<=count:
	ans= count
print(ans)

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

#define rep(i, s, n) for (int i = s; i < n; ++i)
#define rrep(i, n) for (int i = n - 1; i > -1; --i)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
using namespace std;
const long long INF = 1000000000;
typedef long long ll;
typedef pair<int, int> P;

const string YES = "Yes";
const string NO = "No";

void func(long long N, long long M, std::vector<long long> A) {
    ll sum = 0;
    rep(i, 0, N) { sum += A[i]; }
    ll l = sum / (4 * M);
    ll cnt = 0;
    if (sum % (4 * M) == 0) {
        rep(i, 0, N) {
            if (A[i] >= l) cnt++;
        }
    } else {
        rep(i, 0, N) {
            if (A[i] > l) cnt++;
        }
    }

    if (cnt >= M) {
        cout << YES << endl;
    } else {
        cout << NO << endl;
    }
}

int main() {
    // cout << fixed << setprecision(5);

    long long N;
    scanf("%lld", &N);
    long long M;
    scanf("%lld", &M);
    std::vector<long long> A(N);
    for (int i = 0; i < N; i++) {
        scanf("%lld", &A[i]);
    }
    func(N, M, std::move(A));
    return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int a = sc.nextInt();
		int b = sc.nextInt();
		int answer = 0;
		for(int i =1;i <= n;i++) {
			int digitSum = calcDigitSum(i);
			if(digitSum >= a && digitSum <= b) {
				answer+= i;
			}
		}
		System.out.println(answer);
	}

	private static int calcDigitSum(int i) {
		String[] digitArray = String.valueOf(i).split("");
		int result = 0;
		for(String digit : digitArray) {
			result += Integer.parseInt(digit);
		}
		return result;
	}
}

Measured memory_bytes: 50620
from collections import defaultdict
N, K, L = map(int,input().split())
data = [[0, 0] for _ in range(N)]
Lpath = [[] for _ in range(N)]
Tpath = [[] for _ in range(N)]

for _ in range(K):
    p, q = map(int,input().split())
    p -= 1
    q -= 1
    Lpath[p].append(q)
    Lpath[q].append(p)
    
for _ in range(L):
    r, s = map(int,input().split())
    r -= 1
    s -= 1
    Tpath[r].append(s)
    Tpath[s].append(r)
    
for i in range(N):
    if data[i][0]:
        continue
    data[i][0] = i + 1
    stack = [i]
    while stack:
        s = stack.pop()
        for to in Lpath[s]:
            if data[to][0]:
                continue
            data[to][0] = i + 1
            stack.append(to)

for i in range(N):
    if data[i][1]:
        continue
    data[i][1] = i + 1
    stack = [i]
    while stack:
        s = stack.pop()
        for to in Tpath[s]:
            if data[to][1]:
                continue
            data[to][1] = i + 1
            stack.append(to)

ans = [0] * N
d = defaultdict(int)         
for i in range(N):
    d[tuple(data[i])] += 1
for i in range(N):
    ans[i] = d[tuple(data[i])]

print(*ans)

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

int vis[(int)1e5+2];
vector<int> g[(int)1e5+2];

int main(){
	int n;
	cin>>n;
	for(int i=1;i<n;++i){
		int a,b;
		cin>>a>>b;
		g[a].push_back(b);
		g[b].push_back(a);
	}

	int level1[n+1], level2[n+1];

	memset(level1, 0, sizeof level1);

	queue<int> q;

	q.push(1);
	memset(vis, 0, sizeof vis);

	while(!q.empty())
	{
		int t = q.front();
		vis[t]=1;
		q.pop();
		for(int i=0;i<g[t].size();++i)
		{
			if(vis[g[t][i]] == 0)
			{
				vis[g[t][i]]=1;
				q.push(g[t][i]);
				level1[g[t][i]] = level1[t] + 1;
			}
		}
	}

	memset(level2, 0, sizeof level2);

	q.push(n);
	memset(vis, 0, sizeof vis);

	while(!q.empty())
	{
		int t = q.front();
		vis[t]=1;
		q.pop();
		for(int i=0;i<g[t].size();++i)
		{
			if(vis[g[t][i]] == 0)
			{
				vis[g[t][i]]=1;
				q.push(g[t][i]);
				level2[g[t][i]] = level2[t] + 1;
			}
		}
	}

	int f = 0, snuke = 0;

	for(int i=1;i<=n;++i)
	{
		if(level1[i]<=level2[i])
		{
			++f;
		}
		else
		{
			++snuke;
		}
	}

	if(f>snuke)
	{
		cout << "Fennec" << endl;
		return 0;
	}

	cout << "Snuke" << endl;
	return 0;
}

Measured memory_bytes: 7040
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;
using ll = long long;
constexpr long long INF = 1LL << 60;

struct Edge {
    int src, dst, cost;
    Edge(int s, int d, int c = 1) : src(s), dst(d), cost(c) {}
    bool operator<(const Edge &e){ return cost < e.cost;}
};
using Edges = vector<Edge>;
using Graph = vector<Edges>;

// O(|V||E|)
bool bellman_ford(int s, Graph &g, vector<long long> &dist) {
    int n = g.size();
    dist.assign(n, INF);
    dist[s] = 0;

    for(int i = 0; i < n*2; ++i) {
        bool update = false;
        for(int v = 0; v < n; ++v) {
            for(Edge e : g[v]) {
                if(dist[e.src] != INF && dist[e.dst] > dist[e.src] + e.cost) {
                    dist[e.dst] = dist[e.src] + e.cost;
                    update = true;

                    if(i >= n && e.dst == n-1) {
                        // negative cycle
                        return true;
                    }
                }
            }
        }
        if(!update) break;
    }
    return false;
}

int main() {
    cin.tie(0); ios_base::sync_with_stdio(false);
    int N,M; cin >> N >> M;
    Graph g(N);
    for(int i=0; i < M; ++i){
        int a,b,c;
        cin >> a >> b >> c;
        --a; --b;
        g[a].emplace_back(a,b,-c);
    }
    vector<long long> dist;
    bool negative = bellman_ford(0, g, dist);
    if(negative) cout << "inf";
    else cout << -dist[N-1];
    cout << endl;
    return 0;
}

Measured memory_bytes: 384
#include <stdio.h>
#include <assert.h>
#include <fstream>
#include <iostream>
#include <algorithm>
#include <limits>
#include <array>
#include <vector>
#include <queue>
#include <set>
#include <map>
//#include <unordered_map>
//#include <unordered_set>
//#include <boost/container/static_vector.hpp>
//#include <boost/unordered_set.hpp>
//#include <boost/unordered_map.hpp>
//#include <unistd.h>

//#include <cv.h>
//#include <highgui.h>
#include <stdlib.h>
#include <string>

std::vector<std::pair<long long, int>> prime_factor(long long n) {
    // nの素因数分解。計算量はO(sqrt(n))なので、long longも入り得る。
    // intにおさまらない素数を入れた場合を考えて、keyはlong longにしておく。戻り値はintで十分と思われる。
    std::vector<std::pair<long long, int>> res;
    for (long long i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            int num = 0;
            while(n % i == 0) {
                num++;
                n = n / i;
            }
            res.push_back(std::pair<long long, int>({i, num}));
        }
    }
    if (n != 1) {
        res.push_back(std::pair<long long, int>({n, 1}));
    }
    return res;
}

long long pow_mod(long long x, long long n, long long mod_num) {
    long long res = 1;
    while (n > 0) {
        if (n & 1) { res = (res * x) % mod_num; }
        x = (x * x) % mod_num;
        n = (n >> 1);
    }
    return res;
}

class Combi_Num {
    public:
    long long mod_num;
    std::vector<long long> factorial, factorial_inv, inv;
    Combi_Num() {}
    Combi_Num(const int n, const long long mod_num_in) {
        mod_num = mod_num_in;
        factorial.resize(n+1, 0);
        factorial_inv.resize(n+1, 0);
        inv.resize(n+1, 0);
        factorial[0] = 1;
        factorial_inv[0] = 1;
        inv[0] = 1;
        for (int i = 1; i <= n; i++) {
            factorial[i] = (factorial[i-1] * i) % mod_num;
            inv[i] = pow_mod(i, mod_num - 2, mod_num);
            factorial_inv[i] = (factorial_inv[i-1] * inv[i]) % mod_num;
        }
    }

    long long combi(const int n, const int r) {
        return (factorial[n] * ((factorial_inv[r] * factorial_inv[n-r]) % mod_num)) % mod_num;
    }

    long long perm(const int n, const int r) {
        return (factorial[n] * factorial_inv[n-r]) % mod_num;
    }
};

const int MAX_N = 300000;
const long long MOD = 1000000007;

int N, M;

Combi_Num combi_num = Combi_Num(MAX_N, MOD);

int main(int argc, char **argv) {
    std::cin >> N >> M;

    std::vector<std::pair<long long, int>> factor = prime_factor(M);

    long long ret = 1;
    for (auto pair : factor) {
        ret = ret * combi_num.combi(pair.second + N - 1, N - 1);
        ret = ret % MOD;
    }

    std::cout << ret << std::endl;


    return 0;
}

Measured memory_bytes: 7296
buildings = []
4.times do |i|
  floors = []
  3.times do |j|
    rooms = []
    10.times do |k|
      rooms[k] = 0
    end
    floors[j] = rooms
  end
  buildings[i] = floors
end

n = gets.to_i
n.times do |i|
  b, f, r, p = gets.split.map(&:to_i)
  buildings[b - 1][f - 1][r - 1] += p
end

4.times do |i|
  if i != 0 then
    puts "####################"
  end
  3.times do |j|
    10.times do |k|
      printf(" %d", buildings[i][j][k])
    end
    puts
  end
end



Measured memory_bytes: 6904
C = [list(map(int,input().split())) for _ in range(3)]
#a1 = 0 と固定
b = []
for i in range(3):
  b.append(C[0][i] - 0)
a = []
for i in range(3):
  a.append(C[i][0] - b[0])
ans = "Yes"
for i in range(3):
  for j in range(3):
    if(C[i][j] != a[i] + b[j]):
      ans = "No"
print(ans)

Measured memory_bytes: 3064
#include<iostream>
#include<string>
#include<cstdio>
#include<deque>
#include<list>
#include<queue>
#include<stack>
#include<vector>
#include<utility>
#include<algorithm>
#include<map>
#include<set>
#include<complex>
#include<cmath>
#include<limits>
#include<cassert>
#include<bitset>
#include<numeric>
#include<functional>

using namespace std;


void dfs(int cur, vector<int> &a, vector<bool> &used, int &cnt) {
  cnt++;
  used[cur] = true;
  int nxt = a[cur];
  if(used[nxt] == false) dfs(nxt, a, used, cnt);
}

int main() {
  
  int n; cin >> n;
  vector<int> r(n);
  vector<int> c(n);
  set<int> h;
  set<int> w;


  for(int i = 0; i < n; i++) {
    cin >> r[i] >> c[i];
    h.insert(r[i]);
    w.insert(c[i]);
  }

  if(h.size() != n or w.size() != n) {
    cout << -1 << endl;
    return 0;
  }

  vector<int> a(n);
  for(int i = 0; i < n; i++) {
    a[r[i] - 1] = c[i] - 1;
  }
  
  int ans = 0;
  vector<bool> used(n, false);

  for(int i = 0; i < n; i++) {
    if(used[i] == false) {
      int cnt = 0;
      dfs(i, a, used, cnt);
      ans += (cnt - 1);
    }
  }

  cout << ans << endl;

  return 0;
}



Measured memory_bytes: 13320
#include <iostream>
#include <vector>
using namespace std;
int main(){
	int n, p, q;
	while( 1 ){
		cin >> n >> p;
		vector<int> stone(n);
		if( n == 0 && p == 0 ) break;
		for( int j = 0; j < n; j++ ) stone[j] = 0;
		q = p;
		int i = 0;
		while( 1 ){
			if( q != 0 ){
				stone[i]++;
				q--;
				if( q == 0 && p == stone[i] ){
					cout << i << endl;
					break;
				}
			}else{
				q += stone[i];
				stone[i] = 0;
			}
			i++;
			if( i == n ) i = 0;
		}
	}
}

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

int gcd(int a, int b){
	if(a<b)swap(a,b);

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

int main(){
	int N,X;	cin>>N>>X;
	vector<int> d(N);

	int x;
	for(int i=0;i<N;i++){
		cin>>x;
		d[i]=abs(x-X);
	}

	int ans;
	if(N>1){
		ans=gcd(d[0], d[1]);

		for(int i=2;i<N;i++){
			ans=gcd(ans,d[i]);
		}
	}else{
		ans=d[0];
	}

	cout<<ans<<endl;



	return 0;
}


Measured memory_bytes: 640
#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>
#include <algorithm> // sort
#include <math.h> // sort

#define REP(i, n) for (long long i = 0; i < (n); i++) 
typedef long long ll;
static const ll MOD = 1000000007;
static const ll INF = 1000000000000000000LL;
using namespace std;

int main(){
    //std::ifstream in("input.txt");
    //std::cin.rdbuf(in.rdbuf());
    int x,t;
    cin >> x >> t;

    ll res = max(0, x - t);

    cout << res << endl;
    return 0;    
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
using namespace std;

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int n, m;
	cin >> n >> m;
	string a[n], b[m];
	for (int i=0; i<n; i++) {
		cin >> a[i];
	}
	for (int i=0; i<m; i++) {
		cin >> b[i];
	}
	for (int i=0; i+m-1<n; i++) {
		for (int j=0; j+m-1<n; j++) {
			bool same = true;
			for (int r=0; r<m && same; r++) {
				for (int c=0; c<m && same; c++) {
					if (a[i+r][j+c] != b[r][c]) same = false;
				}
			}
			if (same) {cout << "Yes"; return 0;}
		}
	}
	cout << "No";
}

Measured memory_bytes: 256
import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

// Everything Starts With Your Vote
// 2012/12/04
public class Main{
	Scanner sc=new Scanner(System.in);

	int n, m, k, p;
	R[] rs, fs;
	boolean[] isfav;

	void run(){
		for(;;){
			n=sc.nextInt();
			m=sc.nextInt();
			k=sc.nextInt();
			p=sc.nextInt();
			if((n|m|k|p)==0){
				return;
			}

			rs=new R[n];
			HashMap<String, Integer> map=new HashMap<String, Integer>();
			for(int i=0; i<n; i++){
				String name=sc.next();
				int x=sc.nextInt();
				rs[i]=new R(name, x);
			}
			sort(rs);
			for(int i=0; i<n; i++){
				map.put(rs[i].name, i);
			}

			fs=new R[m];
			isfav=new boolean[n];
			for(int i=0; i<m; i++){
				String fav=sc.next();
				int j=map.get(fav);
				fs[i]=rs[map.get(fav)];
				isfav[j]=true;
			}
			sort(fs);

			int left=0, right=m;
			for(int t=0; t<100; t++){
				int mid=(left+right)/2;
				if(ok(mid)){
					left=mid;
				}else{
					right=mid;
				}
			}

			if(left+1<=m&&ok(left+1)){
				println((left+1)+"");
			}else{
				println(left+"");
			}
		}
	}

	boolean ok(int c){
		if(k-c<0){
			return false;
		}
		int index=-1;
		int count=0;
		for(int i=0; i<n; i++){
			if(!isfav[i]){
				if(++count==k-c+1){
					index=i;
					break;
				}
			}
		}
		if(index==-1){
			return true;
		}

		int q=p;
		for(int i=0; i<c; i++){
			if(fs[i].name.compareTo(rs[index].name)<0){
				q-=max(rs[index].x-fs[i].x, 0);
			}else{
				q-=max(rs[index].x+1-fs[i].x, 0);
			}
			if(q<0){
				return false;
			}
		}
		return true;
	}

	class R implements Comparable<R>{
		String name;
		int x;

		R(String name, int x){
			this.name=name;
			this.x=x;
		}

		@Override
		public int compareTo(R r){
			if(r.x!=x){
				return r.x-x;
			}else{
				return name.compareTo(r.name);
			}
		}

		@Override
		public String toString(){
			return name+":"+x;
		}
	}

	void println(String s){
		System.out.println(s);
	}

	public static void main(String[] args){
		new Main().run();
	}
}

Measured memory_bytes: 41000
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vl = vector<ll>;
using vvl = vector<vector<ll>>;
#define all(x) x.begin(),x.end()
#define rep(i,j,n) for (int i = j; i < (int)(n); i++)
#define _GLIBCXX_DEBUG
#define MOD 1000000007
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; }
//name[i][j]-> vvl name(i,vl(j))
//map<int,int>mp
//余りを切り上げる =>  (a + b - 1) / b 

signed main(){
	string s; cin>>s;
	int m=s.size();
	rep(i,0,2) s.pop_back();
	rep(i,0,m/2){
		int n=s.size();
		bool ok=true;
		rep(j,0,n/2){
			if(s[j]!=s[(n/2)+j]) ok=false;
		}
		if(ok){
			cout<<s.size();
			return 0;
		}
		rep(k,0,2) s.pop_back();
	}
	
	return 0;
}

Measured memory_bytes: 256
import numpy as np

N, K = map(int, input().split())
K2 = K*2

M = np.zeros((K2, K2), int)
nb = 0
for _ in range(N):
  x, y, c = input().split()
  x = int(x) % K2
  y = int(y) % K2
  if c=='B': nb+=1
  M[x, y] += 1 if c=='W' else -1

Sx = np.zeros((K2, K2+1), int)
for y in range(K2):
  Sx[:, y+1] = Sx[:, y] + M[:, y]

S = np.zeros((K2+1, K2+1), int)
for x in range(K2):
  S[x+1] = S[x] + Sx[x]

ans = -1000000
for x in range(K2):
  x0 = 0
  x1 = max(x-K , 0)
  x2 = x
  x3 = min(x+K , K2)
  x4 = K2

  T1 = S[x4] - S[x3] + S[x2] - S[x1]
  T2 = S[x3] - S[x2] + S[x1] - S[x0]

  U = T1[K2] - T1[K:K2] + T1[:K] + T2[K:K2] - T2[:K]
  ans = max(ans, np.max(U))
  
print(nb + ans)

Measured memory_bytes: 106188
n=int(input())
a=[list(map(int,input().split()))for i in range(n)]

ans=0
for i in range(n):
    for j in range(n):
        x,y=a[i]
        xx,yy=a[j]
        ans+=((x-xx)**2+(y-yy)**2)**0.5
print(ans/n)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
 
using namespace std;
 
#define ll              long long
#define l1(i, n)        for (ll i = 1; i <= n; i++)
#define l0(i, n)        for (ll i = 0; i < n; i++)
#define lo(i, s, n)     for (ll i = s; i <= n; i++)
#define sca(n)          scanf("%lld", &n)
#define pri(n)          printf("%lld", n)
#define pb              push_back
#define mp              make_pair
#define sorted(x)       sort(x.begin(), x.end())
#define reversed(x)     reverse(x.begin(), x.end())
#define all(x)          x.begin(), x.end()
#define ms(a, b)        memset(a, b, sizeof(a));
#define cases(tc)       cout<<"Case "<<tc<<": "
#define nl              cout<<"\n";
#define pnl             printf("\n");
#define pi              acos(-1)
#define mod             1000000007
#define inf             999999999999999999
			
 


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

    /*
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif
    */

    ll t;
    t=1;
    while(t--){
        ll n;
        cin>>n;
        ll x[n];
        l0(i, n) cin>>x[i];
        ll cnt=0;
        for(ll i=0; i<n; i++){
            for(ll j=i+1; j<n; j++){
                for(ll k=j+1; k<n; k++){
                    ll mx=max(x[i], x[j]);
                    mx=max(mx, x[k]);
                    if(x[i]+x[j]+x[k]-mx>mx && x[i]!=x[j] && x[j]!=x[k] && x[i]!=x[k]) cnt++;
                }
            }
        }
        cout<<cnt;
        nl
    }
    return 0;
}


Measured memory_bytes: 3652
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define f first
#define s second
#define mp make_pair
int main()
{
	int n;
	cin>>n;
	int arr[n];
	for(int i=0;i<n;i++)
	cin>>arr[i];
	int dp[n]={0};
	dp[0]=0;
	dp[1]=abs(arr[0]-arr[1]);
	for(int i=2;i<n;i++)
	{
		dp[i]=min(dp[i-1]+abs(arr[i-1]-arr[i]),dp[i-2]+abs(arr[i-2]-arr[i]));
		
	}
	cout<<dp[n-1]<<endl;
	return 0;
}
  


Measured memory_bytes: 1024
a = input().split()
students = int(a[0])
checkpoints = int(a[1])

st_coord = []
for i in range(students):
    b = input().split()
    st_coord.append((int(b[0]), int(b[1])))

ch_coord = []
for j in range(checkpoints):
    c = input().split()
    ch_coord.append((int(c[0]), int(c[1])))


shortest = abs(st_coord[0][0] - ch_coord[0][0]) + abs(st_coord[0][1] - ch_coord[0][1])
for k in range(len(st_coord)):
    index = 1
    shortest = abs(st_coord[k][0] - ch_coord[0][0]) + abs(st_coord[k][1] - ch_coord[0][1])
    for l in range(len(ch_coord)):
        distance = abs(st_coord[k][0] - ch_coord[l][0]) + abs(st_coord[k][1] - ch_coord[l][1])
        if distance < shortest:
            shortest = distance
            index = l + 1
    print(index)


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

int main(){
  string str;
  cin>>str;
  if(str.at(0)=='7'||str.at(1)=='7'||str.at(2)=='7'){
    printf("Yes\n");
  }else{
    printf("No\n");
  }
  return 0;
}

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

inline int sib(int n){
    return (n & 1) ? (n - 1):(n + 1);
}

int update_gcd(int i, const vector<int> & gcds){
    int g = gcds[sib(i)];
    i = i / 2;
    while (i > 1){
        g = __gcd(g, gcds[sib(i)]);
        i = i / 2;
    }
    return g;
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    cin >> N;
    vector<int> gcds(2 * N, 0LL);
    for (int i = 0; i < N; ++i) cin >> gcds[N + i];
    for (int i = N - 1; i >= 1; --i) gcds[i] = __gcd(gcds[2 * i], gcds[2 * i + 1]);
    int ans = 1;
    for (int i = N; i < 2 * N; ++i) ans = max(ans, update_gcd(i, gcds));
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 1024
#include <cstdio>
#include <vector>
#include <algorithm>
typedef long long ll;

const ll mod = 998244353;
ll dp[202020];
std::vector<int> v[10];

struct Node
{
    ll sum, lazy;
} tree[808080];

void lazy(int node, int l, int r)
{
    tree[node].sum += tree[node].lazy * (r - l + 1);
    tree[node].sum %= mod;
    if (l != r)
    {
        tree[node * 2].lazy += tree[node].lazy;
        tree[node * 2 + 1].lazy += tree[node].lazy;
    }
    tree[node].lazy = 0;
}

Node merge(Node o1, Node o2)
{
    Node me;
    me.sum = (o1.sum + o2.sum) % mod;
    me.lazy = 0;
    return me;
}

void updateRange(int node, int l, int r, int s, int e, ll x)
{
    if (e < s)
        return;
    lazy(node, l, r);
    if (s > r || e < l)
    {
        return;
    }
    if (s <= l && e >= r)
    {
        tree[node].lazy += x;
        lazy(node, l, r);
        return;
    }
    int m = (l + r) >> 1;
    updateRange(node * 2, l, m, s, e, x);
    updateRange(node * 2 + 1, m + 1, r, s, e, x);
    tree[node] = merge(tree[node * 2], tree[node * 2 + 1]);
}

ll query(int node, int l, int r, int idx)
{
    lazy(node, l, r);
    if (idx > r || idx < l)
    {
        return 0;
    }
    if (l == r )
    {
        return tree[node].sum % mod;
    }
    int m = (l + r) >> 1;
    return query(node * 2, l, m, idx) + query(node * 2 + 1, m + 1, r, idx);
}

void init(int node, int l, int r)
{
    if (l == r)
    {
        tree[node] = {dp[l], 0};
        return;
    }
    int m = (l + r) >> 1;
    init(node * 2, l, m);
    init(node * 2 + 1, m + 1, r);
    tree[node] = merge(tree[node * 2], tree[node * 2 + 1]);
}

int main(void)
{
    int N, K;
    scanf("%d%d", &N, &K);

    dp[0] = 1;
    for (int i = 0; i < K; i++)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        v[i].push_back(x);
        v[i].push_back(y);
    }
    init(1, 0, N-1);

    for (int j = 0; j < N; j++)
    {
        for (int i = 0; i < K; i++)
        {
            int st = j + v[i][0];
            int ed = std::min(j + v[i][1], N-1);
            updateRange(1, 0, N - 1, st, ed, query(1, 0, N-1, j));
        }
    }
    printf("%lld\n", query(1, 0, N-1, N-1));

    return 0;
}

Measured memory_bytes: 11448
#include <bits/stdc++.h>
#define syosu(x) fixed<<setprecision(x)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef pair<double,double> pdd;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<string> vs;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<pll> vpll;
typedef pair<int,P> pip;
typedef vector<pip> vip;
const int inf=1<<30;
const ll INF=1ll<<60;
const double pi=acos(-1);
const double eps=1e-8;
const ll mod=1e9+7;
const int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};

int n,q;
vip a;

int main(){
	cin>>n>>q;
	for(int i=0;i<n;i++){
		int l,r,x;
		cin>>l>>r>>x;
		a.push_back({l-x,{x,1}});
		a.push_back({r-x,{x,0}});
	}
	sort(a.begin(),a.end());
	int I=0;
	multiset<int> st;
	for(int i=0;i<q;i++){
		int x;
		cin>>x;
		while(I<2*n&&a[I].first<=x){
			P p=a[I++].second;
			if(p.second) st.insert(p.first);
			else st.erase(st.find(p.first));
		}
		if(st.empty()) cout<<-1<<endl;
		else cout<<*st.begin()<<endl;
	}
}

Measured memory_bytes: 15980
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <cmath>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <deque>


using namespace std;

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


int main() {
	int n;
	cin >> n;
	int a[n], b[n], c[n];

	

	rep(i, n) {
		cin >> a[i];
	}
	rep(i, n) {
		cin >> b[i];
	}
	rep(i, n) {
		cin >> c[i];
	}


	sort(&a[0], &a[n]);
	sort(&b[0], &b[n]);
	sort(&c[0], &c[n]);

	int ca = 0;
	int cc = 0;
	ll total = 0;
	rep(i, n) {
		while(ca < n && a[ca] < b[i]) {
			ca++;
		}
		while(cc < n && b[i] >= c[cc]) {
			cc++;
		}
		total += (ll) ca * (ll) (n - cc); 
		//cout << "i:" << i << " ca:" << ca << " cc:" << cc << endl; 
	}


	cout << total << endl;

	return 0;
}

Measured memory_bytes: 2040
// Original: https://github.com/tanakh/competitive-rs
#[allow(unused_macros)]
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };

    ($next:expr, mut $var:ident : $t:tt $($r:tt)*) => {
        let mut $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, bytes) => {
        read_value!($next, String).into_bytes()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

#[allow(unused_imports)]
use std::cmp::{max, min};
#[allow(unused_imports)]
use std::collections::HashMap;

fn main() {
    input!(n: usize, vs: [usize; n]);

    let nax = vs.iter().max().unwrap();
    let nax = *nax;
    let mut cs = vec![0usize; nax + 1];
    // cs[i]にvs[i]の出現数を記録
    for i in 0..n {
        cs[vs[i]] += 1;
    }

    // cs[i]にi以下の数の出現数を記録
    for i in 1..nax + 1 {
        cs[i] += cs[i - 1];
    }

    // 出力用配列bsにおけるvs[i]の位置を求める
    let mut bs = vec![0usize; n];
    for i in (0..n).rev() {
        bs[cs[vs[i]] - 1] = vs[i];
        // 同じ数の要素が複数ある場合を考慮
        cs[vs[i]] -= 1;
    }

    for i in 0..n {
        if i != n - 1 {
            print!("{} ", bs[i])
        } else {
            println!("{}", bs[i]);
        }
    }
}



Measured memory_bytes: 37796
import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int n = scanner.nextInt();
        List<Long> list = new ArrayList<>();
        long result = 0;

        for (int i = 0; i < n; i++) {
            long a = scanner.nextLong();
            list.add(a);
            if (i == 0) {
                result = a;
            } else {
                result = result ^ a;
            }
        }

        for (int i = 0; i < n; i++) {
            if (i > 0) {
                System.out.print(" ");
            }
            long a = list.get(i);
            long origin = result ^ a;
            System.out.print(origin);
        }
        System.out.println();

    }
}

Measured memory_bytes: 66392
def main():
    n, k = map(int, input().split())
    s = [int(c) for c in input()]
    bl = []
    if s[0] == 0:
        bl.append(0)
    bl.append(0)
    for i in range(1, n):
        if s[i-1] != s[i]:
            bl.append(i)
    bl.append(n)
    bl.append(n)

    nbl = len(bl)
    m = [bl[i+2*k+1] - bl[i]
         for i in range(nbl - 2*k-1) if i % 2 == 0]
    if len(m) == 0:
        print(n)
    else:
        print(max(m))


main()


Measured memory_bytes: 9368
/**
 *    Coded by : lucky_21
 *               --------Lokesh Singh
**/

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

#include<ext/pb_ds/tree_policy.hpp>
#include<ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template<class T> using oset=tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;

#define     F           first
#define     S           second
#define     pb          push_back
#define     lb          lower_bound
#define     ub          upper_bound
#define     pii         pair<int,int>
#define     all(x)      x.begin(),x.end()
#define     fix         fixed<<setprecision(10)
#define     rep(i,a,b)  for(int i=int(a);i<=int(b);i++)
#define     repb(i,b,a) for(int i=int(b);i>=int(a);i--)
#define     FastIO      ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)

typedef double db;
typedef long long ll;

const int N=5e5+5;
const int mod=1e9+7;

ll n,m,f[N],inv[N];
int power(ll x,int b){
    ll res=1;
    while(b){
        if(b&1) res=res*x%mod;
        x=x*x%mod;
        b/=2;
    }
    return res;
}
void pre(){
    f[0]=inv[0]=1;
    rep(i,1,5e5){
        f[i]=f[i-1]*i%mod;
        inv[i]=power(f[i],mod-2);
    }
}
signed main(){
    FastIO;
    pre();
    cin>>n>>m;
    ll ans=f[m],s=-1;
    rep(i,1,n){
        ans=(ans+f[n]*f[m-i]%mod*inv[i]%mod*inv[n-i]%mod*s+mod)%mod;
        s=-s;
    }
    ans=ans*inv[m-n]%mod;
    ans=ans*f[m]%mod*inv[m-n]%mod;
    cout<<ans;
    return 0;
}


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

int main(){
    string S,T,U;
    cin >> S >> T;
    int A=T.size();
    U=T[A-1];
    if(S+U==T){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }
}

Measured memory_bytes: 3632
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;

class TEST{
	static void Main(){
		Sol mySol =new Sol();
		mySol.Solve();
	}
}

class Sol{
	public void Solve(){
		
		List<List<char>> L = new List<List<char>>();
		L.Add(new List<char>{ 'a' });
		
		for(int t=1;t<N;t++){
			var nL = new List<List<char>>();
			foreach(var l in L){
				int ma = 0;
				foreach(var c in l){
					ma = Math.Max(ma, (int)(c - 'a'));
				}
				for(int i=0;i<=ma + 1;i++){
					var nl = new List<char>(l);
					nl.Add((char)('a' + i));
					nL.Add(nl);
				}
			}
			L = nL;
		}
		
		var sb = new StringBuilder();
		foreach(var l in L){
			sb.AppendLine(new String(l.ToArray()));
		}
		Console.Write(sb.ToString());
		
	}
	int N;
	public Sol(){
		N = ri();
	}

	static String rs(){return Console.ReadLine();}
	static int ri(){return int.Parse(Console.ReadLine());}
	static long rl(){return long.Parse(Console.ReadLine());}
	static double rd(){return double.Parse(Console.ReadLine());}
	static String[] rsa(char sep=' '){return Console.ReadLine().Split(sep);}
	static int[] ria(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>int.Parse(e));}
	static long[] rla(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>long.Parse(e));}
	static double[] rda(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>double.Parse(e));}
}


Measured memory_bytes: 37304
#include <iostream>
using namespace std;
int main(void){
    // Your code here!
    
    for(;;){
        int n,m,a,goukei=0,hituyou=0;
        cin>>n>>m;
        if(n==0&&m==0){
            break;
        }
        hituyou=m/n;
        for(int i=0;i<n;i++){
            cin>>a;
            if(a>=hituyou){
                goukei=goukei+hituyou;
            }
            if(a<hituyou){
                goukei=goukei+a;
            }
           
        }
        cout<<goukei<<endl;
        
    }
}


Measured memory_bytes: 3100