akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define mp make_pair
#define CHECK(x) if(!(x)) return false;
#define CHECKRET(x, y) if(!(x)) return (y);
#define SKIP(x) if((x)) continue;
typedef pair<int, int> pii;

const int MAXN = 110;
int mat[MAXN][MAXN];
int mat2[MAXN][MAXN];
int N;

bool bkt(int line) {
  if (line >= N) {
    return true;
  }
  for (int i = 0, val = 0; i < N; ++i) {
    SKIP(i == line);
    mat[line][val++] = i;
  }
  do {
    bool flag = true;
    for (int j = 0; j < N - 1 && flag; ++j) {
      int X = mat[line][j];
      if (X <= line && mat[X][j] == line) flag = false;
    }
    SKIP(!flag);
    if (bkt(line + 1)) return true;
  } while (next_permutation(mat[line], mat[line] + N - 1));
  return false;
}

int mainbkt() {
  //freopen("fis.out", "w", stdout);
  for (N = 2; N <= 12; ++N) {
    printf("Now solving for %d...\n", N);
    if (!bkt(0)) {
      puts("-1\n");
      continue;
    }
    for (int i = 0; i < N; ++i) {
      for (int j = 0; j < N - 1; ++j)
        printf("%d ", mat[i][j]);
      puts("");
    }
    puts("");
  }
  return 0;
}

