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

using ll = long long;
using ull = unsigned long long;

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

    int n;
    cin >> n;

    map<int, int> cnt;

    for (int x = 1; x <= 100; ++x) {
        for (int y = 1; y <= 100; ++y) {
            for (int z = 1; z <= 100; ++z) {
                int p = (x * x) + (y * y) + (z * z) + (x * y) + (y*z) + (z*x);
                ++cnt[p];
            }
        }
    }

    for (int i = 1; i <= n; ++i) {
        cout << cnt[i] << "\n";
    }

    return 0;
}

Measured memory_bytes: 5464
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int a,b,c,k;
    scanf("%d%d%d%d",&a,&b,&c,&k);
    while(k--)
    {
        if(b<=a)
            b*=2;
        else
            c*=2;
    }
    if(a<b && b<c)
        printf("Yes\n");
    else
        printf("No\n");

    return 0;
}

Measured memory_bytes: 3760
#include<bits/stdc++.h>
#define LL long long

using namespace std;
const int N=2e5+10,inf=1<<30;
int rd()
{
    int x=0,w=1;char ch=0;
    while(ch<'0'||ch>'9'){if(ch=='-') w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+(ch^48);ch=getchar();}
    return x*w;
}
int mx[2][N<<2];
void psup(int o){mx[0][o]=max(mx[0][o<<1],mx[0][o<<1|1]),mx[1][o]=max(mx[1][o<<1],mx[1][o<<1|1]);}
void modif(int o,int l,int r,int lx,int x,int ty)
{
    if(l==r){mx[ty][o]=x;return;}
    int mid=(l+r)>>1;
    if(lx<=mid) modif(o<<1,l,mid,lx,x,ty);
    else modif(o<<1|1,mid+1,r,lx,x,ty);
    psup(o);
}
int quer(int o,int l,int r,int ll,int rr,int ty)
{
    if(ll<=l&&r<=rr) return mx[ty][o];
    int an=-inf,mid=(l+r)>>1;
    if(ll<=mid) an=max(an,quer(o<<1,l,mid,ll,rr,ty));
    if(rr>mid) an=max(an,quer(o<<1|1,mid+1,r,ll,rr,ty));
    return an;
}
int n,m,a[N],ps[N],va[N],an[N],sm;
void bui(int o,int l,int r)
{
    mx[0][o]=mx[1][o]=-inf;
    if(l==r) return;
    int mid=(l+r)>>1;
    bui(o<<1,l,mid),bui(o<<1|1,mid+1,r);
}

int main()
{
    n=rd(),m=n+1;
    for(int i=1,mx=0;i<=n;++i)
    {
	a[i]=rd(),ps[a[i]]=i;
	mx=max(mx,a[i]);
	va[i]=1+(mx==a[i]),sm+=mx==a[i];
    }
    bui(1,1,m);
    modif(1,1,m,n+1,0,0);
    for(int i=n;i;--i)
    {
	int dt0=quer(1,1,m,a[i]+1,m,va[i]&1)+va[i],dt1=quer(1,1,m,a[i]+1,m,(va[i]^1)&1)+va[i];
	modif(1,1,m,a[i],dt0,0),modif(1,1,m,a[i],dt1,1);
    }
    for(int i=1,m0=0,m1=0,c0=0,c1=0;i<=n;++i)
    {
	modif(1,1,m,a[i],-inf,0),modif(1,1,m,a[i],-inf,1);
	sm-=va[i]-1;
	int nm0=max(m0,a[i]),nm1=m1,nc0=c0+(nm0==a[i]),nc1=c1,xx;
	xx=sm+nc1-nc0;
	if(xx>=0&&quer(1,1,m,nm0+1,m,xx&1)>=xx)
	{
	    an[i]=0,m0=nm0,m1=nm1,c0=nc0,c1=nc1;
	    continue;
	}
	xx=sm+nc0-nc1;
	if(xx>=0&&quer(1,1,m,nm1+1,m,xx&1)>=xx)
	{
	    an[i]=0,m0=nm0,m1=nm1,c0=nc0,c1=nc1;
	    continue;
	}
	nm0=m0,nm1=max(m1,a[i]),nc0=c0,nc1=c1+(nm1==a[i]);
	xx=sm+nc1-nc0;
	if(xx>=0&&quer(1,1,m,nm0+1,m,xx&1)>=xx)
	{
	    an[i]=1,m0=nm0,m1=nm1,c0=nc0,c1=nc1;
	    continue;
	}
	xx=sm+nc0-nc1;
	if(xx>=0&&quer(1,1,m,nm1+1,m,xx&1)>=xx)
	{
	    an[i]=1,m0=nm0,m1=nm1,c0=nc0,c1=nc1;
	    continue;
	}
	puts("-1");
	return 0;
    }
    for(int i=1;i<=n;++i) printf("%d",an[i]);
    return 0;
}




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

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

template<typename H> bool chmin(H& v1, const H v2) { if (v1 > v2) { v1 = v2; return true; } return false; }
template<typename H> bool chmax(H& v1, const H v2) { if (v1 < v2) { v1 = v2; return true; } return false; }
template<typename H> void read(H& head) { cin >> head; }
template<typename H, typename ...T> void read(H& head, T& ...tail) { cin >> head; read(tail...); }
template<typename H> void write(H head) { cout << head << '\n'; }
template<typename H, typename ...T> void write(H head, T ...tail) { cout << head << " "; write(tail...); }
template<typename ...T> void die(T ...tok) { write(tok...); exit(0); }

struct Dsu {
	int dsu[55];
	Dsu() { rep(i, 0, 55) dsu[i] = -1; }
	int find(int x) {
		return dsu[x] < 0 ? x : dsu[x] = find(dsu[x]);
	}
	void merge(int u, int v) {
		u = find(u), v = find(v);
		if (u == v) return;
		if (-dsu[u] > -dsu[v]) swap(u, v);
		dsu[u] += dsu[v];
		dsu[v] = u;
	}
} dsu;

int a[2505], b[2505];

int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin.exceptions(cin.failbit);

	int n, m; read(n, m);
	rep(i, 0, m) read(a[i], b[i]);
	int ans = 0;
	rep(i, 0, m) {
		dsu = Dsu();
		rep(j, 0, m) if (j != i) dsu.merge(a[j], b[j]);
		if (dsu.dsu[dsu.find(1)] != -n) ans++;
	}
	die(ans);
}


Measured memory_bytes: 256
from operator import xor
from functools import reduce


def resolve():
    s, t = input().split()
    a, b = map(int, input().split())
    d = {s: a, t: b}
    u = input()
    d[u] -= 1
    print(d[s], d[t])

if __name__ == "__main__":
    resolve()


Measured memory_bytes: 9328
import java.util.*;
 
