akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define rep(i,n) for (int i=0; i<(n); ++i)
using namespace std;
using ll = long long;
using P = pair<int,int>;

const ll mod = 1000000007;
const double eps = 1e-8;

#ifdef DEBUG
#include "inc/debug.hpp"
#else
#define debug(...) 42
#endif

class mint {
public:
    ll x;
    mint(ll x = 0) : x((x % mod + mod) % mod) {}
    ll get() const { return x; }
    mint& operator+=(const mint a) { if ((x += a.x) >= mod) x -= mod; return *this; }
    mint& operator-=(const mint a) { if ((x += mod-a.x) >= mod) x -= mod; return *this; }
    mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this; }
    mint operator+(const mint a) const { return mint(*this) += a; }
    mint operator-(const mint a) const { return mint(*this) -= a; }
    mint operator*(const mint a) const { return mint(*this) *= a; }
    mint pow(ll t) const { if (!t) return 1; mint a = pow(t>>1); return (t & 1) ? a*a*(*this) : a*a; }
    operator ll () const { return x; }
    operator string () const { return to_string(x); }
    friend istream& operator>>(istream& is, mint& a) { is>>a.x; return is; }

    // for prime mod
    mint inv() const { return pow(mod-2); }
    mint& operator/=(const mint a) { return (*this) *= a.inv(); }
    mint operator/(const mint a) const { return mint(*this) /= a; }
};

class Combination {
public:
    vector<mint> fc, fci;
    int n;
    Combination(int n): n(n) {
        fc.resize(n+1, mint(1));
        fci.resize(n+1, mint(1));
        for (int i=2; i<=n; ++i) {
            fc[i] = fc[i-1] * mint(i);
            fci[i] = fci[i-1] / mint(i);
        }
    }
    mint operator()(ll n, ll k) {
        if (k == 0 || n == k) return 1;
        return fc[n] * fci[k] * fci[n-k];
    }
};

Combination C(200000);
vector<int> to[200000];
mint dp[200000], ans[200000];
ll num[200000];

int N;

void dfs1(int u, int prev) {
    mint pp = 1;
    ll sum = 0;
    for (int v: to[u]) {
        if (v == prev) continue;
        dfs1(v, u);
        pp *= dp[v];
        pp *= C.fci[num[v]];
        sum += num[v];
    }
    dp[u] = pp * C.fc[sum];
    num[u] = sum + 1;
}

void dfs2(int u, int prev) {
    if (u == 0) {
        ans[u] = dp[u];
    } else {
        ans[u] = ans[prev] * mint(num[u]) / mint(N - num[u]);
    }
    for (int v: to[u]) {
        if (v == prev) continue;
        dfs2(v, u);
    }
}

int main() {
    cin >> N;
    for (int i=0; i<N-1; ++i) {
        int a, b;
        cin >> a >> b;
        a--; b--;
        to[a].push_back(b);
        to[b].push_back(a);
    }
    dfs1(0, -1);
    dfs2(0, -1);
    for (int i=0; i<N; ++i) {
        cout << ans[i] << endl;
    }
    return 0;
}

Measured memory_bytes: 21748
n, c, k = map(int, input().split())
passenger = sorted([int(input()) for _ in range(n)], reverse = True)
#n, c, k = map(int, "6 3 3".split())

#cは一度に乗れる乗客の数
#kは時間の幅
#passenger = [10, 8, 7, 6, 6, 2]
count = 0
while passenger != []:
    bus = []
    time = passenger[0]
    count += 1
    while len(bus) != c and time - k <= passenger[0]:
        bus.append(passenger.pop(0))
        if passenger == []:
            break

print(count)



Measured memory_bytes: 8280
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cctype>
#include<math.h>
#include<string>
#include<string.h>
#include<stack>
#include<queue>
#include<vector>
#include<utility>
#include<set>
#include<map>
#include<stdlib.h>
#include<iomanip>

using namespace std;

#define ll long long
#define ld long double
#define EPS 0.0000000001
#define INF 1e9
#define LINF (ll)INF*INF
#define MOD 1000000007
#define rep(i,n) for(int i=0;i<(n);i++)
#define loop(i,a,n) for(int i=a;i<(n);i++)
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)

#define int ll //!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

typedef vector<int> vi;
typedef vector<string> vs;
typedef pair<int,int> pii;
typedef vector<pii> vp;

int gcd(int a, int b){
    if(b==0) return a;
    return gcd(b,a%b);
}
int lcm(int a, int b){
    return a*b/gcd(a,b);
}


signed main(void) {
    int i,j;
    int n;
    cin >> n;
    vi a(n),b(n);
    rep(i,n) cin >> a[i];
    rep(i,n) cin >> b[i];
    vi more,less;
    rep(i,n){
        if(a[i] < b[i])less.push_back(b[i]-a[i]);
        if(a[i] > b[i])more.push_back(a[i]-b[i]);
    }
    if(less.empty()){
        cout << 0 << endl;
        return 0;
    }
    if(more.empty()){
        cout << -1 << endl;
        return 0;
    }
    int ans = less.size();
    vi used(more.size(),0);
    sort(all(less));
    sort(all(more));
    rep(i,less.size()){
        while(less[i] > more.back() && more.size()){
            less[i] -= more.back();
            more.pop_back();
            used[more.size()]++;
        }
        if(less[i] > 0 && more.size()){
            used[more.size()-1]++;
            more.back() -= less[i];
        }
        if(more.empty())break;
    }
    if(more.empty()){
        rep(i,less.size())if(less[i]){
            cout << -1 << endl;
            return 0;
        }
    }
    rep(i,used.size())if(used[i])ans++;
    cout << ans << endl;
}


Measured memory_bytes: 3188
#include <bits/stdc++.h>
using namespace std;
#define rep(i, m, n) for (int i = m; i < n; ++i)
#define rem(i, m, n) for (int i = m; i > n; --i)

int main() {
    int N; cin >> N;
    vector<int> a(N+1);
    rep(i, 1, N+1) cin >> a[i];
    vector<int> ans(N+1);
    rem(i, N, 0) {
        ans[i] = a[i];
        for(int j = 2 * i; j <= N; j += i) {
            ans[i] ^= ans[j];
        }
    }
    int cnt = 0;
    rep(i, 1, N+1) if(ans[i]) cnt++;
    cout << cnt << endl;
    rep(i, 1, N+1) if(ans[i]) cout << i << " ";
    if(cnt) cout << endl;
    return 0;
}


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

#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define FOR(x,to) for(x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
//-------------------------------------------------------

