akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
#define rep(i,x,y) for (int i=(x); i<=(y); i++)
#define ll long long
#define ld long double
#define inf 1000000000
using namespace std;
ll read(){
	char ch=getchar(); ll x=0; int op=1;
	for (; !isdigit(ch); ch=getchar()) if (ch=='-') op=-1;
	for (; isdigit(ch); ch=getchar()) x=(x<<1)+(x<<3)+ch-'0';
	return x*op;
}
#define N 200005
#define lc (o<<1)
#define rc (o<<1|1)
int n,a[N],tr[2][N<<1];
int Min(int x,int y){ return a[x]<a[y]?x:y; }
void up(int typ,int o){ tr[typ][o]=Min(tr[typ][lc],tr[typ][rc]); }
void build(int typ,int o,int l,int r){
	if (l==r){ tr[typ][o]=2*l-typ; return; }
	int mid=l+r>>1;
	build(typ,lc,l,mid); build(typ,rc,mid+1,r);
	up(typ,o);
}
int qry(int typ,int o,int l,int r,int x,int y){
	if (x<=l && r<=y) return tr[typ][o];
	int mid=l+r>>1,ret=0;
	if (x<=mid) ret=Min(ret,qry(typ,lc,l,mid,x,y));
	if (y>mid) ret=Min(ret,qry(typ,rc,mid+1,r,x,y));
	return ret;
}
struct node{
	int l,r,x,y,tg; node(){}
	node(int l_,int r_,int tg_){
		l=l_,r=r_,tg=tg_;
		if (l+1==r) x=l,y=r;
		else{
			if (!tg) x=qry(tg^1,1,1,n/2,(l+1)/2,r/2),y=qry(tg,1,1,n/2,(x+1)/2,r/2);
			else x=qry(tg^1,1,1,n/2,(l+1)/2,r/2),y=qry(tg,1,1,n/2,(x+2)/2,(r+1)/2);
		}
	}
	bool operator < (const node &t) const{ return a[x]>a[t.x]; }
};
priority_queue<node> q;
void ins(int x,int y,int tg){ if (x<y) q.push(node(x,y,tg)); }
int main(){
	n=read();
	rep (i,1,n) a[i]=read(); a[0]=inf;
	build(1,1,1,n/2); build(0,1,1,n/2);
	q.push(node(1,n,0));
	rep (step,1,n/2){
		node tmp=q.top(); q.pop();
		printf("%d %d ",a[tmp.x],a[tmp.y]);
		ins(tmp.l,tmp.x-1,tmp.tg);
		ins(tmp.x+1,tmp.y-1,tmp.tg^1);
		ins(tmp.y+1,tmp.r,tmp.tg);
	}
	return 0;
}

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

int main() {
  ll n,ans=0; cin>>n;
  vector<ll> a(5);
  for(int i=0; i<n; i++) {
    string s; cin>>s;
    if(s[0]=='M') a[0]++;
    if(s[0]=='A') a[1]++;
    if(s[0]=='R') a[2]++;
    if(s[0]=='C') a[3]++;
    if(s[0]=='H') a[4]++;
  }
  ans += a[0]*a[1]*a[2];
  ans += a[0]*a[1]*a[3];
  ans += a[0]*a[1]*a[4];
  ans += a[0]*a[2]*a[3];
  ans += a[0]*a[2]*a[4];
  ans += a[0]*a[3]*a[4];
  ans += a[1]*a[2]*a[3];
  ans += a[1]*a[2]*a[4];
  ans += a[1]*a[3]*a[4];
  ans += a[2]*a[3]*a[4];
  cout<<ans;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
#define V vector<long long>
#define VV vector<vector<long long>>
#define rep(i,n) for(ll (i)=0;(i)<(n);++(i))
using namespace std;

template<typename T>
struct lowest_common_ancestor{
    T n,logn;
    vector<T> depth;
    vector<vector<T>> g,next;
    lowest_common_ancestor(vector<vector<T>> const& g):g(g),n(g.size()),logn(floor(log2(g.size()))),depth(g.size()){
        next.assign(n,vector<T>(logn+1));
        dfs(0,-1,0);
        for(T k=0;k<logn;++k){
            for(T i=0;i<n;++i){
                if(next[i][k]==-1)next[i][k+1]=-1;
                else next[i][k+1]=next[next[i][k]][k];
            }
        }
    }
    void dfs(T now,T par,T dep){
        depth[now]=dep;
        next[now][0]=par;
        for(T i=0;i<g[now].size();++i){
            if(g[now][i]!=par){
                dfs(g[now][i],now,dep+1);
            }
        }
    }
    T query(T a,T b){
        if(depth[a]<depth[b])swap(a,b);
            for(T k=logn;k>=0;--k){
                if((1<<k) & depth[a]-depth[b]){
                    a=next[a][k];
                }
            }
        if(a==b)return a;
            for(T k=logn;k>=0;--k){
                if(next[a][k] != next[b][k]){
                    a=next[a][k];
                    b=next[b][k];
                }
            }
        return next[a][0];
    }
    T distance(T a,T b){
        return depth[a]+depth[b]-2*depth[query(a,b)];
    }
};

int main(){
    ll n;
    cin>>n;
    VV g(n,vector<ll>());
    rep(i,n){
        ll k;
        cin>>k;
        rep(j,k){
            ll c;
            cin>>c;
            g[i].push_back(c);
            g[c].push_back(i);
        }
    }
    lowest_common_ancestor<ll> lca(g);
    ll q;
    cin>>q;
    rep(i,q){
        ll u,v;
        cin>>u>>v;
        cout<<lca.query(u, v)<<endl;
    }
}



Measured memory_bytes: 34736
#include <iostream>
#include <cstring>
#include <cstdio>
#define ll long long
using namespace std;

inline int read(){
	int sum=0,f=1;char c=getchar();
	while(c>'9'||c<'0'){if(c=='-') f=-1;c=getchar();}
	while(c<='9'&&c>='0'){sum=sum*10+c-'0';c=getchar();}
	return f*sum;
}

const int N=3005;
const int Mod=1000000007;
int n,m;
ll f[N][N][2];

signed main(){
	n=read();m=read();
	for(int i=1;i<=n;i++) f[0][i][0]=1;
	f[0][0][1]=1;
	for(int i=0;i<m;i++){
		for(int j=0;j<=n;j++){
			if(j){
				//黑白
				if(j==1) f[i+1][j][1]=(f[i+1][j][1]+f[i][j][0])%Mod;
				if(j>1)	f[i+1][j][0]=(f[i+1][j][0]+f[i][j][0])%Mod;
				f[i+1][j][1]=(f[i+1][j][1]+f[i][j][1])%Mod;				
				//黑黑
				if(j==1) f[i+1][j-1][1]=(f[i+1][j-1][1]+f[i][j][0])%Mod;				
				if(j>1) f[i+1][j-1][0]=(f[i+1][j-1][0]+f[i][j][0])%Mod;
				f[i+1][j-1][1]=(f[i+1][j-1][1]+f[i][j][1])%Mod;
			}
			if(j<n){
				//白黑
				f[i+1][j][0]=(f[i+1][j][0]+f[i][j][0])%Mod;
				f[i+1][j][1]=(f[i+1][j][1]+f[i][j][1])%Mod;
				//白白
				f[i+1][j+1][0]=(f[i+1][j+1][0]+f[i][j][0])%Mod;
				f[i+1][j+1][1]=(f[i+1][j+1][1]+f[i][j][1])%Mod;				
			}
	   }
	}
	ll ans=0;
	for(int i=0;i<=n;i++) ans=(ans+f[m][i][1])%Mod;
	printf("%lld\n",ans);	
	return 0;
}


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

vector<pair<long long, long long> > prime_factorize(long long N) {
    vector<pair<long long, long long> > res;
    for (long long a = 2; a * a <= N; ++a) {
        if (N % a != 0) continue;
        long long ex = 0; // 指数

        // 割れる限り割り続ける
        while (N % a == 0) {
            ++ex;
            N /= a;
        }

        // その結果を push
        res.push_back({a, ex});
    }

    // 最後に残った数について
    if (N != 1) res.push_back({N, 1});
    return res;
}

int main() {
	int n;
	cin >> n;
	vector<pair<long long, long long>> ans = prime_factorize(n);
	cout << n << ": ";
	for (int i=0;i<ans.size();i++) {
		for (int j=0;j<ans[i].second;j++) {
			cout << ans[i].first;
			if (!(i == ans.size()-1 && j == ans[i].second-1)) {
				cout << " ";
			} else {
				cout << endl;
			}
		}
	}
}


Measured memory_bytes: 3108
#include<bits/stdc++.h>
using namespace std;
int i,j,k,s,x;
int main()
{
  for(cin>>k>>s;i<=k;i++){
    for(j=0;j<=k;j++){
      if(s-i-j>=0&&s-j-i<=k)x++;
    }
  }
  cout<<x;
}

Measured memory_bytes: 256
#include <cstdio>

using namespace std;

int n, init_p;
int s[51];

int main() {
  while (true) {
    scanf("%d %d", &n, &init_p);
    if (n == 0 && init_p == 0) break;
    for (int i=0;i<n;i++) s[i] = 0;
    int p = init_p, curr = 0;
    while (true) {
      if (p == 0) {
        p += s[curr];
        s[curr] = 0;
      } else {
        s[curr]++;
        p--;
        if (s[curr] == init_p) break;
      }
      curr = (++curr)%n;
    }
    printf("%d\n", curr);
  }
  return 0;
}

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

using namespace std;

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


int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    string s;
    getline(cin, s);
    for (int i = 0; i < s.size(); ++i) {
        int l1 = s[i] - 'A';
        int l2 = s[i] - 'a';
        if (l1<26 && l1>=0) { cout<<(char)(l1 + 97); }
        else if (l2<26 && l2>=0) { cout<<(char)(l2 + 65); }
        else { cout<<s[i]; }
    }
    cout<<"\n";
    return 0;
}



