akhauriyash/Code-Regression huggingface dataset:
/*** author: yuji9511 ***/
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using lpair = pair<ll, ll>;
const ll MOD = 1e9+7;
const ll INF = 1e18;
#define rep(i,m,n) for(ll i=(m);i<(n);i++)
#define rrep(i,m,n) for(ll i=(m);i>=(n);i--)
#define printa(x,n) for(ll i=0;i<n;i++){cout<<(x[i])<<" \n"[i==n-1];};
void print() {}
template <class H,class... T>
void print(H&& h, T&&... t){cout<<h<<" \n"[sizeof...(t)==0];print(forward<T>(t)...);}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll N;
    cin >> N;
    ll A[100010];
    rep(i,0,N) cin >> A[i];
    ll red = 0, blue = 0, green = 0;
    ll ans = 1;
    rep(i,0,N){
        if(red == blue && blue == green){
            if(red != A[i]){
                print(0);
                return 0;
            }
            ans *= 3;
            ans %= MOD;
            red++;
        }else if(red == blue){
            if(A[i] == red){
                ans *= 2;
                ans %= MOD;
                red++;
            }else if(A[i] == green){
                green++;
            }else{
                print(0);
                return 0;
            }
        }else if(blue == green){
            if(A[i] == blue){
                ans *= 2;
                ans %= MOD;
                blue++;
            }else if(A[i] == red){
                red++;
            }else{
                print(0);
                return 0;
            }
        }else if(red == green){
            if(A[i] == red){
                ans *= 2;
                ans %= MOD;
                red++;
            }else if(A[i] == blue){
                blue++;
            }else{
                print(0);
                return 0;
            }
        }else{
            if(A[i] == red){
                red++;
            }else if(A[i] == blue){
                blue++;
            }else if(A[i] == green){
                green++;
            }else{
                print(0);
                return 0;
            }
        }
    }
    print(ans);

}

Measured memory_bytes: 1024
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <stdlib.h>
#include <cmath>
#include <numeric>
#include <functional>
#include <stack>
#include <iomanip>
#include <map>
#include <cstdio>

int main() {
	long long h, n;

	std::cin >> h >> n;

	long long sum = 0;

	for (long long i = 0; i < n; i++)
	{
		long long a;
		std::cin >> a;

		sum += a;
	}

	if (sum >= h) {
		std::cout << "Yes" << std::endl;
	}
	else {
		std::cout << "No" << std::endl;
	}

	return 0;
}

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

const int MAXN = 2e5 + 5;

vector<int> edges[MAXN];
long long a[MAXN], add[MAXN];
bool vis[MAXN];

void dfs(int u, long long qtt) {
  vis[u] = true;
  a[u] = add[u] + qtt;

  for (int v : edges[u]) {
    if (!vis[v]) dfs(v, qtt + add[u]); 
  }
}

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

  int n, q; cin >> n >> q;

  for (int i = 1; i <= n-1; i++) {
    int u, v;  cin >> u >> v;
    edges[u].push_back(v);
    edges[v].push_back(u);
  }

  while(q--) {
    int u, x; cin >> u >> x;
    add[u] += x;
  }

  dfs(1, 0);
  for (int i = 1; i <= n; i++) cout << a[i] << ' ';
  cout << endl;


}

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

int main(){
  int n;
  cin >> n;
  bool ok=true;
  int b;
  for(int i=0;i<n;i++){
    cin >> b;
    if(b%2==0)
      if(b%3!=0&&b%5!=0)
        ok=false;
  }
  cout << (ok?"APPROVED":"DENIED") << endl;
  return 0;
}

Measured memory_bytes: 3632
#include <iostream>
#include <vector>
#include <unordered_set>
#include <utility>
using namespace std;
using ll = long long;

struct phash{
	inline size_t operator()(const pair<int,int> & p) const{
		const auto h1 = hash<int>()(p.first);
		const auto h2 = hash<int>()(p.second);
		return h1 ^ (h2 << 1);
	}
};

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

	int H, W, M;
	cin >> H >> W >> M;
	unordered_set<pair<int, int>, phash> tg;
	vector<int> sumr(H, 0), sumc(W, 0);
	for (int i = 0; i < M; i++) {
		int h, w;
		cin >> h >> w;
		tg.insert(make_pair(h - 1, w - 1));
		sumr[h - 1]++;
		sumc[w - 1]++;
	}

	unordered_set<int> maxi, maxj;
	int maxsumr = 0, maxsumc = 0;
	for (int i = 0; i < H; i++) {
		if (sumr[i] > maxsumr) {
			maxi.clear();
			maxsumr = sumr[i];
			maxi.insert(i);
		} else if (sumr[i] == maxsumr) {
			maxi.insert(i);
		}
	}
	for (int j = 0; j < W; j++) {
		if (sumc[j] > maxsumc) {
			maxj.clear();
			maxsumc = sumc[j];
			maxj.insert(j);
		} else if (sumc[j] == maxsumc) {
			maxj.insert(j);
		}
	}
	bool n = true;
	for (auto i : maxi) {
		bool f = false;
		for (auto j : maxj) {
			if (!tg.count(make_pair(i, j))) {
				n = false;
				f = true;
				break;
			}
		}
		if (f) {
			break;
		}
	}
	cout << maxsumr + maxsumc - n << "\n";
	return 0;
}


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

using ld = long double;
const ld eps = 1e-8, pi = acos(-1.0);

bool eq(ld a, ld b) {
	return abs(a - b) < eps;
}

using Point = complex<ld>;
class Line {
public:
	Point a, b;
};
class Circle {
public:
	Point p;
	ld r;
};

ld dot(Point a, Point b) {
	return real(conj(a) * b);
}

ld cross(Point a, Point b) {
	return imag(conj(a) * b);
}

int ccw(Point a, Point b, Point c) {
	b -= a, c -= a;
	if (cross(b, c) > eps) return 1;
	if (cross(b, c) < -eps) return -1;
	if (dot(b, c) < 0) return 2;
	if (norm(b) < norm(c)) return -2;
	return 0;
}

bool isis_ll(Line l, Line m) {
	return abs(cross(l.b - l.a, m.b - m.a)) > eps;
}

bool isis_ls(Line l, Line s) {
	return (cross(l.b - l.a, s.a - l.a) * cross(l.b - l.a, s.b - l.a) < eps);
}

bool isis_lp(Line l, Point p) {
	return abs(cross(l.b - p, l.a - p)) < eps;
}

bool isis_sp(Line s, Point p) {
	return abs(s.a - p) + abs(s.b - p) - abs(s.b - s.a) < eps;
}

Point proj(Line l, Point p) {
	ld t = dot(p - l.a, l.a - l.b) / norm(l.a - l.b);
	return l.a + t * (l.a - l.b);
}

Point is_ll(Line s, Line t) {
	Point sv = s.b - s.a, tv = t.b - t.a;
	assert(cross(sv, tv) != 0);
	return s.a + sv * cross(tv, t.a - s.a) / cross(tv, sv);
}