template<int um> class UF {
	public:
	vector<int> par,rank,cnt;
	UF() {par=rank=vector<int>(um,0); cnt=vector<int>(um,1); for(int i=0;i<um;i++) par[i]=i;}
	void reinit() {int i; FOR(i,um) rank[i]=0,cnt[i]=1,par[i]=i;}
	int operator[](int x) {return (par[x]==x)?(x):(par[x] = operator[](par[x]));}
	int count(int x) { return cnt[operator[](x)];}
	int operator()(int x,int y) {
		if((x=operator[](x))==(y=operator[](y))) return x;
		cnt[y]=cnt[x]=cnt[x]+cnt[y];
		if(rank[x]>rank[y]) return par[x]=y;
		rank[x]+=rank[x]==rank[y]; return par[y]=x;
	}
};

UF<500000> uf;

int N,M;
ll X[201010];
int A[101010],B[101010];
ll Y[101010];
pair<ll,int> P[101010];
int top[202020];
vector<int> E[201010];
int num[202020];
int ok[202020];

void dfs2(int cur) {
	if(cur<N) return;
	ok[E[cur][0]]=1;
	dfs2(E[cur][1]);
	dfs2(E[cur][2]);
}

void dfs(int cur) {
	if(cur<N) return;
	
	if(Y[E[cur][0]]<=X[cur]) {
		dfs2(cur);
	}
	else {
		ok[E[cur][0]]=-1;
		dfs(E[cur][1]);
		dfs(E[cur][2]);
	}
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,N) {
		cin>>X[i];
		top[i]=i;
	}
	FOR(i,M) {
		cin>>A[i]>>B[i]>>Y[i];
		A[i]--;
		B[i]--;
		P[i]={Y[i],i};
	}
	
	sort(P,P+M);
	int cur=N;
	FOR(i,M) {
		x=P[i].second;
		int a=top[uf[A[x]]];
		int b=top[uf[B[x]]];
		if(a!=b) {
			E[cur]={x,a,b};
			X[cur]=X[a]+X[b];
			uf(A[x],B[x]);
			top[uf[A[x]]]=cur;
			cur++;
		}
	}
	
	dfs(cur-1);
	uf.reinit();
	
	int ret=0;
	FOR(i,M) {
		x=P[i].second;
		int a=uf[A[x]];
		int b=uf[B[x]];
		if(ok[x]==1) {
			X[a]=X[b]=X[a]+X[b];
			uf(a,b);
		}
		else if(ok[x]==-1) {
			ret++;
		}
	}
	FOR(i,M) {
		x=P[i].second;
		int a=uf[A[x]];
		if(ok[x]==0 && Y[x]>X[a]) {
			ret++;
		}
	}
	cout<<ret<<endl;
	
}


int main(int argc,char** argv){
	string s;int i;
	if(argc==1) ios::sync_with_stdio(false), cin.tie(0);
	FOR(i,argc-1) s+=argv[i+1],s+='\n'; FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin);
	cout.tie(0); solve(); return 0;
}


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

int main(){
  int a, b, k;
  cin >> a >> b >> k;
  
  vector<int> ans;
  for (int i=1 ; i<=min(a, b) ; i++){
    if (a%i==0 && b%i==0)
      ans.push_back(i);
  }
  
  sort(ans.begin(), ans.end());
  reverse(ans.begin(), ans.end());
  
  cout << ans.at(k-1) << endl;
}

Measured memory_bytes: 3604
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef string str;
#define down_queue(x) priority_queue<x>
#define up_queue(x) priority_queue<x, vector<x>, greater<x>>
#define vec(x) vector<x>
ll gcd(ll a,ll b){while(b){ll tmp = a % b;a = b;b = tmp;}return a;}
ll lcm(ll a,ll b){return a / gcd(a,b) * b;}
#define rep(x, y) for(int x = 0; x < (y); x++)
#define REP(x, z, y) for(int x = (z); x < (y); x++)
#define all(x) x.begin(), x.end()
#define split_str(str, sp_word) istringstream stream(str); string res; for(int cnt = 0; getline(stream,res,sp_word); cnt++)
#define digit(x) ((int)log10((double)(x)) + 1)
#define mp(x,y) make_pair(x,y)
#define pb(x) push_back(x)
#define pf(x) push_front(x)
#define out(x) for(auto i : x) cout << i << " "; cout << endl;
#define outln(x) for(auto i : x) cout << i << " " << endl;
#define vec_cpy(to,from) copy(all(to),back_inserter(from))
#define ary_cpy(to,from) memcpy(to, from, sizeof from)
#define MOD = 1000000007; 
#ifdef DEBUG
#define debug_echo(e) cout << "L" << __LINE__ << ": " << e << endl
#define debug_var(e) cout << "L" << __LINE__ << ": " << #e << " = " << e << endl
#else
#define debug_echo(e)
#define debug_var(e)
#endif
#ifdef DEBUG
#define debug_echo_dp1(dp, N) { cout << "[ "; rep(i, N) cout << dp[i] << " ";  cout << "]" << endl; }
#else
#define debug_echo_dp1(dp, N)
#endif

#define MAX_N 100000

int N;
int a[MAX_N];
int dp[MAX_N];

int solve() {
  rep(i, N) {
    dp[i] = INT_MAX;
  }
  rep(i, N) {
    *lower_bound(dp, dp+N, a[i]) = a[i];
  }
  return lower_bound(dp, dp+N, INT_MAX) - dp;
}

int main() {
  cin >> N;
  rep(i, N) {
    cin >> a[i];
  }
  cout << solve() << endl;
}

Measured memory_bytes: 3852
# coding: utf-8

def check(A):
    tmp = 0
    first = A[0]
    A.pop(0)
    for i in A:
        if i < first:
            tmp += 1
    return tmp

def main():
    N = int(input())
    P = list(map(int, input().split()))
    Q = list(map(int, input().split()))
    con = [1, 1, 2, 6, 24, 120, 720, 5040, 40320]

    a, b = 0, 0

    for i in range(N, 0, -1):
        a += con[i - 1] * check(P)
        b += con[i - 1] * check(Q)

    print(abs(a - b))

if __name__ == "__main__":
    main()


Measured memory_bytes: 9132
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ
		Scanner scan = new Scanner(System.in);
		int a = scan.nextInt();
		int ans = a+ (int) Math.pow(a, 2)+(int) Math.pow(a, 3);
		System.out.println(ans);
	}

}


Measured memory_bytes: 35864
#define _USE_MATH_DEFINES
#include <cstdio>
#include <iostream>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <complex>
#include <string>
#include <vector>
#include <array>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <limits>
#include <climits>
#include <cfloat>
#include <functional>
#include <iterator>
#include <memory>
#include <regex>
using namespace std;