public class Main {
	public static void main (String[] args) {
		Scanner in = new Scanner(System.in);
		
		String s = in.next();
		int nam = s.length();
		char[] chars = s.toCharArray();
		
		int flag = 0;int flag1 = 0;
        for(int i = 0; i < nam ; i++){
            if(i%2==0 & chars[i] == 'L'){
               flag = 1;
            }else if(i%2!=0 & chars[i] == 'R'){
                flag1 = 1;
            }
        }
        if(flag1 == 0 && flag == 0){
            System.out.println("Yes");
        }else{
            System.out.println("No");
        }
	}
}


Measured memory_bytes: 21844
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n, c, k, arr[100005], range, capacity=0, count=0;
    cin >> n >> c >> k;
    for(int i=1; i<=n; i++){
        cin >> arr[i];
    }
    sort(arr+1, arr+n+1);
    range=arr[1]+k;
    capacity++;
    count++;
    for(int i=2;i<=n;i++){
        if(arr[i]<=range && capacity<c) {
            capacity++;
        }
        else{
            range=arr[i]+k;
            capacity=1;
            count++;
        }
    }
    cout <<count;
    return 0;
}

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



int main(){
	string s;
	cin>>s;
	
	for(int i=0;i<s.size();i++){
		if(i!=0){
			if(s[i]==s[i-1]){
				cout<<i<<' '<<i+1<<endl;
				return 0;
			}
		}
		if(i>=2){
			if(s[i]==s[i-2]){
				cout<<i-1<<' '<<i+1<<endl;
				return 0;
			}
		}
	}
	cout<<"-1 -1"<<endl;
	
	
	return 0;
}

Measured memory_bytes: 512
#include <iostream> // cout, endl, cin
#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 <iomanip>
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#include <math.h>
#include <stdlib.h>
#include <stdio.h>
using namespace std;
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
const int INF = 1001001000;
const int MOD = 1000000007;

typedef pair<int, int> P;
int myAbs(int num) {
    if (num > 0)
        return num;
    else
        return -num;
}

long long gcd(long long a, long long b) {
    if (b == 0) return a;
    else return gcd(b, a % b);
}
long long lcm(long long a, long long b) {
    return a * b / gcd(a, b);
}

using Graph = vector<vector<int>>;
//再帰とかグラフを使うときは予めNの最大値のグローバル配列を取っておく
int N;
bool E[101][101];
vector<bool> seen;
typedef pair<int, int> P;
int D[101];
//頂点状態を表すcolor[]において、0は未訪問、1は訪問中、2は完了を表す。
int color[101];
int find_time = 0;

int main() {
    int N; cin >> N;
    vector<int> retu(N);
    for (int i = 0; i < N; i++) {
        cin >> retu.at(i);
    }
    vector<long long> kind(N+1,0);
    vector<long long> rui(N + 1, 0);
    long long R = 0;
    for (int i = 0; i < N; i++) {
        kind.at(retu.at(i))++;
    }
    for (int i = 1; i <= N; i++) {
        rui.at(i) = rui.at(i - 1) + kind.at(i) * (kind.at(i) - 1) / 2;
        R = R + kind.at(i) * (kind.at(i) - 1) / 2;
    }
    for (int i = 0; i < N; i++) {
        int A = retu.at(i);
        if (kind.at(A) < 3) {
            cout << R - kind.at(A) * (kind.at(A) - 1) / 2 << endl;
            continue;
        }
        cout << R - kind.at(A) * (kind.at(A) - 1) / 2 + (kind.at(A) - 1) * (kind.at(A) - 2) / 2 << endl;
    }
}


Measured memory_bytes: 7424
#include<bits/stdc++.h>
using namespace std;
#define  ll long long int
#define ld  long double
#define dd double
#define endl '\n'
#define mo 100005
#define to 1000000007 
#define  fast ios_base::sync_with_stdio(false); cin.tie(NULL);
#define tt int t; cin>>t; while(t--)
#define ff(n,m) for(int i=0;i<n;i++)for(int j=0;j<m;j++)
#define pb push_back
#define ld long double
#define li cout<<endl;
#define fr(a,e) for(int i=a;i<e;i++)

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    string s; cin>>s;
   // int n=s.length();
    int i=0,ma=0;
    while(i<3){
        int cnt=0;
        if(s[i]=='R'){
            while(i<3 && s[i]=='R'){
                i++;
                cnt++;
                ma=max(ma,cnt);
        }
        }
        else i++;

    }
    cout<<ma<<endl;
    return 0;
}

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

using namespace std;


int main(){
	
	
	int n ;
	int legs;
	cin>>n>>legs;
	
	
	for(int i=0;i<=n;i++)
	{
	 if(i*4 + (n-i)*2 == legs)
	{
		 cout << "Yes";
	     return 0;
	 }
}
		cout<<"No";
	return 0;
	}

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

int main(){
    int H, W; cin >> H >> W;
    char a[100][100];
    for(int i=0; i<H; i++){
        for(int j=0; j<W; j++){
            cin >> a[i][j];
        }
    }
    bool used_row[100], used_column[100];
    for(int i=0; i< max(H,W); i++){
        used_row[i]=false; used_column[i]=false;
    }
    for(int i=0; i<H; i++){
        for(int j=0; j<W; j++){
            if(a[i][j]=='#') {
                used_row[i]=true; used_column[j]=true;
            }
        }
    }
    vector<int> row, column;
    for(int i=0; i<H; i++){
        if(used_row[i]) row.push_back(i);
    }
    for(int i=0; i<W; i++){
        if(used_column[i]) column.push_back(i);
    }
    for(auto x : row){
        for(auto y : column){
            cout << a[x][y];
        }
        cout << endl;
    }
}

Measured memory_bytes: 256
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        float ans = 0;
        for (int i = 1; i <= N; i += 2) {
            ans++;
        }
        // 出力
        System.out.println(ans / N);
    }
}


Measured memory_bytes: 21716
import sys

N,K = map(int,input().split())
E = [[] for _ in range(N)]
MOD = 10**9+7
#辺の定義
for _ in range(N-1):
  u,v = map(int,input().split())
  u -= 1
  v -= 1
  E[u].append(v)
  E[v].append(u)

if N == 1:
	print(K)
	sys.exit()
#colorが塗られたかどうか
color = [-1 for _ in range(N)]
dp = [-1 for _ in range(N)]
#dfsで色を塗っていく
stack = []
color[u] = 1
ans = K
for i,v in enumerate(E[u]):
	stack.append(v)
	ans *= (K-i-1)
	ans %= MOD

while stack:
	u = stack.pop()
	color[u] = 1
	length = 0
	for v in E[u]:
		if color[v] == -1:
			stack.append(v)
			length += 1
	if dp[length] == -1:
		tmp = 1
		for i in range(K-1-length,K-1):
			tmp *= i
			tmp %= MOD
		#tmp = p(K-2,length) % MOD
		ans *= tmp
		dp[length] = tmp
	else:
		ans *= dp[length]
	ans %= MOD

#各頂点の色を出力
print(ans%MOD)