int main()
{
	int q;
	ld x1, x2, x3, x4, y1, y2, y3, y4;
	cout << fixed << setprecision(10);
	cin >> q;
	while (q--) {
		cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3 >> x4 >> y4;
		Line l1 = { (Point) { x1, y1 }, (Point) { x2, y2 } };
		Line l2 = { (Point) { x3, y3 }, (Point) { x4, y4 } };
		Point res = is_ll(l1, l2);
		cout << res.real() << ' ' << res.imag() << endl;
	}
	return 0;
}

Measured memory_bytes: 3268
#include <bits/stdc++.h>
#include<limits.h>
#include<stdio.h>
#include<cstring>
#include<string>
using namespace  std;
typedef long long ll;
typedef long double ld;
#define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define pb push_back
#define mp make_pair
#define sz(a) a.size()
#define fi first
#define se second
#define rsz(a,n) a.resize(n)
#define test(t) ll t;cin>>t;while(t--)
#define forn(i,e) for(int i = 0; i < e; i++)
#define forsn(i,s,e) for(int i = s; i < e; i++)
#define rforn(i,s) for(int i = s; i >= 0; i--)
#define rforsn(i,s,e) for(int i = s; i >= e; i--)
#define fillv(a,k) memset(a,k,sizeof(a))
#define leadzero(a) __builtin_clz(a) //count leading zeros
#define trailzero(a) __builtin_ctz(a) //count trailing zeros
#define bitcount(a) __builtin_popcount(a) // count set bits (add ll)
#define ln cout<<"\n"
// #define sp cout<<" "
#define spaceprint(a,i,s,n) {forsn(i,s,n) { cout<<a[i]; sp;}}
#define lineprint(a,i,s,n) {forsn(i,s,n) {cout<<a[i]; ln;}}
#define maxe(a) *max_element(a.begin(),a.end())
#define maxi(a) max_element(a.begin(),a.end())-a.begin()
#define mine(a) *min_element(a.begin(),a.end())
#define mini(a) min_element(a.begin(),a.end())-a.begin()
#define all(c) c.begin(),c.end()
#define trav(container, it) for(typeof(container.begin()) it = container.begin(); it != container.end(); it++)
#define present(container, element) (container.find(element) != container.end())
#define cpresent(container, element)  (find(all(container),element) != container.end())// check the presence of element
//copy(from_begin, from_end, to_begin); copy function
typedef unsigned long long int ull;
typedef long double ld;
typedef pair<ll,ll> p64;
typedef pair<int,int> p32;
typedef pair<int,p32> p96;
typedef vector<ll> v64;
typedef vector<string> vs;
typedef vector<int> v32;
typedef vector<v32> vv32;
typedef vector<v64> vv64;
typedef vector<p32> vp32;
typedef vector<p64> vp64;
typedef vector<vp32> vvp32;
typedef map<int,int> m32;
typedef map<ll,ll> m64;
const int LIM = 1e5+5, MOD =  1e9;
#define sumv(v) accumulate(all(v),ll(0))
#define productv(v) accumulate(all(v), ll(1), multiplies< ll >())
ll gcd(ll a, ll b) { if(b == 0) return a; return gcd(b, a % b); }
ll fastpowMOD(ll a, ll p,ll MOD){ if(p==0) return 1; ll z = fastpowMOD(a,p/2,MOD); z = (z*z)%MOD; if(p%2) z = (z*a)%MOD; return z; }
bool seive[100005];
void SieveOfEratosthenes(ll n)
{ memset(seive, true, sizeof(seive)); for (ll p=2; p*p<=n; p++) if (seive[p] == true) for (ll i=p*p; i<=n; i += p) seive[i] = false; }
// ll a[11*LIM]={0},b[11*LIM]={0};
// vp64 v[LIM];
typedef struct 
{
	ll one,two,three;
}data;





int main()
{
	fast;
	ll n;
	cin>>n;
	ll a=n/500;
	ll b=n%500;
	ll c=b/5;
	// cout<<a<<" "<<b<<endl;
	cout<<a*1000+c*5;

} 

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

using namespace std;