int main()
{
    int n, k;
    string s;
    cin >> n >> k >> s;

    int ans = 2 * k;
    for(int i=0; i<n-1; ++i){
        if(s[i] == s[i+1])
            ++ ans;
    }
    ans = min(ans, n - 1);
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 512
#pragma GCC optimize("Ofast")
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
using ull = unsigned long long;
#define PI 3.141592
#define all(a) (a).begin(), (a).end()


int main(){
    string s;
    cin >> s;
    string t = s;
    reverse(all(s));
    int n = s.size();
    int count = 0;
    for(int i = 0; i < n; i++){
        if(s[i] != t[i]) count++;
    }
    cout << count / 2 << endl;
}


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

int main(){
	int n;
	cin >> n;
	int a[n];
	for(int i = 0; i < n; i++) cin >> a[i];
	sort(a, a + n);
	int ans = 0;
	for(int i = 1; i < n; i++) ans += a[i] - a[i - 1];
	cout << ans << endl;
}

Measured memory_bytes: 256
def count_cs(str1, str2, MOD):
    """文字列str1, str2の共通部分列(Common Subsequence, CS)を数え上げる。
    添字が異なる場合は異なる部分列として考える。
    計算量 O(|str1||str2|)
    """
    dp = [[0] * (len(str2) + 1) for _ in range(len(str1) + 1)]
    for i in range(len(str1)):
        for j in range(len(str2)):
            if str1[i] == str2[j]:
                dp[i + 1][j + 1] = dp[i + 1][j] + dp[i][j + 1] + 1
            else:
                dp[i + 1][j + 1] = dp[i + 1][j] + dp[i][j + 1] - dp[i][j]
            dp[i + 1][j + 1] %= MOD
    return (dp[len(str1)][len(str2)] + 1) % MOD


n, m = map(int, input().split())
s = list(map(int, input().split()))
t = list(map(int, input().split()))
MOD = 10 ** 9 + 7


print(count_cs(s, t, MOD))

Measured memory_bytes: 94220
#include <iostream>
#include <atcoder/all>

using namespace std;
using namespace atcoder;

int main(){
    int t, u, v, n, q;
    cin >> n >> q;
    dsu g(n);
    for (int i = 0; i < q; i++){
        cin >> t >> u >> v;
        if (t == 0){
            g.merge(u, v);
        }else if (t == 1){
            if(g.same(u,v)){
                cout << 1 << endl;
            }else{
                cout << 0 << endl;
            }
        }
    }
    return 0;
}

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

namespace AtcoderTemplateForCSharp
{
    public class Program
    {
        public static void Main(string[] args)
        {
            var s = Console.ReadLine();
            var w = int.Parse(Console.ReadLine());
            var ans = "";
            for (int i = 0; i < s.Length; i++)
            {
                if (i % w == 0)
                {
                    ans += s.Substring(i, 1);
                }
            }
            Console.WriteLine(ans);
        }
    }
}

Measured memory_bytes: 11092
#include<bits/stdc++.h>
using namespace std;
using lli = long long;
#define rep(i,n) for(int i=0;i<n;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; }

string s;

int main(void){
    cin >> s;
    lli n = s.size();
    string t = "";
    lli j = 0;
    while(j < n){
        if(s[j] == 'A') t+='A', j++;
        if(s[j] == 'B'){
            if(j+1 < n && s[j+1] == 'C') t+='D', j+=2;
            else t+='#', j++;
        }
        if(s[j] == 'C') t+='#', j++;
    }
    //cout << t << endl;
    j = 0;
    lli ac = 0;
    lli ans = 0;
    n = t.size();
    while(j < n){
        if(j < n && t[j] == '#') j++;
        else{
            while(j < n && t[j] != '#'){
                if(j < n && t[j] == 'A'){
                    ac++;
                    j++;
                }else if(j < n && t[j] == 'D'){
                    ans+=ac;
                    j++;
                }
            }
            ac = 0;
        }
    }
    cout << ans << endl;
    return 0;
}


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

using namespace std;

typedef long long LL;

#define fin "\n"


#define FOR(i,bg,ed) for(int i=(bg);i<(ed);i++)
#define REP(i,n) FOR(i,0,n)

template <typename T>
inline void chmin(T &l,T r){l=min(l,r);}

template <typename T>
inline void chmax(T &l,T r){l=max(l,r);}

template <typename T>
istream& operator>>(istream &is,vector<T> &v){
    for(auto &it:v)is>>it;
    return is;
}
typedef vector<LL> V;
typedef vector<V> VV;
#define pb push_back
int N;
VV g(112345),tree(112345),cost(112345);
LL A[112345];
bool res=true;
int make_tree(int v,int p){
    LL rest=A[v];
    if(g[v].size()!=1)rest+=A[v];
    for(auto &u:g[v])
        if(u!=p){
            tree[v].pb(u);
            LL k=make_tree(u,v);
            cost[v].pb(k);
            rest-=k;
            if(A[v]<k)res=false;
        }
    if(rest<0||rest>A[v])res=false;//cout<<v<<" "<<rest<<endl;
    return rest;
}

int main(){    
    cin>>N;
    int root=0;
    REP(i,N)cin>>A[i];
    FOR(i,1,N){
        int a,b;
        cin>>a>>b;
        a--,b--;
        g[a].pb(b);
        g[b].pb(a);
    }
    if(N==2){
        res=(A[0]==A[1]);
    }else{
        while(g[root].size()==1)root++;
        if(make_tree(root,root)!=0)res=false;
    }
    if(res)cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
    return 0;
}


Measured memory_bytes: 26368
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
from math import sqrt
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

S = input()
N = len(S)
ans = N
# 次の文字が違うところだけを見る
for i in range(1, N):
  if S[i] != S[i - 1]:
    now = max(i, N - i)
    ans = min(ans, now)

print(ans)

Measured memory_bytes: 83464
A, B, M = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
ans = 10**6

for i in range(M):
    x, y, c = map(int, input().split())
    ans = min(ans, a[x - 1] + b[y - 1] - c)

ans = min(ans, min(a) + min(b))

print(ans)

Measured memory_bytes: 18736
#include<bits/stdc++.h>
#define N 6000
using namespace std;
int a[N], b[N], f[N], g[N], nd[N], nx[N], x[N], tot, n;

void link(int x, int y) {
    nd[++tot] = y, nx[tot] = g[x], g[x] = tot;
}

void dfs(int u) {
    for(int p = g[u]; p; p = nx[p])
        dfs(nd[p]);
    memset(a, 0, sizeof(a)), a[0] = 1;
    int sum = 0;
    for(int p = g[u]; p; p = nx[p]) {
        memset(b, 0, sizeof(b));
        for(int i = 0; i <= x[u]; i++)
            if (a[i]) {
                if (i + x[nd[p]] <= x[u]) b[i + x[nd[p]]] = 1;
                if (i + f[nd[p]] <= x[u]) b[i + f[nd[p]]] = 1;
            }
        for(int i = 0; i <= x[u]; i++) a[i] = b[i];
        sum += x[nd[p]] + f[nd[p]];
    }
    int m = -1;
    for(int i = x[u]; i >= 0; i--)
        if (a[i]) {m = i;break;}
    if (m == -1 && sum > x[u]) {cout << "IMPOSSIBLE" << endl;exit(0);}
    f[u] = sum - m;
}

int main() {
    cin >> n;
    for(int i = 2; i <= n; i++) {
        int x;scanf("%d", &x);
        link(x, i);
    }
    for(int i = 1; i <= n; i++) scanf("%d", &x[i]);
    dfs(1);
    cout << "POSSIBLE" << endl;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
#define rep(i,n) for(ll i=0, i##_len=(n); i<i##_len; ++i)
#define REP(i,num,n) for(ll i=num, i##_len=(n); i<i##_len; ++i)
#define all(x) (x).begin(),(x).end()
#define sz(x) ((ll)(x).size())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
#define MEMSET(v, h) memset((v), h, sizeof(v))
#define y0 y3487465
#define y1 y8687969
#define j0 j1347829
#define j1 j234892
typedef long long ll;
ll INF = 1e18;
using namespace std;

int main(){
  ll N, M;
  cin >> N >> M;
  
  vector<vector<ll>> vvl(M+1);
  
  rep(i,N){
    ll a, b;
    cin >> a >> b;
    if(a>M)continue;
    vvl[a].push_back(b);
  }
  
  priority_queue<ll> q;

  ll ans = 0;
  rep(i,M){
    for(ll bb: vvl[i+1]){
      q.push(bb);
    }
    if(!q.empty()){
      ans += q.top();
      q.pop();
    }
  }
  
  cout << ans << endl;



  return 0;
}


Measured memory_bytes: 5632
import std.stdio, std.string, std.conv;
import std.range, std.algorithm, std.array, std.typecons, std.container;
import std.math, std.numeric, core.bitop;

enum inf3 = 1_001_001_001;
enum inf6 = 1_001_001_001_001_001_001L;
enum mod = 1_000_000_007L;


void main() {
    int n;
    scan(n);
    auto a = iota(n).map!(i => readln.chomp.to!int).array;

    auto as = a.reduce!"a ^ b"();

    auto b = new int[](32);
    foreach (i ; 0 .. n) {
        b[bsf(a[i])]++;
    }

    debug {
        writeln("as:", as);
        writeln("b:", b);
    }

    int s = 0;
    int ans;

    foreach_reverse (i ; 0 .. 32) {
        int ai = (as >> i) & 1;
        ai ^= s;

        debug {
            writefln("i : %d, ai: %d, s: %d", i, ai, s);
        }

        if (ai) {
            if (b[i]) {
                ans++;
                s ^= 1;
            }
            else {
                writeln(-1);
                return;
            }
        }
    }

    writeln(ans);
}









void scan(T...)(ref T args) {
    import std.stdio : readln;
    import std.algorithm : splitter;
    import std.conv : to;
    import std.range.primitives;

    auto line = readln().splitter();
    foreach (ref arg; args) {
        arg = line.front.to!(typeof(arg));
        line.popFront();
    }
    assert(line.empty);
}

void fillAll(R, T)(ref R arr, T value) {
    static if (is(typeof(arr[] = value))) {
        arr[] = value;
    }
    else {
        foreach (ref e; arr) {
            fillAll(e, value);
        }
    }
}


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

class Mondai
{
    static void Main()
    {
        var N = Int32.Parse(Console.ReadLine());
        var a = Console.ReadLine().Split(' ').Select(x => Int32.Parse(x)).ToArray();
        var array = new int[9];
        var rate = new int[] { 400, 800, 1200, 1600, 2000, 2400, 2800, 3200, 4801 };
        for (int i = 0; i < 9; ++i) array[i] = 0;
        for (int i = 0; i < N; ++i)
        {
            for (int j = 0; j < rate.Length; ++j)
            {
                if (j == rate.Length-1) {
                    array[j]++;
                }
                else if (a[i] < rate[j])
                {
                    if (array[j] == 0) { array[j]++; }
                    break;
                }
            }
        }
        var type = array.Take(rate.Length - 1).Sum();
        var min = type == 0 ? 1 : type;
        var max = type + array[rate.Length - 1];
        Console.WriteLine($"{min} {max}");
    }
}

Measured memory_bytes: 13396
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);

		long n = sc.nextLong();
		long a = sc.nextLong();
		long b = sc.nextLong();

		if(a > b || (n == 1 && a != b)){
			System.out.println(0);
			return;
		}
		long minSum = a*(n - 1) + b;
		long maxSum = a + b*(n - 1);

		System.out.println(maxSum - minSum + 1);
	}
}


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