Measured memory_bytes: 24428
#include<bits/stdc++.h>
#define ll long long int
#define v vector
#define pub push_back
#define pob pop_back
#define puh push_heap
#define poh pop_heap
#define com(x) x.begin(),x.end()
#define fast(); ios::sync_with_stdio(0);cin.tie(0);
#define popcount __builtin_popcount
#define F first
#define S second
#define LB lower_bound
#define UB upper_bound 
#define MP make_pair
#define MH make_heap
#define NLmax(x) numeric_limits<x>::max()
#define NLmin(x) numeric_limits<x>::min()
#define bisearch(s) binary_search(s.begin(),s.end())
#define loop(i,a,b,x) for(ll i=a;i<b;i=i+x)
#define M 1000000007
using namespace std;
int main()
{
    fast();
    ll n,q;
    cin>>n>>q;
    string s;
    cin>>s;
    v<ll> arr(n,0);
    ll l,r;
    for(ll i=0;i<s.size();i++)
    {
        if(i>0 && s[i]=='C' && s[i-1]=='A') arr[i]++;
        if(i>0) arr[i]+=arr[i-1];
    }
    while(q--)
    {
        cin>>l>>r;
        r--;
        l--;
        ll ans = arr[r];
        if(l>0) ans-=arr[l-1];
        if(l>0 && arr[l]-arr[l-1]==1) ans--;
        cout<<ans<<"\n";
    }
    return 0;
}

Measured memory_bytes: 1872
import sys
import math

def gcd(x, y):
    if x < y:
        return gcd(y, x)
    if y == 0:
        return x
    return gcd(y, x % y)

sys.setrecursionlimit(1000000)
input = lambda: sys.stdin.readline().rstrip()

