akhauriyash/Code-Regression huggingface dataset:
/*input

*/


// assic value of ('0'-'9') is(48 - 57) and (a-z) is (97-122) and (A-Z) is(65-90) and 32 for space
// #pragma GCC target ("avx2")
// #pragma GCC optimization ("O3")
// #pragma GCC optimization ("unroll-loops")
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;

// order_of_key (k) : Number of items strictly smaller than k .
// find_by_order(k) : K-th element in a set (counting from zero).
using namespace __gnu_pbds;
template<class T> using oset=tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define ll          long long int
#define pb          push_back
#define pii         pair<ll ,ll >
#define vpii        vector< pii >
#define vi          vector<ll >
#define vs			vector< string >
#define vvi         vector< vector< ll > >
#define inf			(ll)1e18
#define all(it,a)   for(auto it=(a).begin();it!=(a).end();it++) 
#define F           first
#define S           second
#define sz(x)       (ll )x.size()
#define rep(i,a,b)	for(ll  i=a;i<b;i++)
#define repr(i,a,b) for(ll  i=a;i>b;i--)
#define lbnd        lower_bound
#define ubnd        upper_bound
#define mp          make_pair
#define whatis(x)   cout << #x << " is " << x << "\n";
#define graph(n)    adj(n,vector< ll > () )
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

#define debug(x)     cout << #x << " " << x << endl;
#define debug_p(x)   cout << #x << " " << x.F << " " << x.S << endl;
#define debug_v(x)   {cout << #x << " "; for (auto ioi : x) cout << ioi << " "; cout << endl;}
#define debug_vp(x)  {cout << #x << " "; for (auto ioi : x) cout << '[' << ioi.F << " " << ioi.S << ']'; cout << endl;}
#define debug_v_v(x) {cout << #x << "/*\n"; for (auto ioi : x) { for (auto ioi2 : ioi) cout << ioi2 << " "; cout << '\n';} cout << "*/" << #x << endl;}

int solve()
{
	ll n;cin>>n;
	vi a(n);
	map<ll,ll> m1,m2;
	rep(i,0,n)
	{
		cin>>a[i];
		m1[i+a[i]]++;
		m2[i-a[i]]++;
	} 

	ll ans=0;
	rep(i,0,n) ans+=m2[i+a[i]];
	cout<<ans<<"\n";




	return 0;
}

int main()
{
	auto start = chrono::high_resolution_clock::now();

	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	ll test_cases=1;
	//cin>>test_cases;
	while(test_cases--)
		solve();

	auto stop = chrono::high_resolution_clock::now();
	auto duration = chrono::duration_cast<chrono::milliseconds>(stop-start);
	//cout<<"\nduration: "<<(double)duration.count()<<" milliseconds";
}

