akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);++i)
#define FOR(i,n,j) for(int i=(j);i<(n);++i)
#define ssort(n) sort((n).begin(),(n).end())
#define rsort(n) sort((n).begin(),(n).end(),greater<ll>())
#define mp make_pair
using ll=long long;
using ld=long double;
typedef pair<int,int> P;
typedef pair<P,int> COST;
#define repl(i,n) for(ll i=0;i<(n);++i)
#define Yes cout << "Yes" << endl
#define No cout << "No" << endl
#define YES cout << "YES" << endl
#define NO cout << "NO" << endl
using Graf=vector<vector<int>>;
#define MAX 1000000007

int main()
{
    int n;
    cin >> n;
    vector<ll> a(n),b(n);
    vector<ll> plus_val,minus_val;
    vector<bool> flag_plus,flag_minus;
    rep(i,n)cin >> a[i];
    rep(i,n)cin >> b[i];
    rep(i,n)a[i]-=b[i];
    ll ans=0;int p,q;p=0;q=0;
    rep(i,n){
        if(a[i]>0){
            plus_val.push_back(a[i]);
            flag_plus.push_back(false);
        }else if(a[i]<0){
            minus_val.push_back(a[i]);
            flag_minus.push_back(false);
        }
    }
    if(!minus_val.empty()){
        ssort(minus_val);
    }else{
        cout << 0 << endl;
        return 0;
    }
    if(!plus_val.empty())rsort(plus_val);

    while(p<plus_val.size()&&q<minus_val.size()){
        if(abs(plus_val[p])==abs(minus_val[q])){
            flag_plus[p]=true;flag_minus[q]=true;
            p++;q++;
        }else if(abs(plus_val[p])<abs(minus_val[q])){
            flag_plus[p]=true;flag_minus[q]=true;
            minus_val[q]+=plus_val[p];
            p++;
        }else{
            flag_plus[p]=true;flag_minus[q]=true;
            plus_val[p]+=minus_val[q];
            q++;
        }
    }
    if(q==minus_val.size()){
        rep(i,plus_val.size()){
            if(flag_plus[i]==true){
                ans++;
            }
        }
        rep(i,minus_val.size()){
            if(flag_minus[i]==true){
                ans++;
            }
        }
        cout << ans << endl;
    }else{
        cout << -1 << endl;
    }

}

Measured memory_bytes: 5880
#include <bits/stdc++.h>
#define st first
#define nd second

using namespace std;

void debug_out() { cerr << endl; }
template<class T> ostream& prnt(ostream& out, T v) {  for(auto e : v) out << e << '\n'; return out;}
template<class T> ostream& operator<<(ostream& out, vector <T> v) { return prnt(out, v); }
template<class T> ostream& operator<<(ostream& out, set <T> v) { return prnt(out, v); }
template<class T1, class T2> ostream& operator<<(ostream& out, map <T1, T2> v) { return prnt(out, v); }
template<class T1, class T2> ostream& operator<<(ostream& out, pair<T1, T2> p) { return out << p.st << ' ' << p.nd; }
template <typename Head, typename... Tail> void debug_out(Head H, Tail... T) { cerr << " " << H; debug_out(T...);}

#define dbg(...) cerr << #__VA_ARGS__ << " ->", debug_out(__VA_ARGS__)
#define dbg_v(x, n) do{cerr<<#x"[]: ";for(int _=0;_<n;++_)cerr<<x[_]<<" ";cerr<<'\n';}while(0)
#define dbg_ok cerr<<"OK!\n"

// const int N = ;
int n;

vector <pair<int, int> > ans;

int main() {
	ios_base::sync_with_stdio(false);

	cin >> n;
	if(n <= 2 || __builtin_popcount(n) == 1) {
		cout << "No\n";
		return 0;
	}


	if(n % 2 == 1) {
		for(int i = 2 ;i <= n; i += 2) {
			ans.push_back({i, i ^ 1});
			ans.push_back({1, i});
			ans.push_back({1, n + (i ^ 1)});
			ans.push_back({n + (i ^ 1), n + i});
		}
		ans.push_back({n + 1, 3});
	} else {
		int x = n;
		int p = -1;
		while(x) x /= 2, p++;
		for(int i = 2 ;i < n; i += 2) {
			if(i == (1 << p)) continue;
			ans.push_back({i, i ^ 1});
			ans.push_back({1, i});
			ans.push_back({1, n + (i ^ 1)});
			ans.push_back({n + (i ^ 1), n + i});
		}
		ans.push_back({n + 1, 3});

		x = n;
		int y = (1 << p);
		int z = (x ^ y);
		dbg(x, y, z);
		ans.push_back({n + z, y});
		ans.push_back({n + z, x});
		ans.push_back({n + x, y});
		ans.push_back({y ^ 1, y});
		ans.push_back({n + z ^ 1, n + (y ^ 1)});
		ans.push_back({n + (y ^ 1), n + y});
	}
	
	cout << "Yes\n" << ans << '\n';


}	

	

Measured memory_bytes: 7152
#include<bits/stdc++.h>
using namespace std;
typedef long long int uli;
const int mx=60;
int x[mx],y[mx];
int main(){
   int n,tt=1;
   while(scanf("%d",&n)==1){
      if(n==0)break;
      for(int i=0;i<n;i++)
         scanf("%d %d",x+i,y+i);
      x[n]=x[0],y[n]=y[0];
      double area=0;
      for(int i=1;i<=n;i++){
         area+=(y[i]+y[i-1])*(x[i]-x[i-1]);
      }
      if(area<0)area*=-1;
      area*=0.5;
      printf("%d %.1lf\n",tt++,area);
   }
   return 0;
}

Measured memory_bytes: 1220
#include <iostream>
#include <vector>
#include <map>
// #include <unordered_map>

int main()
{
  int n;
  std::cin >> n;
  std::vector<int> q(n);
  for (int i = 0; i < n; i++)
  {
    std::cin >> q[i];
  }
  // std::vector<int> ms(m);
  std::map<int, bool> uo;
  for (int bit = 0; bit < 1<<n; bit++)
  {
    int sum = 0;
    for (int a = 0; a < n; a++)
    {
      if(bit & 1<<a)
      {
        sum += q[a];
      }
    }
    uo[sum] = true;

  }
  int m;
  std::cin>>m;
  for (int i = 0; i < m; i++)
  {
    int num;
    std::cin >> num;
    // std::cin >>ms[i];
    if(uo.count(num))
    {
      std::cout << "yes" << std::endl;
    }
    else
    {
      std::cout << "no" << std::endl;
    }


  }


}



Measured memory_bytes: 3124
/*
*	User: Isanchez_Aguilar
*	Problem: AtCoder ABC134B - Golden Apple
*/
#include <bits/stdc++.h>

using namespace std;
using Long = long long;