#define mp make_pair
#define fi first
#define se second
#define all(v) v.begin(),v.end()
#define allarr(a) a , a + n
#define ll long long
#define ull unsigned long long 
#define pb push_back
#define fastio ios_base::sync_with_stdio(false) ; cin.tie(NULL); cout.tie(NULL)
typedef pair<int, int> pi;
typedef pair<ll,ll> pll; 
typedef pair<int,pi> trp ;
typedef vector<pi> vpi;
typedef vector<pll> vpll ;
// int ab  (int  x ) { return (x>0?x:-x); }
//
int main(){
	string s ; cin >> s; 

		if( s== "Sunny" )cout << "Cloudy"<<endl;
		if( s== "Cloudy")cout <<"Rainy"<<endl;
		if( s== "Rainy" ) cout << "Sunny"<<endl; 
	
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std; 
int main(){
	int N; string S; 
	cin >> N >> S; 
	int A[214514] = {}; // i番目から黒が始まるときの修正個数 A[0] が all 黒で A[N] が all 白
	int kuro = 0; 
	for(int i = 0; i < N; i++){
		if(S.at(i) == '#') kuro ++; 
	}
	A[0] = N - kuro; 
	for(int i = 1; i <= N; i++){
		if(S.at(i-1) == '#') A[i] = A[i-1] + 1; 
		else A[i] = A[i-1] - 1; 
	}
	int ans = 214514; 
	for(int i = 0; i <= N; i++){
		ans = min(ans, A[i]);
	}
	cout << ans << endl;
}

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

int main(){

	//初期化
	int n;
	cin >> n;

	int a[n];

	for(int i = 0; i < n; i++){
		cin >> a[i];
	}


	//反転表示
	for(int i = 0; i < n; i++){
		cout << a[n-1-i] ;
		if(i == n-1) break;
		else cout << " ";
	}

	cout << endl;

	return 0;

}


Measured memory_bytes: 3096
#include<iostream>
#include<cmath>
#include<complex>
#include<cstdlib>
#include<algorithm>
#include<functional>
using namespace std;
int main() {
    int a,b,c,d;
    cin>>a>>b>>c>>d;
    if(abs(a-b)<=d&&abs(b-c)<=d||abs(a-c)<=d){
        cout<<"Yes"<<endl;
    }else{
        cout<<"No"<<endl;
    }
    
    return 0;
}


Measured memory_bytes: 256
N,K = map(int,input().split())
array = []
sum = 0
for i in range(N):
    a,b = map(int,input().split())
    array.append([a,b])
array.sort(key = lambda x:x[0])
for i in range(N):
    sum += array[i][1]
    if sum >= K:
        print(array[i][0])
        exit()

Measured memory_bytes: 21248
N = int(input())
T1 = int(input())
if N == 1:
    print(T1)
else:
    ans = T1
    T = T1
    for i in range(N - 1):
        T2 = int(input())
        a = ans
        b = T2
        a, b = sorted([a, b])
        while True:
            if b % a == 0:
                break
            else:
                a, b = b % a, a
        ans = int(ans * T2 // abs(a))

    print(ans)

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

using namespace std ; 

const int N = 1e5 + 7 ; 


int main(){
    ios_base::sync_with_stdio(0) ; 
    cin.tie(0) ; 
   // freopen("in.in" , "r" , stdin) ; 
    int a , b , c; 
    cin>>a>>b>>c  ; 
    cout<<c<<" " << a << " " << b ; 
     


    return 0 ; 
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	static long MOD = 1000000007;

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

		int N = sc.nextInt();
		int M = sc.nextInt();

		boolean[] broken =new boolean[N+1];

		for (int i = 0; i < M; i++) {
			broken[sc.nextInt()] = true;
		}

		long[] dp=new long[N+1];
		dp[0] = 1;
		for (int i = 1; i < N +1; i++) {
			if (broken[i]) {
				continue;
			}else {
				long con = 0;
				//1段
				con = con + dp[i-1] % MOD;

				//2段
				if (i-2 >= 0) {
					con = con + dp[i-2] % MOD;
				}
				dp[i] = con;
			}
		}

		System.out.println(dp[N] % MOD);

	}

}


Measured memory_bytes: 58592
a = input()
b = input()
c = input()
sa = [a[i] for i in range(len(a))]
sb = [b[i] for i in range(len(b))]
sc = [c[i] for i in range(len(c))]

n = 'a'

while True:
  if n == 'a':
    if len(sa) == 0:
      print('A')
      break
    else:
      n = sa.pop(0)
  elif n == 'b':
    if len(sb) == 0:
      print('B')
      break
    else:
      n = sb.pop(0)
  else:
    if len(sc) == 0:
      print('C')
      break
    else:
      n = sc.pop(0)

Measured memory_bytes: 9092
#define _CRT_SECURE_NO_WARNINGS

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

typedef unsigned int uint;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<string> vs;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef map<int, int> mii;
typedef map<string, int> msi;
typedef map<int, string> mis;
typedef pair<int, ii> edge;


#define sc(x)  scanf("%d",&x)
#define scl(x) scanf("%lld",&x)
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define mem(arr,val) memset(arr,val,sizeof arr)
#define sz(v) (int)v.size()
#define rsz(v) v.resize
#define clr(v) v.clear()
#define rev(v) reverse(all(v))
#define lop(i,end) for(int i=0; i<end; i++)
#define rlop(i,start) for(int i=start-1; i>=0; i--)
#define loop(i,start,end) for(int i=start; i<end; i++)
#define rloop(i,start,end) for(int i=start-1; i>=end; i--)
#define PB push_back
#define pb pop_back
#define mP make_pair
#define f first
#define s second

const ll OO = (ll)(4e18) + 9;
const int MOD = (int)(1e9) + 7;
const int oo = 2147483647;
const double EPS = 1e-8;
const double PI = acos(-1.0);

//enum dir { d, r, u, l , dr, ur, dl, ul };
int dx[] = { 1, 0, -1, 0, 1, -1, 1, -1 };
int dy[] = { 0, 1, 0, -1, 1, 1, -1, -1 };

string abc = "abcdefghijklmnopqrstuvwxyz";
string vowels = "aeiou"; //and sometimes "aeiouy"

template<typename X, typename Y> bool ckmin(X& a, Y b) { return a > b ? a = b, true : false; }
template<typename X, typename Y> bool ckmax(X& a, Y b) { return a < b ? a = b, true : false; }

int dcmp(ld d1, ld d2) { return fabs(d1 - d2) <= EPS ? 0 : d1 > d2 ? 1 : -1; } //Compare Double Numbers
ll gcd(ll x, ll y) { return !y ? x : gcd(y, x%y); }
ll lcm(ll a, ll b) { return a * (b / gcd(a, b)); }
//convert index from 2D array to 1D array. (Zero-indexed)
int conv_2_1(int r, int c, int nCol) { return (nCol*r) + c + 1; }
//convert index from 1D array to 2D array. (Zero-indexed)
ii conv_1_2(int n, int nCol) {
	int r = n / nCol, c = n % nCol;
	return ii(r, c);
}

ll poww(ll num, ll p, ll md = MOD) {
	num %= md;
	ll ret = 1;
	while (p > 0) {
		if (p & 1) ret = (ret * num) % md;
		num = (num * num) % md;
		p >>= 1;
	}
	return ret;
}

void inter(string s) {
	cout << s << endl;
	fflush(stdout);
}


int main()
{
#ifndef ONLINE_JUDGE

#else
	//freopen("pyramid.in", "r", stdin);
#endif
	//freopen("in.txt", "r", stdin);
	//freopen("out.txt", "w", stdout);
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	ll n,x;
	cin >> n;
	ll sum = 0;
	map<ll,ll> mp;
	lop(i, n) cin >> x, sum += x, mp[x]++;
	int q;
	cin >> q;
	while (q--) {
		int a, b;
		cin >> a >> b;
		sum -= mp[a] *1ll* a;
		sum += mp[a] *1ll* b;
		mp[b] += mp[a];
		mp[a] = 0;
		cout << sum << endl;
	}



	return 0;
}


Measured memory_bytes: 9532
N, M = map(int, input().split())
A = list(map(int, input().split()))
BC = [list(map(int, input().split())) for _ in range(M)]

A.sort(reverse=True)
BC.sort(key=lambda x:x[1],reverse=True)

R=[]
n=0
for i in range(M):
    R.extend([BC[i][1]]*BC[i][0])
    n = n + BC[i][0]
    if n >= N:
        break

R=sorted(A+R, reverse=True)[:N]
print(sum(R))



Measured memory_bytes: 38080
#include <bits/stdc++.h>
#define fi first
#define se second
#define rep(i,n) for(int i=0;i<(n);i++)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define all(v) v.begin(),v.end()
#define len(x) (ll)(x).length()
#define maxs(x,y) x = max(x,y)
#define mins(x,y) x = min(x,y)
#define pb push_back
#define sz(x) (int)(x).size()
#define v(T) vector<T>
#define vv(T) vector<vector<T>>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
ll gcd(ll a,ll b){if(a%b==0){return b;}else{return(gcd(b,a%b));}}
ll lcm(ll a,ll b){return a*b/gcd(a,b);}
const int INF=1e9;
const ll INFS=1e18;
const int MOD=INF+7;
const int di[] = {-1,0,1,0};
const int dj[] = {0,-1,0,1};
const double PI=acos(-1);
 
int main() { //  1 1 1 2 2 2
  ll n,p;
  cin>>n>>p;
  vi a(n);
  int cnt=0;
  ll ans;
  rep(i,n){
    cin>>a[i];
    if(a[i]%2==0) cnt++;
  }
  if(cnt==n){
    if(p==0){
      ans=pow(2,n);
      cout<<ans<<endl;
      return 0;
    }
    if(p==1){
      cout<<0<<endl;
      return 0;
    }
  }
  ans=pow(2,n-1);
  cout<<ans<<endl;
}

Measured memory_bytes: 3904
// D.

#include <iostream>
#include <sstream>
#include <algorithm>
#include <vector>

using namespace std;

int main(int argc, char *argv[])
{
	int n;
	cin >> n;
	vector<int> a(n);
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
	}
	sort(a.begin(), a.end());
	int x = a.back();
	int y = 0;
	for (int i = 0; i < (n - 1); ++i) {
		if (min(a[i], x - a[i]) > min(y, x - y)) {
			y = a[i];
		}
	}
	cout << x << " " << y << endl;
	return 0;
}


