akhauriyash/Code-Regression huggingface dataset:
import std.algorithm, std.container, std.conv, std.math, std.range, std.typecons, std.stdio, std.string;

void readV(T...)(ref T t){auto r=readln.splitter;foreach(ref v;t){v=r.front.to!(typeof(v));r.popFront;}}
void readA(T)(size_t n,ref T[]t){t=new T[](n);auto r=readln.splitter;foreach(ref v;t){v=r.front.to!T;r.popFront;}}
void readM(T)(size_t r,size_t c,ref T[][]t){t=new T[][](r);foreach(ref v;t)readA(c,v);}

void main()
{
  int n; readV(n);
  int[][] a; readM(n, n, a);

  auto b = new bool[][](n, n);
  foreach (i; 0..n) b[i][i] = true;

  auto r = 0L;
  foreach (i; 0..n-1)
    foreach (j; i+1..n)
      r += a[i][j];

  foreach (i; 0..n)
    foreach (j; 0..n)
      foreach (k; 0..n) {
        if (a[i][j] > a[i][k]+a[k][j]) {
          writeln(-1);
          return;
        } else if (a[i][j] == a[i][k]+a[k][j] && i != k && j != k && !b[i][j]) {
          r -= a[i][j];
          b[i][j] = b[j][i] = true;
        }
      }

  writeln(r);
}


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

int N;
int A[22], B[22], C[22], sum;

int main() {
	cin >> N;
	for (int i = 0; i < N; i++)
		cin >> A[i];
	for (int i = 0; i < N; i++) {
		cin >> B[i];
		sum += B[i];
	}
	for (int i = 0; i < N-1; i++)
		cin >> C[i];
	for (int i = 0; i < N -1; i++) {
		if (A[i] + 1 == A[i + 1])
			sum += C[A[i]-1];
	}
	cout << sum;
}

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

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

  int N; cin >> N;
  vector<string> s(N);
  vector<int> t(N, 0);
  for (int i = 0; i < N; i++) {
    cin >> s[i] >> t[i];
  }
  string X; cin >> X;

  ll ans = 0;
  bool check = false;
  for (int i = 0; i < N; i++) {
    if (check) ans += t[i];
    if (s[i] == X) check = true;
  }

  cout << ans << '\n';
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <math.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
const ll mod = 1000000007;
const int INF = 1001001001;
const ll LINF = 1001001001001001001;

vector<vector<ll>> dp,mtch;
ll n ;
ll f(ll x,ll y){
    if(dp[x][y]!=INF) return dp[x][y];
    bitset<21> yb(y),ybreset(y);
    ll ret = 0;
    for(int i=0;i<n;i++){
        yb = ybreset;
        if(yb.test(i) ||mtch.at(x+1).at(n-1-i) == 0) continue;
        yb.set(i,1);
        ll yu=yb.to_ullong();
        ret = (ret + f(x+1,yu)) % mod;
    }
    dp[x][y] = ret; return ret;
}