Measured memory_bytes: 39088
while True:
    n, m, p = map(int, input().split())
    if n == 0 and m == 0 and p == 0:
        break

    x = [int(input()) for i in range(n)]
    total = sum(x) * (100 - p)
    if x[m - 1] == 0:
        print(0)
    else:
        print(total // x[m - 1])


Measured memory_bytes: 5620
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fastIO cout << fixed << setprecision(12), ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
double const EPS = 1e-10, PI = acos(-1);
const int N = 5e5 + 9, M = 1e5 + 9, OO = 1e9 + 7, MOD = 1e9 + 7;
const ll inf = 1e18;

ll add(ll x, ll y) {
  x += y;
  while(x >= MOD)
    x -= MOD;
  while(x < 0)
    x += MOD;
  return x;
}

ll mul(ll x, ll y) {
  return (x * y) % MOD;
}

ll Left[N], Right[N], cnt[N], dp[102][N], pre[102][N];

int main() {
  fastIO;
#ifdef LOCAL
  freopen("input.in", "rt", stdin);
#endif
  int len, n;
  cin >> n >> len;
  int x = 1, idx = 0;
  while(x <= n) {
    int a = n / x;
    int b = n / a;
    ++idx;
    Left[idx] = x, Right[idx] = b;
    x = b + 1;
  }
  for (ll i = 1; i <= idx; ++i) {
    cnt[i] = Right[i] - Left[i] + 1;
    dp[1][i] = cnt[i];
  }
  for (int i = 2; i <= len; ++i) {
    for (int last = 1; last <= idx; ++last) {
      int L = 1, R = idx - last + 1;
      pre[i][L] = add(pre[i][L], dp[i-1][last]);
      pre[i][R + 1] = add(pre[i][R+1], -dp[i-1][last]);
    }
    for (ll last = 1; last <= idx; ++last) {
      pre[i][last] = add(pre[i][last], pre[i][last - 1]);
      dp[i][last] = add(dp[i][last], mul(cnt[last], pre[i][last]));
    }
  }
  ll answer = 0;
  for (int i = 1; i <= idx; ++i) {
    answer = add(answer, dp[len][i]);
  }
  cout << answer;
  return 0;
}


Measured memory_bytes: 514304
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const double EPS = 1e-9;
typedef vector<int> vint;
typedef pair<int, int> pint;
#define rep(i, n) REP(i, 0, n)
#define ALL(v) v.begin(), v.end()
#define MSG(a) cout << #a << " " << a << endl;
#define REP(i, x, n) for(int i = x; i < n; i++)
template<class T, class C> void chmax(T& a, C b){ a>b?:a=b; }
template<class T, class C> void chmin(T& a, C b){ a<b?:a=b; }

int main(){
    string S;
    cin>>S;
    ll a = 0;
    ll b = 0;
    ll c = 0;
    ll m = 0;

    if(S[0]=='A'){
        a = 1;
    }
    

    REP(i, 1, S.size()){
        auto x = S[i-1];
        auto y = S[i];

        

        if(x == 'A'){
            if(y == 'A'){
                ++a;
            }else if (y =='B'){
            }else if (y == 'C'){
                a = 0;
            }
        }else if (x =='B'){
            if(y == 'A'){
                a = 1;
            }else if (y =='B'){
                a = 0;
            }else if (y == 'C'){
                m += a;
            }
        }else if (x == 'C'){
            if(y == 'A'){
                ++a;
            }else if (y =='B'){
                if(i>=2){
                    if(S[i-2]!='B'){
                        a = 0;
                    }
                }
            }else if (y == 'C'){
                a = 0;
            }
        }

        // MSG(x);
        // MSG(y);
        // MSG(a);
        // MSG(m);
    }

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


Measured memory_bytes: 640
// motatoes cp snippet
#include <bits/stdc++.h>

using namespace std;

#define endl "\n"
#define ll long long

#define forr(a,b,v) for(int v=a; v<=b; v++)
#define ford(a,b,v) for(int v=a; v>=b; v--)

// https://www.topcoder.com/community/competitive-programming/tutorials/power-up-c-with-the-standard-template-library-part-1/#map
typedef vector< int > vi;
typedef vector< vi > vvi;
typedef vector<long> vl;
typedef vector<long long> vll;
typedef pair< int,int > ii;
#define sz(a) int((a).size())
#define pb push_back
#define all(c) (c).begin(),(c).end()
#define tr(c,i) for(typeof((c)).begin() i = (c).begin(); i != (c).end(); i++)
#define present(c,x) ((c).find(x) != (c).end())
#define cpresent(c,x) (find(all(c),x) != (c).end())


string to_string(string s) {
  return '"' + s + '"';
}
 
string to_string(const char* s) {
  return to_string((string) s);
}
 
string to_string(bool b) {
  return (b ? "true" : "false");
}
 
template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
 
template <typename A>
string to_string(A v) {
  bool first = true;
  string res = "{";
  for (const auto &x : v) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}

// get default value from map type
template<class K, class V>
V get(map<K,V> m, K k, V def) {
    if (m.find(k) != m.end()) {
        return m[k];
    } else {
        return def;
    }
}

// <geometry>
const double PI = acos(-1.0);

double toDegreeFromMinutes(double minutes) {
  return (minutes/60);
}

double toRadians(double degree) {
  return (degree * PI/180.0);
}

double toDegree(double radian) {
  if (radian < 0) radian += 2 * PI;
  return (radian * 180 / PI);  
}

double fixAngle(double A) {
  return A > 1 ? 1 : (A < -1 ? -1 : A);
}

// sin(A)/a = sin(B)/b = sin(C)/c
double getSide_a_bAB(double b, double A, double B) {
  return (sin(A)*b)/sin(B);
}

double getAngle_A_abB(double a, double b, double B) {
  return asin( fixAngle(  (a*sin(B))/b ));  
}

// a^2 = b^2 + c^2 - 2*b*c*cos(A)
double getAngle_A_abc(double a, double b, double c) {
  return acos( fixAngle(  (b*b*c*c-a*a) / (2*b*c)  ) );  
}
// </geometry>

const int INF = 1e9;

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

    int n;
    cin >> n;

    int A[n+5];
    forr(1,n,i) {
        cin >> A[i];
    }

    vector<int> dp(n+5, INF) ;
    dp[1] = 0;
    for (int i=1; i<=n; i++) {
        dp[i+1] = min(dp[i+1],  dp[i]+abs(A[i] - A[i+1] )  );
        dp[i+2] = min(dp[i+2],  dp[i]+abs(A[i] - A[i+2] )  );
    }
    // cout << to_string(dp);
    cout << dp[n];

    return 0;
}


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

const int N = 10;

int main()
{
	int r, d; cin >> r >> d;

	vector<long long> x(N + 1); cin >> x[0];

	for (int i = 1; i <= N; i++) {
	
		x[i] = r * x[i - 1] - d;

		cout << x[i] << endl;

	}

	return 0;
}

Measured memory_bytes: 256
fun main(args: Array<String>) {
    val (x, n) = readLine()!!.split(' ').map { it.toInt() }
    val p = if (n > 0) readLine()!!.split(' ').map { it.toInt() } else listOf<Int>()

    val notinc = BooleanArray(102) {true}
    repeat(n) {
        notinc[p[it]] = false
    }
    var min = Int.MAX_VALUE
    var ans = Int.MAX_VALUE
    for (i in 0 until 102) {
        if (notinc[i]) {
            val d = Math.abs(x - i)
            if (d < min) {
                ans = i
            }
            min = Math.min(d, min)
        }
    }
    println(ans)
}


Measured memory_bytes: 36552
#include<bits/stdc++.h>
using namespace std;
long long a,b;
long long sum;
int main()
{
	scanf("%lld%lld",&a,&b);
	sum=a+b;
	if (sum%2==1)
		printf("IMPOSSIBLE");
	else
		printf("%lld",sum/2);
	return 0;
}

Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS
//#define _USE_MATH_DEFINES
#include<stdio.h>
//#include<stdlib.h>
//#include<math.h>
//#include<string.h>
//#include<time.h>
#define P(type,x) fprintf(stdout,"%"#type"\n",x)
int main() {
	int n;
	for (; ~fscanf(stdin, "%d", &n); printf("3C"), P(02d, !(n % 39) ? 39 : n % 39));
	return 0;
}

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

using namespace std;
#define inputInt(a) int a; cin >> a; 
#define inputInt2(a,b) int a; int b; cin >> a >> b; 
#define inputInt3(a,b,c) int a; int b; int c; cin >> a >> b >> c;
#define inputLong(a) long a;cin >> a; 
#define inputIntArray(a,N) int a[N];for(int i=0;i<N;i++){cin >> a[i];}
#define inputLongArray(a,N) long a[N];for(int i=0;i<N;i++){cin >> a[i];}
#define inputIntArray2(a,b,N) int a[N]; int b[N]; for(int i=0;i<N;i++){cin >> a[i] >> b[i];}
#define output(answer) cout << answer << endl;
#define fN(i,N)    for(int i=0; i<N; i++)
#define fSE(i,s,e) for(int i=s; i<=e; i++)
#define ll long long
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define FOR(i,N) for(int i=0; i<N; i++)
#define cinv(v,N) vector<int> v(N); for(int i=0; i<N; i++){ cin >> v[i]; }
#define mt make_tuple
#define vll vector<long long int>
#define vvll vector<vector<long long int>>
#define all(v) (v).begin(),(v).end()
const ll MOD2 = 998244353;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

int main()
{
  //input
  cin.tie(0);
  ios::sync_with_stdio(false);
  
  string S; cin >> S;
  
  //main
  string ans = "Yes";
  if(S.size()%2==1){ cout << "No" << endl; return 0;  }
  FOR(i,S.size()){
    if(i%2 == 0){
      if(S[i]!='h'){ cout << "No" << endl; return 0;  }
    }else{
      if(S[i]!='i'){ cout << "No" << endl; return 0;  }
    }
  }
  
  // output
  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  
  //データ入れと並び替え
  int N;
  cin >> N;
  vector<int> card(N);
  for(int i = 0; i < N; i++){
    cin >> card.at(i);
  }
  sort(card.begin(),card.end());
  reverse(card.begin(),card.end());
  
  //カードを取り合う
  int Alice = 0, Bob = 0;
  bool a = true;
  for(int i = 0; i < N; i++){
    if(a){
      Alice += card.at(i);
      a = false;
    }
    else{
      Bob += card.at(i);
      a = true;
    }
  }
  
  //出力
  cout << Alice - Bob << endl;
}

Measured memory_bytes: 256
// #pragma GCC optimize(3,"Ofast","inline")
// #pragma GCC optimize(2)
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
#include <stack>
#include <vector>
#include <string>
#include <iostream>
#include <list>
#include <cstdlib>
#include <bitset>
#include <assert.h>
#include <time.h>
#include <iomanip>
// #define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
// char buf[(1 << 21) + 1], * p1 = buf, * p2 = buf;
// #define int long long
#define lowbit(x) (x & (-x))
#define lson root << 1, l, mid
#define rson root << 1 | 1, mid + 1, r
#define pb push_back
typedef unsigned long long ull;
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll, ll> pll;
#define bug puts("BUG")
const long long INF = 0x3f3f3f3f3f3f3f3fLL;
const int inf = 0x3f3f3f3f;
const int mod = 998244353;
const double eps = 1e-6;
template <class T>
inline void read(T &x)
{
    int sign = 1;char c = getchar();x = 0;
    while (c > '9' || c < '0'){if (c == '-')sign = -1;c = getchar();}
    while (c >= '0' && c <= '9'){x = x * 10 + c - '0';c = getchar();}
    x *= sign;
}
#ifdef LOCAL
    FILE* _INPUT=freopen("input.txt", "r", stdin);
    // FILE* _OUTPUT=freopen("output.txt", "w", stdout);
#endif
using namespace std;
const int maxn = 1e5 + 10;
int h[maxn];
bool is[maxn];
int main()
{
    int n, m;
    int u, v;
    read(n), read(m);
    memset(is, 1, sizeof(bool) * (n + 10));
    for (int i = 1; i <= n; ++i)
    {
        read(h[i]);
    }
    for (int i = 0; i < m; ++i)
    {
        read(u), read(v);
        is[u] &= (h[u] > h[v]);
        swap(u, v);
        is[u] &= (h[u] > h[v]);
    }
    int res = 0;
    for (int i = 1; i <= n; ++i)
    {
        res += is[i];
    }
    printf("%d\n", res);
}


Measured memory_bytes: 4264
@memo = {}

# 10^n未満で0以外の個数がちょうどkな数の個数
def f(n, k)
  if n == 0
    0
  elsif n == 1
    if k == 1
      9
    elsif k == 0
      1
    else
      0
    end
  elsif k > n
    0
  else
    @memo[[n,k]] ||= f(n - 1, k) + f(n - 1, k - 1) * 9
  end
end

def g(x, k)
  if x.size == 0
    0
  elsif x.size == 1 && k == 0
    1
  elsif x.size == 1 && k == 1
    x[0]
  elsif x.size == 1
    0
  else
    sz = x.size - 1
    y = x[0]
    if y > 0
      f(sz, k) * 1 + f(sz, k - 1) * (y-1) + g(x[1..-1], k - 1)
    else
      g(x[1..-1], k)
    end
  end
end

def h(x, k)
  x = x.to_s.chars.map{|x| x.to_i }
  g(x, k)
end

#k = 2
#(0..200).each do |x|
#  puts "#{x} #{h(x, k)}"
#end


x = gets.to_i
k = gets.to_i
puts h(x, k)

Measured memory_bytes: 2300
import bisect

left_sentinel = -2 * (10 ** 10)
right_sentinel = 3 * (10 ** 10)

A, B, Q = map(int, input().split())
ss = [left_sentinel] + [int(input()) for _ in range(A)] + [right_sentinel]
ts = [left_sentinel] + [int(input()) for _ in range(B)] + [right_sentinel]

for _ in range(Q):
    x = int(input())
    s_index = bisect.bisect_left(ss, x)
    right_s = ss[s_index]
    left_s = ss[s_index - 1]
    t_index = bisect.bisect_left(ts, x)
    right_t = ts[t_index]
    left_t = ts[t_index - 1]
    ans = min(
        max(right_s, right_t) - x,
        right_s - left_t + min(right_s - x, x - left_t),
        right_t - left_s + min(right_t - x, x - left_s),
        x - min(left_s, left_t)
    )
    print(ans)
    

Measured memory_bytes: 104936
#include <bits/stdc++.h>
using namespace std;
using Graph = vector<vector<int>>; // グラフ型

/* // 深さ優先探索
vector<bool> seen;
int dfs(const Graph &G, int v) {
    seen[v] = true; // v を訪問済にする
    int score = 0; 

    // v から行ける各頂点 next_v について
    for (auto next_v : G[v]) { 
        if (seen[next_v]) continue; // next_v が探索済だったらスルー

        // 負荷さ優先探索中の処理



        dfs(G, next_v); // 再帰的に探索, 毎回mat渡してええの？
    }
    return score;
} */


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

    if(s == "ABC"){
        cout << "ARC" << endl;
    }else{
        cout << "ABC" << endl;
    }



}