double dp[320][320][320];

int main(void)
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	int n;
	cin >> n;

	vector<int> freq(4);

	for (int i = 0; i < n; ++i)
	{
		int v;
		cin >> v;

		++freq[v];
	}

	for (int k = 0; k <= 300; ++k)
	{
		for (int j = 0; j <= 300; ++j)
		{
			for (int i = 0; i <= 300; ++i)
			{
				if (i + j + k == 0)
					dp[i][j][k] = 0;
				else
				{
					dp[i][j][k] = double(n) / double(i + j + k);
					
					if (i > 0)
						dp[i][j][k] += double(i) * dp[i - 1][j][k] / double(i + j + k);
					if (j > 0)
						dp[i][j][k] += double(j) * dp[i + 1][j - 1][k] / double(i + j + k);
					if (k > 0)
						dp[i][j][k] += double(k) * dp[i][j + 1][k - 1] / double(i + j + k); 	
				}
			}
		}
	}

	cout << fixed << setprecision(9) << dp[freq[1]][freq[2]][freq[3]];

	return 0;
}

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

using namespace std;

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

#define F first
#define S second

const int MAXN = 2e5 + 10;
const int LOG = 20;

int n, a[MAXN], nxt[MAXN];

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n;
	for (int i = 0; i < n; i++) cin >> a[i];
	int last = n;
	for (int i = n-1; ~i; i--){
		if (a[i])
			last = i;
		nxt[i] = last;
	}

	ll ans = 0;
	for (int l = 0; l < n; l++){
		int cur = 0, ind = l, sm = 0;
		while (ind < n){
			ind = nxt[ind];
			if (ind == n) break;
			cur ^= a[ind];
			sm += a[ind];
			if (sm ^ cur) break;
			ind++;
		}
		ans += ind - l;
	}
	cout << ans << "\n";
	return 0;
}


Measured memory_bytes: 1920
#include<bits/stdc++.h>
using namespace std;
using Graph = vector<vector<int>>;
#define ll long long
#define all(x) (x).begin(),(x).end()
#define rep(i, n) for(ll i = 0; i < n; i++)
const ll INF = 1LL << 60;

vector<bool> seen;
vector<int> values;
vector<int> ans;

void dfs(Graph &G, int v, int val){
    seen[v] = true;
    int tmp = val + values[v];
    ans[v] = tmp;
    for(auto next_v: G[v]){
        if(seen[next_v]) continue;
        dfs(G, next_v, tmp);
    }
}

int main(){
    int N, Q; cin >> N >> Q;
    Graph g(N);
    rep(i, N - 1){
        int a, b;
        cin >> a >> b;
        a--;
        b--;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    values.assign(N, 0);
    ans.assign(N, 0);
    rep(i, Q){
        int p, x; cin >> p >> x;
        p--;
        values[p] += x;
    }
    seen.assign(N, false);
    dfs(g, 0, 0);

    rep(i, N) cout << ans[i] << endl;
}

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

int main(){
	int A, B, C, X;
	cin >> A;
	cin >> B;
	cin >> C;
	cin >> X;

	int cnt = 0;
	for (int i = 0; i <= A; i++) {
		for (int j = 0; j <= B; j++) {
			for (int k = 0; k <= C; k++) {
				if (X == i * 500 + j * 100 + k * 50) {
					cnt++;
				}
			}
		}
	}
	cout << cnt << endl;
	return 0;
}


Measured memory_bytes: 256
K = int(input())

a = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]

if K <= len(a) and K >= 1:
  print(a[K-1])  

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

int main() {
  vector<int> vec;
  vec = {1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};
  int K;
  cin >> K;
  cout << vec.at(K-1) << endl;
}

Measured memory_bytes: 256
/*
CODED BY               
**************
DARSHAN JAIN
darshanjain31
**************
*/
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define pb push_back
#define mp make_pair
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL);
#define endl '\n'
#define MOD 1000000007
using namespace std;

int main()
{
	fast;
	ll t;
	cin>>t;
	ll dp[t+1]={0};
	for (int i = 0; i < t-1; ++i)
	{
		ll x;
		cin>>x;
		dp[x]++;
	}
	for (int i = 1; i <=t; ++i)
	{
		cout<<dp[i]<<endl;
	}
}







Measured memory_bytes: 5224
#include <stdio.h>

int table[30][30];
int main(void)
{
	int i, j, x, y, size, sum, max = 0;
	
	while (scanf("%d,%d,%d", &x, &y, &size) != EOF){
		x += 10;
		y += 10;
		table[x][y]++;
		
		if (size >= 1){
			table[x + 1][y]++;
			table[x - 1][y]++;
			table[x][y + 1]++;
			table[x][y - 1]++;
		}
		if (size >= 2){
			table[x - 1][y - 1]++;
			table[x + 1][y - 1]++;
			table[x - 1][y + 1]++;
			table[x + 1][y + 1]++;
		}
		if (size >= 3){
			table[x][y + 2]++;
			table[x][y - 2]++;
			table[x - 2][y]++;
			table[x + 2][y]++;
		}
	}
	
	sum = 0;
	
	for (i = 10; i < 20; i++){
		for (j = 10; j < 20; j++){
			if (table[i][j] == 0){
				sum++;
			}
			else if (table[i][j] > max){
				max = table[i][j];
			}
		}
	}
	printf("%d\n%d\n", sum, max);
	
	return (0);
}

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

struct UnionFind {
  vector<int> data;
  UnionFind() {}
  UnionFind(int n) : data(n, -1) {}
  bool same(int x, int y) { return root(x) == root(y); }
  int root(int x) { return (data[x] < 0) ? x : data[x] = root(data[x]); }
  int rank(int x) { return -data[root(x)]; }
  bool unite(int x, int y) {
    x = root(x);
    y = root(y);
    if (x != y) {
      if (data[y] < data[x]) swap(x, y);
      data[x] += data[y];
      data[y] = x;
    }
    return x != y;
  }
};
template<typename T> struct Graph {
  struct Edge { int s, t; T cost; };
  int sz;
  vector<Edge> es;
  Graph(int n = 0) : sz(n) {}

  void addEdge(int u, int v, T w) {
    sz = max(sz, max(u, v) + 1);
    es.push_back({u, v, w});
  }
  T kruskal() {
    UnionFind uf(sz);
    sort(begin(es), end(es), [](Edge e1, Edge e2) {
      return e1.cost < e2.cost;
    });
    T res = 0;
    for (auto&& e : es) {
      if (uf.unite(e.s, e.t)) res += e.cost;
    }
    return res;
  }
};

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

  int n, m; cin >> n >> m;
  Graph<ll> g(n);
  for (int i = 0; i < m; ++i) {
    ll s, t, w; cin >> s >> t >> w;
    g.addEdge(s, t, w);
  }
  cout << g.kruskal() << endl;
  return 0;
}