int main(){
    cin >> n;
    dp.resize(n,vector<ll>(1<<n,INF));
    dp[n-1][(1<<n)-1] = 1;
    mtch.resize(n,vector<ll>(n,0));
    rep(i,n) rep(j,n) cin >> mtch.at(i).at(j);
    ll ans = 0;
    for(int i=0;i<n;i++){
        ans = (ans + (f(0,(1<<i)) * mtch.at(0).at(n-1-i))) % mod;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 360832
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n = I()
G = [[] for _ in range(n)]
for a, b, c in LIR(n - 1):
    G[a - 1] += [(b - 1, c)]
    G[b - 1] += [(a - 1, c)]

q, k = LI()
dq = deque([k - 1])
dist = [-1] * n
dist[k - 1] = 0
while dq:
    u = dq.popleft()
    for v, c in G[u]:
        if dist[v] == -1:
            dist[v] = dist[u] + c
            dq += [v]

for _ in range(q):
    x, y = LI()
    print(dist[x - 1] + dist[y - 1])




Measured memory_bytes: 80304
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=int(a);i<int(b);++i)
#define SIZE 200005
#define MOD 1000000007
#define INF 1000000005

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

vector<int> E[SIZE];
int d[SIZE];

void bfs(int s){
  queue<int> que;
  que.push(s);
  fill(d,d+SIZE,INF);
  d[s] = 0; 
  while(!que.empty()){
    int v = que.front();que.pop();
    for(int to : E[v]) if(d[to] == INF){
      d[to] = v;
      que.push(to);
    }
  }
}


int n,m;

int main(){

  cin >> n >> m;
  rep(i,0,m){
    int a,b;
    cin >> a >> b;
    E[a].push_back(b);
    E[b].push_back(a);
  }
  bfs(1);
  rep(i,1,n+1){
    if(d[i] == INF){
      cout << "No" << endl;
      return 0;
    }
  }
  cout << "Yes" << endl;
  rep(i,2,n+1){
    cout << d[i] << endl;
  }

  return 0;
}


Measured memory_bytes: 13068
#include <stdio.h>
#include <math.h>
#include <map>
#include <utility>
#include <algorithm>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define mp make_pair
inline double sq(double a) { return a*a; }
#define INF (1e100)
#define EPS (1e-9)

int n;
double hx, hy, mx, my, xs[32], ys[32], ds[32], ws[32][32];
pair<double, int> ns[32];

bool rec(int b, int at, double t) {
    if (b == (1<<n)-1) return true;
    rep (i, n) {
        const int ix = ns[i].second;
        if (b&(1<<ix)) continue;
        double nt = t + ws[at][ix];
        if (nt > ds[ix]-EPS) return false;
        if (rec(b|(1<<ix), ix, nt)) return true;
    }
    return false;
}

int main() {
    for (;;) {
        scanf("%d%lf%lf%lf%lf", &n, &hx, &hy, &mx, &my);
        if (n == 0) return 0;
        rep (i, n) scanf("%lf%lf", xs+i, ys+i);
        rep (i, n) ds[i] = sqrt(sq(xs[i]-mx) + sq(ys[i]-my));
        rep (i, n) ns[i] = mp(ds[i], i);
        sort(ns, ns+n);
        rep (i, n) rep (j, n) {
            ws[i][j] = sqrt(sq(xs[i]-xs[j]) + sq(ys[i]-ys[j]));
        }
        bool ans = false;
        rep (i, n) {
            double t = sqrt(sq(xs[i]-hx) + sq(ys[i]-hy));
            if (t < ds[i]-EPS && rec(1<<i, i, t)) { ans = true; break; }
        }
        puts(ans ? "YES" : "NO");
    }
}

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

l,r = 1,max(A)
while l<r:
	m = (l+r)//2
	s = sum([a//m+(not a%m==0)-1 for a in A])
	if s <= K:
		r = m
	else:
		l = m+1
print(r)

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

int main() {
  int n;
  cin>>n;
  int m = n%10;

  if(m==3) cout<<"bon"<<endl;
  else if(m==0 || m==1 || m==6 || m==8) cout<<"pon"<<endl;
  else cout<<"hon"<<endl;

  return 0;
}

Measured memory_bytes: 3580
X,K,D = list(map(int,input().split()))

X = abs(X)

nokori = abs(X - (K * D)) #残りマス
q = abs(X // D) #商
p = abs(X % D) #余り
nokorik = K-q #残り回数
if K <= q:
    print(nokori)
else:
    if nokorik % 2 == 0:
        print(p)
    else:
        print(abs(p-D))
        

Measured memory_bytes: 61840
#include<iostream>
#include<string.h>
#include<string>
#include<cstdio>
#include<stdlib.h>
#include<algorithm>
#include<stack>
#include<queue>
#include<vector>
#include<cmath>
#include<utility>
#include<set>
#define ll long long int
#define ld long double
#define INF 1000000000
#define EPS 0.0000000001
#define rep(i,n) for(i=0;i<n;i++)
using namespace std;
typedef pair<int, int> pii;

int main()
{
  int i,j;
  int w,h,n;
  int x,y,a;
  cin>>w>>h>>n;
  int l=0;
  int r=w;
  int u=h;
  int d=0;
  rep(i,n){
    cin>>x>>y>>a;
    switch(a){
    case 1:l=max(l,x);break;
    case 2:r=min(r,x);break;
    case 3:d=max(d,y);break;
    case 4:u=min(u,y);break;
    }
  }
  int ans=(r-l)*(u-d);
  if(ans>0 && r-l>0 && u-d>0)
    cout<<ans<<endl;
  else
    cout<<"0"<<endl;
}


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

int dp[101][100010] = {};
bool vis[101][100010] = {};

int main() {
	int N, W;
	cin >> N >> W;
	vis[0][0] = true;
	for(int i=1;i<=N;i++) {
		int w, v;
		cin >> w >> v;
		for(int j=0;j<v;j++) {
			dp[i][j] = dp[i-1][j];
			vis[i][j] = vis[i-1][j];
		}
		for(int j=v;j<=100005;j++) {
			if(dp[i-1][j-v] + w <= W && vis[i-1][j-v] == true) {
				dp[i][j] = min(dp[i-1][j-v] + w, vis[i-1][j]?dp[i-1][j]:999999999);
				vis[i][j] = true;
			} else {
				dp[i][j] = dp[i-1][j];
				vis[i][j] = vis[i-1][j];
			}
		}
	}
	int ans = 0;
	for(int i=0;i<=100005;i++) {
		if(vis[N][i] == true) {
			ans = i;
		}
	}
	cout << ans;
}

Measured memory_bytes: 49536
import java.util.*

fun main(args: Array<String>) {
    val sc = Scanner(System.`in`)
    val w = sc.nextLong()
    val h = sc.nextLong()
    val x = sc.nextLong()
    val y = sc.nextLong()
    println(problem130c(w, h, x, y))
}

fun problem130c(w: Long, h: Long, x: Long, y: Long): String {

    val num = if (x + x == w &&  y + y == h) 1 else 0
    return "${(w * h / 2.0)} $num"
}

Measured memory_bytes: 29484
/*
Problem : https://atcoder.jp/contests/abc138/tasks/abc138_e	
Algorithm : string
Status :
*/
#include <bits/stdc++.h>
#include <cstring>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <iostream>
using namespace std;
typedef long long ll;

const int INF = 0x3f3f3f3f;
const int MAXN = 1e5 + 5;

int n,m,pos;
ll ans;
vector<int> v[30];
char s[MAXN],t[MAXN];

int main(){
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
	scanf("%s",s + 1);
	scanf("%s",t + 1);
	n = strlen(s + 1);
	m = strlen(t + 1);
	for(int i = 1;i <= n;i++)
	    v[s[i] - 'a'].push_back(i);
	for(int i = 1;i <= m;i++){
		int ch = t[i] - 'a';
		if(!v[ch].size()){
			printf("-1\n");
			return 0;
		}
		int x = lower_bound(v[ch].begin(),v[ch].end(),pos + 1) - v[ch].begin();
		//cout << x << " " << v[ch][x] << endl;
		if(x == v[ch].size()){
			int y = lower_bound(v[ch].begin(),v[ch].end(),1) - v[ch].begin();
			ans += n - pos + v[ch][y];
			pos = v[ch][y];
		}else{
			ans += v[ch][x] - pos;
			pos = v[ch][x];
		}
		//cout << pos << " " << ans << endl << endl;
	}
	printf("%lld\n",ans);
	return 0;
}


Measured memory_bytes: 1024
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization ("unroll-loops")
#include <bits/stdc++.h>
    
#define endl '\n'
//#define int long long

using namespace std;
signed main() {
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int a, b, c, k;
    cin >> a >> b >> c >> k;
    if (k <= a) cout << k;
    else if (k <= a + b) cout << a;
    else cout << a - (k - a - b);
}


Measured memory_bytes: 3636
#include <bits/stdc++.h>
#define fi first
#define se second
#define rep(i, s, n) for (int i = (s); i < (n); ++i)
#define rrep(i, n, g) for (int i = (n)-1; i >= (g); --i)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define len(x) (int)(x).size()
#define dup(x, y) (((x) + (y)-1) / (y))
#define pb push_back
#define Field(T) vector<vector<T>>
using namespace std;
using ll = long long;
using P = pair<int, int>;

int main() {
  int a,b;
  cin >> a>>b;
  if (a*b % 2 == 0)
    cout << "No" << endl;
  else
    cout << "Yes" << endl;
}

Measured memory_bytes: 3584
#include <bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
typedef long long ll;
typedef long double ld;
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define mod 1000000007
#define inf 1000000000000000
#define autoit(x,it) for(auto it = x.begin(); it != x.end(); it++)
#define rep(n) for(ll i = 0; i < n; i++)
#define repi(i,n) for(ll i = 0; i < n; i++)

#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds; 

#define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update> 

using namespace std;


int main()
{
   FAST/**/
   
   ll a,b,c;
   cin>>a>>b>>c;
   
   if((a == b && a!=c) ||(a == c && a!=b) || (a!=b && b == c))
        cout<<"Yes\n";
   else cout<<"No\n";        
   
   return 0;        
}  
   

Measured memory_bytes: 256
k = int(input())
a, b = map(int, input().split())

if b - a >= k - 1:
  print("OK")
elif  k == 1:
  print("OK")
elif b == k or a == k:
  print("OK")
elif b % k == 0 or a % k == 0:
  print("OK")
elif a < k and k < b:
  print("OK")
elif a != b and k == 2:
  print("OK")
elif b < k:
  print("NG")
elif a % k > b % k:
  print("OK")
else:
  print("NG")



Measured memory_bytes: 9060
#include <stdio.h>
#include <ctype.h>
#include <string.h>
 
int main(void){
    char W[11],T[1000];
    int i,count=0;
     
    scanf("%s",W);
    while(scanf("%s",T),strcmp(T,"END_OF_TEXT")){
        for(i=0;T[i]!='\0';i++){
            T[i]=tolower(T[i]);
        }
         
        if(strcmp(W,T)==0) count+=1;
    }
     
    printf("%d\n",count);
     
    return 0;
}


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

int main() {
    char s[6];
    cin >> s;
    if(s[2] == s[3] && s[4] == s[5]) cout << "Yes" << endl;
    else cout << "No" << endl;

}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>

using namespace std;

const int LIM = 1e+5 + 100;

vector<map<int, long long>> vm(LIM);
vector<map<int, long long>> vt(LIM);

vector<long long> a(LIM);
vector<bool> used(LIM, false);
vector<bool> used_c(LIM, false);
vector<bool> setted(LIM, false);

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

  int r, c, n;
  cin >> r >> c >> n;

  for (int i = 0; i < n; ++i) {
    int ii, jj, val;
    cin >> ii >> jj >> val;
    --ii;
    --jj;
    vm[ii][jj] = val;
    vt[jj][ii] = val;
  }

  bool ok = true;
  for (int row = 0; row < r; ++row) {
    if (used[row])
      continue;
    long long min_diff = 0;
    long long max_diff = 0;

    used[row] = true;
    queue<int> current;
    queue<int> q;

    for (const pair<int, int>& p : vm[row]) {
      a[p.first] = p.second;
      used_c[p.first] = true;
      setted[p.first] = true;
      q.push(p.first);
    }

    while (!q.empty()) {
      int col = q.front();
      q.pop();
      current.push(col);

      for (const pair<int, int>& p : vt[col]) {
        int row = p.first;
        if (used[row])
          continue;
        used[row] = true;

        long long diff = 0;
        for (const pair<int, int>& pp : vm[row]) {
          if (setted[pp.first]) {
            diff = pp.second - a[pp.first];
          }
        }

        for (const pair<int, int>& pp : vm[row]) {
          if (setted[pp.first] && pp.second - diff != a[pp.first])
            ok = false;
          if (!setted[pp.first]) {
            a[pp.first] = pp.second - diff;
            setted[pp.first] = true;
          }

          if (!used_c[pp.first]) {
            q.push(pp.first);
            used_c[pp.first] = true;
          }
        }

        min_diff = min(min_diff, diff);
        max_diff = max(max_diff, diff);
      }
    }

    while (!current.empty()) {
      long long x = a[current.front()];
      current.pop();
      if (x + min_diff < 0 || x + max_diff < 0)
        ok = false;
    }
  }

  if (!ok)
    cout << "No" << endl;
  else
    cout << "Yes" << endl;

  return 0;
}


Measured memory_bytes: 23168
#include <bits/stdc++.h>
#define rep(i , n) for (int i = 0; i < (int)(n); i++)
const int INF = 1<<29;
using namespace std;
using ll = long long;
int main(){
    string S;
    cin >> S;
    if(S[0] == 'R' && S[1] == 'R' && S[2] == 'R'){
        cout << 3 << endl;
    }
    else if(S[0] != 'R' && S[1] == 'R' && S[2] == 'R'){
        cout << 2 << endl;
    }
    else if(S[0] == 'R' && S[1] != 'R' && S[2] == 'R'){
        cout << 1 << endl;
    }
    else if(S[0] == 'R' && S[1] == 'R' && S[2] != 'R'){
        cout << 2 << endl;
    }
    else if(S[0] != 'R' && S[1] != 'R' && S[2] == 'R'){
        cout << 1 << endl;
    }
    else if(S[0] == 'R' && S[1] != 'R' && S[2] != 'R'){
        cout << 1 << endl;
    }
    else if(S[0] != 'R' && S[1] == 'R' && S[2] != 'R'){
        cout << 1 << endl;
    }
    else{
        cout << 0 << endl;
    }
}

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

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vector<int>> vvi;
typedef vector<vector<ll>> vvl;

class Increase {
public:
  int n, flowMax = 1000000;
  vector<map<int, int>> p;
  vector<int> parent;
  Increase(int _n, vector<map<int, int>> _p) {
    n = _n;
    p = _p;
    parent.resize(n);
  }
  int dfs(int id, int from, int flow) {
    if (parent[id] != id)
      return 0;
    parent[id] = from;
    if (id == n - 1)
      return flow;
    for (auto &to : p[id])
      if (to.second > 0) {
        int next = dfs(to.first, id, min(flow, to.second));
        if (next > 0)
          return next;
      }
    return 0;
  }
  int solve() {
    int ret = 0, flow;
    for (int i = 0; i < n; i++)
      parent[i] = i;

    while ((flow = dfs(0, -1, flowMax)) > 0) {
      int now = n - 1;
      ret += flow;
      while (parent[now] >= 0) {
        p[parent[now]][now] -= flow;
        p[now][parent[now]] += flow;
        now = parent[now];
      }
      for (int i = 0; i < n; i++)
        parent[i] = i;
    }
    return ret;
  }
};
int n, m;
vector<map<int, int>> p;

int main() {
  cin >> n >> m;
  p.resize(n + 2);
  for (int i = 0; i < m; i++) {
    int t, f;
    cin >> t >> f;
    p[t][f] = 1;
    p[f][t] = 1;
  }
  vector<int> p6, p4, p3;
  for (int i = 1; i <= n; i++) {
    if (p[i].size() >= 6)
      p6.push_back(i);
    if (p[i].size() == 4)
      p4.push_back(i);
    if (p[i].size() % 2 == 1)
      p3.push_back(i);
  }
  if (p3.size() > 0) {
    cout << "No" << endl;
  } else if (p6.size() > 0) {
    cout << "Yes" << endl;
  } else if (p4.size() >= 3) {
    cout << "Yes" << endl;
  } else if (p4.size() == 2) {
    p[0][p4[0]] = 10;
    p[p4[1]][n + 1] = 10;
    Increase flow(n + 2, p);
    if (flow.solve() == 2)
      cout << "Yes" << endl;
    else
      cout << "No" << endl;
  } else {
    cout << "No" << endl;
  }
  return 0;
}


Measured memory_bytes: 42880
$kannondou = [0, 1, 2, 4]
$size = $kannondou.size

def count(n)
  while $size <= n
    $kannondou[$size] = $kannondou[$size-1] + $kannondou[$size-2] + $kannondou[$size-3]
    $size += 1
  end
  $kannondou[n]
end

while n = gets.to_i
  break if n.zero?
  puts count(n) / 3650 + 1
end

Measured memory_bytes: 6084
import java.util.*;

class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);     
      String S = sc.next();
      if(S.charAt(S.length()-1)=='s'){
        System.out.println(S+"es");
      }else{
        System.out.println(S+"s");
      }
    }
}