Measured memory_bytes: 3620
#include<iostream>
using namespace std;
//N!の約数のうち、75個の約数を持つものは何個あるか?
int fac[101];
int tmp = 0;
int prime[] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,
               61,67,71,73,79,83,89,97};
int prime_len = 25;
int x[6];

void dcmp(int n) {
    for (int i = 2; i <= n; i++) {
        tmp = i;
        while (tmp <= n) {
            fac[i] += n / tmp;
            tmp = tmp * i;
        }
    }
}
/*
約数が75個になるのは、素因数がa,b,cに絞られて各指数が
(2,24,0) (4,14,0) (2,4,4) (74,0,0)となる場合

x<2,2<=x<4,4<=x<14,14<=x<24,24<=xの5つに分けてカウント
 x0   x1     x2       x3      x4

1つめ・・・x5*(x5-1)/2 + x5 * (x2+x3+x4)
*/
int main() {
    int n;
    cin >> n;
    
    for (int i = 0; i < n; i++) fac[i] = 0;
    dcmp(n);

    for (int i = 0; i < 6; i++) x[i] = 0;
    for (int i = 0; i < prime_len; i++) {
        tmp = prime[i];
        if (fac[tmp] < 2) x[0]++;
        else if (fac[tmp] < 4) x[1]++;
        else if (fac[tmp] < 14) x[2]++;
        else if (fac[tmp] < 24) x[3]++;
        else x[4]++;
        if (fac[tmp] >= 74) x[5]++;
    }
    //ここまでは正しく算出できてるっぽい

    tmp = x[2] + x[3] + x[4];
    
    int res = 0;
  
    res += x[4] * (x[4] - 1);

    res += x[4] * (x[1] + x[2] + x[3]);

    res += (x[3] + x[4]) * (x[3] + x[4] - 1);

    res += (x[3] + x[4]) * x[2];

    res += tmp * (tmp - 1) / 2 * x[1];
    res += tmp * (tmp - 1) * (tmp - 2) / 2;
    
    res += x[5];
    cout << res << "\n";
}

Measured memory_bytes: 256
def foo
  i = gets.to_i
  i.times do
    max = 0
    min = 0
    list = gets.split.map(&:to_i)
    while true
      break if list.empty?
      j = list[0]
      if max < j
        max = j
      elsif min < j
        min = j
      else
        break
      end
      list.delete(j)
    end

    puts list.empty? ? 'YES' : 'NO'
  end
end
foo

Measured memory_bytes: 8688
n,k=map(int,input().split())

d=[]
a=[]

for i in range(k):
    d1=int(input())
    d.append(d1)
    a1=map(int,input().split())
    a+=a1

b=set(a)
count=0
for i in range(1,n+1):
    if i in b:
        continue
    else:
        count+=1

print(count)



Measured memory_bytes: 66904
import sys
A, B = map(int, input().split())
S = input()
ls = [str(i) for i in range(10)]
for i, x in enumerate(S):
    if i == A:
        if x != '-':
            print('No')
            sys.exit()
    else:
        if not x in ls:
            print('No')
            sys.exit()