Measured memory_bytes: 4996
#include <bits/stdc++.h>
using namespace std;
#define FIN ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

int main() {FIN
    
    int i, j, ns, np;
    string s, p;
    bool is = false, ps;
    cin >> s;
    cin >> p;
    ns = s.size(), np = p.size();
    
    for (i = 0; i <= (2 * ns) - np; i++) {
        ps = true;
        for (j = 0; j < np; j++) {
            if (p[j] != s[(i + j) % ns]) {
                ps = false;
                break;
            }
        }
        if (ps) {
            is = true;
            break;
        }
    }
    cout << (is ? "Yes" : "No") << "\n";
    
    return 0;
}


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

const int maxn = 2e5+7;

int main(int argc, char *argv[]) {  
	long long n, a[maxn];
	std::cin >> n;
	for (int i = 0; i < n; i++) {
		std::cin >> a[i];
		a[i] -= (i+1);
	}
	std::sort(a, a+n);
	long long b = a[(n)/2];
	long long ans = 0;
	for (int i = 0; i < n; i++) {
		ans += std::abs(a[i]-b);
	}
	std::cout << ans;
}

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

#define rep(X, N) for (ll X = 0LL; X < (N); X++)
#define ALL(V) (V).begin(), (V).end()
#define endl "\n"

using namespace std;
typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;

const double PI = 3.1415926535897932384626;
const ll MODN = 1000000007;
const ll MODN2 = 998244353;

class UnionFind{
    vector<int> parent;
    vector<int> sizev;

public:
    UnionFind(){}
    UnionFind(int n){
        for(int i = 0; i < n; i++){
            parent.push_back(i);
            sizev.push_back(1);
        }
    }

    void merge(int a, int b){
        int pa = leader(a);
        int pb = leader(b);

        if(pa != pb){
            if(size(pa) < size(pb)) swap(pa, pb);
            parent[pb] = parent[pa];
            sizev[pb] += sizev[pa];
            sizev[pa] = sizev[pb];
        }
    }

    bool same(int a, int b){
        return leader(a) == leader(b);
    }

    int leader(int a){
        int tmp = parent[a];
        if(tmp == a) return a;

        tmp = leader(tmp);
        parent[a] = tmp;
        return tmp;
    }

    int size(int a){
        return sizev[leader(a)];
    }

    vector<vector<int>> groups(){
        vector<int> index(parent.size(), -1);
        int count = 0;
        for(int i = 0; i < parent.size(); i++){
            if(i == leader(i)){
                index[i] = count;
                count++;
            }
        }
        vector<vector<int>> result(count + 1);

        for(int i = 0; i < parent.size(); i++){
            int tmp = leader(i);
            result[index[tmp]].push_back(i);
        }

        return result;
    }
};

int main(){

    int n,m;
    cin >> n >> m;

    UnionFind uf(n + 1);

    rep(i, m){
        int a, b;
        cin >> a >> b;

        uf.merge(a, b);
    }

    int count = 0;

    rep(i, n){
        if(uf.leader(i + 1) == i + 1) count++;
    }

    cout << count - 1 << endl;


    return 0;
}


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

int main()
{
    int n;
    std::cin>>n;
    long long ans = 0;
    for(int i=0;i<n;i++){
        int a;
        std::cin>>a;
        ans += a-1;
    }
    std::cout<<ans<<std::endl;
}

Measured memory_bytes: 256
ii = lambda:int(input())
mi = lambda:list(map(int,input().split()))
ix = lambda x:list(input() for _ in range(x))
mix = lambda x:list(mi() for _ in range(x))
iix = lambda x:list(int(input()) for _ in range(x))
##########

def resolve():
    a,b = mi()
    print(a*b)

if __name__ == "__main__":
    resolve()

Measured memory_bytes: 9176
#include <bits/stdc++.h>
//#include <boost/multiprecision/cpp_int.hpp>
//namespace mp = boost::multiprecision;
//#include "atcoder/all"

using namespace std;

const double PI = 3.14159265358979323846;
typedef long long ll;
const double EPS = 1e-9;
#define rep(i, n) for (int i = 0; i < (n); ++i)
typedef pair<ll, ll> P;
const ll INF = 10e17;
#define cmin(x, y) x = min(x, y)
#define cmax(x, y) x = max(x, y)
#define ret() return 0;

double equal(double a, double b) {
    return fabs(a - b) < DBL_EPSILON;
}

std::istream &operator>>(std::istream &in, set<int> &o) {
    int a;
    in >> a;
    o.insert(a);
    return in;
}

std::istream &operator>>(std::istream &in, queue<int> &o) {
    ll a;
    in >> a;
    o.push(a);
    return in;
}

bool contain(set<int> &s, int a) { return s.find(a) != s.end(); }

typedef priority_queue<ll, vector<ll>, greater<ll> > PQ_ASK;

ll solve() {
    int n;
    cin >> n;
    ll ans = 0;
    for (int i = 1; i < n; i++) {
        int b = n / i;
        if (i * b == n) b--;
        ans += b;
    }
    return ans;
}

int main() {
    cout << solve() << endl;
}


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

vector<int> xs, ys;
vector<vector<bool> > dpx, dpy;
int main() {
  string s;
  cin >> s;
  int x, y;
  cin >> x >> y;

  int l = s.length();
  int buf = 0;
  bool is_x = true;
  for (int i = 0; i < l; i++) {
    if (s[i] == 'T') {
      if (is_x) {
        xs.push_back(buf);
      } else {
        ys.push_back(buf);
      }
      is_x = !is_x;
      buf = 0;
    } else {
      buf++;
    }
  }
  if (buf != 0) {
    if (is_x) {
      xs.push_back(buf);
    } else {
      ys.push_back(buf);
    }
  }

  dpx = vector<vector<bool> >(xs.size() + 1, vector<bool> (2 * l + 1, false));
  dpx[1][l + xs[0]] = true;
  for (int i = i; i < xs.size(); i++) {
    for (int p = 0; p <= 2 * l; p++) {
      if (dpx[i][p]) {
        dpx[i + 1][p + xs[i]] = true;
        dpx[i + 1][p - xs[i]] = true;
      }
    }
  }

  dpy = vector<vector<bool> >(xs.size() + 1, vector<bool> (2 * l + 1, false));
  dpy[0][l] = true;
  for (int i = 0; i < ys.size(); i++) {
    for (int p = 0; p < 2 * l; p++) {
      if (dpy[i][p]) {
        dpy[i + 1][p + ys[i]] = true;
        dpy[i + 1][p - ys[i]] = true;
      }
    }
  }

  if (dpx[xs.size()][x + l] && dpy[ys.size()][y + l]) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }
  return 0;
}

Measured memory_bytes: 16128
package main

import (
	"fmt"
)