Measured memory_bytes: 27016
#[test]
fn test_solve() {
    assert_eq!(solve("3\ndwango 2\nsixth 5\nprelims 25\ndwango\n"), "30\n");
    assert_eq!(solve("1\nabcde 1000\nabcde\n"), "0\n");
    assert_eq!(solve("15\nypnxn 279\nkgjgwx 464\nqquhuwq 327\nrxing 549\npmuduhznoaqu 832\ndagktgdarveusju 595\nwunfagppcoi 200\ndhavrncwfw 720\njpcmigg 658\nwrczqxycivdqn 639\nmcmkkbnjfeod 992\nhtqvkgkbhtytsz 130\ntwflegsjz 467\ndswxxrxuzzfhkp 989\nszfwtzfpnscgue 958\npmuduhznoaqu\n"), "6348\n");
}
fn solve(src: &str) -> String {
    let mut sc = Scanner::from_str(src);

    let n: usize = sc.read();
    let mut st = Vec::new();
    for _ in 0..n {
        let s = sc.chars();
        let t: usize = sc.read();
        st.push((s,t));
    }
    let x = sc.chars();
    let mut f = false;
    let mut a = 0;
    for (s,t) in st {
        if f {
            a += t;
        }
        if x == s {
            f = true;
        }
    }

    format!("{}\n", a)
}