print('Yes')

Measured memory_bytes: 3060
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<stack>
using namespace std;
stack<char>ss;
string a;
int main(){
    cin>>a;
    for(int i=0;i<a.size();i++)ss.push(a[i]);
    int PD=1;
    for(int i=0;i<a.size();i++){
        char topm=ss.top();
        if(topm=='b') topm='d';
        else if(topm=='d') topm='b';
        else if(topm=='p') topm='q';
        else if(topm=='q') topm='p';
        if(topm==a[i])ss.pop();
        else {
            PD=0;
            break;
        }
    }
    if(PD!=0) cout<<"Yes";
    else cout<<"No";
    return 0;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
using namespace std;
typedef long long int ll;
typedef pair<int,int> P;
#define yn {puts("Yes");}else{puts("No");}
#define MAX_N 200005

const int MAX = 2100000;
const int MOD = 1000000007;
long long fac[MAX], finv[MAX], inv[MAX];
// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}
// 二項係数計算
long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

long long FINV(int n){
    if (n < 0) return 0;
    return finv[n];
}

int main() {
    // 前処理
    COMinit();

    ll a, b, c, d;
    cin >> a >> b >> c >> d;

    int ab = a + b;
    int cd = c + d;

    ll ans = 0;
    ll tmp = 0;

    srep(i,ab,cd+1){
        if(i == ab){
            tmp = COM(i,a);
            tmp %= MOD;
        }else{
            ll tmp2 = tmp * 2 % MOD;

            if(i - b <= c){
                tmp2 += COM(i-1,b-1);
            }else{
                tmp2 += MOD - COM(i-1,c);
            }
            if(i - a <= d){
                tmp2 += COM(i-1,a-1);
            }else{
                tmp2 += MOD - COM(i-1,d);
            }

            tmp = tmp2;
        }
        ans += tmp;
        ans %= MOD;
    }

    

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


Measured memory_bytes: 49408
#include<bits/stdc++.h>
typedef long long ll;
#define REP(i,n) for(int i = 0;i < (n);i++)
#define rep(i,m,n) for(int i = (m);i < (n);i++)
#define P pair<int,int>
#define pb push_back
#define mk make_pair
using namespace std;
#define Vec(a) vector <int> a
#define F first
#define S second
const int INF = 1 << 20;
const int MOD = 1e9+7;





int main(){
    ll n;
    cin >> n;
    vector <ll> a(n);
    REP(i,n)
        cin >> a[i];
    sort(a.begin(),a.end());
    ll cnt = 0;
    if(n == 2){
        cout << abs(a[0]-a[1]) << endl;
        return 0;
    }
    int l = 0,r = n-1;
    bool f = true;
    if(n%2){
        ll cnt2 = 0;
        REP(i,n/2){
            cnt -= 2*a[i];
        }
        cnt += a[n/2]+a[n/2+1];
        if((n/2+1) != n-1){
            rep(i,n/2+2,n){
                cnt += 2*a[i];
            }
        }
        sort(a.begin(),a.end(), greater<ll>());
        REP(i,n/2){
            cnt2 += 2*a[i];
        }
        cnt2 -= (a[n/2]+a[n/2+1]);
        if(n/2+1 != n-1){
            rep(i,n/2+2, n){
                cnt2 -= 2*a[i];
            }
        }
        cout << max(cnt, cnt2) << endl;
    }
    else{
        ll cnt2 = 0;
        sort(a.begin(), a.end(), greater<ll>());
        REP(i,n/2-1){
            cnt += 2*a[i];
        }
        cnt += a[n/2-1];
        //cout << cnt << endl;
        cnt -= a[n/2];
        rep(i,n/2+1, n){
            cnt -= 2*a[i];
        }
        
        cout << max(cnt,cnt2) << endl;
    }

    return 0;
}


Measured memory_bytes: 1024
s = str(input())
flag = 0
a = []
if(len(s)%2 != 0):
    print("No")
    exit()
else:
    for i in range(0,len(s),2):
        if(s[i] != "h" or s[i+1] != "i"):
            print("No")
            exit()
print("Yes")

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

using namespace std;

int main() {
  string t;
  cin>>t;
  
  int a=t.size();
  int ans=0;
  if(t.at(0)=='D'){
    ans++;
  }
  else if(t.at(0)=='?'){
    ans++;
    t.at(0)='D';
  }
  for (int i = 1; i < a; i++) {
    if(t.at(i-1)=='P'&&t.at(i)=='D'){
      ans+=2;
    }
    else if(t.at(i-1)=='P'&&t.at(i)=='?'){
      ans+=2;
      t.at(i)='D';
    }
    else if(t.at(i)=='D'){
      ans++;
    
    }
    else if(t.at(i)=='?'){
      ans++;
      t.at(i)='D';
    }
    
 
  }
  cout<<t<<endl;

  
}

Measured memory_bytes: 3760
#include <bits/stdc++.h>
using namespace std;
#define repr(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define reprrev(i,a,b) for(int i=b-1;i>=a;i--) // [a, b)
#define reprev(i,n) reprrev(i,0,n)
typedef long long ll;
typedef unsigned long long ull;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

const ll mod = 1e9+7;


void chmod(ll &M){
    if(M >= mod) M %= mod;
    else if(M < 0){
        M += (abs(M)/mod + 1)*mod;
        M %= mod;
    }
}

ll modpow(ll x, ll n){
    if(n==0) return 1;
    ll res=modpow(x, n/2);

    if(n%2==0) return res*res%mod;
    else return res*res%mod*x%mod;
}

int getl(int i, int N) { return i==0? N-1:i-1; };
int getr(int i, int N) { return i==N-1? 0:i+1; };

// 線分 ab の偏角 返り値は[-π, π]
double argument(const pair<double, double> &a, const pair<double, double> &b){
    double ax=a.first, ay=a.second, bx=b.first, by=b.second;
    return atan2(by-ay, bx-ax);
}

/* <-----------------------------------------------------------------------------------> */
/* <-----------------------------------------------------------------------------------> */
/* <-----------------------------------------------------------------------------------> */
/* <-----------------------------------------------------------------------------------> */
/* <-----------------------------------------------------------------------------------> */
/* <-----------------------------------------------------------------------------------> */
/* <-----------------------------------------------------------------------------------> */
/* <-----------------------------------------------------------------------------------> */


/* 注意 

    1LL<<60 * N とかのオーバーフローに気を付けろ
    制約がヒントになる、ちゃんと全ての制約を見ろ

*/

ll gcd(ll a, ll b) {
    if (a<b) swap(a, b);

    while(b!=0) {
        ll t = a;
        a = b;
        b = t%b;
    }
    return a;
}

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


vector< pair<ll, ll> > prime_factorization(ll n){
    vector< pair<ll, ll> > res;

    for(ll i=2; i*i<=n; ++i){
        if(n%i == 0){
            int cnt = 0;
            while(n%i == 0){
                ++cnt;
                n /= i;
            }
            res.push_back(make_pair(i, cnt));
        }
    }
    if(n>1) res.push_back(make_pair(n, 1));

    return res;
}



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

    ll n; cin >> n;
    vector<ll> a(n);
    rep(i, n) cin >> a[i];

    
    map<ll, ll> mp;
    rep(i, n) {
        auto div = prime_factorization(a[i]);
        for(auto p: div) { chmax(mp[p.first], p.second); }
    }

    ll ans = 0;
    ll l = 1;
    for(auto itr=mp.begin(); itr!=mp.end(); ++itr) {
        l *= modpow(itr->first, itr->second);
        chmod(l);
    }
    rep(i, n) {
        ans += modpow(a[i], mod-2);
        chmod(ans);
    }
    ans *= l;
    chmod(ans);
    cout << ans << endl;
    
    return 0;
}


Measured memory_bytes: 1024
package main

import (
	"fmt"
	"math"
)

func abs(a int) int {
	if a < 0 {
		return -a
	} else {
		return a
	}
}

func min(nums ...int) int {
	if len(nums) == 0 {
		panic("funciton min() requires at least one argument.")
	}
	res := nums[0]
	for i := 0; i < len(nums); i++ {
		res = int(math.Min(float64(res), float64(nums[i])))
	}
	return res
}

func max(nums ...int) int {
	if len(nums) == 0 {
		panic("funciton max() requires at least one argument.")
	}
	res := nums[0]
	for i := 0; i < len(nums); i++ {
		res = int(math.Max(float64(res), float64(nums[i])))
	}
	return res
}

func findFactors(num int)int {
	count:=0
	for i:=2;i*i<=num;i++{
		j:=i
		for num%j==0{
			count++
			num=num/j
			j*=i
		}
		for num%i==0{
			num/=i
		}
	}
	if num>1{
		count++
	}
	return count
}

func main() {
	var N int
	fmt.Scan(&N)
	fmt.Println(findFactors(N))


}


Measured memory_bytes: 1796
#include <bits/stdc++.h>
#define push_back pb
typedef long long int ll;
typedef long int li;

using namespace std;

int main()
{
	int n;
	cin>>n;
	ll *a = new ll[n];
	ll sum = 0;
	for (int i = 0; i < n; ++i)
	{
		cin>>a[i];
		sum += a[i]-1;
	}
	cout<<sum<<endl;
	// int maxE = *max_element(a,a+n);
	// ll maxS = 0;
	// for (int i = 1 ; i <= maxE*10000; ++i)
	// {
	// 	for (int j = 0; j < n; ++j)
	// 	{
	// 		sum += (i % a[j]);
	// 	}
	// 	maxS = max(maxS, sum);
	// 	sum=0;
	// }
	// cout<<maxS<<endl;
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#define p 1000000007
using namespace std;
int n,m,K,a[202020];
int ma[1000100];
int zs[1000100],las[1000100],sz;
bool d[1000100];
void init()
{
	for(int i=2;i<=1000000;i++)
	{
		if(!d[i]) zs[++sz]=i,las[i]=sz;
		for(int j=1;j<=sz&&zs[j]*i<=1000000;j++)
		{
			d[zs[j]*i]=1;
			las[zs[j]*i]=j;
			if(i%zs[j]==0) break;
		}
	}
}
long long ksm(long long x,int t)
{
	long long res=1;
	for(;t;t>>=1,x=x*x%p) if(t&1) res=res*x%p;
	return res;
}
int main()
{
	scanf("%d",&n);
	init();
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		int x=a[i];
		while(x!=1)
		{
			int y=las[x],cnt=0;
			while(las[x]==y) x/=zs[y],cnt++;
			ma[y]=max(ma[y],cnt);
		}
	}
	int ans=0;
	for(int i=1;i<=n;i++)
	{
		int x=a[i],sum=1;
		for(int y=1;y<=sz;y++)
		{
			int cnt=0;
			while(las[x]==y) x/=zs[y],cnt++;
			if(ma[y]-cnt) sum=1LL*sum*ksm(zs[y],ma[y]-cnt)%p;
		}
		ans=(ans+sum)%p;
	}
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 8448
#include<stdio.h>
main(){
  int a, b, c, tmp;
  scanf("%d %d %d", &a, &b, &c);
  
  if( a > b) {
    tmp = a;
    a = b;
    b = tmp;
  }
  if( b > c) {
    tmp = b;
    b = c;
    c = tmp;
  }
  if( a > b) {
    tmp = a;
    a = b;
    b = tmp;
  }
  printf("%d %d %d\n", a, b, c);
  return 0;
}


Measured memory_bytes: 2104
n,m=map(int,input().split())
a=[-int(aa) for aa in input().split() ]

import heapq
heapq.heapify(a)
for _ in range(m):
    now = -heapq.heappop(a)
    heapq.heappush(a,- (now//2) )
print(-sum(a))

Measured memory_bytes: 72088
//
//  ROIGold.cpp
//  Main calisma
//
//  Created by Rakhman on 05/02/2019.
//  Copyright © 2019 Rakhman. All rights reserved.
//
 
#include <cstring>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <queue>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cassert>
#include <iterator>
 
#define ios ios_base::sync_with_stdio(0), cout.tie(0), cin.tie(0);
#define S second
#define F first
#define pb push_back
#define nl '\n'
#define NL cout << '\n';
#define EX exit(0)
#define all(s) s.begin(), s.end()
#define no_answer return cout << 0, 0;
#define FOR(i, start, finish, k) for(llong i = start; i <= finish; i += k)
 
const long long MXN = 136 + 200;
const long long MNN = 2e3 + 520;
const long long MOD = 1e9 + 7;
const long long INF = 1e18;
const long long OO = 1e9 + 500;
 
typedef long long llong;
typedef unsigned long long ullong;
 
using namespace std;

llong n, k;
vector<vector<llong> > one(51, vector<llong> (51, 0));

vector<vector<llong> > mul(vector<vector<llong> > a, vector<vector<llong> > b){
    vector<vector<llong> > res(n, vector<llong> (n, 0));
    for(llong i = 0; i < n; i++){
        for(llong j = 0; j <n; j++){
            for(llong k = 0; k < n; k++){
                res[i][j] = (a[i][k] * b[k][j] + res[i][j]) % MOD;
            }
        }
    }
    return res;
}

vector<vector<llong> > binpow(vector<vector<llong> > a, llong b){
    if(b == 0) return one;
    if(b % 2 == 1){
        return mul(a, binpow(a, b - 1));
    }else{
        vector<vector<llong> > x = binpow(a, b / 2);
        return mul(x, x);
    }
}

int main () {
    ios;
    cin >> n >> k;
    for(llong i = 0; i < one.size(); i++){
        one[i][i] = 1;
    }
    vector<vector<llong> > v(n, vector<llong> (n, 0));
    for(llong i = 0; i < n; i++){
        for(llong j = 0; j < n; j++){
            llong x;
            cin >> x;
            v[i][j] = x;
        }
    }
    llong sum = 0;
    vector<vector<llong> > ans = binpow(v, k);
    for(llong i = 0; i < ans.size(); i++){
        for(llong j = 0; j < ans.size(); j++){
            sum = (sum + ans[i][j]) % MOD;
        }
    }
    cout << sum;
}


Measured memory_bytes: 2944
#include "bits/stdc++.h"

using namespace std;

int dr[] = {1, -1, 0, 0};
int dc[] = {0, 0, 1, -1};

int row, col;
int name[22][22];
char grid[22][22];
int mat[405][405];

bool inside(int r, int c) {
	return r >= 1 and r <= row and c >= 1 and c <= col;
}

signed main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	
	cin >> row >> col;
	int ptr = 0;
	for (int i = 1; i <= row; i++) {
		for (int j = 1; j <= col; j++) {
			cin >> grid[i][j];
			name[i][j] = ++ptr;
		}
	}
	for (int i = 1; i <= ptr; i++) {
		for (int j = 1; j <= ptr; j++) {
			mat[i][j] = 1e9;
		}
	}

	for (int i = 1; i <= row; i++) {
		for (int j = 1; j <= col; j++) {
			if (grid[i][j] == '#') {
				continue;
			}
			int u = name[i][j];
			mat[u][u] = 0;
			for (int k = 0; k < 4; k++) {
				int x = i + dr[k];
				int y = j + dc[k];
				if (inside(x, y) and grid[x][y] == '.') {
					int v = name[x][y];
					mat[u][v] = mat[v][u] = 1;
				}
			}
		}
	}
	for (int k = 1; k <= ptr; k++) {
		for (int i = 1; i <= ptr; i++) {
			for (int j = 1; j <= ptr; j++) {
				mat[i][j] = min(mat[i][j], mat[i][k] + mat[k][j]);
			}
		}
	}
	int maxDist = 0;
	for (int i = 1; i <= ptr; i++) {
		for (int j = 1; j <= ptr; j++) {
			 if (mat[i][j] < 1e9) {
				maxDist = max(maxDist, mat[i][j]);
			}
		}
	}
	cout << maxDist << endl;
}

Measured memory_bytes: 4264
S = input()
Q = int(input())

c = 0
R = ""
L = ""
for _ in range(Q):
    T = input().split()
    if len(T) == 1:
        c +=1
    else:
        if T[1] == "1":
            if c % 2 == 0:
                L = T[2] + L
            else:
                R = R + T[2]
        else:
            if c % 2 == 0:
                R = R + T[2]
            else:
                L = T[2] + L
if c % 2 == 0:
    print(L + S + R)
else:
    print("".join(list(reversed(L+S+R))))

Measured memory_bytes: 5980
#include<bits/stdc++.h>
#define REP(i,n) for(int i=0;i<(n);i++)
#define ALL(v) (v).begin(),(v).end()
#define int long long
using namespace std;
typedef vector<int>   vint;
typedef pair<int,int> pint;

int cnt[50];

signed main()
{
    int N,K; cin>>N>>K;
    vint a(N); REP(i,N) cin>>a[i];

    REP(i,N) REP(j,50){
        if((a[i]>>j)&1) cnt[j]++;
    }

    int ans=0;
    K++;
    REP(i,50){
        if(!((K>>i)&1)) continue;

        int sum=0;
        REP(j,i)
            sum+=(1LL<<j)*max(cnt[j],N-cnt[j]);
        sum+=(1LL<<i)*cnt[i];
        for(int j=i+1;j<50;j++){
            if((K>>j)&1)
                sum+=(1LL<<j)*(N-cnt[j]);
            else
                sum+=(1LL<<j)*cnt[j];
        }
        ans=max(ans,sum);
    }
    cout<<ans<<endl;

}


Measured memory_bytes: 1024
#pragma region declaration
#include <iostream>
#include <vector>
#include <array>
#include <numeric>
#include <algorithm>
#include <set>
#include <deque>
using namespace std;
using ll = long long;
constexpr double INF{ 1e9 };
constexpr int MOD{ 1000000000 + 7 };
#define rep(i,n) for (int i = 0; i < n; ++i)
constexpr array<int, 4> dy{ -1, 1, 0, 0 };
constexpr array<int, 4> dx{ 0, 0, -1, 1 };
constexpr int div_ru(int a, int b)
{
    return (a - b + 1) / b;
}
ll pow_mod(ll b, ll e, ll m)
{ // https://atcoder.jp/contests/atc002/tasks/atc002_b
    ll r = 1;
    for (; e > 0; e >>= 1)
    {
        if (e & 1)
            r = (r * b) % m;
        b = (b * b) % m;
    }
    return r;
}
#pragma endregion
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);

    ll s, c;
    cin >> s >> c;

    ll ans = 0;

    if (s * 2 >= c) {
        ans = c/2;
    }    else {
        c -= s * 2;
        const ll rm_scc = c / 4;
        ans = s + max(rm_scc, ll(0) );
    }

    cout << ans << endl;
}
// vector<vector<int>> mm(h, vector<int>(w, -1));


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

int main(){
  int n,k;
  cin>>n>>k;
  int mx = (n-1)*(n-2)/2;
  if(k<0 || k>mx){
    cout<<"-1"<<endl;
  } else {
    vector<pair<int,int>> G;
    for(int i=2;i<=n;++i){
      G.push_back(make_pair(1,i));
    }
    int curr = 2;
    int diff = 1;
    while(mx>k){
      G.push_back(make_pair(curr,curr+diff));
      diff ++;
      k++;
      if(curr+diff > n){
        curr++;
        diff=1;
      }
    }
    cout<<G.size()<<endl;
    for(auto i:	G){
      cout<<i.first<<" "<<i.second<<endl;
    }
  }
  return 0;
}

Measured memory_bytes: 384
import java.util.*;
public class Main {
 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int[] daikeihen = new int[3];
        for(byte i = 0;i <= 2; i++){
      	daikeihen[i] = sc.nextInt();
        }System.out.println((daikeihen[0] + daikeihen[1]) * daikeihen[2] / 2);
    }
}

