akhauriyash/Code-Regression huggingface dataset:
// #pragma GCC target("avx2")
#pragma GCC optimize("O3", "unroll-loops")

// #include <bits/extc++.h>
// using namespace __gnu_pbds;

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define double long double
// template <typename T>
// using pbds_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
using pii = pair<int, int>;
template<typename T>
using prior = priority_queue<T, vector<T>, greater<T>>;
template<typename T>
using Prior = priority_queue<T>;

#define X first
#define Y second
#define ALL(x) (x).begin(), (x).end()
#define eb emplace_back
#define pb push_back

#define fastIO() ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define RANDOM() random_device __rd; \
                 mt19937 __gen = mt19937(__rd()); \
                 uniform_int_distribution<int> __dis(1, 1E8); \
                 auto rnd = bind(__dis, __gen)

const int INF = 1E18;
const int mod = 1E9 + 7;
const int maxn = 1E5 + 5;

vector<int> adj[maxn], ans(maxn), degI(maxn), vis(maxn);

void dfs(int now) {
    for (auto x : adj[now]) {
        ans[x] = max(ans[x], ans[now] + 1);
        if (++vis[x] == degI[x]) dfs(x);
    }
}

int32_t main() {
    fastIO();
    
    int n, m, u, v;
    cin >> n >> m;
    
    while (m--) cin >> u >> v, ++degI[v], adj[u].eb(v);
    
    for (int i = 1; i <= n; ++i) {
        if (!degI[i]) dfs(i);
    }
    
    int maxL = 0;
    for (int i = 1; i <= n; ++i) maxL = max(maxL, ans[i]);
    
    cout << maxL << "\n";
    
    return 0;
}

Measured memory_bytes: 17092
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <map>

using namespace std;


int main() {
    long long int n;
    cin >> n;
    vector<string>s;
    vector<int> b;
    string temp;
    map<string, int> dec;
    for (int i = 0; i < n; i++) {
        cin >> temp;
        sort(temp.begin(), temp.end());
        dec[temp]++;
    }

    long long int ans = 0;
    long long int ss = dec.size();
    long long int t;

    for (auto itr = dec.begin(); itr != dec.end(); itr++) {
        t = itr->second;
        ans += t * (t - 1) / 2;
    }


    cout << ans;

    return 0;
}

Measured memory_bytes: 11136
sx,sy,tx,ty=map(int, input().split())

#直角にいく＆回り込むで２往復
dx,dy=tx-sx,ty-sy
one="R"*dx+"U"*dy
#print(one)
two=one.replace("R","L").replace("U","D")
#print(two)

three="D"+"R"*(dx+1)+"U"*(dy+1) +"L"
#print(three)
four=three
four=four.replace("D","d").replace("R","r").replace("U","u").replace("L","l")
four=four.replace("d","U").replace("r","L").replace("u","D").replace("l","R")
#print(four)
print(one+two+three+four)

Measured memory_bytes: 3064
sx, sy, tx, ty = [int(i) for i in input().split()]
dx = tx - sx
dy = ty - sy
print(''.join(("U" * dy, "R" * dx,
         "D" * dy, "L" * dx,
         "L", "U", "U" * dy, "R", "R" * dx, "D",
         "R", "D", "D" * dy, "L", "L" * dx, "U")))


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

int a[7], b[7];

int main() {
	for (int i = 0; i < 7; i++) {
		cin >> a[i] >> b[i];
	}
	for (int i = 0; i < 7; i++) {
		cout << abs(a[i] - b[i]) << endl;
	}
	return 0;
}



Measured memory_bytes: 3216
parseInt(x) = parse(Int, x)
parseMap(x::Array{SubString{String},1}) = map(parseInt, x)
function bsearch(a,x);l,r=0,length(a)+1;while r-l>1;m=(r+l)>>1;if a[m]<x;l=m;else;r=m;end;end;l;end

function main()
	n,o = readline() |> split |> parseMap
	a = readline() |> split |> parseMap |> sort
	l = 0
	r = 3*10^5
	while r-l>1
		m = (l+r)>>1
		k = 0
		for i in 1:n
			z = bsearch(a,m-a[i])
			k += n-z
		end
		if k>o
			l = m
		else
			r = m
		end
	end
	sr = 0
	b = zeros(Int,n+1)
	for i in 1:n
		b[i+1]=b[i]+a[i]
	end
	ct = 0
	for i in 1:n
		zr = bsearch(a,r-a[i])
		sr += b[n+1]-b[zr+1]+a[i]*(n-zr)
		ct += (n-zr)
	end
	println(sr+l*(o-ct))
end
main()

Measured memory_bytes: 124580
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <cstdio>	
#include <limits>
#include <vector>
#include <cstdlib>
#include <numeric>
#include <sstream>
#include <iostream>	
#include <algorithm>
#include <functional> 
#include <iomanip>
#include <unordered_map>
#include <fstream>
#include <cstdio>
#include <memory.h>

using namespace std;

int main(void)
{
	int a, b, c, x;
	int res = 0;

	cin >> a >> b >> c >> x;

	for (int i = 0; i <= a; i++)
	{
		for (int j = 0; j <= b; j++)
		{
			for (int k = 0; k <= c; k++)
			{
				if (x == 500 * i + 100 * j + 50 * k)
				{
					res++;
				}
			}
		}
	}

	cout << res << '\n';

	return 0;
}

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

int main(){
	string s;
  	cin >> s;
  
  	if(s == "SUN") cout << 7 << endl;
    if(s == "MON") cout << 6 << endl;
  	if(s == "TUE") cout << 5 << endl;
  	if(s == "WED") cout << 4 << endl;
  	if(s == "THU") cout << 3 << endl;
  	if(s == "FRI") cout << 2 << endl;
  	if(s == "SAT") cout << 1 << endl;
}

Measured memory_bytes: 3600
#include<bits/stdc++.h>
using namespace std;
long long a[200005],mp[2100],ans;
int main(){
	string s;
	cin>>s;
	reverse(s.begin(),s.end());
	long long y=1;
	for(int i=0;i<s.size();i++){
		a[i]=(y*(s[i]-'0'))%2019;
		y=(y*10)%2019;
	}
	y=0;
	for(int i=0;i<s.size();i++){
		y=(y+a[i])%2019;
		mp[y]++;
	}
	for(int i=0;i<2019;i++)
		ans+=mp[i]*(mp[i]-1)/2;
	ans+=mp[0];
	cout<<ans;
	return 0;
}

Measured memory_bytes: 5260
/*
[ ( ^ _ ^ ) ]
*/
// problem: atc/abc166_d
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define INF 1000000000