fn main() {
    let mut buf = String::new();
    use std::io;
    use std::io::{Read, Write};
    io::stdin().read_to_string(&mut buf).unwrap();
    io::stdout().write_all(solve(&buf).as_bytes()).unwrap();
}

struct Scanner<'a>(std::str::SplitWhitespace<'a>);
impl<'a> Scanner<'a> {
    fn from_str(src: &str) -> Scanner {
        Scanner(src.split_whitespace())
    }
    fn get(&mut self) -> &str {
        self.0.next().unwrap()
    }
    fn read<T: std::str::FromStr>(&mut self) -> T {
        self.get().parse().ok().unwrap()
    }
    fn chars(&mut self) -> Vec<char> {
        self.get().chars().collect()
    }
}

Measured memory_bytes: 4352
#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define inf 1000000000
#define md 1000000007
#define pb push_back
#define li 100005
#define int long long
using namespace std;
int n;
main(){
	scanf("%lld",&n);
	printf("%lld\n",(n)*(n-1)/2);
	return 0;
}




Measured memory_bytes: 256
from math import sqrt

def I(): return int(input())
def MI(): return map(int, input().split())
def LMI(): return list(map(int, input().split()))
MOD=10 ** 9 + 7


N = I()
rt = sqrt(N)
if rt.is_integer():
    print(N)
else:
    print(int(rt) ** 2)


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

#define ll long long
#define ull unsigned long long 
#define endl '\n'

int main(){
    ios_base::sync_with_stdio(false);cin.tie(0);
    int n, t;
    cin >> n >> t;;
    vector<int> a(n);
    for(int i=0; i<n; ++i)
        cin >> a[i];
    
    ull x=t;
    for(int i=1; i<n; ++i){
        x += min(a[i]-a[i-1], t);
    }
    cout << x;
    return 0;
}


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

int main() {
  ll n, a, v0 = 0, v2 = 0, v4 = 0;
  cin >> n;
  rep(i, n) {
    cin >> a;
    if (a % 4 == 0)
      v4++;
    else if (a % 2 == 0)
      v2++;
    else
      v0++;
  }

  if (v2 == 0)
    cout << (v0 - v4 <= 1 ? "Yes" : "No") << endl;
  else
    cout << (v0 - v4 == 0 ? "Yes" : "No") << endl;

  return 0;
}


Measured memory_bytes: 256
program atcoder
implicit none
integer(16) :: a(2),f(2),i

read(*,*) a(1:2)

a(1) = a(1)-1
do i = 1,2
	if (mod(a(i),4) == 0) then
    	f(i) = a(i)
    else if (mod(a(i),4) == 1) then
    	f(i) = 1
    else if (mod(a(i),4) == 2) then
    	f(i) = a(i) + 1
    else if (mod(a(i),4) == 3) then
    	f(i) = 0
    else if (a(i) == -1) then
    	f(i) = 0
    end if
end do

write(*,'(i0)') xor(f(1),f(2))

contains

end program atcoder

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <cmath>
#include <queue>
#include <utility>
#include <map>
#include <climits>
#include <vector>
#include <set>
#include <string>
#include <numeric>

#define FAST_IO ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
//#define int long long
using namespace std;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<pair<int, int>> vii;
const int N = 2 * (1e5 + 1);
const int INF = 1e9 + 5;
const long long MOD = 1e9 + 7;

int32_t main() {
    FAST_IO;
    int a, b;
    char op;
    cin >> a >> op >> b;
    cout << (op == '+' ? a + b : a - b);
    return 0;
}


Measured memory_bytes: 256
package main

// Insertion Sort

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
	"strings"
)

func main() {
	sc.Split(bufio.ScanWords)
	n := nextInt()
	s := make([]int, n)
	for i := range s {
		s[i] = nextInt()
	}
	f := true
	c := 0
	for f {
		f = false
		for i := n - 1; 1 <= i; i-- {
			if s[i] < s[i-1] {
				v := s[i]
				s[i] = s[i-1]
				s[i-1] = v
				f = true
				c++
			}
		}
	}
	fmt.Println(convertIntToString(s, " "))
	fmt.Println(c)
}

func convertIntToString(s []int, d string) string {
	b := make([]string, len(s))
	for i, v := range s {
		b[i] = strconv.Itoa(v)
	}

	return strings.Join(b, d)
}

// =================================
// I/O util
// =================================

var sc = bufio.NewScanner(os.Stdin)

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

func nextInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

// =================================



Measured memory_bytes: 1112
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
#define rep(i,m,n) for(int i=m;i<n;i++)
ll mod=1e9+7;

int main(){
  ll h;
  int n;
  cin>>h>>n;
  ll a=0;
  rep(i,0,n){
    int b;
    cin>>b;
    a+=b;
  }
  if(a>=h) cout<<"Yes"<<endl;
  else cout<<"No"<<endl;
}

Measured memory_bytes: 256
import java.util.*;
import java.io.*;
public class Main{
	static int[][] dp;
	  static int mod = 998244353;
   public static void main(String[] main) throws Exception{
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st = new StringTokenizer(br.readLine());
      PrintWriter out = new PrintWriter(System.out);
      int n = Integer.parseInt(st.nextToken());
      int s = Integer.parseInt(st.nextToken());
      int[] a = new int[n];
      dp = new int[n+1][s+1];
      st = new StringTokenizer(br.readLine());
      for(int i = 0; i < n; i++) {
          a[i] = Integer.parseInt(st.nextToken());
      }
      dp[0][0] = 2;
      if(a[0] <= s) {
    	  dp[0][a[0]] = 1;
      }
      for(int i = 1; i < n; i++) {
    	  for(int j = s; j >= 0; j--) {
    		  if(j + a[i] <= s) {
    			  dp[i][j+a[i]]= (dp[i][j+a[i]] + dp[i-1][j])%mod;
    		  }
    		  dp[i][j] = (dp[i][j] + 2*dp[i-1][j])%mod;
    	  }
      }
      out.println(dp[n-1][s]);
      out.close();
   }
}

