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

#define fst(t) std::get<0>(t)
#define snd(t) std::get<1>(t)
#define thd(t) std::get<2>(t)
#define unless(p) if(!(p))
#define until(p) while(!(p))

using ll = std::int64_t;
using P = std::tuple<int,int>;

ll A, B, C, D;

ll f(ll n, ll m){
    return n / m;
}

ll g(ll m){
    return f(B, m) - f(A - 1, m);
}

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

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

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

    std::cin >> A >> B >> C >> D;

    ll res = (B + 1 - A) - (g(C) + g(D) - g(lcm(C, D)));
    std::cout << res << std::endl;
}


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

#define rep(i,s,n) for (int i = (int)s; i < (int)n; i++)
#define ll long long
#define pb push_back

int N, M;
int s, t;

const int MAX = 100005;

vector<int> adj[MAX];

ll solve() {
  vector<vector<ll>> dist(N, vector<ll>(3, -1));
  dist[s][0] = 0;
  queue<pair<int, int>> que;
  que.push({s, 0});
  while (!que.empty()) {
    // 長さが全て同じの有向グラフなのでpriority_queueを使う必要がない
    pair<int, int> cur = que.front();
    que.pop();
    int u = cur.first;
    int up = cur.second;
    rep(i, 0, adj[u].size()) {
      int v = adj[u][i];
      // 隣接するノード（つまり次の行き先候補）のparityは現在のに+1して3で割ったもの
      int vp = (up + 1) % 3;
      if (dist[v][vp] == -1) {
        dist[v][vp] = dist[u][up] + 1;
        que.push({v, vp});
      }
    }
  }

  if (dist[t][0] == -1) return -1;
  else return dist[t][0] / 3;
};


int main() {
  cin >> N >> M;
  int u, v;
  rep(i, 0, M) {
    cin >> u >> v;
    u--; v--;
    adj[u].pb(v);
  }
  cin >> s >> t;
  s--; t--;
  ll ans = solve();
  cout << ans << endl;
};


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

using namespace std;

int H, W, N;
vector<vector<char>> area;
vector<pair<int, int>> pos;		// S ~ 9 の場所

int bfs(pair<int, int> start, pair<int, int> goal) {
	const vector<int> nh = {1, 0, -1, 0};
	const vector<int> nw = {0, 1, 0, -1};

	vector<vector<int>> depth(H, vector<int>(W, 1e9));		// start からの距離。 十分大きい値に初期化する
	depth[start.first][start.second] = 0;	// start の場所の時間は 0

	queue<pair<int, int>> que;
	que.push(start);
	while (que.size()) {
		pair<int, int> now = que.front();
		que.pop();

		for (int i = 0; i < 4; ++i) {
			// 現在位置と隣接する座標(4近傍)
			int next_h = now.first + nh[i];
			int next_w = now.second + nw[i];

			if (next_h < 0 || next_w < 0 ||
				next_h >= H || next_w >= W) continue;
			if (area[next_h][next_w] == 'X') continue;			// 障害物
			if (depth[next_h][next_w] <=
				depth[now.first][now.second] + 1) continue;		// すでに訪れている = 今いる場所までの時間よりも値が小さい

			depth[next_h][next_w] = depth[now.first][now.second] + 1;		// 次の場所へかかる時間 = 今いる場所までの時間 + 1
			que.push(make_pair(next_h, next_w));
		}
	}

	return depth[goal.first][goal.second];
}

int main() {
	cin >> H >> W >> N;
	area.resize(H, vector<char>(W));
	pos.resize(N + 1);
	for (int h = 0; h < H; ++h) {
		for (int w = 0; w < W; ++w) {
			cin >> area[h][w];
			if (area[h][w] == 'S') {
				pos[0] = make_pair(h, w);
			}
			if ('1' <= area[h][w] && area[h][w] <= '9') {
				pos[area[h][w] - '0'] = make_pair(h, w);
			}
		}
	}

	int ans = 0;
	// S ~ 1 の距離、 1 ~ 2 の距離 ... の和を求めればよい
	for (int i = 0; i < N; ++i) {
		ans += bfs(pos[i], pos[i+1]);
	}

	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 7816
from sys import stdin

N = int(stdin.readline().rstrip())
S = stdin.readline().rstrip()
ans = 0

for i in range(N - 2):
    if S[i] == 'A' and S[i + 1] == 'B' and S[i + 2] == 'C':
        ans += 1

print(ans)


Measured memory_bytes: 38480
#include<bits/stdc++.h>
using namespace std;
#define all(a)  (a).begin(),(a).end()
typedef long long ll;
const ll mod=1000000007;
#define repi(i,a,b) for(int i=int(a);i<int(b);++i)

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

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

int main() {
  ll a,b;cin >>a>>b;
  cout << lcm(a,b) << endl;
  return 0;
}

Measured memory_bytes: 256
n = int(input())
hps = list(map(int, input().split()))
m = min(hps)
def gojo(a, b):
  if b == 0:
    return a
  else:
    return gojo(b, a % b)
res = m
for hp in hps:
  res = gojo(hp, res)
print(res)

Measured memory_bytes: 14224
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int fx[]={1,-1,0,0},fy[]={0,0,1,-1};
struct node{
    int x,y;
};
int n,m,ans=0;
int d[25][25];
char p[25][25];
bool vis[25][25];
queue<node> q;
int main(){
    memset(p,0x3f,sizeof(p));
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
            cin>>p[i][j];//输入
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(p[i][j]=='#') continue;//如果这个点是墙 就跳过
            memset(d,0,sizeof(d));//清空两个数组
            memset(vis,0,sizeof(vis));
            q.push((node){i,j});
            vis[i][j]=1;
            while(!q.empty()){//开始bfs 模板
                node no=q.front();
                q.pop();
                for(int k=0;k<4;k++){
                    int nx=no.x+fx[k],ny=no.y+fy[k];
                    if(nx<n&&ny<m&&nx>=0&&ny>=0&&p[nx][ny]=='.'&&!vis[nx][ny]){
                        vis[nx][ny]=1;
                        d[nx][ny]=d[no.x][no.y]+1;
                        ans=max(d[nx][ny],ans);//取最大距离作为答案 这里d每个点都会重置为0
                        q.push((node){nx,ny});
                    }
                }
            }
        }
    }
    printf("%d",ans);//输出答案即可
    return 0;
}

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