Measured memory_bytes: 3260
#!/usr/bin/perl
( my $s = <STDIN> ) =~ s/[\x00-\x20]+$//ios;
( my $t = <STDIN> ) =~ s/[\x00-\x20]+$//ios;
my $res = 'Yes';
my %st =();
my %ts =();
for(my $i=0;$i<length($s);$i++){
  my $s1 = substr($s,$i,1);
  my $t1 = substr($t,$i,1);
  my $o = $ts{$t1};
  if( $o ne '' and $o ne $s1 ){
    $res = 'No';
    last;
  }
  $ts{$t1} = $s1;
  $o = $st{$s1};
  if( $o ne '' and $o ne $t1 ){
    $res = 'No';
    last;
  }
  $st{$s1} = $t1;
}
print "$res\n";
exit(0);


Measured memory_bytes: 972
import java.util.Scanner;
public class Main {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int x = scan.nextInt();
		
		if(x >= 30) {
			System.out.println("Yes");
		}else {
			System.out.println("No");
		}

	}

}


Measured memory_bytes: 35824
q, h, s, d = map(int, input().split())
n = int(input())

q *= 4
h *= 2
d_ = d / 2

tmp = min(q, h, s)
ans = 0
if d_ < tmp:
    ans += d * (n // 2)
    ans += tmp * (n % 2)
else:
    ans += n * tmp

print(ans)

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


typedef long long ll;
typedef pair<int,int> P;
typedef vector<int> VI;

#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=int(a);i<int(b);++i)
#define all(x) (x).begin(),(x).end()
const int MOD1e97=1e9+7;

template< int mod >
struct ModInt {
  int x;

  ModInt() : x(0) {}

  ModInt(int64_t y) : x(y >= 0 ? y % mod : (mod - (-y) % mod)) {}

  ModInt &operator+=(const ModInt &p) {
    x = (x + p.x) % mod;
    return *this;
  }

  ModInt &operator-=(const ModInt &p) {
    x = (x + mod - p.x) % mod;
    return *this;
  }

  ModInt &operator*=(const ModInt &p) {
    x = static_cast<long long>(1LL * x * p.x % mod);
    return *this;
  }

  ModInt &operator/=(const ModInt &p) {
    *this *= p.inverse();
    return *this;
  }

  ModInt operator-() const { return ModInt(-x); }

  ModInt operator+(const ModInt &p) const { return ModInt(*this) += p; }

  ModInt operator-(const ModInt &p) const { return ModInt(*this) -= p; }

  ModInt operator*(const ModInt &p) const { return ModInt(*this) *= p; }

  ModInt operator/(const ModInt &p) const { return ModInt(*this) /= p; }

  bool operator==(const ModInt &p) const { return x == p.x; }

  bool operator!=(const ModInt &p) const { return !(*this == p); }

  ModInt inverse() const {
    int a = x, b = mod, u = 1, v = 0, t;
    while(b > 0) {
      t = a / b;
      a -= t * b;
      swap(a, b);
      u -= t * v;
      swap(u, v);
    }
    return ModInt(u);
  }

  ModInt pow(int64_t n) const {
    ModInt ret(1), mul(x);
    while(n > 0) {
      if(n & 1) ret *= mul;
      mul *= mul;
      n >>= 1;
    }
    return ret;
  }

  friend ostream &operator<<(ostream &os, const ModInt &p) {
    return os << p.x;
  }

  friend istream &operator>>(istream &is, ModInt &a) {
    int64_t t;
    is >> t;
    a = ModInt< mod >(t);
    return (is);
  }

  constexpr static int get_mod() { return mod; }
};

using modint = ModInt< MOD1e97 >;

int main() {
  string s;
  cin >> s;
  vector< vector<modint> > dp(s.size(), vector<modint>(2, 0));
  // cout << s << endl;
  dp[0][0] = 1;
  dp[0][1] = 2;

  repi(i, 1, s.size()) {
    if(s[i] == '0') {
      dp[i][0] = dp[i-1][0] * 3;
      dp[i][1] = dp[i-1][1];
    }
    else {
      dp[i][0] = dp[i-1][0]*3 + dp[i-1][1];
      dp[i][1] = dp[i-1][1] * 2;
    }
  }

  cout << dp[dp.size() - 1][0] + dp[dp.size() - 1][1] << endl;
}


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

int main(){
    vector<int> vec(3);
    cin>>vec.at(0)>>vec.at(1)>>vec.at(2);
    sort(vec.begin(), vec.end());
    if (vec.at(0)==5&&vec.at(1)==5&&vec.at(2)==7){
        cout<<"YES"<<endl;
    }else{
        cout<<"NO"<<endl;
    }
}


Measured memory_bytes: 256
#ifdef LOCAL
#define _GLIBCXX_DEBUG
#endif
#include <bits/stdc++.h>
using namespace std;

const int mod = 998244353;

int pd[310][310][310];
int pd2[310][310][310];
int cnt[2][310];
string s;
int n;

int rec(int pos, int av0, int av1) {
    if (av0+av1 == 0) return 1;
    
    int &ret = pd2[pos][av0][av1];
    if (ret == -1) {
        ret = 0;

        if (pos != n && s[pos] == '0') {
            ret = (ret + rec(pos+1, av0, av1)) % mod;
        }
        else if (av0) {
            ret = (ret + rec(pos, av0-1, av1)) % mod;
        }

        if (pos != n && s[pos] == '1') {
            ret = (ret + rec(pos+1, av0, av1)) % mod;
        }
        else if (av1) {
            ret = (ret + rec(pos, av0, av1-1)) % mod;
        }
    }

    // cout << pos << " " << av0 << " " << av1 << " -> " << ret << endl;
    return ret;
}


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

    cin >> s;
    n = s.size();

    memset(pd2,-1,sizeof(pd2));

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < 2; j++) cnt[j][i+1] = cnt[j][i];
        cnt[s[i]-'0'][i+1]++;
    }

    pd[0][0][0] = 1;
    for (int pos = 0; pos < n; pos++) {
        for (int del0 = 0; del0 <= cnt[0][n]; del0++) {
            for (int del1 = 0; del1 <= cnt[1][n]; del1++) if (pd[pos][del0][del1]) {

                if (pos+2 <= n) {
                    // delete first value
                    int nd0 = del0, nd1 = del1;
                    if (s[pos] == '0') nd0++;
                    if (s[pos] == '1') nd1++;

                    pd[pos+2][nd0][nd1]=1;

                    // delete second value
                    nd0 = del0; nd1 = del1;
                    if (s[pos+1] == '0') nd0++;
                    if (s[pos+1] == '1') nd1++;
                    pd[pos+2][nd0][nd1]=1;
                }

                // delete extras
                int av0 = cnt[0][pos] - del0, av1 = cnt[1][pos] - del1;
                
                if (av0) pd[pos+1][del0+1][del1]=1;
                if (av1) pd[pos+1][del0][del1+1]=1;

                
                // delete values using extras
                int nd0 = del0, nd1 = del1;
                if (s[pos] == '0') nd0++;
                if (s[pos] == '1') nd1++;
                if (av0 || av1) pd[pos+1][nd0][nd1]=1;
            }
        }
    }

    int ans = 0;
    for (int del0 = 0; del0 <= cnt[0][n]; del0++) {
        for (int del1 = 0; del1 <= cnt[1][n]; del1++) {
            // if (del0 != 1 || del1 != 1) continue;
            for (int pos = n; pos >= 0; pos--) if (pd[pos][del0][del1]) {
                // cout << "for del0 = " << del0 << " , del1 = " << del1 << ", pos = " << pos << " ";
                int av0 = cnt[0][pos] - del0, av1 = cnt[1][pos] - del1;
                ans = (ans + rec(pos, av0, av1)) % mod;
                // cout << " -> ret = " << rec(pos,av0,av1) << endl;
                break;
            }
        }
    }

    cout << ans << endl;
}