Measured memory_bytes: 83768
#include <algorithm>
#include <cassert>
#include <cctype>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstring>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <vector>
#include <list>
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
//#define cerr if(false) cerr
#ifdef DEBUG
#define show(...) cerr << #__VA_ARGS__ << " = ", debug(__VA_ARGS__);
#else
#define show(...) 42
#endif
using namespace std;
using ll = long long;
using pii = pair<int, int>;
template <typename T, typename S>
ostream& operator<<(ostream& os, pair<T, S> a) {
    os << '(' << a.first << ',' << a.second << ')';
    return os;
}
template <typename T>
ostream& operator<<(ostream& os, vector<T> v) {
    for (auto x : v) os << x << ' ';
    return os;
}
void debug() {
    cerr << '\n';
}
template <typename H, typename... T>
void debug(H a, T... b) {
    cerr << a;
    if (sizeof...(b)) cerr << ", ";
    debug(b...);
}
int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    int cnt = 0;
    ll d;
    cin >> d;
    while(n--){
        ll x, y;
        cin >> x >> y;
        if(x *x + y * y <= d * d)cnt++;
    }
    cout << cnt << endl;
}


Measured memory_bytes: 3656
#include<bits/stdc++.h>
using namespace std;
const int N = 3e3 + 1;
int n , b[N] , dp[N][N];
string s , t;
int calc(int i , int j){
    if(i == s.size() || j == t.size())
        return 0;
    int &ret = dp[i][j];
    if(ret != -1)
        return ret;
    if(s[i] == t[j])
        return ret = 1 + calc(i + 1 , j + 1);
    return ret = max(calc(i + 1 , j ) , calc(i , j + 1));
}
void build(int i , int j){
    if(i == s.size() || j == t.size())
        return ;
    if(s[i] == t[j]){
        cout<<s[i];
        build(i + 1, j + 1);
        return ;
    }
    if(calc(i , j) == calc(i + 1 , j) )
        build(i + 1 , j);
    else build(i , j + 1);
}
int main(){
    cin >> s >> t;
    memset(dp , -1 , sizeof dp);
    calc(0 , 0);
    build(0 , 0);
    return 0;
}

Measured memory_bytes: 35712
a,b = map(int,input().split())
c=list(map(int,input().split()))
for i in range(a,99999):
    j = list(str(i))
    n=0
    for k in j:
        for d in c:
            if int(k)==d:
                n+=1
    if n==0:
        print(i)
        break


Measured memory_bytes: 2940
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ii = pair<int, int>;
#define sz(x) (int)(x).size()

const int N = 200010;
int a[N], n;

int main() {
  scanf("%d", &n);
  for (int i = 0; i < n; i++) scanf("%d", &a[i]);
  int x = 0;
  for (int i = 0; i < n; i++) x ^= a[i];
  for (int i = 0; i < n; i++)
    printf("%d%c", x ^ a[i], (i == n - 1 ? '\n' : ' '));
}



Measured memory_bytes: 4316
#include <bits/stdc++.h>
     
typedef long long LL;
     
#define FOR(i, a, b) for (int i = (a), i##_END_ = (b); i <= i##_END_; i++)
#define DNF(i, a, b) for (int i = (a), i##_END_ = (b); i >= i##_END_; i--)
     