int main() {

	int x, y; cin >> x >> y;
	vector<int> c = { 0,1,3,1,2,1,2,1,1,2,1,2,1 };
	string ans;
	if (c[x] == c[y]) ans = "Yes";
	else ans = "No";
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 3616
#!/usr/bin/python3
# -*- coding:utf-8 -*-

import numpy
from collections import defaultdict

def main():
  n, m = map(int, input().split())
  db2a = defaultdict(list)
  for _ in range(m):
    a, b = map(int, input().split())
    db2a[b-1].append(a-1)
    
  cnts = numpy.zeros(n, dtype=numpy.int)
  i = 0
  for b in sorted(db2a.keys()):
    cnts[i:b] = cnts[i-1]
    cnts[b] = max(cnts[max(db2a[b])] + 1, cnts[b-1])
    i = b + 1
  cnts[i:] = cnts[i-1]
  print(cnts[-1])

if __name__=='__main__':
  main()



Measured memory_bytes: 29324
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>

using namespace std;

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

  int a;
  cin >> a;

  string rank[5];
  for (int i = 0; i < 5; i++) {
    rank[i] = "";
  }

  int cnt = 0;
  for (int i = 0; i < s.length(); i++) {
    bool flag = false;
    for (int j = 1; j <= s.length() - i; j++) {
      auto ss = s.substr(i, j);
      for (int k = 0; k < 5; k++) {
        if (ss == rank[k]) goto next;
        if (rank[k] == "" || ss < rank[k]) {
          for (int l = 4; k < l; l--) {
            rank[l] = rank[l - 1];
          }
          rank[k] = ss;
          goto next;
        }
      }
      flag = true;
    next:
      if (flag) break;
    }
  }

  cout << rank[a - 1] << endl;
}

Measured memory_bytes: 888
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
//l={1,2,3,4}
//greater<int>()
//sort(l,l+n)

int main(void)
{
	int a;
	int ans = 0;
	cin >> a;

	int hun = a / 100;
	int ten = a / 10 - hun * 10;
	int one = a % 100 - ten * 10;

	if (hun == 1)
		ans++;
	if (ten == 1)
		ans++;
	if (one == 1)
		ans++;

			
	cout << ans << endl;


	
}


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

typedef long long int ll;
typedef vector<int> vi;
typedef set<int> si;
typedef vector<ll> vll;

#define pvec(v) for(auto e: v) cout << e << " ";
#define IO ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define rep(i, a, b) for(int i = a; i<b; ++i)
#define pb push_back
#define INF 1000000000

ll pow10[200005] = {0};

// ll power(ll x, ll y, ll p = MOD)  {  
//     ll res = 1LL;
//     x = x % p;
//     if (x == 0) return 0; 
  
//     while (y > 0){         
//         if (y & 1)  
//             res = (res*x) % p;  
//         y = y>>1;
//         x = (x*x) % p;  
//     }  
//     return res;  
// } 

int solve(string s){
	int n = s.size();

	ll curr = 0LL;
	// rep(i, 0, n){
	// 	curr = (curr*10);
	// 	curr = (curr + (int)(s[i] - '0'))%2019;
	// 	cout << curr << endl;
	// }
	ll digits = 0;
	map<ll, int> freq;
	freq.insert({0, 1});
	for(int i=n-1; i>=0; --i, ++digits){
		curr = (curr + (pow10[digits]*((ll)s[i] - '0'))%2019)%2019;
		++freq[curr];
	}

	ll ans = 0;
	for(auto e: freq){
		//cout << e.first << " " << e.second << endl;
		ans+=(e.second*(e.second-1)/2);
	}

	return ans;
}

int main(){
	IO
	pow10[0] = 1;
	for(ll i = 1; i<200005; ++i){
		pow10[i] = (10*pow10[i-1])%2019;
	}

	string s;
	cin >> s;
	// reverse(s.begin(), s.end());
	cout << solve(s) << endl;
	return 0;
}

Measured memory_bytes: 5308
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <map>
#include <set>
#include <vector>
#include <stack>
#include <queue>
#include <bitset>
#include <algorithm>
#include <numeric>
#include <functional>
using namespace std;

#define Rep(b, e, i) for(int i = b; i <= e; i++)
#define Repr(e, b, i) for(int i = e; i >= b; i--)
#define rep(n, i) Rep(0, n-1, i)
#define repr(n, i) Repr(n-1, 0, i)
#define all(v) (v).begin(), (v).end()
#define pb(x) push_back(x)
#define uniq(x) (x).erase(unique(all(x)),(x).end())

typedef pair<int, int> intP;

const int MAX_N = 128;
const int MAX_W = MAX_N*MAX_N;


//dp[i][j] := i番目までで重さj以下になるように品物を選んだ時の価値の最大値
int dp[MAX_N][MAX_W];

void solve(void){
    int N, W;
    cin >> N >> W;
    vector <intP> P(N);
    rep(N, i) cin >> P.at(i).first >> P.at(i).second;
    rep(N, i) rep(W+1, j) {
        dp[i+1][j] = max(dp[i][j], dp[i+1][j]);
        if (P[i].second <= j) dp[i+1][j] = max(dp[i+1][j-P[i].second] + P[i].first, dp[i+1][j]);
    }
    cout << dp[N][W] << endl;
}

int main(void){
  solve();
  //cout << "yui(*-v・)yui" << endl;
  return 0;
}



Measured memory_bytes: 7068
#include<iostream>
#include<cassert>
#include<stdio.h>
#include<string>
#include<vector>
#include<map>
#include<tuple>
#include<algorithm>
#include<cmath>
#include<limits>
#include<set>
#include<deque>
#include<queue>
using namespace std;
#define int long  long int
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
int lcm(int a, int b) { return a / gcd(a, b) * b; }
typedef pair<int, int>P;
const int MOD = 1e9 + 7;
const int INF = 1e10;
const long double PI = (acos(-1));


signed main() {
	int N, M;
	cin >> N >> M;
	priority_queue<P>q;
	rep(i, N) {
		int A;
		cin >> A;
		q.push({ A,1 });
	}
	rep(i, M) {
		int B, C;
		cin >> B >> C;
		q.push({ C, B });
	}
	int num = 0;
	int sum = 0;
	while (1) {
		P p = q.top();
		q.pop();
		num += p.second;
		sum += p.first * p.second;
		if (num >= N) {
			sum -= (num - N) * p.first;
			cout << sum << endl;
			return 0;
		}
	}
}

Measured memory_bytes: 6384
#include <bits/stdc++.h>
#define MOD 1000000007
using namespace std;
long long int dp[21][1 << 21];
bool mat[21][21];
int posb[21];
int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> mat[i][j];
			if (mat[i][j])
				posb[i] |= 1 << (n - 1 - j);
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = 1; j < (1 << n); j++) {
			if (i == 0) {
				dp[i][j] = __builtin_popcount(posb[i] & j);
			}
			else {
				int tmpj = j;
				while (tmpj) {
					int pp = (tmpj & (-tmpj));
					tmpj ^= pp;
					if (posb[i]&pp) {
						dp[i][j] += dp[i - 1][j ^ (pp)];
						if (dp[i][j] >= MOD)
							dp[i][j] -= MOD;
					}
				}
			}
		}
	}
	cout << dp[n - 1][(1 << n) - 1];
	return 0;
}