Measured memory_bytes: 640
int main(){
	int W,H,x,y,r;
	scanf("%d %d %d %d %d", &W, &H, &x, &y, &r);
	if((x+r)>W || (y+r)>H || (x-r)<0 || (y-r)<0){
printf("No\n");
}
else{
printf("Yes\n");
}
return 0;
}

Measured memory_bytes: 584
#include<iostream>
#include<vector>
#include<algorithm>
#define loop(i,a,b) for(int i=a;i<b;i++)
#define rep(i,a) loop(i,0,a)
using namespace std;
typedef pair<int,int> pii;

int dx[4]={-1,0,1,0};
int dy[4]={0,-1,0,1};

int main(){
	int n;
	while(cin>>n,n){
		vector<pii> vec;
		vec.push_back(pii(0,0));
		int m,d;
		loop(i,1,n){
			cin>>m>>d;
			pii now=vec[m];
			now.first+=dx[d];
			now.second+=dy[d];
			vec.push_back(now);
		}
		int wmi=1e6,wma=-1*1e6,hmi=1e6,hma=-1*1e6;
		rep(i,vec.size()){
			wma=max(wma,vec[i].first);
			wmi=min(wmi,vec[i].first);
			hmi=min(hmi,vec[i].second);
			hma=max(hma,vec[i].second);
		}
		cout<<wma-wmi+1<<" "<<hma-hmi+1<<endl;
	}
	return 0;
}

Measured memory_bytes: 1204
N, M = map(int, input().split())
X = list(map(int, input().split()))
X.sort()
a = X[0]
d = []
for i in X[1:]:
    d.append(i - a)
    a = i
d.sort()
if N < M:
    print(sum(d[:M - N]))
else:
    print(0)

Measured memory_bytes: 57640
#include <iostream>
#include <cstdio>
#include <vector>
#include <list>
#include <cmath>
#include <fstream>
#include <algorithm>
#include <string>
#include <queue>
#include <set>
#include <map>
#include <complex>
#include <iterator>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <stack>
#include <climits>
#include <deque>
#include <bitset>
#include <cassert>
#include <ctime>
using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
//const int dy[]={-1,0,1,0},dx[]={0,1,0,-1};
// adjust problem by problem
const double EPS=1e-8;
const double PI=acos(-1.0);
#ifdef __GNUC__
int popcount(int n){return __builtin_popcount(n);}
int popcount(ll n){return __builtin_popcountll(n);}
#endif
#ifndef __GNUC__
template<class T> int popcount(T n){int cnt=0;while(n){if(n%2)cnt++;n/=2;}return cnt;}
#endif
template<class T>int SIZE(T a){return a.size();}
template<class T>string IntToString(T num){string res;stringstream ss;ss<<num;return ss.str();}
template<class T>T StringToInt(string str){T res=0;for(int i=0;i<SIZE(str);i++)res=(res*10+str[i]-'0');return res;}
template<class T>T gcd(T a,T b){if(b==0)return a;return gcd(b,a%b);}
template<class T>T lcm(T a,T b){return a/gcd(a,b)*b;}
template<class T> void PrintSeq(T &a,int sz){for(int i=0;i<sz;i++){cout<<a[i];if(sz==i+1)cout<<endl;else cout<<' ';}}
bool EQ(double a,double b){return abs(a-b)<EPS;}
void fastStream(){cin.tie(0);std::ios_base::sync_with_stdio(0);}
vector<string> split(string str,char del){
  vector<string> res;
  for(int i=0,s=0;i<SIZE(str);i++){
    if(str[i]==del){if(i-s!=0)res.push_back(str.substr(s,i-s));s=i+1;}
    else if(i==SIZE(str)-1){res.push_back(str.substr(s));}
  }
  return res;
}

int M,N;
vector<int> G[101];
int in[101];
int main(){
  cin>>M>>N;
  for(int i=0;i<N;i++){
    int x,y;
    cin>>x>>y;
    if(y==2)continue;
    x--;y--;
    G[x].push_back(y);
    in[y]++;
  }
  queue<int> q;
  for(int i=0;i<M;i++){
    if(i==1)continue;
    if(in[i]==0)q.push(i);
  }
  vector<int> res;
  //cout<<q.size()<<endl;
  while(q.size()){
    int idx=q.front();q.pop();
    res.push_back(idx);
    for(int i=0;i<(int)G[idx].size();i++){
      in[G[idx][i]]--;
      if(in[G[idx][i]]==0){
        q.push(G[idx][i]);
      }
    }
  }
  res.push_back(1);
  for(int i=0;i<(int)res.size();i++)
    cout<<res[i]+1<<endl;
  
  return 0;
}

Measured memory_bytes: 1224
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define MAX 100000
vector<int> G[MAX];
int id[MAX],pa[MAX],dp[MAX],used[MAX];
void dfs(int v,int d){
  dp[v]=d;
  for(int i=0;i<(int)G[v].size();i++){
    dfs(G[v][i],d+1);
    pa[G[v][i]]=v;
  }
}
signed main(){
  int n;
  cin>>n;
  for(int i=0,k;i<n;i++){
    cin>>id[i]>>k;
    G[id[i]].resize(k);
    for(int j=0;j<k;j++){
      cin>>G[id[i]][j];
      used[G[id[i]][j]]=1;
    }
  }
  memset(pa,-1,sizeof(pa));
  for(int i=0;i<n;i++){
    if(!used[i]) dfs(i,0);
  }
  for(int i=0;i<n;i++){
    cout<<"node "<<i<<": parent = "<<pa[i]<<", depth = "<<dp[i];
    if(pa[i]<0) cout<<", root, [";
    else if(!G[i].size()) cout<<", leaf, [";
    else cout<<", internal node, [";
    for(int j=0;j<(int)G[i].size();j++){
      if(j) cout<<", ";
      cout<<G[i][j];
    }
    cout<<"]"<<endl;
  }
  return 0;
}


Measured memory_bytes: 9488
#define _CRT_SECURE_NO_WARNINGS
#pragma comment(linker, "/stack:512000000")
#include<utility>
#include<iostream>
#include<fstream>
#include<vector>
#include<array>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<ctime>
#include<functional>
#include<random>
#include<climits>
#include<queue>
#include<stack>
#include<deque>
#include<bitset>
#include<map>
#include<set>
#include<unordered_map>
#include<unordered_set>
#include<cassert>
#include<ccomplex>

#ifdef ONLINE_JUDGE
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,tune=native")
#pragma GCC optimize("unroll-loops")
#endif

//4Head

#define all(x) x.begin(), x.end()
#define mp make_pair
#define X first
#define Y second

using namespace std;

using ll = long long;
using ull = unsigned long long;
using ld = long double;
mt19937_64 gen(time(nullptr));

ll const mod = 1e9 + 7;

namespace {
	ll mul(ll a, ll b) {
		ll val = a * b - (ll)((ld)a * b / mod) * mod;
		if (val < 0) val += mod;
		if (val >= mod) val -= mod;
		return val;
	}