template <typename Tp> void in(Tp &x) {
	char ch = getchar(), f = 1; x = 0;
	while (ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
	if (ch == '-') ch = getchar(), f = -1;
	while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
	x *= f;
}
     
template <typename Tp> void out(Tp x) {
	if (x > 9) out(x / 10);
	putchar(x % 10 + '0');
	return;
}
     
template <typename Tp> Tp Max(const Tp &x, const Tp &y) {return x > y ? x : y;}
template <typename Tp> Tp Min(const Tp &x, const Tp &y) {return x < y ? x : y;}
template <typename Tp> bool chkmax(Tp &x, Tp y) {return x >= y ? 0 : (x=y, 1);}
template <typename Tp> bool chkmin(Tp &x, Tp y) {return x <= y ? 0 : (x=y, 1);}
     
const int MAXN = 52;
     
int n, M, D;
int sz[MAXN], fa[MAXN];
int head[MAXN], data[MAXN], nxt[MAXN], cnt;
     
LL c[MAXN], v[MAXN];
LL f[MAXN][MAXN * MAXN * MAXN];
     
void add(int x, int y)
{
	nxt[cnt] = head[x]; data[cnt] = y; head[x] = cnt++;
}
     
void dfs(int now)
{
	c[now] = 1; v[now] = sz[now];
	for (int i = head[now]; i != -1; i = nxt[i]) {
		dfs(data[i]); c[now] += c[data[i]]; v[now] += v[data[i]];
	}
}
     
int to[MAXN], num[MAXN];
LL que[2][MAXN][MAXN * MAXN * MAXN]; int front[MAXN], tail[MAXN];
     
bool cmp(const int &i, const int &j) {return c[i] * 1ll * v[j] < c[j] * 1ll * v[i];}
     
int main()
{
	in(n); in(M); in(D);
     
	memset(head, -1, sizeof head);
    	
	in(sz[1]);
	FOR(i, 2, n) in(sz[i]), in(fa[i]), add(fa[i], i);
     
	dfs(1);
     
	memset(f, 0x3f, sizeof f);
     
	int all = 50 * 50 * n;
    	
	f[0][0] = 0;
	FOR(i, 1, n) {
		FOR(k, 0, c[i] - 1) front[k] = 1, tail[k] = 0;
		int lim = Min(D, 50); if (i == 1) lim = 50;
		FOR(j, 0, all) {
			int b = j % c[i];
			LL pre = f[i - 1][b + (j / c[i]) * c[i]] - (j / c[i]) * v[i];
			while (tail[b] >= front[b] && que[0][b][tail[b]] >= pre) tail[b]--;
			++tail[b]; que[0][b][tail[b]] = pre; que[1][b][tail[b]] = j / c[i];
			while (tail[b] >= front[b] && que[1][b][front[b]] < (j / c[i]) - lim) front[b]++;
			f[i][j] = que[0][b][front[b]] + (j / c[i]) * v[i];
		}
	}
     
	num[1] = 0x3f3f3f3f; FOR(i, 2, n) num[i] = Max(0, D - 50);
	FOR(i, 1, n) to[i] = i;
     
	std::sort(to + 1, to + n + 1, cmp);
     
	LL ans = 0;
    	
	FOR(i, 0, all) {
		if (f[n][i] > M) continue;
		LL need = f[n][i], sum = i;
		DNF(j, n, 1) {
			int can = Min((LL)num[to[j]], (M - need) / v[to[j]]);
			sum += can * c[to[j]]; need += can * v[to[j]];
		}
		chkmax(ans, sum);
	}
     
	printf("%lld\n", ans);
    	
	return 0;
}


Measured memory_bytes: 170368
h,n=map(int,input().split())
dp=[10**10]*(h+1)
dp[0]=0
X=[]
for i in range(n):
    a,b=map(int,input().split())
    X.append([a,b])


for i in range(h):
    for j in range(n):
        k=min(i+X[j][0],h)
        dp[k]=min(dp[k],dp[i]+X[j][1])
print(dp[h])

Measured memory_bytes: 41580
#include<iostream>
#include<cstdio>
#include<cstring>

typedef long long ll;
const int N=18,L=1<<N,MOD=1000000007;
inline void inc(int a,int &b){b=(a+b)%MOD;}
ll inv(int x){return x==1?1:(-(MOD/x)*inv(MOD%x)%MOD);}
ll qpow(ll a,ll b){ll c=1;for(;b;b>>=1,a=a*a%MOD)if(b&1)c=c*a%MOD;return c;}

int fact[L],ifact[L];
int C(int n,int m){if(n<m)return 0;return (ll)fact[n]*ifact[m]%MOD*ifact[n-m]%MOD;}

int A[N],f[N][1<<16];
int n,m,tot;

void dp()
{
	f[m+1][0]=1;

	for(int i=m;i;i--)
		for(int S=0;S<tot;S++)
		{
			int &v=f[i][S];
			v=f[i+1][S];

			int tmp=tot-A[i];

			for(int k=1;k<tot;k<<=1)
			{
				if(!(S&k) || S-k<0)continue;
				inc((ll)f[i+1][S-k]*C(tmp-(S-k),k-1)%MOD*fact[k]%MOD,v);
			}
		}
}

inline int lowbit(int x){return x&(-x);}
inline int bitcnt(int x){int ret=0;for(;x;x^=lowbit(x))ret++;return ret;}

int main()
{
	fact[0]=1;
	for(int i=1;i<L;i++)fact[i]=(ll)fact[i-1]*i%MOD;
	ifact[L-1]=inv(fact[L-1]);
	for(int i=L-1;i;i--)ifact[i-1]=(ll)ifact[i]*i%MOD;

	scanf("%d%d",&n,&m);
	tot=1<<n;
	for(int i=1;i<=m;i++)scanf("%d",A+i);

	dp();

	int ans=0;

	for(int i=0,x;i<tot;i++)
	{
		x=(ll)f[1][i]*fact[tot-i-1]%MOD;
		if(bitcnt(i)&1)inc(-x,ans);
		else inc(x,ans);
	}

	ans=((ll)ans*tot%MOD+MOD)%MOD;

	printf("%d\n",ans);
	return 0;
}


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

lint gcd(lint x, lint y) {
  if(x == 0) { return y; }
  else { return gcd(y%x,x); }
}

lint lcm(lint x, lint y) { return x/gcd(x,y)*y; }


int main() {
  lint n; cin >> n;
  vector<lint> a(n),b(n); for(lint i=0;i<n;i++) { cin >> a[i] >> b[i]; }

  lint ans=0;
  for(lint i=n-1;i>=0;i--) {
    a[i] += ans;
    if(a[i]%b[i] != 0) { ans += (b[i] - a[i]%b[i]); }
  }

  cout << ans << endl;
  return 0;
}

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

signed main(){
  int n;
  cin>>n;
  int A=0,B=0;
  for(int i=0;i<n;i++){
    int x;
    cin>>x;
    if(x&1)A++;
    else B++;
  }
  if(!A || !B)cout<<0<<endl;
  else{
    if(A%2==1)cout<<(n-1)<<endl;
    else cout<<(n-2)<<endl;
  }
}



Measured memory_bytes: 3092
#define _USE_MATH_DEFINES
#include <math.h>
#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <algorithm>
#include <numeric>
#include <stdio.h>
#include <vector>
#include <map>

using namespace std;
typedef long long ll;

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

int main() {

    ll N,K,S;
    cin >> N >> K >> S;
    rep(i,K){
        cout << S;
        if(i!=N-1) cout << " ";
    }
    if(N!=K){
        ll s = S-1;
        if(S==1) s = 2;
        rep(i,N-K){
            cout << s;
            if(i!=N-K-1) cout << " ";
        }
    }
    cout << endl;
    return 0;
}


Measured memory_bytes: 1280
#include<iostream>
#include<cmath>
#define loop(i,a,b) for(int i=a;i<b;i++)
#define rep(i,a) loop(i,0,a)
using namespace std;
typedef long long ll;

int main(){
	ll x,y;
	ll ans=0;
	cin>>x>>y;
	if(x>0 && y>0){
		if(x>y){
			ans+=2;
			ans+=(x-y);
		}else{
			ans+=(y-x);
		}
	}else if(x<0 && y<0){
		if(abs(x)>abs(y)){
			ans+=abs(x)-abs(y);
		}else{
			ans+=2;
			ans+=abs(y)-abs(x);
		}
	}else if(x==0){
		if(y>0)ans+=y;
		else{
			ans++;
			ans+=abs(y);
		}
	}else if(y==0){
		if(x>=0){
			ans++;
			ans+=x;
		}else{
			ans+=abs(x);
		}
	}else if(x>=0 && y<0){
		if(abs(x)>abs(y)){
			ans++;
			ans+=abs(x)-abs(y);
		}else{
			ans++;
			ans+=abs(y)-x;
		}
	}else{
		if(abs(x)>abs(y)){
			ans++;
			ans+=abs(x)-abs(y);
		}else{
			ans++;
			ans+=abs(y)-abs(x);
		}
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define int int64_t
#define REP(i, n) for (int i = 0; (i) < (int)(n); ++ (i))
#define REP3(i, m, n) for (int i = (m); (i) < (int)(n); ++ (i))
#define REP_R(i, n) for (int i = (int)(n) - 1; (i) >= 0; -- (i))
#define REP3R(i, m, n) for (int i = (int)(n) - 1; (i) >= (int)(m); -- (i))
#define REPP(i, n) for (int i = 1; (i) < (int)(n+1); ++ (i))
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define FORP(i, m, n) for(int i = m; i < n+1; i++)
#define FORR(i, a, b) for(int i=(b)-1; i>=(a); i--)
#define ALL(v) v.begin(), v.end()
#define SZ(a) int((a).size())
#define SORT(c) sort((c).begin(),(c).end())
#define SORTR(c) sort((c).begin(),(c).end(),greater<int>());
#define BIT(n) (1LL<<(n))
#define PCNT(x) __builtin_popcountll(x)
#define GCD(x,y) __gcd(x,y)
#define LCM(x,y) x/__gcd(x,y)*y
#define PB push_back
#define MP make_pair
#define endl "\n"
#define pa cout << ans << endl
#define p(x) cout << x << endl
#define pall(x) for(auto iter : x) p(iter)
#define yes cout << "Yes" << endl
#define no cout << "No" << endl
#define yn(x) cout << (x ? "Yes" : "No") << endl
using namespace std;
typedef long double LD;
typedef vector<int> VI;
typedef vector<vector<int> > VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef vector<PII> VPII;
using UnweightedGraph = vector<vector<int> >;
using WeightedGraph = vector<vector<pair<int, int> > >;
const int INF = 2000000000ll;
const long double PI = acosl(-1);
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }



int power(int a, int b) {return b?power(a*a,b/2)*(b%2?a:1):1;}
int perm(int N, int K){
    int x=1;
    for(int i=1;i<=K;i++)
    {
        x=x*(N-i+1);
    }
    return x;
}
int factorial(int N) {return perm(N,N);}
int comb(int N,int K) {return factorial(N)/factorial(K)/factorial(N-K);}
int hcomb(int N, int K) {return comb(N+K-1, N-1);}

int dtoi(double d) {return round(d);}

int isprime(int n) {
    if (n < 2) return 0;
    for (int i = 2; i*i <= n; ++i) {
        if (n % i ==  0) return 0;
    }
    return 1;
}

int mystoll(string S){
    int num = 0;
    for (int i = (int) S.length()-1; i >= 0; i--){
        num += (S[i]-'0') * power(10,S.length()-1-i);
    }
    return num;
}

template<class T>
int SUM(T a) {
    int sum = 0;
    for(auto iter : a) sum += iter;
    return sum;
}

void solve(int n, const vector<int64_t> & a);

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    cout << fixed << setprecision(10);
    // failed to analyze input format
    // TODO: edit here
    int n, k, d, temp, a = 0;
    
    cin >> n >> k;
    VI ans(n,0);
    REP(i,k) {
        cin >> d;
        REP(j,d) {
            cin >> temp;
            temp--;
            ans[temp]++;
        }
    }
    REP(i,n) if(ans[i] == 0) a++;
    p(a);
    return 0;
}



/*
cd ~/Desktop/Programming/AtCoder/contest/abc166/abc166_b && sh test.sh
cd ~/Desktop/Programming/AtCoder/contest/abc166/abc166_b && sh etest.sh
cd ~/Desktop/Programming/AtCoder/contest/abc166/abc166_b && sh submit.sh
*/


Measured memory_bytes: 3672
import java.util.*;
 
class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int a = sc.nextInt();
    int b = sc.nextInt();
    int r = a-b*2;
    if(r<0) r = 0;
    System.out.println(r);
  }
}