Measured memory_bytes: 344448
// abc114d
#include <bits/stdc++.h>
#include <cassert>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define ok() puts(ok?"Yes":"No");
#define chmax(x,y) x = max(x,y)
#define chmin(x,y) x = min(x,y)
using namespace std;
using ll = long long;
using vi = vector<int>;
using vll = vector<ll>;
using ii = pair<int, int>;
using vvi = vector<vi>;
using vii = vector<ii>;
using gt = greater<int>;
using minq = priority_queue<int, vector<int>, gt>;
using P = pair<ll,ll>;
const ll LINF = 1e18L + 1;
const int INF = 1e9 + 1;
//clang++ -std=c++11 -stdlib=libc++ 
// abc114d
// Sieve of Eratosthenes
// https://youtu.be/UTVg7wzMWQc?t=2774
struct Sieve {
  int n;
  vector<int> f, primes;
  Sieve(int n=1):n(n), f(n+1) {
    f[0] = f[1] = -1;
    for (ll i = 2; i <= n; ++i) {
      if (f[i]) continue;
      primes.push_back(i);
      f[i] = i;
      for (ll j = i*i; j <= n; j += i) {
        if (!f[j]) f[j] = i;
      }
    }
  }
  bool isPrime(int x) { return f[x] == x;}
  vector<int> factorList(int x) {
    vector<int> res;
    while (x != 1) {
      res.push_back(f[x]);
      x /= f[x];
    }
    return res;
  }
  vector<ii> factor(int x) {
    vector<int> fl = factorList(x);
    if (fl.size() == 0) return {};
    vector<ii> res(1, ii(fl[0], 0));
    for (int p : fl) {
      if (res.back().first == p) {
        res.back().second++;
      } else {
        res.emplace_back(p, 1);
      }
    }
    return res;
  }
  vector<pair<ll,int>> factor(ll x) {
    vector<pair<ll,int>> res;
    for (int p : primes) {
      int y = 0;
      while (x%p == 0) x /= p, ++y;
      if (y != 0) res.emplace_back(p,y);
    }
    if (x != 1) res.emplace_back(x,1);
    return res;
  }
};

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

  Sieve sieve(n+2);
  map<int, int> primes;
  for (int i=1; i<=n; i++) {
    vii vec = sieve.factor(i);
    for (auto p: vec) {
      primes[p.first] += p.second;
    } 
  }
  auto num = [&](int n) {
    int ret = 0;
    for (auto p: primes) {
      if (p.second >= n-1) ++ret;
    }
    return ret;
  };
  ll ans = num(75) + num(25) * (num(3)-1) + num(15) * (num(5)-1) + num(5)*(num(5)-1)*(num(3)-2)/2;
  printf("%lld\n", ans);
  return 0;
}

Measured memory_bytes: 3700
#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define mod 1000000007
#define f first
#define se second
#define ios ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define all(v) (v).begin(),(v).end()
typedef long long ll ;
typedef long double ld ;
typedef long long int lli;

using namespace std;
//reference: geeks
ll mult(ll a,ll b, ll p=mod){	return ((a%p)*(b%p))%p;	}
ll add(ll a, ll b, ll p=mod){return (a%p + b%p)%p;}
ll sub(ll a, ll b, ll p=mod){return (a%p - b%p + p)%p;}
ll fpow(ll n, ll k, ll p = mod) {ll r = 1; for (; k; k >>= 1) {if (k & 1) r = mult(r,n,p); n = mult(n,n,p);} return r;}
ll inv(ll a, ll p = mod) {return fpow(a, p - 2, p);}
#define INF 10000000000
ll dp[3005][3005];
string s,t;

int main()
{
	ios
	
	cin>>s>>t;
	int n=s.size(),m=t.size();
	for(int i=0;i<=n;i++)
	{
		for(int j=0;j<=m;j++)
		{
			if(i==0||j==0)	dp[i][j]=0;
			else if(s[i-1]==t[j-1])
			{
				dp[i][j]=dp[i-1][j-1]+1;
			}
			else
			{
				
				if(dp[i][j-1]<dp[i-1][j])		
					dp[i][j]=dp[i-1][j];
				else	dp[i][j]=dp[i][j-1];
			}
			
		}
	}
	string res="";
	while(n && m)
	{
		if(s[n-1]==t[m-1])
		{	res+=s[n-1];
			n--;	m--;
		}
		else if(dp[n][m-1]>=dp[n-1][m])
			m--;
		else	n--;
	}
	reverse(all(res));
	if(res!="")	cout<<res;
	else	cout<<" ";
}


Measured memory_bytes: 70784
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
using namespace std;

int main() {
	long long x, a, b;
	cin >> x >> a >> b;
	if (b - a <= 0) {
		cout << "delicious" << endl;
	}
	else {
		if (b - a <= x) {
			cout << "safe" << endl;
		}
		else {
			cout << "dangerous" << endl;
		}
	}
	return 0;
}


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

#include <iostream>
//#include <algorithm>
// #include <iomanip>
#define ll long long
#define map unordered_map
#define set unordered_set
#define l_l pair<ll, ll>
#define vll vector<ll>
#define mll map<ll, ll>

using namespace std;

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

int main() {
  // std::cout << std::fixed << std::setprecision(10);
  ll A, B;
  scanf("%lld %lld", &A, &B);

  if ((A * B) % 2 == 1) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }
}


Measured memory_bytes: 3668
def main():
    N = int(input())
    A = [int(i) for i in input().split()]
    odd = A[::2]
    even = A[1::2]
    from collections import Counter
    c_odd = Counter(odd)
    c_even = Counter(even)
    ans = 0
    odd_first = c_odd.most_common()[0][1]
    odd_second = c_odd.most_common()[1][1] if odd_first != N//2 else 0
    even_first = c_even.most_common()[0][1]
    even_second = c_even.most_common()[1][1] if even_first != N//2 else 0
    if c_odd.most_common()[0][0] != c_even.most_common()[0][0]:
        ans = N - odd_first - even_first
    else:
        if odd_first > even_first:
            ans = N - odd_first - even_second
        elif odd_first < even_first:
            ans = N - odd_second - even_first
        else:
            if even_second > odd_second:
                ans = N - even_second - odd_first
            else:
                ans = N - even_first - odd_second
    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 76932
n,k=map(int,input().split())
H=list(map(int,input().split()))
dp=[0]*n
for i in range(1,n):
    S=[]
    for j in range(1,min(k+1,i+1)):
        S.append(dp[i-j]+abs(H[i]-H[i-j]))
    dp[i]=min(S)
print(dp[n-1])

Measured memory_bytes: 84244
import math
import sys

a,b = map(int,input().split())

for i in range(1,1251):
	tax_a = math.floor(i * 0.08)
	tax_b = math.floor(i * 0.1)
	if tax_a == a and tax_b == b:
		print(i)
		sys.exit()
print(-1)


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

int main()
{
  int N;
  cin >> N;
  vector<long long> A(N), B(N);
  for (int i = 0; i < N; ++i)
    cin >> A[i] >> B[i];

  vector<long long> C(N + 1, 0); 
  for (int i = N - 1; i >= 0; --i)
  {
    A[i] += C[i + 1];
    long long amari = A[i] % B[i];
    long long need = 0;
    if (amari != 0)
      need = B[i] - amari;
    C[i] = C[i + 1] + need;
  }
  cout << C[0] << endl;
}