long long ManyFormula(long long S, long long head, long long cnt){

    long long sum = 0;

    if(cnt == 1){
        return 0;
    }
    else{
        for(long long i=1; i < cnt; i++){
            long long cnt_next=0;
            long long S_next = S % (long long)pow(10, cnt - i);
            long long head_next = head + S / (long long)pow(10, cnt - i);

            for(long long j=0; j < S_next; j++){
                if(S_next / (long long)pow(10, j) == 0){
                break;
                }
                cnt_next++; 
            }

//            cout << S << " " << S_next << " " << head_next << " " << cnt_next << " " << sum << endl;

            if(cnt_next == 1){
                sum += S_next + head_next;
            }
            else{
                sum += S_next + head_next + ManyFormula(S_next, head_next, cnt_next); 
            }

        }
    }

    return sum;

}


int main() {
    long long S = 0;
    cin >> S;

    long long cnt = 0;
    for(long long i=0; i < S; i++){
        if(S / (long long)pow(10, i) == 0){
            break;
        }
        cnt++; // 125 : 3
    }

    long long sum = S;
    long long head=0;
    sum += ManyFormula(S, head, cnt);
 
    cout <<  sum << endl;

}


Measured memory_bytes: 384
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<iostream>
#include<map>
#include<numeric>
#include<queue>
#include<set>
#include<sstream>
#include<unordered_map>
#include<unordered_set>
#include<vector>
using uint = unsigned int;
using ll = long long;
enum : int { M = (int)1e9 + 7 };
enum : ll { MLL = (ll)1e18L + 9 };
using namespace std;
#ifdef LOCAL
#include"rprint2.hpp"
#include"debug_deque.hpp"
#define vector DebugDeque
#else
#define FUNC(name) template <ostream& out = cout, class... T> void name(T&&...){ }
FUNC(prints) FUNC(printe) FUNC(printw) FUNC(printew) FUNC(printb) FUNC(printd) FUNC(printde);
#endif

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int m; cin >> m;
    cout << 24 + (24 - m) << '\n';
}


Measured memory_bytes: 256
#include <map>
#include <set>
#include <cmath>
#include <ctime> 
#include <queue>
#include <stack>
#include <bitset> 
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <cstring>
#include <iostream>
#include <algorithm>