func main() {
	var n int
	fmt.Scan(&n)
	var cnt = 0
	for i := 0; i <= n; i++ {
		for j := 0; j <= n; j++ {
			if 4*i+7*j == n {
				cnt++
			}
		}
	}
	if cnt != 0 {
		fmt.Println("Yes")
	} else {
		fmt.Println("No")
	}
}


Measured memory_bytes: 512
# E - Handshake

N, M = map(int, input().split())
A = list(int(x) for x in input().split())

A.sort(reverse=True)

S = []
S.append(A[0])
for i in range(N-1):
    S.append(S[i]+A[i+1])
S.append(0)

# 幸福度がX以上となる握手がM以上になることを考える
# つまり、幸福度がXより大きい(X+1以上)の握手と
# 幸福度がXの握手を足すとM以上

def CheckHappy(x):
    X = list(map(lambda y: x - y, A))
    cnt = 0
    happy = 0
    for i in range(N):
        l = -1
        r = N
        while l+1 < r:
            m = (l+r)//2
            if A[m] >= X[i]:
                l = m
            else:
                r = m 
        cnt += l+1
        if l>=0:
            #print(A[i], S[l])
            happy += A[i]*(l+1)+S[l]
    #print('cnt, happy', cnt, happy)
    return cnt, happy

def isGreaterThanM(x):
    X = list(map(lambda y: x - y, A))
    #print('X',X)
    cnt = 0
    for i in range(N):
        l = -1
        r = N
        #print('l, r', l, r)
        while l+1 < r:
            m = (l+r)//2
            if A[m] >= X[i]:
                l = m
            else:
                r = m 
        cnt += l+1
        #print('cnt',cnt)
        if cnt >= M:
            return True
    return False


# 2分探索
left = min(A)*2-1
right = max(A)*2+1

while left+1 < right:
    mid = (left+right)//2
    if isGreaterThanM(mid):
        left = mid
    else:
        right = mid

#print('left, right', left, right)

tmp, ans = CheckHappy(right)
ans += (M-tmp)*left
print(ans)




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

template <class Abel> struct BIT {
    vector<Abel> dat[2];
    Abel UNITY_SUM = 0;                     // to be set
    
    /* [1, n] */
    BIT(int n) { init(n); }
    void init(int n) { for (int iter = 0; iter < 2; ++iter) dat[iter].assign(n + 1, UNITY_SUM); }
    
    /* a, b are 1-indexed, [a, b) */
    inline void sub_add(int p, int a, Abel x) {
        for (int i = a; i < (int)dat[p].size(); i += i & -i)
            dat[p][i] = dat[p][i] + x;
    }
    inline void add(int a, int b, Abel x) {
        sub_add(0, a, x * -(a - 1)); sub_add(1, a, x); sub_add(0, b, x * (b - 1)); sub_add(1, b, x * (-1));
    }
    
    /* a is 1-indexed, [a, b) */
    inline Abel sub_sum(int p, int a) {
        Abel res = UNITY_SUM;
        for (int i = a; i > 0; i -= i & -i) res = res + dat[p][i];
        return res;
    }
    inline Abel sum(int a, int b) {
        return sub_sum(0, b - 1) + sub_sum(1, b - 1) * (b - 1) - sub_sum(0, a - 1) - sub_sum(1, a - 1) * (a - 1);
    }
    /* debug */
    void print() {
        for (int i = 1; i < (int)dat[0].size(); ++i) cout << sum(i, i + 1) << ",";
        cout << endl;
    }
};

int main() {
    int N; cin >> N;
    int Q; cin >> Q;
    vector<int> a(N);
    for (int i = 0; i < N; ++i) cin >> a[i];

    
    vector<int> lefts(Q), rights(Q), ids(Q);
    for (int i = 0; i < Q; ++i) {
        cin >> lefts[i] >> rights[i];
        --lefts[i];
        ids[i] = i;
    }
    sort(ids.begin(), ids.end(), [&](int i, int j) {
            return rights[i] < rights[j];});

    BIT<int> bit(N+5);
    vector<int> prev(1100000, -1);
    vector<int> res(Q, 0);
    int r = 0;
    for (auto i : ids) {
        for (; r < rights[i]; ++r) {
            bit.add(prev[a[r]]+2, r+2, 1);
            prev[a[r]] = r;
        }
        int tmp = bit.sum(lefts[i]+1, lefts[i]+2);
        res[i] = max(res[i], tmp);
    }
    for (int i = 0; i < Q; ++i) cout << res[i] << endl;
}

/*
cd ~/Desktop/Programming/AtCoder/practice/abc174/abc174_f && sh shellscripts/test_cpp.sh
*/

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

int main() {
    int e[4];
    REP(i,4) cin >> e[i];
    sort(e,e+4);
    cout <<(e[0]==e[1] && e[2]==e[3]?"yes":"no") << endl;
    return 0;
}



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

using namespace std;
typedef long long ll;

int main()
{
	int a, b;
	scanf("%d%d", &a, &b);
	int res = a / b;
	a -= res * b;
	if(a > 0) res ++;
	printf("%d\n", res);
	return 0;
}


Measured memory_bytes: 256
from itertools import*
from math import*
from collections import*
from heapq import*
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf = float("inf")
mod = 10**9+7
from functools import reduce
import sys
sys.setrecursionlimit(10**7)

N = int(input())
a = list(map(int,input().split()))
a.sort()
minus = -1
for i in range(N):
    if a[i] < 0:
        minus +=1
    else:
        break

q = deque(a)
if max(a) >= 0 and min(a)<0:
    ans = 0
    for i in range(N):
        ans += abs(a[i])
    print(ans)
    for i in range(minus):
        x = q.pop()
        y = q.popleft()
        print(x,y)
        q.append(x-y)
    for i in range(N-minus-2):
        x = q.popleft()
        y = q.pop()
        print(x,y)
        q.appendleft(x-y)
    print(q[1],q[0])
elif max(a)<0:
    print(-sum(a)+2*a[-1])
    for i in range(N-1):
        x = q.pop()
        y = q.popleft()
        print(x,y)
        q.append(x-y)
else:
    print(sum(a)-2*a[0])
    for i in range(N-2):
            x = q.popleft()
            y = q.pop()
            print(x,y)
            q.appendleft(x-y)
    print(q[1],q[0])

Measured memory_bytes: 65696
n = int(input())
A = list(map(int, input().split()))

for i in range(n):
    v = A[i]
    j = i - 1

    while j>=0 and A[j]>v :
        A[j+1] = A[j]
        j -= 1

    A[j+1] = v

    print(" ".join(map(str, A)))


Measured memory_bytes: 5596
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;

namespace cysharp_test
{
    class Program
    {
        static void Main (string[] args)
        {
            new Program ().solve ();
        }