Measured memory_bytes: 2560
#include <bits/stdc++.h>
using namespace std;
long long ans;
int main () {
	int n;
	cin >> n;
	for (int i = 1; i <= n; ++i) {
		if (i % 3 && i % 5) {
			ans += i;
		}
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 3624
#include<iostream>
#include<vector>
using namespace std;
int main(){
  int n, k;cin >> k >> n;
  vector<int>a(n);
  for(auto &&e:a)cin >> e;
  int res = a[0] + k - a.back();
  for(int i = 0;i < n - 1;i++){
    int t = a[i + 1] - a[i];
    if(t > res)res = t;
  }
  cout << k - res << endl;
}

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

using namespace std;
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);

  int n;
  cin >> n;
  vector<int> a(1e5 + 1, 0);
  for (int i = 0; i < n; ++i) {
    int p;
    cin >> p;
    ++a[p];
  }

  int cnt = 0;
  for (int i = 1; i < 1e5 + 1; ++i) {
    for (;;) {
      if (3 <= a[i]) {
        cnt += 1;
        a[i] -= 2;
      } else if (2 == a[i]) {
        cnt += 1;
        bool finished = false;
        a[i] -= 1;
        for (int j = i + 1; j < 1e5; ++j) {
          if (1 < a[j]) {
            finished = true;
            --a[j];
            break;
          }
        }
        if (!finished) {
          for (int j = i - 1; 0 < j; --j) {
            if (1 < a[j]) {
              finished = true;
              --a[j];
              break;
            }
          }
        }
        if (!finished) {
          for (int j = 0; j < 1e5 + 1; ++j) {
            if (0 < a[j]) {
              finished = true;
              --a[j];
              break;
            }
          }
        }
        break;
      } else {
        break;
      }
    }
  }
  cout << (n - cnt*2) << "\n";

  return 0;
}


Measured memory_bytes: 640
#include <cstdio>
#include <iostream>
#include <cmath>
#include <cstring>
#include <sstream>
#include <algorithm>
#include <cstdlib>
#include <map>
#include <queue>
#include <utility>
#include <vector>
#include <set>
#include <memory.h>
#include <iomanip>
#include <bitset>
#include <list>
#include <stack>
#include <deque>

using namespace std;

#define mod 1000000007

int getsum(int n)
{
	int result = 0;
	while(n > 0){
		result += n % 10;
		n /= 10;
	}
	return result;
}

int main()
{
	int n;
	cin >> n;
	int ans = mod;
	for(int i = 1; i < n; i++){
		ans = min(ans, getsum(i) + getsum(n - i));
	}
	cout << ans << endl;
}

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

int main() {
  int A,B,C;
  cin>>A>>B>>C;
  if(A==B &&B!=C){
    cout<<"Yes"<<endl;
  }
  else if(A==C &&B!=C){
    cout<<"Yes"<<endl;
  }
  else if(B==C &&A!=C){
    cout<<"Yes"<<endl;
  }
  else{
    cout<<"No"<<endl;
  }
  
}
    


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define ll long long
#define ull unsigned long long
#define ld long double
#define pii pair <int, int>
#define pll pair <ll, ll>
#define pci pair <char, int>
#define pld pair <ld, ld>
#define ppld pair <pld, pld>
#define ppll pair <pll, pll>
#define pldl pair <ld, ll>
#define vll vector <ll>
#define vvll vector <vll>
#define vpll vector <pll>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define mll map <ll, ll>
#define fastmap gp_hash_table
#define cd complex <double>
#define vcd vector <cd>
#define PI 3.14159265358979
#pragma 03
using namespace std;
using namespace __gnu_pbds;
// chctxdy
ll ptr = 0, n, k;
bool cur = 0, mark[200005]; 
string s;
int main(){
	fastio;
	cin >> n >> k >> s;
	for (ll i = 0; i < n; i++) mark[i] = (s[i] == 'B');
	for (ll i = 1; i <= min(k, (ll)1e7 + (k % 2)); i++){
		if ((mark[ptr] ^ cur)){
			ptr++; ptr %= n; cur ^= 1;
		}
		else mark[ptr] ^= 1;
	}
	for (ll i = 1; i <= n; i++){
		if (mark[ptr] ^ cur) cout << "B";
		else cout << "A";
		ptr++; ptr %= n;
	}
	return 0;
}

Measured memory_bytes: 920
#include <bits/stdc++.h>
using namespace std;
const int NMAX = 1e5+7;
#define ll long long int
ll a,b,c,tasty,antidote;
int main(){
   std::cin >> a >> b >> c;
   antidote = a+b+1;
   tasty = b;
   std::cout << tasty + min(antidote, c) << '\n';
}


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

#define MOD 1000000007

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

    map<long long, long long> count;
    for (long long i = 1; i * i <= N; i++)
    {
        count[i] = 0;
        count[N / i] = 0;
    }

    long long pre = 0;
    long long idx = 0;
    map<long long, long long> dict;
    for (auto itr = count.begin(); itr != count.end(); itr++, idx++)
    {
        count[itr->first] = itr->first - pre;
        pre = itr->first;

        dict[idx] = itr->first;
    }

    vector<vector<long long>> dp(K + 1, vector<long long>(count.size(), 0));
    dp[0][0] = 1;

    for (long long i = 1; i <= K; i++)
    {
        long long sum = 0;
        for (long long j = count.size() - 1; j >= 0; j--)
        {
            sum += dp[i - 1][count.size() - j - 1];
            sum %= MOD;
            dp[i][j] = sum * count[dict[j]];
            dp[i][j] %= MOD;
        }
    }

    long long ans = 0;
    for (long long v : dp.back())
    {
        ans += v;
        ans %= MOD;
    }
    cout << ans << endl;
}


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

const int mo=int(1e9+7);
int n,f[1000010],ans;

void work()
{
	scanf("%d",&n);
	f[0]=1,f[1]=1;
	for (int i=2,s=2; i<=n; i++)
		f[i]=(s+mo-f[i-2])%mo,s=(s+f[i])%mo;
	for (int i=0; i<=n-2; i++)  ans=(ans+(1LL*(n-1)*(n-1)+(i+1))%mo*f[i])%mo;
	ans=(ans+1LL*f[n-1]*(n-1)+f[n])%mo;
	printf("%d",ans);
}

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


Measured memory_bytes: 4096
#include <iostream>
#include <vector>
#include <array>
#include <set>
#include <cmath>
#include <string>
#include <sstream>
#include <queue> 
#include <list>
#include <stack>
#include <unordered_map>
#include <algorithm> 
#include <numeric>  
#include <functional>
#include <cassert>
#include <bitset>
#include <cctype>  
#include <iomanip> 
#include <limits>  
#include <regex>
// std::numeric_limits<int>::max(), min()
// std::setprecision(X)
// std::islower(), std::isupper(), std::tolower, std::toupper
// std::accumulate(m.begin(), m.end(), 0LL);
// std::sort(begin(),end()) // 0, 1, 2, 3 ,4 (default, less);
// std::priority_queue<int, vector<int>, less<int>> que; // 4, 3, 2, 1 (defualt, less) : 
// if ( std::regex_match(S, std::regex("(dream|dreamer|erase|eraser)*")) ) std::cout << "YES" << std::endl;
 