Measured memory_bytes: 27056
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define NUM 1000000007
#define MAX 100001
#define INF LLONG_MAX
vector<int> BIT;
void update(int i, int val, int n){
    for(;i<=n;i+=(i&(-i)))
        BIT[i]+=val;
}
int query(int i){
    int sum = 0;
    for(;i>0;i-=(i&(-i)))
        sum+=BIT[i];
    return sum;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n,m,l,r,tmp;
    cin>>n>>m;
    vector<int> v;
    v.pb(0);
    for(int i=0;i<n;i++){
        cin>>tmp;
        v.pb(tmp);
    }
    vector<pair<int,int>> Q[n+1];
    for(int i=0;i<m;i++){
        cin>>l>>r;
        Q[r].push_back({l,i});
    }
    BIT.assign(n+1,0);
    vector<int> lastvis(n+1,0);
    vector<int> ans(m);
    for(int i=1;i<=n;i++){
        if(lastvis[v[i]])
            update(lastvis[v[i]],-1,n+1);
        lastvis[v[i]]=i;
        update(i,1,n+1);
        for(int j=0;j<Q[i].size();j++){
            ans[Q[i][j].second] = query(i)-query(Q[i][j].first-1);
        }
    }
    for(int i=0;i<ans.size();i++)
        cout<<ans[i]<<endl;
    return 0;
}


Measured memory_bytes: 33204
# include "iostream"
# include "cstdio"

using namespace std;

const int maxm=1e5+10;
const int Mod=1e9+7;

int N,head[maxm],tot;
long long DP[maxm][2];
int Father[maxm];

struct edge{
	int To;
	int Next;
	# define To(x) Edge[x].To
	# define Next(x) Edge[x].Next
}Edge[maxm<<1];

inline void Add_Edge(int From,int To){Edge[++tot]=(edge){To,head[From]},head[From]=tot;return;}
inline void Insert_Edge(int x,int y){Add_Edge(x,y),Add_Edge(y,x);return;}

void Dfs(int now){
	DP[now][1]=DP[now][0]=1;
	for(int i=head[now];i;i=Next(i)){
		if(To(i)==Father[now]) continue;
		Father[To(i)]=now;
		Dfs(To(i));
		DP[now][1]=(DP[now][1]*DP[To(i)][0])%Mod;
		DP[now][0]=(DP[now][0]*(DP[To(i)][0]+DP[To(i)][1]))%Mod;
	}
	return;
}

int main(){
	register int i;
	int x,y;
	scanf("%d",&N);
	for(i=1;i<N;i++) scanf("%d%d",&x,&y),Insert_Edge(x,y);
	Dfs(1);
	printf("%lld",(DP[1][0]+DP[1][1])%Mod);
	return 0;
}

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

int main(){
	char seireki[12];
	cin >> seireki;
	if(seireki[0] <= '2' && seireki[1] <= '0' && seireki[2] <= '1' && seireki[3] < '9') cout << "Heisei" << endl;
	else if(seireki[0] == '2' && seireki[1] == '0' && seireki[2] == '1' && seireki[3] == '9' && seireki[5] == '0' && seireki[6] <= '4') cout << "Heisei" << endl;
	else cout << "TBD" << endl;
	return 0;
}


Measured memory_bytes: 256
import java.util.*;
public class Main {
	Scanner in = new Scanner(System.in);
	public static void main(String[] args) {
		new Main();
	}

	public Main() {
		new AOJ1173().doIt();
	}
	
	class AOJ1173{
		
		void solve(){
			char[] text = input.toCharArray();
			ArrayList<Character> list = new ArrayList<Character>();
			boolean sw = true;
			int n = text.length;
			for(int i=0;i<n;i++){
				if(text[i]=='('||text[i]=='[')list.add(text[i]);
				else if(text[i]==')'){
					if(list.size()==0){
						sw = false;break;
					}
					if(list.get(list.size()-1)=='(')list.remove(list.size()-1);
					else{
						sw = false;break;
					}
				}else if(text[i]==']'){
					if(list.size()==0){
						sw = false;break;
					}
					if(list.get(list.size()-1)=='[')list.remove(list.size()-1);
					else{
						sw = false;break;
					}
				}
			}
			if(list.size()>0)sw = false;
			System.out.println(sw? "yes":"no");
		}
		String input;
		void doIt(){
			while(in.hasNext()){
				input = in.nextLine();
				if(input.equals("."))break;
				solve();
			}
		}
	}
	
}

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

#define LL long long
#define VI vector<int>
#define VL vector<long long>
#define FOR(i,a,b) for(int i= (a); i<((int)b); ++i)
#define RFOR(i,a) for(int i=(a); i >= 0; --i)
#define FOE(i,a) for(auto i : a)
#define ALL(c) (c).begin(), (c).end()
#define SIZE(v) (v.size())
#define RALL(c) (c).rbegin(), (c).rend()
#define DUMP(x)  cerr << #x << " = " << (x) << endl;
#define SUM(x) std::accumulate(ALL(x), 0LL)
#define MIN(v) *std::min_element(v.begin(), v.end())
#define MAX(v) *std::max_element(v.begin(), v.end())
#define EXIST(v,x) (std::find(v.begin(), v.end(), x) != v.end())
#define BIT(n) (1LL<<(n))
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end());
#define EPS 1e-14