N, M = map(int, input().split())
a = list(map(lambda x : int(x) // 2, input().split()))
lcm = 1
for i in a:
    lcm = lcm * i // gcd(lcm, i)
ok = True
for i in a:
    if lcm // i % 2 == 0:
        ok = False

if not ok:
    print(0)
else:
    print((M // lcm - 1) // 2 + 1)

Measured memory_bytes: 64112
#include "bits/stdc++.h"
using namespace std;
#define int long long
#define double long double
#define low lower_bound
#define upp upper_bound
#define rep(i,n) for (int i = 0; i < (int)(n); i++)
#define Rep(i,n) for (int i = (int)(n); i >= 0; i--)
#define all(vec) vec.begin(),vec.end()
#define rever(vec) reverse(all(vec));
#define cend cout << endl;
#define prique(T) priority_queue<T,vector<T>,greater<T>>
struct edge { int to, cost; };
typedef pair<int, int> P;
const int mod = 1e9 + 7, inf = 1e16;

int modpow(int x, int n) {
	if (n == 0) return 1;
	if (n % 2) return (x * modpow(x * x % mod, n / 2) % mod + mod) % mod;
	return (modpow(x * x % mod, n / 2) + mod) % mod;
}

int fact(int n) {
	int ans = 1;
	rep(i, n) {
		ans *= (i + 1);
		ans %= mod;
	}
	return (ans + mod) % mod;
}

int comb(int n, int r) {
	if (n < r) swap(n, r);
	if (n - r < r) r = n - r;
	return fact(n) * modpow(fact(n - r), mod - 2) % mod * modpow(fact(r), mod - 2) % mod;
}

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

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

bool pri(int p) {
	for (int i = 2; i * i <= p; i++) if (p % i == 0) return false;
	return p > 1;
}

template <typename T>
void greater_sort(vector<T>& vec) {
	sort(all(vec), greater<T>());
	return;
}

int n,m,k;
signed main() {
	cin>>n>>m>>k;
	rep(i,n+1) {
		rep(j,m+1) {
			if(i*(m-j)+j*(n-i)==k) {
				cout<<"Yes"<<endl;
				return 0;
			}
		}
	}
	cout<<"No"<<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define rt return 0
#define endln "\n"
#define all(v) v.begin(), v.end()
#define for1(i, a, b) for (long long int i = a; i < b; i++)
#define for2(i, a, b) for (long long int i = a; i > b; i--)
//  cout << fixed << setprecision(0) << pi <<" "<<npi<<endl;typedef long long int i;
typedef long long int lli;
typedef pair<lli, lli> pll;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    lli a, b, c, k;
    cin >> a >> b >> c >> k;
    swap(a, c);
    vector<lli> v;
    while (b <= c && k)
    {
        b *= 2;
        k -= 1;
    }
    while (a <= b && k)
    {
        a *= 2;
        k -= 1;
    }
    if (a > b && b > c)
    {
        cout << "Yes" << endl;
    }
    else
    {
        cout << "No" << endl;
    }
}

Measured memory_bytes: 3624
import sys
input = sys.stdin.readline
n = int(input())
g = [[] for i in range(n)]
for i in range(n-1):
  a,b,c = map(int,input().split())
  a-=1;b-=1
  g[a].append([b,c])
  g[b].append([a,c])
q,k = map(int,input().split())
k -= 1
con = [-1] * n
con[k] = 0
stack = [k]
while stack:
  cur = stack.pop()
  for i,j in g[cur]:
    if con[i] == -1:
      con[i] = con[cur] + j
      stack.append(i)
for i in range(q):
  x,y = map(int,input().split())
  x-=1;y-=1
  print(con[x]+con[y])

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

using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define MOD 1000000007
#define INF (1LL<<25)     //33554432
#define PI 3.14159265359
#define EPS 1e-12
#define int ll

ll dp[105][15][1010];

int dfs(int n, int m, int k) {
  if(m<0||k<0) return 0;
  if(n<0) {
    if(!k&&!m) return 1;
    else return 0;
  }
  if(dp[n][m][k] != -1) return dp[n][m][k];

  return dp[n][m][k] = dfs(n-1, m, k) + dfs(n-1, m-1, k-n);
}

signed main(void)
{
  int n, s;
  fill(dp[0][0], dp[105][0], -1);
  while(cin>>n>>s, n||s) cout << dfs(100, n, s) << endl;
  return 0;
}

Measured memory_bytes: 15512
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <complex>
#include <queue>
#include <map>
#include <set>
#include <cstring>
#include <cstdlib>
#include <string>
#include <cmath>
using namespace std;

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

int main() {
  vector<string> line;
  string li;
  while(getline(cin, li), li != "END_OF_TEXT")
    line.push_back(li);
//  cin.ignore();
  char c;
  int x = 0, y = 0;
  string buf;
  while(cin >> c, c!='-') {
    switch(c) {
    case 'a':
      x=0;
      break;
    case 'e':
      x=line[y].size();
      break;
    case 'p':
      if (y)
        y--;
      x=0;
      break;
    case 'n':
      if (y<line.size()-1)
        y++;
      x=0;
      break;
    case 'f':
      if (x<line[y].size()) {
        x++;
      } else if (y<line.size()-1) {
        y++;
        x=0;
      }
      break;
    case 'b':
      if (x)
        x--;
      else if (y) {
        y--;
        x=line[y].size();
      }
      break;
    case 'd':
      if (x!=line[y].size()) {
        line[y].erase(line[y].begin()+x);
      } else if (y<line.size()-1) {
        line[y] += line[y+1];
        line.erase(line.begin()+y+1);
      }
      break;
    case 'k':
      if (x==line[y].size()) {
        if (y<line.size()-1) {
          line[y] += line[y+1];
          line.erase(line.begin()+y+1);
          buf = "\n";
        }
      } else {
        buf = line[y].substr(x);
        line[y].resize(x);
      }
      break;
    case 'y':
      if (buf=="") break;
      if (buf=="\n") {
        string tmp = line[y].substr(x);
        line[y].resize(x);
        line.insert(line.begin()+y+1,tmp);
        y++;
        x=0;
      } else {
        line[y].insert(x, buf);
        x+=buf.size();
      }
      break;
      
    }
    // cout << c <<  " "  << x << ","<<y<< endl;
    // REP(i, line.size())
    //   cout << i<< ": "<< line[i] << endl;
  }
  FOR(it, line)
    cout << *it << endl;

}

Measured memory_bytes: 0
from heapq import heappush, heappop
from itertools import permutations, accumulate, combinations
import math
import bisect
import numpy as np
from collections import defaultdict, deque
from operator import itemgetter
from bisect import bisect_left, bisect_right
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(10 ** 6)
# MOD = 10 ** 9 + 7
# INF = float("inf")


def main():
    n = int(input())
    A = sorted(list(map(int, input().split())))
    B = sorted(list(map(int, input().split())))
    C = sorted(list(map(int, input().split())))
    ans = 0
    for b in B:
        i = bisect_left(A, b)
        j = n - bisect_right(C, b)
        if i == 0 or j == 0:
            continue
        ans += i * j
    print(ans)



if __name__ == '__main__':
    main()

Measured memory_bytes: 31780
#include <iostream>
#include <stack>

using namespace std;

int main() {
	stack<int> st;
	int num;
	while(true){
		cin>>num;
		if(cin.eof()){ break; }
		else if(num == 0){
			cout<<st.top()<<endl; 
			st.pop();
		}
		else{ st.push(num); }
	}
	return 0;
}

Measured memory_bytes: 1200
#include <stdio.h>
 
int main(int argc, const char * argv[]) {

    int count[4][3][10]={0};	/* 4?£? 3??¨?±? 10????????? */
    int n, b, f, r, v, i, j, k;
    scanf("%d",&n);
    for(i=0; i<n; i++){
        scanf("%d %d %d %d", &b, &f, &r, &v);	/* 4????????´??°b f r v?????\???(b?£?f??????r???????????¨?±????v??????????????\?±?) */
        count[b-1][f-1][r-1]+=v;
    }
    for(i=0; i<4; i++){
        for(j=0; j<3; j++){
            for(k=0; k<10; k++){
                printf(" %d",count[i][j][k]);	/* ????£??????? ?????? ?????????????????\?±??????°????????? */
            }
            printf("\n");	/* ??????????¬????????????¢?????? */
        }
        if(i<3){
            printf("####################\n");	/* ????£??????????????????????20??????#???????????? */
        }
    }

return 0;
}

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

#define fi first
#define se second
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define rrep(i,n) for (int i = 1; i < (n); ++i)
#define drep(i,n) for (int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define all(x) (x).begin(), (x).end()
#define maxs(x,y) (x = max(x,y))
#define mins(x,y) (x = min(x,y))
#define pb push_back
#define sz(x) (int)(x).size()
#define PQ(T) priority_queue<T, v(T), greater<T> >

using namespace std;
typedef long long ll;
typedef unsigned uint;
typedef unsigned long long ull;
typedef pair<int,int> P;

const ll LINF = 1001002003004005006ll;
const int INF = 1001001001;

const int mod = 1000000007;

int main() {
    int N;
    cin >> N;
    bool ok = false;
    for(int i = 1; i < 10; ++i) {
        int r = N % i;
        if (r != 0) continue;
        else {
            int q = N / i;
            if (q < 10) ok = true;
        }
    }
    if (ok) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
#define For(i, st, en) for(int i=st; i<en; i++)
#define ff first
#define ss second
#define pb push_back
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pii;
typedef long long ll;

int main() {
	int n;
	cin>>n;
	vi a(n);
	For (i, 0, n) cin>>a[i];
	vector<vector<ll>> dp(n, vector<ll>(n, -1));
	vector<vector<ll>> ss(n, vector<ll>(n));
	For (i, 0, n) {
		dp[i][i] = 0;
		ss[i][i] = a[i];
	}
	For (g, 1, n) {
		for (int i = 0, j = g; j < n; i++, j++) {
			ss[i][j] = ss[i][i] + ss[i+1][j];
			For (k, i, j) {
				if (dp[i][j] == -1) dp[i][j] = dp[i][k] + dp[k+1][j] + ss[i][k] + ss[k+1][j];
				else dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] + ss[i][k] + ss[k+1][j]);
			}
		}
	}
	cout<<dp[0][n-1]<<endl;
	return 0;
}


Measured memory_bytes: 2816
s = input()
a = int(s[:2])
p = int(s[-2:])
if 0<a<=12 and 0<p<=12:
    print('AMBIGUOUS')
elif 0<a<=12:
    print('MMYY')
elif 0<p<=12:
    print('YYMM')
else:
    print('NA')

Measured memory_bytes: 3060
N, Q = (int(x) for x in input().split())
S = input()

a_loc = [0] * (N + 1)
for i in range(N):
    a_loc[i+1] = a_loc[i] + (1 if S[i:i+2] == 'AC' else 0)

ans = [0] * Q
for i in range(Q):
    l, r = (int(x) for x in input().split())
    ans[i] = a_loc[r-1] - a_loc[l-1]
    
for i in range(Q):
    print(ans[i])

Measured memory_bytes: 11896
# -*- coding: utf-8 -*-

#整数値入力 1文字の入力
def input_one_number():
    return int(input())



a =[1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]

k = input_one_number()
print(a[k-1])




Measured memory_bytes: 2940
import java.util.*;
import java.io.*;
public class Main
{
	static final int mod=(int)1e9+7;
	static final int inf=(int)1e9;
	static final long INF=(long)1e18;
	public static void main(String[] args)
	{
		FastScanner fs=new FastScanner();
		int n=fs.nextInt();
		long arr[]=fs.longreadArray(n);
		long s=0;
		for(int i=0;i<arr.length-1;i++)
		{
			if(arr[i+1]<arr[i])
			{
				s=s+(arr[i]-arr[i+1]);
				arr[i+1]=arr[i];
			}
		}
		System.out.println(s);
	}
}
class FastScanner 
{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer("");
		public String next() 
		{
			while (!st.hasMoreTokens())
				try {
					st=new StringTokenizer(br.readLine());
				} catch (IOException e) {
					e.printStackTrace();
				}
			return st.nextToken();
			
		}
		ArrayList<Integer> sieve(int n)
		{
			ArrayList<Integer> primes = new ArrayList<Integer>();
			boolean arr[]=new boolean[n+1];
			Arrays.fill(arr,true);
			arr[0]=arr[1]=false;
			for(int i=2;i*i<=n;i++)
			{
				if(arr[i]==true)
				{
					for(int j=i*i;j<arr.length;j+=i)
					{
						arr[j]=false;
					}
				}
			}
			for(int i=0;i<arr.length;i++)
			{
				if(arr[i]==true)primes.add(i);
			}
			return primes;
		}
		long pow(long x,long n)
		{
			long res=1;
			while(n>0)
			{
			   	if(n%2!=0)
			   	{
			   		res=(res*x);n--;
			   	}
			   	else
			   	{
			   		x=(x*x);n/=2;
			   	}
			}
			return res;
		}
		int gcd(int a,int b)
		{
			if(b==0)
			{
				return a;
			}
			return gcd(b,a%b);
		}
		long longgcd(long a,long b)
		{
			if(b==0)
			{
				return a;
			}
			return longgcd(b,a%b);
		}
		int[] sort(int arr[])
		{
			ArrayList<Integer> list = new ArrayList<Integer>();
			for(int i:arr)list.add(i);
			Collections.sort(list);
			for(int i=0;i<arr.length;i++)
			{
				arr[i]=list.get(i);
			}
			return arr;
		}
		char[] charsort(char arr[])
	        {
	    	ArrayList<Character> list = new ArrayList<>();
	    	for(char c:arr)list.add(c);
	    	Collections.sort(list);
	    	for(int i=0;i<list.size();i++)
	    	{
	    		arr[i]=list.get(i);
	    	}
	    	return arr;
	        }
		long[] longsort(long arr[])
		{
			ArrayList<Long> list = new ArrayList<Long>();
			for(long i:arr)list.add(i);
			Collections.sort(list);
			for(int i=0;i<arr.length;i++)
			{
				arr[i]=list.get(i);
			}
			return arr;
		}
		public int nextInt() 
		{
			return Integer.parseInt(next());
		}
		public int[] readArray(int n)
		{
			int[] arr=new int[n];
			for (int i=0; i<n; i++) arr[i]=nextInt();
			return arr;
		}	
		public long nextLong()
		{
			return Long.parseLong(next());
		}
		public long[] longreadArray(int n) 
		{
			long[] a=new long[n];
			for (int i=0; i<n; i++) a[i]=nextLong();
			return a;
		}
}

Measured memory_bytes: 55628
#pragma GCC optimize("Ofast")
#define _USE_MATH_DEFINES
#include "bits/stdc++.h"

using namespace std;

using u8 = uint8_t;
using u16 = uint16_t;
using u32 = uint32_t;
using u64 = uint64_t;
using i8 = int8_t;
using i16 = int16_t;
using i32 = int32_t;
using i64 = int64_t;

constexpr char newl = '\n';
constexpr double eps = 1e-10;

#define FOR(i,a,b) for (int i = (a); i < (b); i++)
#define F0R(i,b) FOR(i,0,b)
#define RFO(i,a,b) for (int i = ((b)-1); i >=(a); i--)
#define RF0(i,b) RFO(i,0,b)
#define fi first
#define se second
#define debug(x) cout << #x << ": " << x << '\n';
#define rng(a) a.begin(),a.end()
#define rrng(a) a.rbegin(),a.rend()

template<typename T1, typename T2> inline void chmin(T1& a, T2 b) { if (a > b) a = b; }
template<typename T1, typename T2> inline void chmax(T1& a, T2 b) { if (a < b) a = b; }
template<class T> void Print(vector<T> v) {
  F0R(i, v.size()) {
    cout << v[i] << ' ';
  }
  cout << newl;
}

#if 1

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

// INSERT ABOVE HERE
signed main() {
  cin.tie(0);
  ios_base::sync_with_stdio(false);

  int N;
  cin >> N;
  vector<int> as(N), ls(N), rs(N);
  F0R(i, N) {
    cin >> as[i];
    if (!i) {
      ls[i] = as[i];
    }
    else {
      ls[i] = gcd(ls[i - 1], as[i]);
    }
  }
  RF0(i, N) {
    if (i == N - 1) {
      rs[i] = as[i];
    }
    else {
      rs[i] = gcd(rs[i + 1], as[i]);
    }
  }
  int result = 0;
  F0R(i, N) {
    if (!i) {
      chmax(result, rs[1]);
    }
    else if (i == N - 1) {
      chmax(result, ls[N - 2]);
    }
    else {
      chmax(result, gcd(ls[i - 1], rs[i + 1]));
    }
  }
  cout << result;
}
#endif


Measured memory_bytes: 4360
N = int(input())
S = input()
SS = list(S)
SSS = []
if N%2 != 0:
    print("No")
else:
    for i in range(int(N/2)):
        SSS.append(SS[i])
    SSS = "".join(SSS)
    SSS += SSS
    if SSS == S:
        print("Yes")
    else:
        print("No")


Measured memory_bytes: 2940
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<map>
#include<set>
#include<string>

#define fast_io ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

using namespace std;

//inline int read(){int t = 0;int neg=1;char c;while((c=getchar_unlocked())!='\n'&&c!=' '&&c!=EOF){if(c=='-'){neg=-1;continue;}t=t*10+c-48;}return neg*t;}
//inline int readl(){long long t = 0;long long neg=1ll;char c;while((c=getchar_unlocked())!='\n'&&c!=' '&&c!=EOF){if(c=='-'){neg=-1ll;continue;}t=t*10+c-48;}return neg*t;}

#define debug(x) cout<<(#x)<<"="<<(x)<<", ";
#define debug1(x) debug(x) cout<<'\n';
#define debug2(x1, x2) debug(x1) debug(x2) cout<<'\n';
#define debug3(x1, x2, x3) debug(x1) debug(x2) debug(x3) cout<<'\n';
#define debug4(x1, x2, x3, x4) debug(x1) debug(x2) debug(x3) debug(x4) cout<<'\n';
#define debug5(x1, x2, x3, x4, x5) debug(x1) debug(x2) debug(x3) debug(x4) debug(x5) cout<<'\n';

typedef long long int lli;
typedef unsigned long long int ulli;
typedef pair<int,int> pi;
typedef pair<lli,lli> plli;
typedef vector<int> vi;
typedef vector<lli> vlli;
typedef vector<pi> vpi;
typedef vector<plli> vplli;
const lli M=1000000007ll;

int main(){
	fast_io
	string s; cin>>s;
	for(int i=0; i<s.size(); ++i){
	if(s[i]=='7'){
		cout<<"Yes";
		return 0;
	}
	
	} 
	cout<<"No";
	return 0;
}

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


int main() {
    string s;
    int a;
    string ans = "";
    cin >> s;
    a = (int)(s.length());
    rep(i, a) {
        ans.append("x");
    }
    cout << ans;
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
const int N=1e5+10;
int xx[N],yy[N];
int d[N],n,m,x,y,cnt,a;
int fa[N];
int find_f(int x){return x==fa[x]?x:find_f(fa[x]);
}
int main(){
//	freopen("a.in","r",stdin);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		scanf("%d%d",&xx[i],&yy[i]);d[xx[i]]++;d[yy[i]]++;
	}
	for(int i=1;i<=n;i++)if(d[i]&1){puts("No");return 0;}
	for(int i=1;i<=n;i++) if(d[i]>=6){puts("Yes");return 0;}
	for(int i=1;i<=n;i++)if(d[i]==4){cnt++;a=i;}
	if(cnt>=3) {puts("Yes");return 0;}
	if(cnt<2){puts("No");return 0;}
	cnt=0;for(int i=1;i<=n;i++)fa[i]=i;
	for(int i=1;i<=m;i++){
		x=xx[i];y=yy[i];if(x==a||y==a)continue;x=find_f(x);y=find_f(y);
		if(x!=y)fa[x]=y;
	}
	for(int i=1;i<=n;i++)cnt+=find_f(i)==i;
	if(cnt>=3)puts("Yes");else puts("No");
}

Measured memory_bytes: 1792
n, d = map(int, input().split())
x = [list(map(int, input().split())) for _ in range(n)]

ans = 0
for i in range(n-1):
  for j in range(i+1, n):
    sm = 0
    for k in range(d):
      sm += (x[i][k] - x[j][k])**2
    if sm == round(sm**0.5)**2:
      ans += 1
      
print(ans)

Measured memory_bytes: 3188
#include <iostream>

using namespace std;
int main()
{
    int n;
    cin>>n;
    n = n%1000;
    if(n==0)
    {
        printf("0\n");
        return  0;
    }
    n = 1000 - n;
    cout<<n<<endl;
    return 0;
}


Measured memory_bytes: 3620
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define mod 1000000009
#define pb push_back
#define endl '\n'
#define tez_chal ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
const ll INF = 1e9+7;
int solve()
{
 
  ll n; cin>>n;
  vector<ll>dp(3,0);
  cin>>dp[0]>>dp[1]>>dp[2];
  for(ll day=1;day<n;day++){
  	vector<ll>new_dp(3,0);
  	vector<ll>points(3);
  	for(auto &p:points) cin>>p;
  	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]+points[j]);
  			}
  		}
  	}
  	dp=new_dp;
  }
  cout<<max({dp[0],dp[1],dp[2]})<<endl;