Measured memory_bytes: 148260
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define all(v) v.begin(), v.end()
typedef long long ll;
typedef pair<ll,ll> P;
typedef vector<ll> vec;
typedef vector<vec> mat;
int main(){
    ll n,A[200001],SUM=0;
    cin>>n;
    rep(i,n) cin>>A[i],SUM+=A[i];
    ll ans=1e18,sum=0;
    rep(i,n-1) sum+=A[i],ans=min(ans,abs(SUM-sum-sum));
    cout<<ans<<"\n";
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
int main(){
  string s;
  int n;
  cin>>n>>s;
  for(int i=0;i<s.size();i++){
  s[i]+=n;
  if(s[i]>'Z')s[i]=s[i]-'Z'+'A'-1;
  }
  cout<<s;
  return 0;
}


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


/* macro */
#define rep(i,a,b) for(int i=a;i<b;i++)
#define revrep(i,a,b) for(int i = a; i > b; i--)
#define int long long
#define exist(s,e) ((s).find(e)!=(s).end())
#define all(v) (v).begin(), (v).end()
#define each(s,itr) for(auto (itr) = s.begin(); (itr) != s.end(); (itr)++)
#define sum(v) accumulate(all(v), (0LL))
#define pb push_back


/* alias */
template<class T> using vec = vector<T>;
typedef vector<int> vi;
typedef pair<int, int> pi;


/* constant */
const int inf = pow(2, 62);
const int mod = 1e9 + 7;
int dx[8]={1,0,-1,0,-1,1,-1,1};
int dy[8]={0,1,0,-1,-1,-1,1,1};
const string alpha = "abcdefghijklmnopqrstuvwxyz";

/* io_method */
int input(){int tmp;cin >> tmp;return tmp;}
string raw_input(){string tmp;cin >> tmp;return tmp;}
string readline(){string s;getline(cin, s);return s;}
template<class T> void printx(T n){cout << n;}
template<class T, class U> void printx(pair<T, U> p){cout << "(" << p.first << "," << p.second << ")";}
template<class T> void printx(vector<T> v){cout << "{";rep(i,0,v.size()){printx(v[i]);if(i != v.size()-1)printx(",");}cout << "}";}
template<class T> void print(T n){printx(n);cout << endl;}
template<class T> void print(set<T> s){cout << "{";each(s, e){if(e != s.begin()) printx(",");printx(*e);}cout << "}" << endl;}
template<class T, class U> void print(map<T, U> mp){cout << "{";each(mp, e){cout << "(" << e -> first << "," << e -> second << ")";}cout << "}" << endl;}


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




/* main */



signed main(){

    cin.tie(0);
    ios::sync_with_stdio(false);

    int n = input();
    int k = input();
    vi arr; rep(i,0,n) arr.push_back(input());

    sort(all(arr));



    int ans = inf;

    rep(i,0,n - k + 1){
        chmin(ans, arr[i + k - 1] - arr[i]);
    }

    print(ans);


    

}

Measured memory_bytes: 1400
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vs = vector<string>;
using msi = map<string, int>;
using mii = map<int, int>;
using psi = pair<string, int>;
using pii = pair<int, int>;
using vlai = valarray<int>;
#define rep(i,n) for(int i=0;i<n;i++)
#define range(i,s,n) for(int i=s;i<n;i++)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define fs first
#define sc second
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define INF 1E9
#define EPS 1E-9
#define MOD (1E9+7)
#define PI 3.1415926535897932384

std::ostream &operator<<(std::ostream &out, const vector<int> &tgt)
{
	string s;
	for (int i = 0; i<tgt.size(); i++) {
		s += (to_string(tgt[i]) + ((i != tgt.size() - 1) ? " " : ""));
	}
	out << s;
	return out;
}

int main() {
	char a, b;
	cin >> a >> b;
	bool c = (a == 'H'), d = (b == 'H');
	cout << (!c^d ? "H" : "D") << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int M=2010;
int n;
ll dp[M][M],ans;
struct elem{
    ll val,pos;
    bool operator<(elem tmp)
    {return val>tmp.val;}
}a[M];
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%lld",&a[i].val),a[i].pos=i;
    sort(a+1,a+n+1);
    for(int i=1;i<=n;i++)
        for(int L=0,R=n-i+2;R<=n+1;L++,R++)
        {
            dp[L+1][R]=max(dp[L+1][R],dp[L][R]+abs(L+1-a[i].pos)*a[i].val);
            dp[L][R-1]=max(dp[L][R-1],dp[L][R]+abs(R-1-a[i].pos)*a[i].val);
            //printf("%d %d %d %d\n",L,R,dp[L+1][R],dp[L][R-1]);
        }
    for(int i=1;i<n;i++)
        ans=max(dp[i][i+1],ans);
   // for(int i=0;i<=n+1;i++)
   // {
   //     for(int j=0;j<=n+1;j++)
   //         printf("%lld ",dp[i][j]);
   //     puts("");
   // }
    printf("%lld\n",ans);
    return 0;
}


Measured memory_bytes: 26464
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define INF 1LL<<62
#define inf 1000000007

vector<vector<ll>> a(200010);
ll c[200010];
bool ch[200010];
void dep(ll now,ll nowc){
	c[now]=nowc;
	if(a[now].size()==0){
		return;
	}
	for(int i=0;i<a[now].size();i++){
		ll next=a[now][i];
		dep(next,nowc+c[next]);
	}
}
int main() {
	ll n,q;
	cin>>n>>q;
	for(int i=0;i<n-1;i++){
		ll x,y;
		cin>>x>>y;
		x--;y--;
		a[x].push_back(y);
	}
	for(int i=0;i<q;i++){
		ll x,y;
		cin>>x>>y;
		x--;
		c[x]+=y;
	}
	dep(0,c[0]);
	for(int i=0;i<n;i++){
		cout <<c[i]<< " ";
	}
	return 0;
}

Measured memory_bytes: 21120
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define ll long long int
#define ld long double
#define pii 3.14
#define mod (ll)(1e9 + 7)
#define inf (ll)(1e18)
#define fio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define ordered_set tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update>
#define pi pair<int,int>
#define N (ll)(5e5+5)

void solve()
{
    ll n;
    cin>>n;

    ll arr[n];
    bool z = 0;
    for(int i=0;i<n;i++)
    {
        cin>>arr[i];
        if(arr[i] == 0)
            z = 1;
    }

    if(z)
    {
        cout<<"0\n";
        return;
    }

    ll ans = arr[0];
    for(int i=1;i<n;i++)
    {
        if(arr[i] <= inf/ans)
            ans *= arr[i];
        else
        {
            cout<<"-1\n";
            return;
        }
    }

    cout<<ans<<"\n";
}

int main()
{
    fio;
    ll tc = 1;
    //cin>>tc;
    while(tc--)
    {
        solve();
    }
}


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

#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define FOR(i,n,m) for(int i=(int)(n); i<=(int)(m); i++)
#define RFOR(i,n,m) for(int i=(int)(n); i>=(int)(m); i--)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define RITR(x,c) for(__typeof(c.rbegin()) x=c.rbegin();x!=c.rend();x++)
#define setp(n) fixed << setprecision(n)

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

#define ll long long
#define vll vector<ll>
#define vi vector<int>
#define pll pair<ll,ll>
#define pi pair<int,int>

#define all(a) (a.begin()),(a.end())
#define rall(a) (a.rbegin()),(a.rend())
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define ins insert

using namespace std;

//-------------------------------------------------
//--Binary Indexed Tree (Sum only)
//-------------------------------------------------
template<typename T>
class BIT
{
private:
    const int n;
    ::std::vector<T> data;
public:
    BIT(int n):n(n),data(n+1){
        for(int i=1; i<=n; i++) data[i] = 0;
    }
    BIT(const ::std::vector<T> &v):n(v.size()),data(v.size()+1){
        for(int i=1; i<=n; i++) data[i] = v[i-1];
        for(int i=1; i<n; i++)
            data[i+(i&-i)] += data[i];
    }
    void add(int k, T x){k++;
        for(int i=k; i<=n; i+=i&-i) data[i] += x;
    }
    T query(int k){
        T ret=0;
        for(int i=k; i>0; i-=i&-i) ret += data[i];
        return ret;
    }
    T query(int a, int b){return query(b)-query(a);}
    void update(int k, T x){
        T upd = x-query(k, k+1);
        add(k, upd);
    }
    T operator[](int k){return query(k, k+1);}
};

const int C_MAX = 5e5;
vi vec[C_MAX];
int idxs[C_MAX];

struct P{
    int l,r,i;
    bool operator<(const P &a){return l<a.l;};
};


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

int main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N,Q; cin>>N>>Q;
    vi c(N);
    rep(i,N) cin>>c[i];
    rep(i,N) c[i]--;
    vector<P> qs(Q);
    rep(i,Q){
        int l,r; cin>>l>>r;
        qs[i] = {l-1,r,i};
    }
    sort(all(qs));

    BIT<int> bit(N);
    rep(i,N) vec[c[i]].pb(i);
    rep(i,C_MAX){
        if (vec[i].empty()) continue;
        bit.add(vec[i][idxs[i]],1);
    }
    vi ans(Q);
    int j=0;
    rep(i,N){
        while(j<Q && qs[j].l==i){
            ans[qs[j].i] = bit.query(qs[j].r);
            j++;
        }
        bit.add(vec[c[i]][idxs[c[i]]],-1);
        idxs[c[i]]++;
        if (idxs[c[i]] < vec[c[i]].size())
            bit.add(vec[c[i]][idxs[c[i]]],1);
    }
    rep(i,Q) cout<<ans[i]<<endl;
    return 0;
}


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