        void solve ()
        {
            int[] NM = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();

            int N = NM[0];
            int M = NM[1];

            int[] A = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();

            if(N - A.Sum() >= 0)Console.WriteLine(N - A.Sum());
            else Console.WriteLine("-1");
        }

    }

    class Vector2
    {
        public Vector2 (long x, long y)
        {
            this.x = x;
            this.y = y;
        }

        long x, y;

        public static Vector2 operator + (Vector2 a, Vector2 b)
        {
            return new Vector2 (a.x + b.x, a.y + b.y);
        }

        public static Vector2 operator - (Vector2 a, Vector2 b)
        {
            return new Vector2 (a.x - b.x, a.y - b.y);
        }

        public static Vector2 operator * (Vector2 a, long scala)
        {
            return new Vector2 (a.x * scala, a.y + scala);
        }
    }
}

Measured memory_bytes: 20408
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,k;
    cin>>n>>k;
    int a[n];
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    int dp[100001];
    dp[0]=0;
    for(int i=1;i<n;i++){
            dp[i]=1e9;
        for(int j=i-1;j>=max(0,i-k);j--){
            dp[i]=min(dp[i],dp[j]+abs(a[i]-a[j]));
        }
    }
    cout<<dp[n-1]<<endl;
return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define FOR(i, a, b) for(int i=(a); i<(b); i++)
#define REP(i, n) FOR(i, 0, n)
#define all(x) (x).begin(), (x).end()
#define bit(x) (1L << (x))
using ll = long long;
using namespace std;

using Graph = vector<vector<int>>;

vector<int> t_sort(const Graph& g){
  int n = g.size();
  vector<int> sorted;
  vector<int> in(n, 0);

  for(int v=0; v<n; v++){
    for(const auto& to: g[v]){
      in[to]++;
    }
  }

  queue<int> que;

  for(int i=0; i<n; i++){
    if(in[i] == 0){
      que.push(i);
    }
  }

  while(!que.empty()){
    int now = que.front(); que.pop();
    sorted.emplace_back(now);
    for(const auto& to: g[now]){
      in[to]--;
      if(in[to] == 0){
        que.push(to);
      }
    }
  }

  return sorted;
}

int main(){
  int n, m; cin >> n >> m;
  Graph g(n);
  REP(i, m){
    int x, y; cin >> x >> y;
    //x--; y--;
    g[x].emplace_back(y);
  }

  vector<int> sorted = t_sort(g);
  for(const auto& node: sorted){
    cout << node << endl;
  }

  return 0;
}



Measured memory_bytes: 3720
import java.io.*;
import java.math.*;
import java.text.*;
import java.util.*;
import java.util.regex.*;

public class Main {

    public static int MOD = 1000000007;

    public static int totalPaths(char[][] grid) {
        int h = grid.length;
        int w = grid[0].length;

        int[][] dp = new int[h][w];
        dp[0][0] = 1;
        for(int i = 0; i < h; i++) {
            for(int j = 0; j < w; j++) {
                if(grid[i][j] == '.') {
                    if(j >= 1) dp[i][j] = (dp[i][j] + dp[i][j - 1]) % MOD;
                    if(i >= 1) dp[i][j] = (dp[i][j] + dp[i - 1][j]) % MOD;
                }
            }
        }
        return dp[h - 1][w - 1] % MOD;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int h = sc.nextInt();
        int w = sc.nextInt();

        sc.nextLine();

        char[][] grid = new char[h][w];
        for(int i = 0; i < h; i++) {
            grid[i] = sc.nextLine().toCharArray();
        }
        System.out.println(totalPaths(grid));
  }
}


Measured memory_bytes: 45532
#include<bits/stdc++.h>
using namespace std;
#define int long long 
#define ii pair <int, int>
#define app push_back
#define all(a) a.begin(), a.end()
#define bp __builtin_popcount
#define ll long long
#define mp make_pair
#define f first
#define s second
#define Time (double)clock()/CLOCKS_PER_SEC
const int N = 1e5 + 7;
int n, a[N];
bool check(int x, int y) { return x <= n && y <= a[x - 1]; }   
int get(int i) {
    int ans = 1;
    while (i + 1 < n && a[i + 1] == a[i]) { ++ans; ++i; }
    return ans;
}   
signed main() {
    #ifdef HOME
    freopen("input.txt", "r", stdin);
    #else
    ios_base::sync_with_stdio(0); cin.tie(0);
    #endif
    cin >> n;
    for (int i = 0; i < n; ++i) cin >> a[i];
    sort(a, a + n); reverse(a, a + n);
    int x = 0, y = 0;
    while (check(x + 1, y + 1)) { ++x; ++y; }
    --x; --y;
    bool win = 0;
    win |= (a[x] - y - 1) & 1;
    if (y + 1 == a[x + 1]) win |= get(x + 1) & 1;
    if (win) cout << "First\n";
    else cout << "Second\n";
}   

Measured memory_bytes: 1024
a,b,m = map(int,input().split())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
Min = (min(A)+min(B))
for _ in range(m):
    x,y,c = map(int,input().split())
    if Min > A[x-1]+B[y-1]-c:
        Min=A[x-1]+B[y-1]-c
print(Min)

Measured memory_bytes: 18608
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int n = sc.nextInt();
        
        int cnt = 0;
        for (int i = 1; i <= 4; i++) {
            if (n % 10 == 2)
                cnt++;
            n /= 10;
        }
        System.out.print(cnt);
    }
}


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

int main(){
    int a,b,c,ans;
	bool ok=false;
	cin >> a >> b >> c;
	for(int i=1;i<100;i++){
		if((a*i)%b==c){
			ok=true;
			break;
		}
	}
	
	if(ok) cout << "YES" << endl;
	else cout << "NO" << endl;
	return 0;
}


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

int main() {
    long long x, k, d;
    cin >> x >> k >> d;

    x = abs(x);
    long long num = x / d;
    if (x % d != 0) {
        num++;
    }
    if (k < num) num = k;

    long long ans;
    if ((k - num) % 2 == 0) {
        ans = abs(x - num * d);
    } else {
        ans = d - abs(x - num * d);
    }

    cout << abs(ans) << endl;
}


Measured memory_bytes: 3592
#!/usr/bin/env python
import sys
import re
from collections import deque, defaultdict
from itertools import combinations, combinations_with_replacement
import bisect
from math import factorial, sqrt, log, ceil, floor
sys.setrecursionlimit(1000000)


def main():
    #N, M = map(int, input().split())
    #N, K = map(int, input().split())
    #ps = list(map(int, input().split()))

    #N, K = map(int, input().split())
    N = int(input())

    dp = []

    for i in range(N):
        vals = list(map(int, input().split()))
        happy = {}
        for j in range(3):
            if dp:
                happy[j] = max([dp[i-1][k] + vals[j]
                                for k in range(3) if k != j])
            else:
                happy[j] = vals[j]
        dp.append(happy)

    print(max(dp[-1].values()))