return 0;
}


 








int main()
{  
    tez_chal;     ll t=1;  //cin>>t;
    
    while(t--) solve();

    // ll testcase=1;
    // while(t--){
    // 	cout<<"Case #"<<testcase++<<": ";
    // 	solve();
    // }

    return 0;
}




Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define F first
#define S second
#define all(x) x.begin(),x.end()
//#define maxi 1e18
#define pll pair<ll,ll>
#define inf 1000000007
#define mod 998244353
map<ll,ll> m;
int main(){
   ll n,i;
   cin>>n;
   pair<ll,ll> p[n];
   for(i=0;i<n;i++){
        cin>>p[i].F;
        p[i].S=i;
   }
   sort(p,p+n);
   for(i=0;i<n;i++){
    cout<<p[i].S+1<<" ";
   }
    /*for(i=0;i<n+3;i++){
        cout<<v[i]<<endl;
    }
    ll n,i;
    cin>>n;
    ll a[n];
    vector<vector<ll> > v(2);
    for(i=0;i<n;i++){
        cin>>a[i];
        ll r=sqrt(a[i]);
        if(a[i]!=r*r){
            if(a[i]-r*r<(r+1)*(r+1)-a[i]){
                v[0].pb(a[i]-r*r);
            }
            else v[0].pb((r+1)*(r+1)-a[i]);
        }
        else if(a[i]==0){
            v[2].pb(0);
        }
        else {
            v[1].pb(0);
        }
    }
    ll sum=0,cnt=0;
    sort(all(v[0]));
    sort(all(v[1]));
    for(i=0;i<v[0].size();i++){
        sum+=v[0][i];
    }
   // cout<<v[0].size()<<endl;
    for(i=1ll*v[0].size()-1;i>=0;i--){
           // cout<<"HI"<<endl;
        if(cnt<n/2){sum-=v[0][i];cnt++;}
        else break;
    }
    ll diff=(n/2)-cnt;
    while(diff>0){
        for(i=v[1].size()-1;i>=0;i--){
            if(diff>0){
                diff--;
                sum++;
            }
            else break;
        }
    }
    cout<<sum<<endl;
   /*
    ll n,don=0;
    cin>>n;
    ll i,z=0;
    ll a[n];
    ll sum=0;
    vector<ll> ans;
    for(i=0;i<n;i++){
        cin>>a[i];
        sum+=a[i];
        if(a[i]==0){
            z=1;
        }
    }
    sort(a,a+n);
    if(!z){
        cout<<-1;
        return 0;
    }
   ll  nz=0;
    if(sum%3==0){
        for(i=0;i<n;i++){
            ans.pb(a[i]);
            if(a[i]!=0)nz=1;
        }
        if(!nz){
            ans.clear();ans.pb(0);
        }
    }
    else if(sum%3==1){
        for(i=0;i<n;i++){
            if(!don&&a[i]%3==1){
                don=1;
            }
            else ans.pb(a[i]);
        }
         if(!don){
                ans.clear();
                don=-1;
            for(i=0;i<n;i++){
                if(don<1&&a[i]%3==2){
                    don++;
                }
                else ans.pb(a[i]);
            }
        }
        if(don<1){
            cout<<-1;
            return 0;
        }
    }
    else{
        for(i=0;i<n;i++){
            if(a[i]%3==2)don=1;
            else ans.pb(a[i]);
        }
        if(!don){
                ans.clear();
                don=-1;
            for(i=0;i<n;i++){
                if(don<1&&a[i]%3==1){
                    don++;
                }
                else ans.pb(a[i]);
            }
        }
        if(don<1){
            cout<<-1;
            return 0;
        }
    }
    reverse(all(ans));
    for(i=0;i<ans.size();i++){
        cout<<ans[i];
    }*/
}


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