int main() {
    int h, m, s;
    int S;
    cin >> S;
    h = S / 3600;
    m = S % 3600 / 60;
    s = S % 3600 % 60;
    cout << h << ":" << m << ":" << s << endl;
}


Measured memory_bytes: 3136
parseInt(x) = parse(Int, x)
parseMap(x::Array{SubString{String},1}) = map(parseInt, x)
function bsearch(a,x);l,r=1,length(a);while l<=r;m=l+div(r-l,2);if a[m]<x;l=m+1;else;r=m-1;end;end;return(l-1);end

function main()
	h,w =readline() |> split |> parseMap
	s = ["" for i in 1:h]
	for i in 1:h
		s[i] = readline() |> chomp
	end
	a = [Int[0] for i in 1:h]
	b = [Int[0] for i in 1:w]
	for i in 1:h
		for j in 1:w
			if s[i][j] == '#'
				push!(a[i],j)
				push!(b[j],i)
			end
		end
	end
	for i in 1:h
		push!(a[i],w+1)
	end
	for i in 1:w
		push!(b[i],h+1)
	end
	k = 0
	for i in 1:h
		for j in 1:w
			t = bsearch(a[i],j+1)
			u = bsearch(b[j],i+1)
			if a[t]!=i && b[t]!=u
				k = max(k,a[i][t+1]-a[i][t]+b[j][u+1]-b[j][u]-2)
			end
		end
	end
	println(k-1)