Measured memory_bytes: 21844
#include<bits/stdc++.h>
#define MP make_pair
#define PB push_back
#define PF push_front
#define POB pop_back
#define POF pop_front
#define F first
#define S second
#define sz(c) (c).size()
#define REP(i,n)  for(ll i=0;i<n;i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=b;i++)
#define FORD(i,a,b) for(ll i=a;i>=b;i--)

#define bit(num,i) ((num>>i)&1)

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;

const ll inf=4e18;
const ll maxn=52;
const ll mod=1e9+7;

#pragma GCC Optimize("Ofast")

bool dp[maxn][maxn][maxn];// x,y,op
ll b[maxn],n;
bool nw[maxn][maxn];

ll next(){
	ll l=0,r=maxn-1,id=-1;
	while(l<=r){
		ll mid=(l+r)/2;
		bool yes=1;
		REP(i,n){
			bool bl=0;
			REP(j,maxn){
				if(nw[i][j]){
					bl|=dp[j][b[i]][mid];
				}
			}
			yes&=bl;
		}
		if(yes){
			id=mid;
			r=mid-1;
		}
		else{
			l=mid+1;
		}
	}
	return id;
}

ll Pow(ll a,ll b){
	ll an=1;
	while(b>0){
		if(b%2)
			an*=a;
		a*=a;
		b/=2;
	}
	return an;
}