int main() {
    ll x;
    scanf("%lld", &x);
    ll l = 2000;
    for(ll a=0; a<=l; a++) {
        for(ll b=-l; b<=l; b++) {
            if(pow(a, 5) - pow(b, 5) == x) {
                printf("%lld %lld\n", a, b);
                return 0;
            }
        }
    }
    assert(false);
}


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

using namespace std;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    int k;
    string s;
    cin >> k;
    while (k--) {
        s += "ACL";
    }
    cout << s << endl;
    return 0;
}





Measured memory_bytes: 3644
#include <iostream>
using namespace std;
int main(void){
    int a,b;
    cin >> a >> b;
    if(a>b && b!=1) cout << "Alice";
    else if(a<b && a!=1) cout << "Bob";
    else if(a==1 && a<b) cout <<"Alice";
    else if(b == 1 && a>b) cout << "Bob";
    else cout << "Draw";
}

Measured memory_bytes: 256
//どっか～引用

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    int ans = 0;
    for(int i=0; i<n; ++i) {
        int l, r;
        cin >> l >> r;
        ans += (r-l)+1;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const long long INF=2E17;
typedef pair<int,int> Pair;
typedef long long int LL;
const int MAX=100010;

int main(){
    int N;
    vector<int> a;
    cin >> N;
    int tmp;
    for(int i=0;i<N;i++){
        cin >> tmp;
        a.push_back(tmp);
    }    
    sort(a.begin(),a.end());
    int n=a.back();
    a.pop_back();
    int r=-1;
    for(int i=0;i<a.size();i++){
        r=( abs(n-2*r) >= abs(n-2*a[i]) ? a[i] : r );
    }
    cout << n << " " << r << endl;
    return 0;
}

Measured memory_bytes: 892
a=int(input())
b=int(input())
c=int(input())
d=int(input())
e=int(input())
f=int(input())
x = (a,b,c,d)
y = (e,f)
z = min(x)
w = sum(x)
z = w-z
g = z+max(y)
print(g)


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

using namespace std;

vector<long long> v;


void divisors(long long n){
    for (long long i=1; i<=sqrt(n); i++){ 
        if (n%i == 0) 
        {
            if (n/i == i) 
                v.push_back(i);
  
            else {
                v.push_back(i);
                v.push_back(n/i);
            }
        } 
    } 
} 

int main(){
    
    
    long long n;
    cin >> n;
    
    
    
    divisors(n);
    long long t1,t2;
    int a = v.size();
    sort(v.begin(), v.end());
    if (a%2 == 0){
        t1 = v[a/2];
        t2 = v[(a/2)-1];
    } else {
        t1 = t2 = v[a/2];
    }
    //cout << t1 << " " << t2 << endl;
    
    cout << t1+t2-2 << endl;
}





Measured memory_bytes: 384
#include<iostream>
using namespace std;
int main()
{
    string s, t;
    bool flag, found = false;
    cin >> s >> t;
    int len = s.length();
    for(int i = 0; i < len; i++)
    {
        flag = true;
        for(int j = 0; j < len; j++)
        {
            if(s[(j+i) % len] == t[j])
                continue;
            else
            {
                flag = false;
                break;
            }
        }
        if(flag == true)
        {
            found = true;
            break;
        }
    }
    if(found)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
    return 0;
}


Measured memory_bytes: 256
n = int(input())
tmp = 0
for i in range(1, 100):
    if n<=tmp+26**i:
        digits = i
        n -= tmp+1
        break
    tmp += 26**i
ans = []
for i in range(digits):
    ans.append(chr(n%26+ord('a')))
    n //= 26
print(''.join(ans[::-1]))

Measured memory_bytes: 9192
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#include <iomanip> // fixed, setprecision 
#include <math.h> // double sqrt
#define rep(i,n) for(int i=0;i<(n);++i)
#define ll long long
using namespace std;
int main(){
    ll x;
    cin>>x;
    int p,q;
    for(int a=-118;a<=119;a++){
        for(int b=-119;b<=118;b++){
            if(a*a*a*a*a-b*b*b*b*b==x){p=a;q=b;break;}
        }
    }
    cout<<p<<" "<<q;
    return 0;
}

Measured memory_bytes: 3164
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect
from heapq import heappush, heappop

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, M = MAP()
ab = [LIST() for _ in range(M)]

def dijkstra(E, start):
    N_d = len(E)
    dist = [INF] * N_d
    dist[start] = 0
    q = [(0, start)]
    while q:
        dist_v, v = heappop(q)
        if dist[v] != dist_v:
            continue
        for u, dist_vu in E[v]:
            dist_u = dist_v + dist_vu
            if dist_u < dist[u]:
                dist[u] = dist_u
                heappush(q, (dist_u, u))
    return dist

E = [[] for _ in range(N)]

for a, b in ab:
	E[a-1].append((b-1, 1))

d = dijkstra(E, 0)

if d[-1] <= 2:
	print("POSSIBLE")
else:
	print("IMPOSSIBLE")


Measured memory_bytes: 93788
#include <cstdio>
#include <iostream>
#include <string>
using namespace std;

int main()
{
    int n, m;
    while(cin >> n && n) {
        char c1[65], c2[65]; string op;
        op = "";
        for(int i=0; i < n; ++i) cin >> c1[i] >> c2[i];
        cin >> m;
        for(int i=0; i < m; ++i) {
            char c;
            cin >> c;
            for(int j=0; j < n; ++j) {
                if (c == c1[j]) {
                    c = c2[j];
                    break;
                }
            }
            op += c;
        }
        cout << op << endl;
    }

    return 0;
}

Measured memory_bytes: 1324
#include <cstdio>

int main(void)
{
    int n, m, l, f;
    scanf("%d %d %d", &n, &m, &l);
    int a[n][m], b[m][l];
    long c[n][l];
    for(int i=0; i<n; i++)
        for(int j=0; j<m; j++)
            scanf("%d", &a[i][j]);
    for(int i=0; i<m; i++)
        for(int j=0; j<l; j++)
            scanf("%d", &b[i][j]);
    for(int i=0; i<n; i++)
        for(int j=0; j<l; j++)
            c[i][j] = 0;
    for(int i=0; i<n; i++)
        for(int j=0; j<l; j++)
            c[i][j] = 0;
    for(int i=0; i<n; i++)
        for(int j=0; j<l; j++)
            for(int k=0; k<m; k++)
                c[i][j] += a[i][k]*b[k][j];
    for(int i=0; i<n; i++)
    {
        for(f=0; f<l-1; f++)
            printf("%ld ", c[i][f]);
        printf("%ld\n", c[i][f]);
    }

    return 0;
}


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

int main(){
	char a[1024],b[1024];
	int i=0,j,k=0,w;
	for(i=0;i<1024;i++){
		a[i]='\0';
		b[i]='\0';
	}
	cin>>a>>w;
	i=0;
	while(a[i]!='\0'){
		for(j=0;j<w;j++){
			if(j==0){
				b[k]=a[i];
				k++;
			}
			i++;
		}
	}
	cout<<b<<endl;
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	
	int n;
	cin >> n;
	
	vector<vector<pair<int, bool>>> v(n);
	
	for (int i = 0; i < n; ++i){
		int m;
		cin >> m;
		for (int j = 0; j < m; ++j){
			int a;
			bool b;
			
			cin >> a >> b;
			
			v[i].emplace_back(make_pair(a - 1, b));
		}
	}
	
	bool pr = false;
	for (int i = 0; i <= n; ++i){
		vector<bool> p(n, true);
		
		for (int j = 0; j < i; ++j){
			p[j] = false;
		}
		
		
		bool ans = true;
		do{
			ans = true;
			for (int j = 0; j < n; ++j){
				for (auto k : v[j]){
					if (!((p[j] && p[k.first] == k.second) || !p[j])){
//						cout << p[j] << p[k.first] << k.second << '\n';
						ans = false;
					}
				}
			}
//			cout << i << ' ' << ans << '\n';
			if (ans){
				break;
			}
		}while (next_permutation(p.begin(), p.end()));
		if (ans){
			cout << n - i << '\n';
			pr = true;
			break;
		}
	}
	if (!pr){
		cout << 0  << '\n';
	}
}


Measured memory_bytes: 256
#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 ll long long
#define Pii pair<int,int>
long long INF = 1e18;
const int MOD = 1e9 + 7;

using namespace std;

Pii vp[300*300+1];
int vl[300*300+1],answer[100000];

int main(){
    int h,w,d,q;
    scanf("%d %d %d",&h,&w,&d);
    FOR(i,1,h+1){
        FOR(j,1,w+1){
            int a;
            scanf("%d",&a);
            vp[a] = Pii{i,j};
        }
    }

    scanf("%d",&q);
    FOR(i,1,d+1) vl[i] = 0;
    FOR(i,d+1,h*w+1) vl[i] = vl[i-d] + abs(vp[i].first-vp[i-d].first) + abs(vp[i].second-vp[i-d].second);

    REP(i,q){
        int l,r;
        scanf("%d %d",&l,&r);
        answer[i] = vl[r] - vl[l];
    }
    REP(i,q) printf("%d\n",answer[i]);
    return 0;
}


Measured memory_bytes: 2560
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define sz(x) (int)(x).size()
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
using namespace std;
using ll = long long;
using P = pair<int, int>;
using vi = vector<int>;
using vc = vector<char>;
using vb = vector<bool>;
using vs = vector<string>;
using vll = vector<long long>;
using vp = vector<pair<int, int>>;
using vvi = vector<vector<int>>;
using vvc = vector<vector<char>>;
using vvll = vector<vector<long long>>;
template<class T> inline bool chmax(T &a, T b) { if (a<b) {a=b; return 1;} return 0;}
template<class T> inline bool chmin(T &a, T b) { if (b<a) {a=b; return 1;} return 0;}

struct edge{ int to, weight;};
vector<vector<edge>> to;
vector<int> color;

void dfs(int v, bool even=false, int p=-1) {
    if (v == 0) color[v] = 0;
    else if (even) color[v] = color[p];
    else color[v] = 1 - color[p];
    for (edge e : to[v]) {
        int u = e.to;
        if (u == p) continue;
        dfs(u, e.weight % 2 == 0, v);
    }
}

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

    int n;
    cin >> n;
    to.resize(n);
    rep(i, n-1) {
        int u, v, w;
        cin >> u >> v >> w;
        u--; v--;
        to[u].pb(edge{v, w});
        to[v].pb(edge{u, w});
    }
    color.resize(n);
    dfs(0);
    rep(i, n) cout << color[i] << endl;
}