#define rep(i, n) for(int i = 0; i < (int)(n);    i++)
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
typedef long long ll;
typedef std::vector<int> vi;
typedef std::vector<std::vector<int>> vvi;

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


int main (void) {
  std::cin.tie(0);  std::ios::sync_with_stdio(false);
  std::string S, T; std::cin >> S >> T;
  std::cout << T << S << std::endl;
  return 0;
}


Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;
const int MAXN = 2e2 + 5;
const int lb = 60;
const int LB = lb + 5;

struct Linear_basis
{
	ll a[LB];
	int size;
	
	inline void init(void){ size=0; memset(a,0,sizeof(a));}
	
	bool insert(ll x)
	{
		for(int i=lb; i>=0 && x; --i)
		{
			if(!((x>>i)&1)) continue;
			if(a[i]){ x^=a[i]; continue;}
			
			for(int j=0; j<i; ++j)
				if((x>>j)&1) x^=a[j];
			for(int j=i+1; j<=lb; ++j)
				if((a[j]>>i)&1) a[j]^=x;
			a[i] = x;
			++size;
			
			return 1;
		}
		return 0;
	}
}lin;

ll a[MAXN];
char s[MAXN];

void solve(void)
{
	int n;
	scanf("%d",&n);
	for(int i=1; i<=n; ++i) scanf("%lld",&a[i]);
	scanf("%s",s+1);
	
	lin.init();
	
	for(int i=n; i>=1; --i)
	{
		if(s[i]=='0') lin.insert(a[i]);
		else
		{
			if(lin.insert(a[i])){ printf("1\n"); return;}
		}
	}
	
	printf("0\n");
}

int main(void)
{
	int T;
	scanf("%d",&T);
	while(T--) solve();
	return 0;
}

Measured memory_bytes: 1644
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <iomanip>
using namespace std;
typedef long long unsigned int ll;
template<typename T> using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
#define MOD 1000000007

#define REP(i,n) for(int i=0;i<n;i++)
#define REPS(i,f,n) for(int i=(f);i<(n);i++)
#define EACH(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define debug(x) #x << "=" << (x)

#define DEBUG

#ifdef DEBUG
#define var_dump(...) fprintf(stdout, __VA_ARGS__)
#define dump(a) cout << a << "\n";
#else
#define var_dump(...) 42
#define dump(a) 42
#endif

typedef pair<int, int> P;
typedef pair<ll, ll> LP;
typedef pair<int, P> PP;
typedef pair<ll, LP> LPP;

int dy4[]={0, 0, 1, -1};
int dx4[]={1, -1, 0, 0};
int dx8[]={0, 0, 1, -1, 1, 1, -1, -1};
int dy8[]={1, -1, 0, 0, 1, -1, -1, 1};

// https://beta.atcoder.jp/contests/abc054/tasks/abc054_c

int A[105][105] = {};

int main() {
    int N, M; cin >> N >> M;
    int a, b;
    REP(i, M) {
        cin >> a >> b;
        A[a][b] = 1;
        A[b][a] = 1;
    }

    vector<int> perm(N-1);
    REPS(i, 2, N+1) {
        perm[i-2] = i;
    }
    sort(perm.begin(), perm.end());

    int ans = 0;
    do {
        int current = 1;
        for (int i = 0; i < perm.size(); i++) {
            if (!A[current][perm[i]]) break;
            current = perm[i];
            if (i == perm.size()-1) ans++;
        }
    } while(next_permutation(perm.begin(), perm.end()));

    cout << ans << "\n";

    return 0;
}


Measured memory_bytes: 256
package main

import (
	"fmt"
)