int main(void) {
	int a = 0, i, n;
	string r, s;
	cin >> s >> n;
	for(i=0 ; cin >> r, i<n ; i++) if(string(r+r).find(s) != -1) a++;
	cout << a << endl;
}

Measured memory_bytes: 1212
#include <iostream>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <algorithm>
#include <set>
#include <map>
#include <bitset>
#include <cmath>
#include <functional>
#define vv(a, b, c, d) vector<vector<d> >(a, vector<d>(b, c))
#define vvi vector<vector<int> >
#define vvl vector<vector<ll> >
#define vll vector<ll>
typedef long long int ll;
typedef long double ld;
using namespace std;

int main(int argc, char const *argv[]) {
  int n, b;std::cin >> n;
  int MAX = 30;
  vector<int> a(n),s(MAX+1, 1);
  vvi amari = vv(MAX, n, 0, int);
  for(int i=1;i<MAX+1;i++) s[i] = s[i-1] * 2;
  for(int i=0;i<n;i++) scanf("%d", &a[i]);
  for(int i=0;i<n;i++){
    scanf("%d", &b);
    for(int j=0;j<MAX;j++) amari[j][i] = (b%s[j+1]);
  }
  for(int i=0;i<MAX;i++) sort(amari[i].begin(), amari[i].end());
  vector<ll> xo(MAX, 0);
  for(int i=0;i<n;i++){
    int t = 0;
    for(int j=0;j<MAX;j++){
      t += s[j] * ((a[i]&(1<<j))!=0?1:0);
      if((a[i]&(1<<j))==0){
        ll out = (1<<(j+1)) - t;
        ll ok = max(0, (1<<j)-t);
        ll r = lower_bound(amari[j].begin(), amari[j].end(), out) - amari[j].begin();
        ll l = lower_bound(amari[j].begin(), amari[j].end(), ok) - amari[j].begin();
        xo[j] += r - l;
      }else{
        int out_1 = (1<<(j+1)) - t;
        int ok_1  = 0;
        int out_2 = 4*(1<<j) - t;
        int ok_2 = 3*(1<<j) - t;
        int r = lower_bound(amari[j].begin(), amari[j].end(), out_1) - amari[j].begin();
        int l = lower_bound(amari[j].begin(), amari[j].end(), ok_1) - amari[j].begin();
        int r2 = lower_bound(amari[j].begin(), amari[j].end(), out_2) - amari[j].begin();
        int l2 = lower_bound(amari[j].begin(), amari[j].end(), ok_2) - amari[j].begin();
        xo[j] += r - l + r2 - l2;
      }
    }
  }
  ll ans = 0;
  for(int i=0;i<MAX;i++) ans += s[i] * (xo[i]%2);
  std::cout << ans << '\n';
  return 0;
}