end

main()

Measured memory_bytes: 204476
#include "bits/stdc++.h"
#define in std::cin
#define out std::cout
#define rep(i,N) for(LL i=0;i<N;++i)
typedef long long int LL;

int main()
{
	LL N, Q;
	in >> N;
	std::vector<LL>a(N);
	rep(i, N) in >> a[i];
	in >> Q;
	std::vector<LL>x(Q), y(Q);
	rep(i, Q) in >> x[i] >> y[i];

	LL cnt = 0;
	auto b = a;
	std::sort(b.begin(), b.end());
	rep(i, N)
	{
		if (a[i] != b[i]) ++cnt;
	}

	if (cnt == 0)
	{
		out << 0 << std::endl;
		return 0;
	}
	rep(i, Q)
	{
		LL t = 0;
		if (a[x[i] - 1] == b[x[i] - 1]) ++t;
		if (a[x[i] - 1] == b[y[i] - 1]) --t;
		if (a[y[i] - 1] == b[y[i] - 1]) ++t;
		if (a[y[i] - 1] == b[x[i] - 1]) --t;
		cnt += t;
		if (cnt == 0)
		{
			out << i + 1 << std::endl;
			return 0;
		}
		std::swap(a[x[i] - 1], a[y[i] - 1]);
	}
	out << -1 << std::endl;
}



Measured memory_bytes: 12372
import sys
input = lambda: sys.stdin.readline().rstrip()

def main():
    n, k = map(int, input().split())
    ans = 0
    for i in range(1, n+1):
        x = 0
        while i < k:
            x += 1
            i *= 2
        ans += (1 / n) * (1 / 2)**x
    print(ans)
    
if __name__ == '__main__':
    main()

Measured memory_bytes: 9332
#include<stdio.h>
#include<stdlib.h>
int sort(int *a,int *b){
return *b-*a;
}
int main(void){
  int n;
  scanf("%d",&n);
  int l[n];
  for(int i=0;i<n;i++){
	scanf("%d",&l[i]);
  }
  int ans=0;
  qsort(l,n,sizeof(int),sort);
  for(int i=0;i<n-2;i++){
	for(int j=i+1;j<n-1;j++){
      for(int k=j+1;k<n;k++){
        if(l[i]!=l[j]&&l[i]!=l[k]&&l[j]!=l[k])
          if(l[i]<l[j]+l[k])ans++;
        }
    }
  }
  printf("%d",ans);
  return 0;
}

Measured memory_bytes: 1704
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <complex>
#include <string>
#include <sstream>
#include <algorithm>
#include <numeric>
#include <vector>
#include <queue>
#include <stack>
#include <functional>
#include <iostream>
#include <map>
#include <set>
using namespace std;
typedef pair<int,int> P;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-9
#define INF 2000000000
#define sz(x) ((int)(x).size())
#define fi first
#define sec second
#define SORT(x) sort((x).begin(),(x).end())
#define all(x) (x).begin(),(x).end()
#define EQ(a,b) (abs((a)-(b))<eps)
int a[27];
int main()
{
	a['q'-'a']=1;
	a['w'-'a']=1;
	a['e'-'a']=1;
	a['r'-'a']=1;
	a['t'-'a']=1;
	a['a'-'a']=1;
	a['s'-'a']=1;
	a['d'-'a']=1;
	a['f'-'a']=1;
	a['g'-'a']=1;
	a['z'-'a']=1;
	a['x'-'a']=1;
	a['c'-'a']=1;
	a['v'-'a']=1;
	a['b'-'a']=1;
	string s;
	while(1)
	{
		cin >> s;
		if(s=="#")break;
		int ans=0;
		for(int i=1;i<s.size();i++)
		{
			if(a[s[i]-'a']!=a[s[i-1]-'a'])ans++;
		}
		cout << ans << endl;
	}
	return 0;
}

Measured memory_bytes: 1184
#include <algorithm>
#include <cassert>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
using namespace std;
typedef long long ll;

#define rep(i, n) for(ll i = 0; i < n; i++)
#define REP(i, n) for(ll i = 1; i < n + 1; i++)
#define PI 3.14159265359
#define EPS 0.0000000001
#define MOD 1000000007
//cout << std::fixed << std::setprecision(15) << y << endl;


int main(){
    ll a, b, c;
    cin >> a >> b >> c;

    if(a + b == c || b + c == a || c + a == b){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }

    return 0;
}

Measured memory_bytes: 3624
#include <bits/stdc++.h>
#define DAU  ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define PLEC exit(0);
using namespace std;
int a, b, c, k;
int main() {
    DAU
    cin >> a >> b >> c >> k;
    while (b <= a)
        b *= 2, --k;
    while (c <= b)
        c *= 2, --k;
    if (k >= 0)
        cout << "Yes";
    else cout << "No";
    PLEC

}


Measured memory_bytes: 3632
import itertools
n = int(input())
l = [list(map(int,input().split())) for _ in range(n)]

def factorization(n):
    if n == 1:
        return 1
    return n * factorization(n-1)

size = factorization(n)
a = list(itertools.permutations(l,n))
total = 0
for i in range(size):
    for j in range(n-1):
        x1 = a[i][j][0]
        x2 = a[i][j+1][0]
        y1 = a[i][j][1]
        y2 = a[i][j+1][1]
        x_total = (x1-x2)**2
        y_total = (y1-y2)**2
        total += (x_total + y_total)**.5
print(total/size)