func main() {
	var a, b, c int
	fmt.Scan(&a, &b, &c)

	if a < b && c > a && c < b || a > b && c < a && c > b {
		fmt.Println("Yes")
	} else {
		fmt.Println("No")
	}
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
#define INF 100000007
#define rep(i, N) for(ll i = 0; i < N; i++)
#define rep2(i, j, k) for(ll i = j; i < k; i++)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = inx(x, y)
#define print(x) cout << x << "\n"
#define print2(x, y) cout << x << " " << y << "\n"
#define printv(vec) rep(i, vec.size()) cout << vec[i] << " "; print("");
#define ALL(v) v.begin(), v.end()
#define SUM(v) accumulate(ALL(v), 0)
#define MAX(v) *max_element(ALL(v))
#define MIN(v) *min_element(ALL(v))
#define SORT(v) sort(ALL(v))
#define REV(v) reverse(ALL(v))
typedef long long ll;
using namespace std;
using vl = vector<ll>;
using vvl = vector<vector<ll>>;
using vs = vector<string>;
using vvs = vector<vector<string>>;

struct union_find{

  vl parent;
  vl sizes;

  void init(ll n) {
    rep(i, n) parent.push_back(i);
	rep(i, n) sizes.push_back(1);
    return;
  }

  ll root(ll n){
    if(parent[n] == n) return n;
    return parent[n] = root(parent[n]);
  }
  
  ll size(ll n) {
    return sizes[root(n)];
  }

  bool is_same(ll a, ll b){
    return root(a) == root(b);
  }

  void unite(ll a, ll b){
    if(is_same(a, b)) return;
	sizes[root(a)] += size(b);
    parent[root(b)] = root(a);
    return;
  }
};

void solve(){
	
	ll N, M, in1, in2;
	cin >> N >> M;	
	union_find uf;
	uf.init(N);
	rep(i, M){
		cin >> in1 >> in2;
		uf.unite(in1 - 1, in2 - 1);
	}
	ll ans = 0;
	rep(i, N) chmax(ans, uf.size(i));
	print(ans);
		
}	

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





Measured memory_bytes: 7928
#include<iostream>
using namespace std;
int k,s,cnt=0;
int main(){
	cin >> k;
	cin >> s;
	for (int i=0;i<=k;i++){
		for(int j=0;j<=k;j++){
			if (((s-i-j)<=k)&&(s-i-j)>=0){
				cnt++;
			}
		}
	}
	cout << cnt << "\n";
	return 0;
}

Measured memory_bytes: 3556
import std.stdio, std.string, std.conv, std.algorithm;

void main(){
  int n, m, q; rd(n, m, q);
  struct T{int l, r, t, idx;}
  T[] seqs;
  foreach(i; 0..m){
    int l, r; rd(l, r);
    seqs~=T(l-1, r-1, 0, i);
  }
  foreach(i; 0..q){
    int l, r; rd(l, r);
    seqs~=T(l-1, r-1, 1, i);
  }
  seqs.sort!((a, b)=>(a.r==b.r ? a.t<b.t : a.r<b.r));
  auto tree=new SegmentTree(n);
  auto ans=new int[](q);
  foreach(seq; seqs){
    if(seq.t==0){
      tree.add(seq.l, 1);
    }else{
      ans[seq.idx]=tree.sum(seq.l, seq.r+1);
    }
  }
  writefln("%(%s\n%)", ans);
}

class SegmentTree{
  int n=1;
  int[] dat;
  this(int N){
    while(n<N) n*=2;
    dat.length=n*2-1;
  }
  void add(int i, int x){
    i+=n-1;
    dat[i]+=x;
    while(i>0){
      i=(i-1)/2;
      dat[i]=dat[i*2+1]+dat[i*2+2];
    }
  }
  int sum(int ql, int qr){
    return sum(ql, qr, 0, 0, n);
  }
  int sum(int ql, int qr, int i, int il, int ir){
    if(qr<=il || ir<=ql) return 0;
    if(ql<=il && ir<=qr) return dat[i];
    int m=(il+ir)/2;
    return sum(ql, qr, i*2+1, il, m)+sum(ql, qr, i*2+2, m, ir);
  }
}

void rd(T...)(ref T x){
  import std.stdio, std.string, std.conv;
  auto l=readln.split;
  assert(l.length==x.length);
  foreach(i, ref e; x) e=l[i].to!(typeof(e));
}


Measured memory_bytes: 14076
import itertools

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

a,b,c = getints()

res = 0
if a % 2 == b % 2 and a % 2 != c % 2:
    a += 1
    b += 1
    res += 1
if b % 2 == c % 2 and c % 2 != a % 2:
    b += 1
    c += 1
    res += 1
if c % 2 == a % 2 and a % 2 != b % 2:
    c += 1
    a += 1
    res += 1

xs = list(sorted([a,b,c]))
while xs[0] != xs[2]:
    xs[0] += 2
    xs = list(sorted(xs))
    res += 1

print(res)

Measured memory_bytes: 3064
import sys
S = input()
list = [int(S[i]) for i in range(4)]
ans=str(S[0])

for bit in range(1 << 3):
    for i in range(3):
        if bit & (1 << i):
            list[i+1] = list[i+1] * -1
        
        if sum(list) == 7:
            for j in range(1,4):
                if list[j] < 0:
                    ans = ans + "-" + S[j]
                else:
                    ans = ans + "+" + S[j]
            
            print(ans+"=7")
            sys.exit()


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

int main(){
  char c; cin>>c;
  if(c=='a'){cout<<'b'<<endl;}
  else if(c=='b'){cout<<'c'<<endl;}
  else if(c=='c'){cout<<'d'<<endl;}
  else if(c=='d'){cout<<'e'<<endl;}
  else if(c=='e'){cout<<'f'<<endl;}
  else if(c=='f'){cout<<'g'<<endl;}
  else if(c=='g'){cout<<'h'<<endl;}
  else if(c=='h'){cout<<'i'<<endl;}
  else if(c=='i'){cout<<'j'<<endl;}
  else if(c=='j'){cout<<'k'<<endl;}
  else if(c=='k'){cout<<'l'<<endl;}
  else if(c=='l'){cout<<'m'<<endl;}
  else if(c=='m'){cout<<'n'<<endl;}
  else if(c=='n'){cout<<'o'<<endl;}
  else if(c=='o'){cout<<'p'<<endl;}
  else if(c=='p'){cout<<'q'<<endl;}
  else if(c=='q'){cout<<'r'<<endl;}
  else if(c=='r'){cout<<'s'<<endl;}
  else if(c=='s'){cout<<'t'<<endl;}
  else if(c=='t'){cout<<'u'<<endl;}
  else if(c=='u'){cout<<'v'<<endl;}
  else if(c=='v'){cout<<'w'<<endl;}
  else if(c=='w'){cout<<'x'<<endl;}
  else if(c=='x'){cout<<'y'<<endl;}
  else{cout<<'z'<<endl;}
}

Measured memory_bytes: 3640
w = gets.to_i
n = gets.to_i
v = (0..w).to_a
n.times do
   a1,a2 = gets.split(",").map{|x| x.to_i}
   v[a1],v[a2] = v[a2],v[a1]
end
v.shift
v.each do |i|
   puts i
end

Measured memory_bytes: 16000
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MOD 1000000007

vector<vector<int>> P(100010), P2 = P;
vector<set<ll>> A(100010);
vector<ll> parent(100010), psize(100000);

void UFinit(void) {
	for (int i = 0;i < 100010;i++) {
		parent[i] = i;
		psize[i] = 1;
	}
	return;
}

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

void unite(int x, int y) {
	x = root(x);
	y = root(y);
	if (x == y)return;
	parent[y] = parent[x];
	psize[x] += psize[y];
	psize[y] = 0;
}

int main() {
	UFinit();
	int N, x, y, vs;
	cin >> N;
	for (int i = 0;i < N;i++) {
		cin >> x >> y;
		P[y].push_back(x);
		P2[x].push_back(y);
	}
	for (int i = 0;i < 100010;i++) {
		vs = P[i].size();
		if (vs == 0)continue;
		for (int j = 1;j < vs;j++) {
			unite(P[i][0], P[i][j]);
		}
	}
	for (int i = 0;i < 100010;i++) {
		x = root(i);
		for (int j : P2[i]) {
			A[x].insert(j);
			//cout << x << " " << j << endl;
		}
	}
	ll ans = 0;
	for (int i = 0;i < 100010;i++) {
		ans += psize[i] * A[i].size();
		//cout << i << " " << psize[i] << " " << A[i].size() << endl;
	}
	cout << ans - N << endl;
}

Measured memory_bytes: 16640
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
using namespace __gnu_pbds;
using namespace std;
#define IO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define PI 3.1415926535897932384626433832795
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
long long MOD = 1e9+7;
pair<int,int> dx[4] = {{1,0},{-1,0},{0,1},{0,-1}};
const int RANDOM = chrono::high_resolution_clock::now().time_since_epoch().count();
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
struct chash {
    int operator()(int x) const { return x ^ RANDOM; }
};
string toString(long long x)
{
stringstream ss;
ss << x;
string str = ss.str();
return str;
}
long long fastpow(long long x,long long k)
{
    if(!k)
        return 1;
    if(k & 1)
        return ((x * fastpow(x,k-1) % MOD) % MOD) % MOD;
    long long ans = fastpow(x,k/2);
    ans %= MOD;
    ans *= ans;
    ans %= MOD;
    return ans;
}
long long sumF(long long x)
{
    int s = 0;
    while(x)
        s += x%10,x /= 10;
    return s;
}
//a = 1,g = 2,c = 3,t = 4
string toFind = "123";
int n;
bool isBad(int l1,int l2,int l3,int l4)
{
    string s = toString(l1) + toString(l2) + toString(l3) + toString(l4);
    for(int i = 0;i < s.length();i++)
    {
        for(int j = 0;j < s.length();j++)
        {
            if(abs(i-j) > 1)
                continue;
            swap(s[i],s[j]);
            if(s.find(toFind) != string::npos)
            {
               // cout << s << endl;
                return true;
            }
            swap(s[i],s[j]);
        }
    }
    return false;
}
long long dp[105][5][5][5];
long long solve(int idx,int l1,int l2,int l3)
{
    if(idx == n)
        return !isBad(l1,l2,l3,0);
    if(dp[idx][l1][l2][l3] != -1)
        return dp[idx][l1][l2][l3];
    long long C = 0;
    for(int i = 1;i <= 4;i++)
    {
        if(isBad(l1,l2,l3,i))
            continue;
        if(l1 == 0 && l2 == 0 && l3 == 0)
            C += solve(idx + 1,i,0,0) % MOD;
        else if(l2 == 0 && l3 == 0)
            C += solve(idx + 1,l1,i,0) % MOD;
        else if(l3 == 0)
            C += solve(idx + 1,l1,l2,i) % MOD;
        else
            C += solve(idx + 1,l2,l3,i) % MOD;
    }
    return dp[idx][l1][l2][l3] = C % MOD;
}
int main()
{
    memset(dp,-1,sizeof dp);
    IO;
    cin >> n;
    //cout << isBad(2,1,3,0) << endl;
    cout << solve(0,0,0,0);
    return 0;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define DBG(v) cerr << #v << " = " << (v) << endl;

bool M(string s) {
	const int x = stoi(s);
	return 1 <= x && x <= 12;
}

ld dp[(int) 1e6 + 9];

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

	cout << fixed << setprecision(10);

	int n, k;
	cin >> n >> k;

	for (int i = 1; i <= n; ++i)
		dp[i] = 1.0L / n;

	fill(dp + k, end(dp), 1);
	for (int i = k - 1; i >= 1; --i)
		dp[i] = .5 * dp[2 * i];

	ld ans = 0;
	for (int i = 1; i <= n; ++i) {
		ans += dp[i] / n;
	}
	cout << ans;
	return 0;
}


Measured memory_bytes: 15872
#定数
#1≦n≦2*10^5
n = int(input())
P = list(map(int, input().split())) #O(n)

b = n + 1 #border
ans = 0
for i in range(n):  #O(n)
    if P[i] <= b:
        b = P[i]
        ans += 1
    else:
        pass
print(ans)



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

namespace ConsoleApplication39
{
    class Program
    {
        static void Main(string[] args)
        {
            string a = Console.ReadLine();
            if (a[0] == 'a' || a[0] == 'e' || a[0] == 'i' || a[0] == 'u' || a[0] == 'o')
                Console.WriteLine("vowel");
            else
                Console.WriteLine("consonant");
        }
    }
}


Measured memory_bytes: 2648
import java.util.BitSet;
import java.util.HashMap;
import java.util.Scanner;

public class Main{
	public static void main(String[] args){
		Scanner in = new Scanner(System.in);
		HashMap<Integer, BitSet> member;
		HashMap<Integer, Integer> map;
		BitSet counter = new BitSet(2000);
		while(true){
			int n = in.nextInt();
			int m = in.nextInt();
			if(n == 0) return;
			int r = in.nextInt();
			member = new HashMap<Integer, BitSet>();
			map = new HashMap<Integer, Integer>();
			for(int i=0; i<r; i++){
				int t = in.nextInt();
				int pc = in.nextInt();
				int mem = in.nextInt();
				int s = in.nextInt();
				if(!member.containsKey(mem)) member.put(mem, new BitSet(2000));
				if(s==1){
					map.put(pc, t);
				}else{
					member.get(mem).set(map.get(pc), t);
				}
			}
			int q = in.nextInt();
			for(int i=0; i<q; i++){
				int ts = in.nextInt();
				int te = in.nextInt();
				int mem = in.nextInt();
				if(!member.containsKey(mem)){
					System.out.println(0);
					continue;
				}
				counter.clear();
				counter.set(ts, te);
				counter.and(member.get(mem));
				System.out.println(counter.cardinality());
			}
		}
	}
}

Measured memory_bytes: 54380
#include <iostream>

using namespace std;

class A {
	int a, b;
public:
	void solve()
	{

		if ((a <= 8) && (b <= 8)) cout << "Yay!" << endl;
		else cout << ":(" << endl;

	}

	A() { cin >> a >> b; }
};


int main()
{
	A solution;
	solution.solve();

	return 0;
}

Measured memory_bytes: 256
void main(){
	int n = _scan();
	writeln(n%1000==0? 0: 1000-n%1000);
}

import std.stdio, std.conv, std.algorithm, std.numeric, std.string, std.math;

// 1要素のみの入力
T _scan(T= int)(){
	return to!(T)( readln().chomp() );
}

// 1行に同一型の複数入力
T[] _scanln(T = int)(){
	T[] ln;
	foreach(string elm; readln().chomp().split()){
		ln ~= elm.to!T();
	}
	return ln;
}


Measured memory_bytes: 2720
H,W,K = map(int,input().split())
chocolate = []
for _ in range(H):
  chocolate.append(list(input()))
INF = 10**15
ans = INF

for div in range(1<<(H-1)):
  g = 0
  id = [None] * (H)

  # 列をgroup分け
  for i in range(H):
    id[i] = g
    if (div>>i)&1: g += 1

  # groupごとにwhite chocolateが何個あるのか
  c = [ [0]*W for _ in range(g+1) ]
  for i,block in zip(id, chocolate):
    for j,b in enumerate(block):
      if b == "1":
        c[i][j] += 1

  # 縦方向の列をgroup化する
  now = [0] * (g+1)
  lines = g
  for j in range(W):
    for i in range(g+1):
      now[i] += c[i][j]

    ok = all( n<=K for n in now )
    if not ok:
      lines += 1
      now = [0] * (g+1)
      for i in range(g+1):
        now[i] += c[i][j]
      ok = all( n<=K for n in now )
      if not ok:
        # 絶対不可能な場合
        lines = INF
        break

  ans = min(ans, lines)

print(ans)


Measured memory_bytes: 52444
//#define _GLIBCXX_DEBUG
#include<bits/stdc++.h>
#define PI 3.14159265359
using namespace std;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define bit(n,k) (((ll)n>>(ll)k)&1) /*nのk bit目*/
const long long INF= 1e+18+1;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll> >vvl;
typedef pair<ll,ll> P;
typedef tuple<ll,ll,ll> T;
const ll MOD=1000000007LL;
//const ll MOD=998244353LL;
string abc="abcdefghijklmnopqrstuvwxyz";
string ABC="ABCDEFGHIJKLMNOPQRSTUVWXYZ";
vl dx={-1,-1,-1,0,0,1,1,1};
vl dy={1,-1,0,1,-1,1,0,-1};
ll modpow(ll a, ll n, ll mod) {
  
    ll res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}
ll factorial(ll x){
  if(x==0)return 1;
  return x*factorial(x-1)%MOD;
}
int main(){
  ll n;cin>>n;
  ll c,k;cin>>c>>k;
  vl t(n);
  rep(i,n)cin>>t[i];
  sort(t.begin(),t.end());
  ll count=0;
  ll bus=0;
  while(count<n){
    ll now=count;
    while(t[count]<=t[now]+k&&count-now+1<=c&&count<n){
      count++;
    }
    bus++;
  }  

  cout<<bus<<endl;
}

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

int main() {
    int N, M;
    cin >> N >> M;
    vector<int> p(M);
    vector<string> S(M);

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

    int AC = 0;
    int WA = 0;

    unordered_map<int, int> mp;

    for (int i = 0; i < M; i++) {
        if (mp[p[i]] >= 0) {
            if (S[i] == "WA") mp[p[i]]++;
            else {
                WA += mp[p[i]];
                mp[p[i]] = -1;
                AC++;
            }
        }
    }
    
    cout << AC << " " << WA;
}

Measured memory_bytes: 10276
#include <iostream>
#include <algorithm>

using namespace std;

int main(void){
    int a, b, c, d;
    cin >> a >> b;
    c = max(a, b);
    d = min(a, b);
    if(c <= 8 && d <= 8)
        cout<< "Yay!" << "\n";
    else if(c >= 9 || d >= 9)
        cout<< ":(" << "\n";
    return 0;
}

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

bool checkkaibun(int x){
    int a[5];
    for(int i = 0; i < 5; i++){
        a[i] = x % 10;
        x /= 10;
    }
    if(a[0] == a[4] && a[1] == a[3]){
        return true;
    }else{
        return false;
    }
}

int main() {
    int A, B;
    cin >> A >> B;
    int count = 0;
    for(int i = A; i <= B; i++){
        if(checkkaibun(i) == true)count ++;
    }
    cout << count << endl;
    return 0;
}

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

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> p(m), y(m);
    for (int i = 0; i < m; ++i) cin >> p[i] >> y[i], --p[i];
    vector<vector<int> > val(n);
    for (int i = 0; i < m; ++i) val[p[i]].push_back(y[i]);
    for (int v = 0; v < n; ++v) {
        sort(val[v].begin(), val[v].end());
        val[v].erase(unique(val[v].begin(), val[v].end()), val[v].end());
    }
    
    for (int i = 0; i < m; ++i) {
        int v = p[i];
        printf("%06d", v + 1);
        int id = lower_bound(val[v].begin(), val[v].end(), y[i]) - val[v].begin();
        printf("%06d\n", id + 1);
    }
}

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