Measured memory_bytes: 26608
program different_distribution
  implicit none
  integer :: n, a, b, ma, mb, i
  ma = 0
  mb = 0
  read(*,*) n
  do i = 1, n
    read(*,*) a, b
    if (ma.lt.a) then
      ma = a
      mb = b
    end if
  end do
  write(*,'(i0)') ma+mb
  stop
end program different_distribution

Measured memory_bytes: 768
using System;

namespace AtCoder
{
    class Program
    {
        static int GetDayOfWeek(string s)
        {
            switch (s)
            {
                case "SUN":
                    return 0;
                case "MON":
                    return 1;
                case "TUE":
                    return 2;
                case "WED":
                    return 3;
                case "THU":
                    return 4;
                case "FRI":
                    return 5;
                case "SAT":
                    return 6;
                default:
                    throw new Exception();
            }
        }

        static void Main(string[] args)
        {
            string s = Console.ReadLine();

            int dayOfWeek = GetDayOfWeek(s);
            int ans = 7 - dayOfWeek;
            Console.WriteLine(ans);
        }
    }
}

Measured memory_bytes: 11104
n = int(input())
keta = len(str(n))
if keta==1 or keta==2:
  print(min(n, 9))
elif keta==3 or keta==4:
  print(min(n-90, 909))
elif keta==5 or keta==6:
  print(min(n-9090, 90909))

Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
int n,k,val[100005],l[100005],r[100005];
vector<int> g[100005];
void die()
{
	cout<<"No"<<endl;
	exit(0);
}
void solve(int v,int p)
{
	l[v]=-1e9-1;
	r[v]=1e9+1;
	if(val[v]!=-1) l[v]=r[v]=val[v];
	for(int i=0;i<g[v].size();i++)
	{
		int to=g[v][i];
		if(to==p) continue;
		solve(to,v);
		if(l[to]<-1e8) continue;
		if(l[v]<-1e8)
		{
			l[v]=l[to]-1;
			r[v]=r[to]+1;
		}
		else
		{
			if(abs(l[to])%2==abs(l[v])%2)
				die();
			l[v]=max(l[v],l[to]-1);
			r[v]=min(r[v],r[to]+1);
		}
	}
	if(l[v]>r[v]) die();
}
void make(int v,int p)
{
	for(int i=0;i<g[v].size();i++)
	{
		int to=g[v][i];
		if(to==p) continue;
		if(val[to]==-1)
		{
			if(l[to]<=val[v]-1&&val[v]-1<=r[to]) val[to]=val[v]-1;
			else val[to]=val[v]+1;
		}
		make(to,v);
	}
}
int main()
{
	cin>>n;
	for(int i=1;i<=n-1;i++)
	{
		int a,b;
		cin>>a>>b;
		g[a].push_back(b);
		g[b].push_back(a);
	}
	memset(val,-1,sizeof(val));
	cin>>k;
	for(int i=1;i<=k;i++)
	{
		int v,p;
		cin>>v>>p;
		val[v]=p;
	}
	solve(1,-1);
	cout<<"Yes"<<endl;
	val[1]=l[1];
	make(1,-1);
	for(int i=1;i<=n;i++)
		cout<<val[i]<<endl;
	return 0;
}


Measured memory_bytes: 15360
#include <bits/stdc++.h>
using namespace std::literals::string_literals;
using i64 = long long;
using std::cout;
using std::endl;
using std::cin;

template<typename T>
std::vector<T> make_v(size_t a){return std::vector<T>(a);}

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

int main() {
	int n; scanf("%d", &n);
	std::vector<std::vector<int>> g(n);
	for(int i = 0; i < n - 1; i++) {
		int a, b; scanf("%d%d", &a, &b);

		g[a - 1].push_back(b - 1);
		g[b - 1].push_back(a - 1);
	}

	std::vector<double> dp(n);
	std::vector<std::vector<std::pair<double, int>>> d(n);
	auto dfs = [&](auto&& dfs, int v, int par) -> void {
		int deg = g[v].size() - (par != -1);
		for(auto e: g[v]) {
			if(e == par) continue;
			dfs(dfs, e, v);
			dp[v] += (dp[e] + 1) / deg;
			d[v].push_back({dp[e], e});
		}
	};
	dfs(dfs, 0, -1);
	
	std::vector<double> t(n), ans(n);
	auto solve = [&](auto&& solve, int v, int par) -> void {
		double sum = 0;
		for(auto e: d[v]) sum += e.first;
		for(auto e: d[v]) t[e.second] = e.first;

		for(auto e: g[v]) {
			if(e == par) continue;
			int deg = g[e].size() - (g[e].size() != 1);
			double tmp = (sum - t[e]) / (g[v].size() - (g[v].size() != 1)) + 1;
			if(g[v].size() == 1) tmp = 0;

			ans[e] += (tmp + 1) / g[e].size();
			ans[v] += (dp[e] + 1) / g[v].size();
			d[e].push_back({tmp, v});
			solve(solve, e, v);
		}
	};
	solve(solve, 0, -1);

	for(auto v: ans) printf("%.12lf\n", v);
	return 0;
}