#define fi first
#define se second
#define pb push_back
#define MP std::make_pair
#define PII std::pair<int, int>
#define all(x) (x).begin(), (x).end()
#define CL(a, b) memset(a, b, sizeof a)
#define rep(i, l, r) for (int i = (l); i <= (r); ++ i)
#define per(i, r, l) for (int i = (r); i >= (l); -- i)
#define PE(x, a) for (int x = head[a]; x;x = edge[x].next)

typedef long long ll;

const int MAXN = 82;
const int H = 80 * 80;

int n, m, a[MAXN][MAXN], b[MAXN][MAXN], ans = INT_MAX;
bool f[MAXN][MAXN][MAXN * MAXN * 2];

inline bool chk(int x) {
    return x >= 0 && x <= 2 * H;
}

int main() {
    scanf("%d %d", &n, &m);
    rep(i, 1, n) rep(j, 1, m) scanf("%d", &a[i][j]);
    rep(i, 1, n) rep(j, 1, m) scanf("%d", &b[i][j]);
    f[1][1][H + a[1][1] - b[1][1]] = 1;
    f[1][1][H - a[1][1] + b[1][1]] = 1;
    rep(i, 1, n) rep(j, 1, m) rep(k, 0, 2 * H){
        if (!f[i][j][k]) continue;
        int t1 = a[i + 1][j] - b[i + 1][j];
        int t2 = a[i][j + 1] - b[i][j + 1];
        if (chk(k + t1)) f[i + 1][j][k + t1] = 1;
        if (chk(k - t1)) f[i + 1][j][k - t1] = 1;
        if (chk(k + t2)) f[i][j + 1][k + t2] = 1;
        if (chk(k - t2)) f[i][j + 1][k - t2] = 1;
    }
    rep(i, 0, 2 * H) if (f[n][m][i]) ans = std::min(ans, abs(H - i));
    printf("%d\n", ans);
    return 0;
}

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

using namespace std;

int main(){
    int n,m;
    cin >> n >> m;
    char c;
    int row = 0, col = 0;
    int all = 1, cnt = 0;
    for (int i = 0; i < n; ++i){
        for (int j = 0; j < m; ++j){
            cin >> c;
            if (i==0 && j==0 && c=='.'){
                cout << "Impossible";
                return 0;
            }
            if (c == '.') 
                continue;
            cnt++;
            if (row == i && col == (j-1)){
                col++;
                all++;
                continue;
            }
            if (row == (i-1) && col == j){
                row++;
                all++;
            }
        }
    }
    if (row == (n-1) && col == (m-1) && all == cnt){
        cout << "Possible";
    }
    else {
        cout << "Impossible";
    }

    return 0; 
}


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

int main() {
  
  int N,a;
  cin >> N;
  vector<int> vec(N);
  
  for (int i=0; i<N; i++) cin >> vec.at(i);
  
  int s=1;
  for (int i=0; i<N-1; i++) {
    s=vec.at(s-1);
    if (s==2) {
      cout << i+1;
      break;
    }
  }
  
  if (s!=2) cout << -1 << endl;
}

Measured memory_bytes: 640
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <complex>
#include <string>
#include <sstream>
#include <algorithm>
#include <numeric>
#include <vector>
#include <queue>
#include <stack>
#include <functional>
#include <iostream>
#include <map>
#include <set>
using namespace std;
typedef pair<int,int> P;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-9
#define INF 2000000000
#define sz(x) ((int)(x).size())
#define fi first
#define sec second
#define SORT(x) sort((x).begin(),(x).end())
#define all(x) (x).begin(),(x).end()
#define rep(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define repn(i,a,n) for(int (i)=(a);(i)<(int)(n);(i)++)
#define EQ(a,b) (abs((a)-(b))<eps)
int N,M;
string a[5010];
int x[5010];
map<string,int> m;
struct UnionFind
{
	int par[5010];
	void init(){rep(i,5010)par[i]=i;}
	int find(int x)
	{
		if(x==par[x])return x;
		return par[x]=find(par[x]);
	}
	void unite(int a,int b)
	{
		a = find(a);
		b = find(b);
		if(x[a]<x[b])par[b]=a;
		else par[a]=b;
	}
}uf;
int main()
{
	scanf("%d",&N);
	rep(i,N)
	{
		cin >> a[i] >> x[i];
		m[a[i]]=i;
	}
	uf.init();
	scanf("%d",&M);
	rep(i,M)
	{
		string a,b;
		cin >> a >> b;
		uf.unite(m[a],m[b]);
	}
	int ans = 0;
	rep(i,N)ans += x[uf.find(i)];
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 1912
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<cmath>
#include <numeric>

using namespace std;
typedef long long ll;

bool is_prime(ll n){
    if (n == 1) return false;
    for (ll i = 2; i * i <= n; i++){
        if (n % i == 0 ) return false;
    }
    return true;
}

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

    if (b / a > c) cout << c << endl;
    else cout << int(b / a) << endl;
    return 0;
}

Measured memory_bytes: 256
import java.util.*;
public class Main{
	public static void main(String[] args){
    	Scanner sc = new Scanner(System.in);
      int h = sc.nextInt();
      int w = sc.nextInt();
      char[][] a = new char[h+1][];
      for(int i = 0;i < h;i++){
        	a[i] = sc.next().toCharArray();
      }
  	  for(int i = 0;i < w+2;i++){System.out.print('#');}
      System.out.println("");
      for(int i = 0;i < h;i++){
        System.out.print('#');
      	for(int j = 0;j < w;j++){
        	System.out.print(a[i][j]);
        }
        System.out.print('#');
        System.out.println("");
      }
      
      for(int i = 0;i < w+2;i++){System.out.print('#');}
    }
}


Measured memory_bytes: 26452
# include "bits/stdc++.h"
using namespace std;
using LL = long long;
using ULL = unsigned long long;
const double PI = acos(-1);
template<class T>constexpr T INF() { return ::std::numeric_limits<T>::max(); }
template<class T>constexpr T HINF() { return INF<T>() / 2; }
template <typename T_char>T_char TL(T_char cX) { return tolower(cX); };
template <typename T_char>T_char TU(T_char cX) { return toupper(cX); };
const int vy[] = { -1, -1, -1, 0, 1, 1, 1, 0 }, vx[] = { -1, 0, 1, 1, 1, 0, -1, -1 };
const int dx[4] = { 0,1,0,-1 }, dy[4] = { 1,0,-1,0 };
int popcnt(unsigned long long n) { int cnt = 0; for (int i = 0; i < 64; i++)if ((n >> i) & 1)cnt++; return cnt; }
int d_sum(LL n) { int ret = 0; while (n > 0) { ret += n % 10; n /= 10; }return ret; }
int d_cnt(LL n) { int ret = 0; while (n > 0) { ret++; n /= 10; }return ret; }
LL gcd(LL a, LL b) { if (b == 0)return a; return gcd(b, a%b); };
LL lcm(LL a, LL b) { LL g = gcd(a, b); return a / g*b; };
# define ALL(qpqpq)           (qpqpq).begin(),(qpqpq).end()
# define UNIQUE(wpwpw)        sort(ALL((wpwpw)));(wpwpw).erase(unique(ALL((wpwpw))),(wpwpw).end())
# define LOWER(epepe)         transform(ALL((epepe)),(epepe).begin(),TL<char>)
# define UPPER(rprpr)         transform(ALL((rprpr)),(rprpr).begin(),TU<char>)
# define FOR(i,tptpt,ypypy)   for(LL i=(tptpt);i<(ypypy);i++)
# define REP(i,upupu)         FOR(i,0,upupu)