	ll poww(ll a, ll b) {
		ll val = 1;
		a %= mod;
		while (b > 0) {
			if (b % 2) val = mul(a, val);
			a = mul(a, a);
			b >>= 1;
		}
		return val % mod;
	}

	ll inv(ll a) {
		return poww(a, mod - 2);
	}
}

int const maxn = 3e5 + 5;

ll m[maxn], fw[maxn];

void upd(ll i, ll x) {
	if (x < m[i]) return;
	m[i] = x;
	for (++i; i < maxn; i += -i & i) {
		fw[i] = max(fw[i], x);
	}
}

ll get(ll r) {
	ll ret = LLONG_MIN;
	for (++r; r > 0; r -= -r & r) {
		ret = max(ret, fw[r]);
	}
	return ret;
}

signed main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	ll n;
	cin >> n;
	vector<ll>h(n), a(n);
	for (ll i = 0; i < n; i++) cin >> h[i];
	for (ll i = 0; i < n; i++) cin >> a[i];

	for (ll i = 0; i < n; i++) {
		ll x = get(h[i] - 1) + a[i];
		upd(h[i], x);
	}

	cout << get(n + 1) << endl;

	return 0;
}

/*
5
2 6 15 5 10

4
2 6 15 5

*/

Measured memory_bytes: 7040
// ---------- begin ModInt ----------
const MOD: u32 = 1_000_000_007;

#[derive(Clone, Copy)]
struct ModInt(u32);

impl std::ops::Add for ModInt {
    type Output = ModInt;
    fn add(self, rhs: ModInt) -> Self::Output {
        let mut d = self.0 + rhs.0;
        if d >= MOD {
            d -= MOD;
        }
        ModInt(d)
    }
}

impl std::ops::AddAssign for ModInt {
    fn add_assign(&mut self, rhs: ModInt) {
        *self = *self + rhs;
    }
}

impl std::ops::Sub for ModInt {
    type Output = ModInt;
    fn sub(self, rhs: ModInt) -> Self::Output {
        let mut d = self.0 + MOD - rhs.0;
        if d >= MOD {
            d -= MOD;
        }
        ModInt(d)
    }
}

impl std::ops::SubAssign for ModInt {
    fn sub_assign(&mut self, rhs: ModInt) {
        *self = *self - rhs;
    }
}

impl std::ops::Mul for ModInt {
    type Output = ModInt;
    fn mul(self, rhs: ModInt) -> Self::Output {
        ModInt((self.0 as u64 * rhs.0 as u64 % MOD as u64) as u32)
    }
}

impl std::ops::MulAssign for ModInt {
    fn mul_assign(&mut self, rhs: ModInt) {
        *self = *self * rhs;
    }
}

impl std::ops::Neg for ModInt {
    type Output = ModInt;
    fn neg(self) -> Self::Output {
        ModInt(if self.0 == 0 {0} else {MOD - self.0})
    }
}

impl std::fmt::Display for ModInt {
    fn fmt<'a>(&self, f: &mut std::fmt::Formatter<'a>) -> std::fmt::Result {
        write!(f, "{}", self.0)
    }
}

impl std::str::FromStr for ModInt {
    type Err = std::num::ParseIntError;
    fn from_str(s: &str) -> Result<Self, Self::Err> {
        let val = s.parse::<u32>()?;
        Ok(ModInt::new(val))
    }
}

impl From<usize> for ModInt {
    fn from(val: usize) -> ModInt {
        ModInt((val % MOD as usize) as u32)
    }
}

#[allow(dead_code)]
impl ModInt {
    pub fn new(n: u32) -> ModInt {
        ModInt(n % MOD)
    }
    pub fn zero() -> ModInt {
        ModInt(0)
    }
    pub fn one() -> ModInt {
        ModInt(1)
    }
    pub fn pow(self, mut n: u32) -> ModInt {
        let mut t = ModInt::one();
        let mut s = self;
        while n > 0 {
            if n & 1 == 1 {
                t *= s;
            }
            s *= s;
            n >>= 1;
        }
        t
    }
    pub fn inv(self) -> ModInt {
        assert!(self.0 > 0);
        self.pow(MOD - 2)
    }
}
// ---------- end ModInt ----------

use proconio::*;

fn run() {
    input! {
        n: u32,
        k: usize,
    }
    let mut memo = vec![ModInt::zero(); k + 1];
    for i in (1..=k).rev() {
        let mut way = ModInt::from(k / i).pow(n);
        let mut j = 2 * i;
        while let Some(&v) = memo.get(j) {
            way -= v;
            j += i;
        }
        memo[i] = way;
    }
    let mut ans = ModInt::zero();
    for (i, c) in memo.into_iter().enumerate() {
        ans += ModInt::from(i) * c;
    }
    println!("{}", ans);
}

fn main() {
    run();
}


Measured memory_bytes: 2284
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <numeric>
#include <sstream>
#include <iostream>
#include <iomanip>
#define _USE_MATH_DEFINES
#include <cmath>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <cfloat>
#include <cmath>
#include <ctime>
#include <cassert>
#include <cctype>
#include <cstdio>
#include <cassert>
using namespace std;

#define EPS 1e-12
#define ull unsigned long long
#define ll long long
#define VI vector<ll>
#define PII pair<ll, ll> 
#define VVI vector<vector<ll> >
#define VVVI vector<vector<vector<ll>>>
#define VVVVI vector<vector<vector<vector<ll>>>>
#define REP(i,n) for(ll i=0,_n=(n);(i)<(ll)_n;++i)
#define REPR(i,n) for(ll i=(ll)(n)-1;0<=(i);--i)
#define RANGE(i,a,b) for(ll i=(ll)a,_b=(ll)(b);(i)<_b;++i)
#define RANGER(i,a,b) for(ll i=(ll)(b)-1,_a=(ll)(a);(_a)<=i;--i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()
#define ALLR(c) (c).rbegin(), (c).rend()
#define PB push_back
#define MP(a, b) make_pair(a, b)
#define POPCOUNT __builtin_popcount
#define POPCOUNTLL __builtin_popcountll
#define CLEAR(table, v) memset(table, v, sizeof(table));
#define UNIFORM_DOUBLE(a, b) (((b-a)*(double)rand()/RAND_MAX)+a) // [a, b) 
#define UNIFORM_LL(a, b) (ll)UNIFORM_DOUBLE(a, b) // [a, b) 
#define IN(v, lo, hi) ((lo)<=(v) && (v)<(hi))
#define DD(v) cout<<#v<<": "<<v<<endl
#define FI first
#define SE second
template <typename T0, typename T1> std::ostream& operator<<(std::ostream& os, const map<T0, T1>& v) { for( typename map<T0, T1>::const_iterator p = v.begin(); p!=v.end(); p++ ){os << p->first << ": " << p->second << " ";} return os; }
template <typename T0, typename T1> std::ostream& operator<<(std::ostream& os, const pair<T0, T1>& v) { os << v.first << ": " << v.second << " "; return os; }
template <typename T> std::ostream& operator<<(std::ostream& os, const vector<T>& v) { for( int i = 0; i < (int)v.size(); i++ ) { os << v[i] << " "; } return os; }
template <typename T> std::ostream& operator<<(std::ostream& os, const set<T>& v) { vector<T> tmp(v.begin(), v.end()); os << tmp; return os; }
template <typename T> std::ostream& operator<<(std::ostream& os, const deque<T>& v) { vector<T> tmp(v.begin(), v.end()); os << tmp; return os; }
template <typename T> std::ostream& operator<<(std::ostream& os, const vector<vector<T> >& v) { for( int i = 0; i < (int)v.size(); i++ ) { os << v[i] << endl; } return os; }
template<typename T>void maxUpdate(T& a, T b) {a = max(a, b);}
template<typename T>void minUpdate(T& a, T b) {a = min(a, b);}