int main() {
    double r;
    cin >> r;
    cout << fixed << setprecision(8);
    cout << 2*r*M_PI << endl;
    return 0;
}

Measured memory_bytes: 3788
#include <bits/stdc++.h>
using namespace std;
#define IOS ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define rep(i,n) for(ll i=0;i<n;i++)
#define rep1(i,n) for(ll i=1;i<=n;i++)
#define rep_start(a,i,n) for(ll i=a;i<=n;i++)
#define rev(i,n) for(ll i=n-1;i>=0;i--)
#define rev1(i,n) for(ll i=n;i>0;i--)
#define sz(a) int((a).size())
#define all(c) c.begin(),c.end()
#define tr(c,i) for(typeof(c).begin() i+=c.begin; i!=c.end(); i++)
#define present(c,x) (c.find(x)!=c.end())
#define cpresent(c,x) (find(all(c),x)!=c.end())
#define pb push_back
#define F first
#define S second
#define INF INT_MAX
#define mod 1000000007
#define print1(a) cout<<a<<"\n";
#define print2(a,b) cout<<a<<" "<<b<<"\n";
#define print3(a,b,c) cout<<a<<" "<<b<<" "<<c<<"\n";
#define mt make_tuple
#define eb emplace_back

typedef long long int ll;
typedef vector<ll> vi;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<vi> vvi;
typedef pair<ll,ll> ii;
typedef vector<ii> vii;
typedef tuple<int,int,int> State;