struct INIT{
    INIT(){
        std::ios::sync_with_stdio(false);
        std::cin.tie(0);
        cout << fixed << setprecision(13);
    }
}INIT;

int n;
string s, t;

int main(){
    cin >> n >> s >> t;
    REP(i, n){
        cout << s[i] << t[i];
    }
    cout << endl;
}

Measured memory_bytes: 256
#include<deque>
#include<queue>
#include<vector>
#include<algorithm>
#include<iostream>
#include<set>
#include<cmath>
#include<tuple>
#include<string>
#include<chrono>
#include<functional>
#include<iterator>
#include<random>
#include<unordered_set>
#include<array>
#include<map>
#include<iomanip>
#include<assert.h>
#include<bitset>
#include<stack>
#include<memory>
using namespace std;
typedef long long int llint;
typedef long double lldo;
#define mp make_pair
#define mt make_tuple
#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pop_front
#define fir first
#define sec second
#define res resize
#define ins insert
#define era erase
/*
cout<<fixed<<setprecision(20);
cin.tie(0);
ios::sync_with_stdio(false);
*/
const llint mod=1000000007;
const llint big=2.19e15+1;
const long double pai=3.141592653589793238462643383279502884197;
const long double eps=1e-15;
template <class T,class U>bool mineq(T& a,U b){if(a>b){a=b;return true;}return false;}
template <class T,class U>bool maxeq(T& a,U b){if(a<b){a=b;return true;}return false;}
llint gcd(llint a,llint b){if(a%b==0){return b;}else return gcd(b,a%b);}
llint lcm(llint a,llint b){if(a==0){return b;}return a/gcd(a,b)*b;}
template<class T> void SO(T& ve){sort(ve.begin(),ve.end());}
template<class T> void REV(T& ve){reverse(ve.begin(),ve.end());}
template<class T>llint LBI(vector<T>&ar,T in){return lower_bound(ar.begin(),ar.end(),in)-ar.begin();}
template<class T>llint UBI(vector<T>&ar,T in){return upper_bound(ar.begin(),ar.end(),in)-ar.begin();}
int main(void){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n,i,ans=0,dco=1;cin>>n;
	for(i=1;i<=n;i++){
		int m;cin>>m;
		int aru=0,dme=0;
		while(m--){
			int x;cin>>x;
			if(dme){continue;}
			if(x==i+1){aru=1;continue;}
			if(dco<=x){ans++;aru=0;dme=1;continue;}
		}
		if(aru==0){dco=i+1;}
	}
	cout<<ans<<endl;
	return 0;
}


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

#define int long long

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

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

      vector<int> c;
      vector<int> ind;
      for (int i = 0; i < n; i++) {
            int tmp = 0;
            for (int j = i; j < n; j++) {
                  tmp += a[j];
                  ind.push_back(c.size());
                  c.push_back(tmp);
            }
      }

      int ans = 0;
      for (int b = 60; b >= 0; b--) {
            vector<int> bucket;
            for (int i: ind) {
                  if (c[i] & (1LL << b)) bucket.push_back(i);
            }
            if (bucket.size() >= k) {
                  ans |= (1LL << b);
                  swap(ind, bucket);
            }
      }
      cout << ans;

      return 0;
}



Measured memory_bytes: 10464
#include <bits/stdc++.h>
#define N 100
using namespace std;
typedef complex<double> P;
typedef pair<P,P> L;
const double EPS = 1e-8;
double dot(P a, P b){ return real(conj(a)*b); }
double cross(P a, P b){ return imag(conj(a)*b); }

int ccw(P a, P b, P c){
  b -= a;
  c -= a;
  if(cross(b,c) > EPS) return 1;   // ????????????(b-a)????????´???????????????(c-a)????????¨?????????
  if(cross(b,c) < -EPS) return -1; // ????????????(b-a)????????´???????????????(c-a)????????¨?????????
  if(dot(b,c) < -EPS) return 2;
  if(norm(b) < norm(c)) return -2;
  return 0;
}

bool isIntersect(L s1, L s2){
  //ccw ??????????????????????????¨, ????????????????????´?????????????????¨??????????????????????????????
  if(max(real(s1.first), real(s1.second)) + EPS < min(real(s2.first), real(s2.second)) ||
     max(imag(s1.first), imag(s1.second)) + EPS < min(imag(s2.first), imag(s2.second)) ||
     max(real(s2.first), real(s2.second)) + EPS < min(real(s1.first), real(s1.second)) ||
     max(imag(s2.first), imag(s2.second)) + EPS < min(imag(s1.first), imag(s1.second))) return false;

  return ( ccw(s1.first,s1.second,s2.first) * ccw(s1.first,s1.second,s2.second) <= 0 &&
           ccw(s2.first,s2.second,s1.first) * ccw(s2.first,s2.second,s1.second) <= 0 );
}

bool isIntersect(vector<P> a,vector<P> b){
  for(int i=0;i<5;i++)
    for(int j=0;j<5;j++)
      if(isIntersect(L(a[i],a[(i+2)%5]),L(b[j],b[(j+2)%5])))return 1;
  return 0;
}

vector<P> get_p(P a,double d,double r){
  vector<P> res(5);
  d=(d/360)*2*M_PI;
  P p=P(0,r)*P(cos(d),sin(d));
  res[0]=p+a;
  d=2*M_PI/5;
  for(int i=1;i<=4;i++){
    p=p*P(cos(d),sin(d));
    res[i]=p+a;
  }
  return res;
}
double getDistanceSP(L s, P p){
  if(dot(s.second - s.first, p - s.first) < -EPS) return abs(p - s.first);
  if(dot(s.first - s.second, p - s.second) < -EPS) return abs(p - s.second);
  return abs(cross(s.second - s.first, p - s.first) / abs(s.second - s.first));  }

double getDistanceSS(L s1, L s2){
  if(isIntersect(s1,s2)) return 0.0;
  return min( min(getDistanceSP(s1, s2.first), getDistanceSP(s1, s2.second)),
              min(getDistanceSP(s2, s1.first), getDistanceSP(s2, s1.second)));
}