#define MOD 1000000007LL
#define INF (1LL<<60)

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	ll N;
	string s;
	while(cin>>N>>s) {
		bool ans = true;
		if(N%2==0) {
			REP(i, N/2) {
				if(s[i]!=s[i+N/2]) ans=false;
			}
		} else ans=false;
		
		cout<<(ans?"Yes":"No")<<endl;
	}
	
	return 0;
}


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

#define NEW(p,n){p=malloc((n)*sizeof(p[0]));if(p==NULL){printf("not enough memory\n");exit(1);};}
//pの型の変数n個の要素分のメモリを確保し、そのアドレスをpに代入するマクロ

#define MAX(a, b) ((a) > (b) ? (a) : (b))
#define MIN(a, b) ((a) < (b) ? (a) : (b))

void solve(int n) {
	int a = (n % 2 == 0) ? 0 : 1;
	int m = (a - n) / 2;
	if (m != 0) solve(m);
	printf("%d", a);
}

int main(void){
    int N;
    scanf("%d",&N);

    solve(N);
    return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
  
 using namespace std;
 #define rep(i,n) for(int i=0; i<(n); i++)
 typedef long long ll;
 #define INF 1e9
  
  
  
 int main(){
   
     int n, k; cin >> n >> k;
     vector<int> x(n);
     rep(i,n) cin >> x[i];
     int ans = INF;
     rep(i, n-k+1){
         int dist;
         if((x[i] < 0) && (x[i+k-1] > 0)){
             dist = abs(x[i]-x[i+k-1]);
             dist += min(abs(x[i]), x[i+k-1]);
             ans = min(ans ,dist);

         }else{
             dist =max(abs(x[i]), abs(x[i+k-1]));
             ans = min(ans ,dist);
         }
     }
     
     
     cout << ans << endl;
     



    
 }


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

int main(){
    int n;
    cin>>n;
    vector<int>p(n);
    for(int i=0; i<n; i++){
        cin>>p.at(i);
    }
    vector<int>q(n);
    for(int i=0; i<n; i++){
        cin>>q.at(i);
    }
    vector<int>v(n);
    for(int i=0; i<n; i++){
        v.at(i)=i+1;
    }
    int c=0;
    int pc=0;
    int qc=0;
    do{
        c++;
        int che1=0;
        int che2=0;
        for(int i=0; i<n; i++){
            if(v.at(i)==p.at(i)){
                che1++;
            }
        }
        if(che1==n)pc=c;
        for(int i=0; i<n; i++){
            if(v.at(i)==q.at(i)){
                che2++;
            }
        }
        if(che2==n)qc=c;

    }while(next_permutation(v.begin(),v.end()));

    cout<<abs(pc-qc)<<endl;
    /*for(int i=0; i<n; i++){
        cout<<v.at(i)<<endl;
    }
    cout<<c<<endl;
    cout<<pc<<endl;
    cout<<qc<<endl;*/
}

Measured memory_bytes: 256
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <queue>
#include <stack>
#include <vector>

using namespace std;

using Pair = pair<int, int>;
using lint = long long;

const int mod = 1e9 + 7;
// const int mod = 998244353;

template <typename T>
vector<T> make_v(size_t a) {
  return vector<T>(a);
}

template <typename T, typename... Ts>
auto make_v(size_t a, Ts... ts) {
  return vector<decltype(make_v<T>(ts...))>(a, make_v<T>(ts...));
}

int main() {
  int n, k;
  cin >> n >> k;
  vector<int> a(n);
  lint s = 0;
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    s += a[i];
  }
  if(s<=k){
    cout << 1 << endl;
    return 0;
  }
  int l = 1, r = mod;
  while (abs(l - r) > 1) {
    int mid = (l + r) / 2;
    lint cnt = 0;
    for (int i = 0; i < n; i++) {
      cnt += (a[i] + mid - 1) / mid - 1;
    }
    if (cnt <= k)
      r = mid;
    else
      l = mid;
  }
  cout << r << endl;
}


Measured memory_bytes: 4036
# -*- coding: utf-8 -*-
# 

import math
import sys
import itertools
import numpy as np

n =int(input())
t = [int(input()) for i in range(n)] 

a = [0]*(n)
for i in range(n):
    a[t[i]-1]=i
lmax =1
length=1

for i in range(1,n):
    if a[i] < a[i-1]:
        length = 1
    else:
        length += 1
        lmax = max(lmax,length)

print(n - lmax)


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

int main(){
  long N, K;
  cin >> N >> K;
  
  long p[N+1];
  for (long i = 1; i <= N; i++) {
    cin >> p[i];
  }
  
  long sum[1001];
  sum[0] = 0;
  for (long i = 1; i < 1001; i++) {
    sum[i] = sum[i-1]+i;
  }
  
  queue<pair<long, double>> effectiveSum;
  
  double ans = 0;
  double comulativeSum = 0;
  for (long i = 1; i <= N; i++) {

    while (!effectiveSum.empty()) {
      if (i - effectiveSum.front().first + 1 <= K) break;
      comulativeSum -= effectiveSum.front().second;
      effectiveSum.pop();
    }
    double val = (double)sum[p[i]]/(double)p[i];
    comulativeSum += val;
    ans = max(ans, comulativeSum);
    effectiveSum.push({i, val});
  }
  cout<<fixed<<setprecision(9); 
  cout << ans << endl;
  
}


Measured memory_bytes: 5120
import std.stdio,std.conv, std.algorithm, std.container,std.array,std.range,std.string,std.typecons;
const dx = [1,0,-1,0], dy = [0,1,0,-1];
void read(T...)(auto ref T args){ auto line = readln().split(); foreach(i,ref arg; args) arg = line[i].to!(typeof(arg));}
int sum(int n){return n * (n + 1)/ 2;}
void main(){
	int n ;
	while(read(n),n){
		int c;
		foreach(i;2..n){
			if(n < i.sum ) break;
			if((n - i.sum) % i == 0) {c++;}
		}
		c.writeln;
	}
}

Measured memory_bytes: 2456
#include <string>
#include <vector>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <map>
#include <list>
#include <set>
#include <numeric>
#include <queue>
#include <stack>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <cstring>
#include <climits>
#include <cfloat>
#include <ctime>
#include <complex>
#include <cassert>
#include <array>
#include <bitset> 
#include <unordered_map>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> P;