int main(){
	REP(i,maxn)
		dp[i][i][0]=1;
	FOR(op,1,(maxn-1))
		REP(x,maxn)
			REP(y,maxn)
				dp[x][y][op]=(dp[x][y][op-1]|dp[x%op][y][op-1]);
	cin>>n;
	REP(i,n){
		ll x;cin>>x;
		nw[i][x]=1;
	}
	REP(i,n){
		cin>>b[i];
	}
	ll ans=0;
	while(true){
		ll nxt=next();
		if(nxt==-1){
			cout<<-1;
			return 0;
		}
		if(nxt==0)
			break;
		ans+=Pow(2,nxt);
		REP(i,n){
			REP(j,maxn){
				if(!nw[i][j])
					continue;
				if(!dp[j][b[i]][nxt-1])
					nw[i][j]=0;
				if(dp[j%nxt][b[i]][nxt-1])
					nw[i][j%nxt]=1;
			}
		}
	}
	cout<<ans;
}

Measured memory_bytes: 384
x, y, z, k = map(int,input().split())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
C = list(map(int,input().split()))

A.sort(reverse=1)
B.sort(reverse=1)
C.sort(reverse=1)

D = [0] * (min(k, x) * min(k, y))

for i in range(min(k, x)):
    for j in range(min(k, y)):
        D.append(A[i] + B[j])