double G[N][N],x[N],y[N],d[N],r[N];

double get_dis(int a,int b){
  vector<P> A=get_p(P(x[a],y[a]),d[a],r[a]);
  vector<P> B=get_p(P(x[b],y[b]),d[b],r[b]);
  double res=1e9;
  for(int i=0;i<5;i++)
    for(int j=0;j<5;j++)
      res=min(res,getDistanceSS(L(A[i],A[(i+2)%5]),L(B[j],B[(j+2)%5])));
  return res;
}

int main(){
  while(1){
  int n,s,g;
  cin>>n>>s>>g;
  if(!n&&!s&&!g)break;
  for(int i=0;i<n;i++)for(int j=0;j<n;j++)G[i][j]=1e9*(i!=j);
  for(int i=0;i<n;i++)cin>>x[i]>>y[i]>>d[i]>>r[i];
  
  for(int i=0;i<n;i++)
    for(int j=0;j<n;j++)if(i!=j) G[i][j]=get_dis(i,j);
  
  for(int k=0;k<n;k++)
    for(int i=0;i<n;i++)
      for(int j=0;j<n;j++)
	G[i][j]=min(G[i][j],G[i][k]+G[k][j]);

  printf("%.20f\n",G[s-1][g-1]);
  }
  return 0;
}

Measured memory_bytes: 3536
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <string>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <bitset>

using namespace std;

#define PB push_back
#define MP make_pair
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define repp(i,a,b) for(int i=a;i>=b;i--)
#define Set(x,a) memset(x,a,sizeof(x));

#define vs vector<string>
#define vi vector<int>
#define ll long long
#define ff first
#define ss second

struct comp {
       bool operator() (int a,int b) {
            return a>b;
       }
};