const int L=100*1000+1;
char color[L];
vector<int> edge[L];
bool ok[L];
void solve(long long N, long long M, std::vector<long long> D, std::vector<long long> U, std::vector<long long> V){
	vector<P> order;
	for(int i=0;i<M;i++){
		int u=U[i];
		int v=V[i];
		edge[u].push_back(v);
		edge[v].push_back(u);
		if(D[u]<=D[v]){
			ok[v]=true;
		}
		if(D[u]>=D[v]){
			ok[u]=true;
		}
	}
	for(int i=0;i<N;i++){
		if(!ok[i]){
			cout << -1 << endl;
			return;
		}
		order.push_back(P(D[i],i));
	}
	sort(order.begin(),order.end());
	for(auto p:order){
		int r=p.second;
		bool hasB=false;
		bool hasW=false;
		for(auto s:edge[r]){
			if(color[s]=='B'){
				hasB=true;
			}
			else if(color[s]=='W'){
				hasW=true;
			}
		}
		if(hasB){
			color[r]='W';
		}
		else {
			color[r]='B';
		}
	}
	printf("%s\n",color);
	for(auto i=0;i<M;i++){
		printf("%lld\n",max(D[U[i]],D[V[i]]));
	}
}

int main(){
    long long N;
    scanf("%lld",&N);
    long long M;
    scanf("%lld",&M);
    std::vector<long long> D(N);
    for(int i = 0 ; i < N ; i++){
        scanf("%lld",&D[i]);
    }
    std::vector<long long> U(M);
    std::vector<long long> V(M);
    for(int i = 0 ; i < M ; i++){
        scanf("%lld",&U[i]);
		U[i]--;
        scanf("%lld",&V[i]);
		V[i]--;
    }
    solve(N, M, std::move(D), std::move(U), std::move(V));
    return 0;
}


Measured memory_bytes: 14832
import heapq
n,m = map(int,input().split())
a = list(map(lambda x: (-1)*int(x),input().split()))
heapq.heapify(a)

for i in range(1,m+1):
  t=heapq.heappop(a)
  heapq.heappush(a,-(-t//2))

print(-sum(a))

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

#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define f first
#define s second

using ll = long long;
using ld = long double;
ll INF = LLONG_MAX;

using vi = vector<int>;
using vll = vector<ll>;
using pii = pair<int, int>;

namespace output {
	void pr(int x) { cout << x; }
	void pr(long x) { cout << x; }
	void pr(ll x) { cout << x; }
	void pr(unsigned x) { cout << x; }
	void pr(unsigned long x) { cout << x; }
	void pr(unsigned long long x) { cout << x; }
	void pr(float x) { cout << x; }
	void pr(double x) { cout << x; }
	void pr(ld x) { cout << x; }
	void pr(char x) { cout << x; }
	void pr(const char* x) { cout << x; }
	void pr(const string& x) { cout << x; }
	void pr(bool x) { pr(x ? "true" : "false"); }
	template<class T> void pr(const complex<T>& x) { cout << x; }
	
	template<class T1, class T2> void pr(const pair<T1,T2>& x);
	template<class T> void pr(const T& x);
	
	template<class T, class... Ts> void pr(const T& t, const Ts&... ts) { 
		pr(t); pr(ts...); 
	}
	template<class T1, class T2> void pr(const pair<T1,T2>& x) { 
		pr("{",x.f,", ",x.s,"}"); 
	}
	template<class T> void pr(const T& x) { 
		pr("{"); // const iterator needed for vector<bool>
		bool fst = 1; for (const auto& a: x) pr(!fst?", ":"",a), fst = 0; 
		pr("}");
	}
	
	void print() { pr("\n"); } // print w/ spaces
	template<class T, class... Ts> void print(const T& t, const Ts&... ts) { 
		pr(t); if (sizeof...(ts)) pr(" "); print(ts...); 
	}
}

using namespace output;

int main() {
    // ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int N; cin >> N;
	vector<pii> arr (N);
	F0R(i, N) {
		int x; cin >> x; arr[i] = {x, i + 1};
	}
	arr.push_back({0, 0});
	sort(arr.begin(), arr.end());
	vll ans (N+1);
	ll count = 0;
	int minIndex = N + 1;
	ROF(i, 1, N+1) {
		++count;
		minIndex = min(minIndex, arr[i].second);
		ans[minIndex] += (arr[i].first - arr[i-1].first) * count;
	}
	FOR(i, 1, N+1) print(ans[i]);
}

Measured memory_bytes: 4948
// template version 1.2
using namespace std;
#include <iostream>
#include <bits/stdc++.h>

#define infile "../test/sample-1.in"
#define int long long
// #define INF 2147483647
#define INF 1000000000000000000LL
#define MOD 1000000007LL

// {{{ define basic macro
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define _rrep(i,n) rrepi(i,0,n)
#define rrepi(i,a,b) for(int i=(int)(b-1);i>=(int)(a);--i)
#define rrep(...) _overload3(__VA_ARGS__,rrepi,_rrep,)(__VA_ARGS__)

#define foreach(x,a) for(auto& (x) : (a) )
#define each(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();it++)

#define all(x) (x).begin(),(x).end()
#define sum(v) accumulate(all(v), 0LL)
#define sz(x) ((int)(x).size())
#define pb(a) push_back(a)
#define mp(a, b) make_pair(a, b)
#define uni(x) sort(all(x));x.erase(unique(all(x)),x.end())
#define ten(n) ((int)1e##n)

template<class T> inline void chmax(T &a, const T &b) { if(a < b) a = b; }
template<class T> inline void chmin(T &a, const T &b) { if(a > b) a = b; }

template<typename A, size_t N, typename T> // n次元配列の初期化。第２引数の型のサイズごとに初期化していく。
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}

template <class T = int>
T in() {T x; cin>>x; return (x);}

struct Fast {
  Fast(){
    std::cin.tie(0);
    ios::sync_with_stdio(false);
  }
} fast;
// }}}
//{{{ dump macro
#ifdef PCM
  #include "dump.hpp"
#else
  #define dump(...) 42
  #define dump_1d(...) 42
  #define dump_2d(...) 42
#endif
//}}}
//{{{ others
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef long double ld;
typedef pair<int,int> pii;
typedef tuple<int,int,int> iii;
template<typename T>
using PQ = priority_queue<T, vector<T>, greater<T>>;

int dx[]={1, -1, 0, 0};
int dy[]={0, 0, 1, -1};
//}}}


int solve(){
  int a[3];
  cin>>a[0]>>a[1]>>a[2];
  set<iii> x;
  sort(a,a+3);

  x.insert(iii(a[0], a[1], a[2]));
  int cnt=0;
  while (true){
    if (a[0]%2==1 || a[1]%2==1 || a[2]%2==1){
      cout << cnt << endl;
      return 0;
    }
    int b[3];
    b[0] = (a[1]+a[2])/2;
    b[1] = (a[0]+a[2])/2;
    b[2] = (a[0]+a[1])/2;
    rep(i, 3){
      a[i]=b[i];
    }
    if (x.find(iii(a[0],a[1],a[2]))!=x.end()){
      cout << -1 << endl;
      return 0;
    }
    cnt++;
  }

  return 0;
}

int test(){ //{{{
  return 0;
}
//}}}

signed main() { //{{{
#ifdef INPUT_FROM_FILE
  std::ifstream in(infile);
  std::cin.rdbuf(in.rdbuf());
#endif
#ifdef PCM
  test();
#endif
  solve();
  return 0;
} //}}}


Measured memory_bytes: 256
#include <stdio.h>

int main(void){
	int n,m;
	int l[1000000],r[1000000];
	int max,min;
	int ans=0;

	scanf("%d%d",&n,&m);
	for(int i=0;i<m;i++){
		scanf("%d%d",&l[i],&r[i]);
	}
	max = l[0];
	min = r[0];
	for(int j=0;j<m;j++){
		if(l[j] > max){
			max = l[j];
		}
		if(r[j] < min){
			min = r[j];
		}
	}
	ans  = min-max+1;
	if(ans < 0){
		printf("0\n");
	}else{
		printf("%d\n",ans);

	}
}

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

#define fi first
#define se second
#define forn(i,n) for(int i=0; i< (int)n; ++i)
#define for1(i,n) for(int i=1; i<= (int)n; ++i)
#define fore(i,l,r) for(int i=(int)l; i<= (int)r; ++i)
#define ford(i,n) for(int i=(int)(n) - 1; i>= 0; --i)
#define fored(i,l,r) for(int i=(int)r; i>= (int)l; --i)
#define pb push_back
#define el '\n'
#define d(x) cout<< #x<< " " << x<<el

using namespace std;

typedef long long ll;
typedef pair<int,int> ii;
typedef pair<char,int> pci;
typedef tuple<int, int, int> tiii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;

const ll INF = LONG_LONG_MAX;
const double PI = atan(1)*4;
const int MAXN = 1e5+20;
const double EPS= 1e-10;

int dp[MAXN], n, k;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    cout<< setprecision(2)<< fixed;
    cin>> n>> k;
    int arr[n];
    forn(i,n){
        cin>> arr[i];
        dp[arr[i]]=1;
    }
    forn(i,k+1){
        forn(j,n){
            if(i-arr[j]>=0 && dp[i-arr[j]]==0){
                dp[i]=1;
            }
        }
    }
    cout<< (dp[k] ? "First" : "Second" ) <<el;


}



Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
char s[15];
int main(){
	scanf("%s", s+1);
	int n = strlen(s+1);
	if(s[1] != 'A') return !printf("WA\n");
	bool ok = 0;
	for(int i=3;i<=n-1;i++){
		if(s[i] == 'C'){
			if(ok) return !printf("WA\n");
			ok = 1;
		}
	}
	if(!ok) return !printf("WA\n");
	for(int i=2;i<=n;i++){
		if(s[i] == 'C') continue;
		if('A' <= s[i] && s[i] <= 'Z') return !printf("WA\n");
	}
	printf("AC\n");
}