LL MOD = 1000000007; 

using namespace std;


int main(int argc, char *argv[]) {
    int N, a;
    cin >> N;
    map<int, int> m;
    FOR(_, 0, N) {
        cin >> a; 
        m[a]++;
    }
    
    int num_of_two = 0;
    FOE(p, m) {
        if (p.second > 2) {
            std::cout << 0 << std::endl;
            return 0;
        }
        num_of_two += !(p.second % 2);
    }

    if (N % 2 == 0) {
        for(int i = N - 1; i >= 0; i -= 2) {
            if (m[i] != 2) {
                std::cout << 0 << std::endl;
                return 0;
            }
        }
    }
    else {
        for(int i = N - 1; i >= 0; i -= 2) {
            if (i == 0) {
                if (m[i] != 1) {
                    std::cout << 1 << std::endl;
                    return 0;
                }
            }
            else if (m[i] != 2) {
                std::cout << 0 << std::endl;
                return 0;
            }
        }
    }
    
    LL ans = 1;
    FOR(i, 0, num_of_two) {
        ans *= 2;
        ans %= MOD;
    }
    std::cout << ans << std::endl;
    
    
    return 0;
}

Measured memory_bytes: 3200
#include<iostream>
#include<vector>
#include<stack>
#include<map>
#include<algorithm>
#include<utility>
#include<sstream>
using namespace std;
int main(){
	int a, b;string s, t, u;;cin >> a >> s >> t;
	for (int i = 0; i < a;i++) {
		u += s[i];
		u += t[i];
	}
	cout << u << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <set>
using namespace std;
#define MOD 1000000007

long long add(long long &x, long long y){ x = (x + y) % MOD; }

int main(){
    int N;
    cin >> N;
    vector<int> A(N+1);
    for(int i=1; i<=N; i++)
        cin >> A[i];

    for(int i=1; i<=N; i++)
        A[i] ^= A[i-1];

    vector<int> C(N+1);
    for(int i=1; i<=N; i++)
        if(A[i] == 0)
            C[i] += 1;
    for(int i=1; i<=N; i++)
        C[i] += C[i-1];

    map<int, vector<int>> mp;
    for(int i=1; i<=N; i++)
        mp[A[i]].push_back(i);

    long long ans = 0;
    for(auto &x : mp){
        if(x.first == 0 && A[N] == 0){
            long long tmp = 1;
            for(int i=0; i<x.second.size()-1; i++)
                tmp = (2 * tmp) % MOD;
            add(ans, tmp);
            continue;
        }
        if(A[N] != 0 && x.first != A[N]) continue;

        auto &v = x.second;
        vector<int> vv;
        for(int i=0; i<v.size()-1; i++){
            int tmp = C[v[i+1]] - C[v[i]-1];
            vv.push_back(tmp);
        }
        long long dp0 = 1;
        long long dp1 = 0;
        for(int i : vv){
            add(dp1, dp0);
            add(dp0, (dp1 * i) % MOD);
        }
        if(A[N] == 0)
            add(ans, (dp0 + dp1) % MOD);
        else
            add(ans, dp0);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 36212
#include <cstdio>
#include <iostream>
using namespace std;
#define MAX(a,b) (((a)>(b))?(a):(b))
#define MIN(a,b) (((a)<(b))?(a):(b))
typedef long long LL;
int n,m,a,b;
LL MOD=1000000007;
struct segT{
	LL arr[3000005];
	int l[3000005],r[3000005];
	void Init(int p,int L,int R){
		l[p]=L;
		r[p]=R;
		if(L!=R){
			int m=(L+R)>>1;
			Init((p<<1),L,m);
			Init(((p<<1)|1),m+1,R);
			arr[p]=arr[(p<<1)]*arr[((p<<1)|1)];
			arr[p]%=MOD;
		}
		else {
			arr[p]=(LL)L;
		}
	}
	LL getv(int p,int L,int R){
		if(l[p]>=L && r[p]<=R){
			return arr[p];
		}
		int m=(l[p]+r[p])>>1;
		LL ret=1;
		if(L<=m) ret=getv((p<<1),L,R);
		if(R>m) ret*=getv(((p<<1)|1),L,R);
		ret%=MOD;
		return ret;
	}
}segt;
LL multiply(LL val,int times){
	LL res=1;
	while(times){
		if(times&1) {
			res*=val;
			res%=MOD;
		}
		val*=val;
		val%=MOD;
		times>>=1;
	}
	return res;
}
LL GC(int N,int M){
	if(N<M) return 0;
	if(M==0) return 1;
	LL s1,s2,s3;
	s1=multiply(segt.getv(1,1,MIN(M,N-M)),(int)MOD-2);
	s2=multiply(segt.getv(1,MIN(M,N-M)+1,MAX(M,N-M)),(int)MOD-1);
	s3=multiply(segt.getv(1,MAX(M,N-M)+1,N),(int)MOD);
	s1*=s2;
	s1%=MOD;
	s1*=s3;
	s1%=MOD;
	return s1;
}
LL getv(int xx,int yy,int nn,int mm){
	return GC(nn+mm-xx-yy,mm-yy);
}
int main(){
	scanf("%d%d%d%d",&n,&m,&a,&b);
	int xb,x2;
	segt.Init(1,1,1000000);
	LL res=0;
	for(x2=b;x2<m;x2++){
		res+=getv(0,0,n-a-1,x2)*getv(n-a,x2,n-1,m-1);
		res%=MOD;
	}
	cout<<res<<endl;
	return 0;
}

Measured memory_bytes: 39168
#include <iostream>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <tuple>
#include <bitset>
#include <memory>
#include <cmath>
#include <algorithm>
#include <functional>
#include <iomanip>
#include <numeric>
#include <climits>
#include <cfloat>
#include <random>

int main() {
	int n; std::cin >> n;
	std::vector<int> heights(n); for (auto& h : heights) std::cin >> h;
	std::vector<int> max_length(n, 0);
	for (int i = n - 1; i > 0; --i) {
		if (heights[i] <= heights[i - 1]) {
			max_length[i - 1] = max_length[i] + 1;
		}
	}
	std::cout << *std::max_element(max_length.begin(), max_length.end()) << std::endl;
}


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

ll comb(int a, int b) {
  ll nume = 1, deno = 1;
  rep(i, b) nume *= a - i;
  rep(i, b) deno *= b - i;
  return nume / deno;
}

int main() {
  int N;
  cin >> N;
  vector<string> S(N);
  rep(i, N) {
    string s;
    cin >> s;
    sort(s.begin(), s.end());
    S[i] = s;
  }

  sort(S.begin(), S.end());

  int b = 0, e = 0;
  ll count = 0;
  for (int i = 1; i < N; i++) {
    if (S[b] == S[i]) {
      e++;
    } else {
      int d = e - b + 1;
      count += comb(d, 2);
      b = i;
      e = i;
    }
  }
  int d = e - b + 1;
  count += comb(d, 2);
  cout << count << endl;
}

Measured memory_bytes: 5760