if __name__ == '__main__':
    main()


Measured memory_bytes: 112900
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef priority_queue<double, vector<double>, less<double> > QUE_double;
typedef priority_queue<int, vector<int>, less<int> > QUE_int;//lessは大きい順にならべるよ
const int MAX = pow(10, 5)+1;//+1しないとREになる(out of rangeになるんかな?? )



int main(){
  ll A, B, K;
  cin >> A >> B >> K;
  ll ans1=0, ans2 = 0;
  if(A-K >= 0){
    ans1 = A-K;
    ans2 = B;
    
  }
  else{
    ans1 = 0;
    ans2 = max((ll)0, B-(K-A));
  }
  cout << ans1 << " " << ans2 << endl;
  return 0;
}



Measured memory_bytes: 256
#include<stdio.h>
int main(){
  int H,W,i,j;
  while(1){
    scanf("%d %d",&H,&W);
    if(H==0&&W==0)break;
    for(j=1;j<=H;j++){
	for(i=1;i<=W;i++)
	  {if(i%2==0&&j%2==1){
	      printf(".");
	    }else if(i%2==1&&j%2==0){
	      printf(".");
	    }else{printf("#");}
	  }
	  printf("\n");
	}
    printf("\n");
  }return 0;
}

Measured memory_bytes: 572
using System;
using System.Collections.Generic;
class Program
{
	static void Main(string[] args)
	{
		string[] str = Console.ReadLine().Split();
		long H = long.Parse(str[0]);
		long W = long.Parse(str[1]);
		long[,]A = new long[H,W];
		for(var i=0;i<H;i++){
			string str2 = Console.ReadLine();
			for(var j=0;j<W;j++){
				if(str2.Substring(j,1) == "#"){
					A[i,j] = 1;
				}
			}
		}
		long[]B = new long[W];
		for(var i=0;i<W;i++){
			long t = 0;
			for(var j=0;j<H;j++){
				if(A[j,i] == 1){
					t = 1;
					break;
				}
			}
			if(t==0){
				B[i] = 1;
			}
		}
		for(var i=0;i<H;i++){
			long s = 0;
			for(var j=0;j<W;j++){
				if(A[i,j] == 1){
					s = 1;
					break;
				}
			}
			if(s == 1){
				string str3 = "";
				for(var j=0;j<W;j++){
					if(B[j] == 0){
						if(A[i,j] == 1){
							str3 += "#";
						} else {
							str3 += ".";
						}
					}
				}
				Console.WriteLine(str3);
			}
		}
	}
}

Measured memory_bytes: 13180
import java.util.Scanner;
import java.util.List;
import java.util.ArrayList;
import java.lang.Math;

class Main{

    public static void main(String[] args){
        
        Scanner scanner = new Scanner(System.in);
        double n = scanner.nextDouble();
        List<Integer> list = new ArrayList<>();
        for(int i=0; i<n; i++){
            int input = scanner.nextInt();
            list.add(input);
        }
        scanner.close();
        double sum = 0;
        for (int i : list) {
            sum += i;
        }
        double p1 = Math.floor(sum/n);
        double p2 = Math.ceil(sum/n);
        double result1 = 0;
        double result2 = 0;
        for(int i : list){
            result1 += Math.pow(i-p1, 2);
            result2 += Math.pow(i-p2, 2);
        }
        if(result1 > result2){
            System.out.println((int)result2);
        }else{
            System.out.println((int)result1);
        }
        
    }
}

Measured memory_bytes: 23252
#include<algorithm>
#include<iostream>
#include<cstring>
#include<string>
#include<queue>
#include<set>
#include<cmath>
#include<vector>
#include<cstdio>
#include<cstdlib>
#define ll long long
using namespace std;
const ll mod=998244353;
ll f[300005],c[300005];
ll n,a,b,k,ans;
ll ksm(ll x,ll num){
	if(num==1) return x;
	ll j=ksm(x,num/2);
	if(num&1) return j*j%mod*x%mod;
	else return j*j%mod;
}
ll C(ll x,ll y){
	// c x y
	return c[x]*f[y]%mod*f[x-y]%mod;
}
int main(){
	c[0]=1;ll tmp;
	scanf("%lld%lld%lld%lld",&n,&a,&b,&k);
//	if(k==0) {printf("1");return 0;}
	for(int i=1;i<=n;i++) c[i]=c[i-1]*i%mod;
	f[n]=ksm(c[n],mod-2);
	for(int i=n;i>=1;i--) f[i-1]=f[i]*i%mod;
	for(int i=0;i<=n;i++){
		tmp=k-a*i;
		if(tmp<0 || tmp%b) continue;
		tmp=tmp/b;if(tmp>n) continue;
		(ans+=C(n,i)*C(n,tmp)%mod)%=mod;
	}
	printf("%lld",ans);
	return 0;
}

Measured memory_bytes: 4992
import java.lang.reflect.Array;
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        int n = s.nextInt();
        int []a = new int [n];
        for(int i = 0; i < n; ++i) {
            a[i] = s.nextInt();
        }
        Arrays.sort(a);
        int cnt1 = 0,cnt2 = 0;
        boolean al = true;
        for(int i = n - 1; i >= 0; --i) {
            if(al) {
                al = false;
                cnt1 += a[i];
            }
            else {
                al = true;
                cnt2 += a[i];
            }
        }
        System.out.println(cnt1 - cnt2);
    }
}


Measured memory_bytes: 22996
#include <stdio.h>

int main(void) {
	int N;
	int mikakosi;
	if (scanf("%d", &N) != 1) return 1;
	for (mikakosi = N * 100 / 110; mikakosi <= N; mikakosi++) {
		if (mikakosi * 108 / 100 == N) {
			printf("%d\n", mikakosi);
			return 0;
		}
	}
	puts(":(");
	return 0;
}


Measured memory_bytes: 1732
#include <iostream>
#include <algorithm>
#include <string>
#include <cmath>
#include <iomanip>
#include <vector>
#include <queue>
#include <map>
#include <set>

#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define pb push_back
#define in insert
#define er erase
#define fi first
#define se second
#define mp make_pair
#define all(x) x.begin(),x.end()
#define le(x) (int) x.length()
#define rsz resize

using namespace std;
typedef vector <int> vi;
typedef vector <vector <int> > vii;
typedef pair <int, int> pii;
typedef queue <int> qi;
typedef double db;
typedef long long ll;
typedef long double ld;
 
const long double PI=3.141592653589793238462643383279502884;
const long long PRIME1=1e9+787;
 
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
ll minll(ll a,ll b) {return a<=b?a:b;}
ll maxll(ll a,ll b) {return a>=b?a:b;}