D.sort(reverse=1)
E = [0] * (min(k, len(D)) * min(k, z))

for i in range(min(k, len(D))):
    for j in range(min(k, z)):
        E.append(D[i] + C[j])

E.sort(reverse=1)

for i in range(k):
    print(E[i])

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

#define ALL(c) (c).begin(), (c).end()
#define CALL(c) (c).cbegin(), (c).cend()
#define RALL(c) (c).rbegin(), (c).rend()
#define CRALL(c) (c).crbegin(), (c).crend()
#define REP(i, n) for (int i = 0; i < static_cast<int>(n); i++)
#define FOR(i, s, n) for (int i = s; i < static_cast<int>(n); i++)
#define PSORT(s,p,e) partial_sort((s), next((s), (p)), (e))
#define VIEW(v,t) for_each((v).begin(), (v).end(), [](t& a) { cout << a << " "; }); cout << endl;

const int INF = INT_MAX;
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, -1, 0, 1};

using PII = pair<int, int>;
using PLL = pair<long long, long long>;
using LL = long long;
using ULL = unsigned long long;
template<class T> using V = vector<T>;
template<class T> using V2 = vector<vector<T>>;
template<class T, int W=255> using A = array<T, W>;
template<class T, int W=255, int H=255> using A2 = array<array<T, W>, W>;

template<int N=255>
class UnionFindTree {
public:
  const LL len = N;
  A<LL, N> uftq{};
  A<LL, N> s{};
  A<LL, N> rank{};

  UnionFindTree(LL &n) {
    FOR(i,0,n) {
        uftq[i] = i;
        s[i] = 1;
        rank[i] = 1;
    }
  }
  LL find(LL& x) {
      LL xParent = uftq[x];
      V<LL> v;
      while(xParent != uftq[xParent]) {
          v.push_back(xParent);
          xParent = uftq[xParent];
      }
      REP(i, v.size()) {
          uftq[v[i]] = xParent;
      }
      return xParent;
  }
  LL size(LL& idx) {
      return s[find(idx)];
  }
  bool unite(LL& x, LL& y) {
      LL xRoot = find(x);
      LL yRoot = find(y);
      if(xRoot == yRoot) return false;
      if(rank[xRoot] > rank[yRoot])
          std::swap(xRoot, yRoot);
      if(rank[xRoot] == rank[yRoot])
          rank[yRoot] += 1 + rank[yRoot] - rank[xRoot];
      s[yRoot] = s[xRoot] + s[yRoot];
      s[xRoot] = 0;
      uftq[xRoot] = yRoot;
      return true;
  }
};


LL n, m;
V<LL> ai;
V<LL> bi;
V<LL> ans;

int main(){
    std::cin.tie(0);
    std::ios::sync_with_stdio(false);
    cin >> n; cin >> m;
    UnionFindTree<100001> uft{n};
    REP(i, m) {
        LL a, b;
        cin >> a; cin >> b;
        ai.push_back(a-1);
        bi.push_back(b-1);
    }

    LL f = (n * (n - 1)) / 2;
    ans.push_back(f);
    for(int i = m-1; i >= 0; i--) {
        LL x = uft.size(ai[i]);
        LL y = uft.size(bi[i]);
        if(uft.unite(ai[i], bi[i]) && (f - (x*y) >= 0)) f -= (x*y);
        ans.push_back(f);
    }
    for(int i=m-1; i >= 0; i--) {
        cout << ans[i] << "\n";
    }
}

Measured memory_bytes: 6124
import java.math.BigDecimal;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Scanner;

class DiscountedItem {
    final long original;
    int count;

    DiscountedItem(long value){
        this.original = value;
    }

    double actualPayment(){
        return original / Math.pow(2, count);
    }

    long actualPaymentExact(){
        return new BigDecimal(original).divideToIntegralValue(new BigDecimal(2).pow(count)).longValueExact();
    }
}

class Solver {
    void solve(Scanner sc) {
        int N = sc.nextInt();
        int M = sc.nextInt();
        PriorityQueue<DiscountedItem> A = new PriorityQueue<>(Comparator.comparingDouble(DiscountedItem::actualPayment).reversed());
        for (int i = 0; i < N; i++) {
            A.add(new DiscountedItem(sc.nextLong()));
        }
        for (int i = 0; i < M; i++) {
            DiscountedItem peek = A.remove();
            peek.count++;
            A.add(peek);
        }
        System.out.println(A.stream().mapToLong(DiscountedItem::actualPaymentExact).sum());
    }
}

class Main {
    public static void main(String... args) {
        Scanner in = new Scanner(System.in);

        new Solver().solve(in);

        in.close();
    }
}

Measured memory_bytes: 67184
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, a, b) for (int i = a; i < b; i++)
#define all(v) v.begin(), v.end()
const int MOD = 1e9 + 7;
const int INF = 1e9;
//'A' = 65, 'Z' = 90, 'a' = 97, 'z' = 122

int main() {
    ll n;
    cin >> n;
    ll a[n], b[n];

    rep(i, 0, n) {
        cin >> a[i];
        b[i] = a[i];
    }
    sort(b, b + n, greater<ll>());

    if (b[0] == b[1]) {
        rep(i, 0, n) {
            cout << b[0] << endl;
        }
    } else {
        rep(i, 0, n) {
            if (a[i] == b[0]) cout << b[1] << endl;
            else cout << b[0] << endl;
        }
    }


    return 0;
}