Measured memory_bytes: 13748
#include <bits/stdc++.h>
using namespace std;
int main()
{
 long long n,i,j,s=0,c=0,k,w,a,b;
 cin>>w>>a>>b;
 i=max(a,b);
 j=min(a,b);
 if((i-j-w)<=0) cout<<"0"<<endl;
 else cout<<i-j-w<<endl;
return 0;
}


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

int main() {
    int N, K;  cin >> N >> K;
    vector<int> p(N);
    for (int i = 0; i < N; ++i) cin >> p[i];
    sort(p.begin(), p.end());
    int ans = 0;
    for (int i = 0; i < K; ++i) ans += p[i];
    cout << ans << endl;
}


Measured memory_bytes: 3628
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define INF (1LL<<50)
#define MOD 1000000007

int N,M,Q;
vector<int> a,b,c,d;
vector<int> A;
ll ans=0;
void DFS(vector<int>&V){
    if(V.size()==N+1){
        ll tmp=0;
        rep(i,Q){
            if(V[b[i]]-V[a[i]]==c[i]){
                tmp+=d[i];
            }
        }
        ans = max(ans,tmp);
        return;
    }else{
        int tail = V.back();
        for(int nv=tail;nv<=M;nv++){
            V.push_back(nv);
            DFS(V);
            V.pop_back();
        }
    }
}

int main(){
    cin >> N >> M >> Q;
    a.assign(Q,0);
    b.assign(Q,0);
    c.assign(Q,0);
    d.assign(Q,0);
    rep(i,Q){
        cin >> a[i] >> b[i] >> c[i] >> d[i];
    }
    vector<int> V(1,1);
    DFS(V);
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3644
#include <iostream>
#include <queue>
#include <map>
#include <set>

using namespace std;

int len;
string str;

bool check(string s){
  char ch = s[0];

  for(int i = 1 ; i < len ; i++){
    if(ch != s[i]) return false;
  }
  return true;
}

int bfs(){
  string ans;
  queue<string> Q;
  Q.push(str);

  bool found = false;
  set<string> used;
  used.insert(str);
  map<string,int> dist;
  dist[str] = 0;

  while(!Q.empty()){
    string s = Q.front(); Q.pop();
    
    if(check(s)){
      found = true;
      ans = s;
      break;
    }

    for(int i = 1 ; i < len ; i++){
      string next = s;
      if(s[i-1] == 'b' && s[i] == 'r' ||
	 s[i-1] == 'r' && s[i] == 'b'){
	next[i-1] = next[i] = 'g';
      }else if(s[i-1] == 'b' && s[i] == 'g' ||
	       s[i-1] == 'g' && s[i] == 'b'){
	next[i-1] = next[i] = 'r';
      }else if(s[i-1] == 'r' && s[i] == 'g' ||
	       s[i-1] == 'g' && s[i] == 'r'){
	next[i-1] = next[i] = 'b';
      }
      
      if(!used.count(next)){
	dist[next] = dist[s] + 1;
	used.insert(next);
	Q.push(next);
      }
    }
  }

  if(!found) return -1;
  return dist[ans];
}

int main(){
  while(cin >> str,str != "0"){
    len = (int)str.size();
    int res = bfs();
    if(res == -1){
      cout << "NA" << endl;
    }else{
      cout << res << endl;
    }
  }
  return 0;
}

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

using namespace std;

using ll = long long;

ll powll(ll b, int e) {
    ll result = 1;
    while (e) {
        if (e & 1) {
            result *= b;
        }
        b *= b;
        e >>= 1;
    }
    return result;
}

bool is_palindrome(const string &s) {
    int N = s.size();
    int i = 0;
    int j = N - 1;
    while (i < j) {
        if (s[i++] != s[j--]) {
            return false;
        }
    }
    return true;
}

ll count_palindromes(string s, bool is_inner) {

    int L = s.size();

    if (L == 0) {
        return 1;
    }

    if (L == 1) {
        int n = stoi(s);
        if (is_inner) {
            return n + 1;
        } else {
            return n;
        }
    }

    string t = s.substr(1, L - 2);
    int a = stoi(s.substr(0, 1));
    int b = stoi(s.substr(L - 1, 1));

    ll result = 0;

    if (!is_inner) {
        for (int k = 1; k < L; ++k) {
            result += 9 * powll(10, (k - 1) / 2);
        }
    }

    if (is_inner) {
        result += a * powll(10, (L - 1) / 2);
    } else {
        result += (a - 1) * powll(10, (L - 1) / 2);
    }

    if (is_inner || a > 0) {
        result += count_palindromes(t, true);
        if (a > b) {
             if (is_palindrome(t)) {
                --result;
            }
        }
    }

    return result;
}

ll count_palindromes(ll n) {
    if (n) {
        return count_palindromes(to_string(n), false);
    } else {
        return 0;
    }
}

int main() {

    cin.tie(0);
    ios::sync_with_stdio(false);

    int A, B;
    cin >> A >> B;

    int result = count_palindromes(B) - count_palindromes(A - 1);
    cout << result << endl;

    return 0;
}

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

using namespace std;

#define pb push_back
#define mk make_pair
#define mod 1000000007
#define ff first
#define ss second

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

ll modpow(ll a, ll b){

    ll ans=1;
    while(b){
        if(b&1){
            ans=(ans*a)%mod;
        }
        a=(a*a)%mod;
        b=b/2;
    }
    return ans;
}

int main(){

    cin.tie(0);
    ios::sync_with_stdio(false);

    int n,q;
    string s;
    cin>>n>>s>>q;

    set<int> ind[26];

    for(int i = 0; i < n; i++) {
        ind[s[i]-'a'].insert(i + 1);
    }

    while(q--) {
        int type;
        cin>>type;

        if(type == 1) {
            int idx;
            char c;
            cin>>idx>>c;

            ind[s[idx - 1] - 'a'].erase(idx);
            s[idx - 1] = c;
            ind[s[idx - 1] - 'a'].insert(idx);
        } else {
            int a, b;
            cin>>a>>b;

            int cnt = 0;
            for(int i = 0; i < 26; i++) {
                auto it = ind[i].lower_bound(a);
                if(it == ind[i].end()) continue;
                if(*it <= b) cnt++;
            }

            cout<<cnt<<endl;
        }
    }

}


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

int main() {
  
  int N;
  cin >> N;
  
  double sum = 0;
  vector<double> x(N);
  vector<string> u(N);
  for (int i = 0; i < N; i++){
    cin >> x.at(i) >> u.at(i);
  }
  


  for (int i = 0; i < N; i++){
    if(u.at(i) == "JPY"){
      sum += x.at(i);
    } else {
      sum += x.at(i)*380000.0;
    }
  }
  
  cout << sum << endl;
    
  
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

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

    while (scanner.hasNext()) {
      long a = scanner.nextLong();
      long b = scanner.nextLong();

      long gcd = gcd(a, b);
      long lcm = (a * b) / gcd;

      System.out.println(gcd + " " + lcm);
    }
  }

  static long gcd(long n, long m) {
    // 剰余を求めて rに入れる
    long r = n % m;
    // nがmの倍数になっているなら最大公約数は m自身になる．
    if (r == 0) {
      return m;
    }
    // n,mの最大公約数は m,rの最大公約数と等しい
    else {
      return gcd(m, r);
    }
  }
}