Measured memory_bytes: 8192
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; i++)
using namespace std;
int main()
{
    int n;
    cin >> n;
    string s, t;
    cin >> s >> t;
    string ans;
    rep(i,n){
        ans = ans + s[i] + t[i];
    }
    cout << ans << endl;
}


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

#define rep(i, n) for(int i = 0; i < (n); ++i)
#define repr(i, n) for(int i = (n-1); i >= 0; --i)

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

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

const int MAX = 200005;
const int INF = 1001001001;
const int MOD = 1000000007;

int main(){
    int K;
    string S;
    cin >> K >> S;

    if (K < S.size()) {
        S = S.substr(0, K);
        rep(i, 3) S.push_back('.');
    }

    cout << S << endl;
}

Measured memory_bytes: 3632
import math
n,k = map(int,input().split())
a = list(map(int,input().split()))
a.sort(reverse=True)
l = 0 
h = a[0]
def pos(b):
  c = 0
  for i in range(n):
    if a[i] <= b:
      break
    c += math.ceil(a[i]/b)-1
    if c > k:
      return False
  return True
while l+1 < h:
  m = (l+h)//2
  if pos(m):
    h = m
  else:
    l = m
print(h)
  


Measured memory_bytes: 93828
import java.io.PrintWriter;
import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		PrintWriter pw = new PrintWriter(System.out);
		char[] S = sc.next().toCharArray();
		int N = S.length;
		
		int index = 0;
		while(index < N) {
			int[] LRcount = getLR(S, index);
			int[] ans = getChild(LRcount);
			for(int a : ans) {
				pw.println(a);
			}
			index += LRcount[0]+LRcount[1];
		}
		
		pw.close();
		sc.close();
	}
	
	static int[] getLR(char[] S, int index) {
		int[] count = new int[2];
		
		for(; index<S.length && S[index]=='R'; index++)
			count[0]++;
		for(; index<S.length && S[index]=='L'; index++)
			count[1]++;
		
		return count;
	}
	
	static int[] getChild(int[] count) {
		int R = count[0];
		int L = count[1];
		int[] ans = new int[R+L];
		
		ans[R-1] = (R+1)/2 + L/2;
		ans[R] = R/2 + (L+1)/2;
		
		return ans;
	}
}

Measured memory_bytes: 32364
#include<cstdio>
int main(){
  bool flag[30];
  for(int i=0;i<30;i++) flag[i] = false;
  for(int i=0;i<28;i++){
    int x;
    scanf("%d",&x);
    flag[--x] = true;
  }
  for(int i=0;i<30;i++) if(!flag[i]) printf("%d\n",i+1);
  return 0;
}