int main () {
    fast;
    ll n,k;
    cin>>n>>k;
    vi a(n);
    int mx=-1;
    for (int i=0; i<n; i++) {
        cin>>a[i];
        mx=max(a[i],mx);
    }
    int l=1, r=mx;
    while (l<r) {
        int d=(l+r)/2;
        ll count=0;
        for (int i=0; i<n; i++) {
            count+=(a[i]-1)/d;
        }
        if (count>k) {
            l=d+1;
        } else {
            r=d;
        }
    }
    cout<<l;
    return 0;
}
 
 


Measured memory_bytes: 3964
#include <iostream>
#include <algorithm>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<vector>
#include<iomanip>
#define sqr(x) (x)*(x)
using namespace std;
string st;
int n,i,s;
int main()
{
	cin>>st;
	for (i=0;i<st.length();i++)
	{
		if (i&1)
		{
			if (st[i]=='g') s++;
		}
		else
		{
			if (st[i]=='p') s--;
		}
	}
	cout<<s;
	return 0;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
int main()
{
   ios::sync_with_stdio(false);
   cin.tie(0);
   cout.tie(0);
   
   int n;
   cin>>n;
   
   int arr[n];
   
   for(int i=0;i<n;i++)
   cin>>arr[i];
   
   int flag=0,cnt=0;
   
   for(int i=0;i<n;i++)
   {
       if(arr[i]%2==0)
       {
           if(arr[i]%3==0 || arr[i]%5==0)
           cnt++;
           else
           flag=1;
           
       }
   }
  
    if(flag==0)
    cout<<"APPROVED"<<endl;
    else
    cout<<"DENIED"<<endl;

   return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <cmath>
#include <sstream>
#include <iomanip>
#include <set>
using namespace std;
typedef long long int ll;

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define YES cout << "YES" << endl
#define Yes cout << "Yes" << endl
#define yes cout << "yes" << endl
#define NO cout << "NO" << endl
#define No cout << "No" << endl
#define no cout << "no" << endl

const int INF = 1001001001;
const int mod = 1000000007;
#define PI 3.14159265359;

void P(int x) {cout << x << endl;}
void P(long x) {cout << x << endl;}
void P(double x) {cout << x << endl;}
void P(ll x) {cout << x << endl;}
void P(string x) {cout << x << endl;}
void P(char x) {cout << x << endl;}

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

int main() {
  string s;
  cin >> s;
  rep (i, s.size()) {
    if (i % 2 == 0) { // kisu
      if (s[i] != 'R' && s[i] != 'U' && s[i] != 'D') {
        No;
        return 0;
      }
    } else { // gusu
      if (s[i] != 'L' && s[i] != 'U' && s[i] != 'D') {
        No;
        return 0;
      }
    }
  }
  Yes;

  return 0;
}





Measured memory_bytes: 256
/* tempate
 *
 *
 */

#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <queue>
#include <deque>
#include <list>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <fstream>
#include <functional>
#include <bitset>

using namespace std;


#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define repr(i,n) for(int (i)=(n); (i)>=(0); (i)--)
#define SIZE(x) ((int)(x).size())
#define GCD(a, b) int gcd(int a,int b){return b?gcd(b,a%b):a;}
#define QP(a, b) int qp(int a,ll b){int ans=1;do{if(b&1)ans=1ll*ans*a%mo;a=1ll*a*a%mo;}while(b>>=1);return ans;}
#define pb(a) push_back(a)
#define mp(a,b) make_pair(a,b)
#define all(v) (v).begin(),(v).end()


template<typename T> void chmax(T &a, T b) {a = max(a, b);}
template<typename T> void chmin(T &a, T b) {a = min(a, b);}
template<typename T> void chadd(T &a, T b) {a = a + b;}
template<typename A, size_t N, typename T>
void FILL(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}

typedef vector<int, int> vint;
typedef pair<int,int> pint;
typedef vector<pint>vpint;
typedef long long ll;

int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
const ll INF = 1LL << 60;
const ll MOD = 1000000007LL;


int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n; cin >> n;
    vector<vector<ll>> a(2, vector<ll>(n));
    vector<vector<ll>> dp(2, vector<ll>(n, 0));
    rep(i, 2){
        rep(j, n) cin >> a[i][j];
    }
    dp[0][0] = a[0][0];
    rep(i, 2){
        rep(j, n){
            if(i == 0){
                if(j != n - 1){
                    chmax(dp[i][j + 1], dp[i][j] + a[i][j + 1]);
                }
                chmax(dp[i + 1][j], dp[i][j] + a[i + 1][j]);
            }
            else{
                if(j != n - 1){
                    chmax(dp[i][j + 1], dp[i][j] + a[i][j + 1]);
                }
            }
        }
    }
    cout << dp[1][n - 1];
    cout << endl;
    return 0;
}


Measured memory_bytes: 256
#include "iostream"
#include "climits"
#include "list"
#include "queue"
#include "stack"
#include "set"
#include "functional"
#include "algorithm"
#include "string"
#include "map"
#include "unordered_map"
#include "unordered_set"
#include "iomanip"
#include "cmath"
#include "random"
#include "bitset"
#include "cstdio"
#include "numeric"
#include "cassert"
#include "ctime"

using namespace std;

//constexpr long long int MOD = 1000000007;
//constexpr int MOD = 1000000007;
//constexpr int MOD = 998244353;
constexpr long long int MOD = 998244353;
constexpr double EPS = 1e-9;

//int N, M, K, H, W, L, R;
long long int N, M, K, H, W, L, R;

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

	vector<int>dp(200001);
	dp[0] = 0;
	for (int i = 1; i <= 200000; i++) {
		int box = i;
		int num = 0;
		while (box) {
			num += box & 1;
			box >>= 1;
		}
		dp[i] = dp[i%num] + 1;
	}
	cin >> N;
	string s;
	cin >> s;
	int num = 0;
	for (auto i : s) {
		num += i == '1';
	}
	int amari = 0;
	vector<int>two(200001, 1);
	for (int i = 1; i <= 200000; i++) {
		two[i] = two[i - 1] * 2 % (num + 1);
	}
	vector<int>ans(N);
	reverse(s.begin(), s.end());
	for (int i = 0; i < N; i++) {
		if (s[i] == '1') {
			amari += two[i];
			amari %= (num + 1);
		}
	}
	for (int i = 0; i < N; i++) {
		if (s[i] == '1')continue;
		ans[i] = dp[(amari + two[i]) % (num + 1)] + 1;
	}
	if (num > 1) {
		for (int i = 1; i <= 200000; i++) {
			two[i] = two[i - 1] * 2 % (num - 1);
		}
		amari = 0;
		for (int i = 0; i < N; i++) {
			if (s[i] == '1') {
				amari += two[i];
				amari %= (num - 1);
			}
		}
		for (int i = 0; i < N; i++) {
			if (s[i] == '0')continue;
			ans[i] = dp[(amari + num - 1 - two[i]) % (num - 1)] + 1;
		}
	}
	reverse(ans.begin(), ans.end());
	for (auto i : ans)cout << i << endl;
}

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