Measured memory_bytes: 26228
#include <ext/pb_ds/assoc_container.hpp>
#include <bits/stdc++.h>
using namespace std;
using namespace __gnu_pbds;
template <class c, class cmp = less<c> > using ordered_set = tree<c, null_type, cmp, rb_tree_tag, tree_order_statistics_node_update>;
#define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define TRACE
#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
  cerr << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
  const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...) 
#endif
template<class T> ostream& operator<<(ostream &os, vector<T> V) {os << "[ "; for(auto v : V) os << v << " "; return os << "]";}
template<class L, class R> ostream& operator<<(ostream &os, pair<L,R> P) {return os << "(" << P.first << "," << P.second << ")";}
template <typename T,typename U>pair<T,U> operator+(const pair<T,U> & l,const std::pair<T,U> & r) { return {l.first+r.first,l.second+r.second};}
typedef long long int ll;
const ll mod =1e9+7;
const int maxn = 100002;
#define endl '\n'
#define int ll
#define ld long double
#define all(x) (x).begin(),(x).end()
int32_t main()
{ 
   IOS
 
  
  int n;
  cin >> n;
  int rem = 1000 - n%1000;
  if(rem == 1000){
    cout<<0<<endl;
  }
  else{
    cout<<rem<<endl;
  }
    



  




  
}

Measured memory_bytes: 3620
import sys
sys.stdin.readline
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
mod=10**9+7

def main():
    N,M,X=MI()
    A=LI()
    temp=0
    import bisect 
    num=bisect.bisect_left(A,X)
    print(min(num,M-num))
        
    


main()

Measured memory_bytes: 38256
#include<bits/stdc++.h>
#define rep(i, n) for (ll i = 0; i < (ll)(n); ++i)
#define repk(i,k,n) for (ll i = k; i < (ll)(n); ++i)
#define MAX 500000001000000000
#define MOD 1000000007
typedef long long  ll;

using namespace std;



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

	int M,N;
	cin >> N >> M;

	vector<double>A(N);
	int sum = 0;
	rep(i, N) {
		cin >> A[i];
		sum += A[i];
	}

	sort(A.begin(), A.end(),greater<int>());
	
	rep(i, M) {
		if (A[i] < ((double)1 / (4 * M)) * sum) {
			cout << "No" << endl;
			return 0;
		}
	}

	cout << "Yes" << endl;

	return 0;
}


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

#define FOR(i, a, b) for(int i=(a); i<(b); i++)
#define RFOR(i, a, b) for(int i=(a); i>=(b); i--)
#define rep(i, n) FOR(i, 0, n)
#define rrep(i, n) RFOR(i, n, 0)
#define dump(x)  cout << #x << " = " << (x) << endl;

typedef long long ll;
typedef pair<int, int> ii;
const ll INF = 1e18;
const int inf = 1e8;


void solve()
{
  ll X;
  scanf("%lld",&X);
  ll t;
  scanf("%lld",&t);
  cout << max(0ll,X-t) << endl;
}

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


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i < (n); i++)
template<class T> istream& operator >> (istream& s, vector<T>& v)
{ for (T& x: v) { s >> x; } return s;}

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

    string s, t;
    cin >> s >> t;

    int ns = s.size();
    int nt = t.size();

    vector<vector<int>> abc(26);
    rep(i, ns) abc[s[i]-'a'].push_back(i);

    ll ans_q = 0, ans_r = 0;
    rep(i, nt) {
        int ci = t[i]-'a';
        if (abc[ci].size() ==0) {
            ans_q = -1;
            break;
        }
        auto it = lower_bound(abc[ci].begin(), abc[ci].end(), ans_r);
        if (it != abc[ci].end()) {
            ans_r = *it + 1;
        } else {
            ans_q++;
            ans_r = abc[ci][0]+1;
        }
    }
    cout << (ans_q < 0 ? ans_q : ans_q * ns + ans_r) << endl;
}


Measured memory_bytes: 1228
#include "bits/stdc++.h"
#define rep(i,cc,n) for(int i=cc;i<(n);++i)
#define drep(i,cc,n) for(int i=cc;i>(n);--i)
using namespace std;
using ll = long long;

int main()
{
	int N, K, Q, count = 0;
	string S;
	cin >> N >> K;
	vector<int> d(K), B(N);
	vector<int> A(N);
	rep(i, 0, K)
	{
		cin >> d[i];
		rep(j, 0, d[i])
		{
			cin >> A[j];
			B[A[j]-1] = 1;
		}
	}
	rep(i, 0, N)
	{
		if (B[i] == 0)
			++count;
	}
	cout << count << endl;
}

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

typedef long long ll;
typedef pair<int,int> P;
int dx[] = {-1, 1, 0,  0};
int dy[] = { 0, 0, 1, -1};
 
int main(){
  int n, k; 
  cin >> n >> k;
  int ans = 1;
  ans += (n-k)/(k-1);
  if((n-k)%(k-1)!=0) ans++;
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

a,b = inpl()
if a <= 0 and b >= 0:
    print('Zero')
else:
    if a > 0:
        print('Positive')
    else:
        if (b - a) % 2 == 0:
            print('Negative')
        else:
            print('Positive')

           

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

int main(){
    int X, A, B, N;
    scanf("%d %d %d", &X, &A, &B);
    scanf("%d", &N);
    char S[N][7];

    int i=0;
    for(i=0; i<N; i++)scanf("%s", S[i]);

    for(i=0; i<N; i++){
        if(!strcmp(S[i], "nobiro"))X += A;
        else if(!strcmp(S[i], "tidime"))X += B;
        else {
            if(!strcmp(S[i], "karero"))X = 0;
        }
        if(X < 0)X = 0;
    }
    printf("%d\n", X);
    
    return 0;
}


Measured memory_bytes: 2144
N, C, K = map(int, input().rstrip().split())
TT = sorted(map(int, [input() for _ in range(N)]))
startT = TT[0]
bus_count = 1
p = 1
for T in TT[1:]:
    if T - startT > K or p >= C:
        bus_count += 1
        startT = T
        p = 1
    else:
        p += 1
print(bus_count)


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

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    def sum(self, i):
        ret = 0
        while i > 0:
            ret += self.tree[i]
            i -= i & -i
        return ret

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

bit = Bit(2000)

intra, inter = 0, 0
for i, a in enumerate(A):
    bit.add(a, 1)
    intra += i + 1 - bit.sum(a)
    inter += bit.sum(a - 1)

mod = 10**9 + 7
ans = (intra * K * (K + 1) // 2) % mod
ans += (inter * (K - 1) * K // 2) % mod
print(ans % mod)


Measured memory_bytes: 41452
#include <iostream>
#include <iomanip>
using namespace std;
int main(void){
  long long W,H,x,y;
  cin >> W >> H >> x >> y;

  double S;
  int ans;

  if(x == W / 2 && y == H / 2 && W % 2 == 0 && H % 2 == 0){
    ans = 1;
    double X = W;
    double Y = H;
    S = (X * Y) / 2.0;
  }
  else{
    ans = 0;
    double X = W;
    double Y = H;
    S = (X * Y) / 2.000000;
  }

  cout << setprecision(20) << S << " " << ans << endl;

  return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ
		Scanner sc = new Scanner(System.in);
		String s = sc.next();
		int cnt = 0;
		if(s.length()==1){
			cnt = 1;
		}
		for(int i = 0; i < s.length()-1;){
			if(i != s.length()-2){

			if(s.charAt(i)==s.charAt(i+1)){
				i += 3;
				cnt += 2;
				if(i == s.length()-1){
					cnt++;
				}
			}
			else{
				i ++;
				cnt ++;
			}

			}
			else{
				if(s.charAt(i)==s.charAt(i+1)){
					i ++;
					cnt ++;
				}
				else{
					i ++;
					cnt += 2;
				}
			}
		}

		System.out.println(cnt);
	}
}

Measured memory_bytes: 28624
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); i++)
#define sz(x) int(x.size())
using namespace std;
typedef long long ll;
const long long  mod = 1000000007;