void solve(){
    ll n;cin>>n;
    vi arr(n);
    rep(i,n) cin>>arr[i];
    ll tmp=arr[0];
    rep(i,n-1) tmp^=arr[i+1];
    rep(i,n) cout<<(tmp^arr[i])<<" ";
}

signed main() {
    // your code goes here
    IOS
    ll t=1;
    //cin>>t;
    rep1(i,t){
        solve(); 
    }
    return 0;
}

Measured memory_bytes: 4740
N = int(input())
S = input()

ris = [i for i, s in enumerate(S) if s == "R"]
gis = [i for i, s in enumerate(S) if s == "G"]
bis = [i for i, s in enumerate(S) if s == "B"]

all = len(ris) * len(gis) * len(bis)

cnt = 0
for i in range(N):
    for j in range(i+1, N):
        k = 2*j - i
        if 0 <= k < N:
            if S[i] != S[j] and S[i] != S[k] and S[j] != S[k]:
                cnt += 1

ans = all - cnt


print(ans)


Measured memory_bytes: 9176
#include<iostream>

using namespace std;

int main() {
	int a, b, c,tmp;

	cin >> a >> b >> c;

	if (a > b) {
		tmp = a;
		a = b;
		b = tmp;
	}

	if (a <= c && c <= b) {
		printf("Yes\n");
	}
	else {
		printf("No\n");
	}

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
signed main(){
  int a,b,c,d,e,t;
  cin>>a>>b>>c>>d>>e>>t;
  if(e-a<=t)
    cout<<"Yay!"<<endl;
  else
    cout<<":("<<endl;

  return(0);
}


Measured memory_bytes: 256
#coding: utf-8

swap = 0
n = int(input())
a = list(map(int, input().split()))
for i in range(n - 1):
    for j in range(n - 1 - i):
        if a[j] > a[j + 1]:
            temp = a[j]
            a[j] = a[j + 1]
            a[j + 1] = temp
            swap += 1
print(' '.join([str(i) for i in a]))
print(swap)


Measured memory_bytes: 5612
import sys

N = int(input())
C = [0]
for line in sys.stdin:
    c = int(line)
    if C[-1] == c:
        continue
    else:
        C.append(c)

ans = 1
dic = {}
for c in C:
    if c in dic.keys():
        a = dic[c]
        dic[c] += ans
        ans += a
    else:
        dic[c] = ans

print(ans % (10 ** 9 + 7))

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

vector<int> to[200005];
vector<int> ans;

void dfs(int v, int p=-1){
  for (int u: to[v]){
    if (u == p) continue;
    ans[u] += ans[v];
    dfs(u,v);
  }
}

int main(){
  int N, Q;
  cin >> N >> Q;
  for(int i; i<N-1; i++){
    int a,b;
    cin >> a >> b;
    --a;
    --b;
    to[a].push_back(b);
    to[b].push_back(a);
  }

  ans.resize(N);

  for (int i; i<Q; i++){
    int p, x;
    cin >> p >> x;
    --p;
    ans[p] += x;
  }
  dfs(0);
  for(int i=0; i<N; i++){
    cout << ans[i] << endl;
  }
  return 0;
}

Measured memory_bytes: 23424