Measured memory_bytes: 30336
import java.util.*;
import java.math.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		// 整数の入力
		int n = sc.nextInt();
		int m = sc.nextInt();
		int maxLeft = 0;
		int minRight = n;

		for (int i = 0; i < m; i++) {
			int l = sc.nextInt();
			int r = sc.nextInt();

			maxLeft = Math.max(l, maxLeft);
			minRight = Math.min(r, minRight);
		}

		if (minRight < maxLeft) {
			System.out.println(0);
		} else {
			System.out.println(minRight - maxLeft + 1);
		}
	}
}


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

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

    char b, c[128];
    c['A'] = 'T';
    c['T'] = 'A';
    c['C'] = 'G';
    c['G'] = 'C';

    cin >> b;
    cout << c[b] << endl;
}

Measured memory_bytes: 256
N,K=map(int,input().strip().split())
A=list(map(int,input().strip().split()))

l=[1]
x=1
cnt=[0 for n in range(N)]
cnt[0]=1
for n in range(N):
    y=A[x-1]
    l.append(y)
    cnt[y-1]+=1
    x=y
    if cnt[y-1]==2:
        value=y
        temp=n
        break

for m in range(len(l)):
    if l[m]==value:
        bias=m
        mul=temp-bias+1
        break
    
if bias>K:
    print(l[K])
else:
    print(l[bias+(K-bias)%mul])

Measured memory_bytes: 32260
#include<iostream>
#include<fstream>
#include<string>
#include<algorithm>
#include<cmath>
#include<vector>
#include<stack>
#include<climits>
#include<cstring>
#include<queue>
using namespace std;

const int MAX_N = 300000;
typedef unsigned long long ull;
typedef long long ll;
const ull mod = 1000000000 + 7;
#define REP(i,n) for(int i=0;i<(int)n;++i)

int main(){
    ll N, T;
    cin >> N >> T;
    vector<ll> ts(N);
    REP(i, N) cin >> ts[i];

    ll res = 0;
    REP(i, N-1){
        res += min(ts[i+1]-ts[i], T);
    }
    res += T;
    cout << res << endl;
    return 0;
}

Measured memory_bytes: 1792
#include <cstdio>
#include <cmath>
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <map>
#include <queue>
#include <algorithm>
 
#ifdef _DEBUG
#define DMP(x) cerr << #x << ": " << x << "\n"
#else
#define DMP(x) ((void)0)
#endif
 
const int MOD = 1000000007, INF = 1111111111; 
using namespace std;
typedef long long lint;
 
lint mypow(lint a, lint n) {
	lint res = 1;
	while (n > 0) {
		if (n & 1) res = res * a;
		a *= a;
		n >>= 1;
	}
	return res;
}
 
int main() {
 
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
    
    string S;
    int K;
    cin >> S >> K;
  
    for(int i = 0; i <= (int)S.length(); i++){
        
        if(K != 1 && S[i] == '1') K--;
        else {
        	cout << S[i] << "\n";
            break;
        }
    }
 
	return 0;
}

Measured memory_bytes: 256
from collections import deque
n = int(input())
G = []
for _ in range(n):
    tmp = list(map(int, input().split()))
    u = tmp.pop(0)
    k = tmp.pop(0)
    t = []
    for i in range(k):
        a = tmp.pop(0)
        t.append(a-1)
    G.append(t)
    
dist = [-1]*n
dist[0] = 0
que = deque()
que.append(0)

while que:
    v = que.popleft()
    for nv in G[v]:
        if dist[nv] != -1:
            continue
        dist[nv] = dist[v] + 1
        que.append(nv)
    
for i in range(n):
    print(i+1, dist[i])


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

int main(){
  int cou=0,ans=0,j,i,o;
  char joi[1111111];
  string tmp;
  scanf("%s",joi);
  tmp = joi;
  int len = tmp.size();
  while(len > cou){
    if(joi[cou] != 'J'){
      cou++;
      continue;
    }
    j=0,o=0,i=0;
    while(joi[cou] == 'J' && len > cou){
      cou++;
      j++;
    }
    while(joi[cou] == 'O' && len > cou){
      cou++;
      o++;
    }
    while(joi[cou] == 'I' && len > cou){
      cou++;
      i++;
    }
    if(j >= o && o <= i && ans < o){
      ans =  o;
    }
  }
  cout << ans << endl;
}

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

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(v) v.begin(), v.end()
using llint = long long;
using vint = vector<int>;


int sum_of_digit (int x) {
    llint sum = 0;
    while (x > 0) {
        sum += x % 10;
        x /= 10;
    }
    return sum;
}

int main () {
    int n, x; cin >> n;
    x = sum_of_digit(n);
    if (n % x == 0) cout << "Yes\n";
    else cout << "No\n";
}

Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <limits>
#include <numeric>
#include <string>
#include <type_traits>

#define rep(i, x, n) for(int i = x; i < n; i++)
using namespace std;
const long long INF = 1LL << 60;
int N;
long long A[100010];
long long dp[100010][2];
int GCD(long long x, long long y) { return x ? GCD(y % x, x) : y; }
int main() {
    int N;
    cin >> N;
    string S[10010];
    rep(i, 0, N) { cin >> S[i]; }
    int A = 0, B = 0, kihon = 0;
    int arisuu = 0;
    rep(i, 0, N) {
        int size = S[i].size();
        int ari = false;
        if(S[i][0] == 'B') {
            B++;
            ari = true;
        }
        if(S[i][size - 1] == 'A') {
            A++;
            ari = true;
        }
        if(ari) {
            arisuu++;
        }
        int flg = 0;
        rep(r, 0, size) {

            if(S[i][r] == 'A') {
                flg = 1;
            } else if(flg == 1 && S[i][r] == 'B') {
                kihon++;
                flg = 0;
            } else {
                flg = 0;
            }
        }
    }
    int res = kihon + min({A, B});
    if(arisuu > 0 && A == arisuu && B == arisuu) {
        res--;
    }
    cout << res << endl;
}

Measured memory_bytes: 768
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <vector>
#include <string>
#include <queue>
#include <deque>
#include <list>
#include <stack>
#include <set>
#include <map>
#include <algorithm>

#define int long long
#define MOD7 1000000007
#define MOD9 1000000009

#define rep(i, n) for (int i = 0; i < (n); i++)
#define REP(i, a, n) for (int i = (a); i <= (n); i++)
#define all(a) (a).begin(), (a).end()

using namespace std;

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

int nextInt() {int a; cin >> a; return a;}
char nextChar() {char a; cin >> a; return a;}
double nextDouble() {double a; cin >> a; return a;}
string nextString() {string a; cin >> a; return a;}

template<class T> void inputVector(vector<T>& v, int n) {
    v.resize(n);
    for (int i = 0; i < v.size(); i++) cin >> v[i];
}

map<int, int> m;

signed main() {
	int N, K;
	cin >> N >> K;

	rep(i, N) {
		int a, b;
		cin >> a >> b;

		m[a] += b;
	}

	for (auto it = m.begin(); it != m.end(); it++) {
		K -= (*it).second;
		if (K <= 0) {
			cout << (*it).first << endl;
			break;
		}
	}

    return 0;
}


Measured memory_bytes: 4224