Measured memory_bytes: 2704
#include <stdio.h>
#include <stdlib.h>

int GCDa(int N, int M)
{
  int z,i;
  if(M<2*N)
    return 1;
  else
  {
    for(i=M/N+1; i>0; i--)
      if(M%i==0)
        break;
    if(i==1)
      return 1;
    else
    {
      //printf("%d %d %d\n",N,M,i);
      return i*GCDa(N,M/i);
    }
  }
}

main()
{
  int N,M,z,sum;
  scanf("%d%d",&N,&M);
  printf("%d\n",GCDa(N,M));
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 1e16;
const ll mod = 1000000007;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)

int main() {
  ll n; cin >> n;
  if (n%2) cout << 0 << endl;
  else {
    ll res = 0;
    ll tmp = 10;
    while (tmp <= n) {
      res += n/tmp;
      tmp *= 5;
    }
    cout << res << endl;
  }
}

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

int main() {
  int H, W;
  cin >> H >> W;
  vector<vector<char>> maze(H, vector<char>(W));
  for (int i = 0; i < H; i++) {
    for (int j = 0; j < W; j++) {
      cin >> maze[i][j];
    }
  }
  vector<vector<int>> H_cnt(H, vector<int>(W, 0));
  vector<vector<int>> W_cnt(H, vector<int>(W, 0));
  for (int i = 0; i < H; i++) {
    int a = 0;
    for (int j = 0; j <= W; j++) {
      if (j == W) {
        for (int k = a; k < j; k++) {
          H_cnt[i][k] = j-a;
        }
      }
      else if (maze[i][j] == '#') {
        H_cnt[i][j] = -1;
        for (int k = a; k < j; k++) {
          H_cnt[i][k] = j-a;
        }
        a = j+1;
      }
    }
  }
  for (int i = 0; i < W; i++) {
    int a = 0;
    for (int j = 0; j <= H; j++) {
      if (j == H) {
        for (int k = a; k < j; k++) {
          W_cnt[k][i] = j-a;
        }
      }
      else if (maze[j][i] == '#') {
        W_cnt[j][i] = -1;
        for (int k = a; k < j; k++) {
          W_cnt[k][i] = j-a;
        }
        a = j+1;
      }
    }
  }
  int ans = 0;
  for (int i = 0; i < H; i++) {
    for (int j = 0; j < W; j++) {
      ans = max(ans, H_cnt[i][j] + W_cnt[i][j] -1);
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 35584
#include <iostream>
#include <cmath>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;

int main() {
    ll n,T;
    cin >> n >> T;
    ll t[n];
    for(int i=0;i<n;i++) cin >> t[i];

    ll ans=0;
    for(int i=0;i<n-1;i++){
        ans += min(T, t[i+1]-t[i]);
    }
    cout << ans+T << endl;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
main(){
int N,M,i,j;
cin>>N>>M;
vector<int>D(N);
vector<int>C(M);
for(i=0;i<N;i++){cin>>D[i];}
for(i=0;i<M;i++){cin>>C[i];}
vector<vector<int> >dp(M+1,vector<int>(N+1,1<<30));dp[0][0]=0;
for(i=1;i<=M;i++){for(j=0;j<=N;j++){
if(j==0){dp[i][j]=dp[i-1][j];}
else{dp[i][j]=min(dp[i-1][j],dp[i-1][j-1]+C[i-1]*D[j-1]);}}}
cout<<dp[M][N]<<endl;
return 0;}

Measured memory_bytes: 6072
//B - OddString: 
//Assunto: 
#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define loop(i, a, b) for(int i = a; i < b; i++)
#define loopBack(i, a, b) for(int i = a; i >= b; i--)
#define INF INT_MAX
#define LINF LLONG_MAX
#define DINF DBL_MAX
#define MAX 100050
#define MOD 1000000007
using namespace std;
typedef long long int ll;
typedef pair<int, int> ii;

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
    string s, ans = "";
    cin >> s;
    loop(i, 0, s.size()) {
        if((i+1) % 2 != 0) ans += s[i];
    }
    cout << ans << "\n";
}

Measured memory_bytes: 592
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <numeric>
#include <bitset>

using namespace std;
using ll = long long;
using ld = long double;
const ll mod =  998244353;
const ll inf = 1e18;

#define REP(i, n) for (ll i = 0; i < (n); ++i)
#define REP_FROM(i, j, n) for (ll i = (j); i < (n); ++i)
#define all(x) (x).begin(),(x).end()

template<typename T> void print_vec(vector<T> a) {int n = a.size();REP(i, n) {cout >> a[i]; if(i!=n-1) cout << " "; else cout << endl;}}
ll power(ll base, ll exponent){ if(exponent % 2){ return power(base, exponent - 1) * base % mod; }else if(exponent){ ll root_ans = power(base, exponent / 2); return root_ans * root_ans % mod; }else{ return 1; }}
ll inverse(ll x){ return power(x, mod - 2);}
ll gcd(ll a, ll b) {if(a < b) gcd(b, a);ll r;while(r=a%b) {a=b;b=r;}return b;}
template<typename T> ll sum(T begin, T end) {return accumulate(begin, end, 0ll);}
struct combination{ vector<ll> fact, inv; combination(int sz) : fact(sz + 1), inv(sz + 1){ fact[0] = 1; for(int i = 1; i <= sz; i++){ fact[i] = fact[i - 1] * i % mod; } inv[sz] = power(fact[sz], mod - 2); for(int i = sz - 1; i >= 0; i--){ inv[i] = inv[i + 1] * (i + 1) % mod; } } ll C(int p, int q) const{ if(q < 0 || p < q) return 0; return (fact[p] * inv[q] % mod * inv[p - q] % mod); } };

int bsearch(const vector<ll>& a, ll x){
  int lft = 0;
  int rgt = a.size();
  while (rgt - lft > 1) {
    int mid = (lft + rgt) / 2;
    if(a[mid] < x) {
      lft = mid;
    }
    else {
      rgt = mid;
    }
  }
  return lft;
}

ll count(ll i, ll n, const vector<ll>& a) {
  // cout << i << endl;
    vector<ll> tmp = a;    
    REP(j, n) {
      tmp[j] = tmp[j] % i;
    }
    sort(all(tmp));
    // REP(k, n) cout << tmp[k] << " "; cout << endl;
    ll cnt = 0;
    int lft = 0;
    int rgt = n - 1;
    while(lft < rgt) {
      cnt += tmp[lft];
      tmp[rgt] += tmp[lft];
      tmp[lft] = 0;
      while(i <= tmp[rgt]  && rgt > 0) {
        tmp[rgt-1] += tmp[rgt] - i;
        rgt--;
      }
      lft++;
      // REP(k, n) cout << tmp[k] << " "; cout << endl;
    }
    // cout << cnt << endl;
    // cout << "======" << endl;
    return cnt;
}


signed main() {
  ios::sync_with_stdio(false);
  int n, k;
  cin >> n >> k;
  vector<ll> a(n);
  REP(i, n) cin >> a[i];
  ll s = sum(all(a));
  
  ll ans = 1;
  for(ll i = 1; i*i <=s; i++) {
    if(s % i != 0) continue;  
    if(count(i, n, a) <= k) ans = max(ans, i);
    if(count(s / i, n, a) <= k) ans = max(ans, s / i);
  }
  cout << ans << endl;
  return 0; 
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define int long long
#define ll long long 
#define rep(i,a,b) for(signed i=a;i<(b);++i)
#define erep(i,a,b) for(signed i=a;i<=(b);++i)
#define per(i,a,b) for(signed i=(a);i>(b);--i)
#define eper(i,a,b) for(signed i=(a);i>=b;--i)
#define fore(i, x, a) for(auto &&x:a) 
#define ITR(i,b,e) for(auto i=(b);i!=(e);++i)
#define pb emplace_back
#define mp make_pair
#define ALL(x) begin(x),end(x)
#define F first
#define S second
#define debug(x)  cout << #x << ": " << (x) << '\n';
const long long INF=1001001001001001001;
const int MOD=(int)1e9 + 7;
const double EPS=1e-9;
using namespace std;
using Pii = pair<int,int>;
using vii = vector<int>;
template<class T>using  PS_queue = priority_queue<T, vector<T>, greater<T> >;
template<class T>using vv = vector<T>;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a = b; return 1; } return 0; }
template<typename A, size_t N, typename T> void Fill(A (&array)[N], const T &val){fill( (T*)array, (T*)(array+N), val );}
template<class T> ostream& operator<<(ostream &os,const vector<T> &v) {
    ITR(i,begin(v),end(v))os<<*i<<(i==end(v)-1?"":" ");return os;}
template<class T> istream& operator>>(istream &is,vector<T> &v) {
    ITR(i,begin(v),end(v)) is>>*i;return is;}
template<class T,class U> istream& operator>>(istream &is, pair<T,U> &p) {
    is>>p.first>>p.second;return is;}
template<class T>T gcd(T a, T b){ return b ? gcd(b, a % b) : a; }
template<class T>T lcm(T a, T b){ return a / gcd(a, b) * b; }
struct edge { int from, to, cost; };
int dy[]={0, 1, -1, 0}; int dx[]={1, 0, 0, -1};
// cout << fixed;
// cout << setprecision(10) << val;

int n, m;
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(false);
  cin >> n >> m;
  vii a(n);
  cin >> a;
  vv<Pii> bc(m);
  rep(i, 0, m) {
    int x, y;
    cin >> x >> y;
    bc[i] = mp(y, x);
  }
  a.pb(INF);
  sort(ALL(a));
  sort(ALL(bc), greater<Pii>());
  int ans = 0, l = 0;
  rep(i, 0, m) {
    int r = upper_bound(a.begin() + l, a.end(), bc[i].F) - a.begin();
    if (r > bc[i].S + l) r = bc[i].S + l;
    ans += bc[i].F * (r - l);
    l = r;
  }
  if (l != n) {
    rep(i, l, n) ans += a[i];
  }
  cout << ans << endl;
  return 0;
}



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

int main(){
    int n;
    cin >> n;
    vector<int> X(n);
    int ans =0;
    for(int i=0; i<n; i++){
        cin >> X.at(i);
        ans += X.at(i)*X.at(i);
    }
    for(int p=1; p<=100; p++){
        int power=0;
        for(int i=0; i<n; i++){
            power += (p-X.at(i))*(p-X.at(i));
        }
        ans = min(ans, power);
    }
    cout << ans << endl;
}

Measured memory_bytes: 3576
import sys
if sys.argv[-1] == 'ONLINE_JUDGE':
    import os, zlib, base64
    open('solve.pyx', 'wb').write(zlib.decompress(base64.b85decode("c${rg?P`QD5d7~`ER<5McXC316zM&QJxYwLw=|bXvi9iPcVn!*mIj3E%<Q-yxr3ep&rBvXV3ZwaHR4g1Wj1(s0YjahrYazVrpx3!gWP{{AE?>+jZWc@q6*xT+vpKlpOxRi<jL}obo!Ie&Q@+huWr41^f<_8HG&E$jG5S@_IN?d3D%kJaR4!tRGSxI-AJa%K+eW=JJ4{1!-8JVWDx2kiKi24txfXx@btV<Gzj|whXy*2>V3nbn}$cI4^Tq4z#e(_7H;aXQ50+10VUKpJANzDu-XWnK#BAg$Ze4gG7S<V@Uj{dqyg2Y9`{h6Bx7}zt*kadz%9z#eZ2#FD*mV{;&s-<|NLZWhB!J^#$D0Bb#AtOu38eS)O>k_eA!4&9IIJ48OI`$IB~L^$QKJkGN?M`hl*@K&#Ps64f(^p>0j-GY^un<0PhaYas")))
    os.system('cythonize -i -3 -b solve.pyx')
import solve

Measured memory_bytes: 22192
#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;
long long n,k;
int main()
{
	scanf("%lld%lld",&n,&k);
	if(k*2LL==n)
	{
		printf("%lld",3LL*k);
	}
	else
	{
		long long res=n,x,y;
		if(k<n-k)
		{
			x=k;
			y=n-k-k;
			res+=2LL*x;
		}
		else
		{
			x=n-(n-k)-(n-k);
			y=n-k;
			res+=2LL*y;
		}
		while(x!=0LL && y!=0LL)
		{
			if(x<y)
			{
				res+=(y-1LL)/x*2LL*x;
				y%=x;
				res+=y*2LL;
				x-=y;
			}
			else
			{
				res+=(x-1LL)/y*2LL*y;
				x%=y;
				res+=x*2LL;
				y-=x;
			}
		}
		res+=x+y;
		printf("%lld",res);
	}
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<deque>
#include<cmath>
#include<iomanip>
#include<map>
#include<cstring>

using namespace std;

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using ll = long long;
using P = pair<int, int>;
const int INF = 1e9;
const ll LLINF = 4 * 1e18;
/* -- template -- */
int A, B, C, D, E, F;

int ff(int cap) {
    int minv = INF;
    for(int i = 0;i <= cap;++i) {
        int capC = i, capD = cap - i;
        minv = min(minv, capC % C + capD % D);
    }
    return ((minv == INF) ? cap : minv);
}

int main() {
    cin >> A >> B >> C >> D >> E >> F;
    int ansSugar, ansWater;
    double maxv = 0.0;
    for(int nA = 0; nA <= int(F / (100.0 * A)); ++nA){
        for(int nB = 0; nB <= int(F / (100.0 * B)); ++nB){
            int water = (nA * A + nB * B) * 100.0;
            if(water == 0)continue;
            int cap = F - water;
            cap = min(cap, (nA * A + nB * B) * E);

            int sugar = cap - ff(cap);

            if(double(sugar) * 100.0 / double(sugar + water) >= maxv)
                ansSugar = sugar, ansWater = water, maxv = double(sugar) * 100.0 / double(sugar + water);
        }
    }
    cout << ansWater + ansSugar << ' ' << ansSugar << endl;
}


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"

using namespace std;

const long long int MOD = 1000000007;

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

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

	cin >> N;
	vector<long long int>v(N+1);
	for (int i = 1; i <= N; i++) {
		cin >> v[i];
	}
	for (int i = 1; i <= N; i++) {
		v[i] += v[i - 1];
	}
	map<long long int, long long int>m;
	for (auto i : v) {
		m[i]++;
	}
	long long int ans = 0;
	for (auto i : m) {

		ans += (i.second - 1)*(i.second) / 2;
	}
	cout << ans << endl;
	return 0;
}


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

int main()
{
    string s;
    cin >> s;
    for(int i = 0; i < 19; i++){
        if(s[i] == ',') printf(" ");
        else printf("%c", s[i]);
    }
    cout << endl;
    return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
int main()
{
  long int x,save=100,a=0;
  scanf("%ld",&x);
  while(1){
    save=save*0.01+save;
    a++;
    if(x<=save){
      printf("%ld\n",a);
      break;
    }
  }
  return 0;
}


Measured memory_bytes: 2152
s=list(input())
k=int(input())
ss=s*2
a,b=0,0
i=1
while i<len(s):
    if s[i]==s[i-1]:
        i+=2
        a+=1
    else:
        i+=1
i=1        
while i<len(ss):
    if ss[i]==ss[i-1]:
        i+=2
        b+=1
    else:
        i+=1    
if len(set(s))==1:
    print(len(s)*k//2)
else:
    print(a+(b-a)*(k-1))

Measured memory_bytes: 3064
N=int(input())
DP=[0]*(N+1)
def fin(n):
    if DP[n]!=0:
        return DP[n]
    if n<=1:
        DP[n]=1
        return DP[n]
    else:
        DP[n]=fin(n-1)+fin(n-2)
        return DP[n]
print(fin(N))


Measured memory_bytes: 5600
import queue
import math
import copy
"""
N = int(input())
#S = input()
# (N,M) = (int(i) for i in input().split(" "))
# A = [int(i) for i in input().split()]
A = []
for i in range(N):
	A.append(int(input()))

print(A)

"""
(N,M) = (int(i) for i in input().split(" "))
if N==1 or M==1:
	print(1)
else:
	S = N%2 + M%2
	T = (N-N%2)*(M-M%2)//2
	if N%2:
		T += (M+1)//2
	if M%2:
		T += (N+1)//2
	if S == 2:
		T -= 1
	print(T)


Measured memory_bytes: 4080
#include<cstdio>
#include<vector>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=202202;
int a[N],p[N],be[N],c[N];
ll sum[N],sm[N];
vector <int> v[N];
int n,k,tot;
ll ans=-1e18;
void dfs(int x,int id){
	if (be[x])	return;
	be[x]=id;
	v[id].push_back(c[x]);
	dfs(p[x],id);
}
int main(){
	scanf("%d%d",&n,&k);
	for (int i=1; i<=n; i++)
		scanf("%d",&p[i]);
	for (int i=1; i<=n; i++)
		scanf("%d",&c[i]);
	for (int i=1; i<=n; i++)
		if (!be[i])	dfs(i,++tot);
	for (int i=1; i<=tot; i++){
		for (int j=0; j<(int)v[i].size(); j++)
			a[j+1]=a[j+(int)v[i].size()+1]=v[i][j];
		int m=v[i].size();
		for (int j=1; j<=2*m-1; j++)
			sum[j]=sum[j-1]+a[j];
		sm[0]=-1e18;
		for (int s=1; s<=m; s++){
			sm[s]=-1e18;
			for (int j=1; j<=2*m-s; j++)
			sm[s]=max(sm[s],sum[j+s-1]-sum[j-1]);
			sm[s]=max(sm[s],sm[s-1]);
		}
		if(sum[m]<=0)	ans=max(ans,sm[min(m,k)]);	
		else {
			if (k>=m){
				ans=max(ans,max(sum[m]*(k/m)+sm[k%m],sum[m]*(k/m-1)+sm[m]));
			}else ans=max(ans,sm[k]);
		}
	}
	printf("%lld\n",ans);
    return 0;
}

Measured memory_bytes: 8276
#include"bits/stdc++.h"
//#include<bits/stdc++.h>
using namespace std;
#define print(x) cout<<x<<endl;
#define rep(i,a,b) for(int i=a;i<b;i++)
typedef long long ll;
//const int mod = 1e9 + 7;

int main() {
	string s;
	cin >> s;
	bool flag1 = false, flag2 = false;
	if (s.size() % 2 == 0) { flag1 = 1; }
	if (s[0] == s[s.size()-1]) { flag2 = 1; }
	if (flag1^flag2) { print("Second"); }
	else{print("First") }
}

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

int main()
{
    int A, B, K;
    cin >> A >> B >> K;

    int count = 0;
    int result = 0;

    int t = max(A, B);

    for(int i = t; i > 0; i--)
    {
        if(A % i == 0 and B % i == 0)
        {
            count += 1;
            if(count == K)
            {
                result = i;
                break;
            }
        }
    }    
    cout << result << endl;
    return 0;
}

Measured memory_bytes: 256
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#define rep(i, n) for(int i=0; i<n; ++i)
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
using namespace std;
using ll = int64_t;
using P = pair<int, int>;
using vs = vector<string>;
using vi = vector<int>;
using vvi = vector<vi>;
const int INF = 100010001;
const ll LINF = (ll)INF*INF*10;

int main() {
    int n;
    cin >> n;
    vector<ll> a(n);
    rep(i, n) {
        cin >> a[i];
    }
    sort(all(a));

    ll ans = 1;
    __int128_t aa = 1;
    rep(i, n) {
        ans *= a[i];
        aa *= a[i];
        if(aa > 1000000000000000000) {
            cout << -1 << endl;
            return 0;
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 3996
#define _USE_MATH_DEFIMES
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cctype>
#include <climits>
#include <clocale>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <regex>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

const int MOD = 1'000'000'007;
const int INF = 1'000'000'000; //1e9
const int NIL = -1;
const long long LINF = 1'000'000'000'000'000'000; // 1e18
const long double EPS = 1E-10;

template<class T, class S> inline bool chmax(T &a, const S &b){
    if(a < b){
        a = b; return true;
    }
    return false;
}
template<class T, class S> inline bool chmin(T &a, const S &b){
    if(b < a){
        a = b; return true;
    }
    return false;
}







int main(){
    int N; std::cin >> N;
    std::vector<int> A(N);
    int mxa(0);
    for(int i(0); i < N; ++i){
        std::cin >> A[i];
        chmax(mxa, A[i]);
    }
    std::sort(std::begin(A), std::end(A));
    std::vector<bool> okay(mxa + 1, true), has(mxa + 1, false);
    for(int i(0); i < N; ++i){
        if(has[A[i]]) okay[A[i]] = false;
        if(okay[A[i]]){
            for(int j(2*A[i]); j <= mxa; j += A[i]){
                okay[j] = false;
            }
            has[A[i]] = true;
        }
    }
    int ans(0);
    for(int i(0); i < N; ++i) if(okay[A[i]]) ++ans;
    std::cout << ans << std::endl;
    return 0;
}


Measured memory_bytes: 4224
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        // String n = sc.next();
        sc.close();

        int ans = 0;
        for(int i=0; i<1000000; i++){
            String s = Integer.toString(i, 4);
            s = s.replace('2', '5');
            s = s.replace('3', '7');
            s = s.replace('1', '3');
            if(Long.parseLong(s) > n){
                break;
            }
            boolean[] exist = new boolean[4];
            for(int j=0; j<s.length(); j++){
                if(s.charAt(j) == '3') exist[0] = true;
                if(s.charAt(j) == '5') exist[1] = true;
                if(s.charAt(j) == '7') exist[2] = true;
                if(s.charAt(j) == '0') exist[3] = true;
            }
            if(exist[0] && exist[1] && exist[2] && !exist[3]){
                ans++;
            }
        }

        System.out.println(ans);

        // long[] num = new long[9];
        // num[0] = 0;
        // num[1] = 0;
        // num[2] = 6;
        // for(int i=3; i<9; i++){
        //     num[i] = Math.pow(3, i+1) - 3*Math.pow(2, i+1) + 3;
        // }

        // String s = (String)n;
        // long ans = 0;
        // for(int i=0; i<s.length() - 1; i++){
        //     ans += num[i];
        // }

        // for(int =0; <; ++){
            
        // }
    }
}

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

int main() {
  int a,b,c;
  cin >> a >> b >> c;
  if (a == b || b == c || c == a) {
    if (a == b && b == c) cout << 1 << endl;
    else cout << 2 << endl;
  }
  else cout << 3 << endl;
} 

Measured memory_bytes: 256
class BinaryIndexedTree:
  def __init__(self,n):
    self.bit=[0]*n
  def add(self,i,x):
    i+=1
    while i<=len(self.bit):
      self.bit[i-1]+=x
      i+=i&-i
  def sum_sub(self,i):
    a=0
    i+=1
    while i:
      a+=self.bit[i-1]
      i-=i&-i
    return a
  def sum(self,i,j):
    a=self.sum_sub(j+1)
    if i!=0:a-=self.sum_sub(i-1)
    return a
n,q=map(int,input().split())
a=list(map(int,input().split()))
ans=[0]*q
queries=[[]for _ in range(n)]
for i in range(q):
  l,r=map(int,input().split())
  l-=1
  r-=1
  queries[r].append((l,i))
lastAppeared=[-1]*n
bitt=BinaryIndexedTree(n)
j=0
for i in range(n):
  if lastAppeared[a[i]-1]!=-1:
    bitt.add(lastAppeared[a[i]-1],-1)
    bitt.add(i,1)
    lastAppeared[a[i]-1]=i
  else:
    bitt.add(i,1)
    lastAppeared[a[i]-1]=i
  for l,ind in queries[i]:
    ans[ind]=bitt.sum(l,i-1)
print(*ans)


Measured memory_bytes: 204304
#include<stdio.h>
int went[200000];
int way[200000];
int main(void){
    int i,n,fl,cnt;
    for(i=0;i<200000;i++){
        went[i]=0;
    }
    scanf("%d",&n);
    for(i=1;i<=n;i++){
        scanf("%d",&way[i]);
    }
    fl=1;
    went[1]++;
    cnt=0;
    while(1){
        fl=way[fl];
        cnt++;
        went[fl]++;
        if(went[fl]>1){
            printf("-1\n");
            return 0;
        }
        if(fl==2){
            break;
        }
    }
    printf("%d\n",cnt);
    return 0;
}



Measured memory_bytes: 1408
N= int(input())
V = list(map(int, input().split()))
C = list(map(int, input().split()))
V_add = 0
C_add = 0
for i in range(N):
  if V[i] > C[i]:
    V_add += V[i]
    C_add += C[i]
  else:
    continue
    
print(V_add - C_add)

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


int main(){
  int n,k;cin>>n>>k;
  int a[n];
  int x[n+1]={};
  for(int i=0;i<n;i++){cin>>a[i];x[a[i]]+=1;}
  sort(x,x+n+1,greater<int>());

  int sum=n;
  
  for(int i=0;i<k;i++){
    sum-=x[i];
  }

  cout<<sum<<endl;
  return 0;
}


Measured memory_bytes: 1792
inf = 10**12


def main():
    import sys
    from random import randint
    from bisect import bisect_left
    input = sys.stdin.readline

    D = int(input())
    C = list(map(int, input().split()))
    S = []
    for _ in range(D):
        S.append(list(map(int, input().split())))
    ans = 0
    last = [-1] * 26
    days = [[-1] for _ in range(26)]
    T = []
    # greedy
    for d in range(D):
        plus = -inf
        t = -1
        for tt in range(26):
            plus_new = S[d][tt] + C[tt] * (d - last[tt])
            if plus_new > plus:
                t = tt
                plus = plus_new
        T.append(t)
        ans += S[d][t]
        last[t] = d
        days[t].append(d)
        for i in range(26):
            ans -= C[i] * (d - last[i])
    for t in range(26):
        days[t].append(D)

    def calc(d, q, cur):
        t = T[d]
        cur += S[d][q]
        cur -= S[d][t]
        i = bisect_left(days[q], d)
        cur += C[q] * (d - days[q][i - 1]) * (days[q][i] - d)
        j = bisect_left(days[t], d)
        cur -= C[t] * (d - days[t][j - 1]) * (days[t][j + 1] - d)
        return cur

    # climb
    size = 5
    try_num = 1000
    for x in range(D // size):
        d_list = list(range(x*size, (x+1)*size))
        for _ in range(try_num):
            t_new = [randint(0, 25) for _ in range(size)]
            ans_new = ans
            for i, d in enumerate(d_list):
                ans_new = calc(d, t_new[i], ans_new)
            if ans_new > ans:
                ans = ans_new
                for i, d in enumerate(d_list):
                    t_old = T[d]
                    T[d] = t_new[i]
                    days[t_new[i]].append(d)
                    days[t_new[i]].sort()
                    days[t_old].remove(d)
    for t in T:
        print(t+1)


if __name__ == '__main__':
    main()


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

#define rep(i,x,y) for(ll i=(x);i<(y);i++)
#define rrep(i,x,y) for(ll i=(ll)(y)-1;i>=(x);i--)
#define all(x) (x).begin(),(x).end()
#ifdef LOCAL
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl
#define itrdebug(x) cerr << #x << " "; for (auto & el : (x)) {cerr << (el) << " ";} cerr << endl
#define dassert(...) assert(__VA_ARGS__)
#else
#define debug(x)
#define itrdebug(x)
#define dassert(...)
#endif
//#define int long long

typedef long long ll;
const ll MOD = 1e9 + 7;
const long double EPS = 1e-8;

void solve(long long N){
    ll answer = 0;
    rep(i,1,N+1) {
        ll current = i;
        while (current <= N) {
            answer += current;
            current += i;
        }
    }
    cout << answer << endl;
}

signed main(){
    // ios_base::sync_with_stdio(false);
    // cin.tie(NULL);
    long long N;
    scanf("%lld",&N);
    solve(N);
    return 0;
}


Measured memory_bytes: 3764
// ref. https://atcoder.jp/contests/tokiomarine2020/submissions/14238080

#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <unordered_map>
#include <vector>
#include <string.h>
#include <set>
#include <stack>

using namespace std;

#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl

template<class T> void printvec(const vector<T>& v) {
  for (auto x : v) { cout << x << " "; }
  cout << endl;
}
template<class T> void printtree(const vector< vector<T> >& tree) {
  for (long long i = 0; i < tree.size(); ++i) {
    cout << i + 1 << ": "; printvec(tree[i]);
  }
}
template<class T, class U> void printmap(const map<T, U>& mp) {
  for (auto x : mp) { cout << x.first << "=>" << x.second << endl; }
}

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; }

#define rep(i, n) for(ll i = 0; i < n; ++i)
#define all(s) s.begin(), s.end()
#define sz(x) (ll)(x).size()
#define fr first
#define sc second
#define mp make_pair
#define pb push_back
#define eb emplace_back

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
typedef tuple<ll, ll, ll> triple;
typedef double D;
typedef vector<ll> vl;
typedef vector<P> vp;

const ll INF = 1e9;
const ll MOD = 1000000007;  // 1e9 + 7

int main(int argc, char** argv) {
  cin.tie(NULL);
  cout.tie(NULL);
  ios_base::sync_with_stdio(false);
  //cout << setprecision(10) << fixed;

  ll n,k,s,t;
  cin >> n >> k >> s >> t;
  vector<ll> a(n);
  rep(i,n) {
    cin >> a[i];
  }

  // Check t,s
  if ((t&s) != s) {
    cout << 0 << endl;
    return 0;
  }

  // Pre-calculation of Combination
  vector<vector<ll>> comb(n+1, vector<ll>(n+1));
  rep(i,n+1) {
    comb[i][0] = 1;
    for (int j = 1; j <= i; ++j) {
      comb[i][j] = comb[i-1][j-1] + comb[i-1][j];
    }
  }
  // ways[i] .. sum of comb[i][j] where j <= k
  vector<ll> ways(n+1);
  rep(i,n+1) {
    for (int j = 1; j <= min(i,k); ++j) {
      ways[i] += comb[i][j];
    }
  }

  ll ans = 0;
  rep(mask,1ll<<18) {
    // Check mask. mask must be in t^s.
    if ((mask&(t^s)) != mask) {
      continue;
    }

    int sign = (__builtin_popcount(mask)%2 == 0 ? 1 : -1);
    map<ll,ll> cnts;
    rep(i,n) {
      // First, check the validness of a[i]. a[i] must include s. a[i] must not exceed t.
      if ((a[i]&s) != s) {
        continue;
      }
      if ((a[i]|t) != t) {
        continue;
      }
      ++cnts[a[i]&mask];
    }

    for (auto& p : cnts) {
      ans += sign * ways[p.second];
    }
  }
  cout << ans << endl;
}


Measured memory_bytes: 3668
#include<iostream>
#include<cstdio>
#include<cstring>
#include <cstdlib>  
#include <math.h>
#include <cmath>
#include<cctype>
#include<string>
#include<set>
#include<iomanip>
#include <map>
#include<algorithm>
#include <functional>
#include<vector>
#include<climits>
#include<stack>
#include<queue>
#include<bitset>
#include <deque>
#include <climits>
#include <typeinfo>
#include <utility> 
using namespace std;
using ll = long long;
template<typename T>using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;
const ll MOD = 1e9 + 7;
const ll inf = 1LL << 60;
#define all(x) (x).begin(),(x).end()
#define puts(x) cout << x << endl;
#define rep(i,m,n) for(ll i = m;i < n;++i)
#define pb push_back
#define fore(i,a) for(auto &i:a)
#define rrep(i,m,n) for(ll i = m;i >= n;--i)
#define INF INT_MAX/2


int main() {
	int N, X;
	cin >> N >> X;
	vector<int>S(N);
	rep(i, 0, N)cin >> S[i];
	sort(all(S));
	vector<vector<ll>>dp(N + 1, vector<ll>(X + 1));
	rep(i, 0, X+1)dp[0][i] = i;
	rep(i, 0, N)rep(j, 0, X+1) {
		dp[i + 1][j] = dp[i][j%S[i]] + i * dp[i][j];
		dp[i + 1][j] %= MOD;
	}

	cout << dp[N][X] << endl;

	return 0;
}

Measured memory_bytes: 158592
def main():
    S = input()
    T = input()

    ans = f(S, T)
    if ans:
        print("Yes")
    else:
        print("No")


def f(S, T):
    for i in range(len(S)):
        t = S[-i:] + S[:-i]
        #print(S[-i:], S[:-i])
        if t == T:
            return True

    return False


if __name__ == '__main__':
    main()


Measured memory_bytes: 2940