Measured memory_bytes: 256
H,W,K=map(int,input().split())
L=[list(input()) for _ in range(H)]
x=0
for h in range(H):
    for w in range(W):
        if L[h][w]=='#':
            x+=1
            k=str(x)
            L[h][w]=k
            a=0
            b=W
            for i1 in range(w-1,-1,-1):
                if L[h][i1]=='.':
                    L[h][i1]=k
                else:
                    a=i1+1
                    break
            for i2 in range(w+1,W):
                if L[h][i2]=='.':
                    L[h][i2]=k
                else:
                    b=i2
                    break
            for j1 in range(h-1,-1,-1):
                if set(L[j1][a:b])-set('.')==set() :
                    for l in range(a,b):
                        L[j1][l]=k
                else:
                    break
            for j2 in range(h+1,H):
                if set(L[j2][a:b])-set('.')==set():
                    for l in range(a,b):
                        L[j2][l]=k
                else:
                    break
for line in L:
  print(' '.join(line))

Measured memory_bytes: 9284
#include <iostream>
#include <vector>
#include <algorithm>
#include <list>
#include <iomanip>
#include <string>



using namespace std;

int calc(int a, int b,string op);

int main() {
    int a, b;
    char op;
    int i = 0;
    while(true) {
        cin >> a >> op >> b;
        if (op == '?') {
            break;
        }
        if (op == '+') {
            cout << a + b;
        }
        else if (op == '-') {
            cout << a - b;
        }
        else if (op== '*') {
            cout << a * b;
        }
        else {
            cout << a / b;
        }
        cout << endl;
        
    }
    

}


Measured memory_bytes: 3104
#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <algorithm>

using namespace std;

struct Node{
  int num;
  int dep;
  Node *parent;
  vector<Node*> children;

  Node(int num_, int dep_, Node *parent_){
    num = num_;
    dep = dep_;
    parent = parent_;
  }

};

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

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

    //test
    int nodeno = 0;

    int deph = 0;
    Node *root = new Node(-1, 0, NULL);

    Node *currentNode = root;

    for(int j=1; j<s.size(); j++){
      if(isdigit(s[j])){
        int num = 0;
        while(1){
          num = (10 * num) + (s[j] - '0');
          if(s[j+1] == ']') break;
          j++;
        }
        currentNode->num = (num/2)+1;
      }else{
        if(s[j] == '['){
          deph++;
          Node *nd = new Node(-1, deph, currentNode);
          currentNode->children.push_back(nd);
          currentNode = nd;
        }else{
          deph--;
          int sum = 0;
          if(currentNode->children.size() > 0){
            //copy
            vector<int> v;
            for(int k=0; k<currentNode->children.size(); k++){
              v.push_back(currentNode->children[k]->num);
            }
            sort(v.begin(), v.end());
            for(int k=0; k<(v.size())/2 + 1; k++){
              sum += v[k];
            }
          }else{
            sum = currentNode->num;
          }
          currentNode->num = sum;
          currentNode = currentNode->parent;
        }
      }
    }
    cout<<root->num<<endl;
    //????????§??¨????????????delete?????????
  }

  return 0;
}

Measured memory_bytes: 5292
#include <bits/stdc++.h>
 
using namespace std;
typedef long long ll;
typedef vector<int> VI;
ll mm=1000000000;ll MM=mm+7;
#define rep(i, n) for(int i=0;i<n;i++)
#define PI 3.141592653589793

int main(){
  int n;
  cin >> n;
  vector<char> c(n);
  int sumr=0;
  int sumw=0;
  rep(i,n){
    cin >> c.at(i);
    if(c.at(i)=='R')sumr++;
  }
  rep(i,sumr){
    if(c.at(i)=='W')sumw++;
  }
  cout << sumw << endl;

}

Measured memory_bytes: 3592
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MM = 1000000000;
const int MOD = MM + 7;
const int MAX = 510000;
#define rep(i, n) for(ll i=0; i<n; i++)
#define Rep(i, j, n) for(ll i=j; i<n; i++)
#define all(vec) vec.begin(), vec.end()
template<class T> inline bool chmin(T& a, T b) {if(a > b) {a = b; return true;} return false;}
template<class T> inline bool chmax(T& a, T b) {if(a < b) {a = b; return true;} return false;}
const ll INF = 1LL << 60;

int main() {
    int n; cin >> n;
    set<string> s;
    rep(i, n) {
        string t; cin >> t;
        s.insert(t);
    }
    cout << s.size() << endl;
}


Measured memory_bytes: 19208