int main()
{
//    freopen("input.txt","r",stdin);
//    freopen("output.txt","w",stdout);
//    std::ios::sync_with_stdio(false);
    int n, a[100005], b[100005], c[100005];;
    ll ans = 0, tmp_b[100005] = {};
    scanf("%d", &n);
    rep(i,1,n) scanf("%d", &a[i]);
    rep(i,1,n) scanf("%d", &b[i]);
    rep(i,1,n) scanf("%d", &c[i]);
    sort(a+1, a+n+1, comp());
    sort(b+1, b+n+1, comp());
    sort(c+1, c+n+1, comp());
    int indexC = 0;
    rep(i,1,n) {
        while (indexC + 1 <= n && c[indexC + 1] > b[i]) indexC++;
        tmp_b[i] = tmp_b[i - 1] + indexC;
    }
    int indexB = 0;
    rep(i,1,n) {
        while (indexB + 1 <= n && b[indexB + 1] > a[i]) indexB++;
        ans += tmp_b[indexB];
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 2176
private fun readLn() = readLine()!!
private fun readInt() = readLn().toInt()
private fun readLong() = readLn().toLong()
private fun readStrings() = readLn().split(" ")
private fun readInts() = readStrings().map(String::toInt)
private fun readLongs() = readStrings().map(String::toLong)

fun main() {
    val (l, r, d) = readInts()
    println(r / d - (l - 1) / d)
}

Measured memory_bytes: 36152
n,k = map(int,input().split())
A = list(map(int,input().split()))
a = A.index(1)
b = -(-a//(k-1))*(k-1)
if n == k:
    print(1)
else:
    print(-(-a//(k-1))-(-(n-b-1)//(k-1)))

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

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

    int a, b;
    cin >> a >> b;
    if(b % a == 0){
        cout << a + b << endl;
    }else{
        cout << b - a << endl;
    }

    return 0;
}

Measured memory_bytes: 256
#pragma GCC optimize("Ofast")
#define _USE_MATH_DEFINES
#include "bits/stdc++.h"

using namespace std;

using u8 = uint8_t;
using u16 = uint16_t;
using u32 = uint32_t;
using u64 = uint64_t;
using i8 = int8_t;
using i32 = int32_t;
using i64 = int64_t;
constexpr char newl = '\n';

template<typename T1, typename T2> inline void chmin(T1& a, T2 b) { if (a > b) a = b; }
template<typename T1, typename T2> inline void chmax(T1& a, T2 b) { if (a < b) a = b; }
#define FOR(i,a,b) for (int i = (a); i < (b); i++)
#define F0R(i,b) FOR(i,0,b)
#define RFO(i,a,b) for (int i = ((b)-1); i >=(a); i--)
#define RF0(i,b) RFO(i,0,b)
//#define F first
//#define S second
#define debug(x) cout << #x << ": " << x << '\n';
template<class T> void Print(vector<T> v) {
  F0R(i, v.size()) {
    cout << v[i] << ' ';
  }
  cout << newl;
}

#if 1


// INSERT ABOVE HERE
signed main() {
  cin.tie(0);
  ios_base::sync_with_stdio(false);

  int N;
  cin >> N;

  // "(" を +1, ")" を -1 として扱う

  struct Unit {
    int m, p;
  };

  vector<Unit> us(N);
  F0R(i, N) {
    string s;
    cin >> s;

    int low = 0, sum = 0;
    for (auto c : s) {
      int n = c == ')' ? -1 : 1;
      sum += n;
      chmin(low, sum);
    }
    us[i] = { -low, sum };
  }

  sort(us.begin(), us.end(), [](const Unit& l, const Unit& r)->bool {
    
    // マイナスがないなら、それらを最優先で使う
    if (l.m == 0 || r.m == 0) {
      return l.m != r.m ? l.m < r.m : l.p > r.p;
    }

    // マイナスがある場合、合計でプラスになるものから優先して使う

    // どちらもプラスなら、マイナスが少ない方から
    if (l.p >= 0 && r.p >= 0) {
      return l.m < r.m;
    }

    // 片方だけプラスなら、そちらから使う
    if (l.p >= 0 || r.p >= 0) {
      return l.p > r.p;
    }

    // どちらもマイナスなら、マイナスと合計に差がある、つまり )))((のような形から使う
    return l.p + l.m > r.p + r.m;

    });

  i64 cur = 0;
  bool result = true;

  auto check = [&cur, &result](const Unit& u)->bool {

    //cout << " -" << u.m << " +" << u.p << newl;

    cur -= u.m;
    if (cur < 0) {
      result = false;
      return false;
    }
    cur += u.m + u.p;
    return true;
  };

  auto calc = [&check](const vector<Unit>& us) {

    for (auto u : us) {
      if (!check(u)) return;
    }
  };

  calc(us);
  if (cur != 0) result = false;

  cout << (result ? "Yes" : "No");
}
#endif


Measured memory_bytes: 10996
def insertsort(A,n,g):
    global cnt
    for i in range(g,n):
        v=A[i]
        j=i-g
        while j>=0 and A[j]>v:
            A[j+g],A[j]=A[j],A[j+g]
            j=j-g
            cnt +=1

n=int(input())
A=[int(input()) for i in range(n)]
cnt=0

G=[1]
def G_choice(n):
    for i in range(1,n):
        point=3*G[i-1]+1
        if point>=n:break
        else:G.append(point)
G_choice(n)
m=len(G)
G.reverse()

for i in range(m):
    insertsort(A,n,G[i])

print(m)
print(*G)
print(cnt)
print(*A,sep="\n")


Measured memory_bytes: 53308
package main

import (
	"bufio"
	"fmt"
	"os"
	"sort"
	"strconv"
)

func out(x ...interface{}) {
	fmt.Println(x...)
}

var sc = bufio.NewScanner(os.Stdin)

func getInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

func getString() string {
	sc.Scan()
	return sc.Text()
}

// min, max, asub, absなど基本関数
func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func asub(a, b int) int {
	if a > b {
		return a - b
	}
	return b - a
}

func abs(a int) int {
	if a >= 0 {
		return a
	}
	return -a
}

func lowerBound(a []int, x int) int {
	idx := sort.Search(len(a), func(i int) bool {
		return a[i] >= x
	})
	return idx
}

func upperBound(a []int, x int) int {
	idx := sort.Search(len(a), func(i int) bool {
		return a[i] > x
	})
	return idx
}

func main() {
	sc.Split(bufio.ScanWords)
	N := getInt()
	a := make([]int, N)
	b := make([]int, N)
	c := make([]int, N-1)
	for i := 0; i < N; i++ {
		a[i] = getInt() - 1
	}
	for i := 0; i < N; i++ {
		b[i] = getInt()
	}
	for i := 0; i < N-1; i++ {
		c[i] = getInt()
	}

	prev := -1
	ans := 0
	for i := 0; i < N; i++ {
		x := a[i]
		ans += b[x]
		if x == prev+1 && x != 0 {
			ans += c[x-1]
		}
		prev = x
	}
	out(ans)
}


Measured memory_bytes: 640
#include <iostream>
#include <cmath>
#include <limits>
using namespace std;
typedef long long ll;

int main() {
	ll total, min = numeric_limits<int>::max(); ll check = 0;
	ll n; cin >> n;
	for (ll i = 0; i < n; i++){
		ll num; cin >> num;
		if (abs(num) < abs(min)) min = abs(num);
		if (num < 0) check++;
		total += abs(num);
	}
	if (check & 1) {
		total -= 2*min;
	}
	cout << total;
	return 0;
}

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

int main() {
  int N, K;
  cin >> N >> K;
  
  vector<int> a(N);
  for (int i=0; i<N; i++) {
    cin >> a.at(i);
  }
  
  int x, y;
  for (int i=0; i<(N-K); i++) {
    if (a.at(i) < a.at(i+K)) {
      cout << "Yes" << endl;
    }
    else {
      cout << "No" << endl;
    }
  }
}

Measured memory_bytes: 4048
import heapq
n = int(input())
a = list(map(int,input().split()))

big_a = []
for i in range(n):
    heapq.heappush(big_a,a[i])

small_a = []
for i in range(n):
    heapq.heappush(small_a,-a[3*n-1-i])

now_big = sum(big_a)
now_small = -sum(small_a)
big_data = [now_big]
small_data = [now_small]

for k in range(n):
    now_big += a[k+n]
    heapq.heappush(big_a,a[k+n])
    now_big -= heapq.heappop(big_a)
    big_data.append(now_big)

    now_small += a[2*n-1-k]
    heapq.heappush(small_a,-a[2*n-1-k])
    now_small += heapq.heappop(small_a)
    small_data.append(now_small)
    
#print(big_data)
#print(small_data)

ans = -10**18
for k in range(n+1):
    ans = max(ans,big_data[k]-small_data[n-k])

print(ans)

Measured memory_bytes: 124560
MOD = 10**9 + 7


def comb(n, k, MOD):
    if n < k or n < 0 or k < 0:
        return 0
    if k > n - k:
        k = n - k
    ans = 1
    for i in range(1, k + 1):
        ans *= n + 1 - i
        ans %= MOD
        ans *= pow(i, MOD - 2, MOD)  # a //= i
        ans %= MOD
    return ans


x, y = map(int, input().split())
a = 2 * y - x
b = 2 * x - y

if a < 0 or b < 0:
    ans = 0
elif a % 3 != 0 or b % 3 != 0:
    ans = 0
else:
    a //= 3
    b //= 3
    # print(a, b)
    ans = comb(a + b, a, MOD)

print(ans)


Measured memory_bytes: 3064
import java.util.Scanner;

public class Main {

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

	    String s =scanner.next();
	    String t =scanner.next();
	    int c=0;
	    for (int i=0; i<s.length(); i++) {
	    	if (s.charAt(i) != t.charAt(i)) {
	    		c++;
	    	}
	    }



	    System.out.println(c);
	}

	public static int uclid(int m, int n) {
		if (m<n) {
			m ^= n;
			n^=m;
			m^=n;
		}

		while (true) {
			int t=m%n;
			if (t==0) {
				return n;
			} else {
				m=n;
				n=t;
			}
		}
	}

}

Measured memory_bytes: 41208
#include <utility>
#include <bitset>
#include <string>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <numeric>
#include <iostream>
#include <ios>
#include <iomanip>
#include <sstream>
#include <climits>
#include <cmath>

using namespace std;

#define FOR(v, b, e)   for (int v = (b); v < (e); ++v)
#define REP(v, n)      FOR(v, 0, n)

#define ALL(c)         (c).begin(), (c).end()

typedef long long           ll;
typedef unsigned long long  ull;

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

	int N;
	cin >> N;

	int x;
	cin >> x;

	vector<int> a(N);
	for (auto& i : a) cin >> i;

	sort(ALL(a));

	int result = N - 1;
	REP (i, N) {
		x -= a[i];
		if (x < 0) {
			result = i;
			break;
		}
	}

	if (x == 0) {
		cout << N << endl;
	} else {
		cout << result << endl;
	}
}

Measured memory_bytes: 888
from collections import deque
import sys
input = sys.stdin.readline

S = input().rstrip()
Q = int(input())
FTC = [tuple(input().split()) for _ in range(Q)]

que = deque(['?'])
cnt = 0
for query in FTC:
    if query[0] == '1':
        cnt ^= 1
        continue

    sign = 0 if query[1] == '1' else 1

    if sign ^ cnt == 0:
        que.appendleft(query[2])
    else:
        que.append(query[2])

que = list(que)
ans = ''.join(que[:: (-1)**cnt])
ans = ans.replace('?', S[:: (-1)**cnt])

print(ans)

Measured memory_bytes: 22808