int main() {
  scanf("%d", &N);
  if (N <= 2) {
    puts("-1");
    return 0;
  }
  int swidx = 0;
  for (int line = 0; line < N; ++line) {
    for (int i = 0, val = 0; i < N; ++i) {
      SKIP(i == line);
      mat2[line][val++] = i;
    }
    if (line % 2 == 1) {
      if (swidx + 1 < N - 1)
        swap(mat2[line][swidx], mat2[line][swidx + 1]);
      swidx += 2;
    }
  }
  if (N % 2 == 0) {
    swap(mat2[N - 2][N - 2], mat2[N - 2][N - 3]);
  }
  for (int i = 0; i < N; ++i) {
    for (int j = 0; j < N - 1; ++j)
      printf("%d ", mat2[i][j] + 1);
    puts("");
  }
  /*
  bkt(0);
  for (int i = 0; i < N; ++i)
    for (int j = 0; j < N - 1; ++j) {
      if (mat[i][j] != mat2[i][j]) {
        printf("%d %d\n", i, j);
        assert(0);
      }
    }
    */
  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define maxn 1000119
int num[maxn],tree[maxn],booll[maxn],nnn[maxn],N,ww;;
//numÊý×é±£´æÔ­ÊýÁÐ£¬treeÊ÷×´Êý×é£¬nnn±£´æ½á¹û
struct tt
{
    int l,r;//×óÓÒ±ß½ç
    int pos;//Ô­Î»ÖÃ£¨ÒòÎªÎÒÃÇÒªÀëÏßÅÅÐòºó´¦Àí£©
};
tt ask[maxn];
bool cmp(tt x,tt y)
{ 
    return x.r<y.r;
    //¿ìÅÅ´ó·¨ºÃ£¬Ã»ÓÐÊ²Ã´ÊÇ¿ìÅÅ½â¾ö²»À´Å¶
    //ÊµÔÚ²»ÐÐ¾Í¼ÓÉÏÒ»¸öcmp
}
int lowbit(int n) 
{
    return n&(-n);
    //Ê÷×´Êý×éºËÐÄ²Ù×÷¡Á1
}
void add(int n,int now)
{
    while(n<=N)
    {
        tree[n]+=now;
        n+=lowbit(n);
    }
    //Ê÷×´Êý×éºËÐÄ²Ù×÷¡Á2-->¸üÐÂ²Ù×÷
}
int sum(int n)
{
    int ans=0;
    while(n!=0)
    {
        ans+=tree[n];
        n-=lowbit(n);
    }
    return ans;
    //Ê÷×´Êý×éºËÐÄ²Ù×÷¡Á3¡ª¡ª¡ª>²éÑ¯²Ù×÷
}
int main()
{
	//freopen("1.in","r",stdin);
        scanf("%d",&N);scanf("%d",&ww);
        for(int i=1;i<=N;i++)
            scanf("%d",&num[i]);
        
        for(int i=1;i<=ww;i++)
        {
            scanf("%d%d",&ask[i].l,&ask[i].r);
            ask[i].pos=i; 
        }
        sort(ask+1,ask+1+ww,cmp);
        int next=1;
        for(int i=1;i<=ww;i++)
        {
            for(int j=next;j<=ask[i].r;j++)
            {
                if(booll[num[j]]) 
                    add(booll[num[j]],-1);
                add(j,1);
                booll[num[j]]=j;
            }
            next=ask[i].r+1;
            nnn[ask[i].pos]=sum(ask[i].r)-sum(ask[i].l-1);
        }
    for(int i=1;i<=ww;i++)
      cout<<nnn[i]<<endl;
    return  0;
}

Measured memory_bytes: 17440
#include <iostream>
using namespace std;
int main() {
 int n; cin >> n;
 int a[n];
 for (int i = 0; i < n; i++) cin >> a[i];
 int ans = 0;
 for (int i = 0; i < n; i++) for (int j = i + 1; j < n; j++) ans += a[i] * a[j];
 cout << ans << endl;
 return 0;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main(void){
    int d , a, b;
    cin >> d >> a >> b;
    if (b <= a) {
        cout << "delicious";
    } else if (b <= a + d) {
        cout << "safe";
    } else if (b > a + d) {
        cout << "dangerous";
    }
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <stack>
#include <queue>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <algorithm>

#include <cstdio>

using namespace std;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define repc(i, s, n) for (int i = (s); i <= (n); i++)
#define rrep(i, n) for (int i = (n) - 1; i >= 0; i--)
#define rrepc(i, s, n) for (int i = (s); i >= (n); i--)
typedef long long ll;
typedef unsigned long long ull;


vector<int> DAG[10000];
vector<int> ans;
bool done[10000] = { false };
int indeg[10000] = { 0 };

int main()
{
	int V, E;
	int s, t;
	queue<int> Q;

	cin >> V >> E;
	rep(i, E) {
		cin >> s >> t;
		DAG[s].push_back(t);
		indeg[t]++;
	}

	rep(i, V) {
		if (indeg[i] == 0 && !done[i]) {
			Q.push(i);

			while (!Q.empty()) {
				s = Q.front(); Q.pop();
				done[s] = true;
				ans.push_back(s);

				rep(j, DAG[s].size()) {
					t = DAG[s][j];
					indeg[t]--;

					if (indeg[t] == 0 && !done[t]) {
						Q.push(t);
					}
				}
			}
		}
	}

	rep(i, ans.size()) cout << ans[i] << endl;

	return 0;
}


Measured memory_bytes: 3944
#include <iostream>
#include <cmath>

using namespace std;


bool prime[50000];

int main() {

  int n;

  int count;


  prime[0]=prime[1]=false;

  for(int i=2;i<=50000;i++) prime[i]=true;

  for(int i=2;i<=sqrt(50000);i++) {

    if(prime[i]==true) {

      for(int j=2*i;j<=50000;j+=i) prime[j]=false;

    }

  }

  while(cin >> n,n) {

    count=0;

    for(int i=0;i<=n/2;i++) {

      if(prime[i]==true && prime[n-i]==true) count++;

    }

    cout << count << endl;

  }

  return 0;

}

Measured memory_bytes: 0
H, W, K = map(int,input().split())

c = []
answer = 0
for i in range(H):
    c.append(input())

for i in range(2**H):
    for j in range(2**W):
        count = 0
        for m in range(H):
            for n in range(W):
                if ((i >> m) & 1) and ((j >> n) & 1) and c[m][n] == '#':
                    count = count + 1
        if count == K:
            answer = answer + 1

print(answer)


Measured memory_bytes: 9060
#include <stdio.h>
int main(void)
{
    int n,i,a[1100];
    scanf("%d",&n);
    for(i=0;i<n;i++){
        scanf("%d",&a[i]);
    }
    for(i=0;i<n;i++){
        if(a[i]%2==0&&a[i]%3!=0&&a[i]%5!=0){
            printf("DENIED");
            break;
        }
    }
    if(i>=n)
        printf("APPROVED");
    return 0;
}

Measured memory_bytes: 128
import java.io.*;
import java.util.*;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(in.readLine());
        int n = Integer.parseInt(st.nextToken());
        int a = Integer.parseInt(st.nextToken())*n;
        int b = Integer.parseInt(st.nextToken());
        System.out.println(Math.min(a, b));
    }

}
/*

 */

Measured memory_bytes: 21204
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>

#define REP(i, m, n) for(int i=int(m);i<int(n);i++)
#define EACH(i, c) for (auto &(i): c)
#define all(c) begin(c),end(c)
#define EXIST(s, e) ((s).find(e)!=(s).end())
#define SORT(c) sort(begin(c),end(c))
#define pb emplace_back
#define MP make_pair
#define SZ(a) int((a).size())

//#define LOCAL 0
//#ifdef LOCAL
//#define DEBUG(s) cout << (s) << endl
//#define dump(x)  cerr << #x << " = " << (x) << endl
//#define BR cout << endl;
//#else
//#define DEBUG(s) do{}while(0)
//#define dump(x) do{}while(0)
//#define BR
//#endif


//改造
typedef long long int ll;
using namespace std;
#define INF (1 << 20)
#define INFl (ll)5e15
#define DEBUG 0 //デバッグする時1にしてね

//ここから編集する
class UnionFind {
    vector<int> p;//p[i]はiの属する組織
public:
    UnionFind(int n) {
        p = vector<int>(n);
        for (int i = 0; i < n; i++) {
            p[i] = i;
        }
        return;
    }

    void printState() {
        if (DEBUG) {
            cout << "---" << endl;
            for (int i = 0; i < p.size(); i++) {
                printf("%dの親は%d\n", i, p[i]);
            }
            cout << "---" << endl;
        }
    }

/* xの属する集合を返す */
    int find(int x) {
        if (p[x] == x) return x;
        return p[x] = find(p[x]);
    }

/* yにxを統合する */
    void unite(int x, int y) {
        p[find(x)] = p[find(y)];
    }

/* xとyが属する集合が同じかを判定する */
    bool same(int x, int y) {
        return find(x) == find(y);
    }

};

int main() {
    int N, M;
    cin >> N >> M;
    vector<pair<int, int> > e(M);
    REP(i, 0, M) {
        int a, b;
        cin >> a >> b;
        a--;
        b--;
        e[i] = make_pair(a, b);
    }

    int ans = 0;
    REP(i, 0, M) {
        UnionFind u(N);
        REP(j, 0, M) {
            if (i != j) {
                u.unite(e[j].first,e[j].second);
            }
        }

        REP(j,0,N-1){
            if(!u.same(j,j+1)){
                ans++;
                break;
            }
        }
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 256
import java.util.*;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String s = sc.next();
		sc.close();
		if (s.equals("ABC")) {
			System.out.println("ARC");
		} else {
			System.out.println("ABC");
		}
	}
}


Measured memory_bytes: 35624
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#define MOD 1000000007
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;

typedef pair<int, int> P;
typedef pair<long long, long long> LLP;

int main() {
    int A, B;
    cin >> A >> B;
    cout << max(A - 2 * B, 0) << endl;
    
    return 0;
}

Measured memory_bytes: 256
#!/usr/bin/env python3
import sys
from datetime import datetime as dt

def solve(S: str):
    p = '%Y/%m/%d'
    base = dt.strptime('2019/04/30', p)
    sd = dt.strptime(S, p)
    print('Heisei' if sd <= base else 'TBD')
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    S = next(tokens)  # type: str
    solve(S)

if __name__ == '__main__':
    main()


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

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<int, pii> pipii;
typedef pair<pii, int> piipi;
typedef pair<pii, pii> piipii;
typedef pair<ll, ll> pll;

#define mp make_pair
#define fi first
#define se second
#define all(a) (a).begin(), (a).end()
#define sz(a) (int)(a).size()
#define eb emplace_back

int X[100005], Y[100005];
bool vis[100005];
multiset<piipi> dx, dy;
ll d;
void dfs(int u){
    vis[u] = 1;
    dx.erase(mp(mp(X[u], Y[u]), u));
    dy.erase(mp(mp(Y[u], X[u]), u));

    while(1){
        auto it = dx.lower_bound(mp(mp(X[u]-d, Y[u]-d), 0));
        if(it != dx.end() && it->fi.fi == X[u]-d && it->fi.se <= Y[u]+d) dfs(it->se);
        else break;
    }
    while(1){
        auto it = dx.lower_bound(mp(mp(X[u]+d, Y[u]-d), 0));
        if(it != dx.end() && it->fi.fi == X[u]+d && it->fi.se <= Y[u]+d) dfs(it->se);
        else break;
    }
    while(1){
        auto it = dy.lower_bound(mp(mp(Y[u]-d, X[u]-d), 0));
        if(it != dy.end() && it->fi.fi == Y[u]-d && it->fi.se <= X[u]+d) dfs(it->se);
        else break;
    }
    while(1){
        auto it = dy.lower_bound(mp(mp(Y[u]+d, X[u]-d), 0));
        if(it != dy.end() && it->fi.fi == Y[u]+d && it->fi.se <= X[u]+d) dfs(it->se);
        else break;
    }
}
int main(){
    int n, a, b, x, y;
    scanf("%d%d%d", &n, &a, &b);
    for(int i=1;i<=n;i++){
        scanf("%d%d", &x, &y);
        X[i] = x+y;
        Y[i] = x-y;
        dx.insert(mp(mp(X[i], Y[i]), i));
        dy.insert(mp(mp(Y[i], X[i]), i));
    }

    d = max(abs(X[a]-X[b]), abs(Y[a]-Y[b]));
    dfs(a);

    vector<pll> v1, v2;
    for(int i=1;i<=n;i++){
        if(vis[i]){
            v1.eb(mp(X[i], Y[i]));
            v2.eb(mp(Y[i], X[i]));
        }
    }
    sort(all(v1));
    sort(all(v2));
    ll ans = 0;
    for(int i=1;i<=n;i++){
        if(vis[i]){
            ans += (upper_bound(all(v1), mp(X[i]-d, Y[i]+d)) - v1.begin()) - (lower_bound(all(v1), mp(X[i]-d, Y[i]-d+1)) - v1.begin());
            ans += (upper_bound(all(v1), mp(X[i]+d, Y[i]+d)) - v1.begin()) - (lower_bound(all(v1), mp(X[i]+d, Y[i]-d+1)) - v1.begin());
            ans += (upper_bound(all(v2), mp(Y[i]-d, X[i]+d)) - v2.begin()) - (lower_bound(all(v2), mp(Y[i]-d, X[i]-d)) - v2.begin());
            ans += (upper_bound(all(v2), mp(Y[i]+d, X[i]+d-1)) - v2.begin()) - (lower_bound(all(v2), mp(Y[i]+d, X[i]-d+1)) - v2.begin());
        }
    }
    printf("%lld\n", ans/2);
}

Measured memory_bytes: 26552
#include <algorithm>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <functional>
#include <iostream>
#include <map>
#include <memory>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>

using namespace std;

typedef long long ll;

#define sz size()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define all(c) (c).begin(), (c).end()
#define rep(i,a,b) for(ll i=(a);i<(b);++i)
#define per(i,a,b) for(ll i=b-1LL;i>=(a);--i)
#define clr(a, b) memset((a), (b) ,sizeof(a))
#define ctos(c) string(1,c)
#define print(x) cout<<#x<<" = "<<x<<endl;

#define MOD 1000000007

ll d[60][300100];

int main(){
  clr(d,0);
  ll n;
  cin>>n;
  vector<ll> v;
  rep(i,0,n){
    ll a;
    cin>>a;
    v.pb(a);
    rep(j,0,60){
      d[j][i] = (a>>j)&1;
    }
  }
  rep(i,0,60){
    per(j,0,n-1){
      d[i][j] += d[i][j+1];
    }
  }
  ll ans = 0;
  rep(i,0,60){
    rep(j,0,n){
      ll a = (v[j]>>i)&1;
      ll b0 = (n-j)-d[i][j];
      ll b1 = d[i][j];
      if(a==0)b0--;
      if(a==1)b1--;
      if(a==1)swap(b0,b1);
      ans += ((ll)pow(2,i)%MOD)*b1;
      ans %= MOD;
    }
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 147184
#include <algorithm>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <map>
#include <math.h>
#include <set>
#include <stdio.h>
#include <string>
#include <utility>
#include <vector>
using namespace std;

/*
class BIT {
public:
  int n;
  vector<int> bit;
  BIT(int n_) {
    n = n_;
    bit.resize(n + 1);
  }
  void add(int a, int w) {
    a += 1;
    if (a == 0 || a > n)
      return;
    for (int x = a; x <= n; x += x & -x)
      bit[x] += w;
  }
  int sum(int a) {
    a += 1;
    if (a == 0)
      return 0;
    int ret = 0;
    for (int x = a; x > 0; x -= x & -x)
      ret += bit[x];
    return ret;
  }
  // [l, r]
  int q(int l, int r) { return sum(r) - sum(l - 1); }
};
*/

int n, k, q;
vector<long long> a;

bool f(long long x, long long y) {
  vector<long long> c;
  int d = 0;
  for (int i = 0; i < n; i++) {
    if (a[i] >= x)
      c.push_back(a[i]);
    else {
      if (c.size() < k) {
        c.clear();
        continue;
      }
      sort(c.begin(), c.end());
      auto it = upper_bound(c.begin(), c.end(), x + y);
      if (it != c.begin()) {
        it--;
        d += min((int)(it - c.begin() + 1), (int)(c.size() - k + 1));
      }
      c.clear();
    }
  }
  if (c.size() >= k) {
    sort(c.begin(), c.end());
    auto it = upper_bound(c.begin(), c.end(), x + y);
    if (it != c.begin()) {
      it--;
      d += min((int)(it - c.begin() + 1), (int)(c.size() - k + 1));
    }
  }
  //  cerr << x << " " << y << " " << d << " " << q << " " << endl;
  return d >= q;
}

int main() {
  cin >> n >> k >> q;
  a.resize(n);

  for (int i = 0; i < n; i++)
    cin >> a[i];
  vector<long long> b = a;
  sort(b.begin(), b.end());

  long long ans = 1000000001;

  for (int i = 0; i < n - q + 1; i++) {
    long long minS = 1000000001, maxS = -1;
    while (minS - maxS > 1) {
      int s = (maxS + minS) / 2;
      if (f(b[i], s)) {
        minS = s;
      } else {
        maxS = s;
      }
    }
    ans = min(ans, minS);
  }
  cout << ans << endl;
  return 0;
}


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

int main(){
  int n;
  cin >> n;
  vector<int> h(n);
  for(int i=0;i<n;i++)
    cin >> h.at(i);
  
  int k=0;
  
  for(int i=0;i<n-1;i++){
    int x=0;
    while(i<n-1&&h.at(i)>=h.at(i+1)){
      x++;
      i++;
    }
    k=max(k,x);
  }
    cout << k << endl;
}

Measured memory_bytes: 640
n = int(input())
c = input()

lw, rr = [0]*(n+1), [c.count('R')]*(n+1)
for i in range(n):
    lw[i+1] = lw[i] + (c[i] == 'W')
    rr[i+1] = rr[i] - (c[i] == 'R')


def operation(left_white, right_red):
    swap = min(left_white, right_red)
    white_to_red, red_to_white = max(0, left_white-swap), max(0, right_red-swap)
    return swap + white_to_red + red_to_white


print(min(operation(white, red) for white, red in zip(lw, rr)))


Measured memory_bytes: 24928
n = int(input())
A = list(map(int,input().split()))
B = []
for i in A:
    if (int(i)%2 == 0):
        B.append(int(i))

for j in B:
    if (int(j)%3 == 0 or int(j)%5 == 0):
        pass
    else:
        print('DENIED')
        exit()
print('APPROVED')

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

#define REP(i,n) for(int i=0; i < (n); ++i)
#define REPR(i,n) for(int i=(n); i >=0; --i)
#define FOR(i, m, n) for(int i = (m); i < (n); ++i)

typedef long long ll;
#define INF 1e9

int main(){
  int N;
  cin >> N;
  ll ans = 0, cntAB = 0, cntA = 0, cntB = 0;
  vector<string> s(N);
  REP(i, N){
    cin >> s[i];
  }

  REP(i, N){
    REP(j,s[i].length()-1){
      if(s[i][j] == 'A' && s[i][j+1] == 'B'){
        ans++;
      }
    }
  }

  REP(i, N){
    if(s[i][0] == 'B' && s[i][s[i].length()-1] == 'A'){
      cntAB++;
    }
    else if(s[i][0] == 'B'){
      cntB++;
    }
    else if(s[i][s[i].length()-1] == 'A'){
      cntA++;
    }
  }

  if(cntAB == 0){
    ans += min(cntA, cntB);
  }
  else if(cntA == 0 && cntB == 0){
    ans += cntAB-1;
  }
  else if(cntA == 0 || cntB==0){
    ans += cntAB;
  }
  else{
    cntA--, cntB--;
    ans += cntAB+1+min(cntA, cntB);
  }
  cout << ans << endl;
  // cout << "cntAB:" << cntAB << endl;
  // cout << "cntA:" << cntA << endl;
  // cout << "cntB:" << cntB << endl;

  return 0;
}

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

#define rep(l, r) for (int i = (l); i < (r); i++)

typedef long long ll;
 
using namespace std;

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

    cout << (t / a * b) << endl;

    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <tuple>
#include <utility>
#include <set>
using namespace std;
using LLI = long long int;




int main(int argc, char *argv[])
{
    // BASE VARIABLES
    int H, W;
    vector<string> S;

    // INPUT
    cin >> H >> W;
    for (int i=0; i<H; i++){
        string line;
        cin >> line;
        S.push_back(line);
    }

    // PROC
    vector<vector<int>> A(H, vector<int>(W, -10000));
    vector<vector<int>> B(H, vector<int>(W, -10000));
    for (int i=0; i<H; i++) {
        int jj=0;
        int s = 0;
        for (int j=0; j<W+1; j++) {
            if (j == W || S[i][j] == '#') {
                for (int k=jj; k<j; k++) {
                    A[i][k] = s;
                }
                s = 0;
                jj = j + 1;
            } else {
                s++;
            }
        }
    }

    for (int j=0; j<W; j++) {
        int ii=0;
        int s = 0;
        for (int i=0; i<H+1; i++) {
            if (i == H || S[i][j] == '#') {
                for (int k=ii; k<i; k++) {
                    B[k][j] = s;
                }
                s = 0;
                ii = i + 1;
            } else {
                s++;
            }
        }
    }

    int m = 0;
    for (int i=0; i<H; i++) {
        for (int j=0; j<W; j++) {
            m = max(A[i][j] + B[i][j] - 1, m);
        }
    }

    // OUTPUT
    cout << m << endl;
    
    return 0;   
}

Measured memory_bytes: 35840
import sys
stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

n,k =na()
h =na()
h = sorted(h)

import bisect

m = bisect.bisect_left(h,k)
print(n-m)

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

int N;
vector<int> D;
int M;
vector<int> T;

map<int, int> mapd, mapt;

int main(void)
{
  cin >> N;
  for(int i = 0; i < N; i++){
    int t;
    cin >> t;
    D.push_back(t);
    mapd[t]++;
  }
  cin >> M;
  for(int i = 0; i < M; i++){
    int t;
    cin >> t;
    T.push_back(t);
    mapt[t]++;
  }
  for(int i = 0; i < M; i++){
    if(mapd[T[i]] < mapt[T[i]]){
      printf("NO\n");
      return 0;
    }
  }

  printf("YES\n");
  return 0;  
}


Measured memory_bytes: 20596
<?php
$n = trim(fgets(STDIN));
$input = explode(' ',trim(fgets(STDIN)));
$count = 0;
$start = 0;

while(1) {
  $flag = 0;
  for($i = $start; $i < $n; $i++) {
    if($input[$i] % 2 == 0) {
      $input[$i] = $input[$i] / 2;
      $count++;
      break;
    }
    $start = $i + 1;
  }
  if($i == $n) break;
}
echo "$count\n";
?>


Measured memory_bytes: 4856
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
int main(){
    int a,b,k; cin>>a>>b>>k;
    rep(i,a+1)rep(j,b+1)if(i*j+(a-i)*(b-j)==k)return puts("Yes")*0;
    return puts("No")*0;
}


Measured memory_bytes: 256
#include <iostream>
#include <map>

int main() {
  std::map<char, char> ATGC = {
    {'A', 'T'},
    {'T', 'A'},
    {'G', 'C'},
    {'C', 'G'}
  };
  char s;
  std::cin >> s;
  std::cout << ATGC.at(s) << std::endl;
  return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cctype>
#include <climits>
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <string>
#include <sstream>
#include <vector>
#include <map>
#include <set>
#include <complex>
#include <functional>
#include <utility>
#include <iterator>

#define REP(i, n) for(int i = 0; i < (int)(n); ++i)
#define FOR(i, m, n) for(int i = (m); i < (int)(n); ++i)
#define ALL(x) (x).begin(), (x).end()
#define INF 2000000000

#ifdef LOCAL
  #define dprintf(...) fprintf(stdout, __VA_ARGS__)
#else
  #define dprintf(...) 0
#endif

using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
typedef unsigned int uint;

//const double PI = 3.1415926535897932384626433832795;

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

  int ans = 0;
  REP(i, 3) {
    if(s[i] == t[i]) {
      ans++;
    }
  }

  cout << ans << '\n';

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
using P = pair<int, int>;
using vec = vector<int>;
using mat = vector<vector<int>>;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(v) v.begin(), v.end()
#define endl "\n"

constexpr int MOD = 1000000007;
const int INF = 1 << 30;

lint choose2(lint n) {
    return n * (n-1) / 2;
}

int main() {
    int n, m;
    cin >> n >> m;
    vec a(n);
    rep(i, n) cin >> a[i];

    vector<lint> s(n+1);
    rep(i, n) s[i+1] = (s[i] + a[i]) % m;

    map<int, int> mp;
    rep(i, n+1) mp[s[i]]++;

    lint res = 0;

    for (auto&& p : mp) {
        lint v = p.second;
        res += choose2(v);
    }

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

Measured memory_bytes: 4352
m,a[7][2];
//M(int*a){return*1[&a]-*a;}
M(int*a,int*b){return*b-*a;}
C(b,n){
	int c=0,i;
	if(b==m)
		return n==0;
	for(i=0;i<=a[b][1]&&i*a[b][0]<=n;i++)
		c+=C(b+1,n-i*a[b][0]);
	return c;
}
main(){
	int i,g,n;
	for(;scanf("%d",&m),m;){
		for(i=0;i<m;i++)
			scanf("%d%d",&a[i][0],&a[i][1]);
		qsort(a,m,sizeof(*a),M);
		scanf("%d",&g);
		for(;g--;){
			scanf("%d",&n);
			printf("%d\n",C(0,n));
		}
	}
	exit(0);
}

Measured memory_bytes: 420
def main():
    import math

    def is_prime(n):
        if n == 1:
            return False

        for k in range(2, int(math.sqrt(n)) + 1):
            if n % k == 0:
                return False

        return True

    q = int(input())
    scope = [tuple(map(int, input().split())) for _ in range(q)]
    prime_cnt = [0] * (10 ** 5 + 1)
    for i in range(1, 10 ** 5 + 1):
        prime_cnt[i] = prime_cnt[i - 1]
        if ((i + 1) / 2) % 1 == 0 and is_prime(i) and is_prime((i + 1) / 2):
            prime_cnt[i] += 1

    for i in range(q):
        left = scope[i][0]
        right = scope[i][1]
        print(prime_cnt[right] - prime_cnt[left - 1])


if __name__ == '__main__':
    main()

Measured memory_bytes: 18144
#include <unistd.h>
#include <cctype>
#include <cstdio>
#define REP(i, n) for (int i = 0; (i) < (int)(n); ++ (i))

int input() {
    char buf[6];
    int size = read(0, buf, 6);
    int n = 0;
    REP (i, 5) {
        n = n * 10 + buf[i] - '0';
    }
    return n;
}
void output(int n) {
    char buf[20];
    char *s = buf + sizeof buf;
    *(-- s) = '\n';
    if (not n) *(-- s) = '0';
    for (; n; n /= 10) {
        *(-- s) = (n % 10) + '0';
    }
    write(1, s, buf + sizeof buf - s);
}

int main() {
    int a = input();
    int b = input();
    int cnt = 0;
    REP (x, 10) REP (y, 10) REP (z, 10) {
        int n = x * 10000 + y * 1000 + z * 100 + y * 10 + x;
        cnt += (a <= n and n <= b);
    }
    output(cnt);
    return 0;
}


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

using namespace std;
using int64 = long long;

constexpr int DEBUG = 0;

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

  string s;
  cin >> s;
  int n = s.length();
  int c = 0;
  for (int i = 0; i < n - 1 - i; i++) {
    if (s[i] != s[n - 1 - i]) c++;
  }
  cout << c << endl;
}

Measured memory_bytes: 256
n = input()
k = int(input())

l = len(n)
n = int(n)

ans=0

def one(n):
    l = len(str(n))
    ans = 9 * (l-1)
    ans += n//(10**(l-1))
    return ans

def two(n):
    l = len(str(n))
    ans = 0
    if l == 1:
        return 0
    elif l == 2:
        ans = (n//10-1) *9 + n%10
        return ans
    else:
        ans +=   81 * (l-1) * (l-2) // 2
        # print(81*5*4/2)
        # print(ans)
        t = n % (10**(l-1))
        ans += one(t) + one(10**(l-1)-1)* (n// (10**(l-1))-1)
        return ans

def three(n):
    l = len(str(n))
    ans = 0
    if l <= 2:
        # print(n)
        return ans
    elif l == 3:
        ans = (n//100-1) * two(99) + two( n % 100 )
        return  ans
    else:
        ans = 729 * (l-1) * (l-2) * (l-3) // 6
        t = n % (10**(l-1))
        ans += two(t) + two(10**(l-1)-1)* (n// (10**(l-1))-1)
        return ans
    return ans

if k == 1:
    ans = one(n)
if k == 2:
    ans = two(n)
if k == 3:
    ans = three(n)

if l <= 3 and n != one(n) + two(n) + three(n):
    print(one(n),two(n),three(n))
    print("Error!")

print(ans)

# 100000 ~ 314159 

# print()

# n=9 k=1:9
# n=99 k=1:18 k=2:81=81*2C2
# n=999 k=1:27 k=2:81*3=243,81*(3C2) k=3:9^3=729 = 729*3C3
# n=9999 k=1:9*4, k=2:81*4C2, K=3:729*4C3=

# k=2, 1,2,6,10,15,

# n=515 nの桁数:d=3 10^(d-1)=100 515/100=5 100,200,300,400,500 18+5=23
# n=515, k=2:101~109,110,120,130~190,201~209
# n=250,18,
# k=2,1001-1009,1010,1020...1090,1100,1200..1900 27*9=243
# k=2を求めるよりも、k<=2を求めてからk=1を求める方が簡単か? そんなこともないか

Measured memory_bytes: 3188
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		long H = sc.nextLong();
		sc.close();
		long cnt = 0;
		while(H > 0){
			H /= 2;
			cnt++;
		}
		System.out.println((long)Math.pow(2, cnt) - 1);

	}

}

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

using namespace std;


map<string,int>cjt;
int main(){
    int a;
    string s;
    cin>>a;
    for (int i = 0; i < a; i++)
    {
        cin>> s;
        cjt[s]++;
    }
    int maxx;

    for(auto &x : cjt){
        int v = x.second;

        if( v > maxx) maxx = v;
    }
    
    for (auto it = cjt.begin(); it != cjt.end(); ++it){
        if(it->second == maxx) cout<<it->first<<"\n";

    }

    
    

    
    
    

    return 0;
}

Measured memory_bytes: 25216
using System;
using System.Linq; 

namespace Sample
{
  class Sample
  {
    static void Main(string[] args)
    {
	int N=int.Parse(Console.ReadLine());
    string[] str=Console.ReadLine().Split(' ');
      int[] input=new int[N];
      for(int i=0;i<N;i++){
        input[i]=int.Parse(str[i]);
      }
      int a=0;
      int b=0;
      Array.Sort(input);
      Array.Reverse(input);
      for(int j=0;j<N;j++){
        
        if(j%2==0){
          a+=input[j];
        }else{
          b+=input[j];
        }       
      }
      Console.WriteLine(a-b);
      
    }
    
  }

}

Measured memory_bytes: 27384
#include <bits/stdc++.h>
using namespace std;
const int INF = INT_MAX;

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

    vector<vector<int>> f(n,vector<int>(10)), p(n,vector<int>(11));
    for(int i=0; i<n; i++){
        for(int j=0; j<10; j++){
            cin >> f[i][j];
        }
    }
    for(int i=0; i<n; i++){
        for(int j=0; j<11; j++){
            cin >> p[i][j];
        }
    }

    int ans = -INF;
    for(int bit = 1; bit < (1<<10); bit++){// 1, 2, ..., 2^10 -1
        int profit = 0;
        for(int i=0; i<n; i++){// store
            int c = 0;
            for(int j=0; j<10; j++){// time
                if(bit & (1<<j)) c += f[i][j];
            }
            profit += p[i][c];
        }
        ans = max(ans, profit);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <set>
#include <cmath>
#include <string>

using namespace std;

int a,b;
unsigned char m[100][100] = {0};

int main(void) {
    cin >> a >> b;
    for(int i = 0;i < 50;i++) {
        for(int ii = 0;ii < 100;ii++) {
            m[i][ii] = 0;
            m[i+50][ii] = 1;
        }
    }
    for(int i = 0;i < b-1;i++) {
        m[(i / 50) * 2][(i % 50) * 2] = 1;
    }
    for(int i = 0;i < a-1;i++) {
        m[(i / 50) * 2 + 51][(i % 50) * 2] = 0;
    }
    cout << "100 100" << endl;
    for(int i = 0;i < 100;i++) {
        for(int ii = 0;ii < 100;ii++) {
            if(m[i][ii] == 0)
                cout << ".";
            else
                cout << "#";
        }
        cout << endl;
    }
    return 0;
}


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

llong N, x;
vector<llong> a(51); //a[i] = レベルiバーガーの層数
vector<llong> p(51);

llong rec(llong L, llong X) { //レベルLバーガーの下からX層でパティが含まれる枚数
    if (L == 0) return (X <= 0) ? 0 : 1;
    if (X <= 1) return 0ll;
    if (X <= a[L-1]+1) return rec(L-1, X-1);
    else return p[L-1] + 1 + rec(L-1, X-2-a[L-1]);
}

int main() {
    cin >> N >> x;
    a[0] = 1; p[0] = 1;
    for (int i = 0; i < 50; i++) {
        a[i+1] = 2*a[i] + 3;
        p[i+1] = 2*p[i] + 1;
    }
    cout << rec(N,x) << endl;
    return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <algorithm>
using namespace std;
int N,X,Y,ans[2005];
int main() {
    scanf("%d%d%d",&N,&X,&Y);
    for (int i = 1;i <= N;i++) for (int j = i + 1;j <= N;j++)
        ans[min(j - i,abs(j - Y) + abs(X - i) + 1)]++;
    for (int i = 1;i < N;i++) printf("%d\n",ans[i]);
}


Measured memory_bytes: 128
// lcmとか__builtin_popcountとかはg++ -std=c++17 default.cppみたいなかんじで
#include <bits/stdc++.h>
#define mod 1000000007
#define INF LLONG_MAX
#define ll long long
#define ln cout<<endl
#define Yes cout<<"Yes"<<endl
#define NO cout<<"NO"<<endl
#define YES cout<<"YES"<<endl
#define No cout<<"No"<<endl
#define REP(i,m,n) for(ll i=(ll)(m);i<(ll)(n);i++)
#define rep(i,n) REP(i,0,n)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
using namespace std;
ll dx[4]={1,0,-1,0};
ll dy[4]={0,1,0,-1};
int main() {
    cin.tie(0);
   	ios::sync_with_stdio(false);
 
    ll a,b,c,d,m,n,maxi=0,f=0,mini=INF,sum=0;
    string str;
    ll k;
    ll w,x;
    cin>>a>>d>>x;
    rep(i,10){
        x=x*a-d;
        cout<<x<<endl;
    }

    return 0;
}


Measured memory_bytes: 3592
#include <stdio.h>

int gcd(int x, int y){
	int ans;
	if(x == 0){
		return y;
	}else if(y == 0){
		return x;
	}else if(x > y){
		ans = gcd(y, x % y);
	}else{
		ans = gcd(x, y % x);
	}
	return ans;
}

int main(void){
	int x, y;
	scanf("%d %d", &x, &y);
	printf("%d\n", gcd(x, y));
	return 0;
}

Measured memory_bytes: 1020
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ABC120 {
	class ABC120_A {
		static void Main(string[] args) {
			var input = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
			var A = input[0];
			var B = input[1];
			var C = input[2];
			Console.WriteLine(B/A > C ? C : B/A);
		}
	}
}


Measured memory_bytes: 13268
#include <stdio.h>
int  main() {
	char kai[101], kai2[101];
	int i, num = 0, cou = 0;
	scanf("%s", &kai);
	for (i = 0; i < 101; i++) {
		if (kai[i] == '\0') 
			break;
	}
	num = i;
	for (i = 0; i < num; i++) {
		kai2[i] = kai[num - i - 1];
		if (kai[i] != kai2[i])
			cou++;
	}
	printf("%d", cou / 2);


	return 0;
}

Measured memory_bytes: 128
#pragma comment(linker, "/STACK:10240000")
#include <bits/stdc++.h>

using namespace std;

int nums = 0, ansa = 0, ansb = 0;
bool use[20];
int a[20], b[20], c[20];

int dfs(int k, int all)
{
    if (k > all)
    {
        nums ++;
        bool flag = true;
        for (int i = 1; i <= all; i ++)
        {
            if (a[i] != c[i])
            {
                flag = false;
                break;
            }
        }
        if (flag == true)
        {
            ansa = nums;
        }
        flag = true;
        for (int i = 1; i <= all; i ++)
        {
            if (b[i] != c[i])
            {
                flag = false;
                break;
            }
        }
        if (flag == true)
        {
            ansb = nums;
        }
    }
    else
    {
        for (int i = 1; i <= all; i ++)
        {
            if (!use[i])
            {
                c[k] = i;
                use[i] = true;
                dfs(k + 1, all);
                use[i] = false;
            }
        }
    }
}

int main()
{
    int n;
    scanf("%d", &n);
    memset(use, false, sizeof(use));
    for (int i = 1; i <= n; i ++)
    {
        scanf("%d", &a[i]);
    }
    for (int i = 1; i <= n; i ++)
    {
        scanf("%d", &b[i]);
    }
    dfs(1, n);
    printf("%d\n", abs(ansa-ansb));
    return 0;
}


Measured memory_bytes: 256
import sys
import math
def I():return int(sys.stdin.readline().replace("\n",""))
def I2():return map(int,sys.stdin.readline().replace("\n","").split())
def S():return str(sys.stdin.readline().replace("\n",""))
def L():return list(sys.stdin.readline().replace("\n",""))
def Intl():return [int(k) for k in sys.stdin.readline().replace("\n","").split()]
def Lx(k):return list(map(lambda x:int(x)*-k,sys.stdin.readline().replace("\n","").split()))

if __name__ == "__main__":
    n,m =I2()
    h = Intl()
    l = [[] for i in range(n)]
    cnt = 0
    for i in range(m):
        a,b = I2()
        l[a-1].append(b)
        l[b-1].append(a)
    #print(l)
    for i in range(n):
        if len(l[i]) == 0:
            cnt +=1
            continue
        #print(cnt)
        for j in l[i]:
            if h[i] > h[j-1]:
                f = True
            else:
                f = False
                break
        if f:cnt += 1
    print(cnt)

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

#define INF 10000001

#define MOD 1000000007

typedef long long ll;

int main(void){
  ll x,y;
  std::cin >> x >> y;

  ll ans = 0;
  ll a = x;
  while(a<=y){
    a *= 2;
    ans++;
  }

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


Measured memory_bytes: 256
#include<stdio.h>

int main(void){
  int n,m,k,i,j,l,counter;
  counter=0;
  while(scanf("%d",&n)!=1);
  while(scanf("%d",&m)!=1);
  int check[m];
  int count[m];
  for(i=0;i<m;i++){
    check[i]=i+1;
    count[i]=0;
  }
  for(i=0;i<n;i++){
    while(scanf("%d",&k)!=1);
    int array[k];
    for(j=0;j<k;j++){
      while(scanf("%d",&array[j])!=1);
    }
    for(j=0;j<m;j++){
      for(l=0;l<k;l++){
        if(check[j]==array[l])count[j]+=1;
      }
    }
  }
  for(i=0;i<m;i++){
    if(count[i]==n)counter++;
  }
  if(n==1){
    printf("%d\n",k);
  }else{
    printf("%d\n",counter);
  }
  return 0;
}

Measured memory_bytes: 128
// #includes {{{
#ifdef MY_DEBUG
#include "header/header.hpp"
#else
#include <bits/stdc++.h>
#endif

using namespace std;

#define REP(i,n) for(int i=0;i<(int)(n);++i)
#define RREP(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
#define FOR(i,c) for(__typeof((c).begin()) i=(c).begin();i!=(c).end();++i)
#define LET(x,a) __typeof(a) x(a)
//#define IFOR(i,it,c) for(__typeof((c).begin())it=(c).begin();it!=(c).end();++it,++i)
#define ALL(c) (c).begin(), (c).end()
#define MP make_pair

#define EXIST(e,s) ((s).find(e)!=(s).end())

#define RESET(a) memset((a),0,sizeof(a))
#define SET(a) memset((a),-1,sizeof(a))
#define PB push_back
#define DEC(it,command) __typeof(command) it=command

//debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
#define debug_v(x) cerr << #x << " = [";REP(__ind,(x).size()){cerr << (x)[__ind] << ", ";}cerr << "] (L" << __LINE__ << ")" << endl;

#define whole(f,x,...) ([&](decltype((x)) whole) { return (f)(begin(whole), end(whole), ## __VA_ARGS__); })(x)

typedef long long Int;
typedef unsigned long long uInt;
typedef long double rn;

template<class T>
T inf(){
	return numeric_limits<T>::has_infinity?numeric_limits<T>::infinity():(numeric_limits<T>::max()/2);
}

typedef pair<int,int> pii;

#ifdef MY_DEBUG
#include"debug.hpp"
#include"print.hpp"
#endif
// }}}

const string YES = "YES";
const string NO = "NO";
string S;
string T;
Int q;
vector<Int> a;
vector<Int> b;
vector<Int> c;
vector<Int> d;

void solve(){
	vector<int> sumS(S.size()+1), sumT(T.size()+1);
	sumS[0] = sumT[0] = 0;
	REP(i,S.size()){
		sumS[i+1] = sumS[i];
		if(S[i]=='A')sumS[i+1]+=1;
		else if(S[i]=='B')sumS[i+1]+=2;
		sumS[i+1]%=3;
	}
	REP(i,T.size()){
		sumT[i+1] = sumT[i];
		if(T[i]=='A')sumT[i+1]+=1;
		else if(T[i]=='B')sumT[i+1]+=2;
		sumT[i+1]%=3;
	}
	REP(i,q){
		if((sumS[b[i]]-sumS[a[i]]+3)%3==(sumT[d[i]]-sumT[c[i]]+3)%3){
			cout<<YES<<endl;
		}else{
			cout<<NO<<endl;
		}
	}
}


//{{{ main function
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> S;
	cin >> T;
	cin >> q;
	a.resize(q);
	b.resize(q);
	c.resize(q);
	d.resize(q);
	for(int i = 0 ; i < q ; i++){
		cin >> a[i];
		a[i]--;
		cin >> b[i];
		cin >> c[i];
		c[i]--;
		cin >> d[i];
	}
	solve();
	return 0;
}

//}}}



Measured memory_bytes: 4944
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <unordered_map>
#include <stack>



template <class T> class UnionFind {

  private:
    struct subset  {
      T parent;
      T rank;
      T diff_weight;
      T sizes;
    };
    std::vector<subset> subsets;

  public:
    UnionFind (T N) {
      subsets.reserve(N);
      for(T i=0; i<N; i++){
        subsets.push_back( { i, 0, 0, 1 } );
      }
    }

    T Find (T x) {
      if (subsets[x].parent == x) return x;
      subsets[x].diff_weight += subsets[subsets[x].parent].diff_weight;
      return subsets[x].parent = Find(subsets[x].parent);
    }

    T weight(T x) {
      Find(x);
      return subsets[x].diff_weight;
    }

    bool Same (T x, T y) {
        return Find(x) == Find(y);
    }

    bool Union (T x, T y, T w) {
      w += weight(x); w -= weight(y);

      T xroot = Find(x);
      T yroot = Find(y);
      if ( xroot == yroot ) return false;

      if (subsets[xroot].rank < subsets[yroot].rank) {
        subsets[xroot].parent = yroot;
        w = -w;
        subsets[yroot].sizes += subsets[xroot].sizes;
      }
      else if (subsets[xroot].rank > subsets[yroot].rank) {
        subsets[yroot].parent = xroot;
        subsets[xroot].sizes += subsets[yroot].sizes;
      }
      else {
        subsets[yroot].parent = xroot;
        subsets[xroot].rank++;
        subsets[xroot].sizes += subsets[yroot].sizes;
      }
      subsets[yroot].diff_weight = w;
      return true;
    }

    T diff(T x, T y) {
      return weight(y) - weight(x);
    }

    T size (T x) {
      return subsets[Find(x)].sizes;
    }
};




int main (void) {
  int N, M;
  std::cin >> N >> M;

  std::vector<std::pair<int, int>> p(M);
  for(int i=0; i<M; i++){
    int A, B; std::cin >> A >> B;
    p[i].first = A-1; p[i].second = B-1;
  }

  UnionFind<int> uf(N);

  // ans[i] : incovinience after i ( 1 <= i <= M )
  std::vector<long long> ans(M+1);
  ans[M] = (long long) N * (N-1) / 2;
  for(int i=M-1; i>=0; i--){
    if ( uf.Same(p[i].first, p[i].second) ) ans[i] = ans[i+1];
    else {
      long long N1 = uf.size(p[i].first);
      long long N2 = uf.size(p[i].second);
      ans[i] = ans[i+1] - (long long) N1*N2;
    }
    uf.Union(p[i].first, p[i].second, 0);
  }

  for(int i=1; i<=M; i++) std::cout << ans[i] << std::endl;

  return 0;
}

Measured memory_bytes: 4480
#include "bits/stdc++.h"
using namespace std;
#define OUT(x)                cout << #x << " = " << x << endl
#define rep(i, n)             for (int (i) = 0; (i) < (int)(n); (i)++)
#define rer(i, l, r)          for (int (i) = (int)(l); (i) <= (int)(r); (i)++)
#define reu(i, l, r)          for (int (i) = (int)(l); (i) < (int)(r); (i)++)
#define all(x)                (x).begin(), (x).end()
#define rall(x)               (x).rbegin(), (x).rend()
template<typename T> void pv(T a, T b) { for (T i = a; i != b; i ++) cout << *i << " "; cout << endl; }
template<typename T, typename U> inline void amin(T &x, U y) { if (y < x) x = y; }
template<typename T, typename U> inline void amax(T &x, U y) { if (x < y) x = y; }
int in() { int x; scanf("%d", &x); return x; }
long long lin() { long long x; scanf("%lld", &x); return x; }

#define int long long

signed main() { 
        string s;
        cin >> s;
        int n = s.size();
        int ans = 0;
        rep(i, 1 << (n - 1)) {
                int sum = s[n - 1] - '0';
                int x = 10;
                for (int j = n - 2; j >= 0; j --) {
                        if (i & (1 << (n - 2 - j))) {
                                sum += (s[j] - '0') * x;
                                x *= 10;
                        } else {
                                ans += sum;
                                sum = (s[j] - '0');
                                x = 10;
                        }
                }
                ans += sum;
        }
        cout << ans << endl;
        return 0;
}               


Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

import static java.lang.Integer.parseInt;

/**
 * Cyclic Sugoroku
 */
public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String line;

		int N = parseInt(br.readLine());
		int[] a = new int[N];

		StringTokenizer st = new StringTokenizer(br.readLine());

		for (int i = 0; i < N; i++) {
			a[i] = parseInt(st.nextToken());
		}

		//
		int[] indeg = new int[N];
		boolean[] used = new boolean[N];

		for (int i = 0; i < N; i++) {
			indeg[(i + a[i]) % N]++;
		}


		for (int i = 0; i < N; i++) {
			int j = i;
			while (!used[j] && indeg[j] == 0) {
				used[j] = true;
				j = (j + a[j]) % N;
				indeg[j]--;
			}
		}

//		System.out.println(Arrays.stream(indeg).filter(x -> x != 0).count());

		int count = 0;
		for (int i = 0; i < N; i++) {
			if (indeg[i] != 0) count++;
		}
		System.out.println(count);
	}
}

Measured memory_bytes: 44356
function LunlunNumber()
    K = parse(Int, readline())
    ans = 0
    que = [1,2,3,4,5,6,7,8,9]
    for k in 1:K
        ans = popfirst!(que)
        ans%10>0 && push!(que, 10ans + (ans%10) -1)
        push!(que, 10ans + ans%10)
        ans%10<9 && push!(que, 10ans + (ans%10) + 1)
    end
    return println(ans)
end
LunlunNumber()

Measured memory_bytes: 167356
sx,sy,tx,ty=map(int,input().split())
x=tx-sx
y=ty-sy
def p(h,n):
    for i in range(n):
        print(h,end="")
p("U",y)
p("R",x)
p("D",y)
p("L",x+1)
p("U",y+1)
p("R",x+1)
p("D",1)
p("R",1)
p("D",y+1)
p("L",x+1)
p("U",1)    

Measured memory_bytes: 4468
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii =  pair<int, int>;
using pll =  pair<long long, long long>;
constexpr char ln =  '\n';
constexpr long long MOD = 1000000007LL;
constexpr long long INF = 1000000000LL;
#define all(x) (x).begin(),(x).end()
#define rep(i,n) for(int i=0;i<(n);i++)
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; }

vector<ll> hum_layer(55,0);
vector<ll> pate_num(55, 0); //各層ごとのパティの枚数

ll eat_layer(int n, ll pos, ll sum){
    //cout << "n:" << n << " pos:" << pos << " sum: " << sum << ln;
    if(n == 1){
        sum += min((ll)3, pos);
        return sum;
    }
    ll layer = hum_layer[n], pate = pate_num[n];
    if(pos == 0) return sum;
    if(pos == layer-1) return (sum + pate);
    if(pos == (layer-1)/2) return (sum + pate / 2 + 1);

    if(pos > (layer-1)/2){
        pos -= layer/2+1;
        sum += pate / 2+1;
    } else{
        pos--;
    }
    return eat_layer(n-1, pos, sum);
}

int main() {
    ll n, x;
    cin >> n >> x; x--;
    
    ll num = 1;
    hum_layer[0] = 1;
    for(int i = 1; i <= 50; i++){
        num = num * 2 + 1;
        pate_num[i] = num;
        hum_layer[i] = hum_layer[i-1] * 2 + 3;
    }

    ll res = eat_layer(n, x, 0);
    cout << res << ln;
}



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

using namespace std;

struct Edge
{
	int to;
};

vector<Edge> E[100];
bool isVisit[5];

bool DFS(int p, int c)
{
	if (c >= 4)
	{
		return(true);
	}
	isVisit[p] = true;
	for (int i = 0; i < E[p].size(); ++i)
	{
		if (isVisit[E[p][i].to] == false)
		{
			return(DFS(E[p][i].to, c + 1));
		}
	}
	return(false);
}

void solve()
{
	vector<int> a(3);
	vector<int> b(3);
	for (int i = 0; i < 3; ++i)
	{
		cin >> a[i] >> b[i];
		Edge e;
		e.to = b[i];
		E[a[i]].push_back(e);
		e.to = a[i];
		E[b[i]].push_back(e);
	}
	for (int i = 1; i < 5; ++i)
	{
		for (int j = 1; j < 5; ++j)
		{
			isVisit[j] = false;
		}
		if (DFS(i, 1))
		{
			cout << "YES" << endl;
			return;
		}
	}
	cout << "NO" << endl;
}

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

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define finish(x) return cout << x << endl, 0
#define ll long long

string s;

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> s;
    int n = s.size();
    vector <int> a(n + 1);
    int cur = 0;
    for(int i = 0 ; i < n ; i++){
        if(s[i] == '<') cur++;
        else cur = 0;
        a[i + 1] = cur;
    }
    cur = 0;
    for(int i = n - 1 ; i >= 0 ; i--){
        if(s[i] == '>') cur++;
        else cur = 0;
        a[i] = max(a[i], cur);
    }
    ll ans = 0;
    for(auto &i : a) ans += i;
    cout << ans << endl;
}


Measured memory_bytes: 2844