int main(){
  int a,b;
  cin >> a >> b;

  if(a >= 13) cout << b << endl;
  else if (a>5 && a <= 12) cout << b/2 << endl;
  else cout << 0 << endl;
  

}


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

using namespace std;

#define int long long
#define all(v) (v).begin(), (v).end()
#define resz(v, ...) (v).clear(), (v).resize(__VA_ARGS__)
#define reps(i, m, n) for(int i = (int)(m); i < (int)(n); i++)
#define rep(i, n) reps(i, 0, n)

template<class T1, class T2> void chmin(T1 &a, T2 b){if(a>b)a=b;}
template<class T1, class T2> void chmax(T1 &a, T2 b){if(a<b)a=b;}

using Pi = pair<int, int>;
using Tapris = tuple<int, int, int>;
using vint = vector<int>;

const int inf = 1LL << 55;
const int mod = 1e9 + 7;

struct State {
  int l, r;
  double cost;
  State(){}
  State(int l, int r, double cost):l(l), r(r), cost(cost){}
  bool operator < (const State& rhs) const {
    return cost > rhs.cost;
  }
};

using Point = pair<double, double>;

inline double sq(double x) {
  return x*x;
}

signed main() {
  cin.tie(0);
  ios_base::sync_with_stdio(0);
  cout << fixed << setprecision(12);

  int n;
  while(cin >> n, n) {
    vector<Point> ps;
    rep(i, n) {
      double x, y;
      cin >> x >> y;
      ps.emplace_back(x, y);
    }
    rep(i, n) {
      double x = ps[i].first, y = ps[i].second;
      rep(j, n-1) {
	double x1 = ps[j].first, y1 = ps[j].second;
	double x2 = ps[j+1].first, y2 = ps[j+1].second;
	if(min(y1, y2) < y && y < max(y1, y2)) {
	  double a = (y2-y1)/(x2-x1);
	  ps.emplace_back((y-y1)/a+x1, y);
	}
      }
    }
    sort(all(ps));
    ps.erase(unique(all(ps)), ps.end());
    n = ps.size();
    //rep(i, n) cout << ps[i].first << " " << ps[i].second << endl;
    //vector<vector<double> > mincost(n, vector<double>(n, DBL_MAX/4));
    map<int, map<int, double> > mincost;
    auto dijkstra = [&]() {
      priority_queue<State> que;
      que.emplace(0, n-1, 0);
      mincost[0][n-1] = 0;
      while(!que.empty()) {
	State s = que.top(); que.pop();
	//cout<<s.l<<" "<<s.r<<" "<<ps[s.l].second<<" "<<ps[s.r].second<<" "<<s.cost<<endl;
	if(s.l == s.r)  return s.cost;
	//rep(bit, 1<<2) {
	reps(i, -1, 2) reps(j, -1, 2) {
	  int nl = s.l+i, nr = s.r+j;
	  //if((bit>>0)&1) ++nl; else --nl;
	  //if((bit>>1)&1) ++nr; else --nr;
	  if(nl < 0 || n <= nl || nr < 0 || n <= nr) continue;
	  double xl = ps[s.l].first, yl = ps[s.l].second;
	  double nxl = ps[nl].first, nyl = ps[nl].second;
	  double xr = ps[s.r].first, yr = ps[s.r].second;
	  double nxr = ps[nr].first, nyr = ps[nr].second;
	  //cout<<nl<<" "<<nr<<" "<<nyl<<" "<<nyr<<endl;
	  if(nyl != nyr) continue;
	  double ncost = s.cost + sqrt(sq(nxl-xl)+sq(nyl-yl)) + sqrt(sq(nxr-xr)+sq(nyr-yr));
	  if(!mincost[nl].count(nr) || ncost < mincost[nl][nr]) {
	    que.emplace(nl, nr, ncost);
	    mincost[nl][nr] = ncost;
	  }
	}
      }
      return -1.0;
    };
    cout << dijkstra() << endl;
  }

  return 0;
}



Measured memory_bytes: 5388
#include <iostream>
#include <algorithm>
#include <string>
#include <limits.h>
#include <vector>
#include <numeric>

using namespace std;



bool gooddis(long long int n) {

	long long int a = 0;

	while (n >= a * a) {
		if (n == a * a)return true;
		a++;
	}

	return false;
}



vector<pair<long long int, long long int>> getPrimeElements(long long int num) {

	long long int firstnum = num;

	vector<pair<long long int, long long int>> result;
	pair<long long int, long long int> wk;

	if (num % 2 == 0) {
		wk.first = 2;
		wk.second = 0;
		while (num % 2 == 0) {
			wk.second++;
			num /= 2;
		}

		result.push_back(wk);
	}

	long long int waru = 3;

	while (true) {

		if (num % waru == 0) {
			wk.first = waru;
			wk.second = 0;
			while (num % waru == 0) {
				wk.second++;
				num /= waru;
			}

			result.push_back(wk);
		}
		waru += 2;

		if (waru * waru > num) break;

	}

	if (num != 1) {
		wk.first = num;
		wk.second = 1;
		result.push_back(wk);

	}

	return result;
}


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

	vector<int> a(n);
	for (auto& i : a)cin >> i;

	int ans = 0;

	for (auto& i : a) {
		if (i % 2 != 0) {
			ans = 1;
			break;
		}
	}


	if (ans == 1) {
		cout << "first" << endl;
	}
	else {
		cout << "second" << endl;
	}

	return 0;

}




Measured memory_bytes: 640