Measured memory_bytes: 4736
#include <cstdint>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>

int main(void)
{
    uint32_t a, b;

    std::cin >> a >> b;

    uint32_t min = std::min(a, b);
    uint32_t max = std::max(a, b);

    uint32_t sum = 0;

    for (uint32_t i=min; i<=max; ++i) {
        std::string str = std::to_string(i);
        if (str.at(0) != str.at(4)) continue;
        if (str.at(1) != str.at(3)) continue;
        sum++;
    }

    std::cout << sum << std::endl;

    return 0;
}


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

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

    int r;
    cin >> r;

    if(r<1200) puts("ABC");
    else if(1200<=r && r<2800) puts("ARC");
    else puts("AGC");
}

Measured memory_bytes: 256
#include<iostream>
#include <stdio.h>
using namespace std;

void trace(int A[], int n) {
  int i;
  for(i=0; i<n; i++) {
    if (i>0) {
      printf(" ");
    }
    printf("%d", A[i]);
  }
  printf("\n");
}

void InsertionSort(int A[], int n) {
  int i, j, v;

  for (i=0; i<n; i++) {
    v = A[i];
    j = i-1;
    while (j >= 0 && A[j] > v) {
      A[j+1] = A[j];
      j--;
    }
    A[j+1] = v;
    trace(A, n);
  } 
}

int main() {
  int n;
  int A[1000];
  scanf("%d", &n);
  for (int i=0; i<n; i++) {
    scanf("%d", &A[i]);
  }
  InsertionSort(A, n);

  return 0;
}


Measured memory_bytes: 3220
#include <bits/stdc++.h>
#include <unistd.h>
 
using namespace std;
 
typedef long long ll;
typedef pair<ll,ll> P;
 
long long int INF = 3e18;
const ll fact_table = 5000000;
double Pi = 3.1415926535897932384626;
 
//vector<ll> G[550010];
vector<P> tree[500010];
priority_queue <ll> pql;
priority_queue <P> pqp;
//big priority queue
priority_queue <ll,vector<ll>,greater<ll> > pqls;
priority_queue <P,vector<P>,greater<P> > pqps;
//small priority queue
//top pop
 
int dx[8]={1,0,-1,0,1,1,-1,-1};
int dy[8]={0,1,0,-1,1,-1,-1,1};
char dir[] = "DRUL";
//ll bit[500005];
//↓,→,↑,←
 
 
#define p(x) cout<<x<<"\n";
#define el cout<<endl;
#define pe(x) cout<<(x)<<" ";
#define ps(x) cout<<fixed<<setprecision(25)<<x<<endl;
#define pu(x) cout<<(x);
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define CLEAR(a) a = decltype(a)(); 
 
 
ll mod = 998244353;
//ll mod = 1000000007;
 
ll rui(ll number1,ll number2){
 
    if(number2 == 0){
        return 1;
    }else{
        ll number3 = rui(number1,number2 / 2);
        number3 *= number3;
        number3 %= mod;
        if(number2%2==1){
            number3 *= number1;
            number3 %= mod;
        }
        return number3;
    }
}
ll gcd(ll number1,ll number2){
 
    if(number1 > number2){
        swap(number1,number2);
    }
    if(number1 == 0 || number1 == number2){
        return number2;
    }else{
        return gcd(number2 % number1,number1);
    }
}
void YES(bool condition){
 
    if(condition){
        p("YES");
    }else{
        p("NO");
    }
    return;
}
void Yes(bool condition){
 
    if(condition){
        p("Yes");
    }else{
        p("No");
    }
    return;
}
 
/*
ll fact[fact_table + 5],rfact[fact_table + 5];
 
void c3_init(){
    fact[0] = rfact[0] = 1;
    for(ll i=1; i<=fact_table; i++){
        fact[i] = (fact[i-1]*i) % mod;
    }
    rfact[fact_table] = rui(fact[fact_table],mod - 2);
    for(ll i=fact_table; i>=1; i--){
       rfact[i-1] = rfact[i] * i;
       rfact[i-1] %= mod;
    }
    return;}
ll c3(ll n,ll r){
    return (((fact[n] * rfact[r]) % mod ) * rfact[n-r]) % mod;}
*/
 
ll n,m,num,sum,a,b,c,d,e,g,h,w,i,j,q,r,l;
ll k,idx,ans;
ll x[500005],y[500005],z[500005];
char s[500005];

int main(){
    cin >> n;
    ll maxi = 0;
    for(int i=0;i<n;i++){
        cin >> x[i];
        maxi = max(maxi, x[i]);
    }
    bool dame = false;
    for(int i=1;i<n;i++){
        if(x[i] == 0)dame = true;
    }
    if(x[0] != 0)dame = true;
    for(int i=0;i<n;i++){
        y[x[i]] ++;
    }
    ans = 1;
    num = 1;
    for(int i=1;i<=maxi;i++){
        ans *= rui(num, y[i]);
        num = y[i];
        ans %= mod;
    }
    if(dame){
        p(0);
    }else{
        p(ans);
    }
    return 0;
}


















Measured memory_bytes: 18048
#include <algorithm>
#include <iostream>
#include <math.h>
#include <stdio.h>
#include <string>
#include <sstream>
#include <vector>
#include <stack>
#include <set>
#include <map>
#include <cmath>
#include <queue>
#include <deque>
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
using namespace std;
typedef unsigned long long int ll;


int main()
{
	ll N,T;
	cin>>N>>T;
	ll sum = T * N;
	ll *t = new ll[N];
	cin>>t[0];
	for(int i = 1; i < N; i++){
		cin>>t[i];
		if( T > (t[i] - t[i-1])){
			ll deltaT = t[i] - t[i-1];
			sum -= (T - deltaT);
		}
	}
	cout<<sum<<endl;
	return 0;
}



Measured memory_bytes: 1792
#include<bits/stdc++.h>
using namespace std;
#define ll long long int 
#define ld long double
#define mod 1000000007
#define endl "\n"
#define pb push_back
#define mp make_pair
int main()
{
    ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	ll i,j,x,y,an=0,c=0;
	vector<vector<ll> > a(27);
	string s,t;
	cin>>s>>t;
	for(i=0;i<s.length();i++)
	{
		a[s[i]-'a'].pb(i+1);
	}
	for(i=0;i<t.length();i++)
	{
		if(a[t[i]-'a'].size()==0)
		{
			cout<<-1;
			return 0;
		}
		auto p=lower_bound(a[t[i]-'a'].begin(),a[t[i]-'a'].end(),c);
		if(*p==c)
		{
			p++;
		}
		if(p!=a[t[i]-'a'].end())
		{
			an+=*p-c;
			c=*p;
		}
		else
		{	
			an+=s.length()-c;
			an+=a[t[i]-'a'][0];
			c=a[t[i]-'a'][0];
		}
	}
	cout<<an;	
	return 0;
}

Measured memory_bytes: 1736