int main(){
    int n;
    long long t,m=0;
    cin>>n>>t;
    for(int i=0;i<n;i++)
    {
        long long h;cin>>h;
        if(m<h)m=h;
        t-=h;
        if(t<0)cout<<1<<endl;
        else cout<<t/m+2<<endl;
    }
    return 0;
}


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

int main() {
  int n;
  cin >> n;
  int cnt=0;
  for(int i=0;i<n;i++){
    int a;
    cin >> a;
    if(a%2){
      cnt++;
    }
  }
  if(cnt%2){
    cout << "NO" << endl;
  }
  else{
    cout << "YES" << endl;
  }
}

Measured memory_bytes: 3608
#include <stdio.h>

int main(){
    int num1, num2;

    for (num1=1;num1<10;num1++) {
        for (num2=1; num2<10; num2++) {
            printf("%dx%d=%d\n", num1, num2, num1*num2);
        }
    }

    return(0);
}

Measured memory_bytes: 524
#define _USE_MATH_DEFINES
#include <cassert>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <queue>
#include <stack>
#include <list>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <complex>
#include <cmath>
#include <numeric>
#include <bitset>
#include <functional>
#include <random>
#include <ctime>

using namespace std;

#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
  cerr << name << ": " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
  const char* comma = strchr(names + 1, ',');
  cerr.write(names, comma - names) << ": " << arg1 << " |";
  __f(comma + 1, args...);
}

typedef long long int64;
typedef pair<int, int> ii;
const int INF = 1 << 29;
const int MOD = 1e9 + 7;

const int N = 1e5 + 10;
vector<ii> a[N];
int color[N];

void DFS(int u, int parent) {
  for (auto& it : a[u]) {
    int v = it.first, w = it.second;
    if (v == parent) continue;
    color[v] = (color[u] + w) % 2;
    DFS(v, u);
  }
}

int main() {
  int n;
  scanf("%d", &n);
  for (int i = 1; i < n; ++i) {
    int x, y, z;
    scanf("%d%d%d", &x, &y, &z);
    z %= 2;
    --x; --y;
    a[x].push_back({y, z});
    a[y].push_back({x, z});
  }
  fill(color, color + n, -1);
  color[0] = 0;
  DFS(0, -1);
  for (int i = 0; i < n; ++i) {
    printf("%d\n", color[i]);
  }
  return 0;
}


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

typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pi;
typedef pair<ll,ll> pll;

#define endl '\n'
#define ff first
#define ss second
#define int long long
#define pb push_back
#define f(i,l,r) for(ll i=l;i<=r;i++)
#define rf(i,r,l) for(ll i=r;i>=l;i--)
#define Max 5000001
#define inf 2147483647
#define llinf 9223372036854775807
#define all(v) v.begin(),v.end()
#define bp(n) __builtin_popcountll(n)
#define fast ios_base::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL)

#define d0(a) cout<<a<<' ';
#define d1(a) cout<<a<<endl;
#define d2(a,b) cout<<a<<' '<<b<<endl;
#define d3(a,b,c) cout<<a<<' '<<b<<' '<<c<<endl;
#define d4(a,b,c,d) cout<<a<<' '<<b<<' '<<c<<' '<<d<<endl;
#define d5(a,b,c,d,e) cout<<a<<' '<<b<<' '<<c<<' '<<d<<' '<<e<<endl;
#define d6(a,b,c,d,e,f) cout<<a<<' '<<b<<' '<<c<<' '<<d<<' '<<e<<' '<<f<<endl;

const ll N=100,mod=1e9+7,bit=61;
const ld PI=acos(-1.00);

ll a,b,n;

ll fun(ll x)
{
    assert(x<=n);
    ll ans=((a*x)/b)-a*(x/b);
    return ans;
}

signed main()
{
    fast;

    ll t=1;
    //cin>>t;
    while(t--)
    {
        scanf("%lld %lld %lld",&a,&b,&n);
        ll mx=(a*n)/b;
        ll l=0,r=n,x=n;
        while(l<=r)
        {
            ll mid=(l+r)>>1;
            ll nw=(a*mid)/b;
            if(nw==mx)
            {
                x=min(x,mid);
                r=mid-1;
            }
            else
            {
                l=mid+1;
            }
        }
        ll ans=fun(x);
        f(i,0,min(5000000ll,n))
        {
            ans=max(ans,fun(i));
            ans=max(ans,fun(n/max(1ll,i)));
        }
        f(i,1,5000000)
        {
            ll x=i;
            ll k=min(b*x+b-1,n);
            ans=max(ans,fun(k));
            x=b/i;
            k=min(b*x+b-1,n);
            //ans=max(ans,fun(k));
        }
        ans=max(ans,fun(min(n,b-1)));
        ans=max(ans,fun(min(n,a)));
        ans=max(ans,fun(n));
        //assert(ans<=fun(min(a,b-1)));
        printf("%lld\n",ans);
    }
    return 0;
}


















Measured memory_bytes: 3880
import sys
import os
import re
import datetime
import bisect

####### main #######

N = int(input())

partsNumA = sorted(map(int, input().split()))
partsNumB = sorted(map(int, input().split()))
partsNumC = sorted(map(int, input().split()))

# Bに対してAの個数のBによるループ
partsNumSumBa = []
sumA = 0
for curPartsB in partsNumB:
    indexA = bisect.bisect_left(partsNumA, curPartsB)
    numA = indexA
    sumA += numA
    partsNumSumBa.append(sumA)

# Cに対してBの個数のCによるループ
sumBAll = 0
for curPartsC in partsNumC:
    indexB = bisect.bisect_left(partsNumB, curPartsC)
    if indexB == 0:
        continue
    numB = partsNumSumBa[indexB - 1]
    sumBAll += numB

print(sumBAll)

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

a = [0]*n
for i in range(k):
    d = int(input())
    s = list(map(int, input().split()))
    for j in range(d):
        a[s[j]-1] = 1
cnt = 0
for i in range(n):
    if a[i] == 0:
        cnt += 1
        
print(cnt)

Measured memory_bytes: 67540
# https://atcoder.jp/contests/arc061/tasks/arc061_a
# 復習課題
# シフト演算を用いてリファクタリングせよ。

S = list(input())
ans = 0

for i in range(2**(len(S)-1)):
    p = list(bin(i))
    flag = ['0' for _ in range(len(S) - len(p) + 1)] + p[2:]
    l = 0
    for j in range(len(S)-1):
        if (i >> j) & 1:
            ans += int("".join(S[l:j+1]))
            l = j+1
    ans += int("".join(S[l:]))

print(ans)


Measured memory_bytes: 9180