akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;

using ll= long long;
#define double long double
#define sz(x) (int)x.size()
#define all(x) (x).begin(),(x).end()
#define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define _set(x) __builtin_popcount(x)
#define _setl(x) __builtin_popcountll(x)
#define PI  3.14159265358979323846264338327950L
#define mod 1000000007LL

void debug(){
	cerr<<"]\n";
}
template<class H,class ... T> void debug(H h,T... t){
	cerr<<h;
	if(sizeof... (t)){
		cerr<<", ";
	}
	debug(t...);
}
#ifdef DEBUG
	#define dbg(...) cerr << "LINE(" << __LINE__ << ") -> [" << #__VA_ARGS__ << "]: [", debug(__VA_ARGS__)
	#define dpv(...) cerr<< "["#__VA_ARGS__ " : ";for(int i: (__VA_ARGS__)){cerr<<i<<" ";}cerr<<"]\n"
#else
	#define dbg(...) 0
	#define dpv(...) 0
#endif

void solve(){
	int n;
	cin>>n;
	vector<ll> cnt(n+3,2);
	cnt[1]=1;
	for(ll i=2;i<n+3;i++){
		for(ll j=i+i;j<n;j+=i){
			cnt[j]++;
		}
	}
	for(int i=2;i<=n;i++){
		cnt[i] += cnt[i-1];
	}
	cout<<cnt[n-1]<<"\n";
}


int32_t main(){
	IOS
	// freopen("input.txt","r",stdin);
	int _;
	// cin>>_;
	_=1;
	for(int i=1;i<=_;i++){
		// cout<<"Case #"<<i<<": ";
		solve();
	}
	return 0;
}

/*
   check for overflows int long long
   correct mize of array
*/


Measured memory_bytes: 11048
#include <bits/stdc++.h>
using namespace std;
//using Graph = vector<vector<edge>>;
using dou =long double;
string yes="yes";
string Yes="Yes";
string YES="YES";
string no="no";
string No="No";
string NO="NO";

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

#define rep(i, n)         for(int i = 0; i < (int)(n); i++)
#define brep(n)           for(int bit=0;bit<(1<<n);bit++)
#define erep(i,container) for (auto i : container)
#define irep(i, n)        for(int i = n-1; i >= (int)0; i--)
#define rrep(i,m,n) for(ll i = m; i < (ll)(n); i++)
#define reprep(i,j,h,w) rep(i,h)rep(j,w)
#define all(x) (x).begin(),(x).end()
#define VEC(type,name,n) std::vector<type> name(n);rep(i,n)std::cin >> name[i];
#define pb push_back
#define pf push_front
#define query int qq;std::cin >> qq;rep(qqq,qq)
#define lb lower_bound
#define ub upper_bound
#define fi first
#define se second
#define itn int
#define mp make_pair
#define sum(a) accumulate(all(a),0ll)
#define keta fixed<<setprecision
#define vvector(name,typ,m,n,a)vector<vector<typ> > name(m,vector<typ> (n,a))
//#define vvector(name,typ,m,n)vector<vector<typ> > name(m,vector<typ> (n))
#define vvvector(name,t,l,m,n,a) vector<vector<vector<t> > > name(l, vector<vector<t> >(m, vector<t>(n,a)));
#define vvvvector(name,t,k,l,m,n,a) vector<vector<vector<vector<t> > > > name(k,vector<vector<vector<t> > >(l, vector<vector<t> >(m, vector<t>(n,a)) ));
#define case std::cout <<"Case #" <<qqq+1<<": "
#define res resize
#define as assign
#define ffor for(;;)
#define ppri(a,b) std::cout << a<<" "<<b << std::endl
#define pppri(a,b,c) std::cout << a<<" "<<b <<" "<< c<<std::endl
#define aall(x,n) (x).begin(),(x).begin()+(n)
#define ssum(a) accumulate(a,0ll) 

typedef long long ll;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;
//typedef long long T;
ll ceil(ll a,ll b){
    return ((a+b-1)/b);
}
const int INF = 2000000000;
const ll INF64 = 9223372036854775807ll;
const ll MOD = 1000000007ll;
const dou pi=3.141592653589793;
//mapは、if関数などで覗いただけで構成されるので注意しよう！
//std::vector<vector<int>> g;
int main(){
    string s;
    std::cin >> s;
    int n=s.size();
    rep(i,n){
        if(s[i]=='?')s[i]='D';
    }
    std::cout << s << std::endl;
}

Measured memory_bytes: 3760
#include <iostream>
#include <string>

using namespace std;

int
main(){
    string s, t;

    cin >> s >> t;

    int minDiff = 999999;
    for(int i=0;i<=s.length()-t.length();i++){
        int curDiff = 0;
        for(int j=0;j<t.length();j++){
            if (s[i+j] != t[j]) {
                curDiff++;
            }
        }

        if (curDiff < minDiff) {
            minDiff = curDiff;
        }
    }

    cout << minDiff << endl;

    return 0;
}


Measured memory_bytes: 3628
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef string str;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector <pii> vpii;
typedef vector <pll> vpll;
typedef map <str,int> mapsi;
typedef map <str,int> :: iterator mapsitr;
typedef map <int , int> mint;
typedef map <ll , ll> mll;
typedef set <int> si;
typedef set <ll> sll;
typedef si :: iterator sitr;
typedef si :: reverse_iterator rsitr;
typedef sll :: iterator sltr;
typedef sll :: reverse_iterator rsltr;
#define mset multiset
typedef mset <int> msi;
typedef mset <ll> msll;
typedef msi :: iterator msitr;
typedef msi :: reverse_iterator msritr;
typedef msll :: iterator msltr;
typedef msll :: reverse_iterator mslritr;
#define mp make_pair
#define pb push_back
#define pob pop_back
#define fi first
#define se second
#define fs first.second
#define ss second.second
#define ff first.first
#define sf second.first
#define newl '\n'
char to_upper (char x){
    if( 97 <= int(x) && int(x) <= 126)return char(x-32);
    else if( 65 <= int(x) && int(x) <= 90)return x;
}
char to_lower (char x){
    if( 97 <= int(x) && int(x) <= 126)return x;
    else if( 65 <= int(x) && int(x) <= 90)return char(x+32);
}
int numerize (char x){
    if(48 <= int(x) && int(x) <= 57)return int(x-'0');
    else if( 97 <= int(x) && int(x) <= 126)return int(x-96);
    else if( 65 <= int(x) && int(x) <= 90)return int(x-64);
}
//void IO(){
//	#ifndef ONLINE_JUDGE
//	    freopen("input.txt", "r", stdin);
//	    freopen("output.txt", "w", stdout);
//	#endif
//}
// end of Template

int n;
void label (int x){
    if(x<10)cout<<"00";
    else if(x<100)cout<<"0";

    cout<<x<<newl;
}
int main(){
	//IO();
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin>>n;
    if(n<=999){cout<<"ABC"<<newl;}
    else {cout<<"ABD"<<newl;}
}


Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<queue>
#include<vector>
#include<string.h>
#include<algorithm>
#include <cmath>

using namespace std;
 
long long A,B,N;

long long gcd(long long n,long long m)
{
  long long a;
  if(n<m)
  {
    a=m;
    m=n;
    n=a;
  }
  
  a=n%m;
  while(a!=0)
  {
    n=m;
    m=a;
    a=n%m;
  }
  
  return m;
  
}
 
int main()
{
  cin >> A >> B;
  
  long long i,j,k,minN,count=1,n;

  n=gcd(A,B);
  
  for(i=2;i*i<=n;i++)
  {
    if(n%i!=0)
    {
      continue;
    }
    else
    {
      while(n%i==0)
      {
        n=n/i;
      }
      count++;
    }
  }
  
  if(n>1)
  {
    count++;
  }

   
  cout << count ;


}

Measured memory_bytes: 256
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     

fac = [-1] * (2 * 10**6+1)
inv = [-1] * (2 * 10**6+1)
finv = [-1] * (2 * 10**6+1)

fac[0] = fac[1] = 1
inv[1] = 1
finv[0] = finv[1] = 1

def initNCMMod(limit):
    for i in range(2, limit):
        fac[i] = fac[i-1] * i % mod
        inv[i] = mod - inv[mod%i] * (mod // i) % mod
        finv[i] = finv[i-1] * inv[i] % mod

def NCMMod(n, k):
    if n < k:
        return 0
    if (n < 0 or k < 0):
        return 0
    return fac[n] * (finv[k] * finv[n-k] % mod) % mod

initNCMMod(2 * 10**6 + 1)
def main():
    H, W, A, B = LI()
    cnt = 0
    for i in range(H-A):
        way = NCMMod(B + i - 1, i) * NCMMod(W + H - B - i - 2, W - 1 - B)
        way %= mod
        cnt += way
        cnt %= mod
    print(cnt)


main()



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

using namespace std;

#define rep(i, n) for(int i = 0; i < (int)n; ++i)
#define FOR(i, a, b) for(int i = a; i < (int)b; ++i)
#define rrep(i, n) for(int i = ((int)n - 1); i >= 0; --i)

using ll = long long;
using ld =  long double;

const ll INF = 1e18;
const int Inf = 1e9;
const double EPS = 1e-9;
const int MOD = 1e9 + 7;

class DisjointSet {
    public:
        vector<int> rank, p, size;

        DisjointSet() {}
        DisjointSet(int s) {
            rank.resize(s, 0);
            p.resize(s, 0);
            size.resize(s, 0);
            rep (i, s) init(i);
        }

        void init(int x) {
            p[x] = x;
            rank[x] = 0;
            size[x] = 1;
        }

        bool isSame(int x, int y) {
            return root(x) == root(y);
        }

        void makeSet(int x, int y) {
            if (isSame(x, y)) return;
            link(root(x), root(y));
        }

        void link(int x, int y) {
            if (rank[x] > rank[y]) {
                p[y] = x;
                size[x] += size[y];
            } else {
                p[x] = y;
                size[y] += size[x];
                if (rank[x] == rank[y]) {
                    rank[y]++;
                }
            }
        }

        int root(int x) {
            if (x != p[x]) {
                p[x] = root(p[x]);
            }
            return p[x];
        }

        int getSize(int x) {
            return size[root(x)];
        }
};

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(0);
    int n, m, k;
    cin >> n >> m >> k;
    DisjointSet dj = DisjointSet(n);
    vector<int> f(n);
    rep (i, m) {
        int a, b;
        cin >> a >> b;
        a--, b--;
        dj.makeSet(a, b);
        f[a]++, f[b]++;
    }
    vector<int> block[n];
    rep (i, k) {
        int c, d;
        cin >> c >> d;
        c--, d--;
        block[c].push_back(d);
        block[d].push_back(c);
    }
    rep (i, n) {
        int cnt = 0;
        for (auto b : block[i]) {
            if (dj.isSame(i, b)) cnt++;
        }
        cout << dj.getSize(i) - 1 - cnt - f[i];
        if (i == n - 1) cout << endl;
        else cout << " ";
    }
    
    return 0;
}



Measured memory_bytes: 7552
#include<iostream>
using namespace std;
int n,dp[5][107],o,ans;
int main()
{
    cin>>n;
    for(int i=1;i<=2;i++)
        for(int j=1;j<=n;j++)
        {
            cin>>o;
            dp[i][j]=dp[i][j-1]+o;
        }
    for(int i=1;i<=n;i++)
        ans=max(ans,dp[1][i]+dp[2][n]-dp[2][i-1]);
    
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1000000007;
 
ll powmod(ll x,ll y){
    ll res=1;
    for(ll i=0;i<y;i++){
        res=res*x%mod;
    }
    return res;
}
int main(){
    ll n;
    cin>>n;
    ll ans=powmod(10,n)-powmod(9,n)-powmod(9,n)+powmod(8,n);
    ans%=mod;
    ans=(ans+mod)%mod;
    cout<<ans<<"\n";
}

Measured memory_bytes: 3620
#include<stdio.h>
int main(){

	int a,b;
	scanf("%d%d",&a,&b);
	if(a < b){
		printf("a < b\n");
	}else if(a > b){
		printf("a > b\n");
	}else if(a==b){
		printf("a == b\n");
	}
	
	return 0;
}

Measured memory_bytes: 1008
import sys
import math
from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
from collections import deque
from bisect import bisect_left
from itertools import product
def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def LSI(): return list(map(int, list(sys.stdin.readline().rstrip())))
def LSI2(N): return [list(map(int, list(sys.stdin.readline().rstrip()))) for i in range(N)]
def S(): return sys.stdin.readline().rstrip()
def LS(): return sys.stdin.readline().split()
def LS2(N): return [sys.stdin.readline().split() for i in range(N)]
def FILL(i,h): return [i for j in range(h)]
def FILL2(i,h,w): return [FILL(i,w) for j in range(h)]
def FILL3(i,h,w,d): return [FILL2(i,w,d) for j in range(h)]
def FILL4(i,h,w,d,d2): return [FILL3(i,w,d,d2) for j in range(h)]
def sisha(num,digit): return Decimal(str(num)).quantize(Decimal(digit),rounding=ROUND_HALF_UP)
#'0.01'や'1E1'などで指定、整数に戻すならintをかます
MOD = 1000000007
INF = float("inf")
sys.setrecursionlimit(10**6+10)
input = sys.stdin.readline


ans = INF
H,W,K = MI()
s = LSI2(H)
for pattern in product([0,1],repeat=H-1):
    cut = 0
    before_idx = 0
    row_list = []
    for i,div in enumerate(pattern):
        if div==1:
            cut += 1
            square = s[before_idx:i+1]
            inv = list(zip(*square))
            row = [sum(inv[i]) for i in range(W)]
            row_list.append(row)
            before_idx = i+1
    square = s[before_idx:] #のこりのブロック
    inv = list(zip(*square))
    row_list.append([sum(inv[i]) for i in range(W)])
    if any([any([c>K for c in r]) for r in row_list]):
        continue
    cnt = [0]*len(row_list)
    tmp = [0]*len(row_list)
    for i in range(W):
        for j in range(len(row_list)):
            cnt[j] += row_list[j][i]
            tmp[j] = row_list[j][i]
        if any([c>K for c in cnt]):
            cut += 1
            cnt = tmp[:]
    ans = min(ans,cut)
print(ans)


Measured memory_bytes: 115800
// Words are flowing out like endless rain into a paper cup
// They slither while they pass they slip away across the universe
// Pools of sorrow, waves of joy are drifting through my open mind
// Possessing and caressing me

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

using LL = long long;

namespace _buff {

const size_t BUFF = 1 << 19;
char ibuf[BUFF], *ib = ibuf, *ie = ibuf;
char getc() {
    if (ib == ie) {
        ib = ibuf;
        ie = ibuf + fread(ibuf, 1, BUFF, stdin);
    }
    return ib == ie ? -1 : *ib++;
}

}

LL read() {
    using namespace _buff;
    LL ret = 0;
    bool pos = true;
    char c = getc();
    for (; (c < '0' || c > '9') && c != '-'; c = getc()) {
        assert(~c);
    }
    if (c == '-') {
        pos = false;
        c = getc();
    }
    for (; c >= '0' && c <= '9'; c = getc()) {
        ret = (ret << 3) + (ret << 1) + (c ^ 48);
    }
    return pos ? ret : -ret;
}

const size_t N = 1e5 + 5;

int n;
LL arr[N], sum[N];

pair<LL, LL> solve(int bound) {
    LL ret1 = 0, ret2 = 0;
    for (int i = 1, j = n; i <= n; ++i) {
        while (j && arr[j] + arr[i] >= bound) {
            --j;
        }
        ret1 += (n - j);
        ret2 += (n - j) * (LL) arr[i];
        ret2 += sum[n] - sum[j];
    }
    return {ret1, ret2};
}

int main() {
    n = read();
    LL m = read();
    generate_n(arr + 1, n, read);
    sort(arr + 1, arr + n + 1);
    partial_sum(arr + 1, arr + n + 1, sum + 1);

    int l = 1, r = 2e5, ans = 0;
    while (l <= r) {
        int mid = (l + r) >> 1;
        if (solve(mid).first >= m) {
            ans = mid;
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }
    cout << solve(ans).second - ans * (solve(ans).first - m);

    return 0;
}


Measured memory_bytes: 2304
#define __USE_MINGW_ANSI_STDIO 0
#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl '\n'
#define INF (1LL<<59)
#define ff first
#define ss second
#define mod 1000000007
#define pb push_back
#define mp make_pair
#define int long long
#define all(a) a.begin(), a.end()
#define inf (1LL<<61)
#define ull unsigned long long
#define debug1(x) cerr << #x << ": " << x <<'\n'
#define debug2(x, y) cerr << #x << ": " << x << '\t' << #y << ": " << y <<'\n'
#define debug3(x, y, z) cerr << #x << ": " << x << '\t' << #y << ": " << y << '\t' << #z << ": " << z <<'\n'
using namespace std;
int dx[]={1,0,-1,0};int dy[]={0,1,0,-1}; //4 Direction
//int dx[]={1,1,0,-1,-1,-1,0,1};int dy[]={0,1,1,1,0,-1,-1,-1};//8 direction
int gcd(int x,int y)
{
    if(y==0)
        return x;
    else
        return gcd(y,x%y);
}
int expo(int n,int m,int p)   //modULAR EXPONENTIATION
{
    int r=1;
    n=n%p;
    while(m>0)
    {
        if(m%2)
            r=(r*n)%p;
        n=(n*n)%p;
        m=m/2;
    }
    return r%p;
}
bool isPrime(int n)
{
    // Corner cases
    if (n <= 1)  return false;
    if (n <= 3)  return true;
 
    // This is checked so that we can skip 
    // middle five numbers in below loop
    if (n%2 == 0 || n%3 == 0) return false;
 
    for (int i=5; i*i<=n; i=i+6)
        if (n%i == 0 || n%(i+2) == 0)
           return false;
 
    return true;
}
int c,d;
int f(int x)
{
	if(x==0)
		return 0;
	int lcm=(c*d)/gcd(c,d);
	int s=x/c+x/d-x/lcm;
	return x-s;
}
int32_t main()
{
   IOS;
  /* #ifndef ONLINE_JUDGE
   freopen("input.txt","r",stdin); 
   freopen("output.txt","w",stdout);
   #endif 
   /********************* Code starts here ***********************/   
   int a,b;
   cin>>a>>b>>c>>d;
   cout<<f(b)-f(a-1)<<endl;
}	

Measured memory_bytes: 256
#include<cstdio>
#include<algorithm>

#define rep(i,n) for(int i=0;i<(n);i++)

using namespace std;

int w,h,a[20][20];

int idx[1<<20]; // 2^w -> Fibonacci ID

int dp[20][4][76866]; // partial memoization (got MLE!!)
int dfs(int i,int j,int S){
	if(i==h) return 0;
	if(j==w) return dfs(i+1,0,S);

	int dummy=-1;
	int &res=(j%5==0?dp[i][j/5][idx[S]]:dummy);

	if(res!=-1) return res;

	// not choose a[i][j]
	res=dfs(i,j+1,S&~(1<<j));
	// choose a[i][j]
	if((S>>j&1)==0 && (j==0 || (S>>j-1&1)==0)){
		res=max(res,dfs(i,j+1,S|1<<j)+a[i][j]);
	}
	return res;
}

int solve(){
	scanf("%d%d",&w,&h);
	rep(i,h) rep(j,w) scanf("%d",a[i]+j);

	int n=0;
	rep(S,1<<w){
		int adj=0;
		rep(j,w-1) if((S>>j&1) && (S>>j+1&1)) adj++;
		if(adj<=1) idx[S]=n++;
	}

	rep(i,h) rep(j,4) rep(k,n) dp[i][j][k]=-1;

	return dfs(0,0,0);
}

int main(){
	int T; scanf("%d",&T);
	for(int cas=1;cas<=T;cas++) printf("Case %d: %d\n",cas,solve());
	return 0;
}

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

int abs (int z)
{
	return z > 0 ? z : -z;
}
int min (int a, int b)
{
	return a < b ? a : b;
}
int result(int a[], int n)
{
	int dp[n];
	dp[0] = 0;
	dp[1] = abs(a[1] - a[0]);
	for (int i = 2; i < n; ++i)
	{
		dp[i] = min((abs(a[i]-a[i-2])+ dp[i-2]),(abs(a[i]-a[i-1])+ dp[i-1]));
	}
	return dp[n-1];
}

int main()
{
	int n;
	cin >> n;
	int a[n];
	for (int i = 0; i < n; ++i)
	{
		cin >> a[i];
	}
	int res = result(a,n);
	cout << res << endl;
	return 0;
}

Measured memory_bytes: 1024
import java.util.Scanner;

public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int a,b,c;
		boolean door = false;
		a = sc.nextInt();
		b = sc.nextInt();
		c = sc.nextInt();
		if(c == 1){
			door = true;
		} else if(a == 1&&b == 1){
			door = true;
		}
		if(door){
			System.out.println("Open");
		} else {
			System.out.println("Close");
		}
	}

}

Measured memory_bytes: 26248
#include <bits/stdc++.h>
#define int long long
using namespace std;

int n, D, d[500005];
int P[500005], ans[500005];

signed main(){
  
  cin>>n>>D;
  
  for(int i=0;i<n;i++) cin>>d[i];
    
  int p = 1;
  
  for(int i=n-1;i>=0;i--){
        
    P[i] = p;
    
    if( p * 2 <= d[i] ) continue;
    
    p += d[i];
  }
  
  int x = D;
  
  for(int i=0;i<n;i++){
    
    if( x >= P[i] ) ans[i] = 1;
    if( x == 0 ) ans[i] = 0;
    
    if( x > abs( x - d[i] ) ) x = abs( x - d[i] );
    
  }
  
  int q;
  cin>>q;
  
  while(q--){
    
    int A;
    cin>>A;
    
    if( ans[A-1] ) cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
    
  }
  
  return 0;
}


Measured memory_bytes: 13696
#include<iostream>
#include<queue>
#include<utility>
#include<vector>
#include<algorithm>
#include<functional>
#define INF 1e7
using namespace std;
typedef long long LL;
typedef pair<LL, LL> P;
struct edge { LL to, cost; };
 
vector<int>danger;
vector<int>v[114514];
LL ddis[114514];
vector<edge>G[114514];
LL dis[114514];
 
void dijkstra(int st) {
    priority_queue<P, vector<P>, greater<P> > Q;
    fill(dis, dis + 110000, 1e17);
    dis[st] = 0;
    Q.push(P(0, st));
 
    while (!Q.empty()) {
        P p = Q.top();
        Q.pop();
        int V = p.second;
        if (dis[V] < p.first)continue;
        for (int i = 0;i < G[V].size();i++) {
            edge e = G[V][i];
            if (dis[e.to] > dis[V] + e.cost) {
                dis[e.to] = dis[V] + e.cost;
                Q.push(P(dis[e.to], e.to));
            }
        }
    }
}
 
int main() {
    int n, m, k, s;
    cin >> n >> m >> k >> s;
 
    int p, q;
    cin >> p >> q;
 
    for (int i = 0;i<k;i++) {
        int a;
        cin >> a;
        danger.push_back(a-1);
    }
 
    for (int i = 0;i<m;i++) {
        int a, b;
        cin >> a >> b;
        v[a - 1].push_back(b - 1);
        v[b - 1].push_back(a - 1);
    }
 
    for (int i = 0;i<danger.size();i++) {
        v[114500].push_back(danger[i]);
    }
 
    queue<int>qe;
    queue<int>nq;
    fill(ddis, ddis +114501, INF);
    ddis[114500] = 0;
 
    qe.push(114500);
 
    for (int x = -1;x< s;x++) {
        int z = qe.size();
        for (int i = 0;i<z;i++) {
            int a = qe.front();
            qe.pop();
            for (int j = 0;j<v[a].size();j++) {
                if (ddis[v[a][j]] == 10000000) {
                    ddis[v[a][j]] = x;
                    nq.push(v[a][j]);
                }
            }
        }
        while (nq.size()) {
            qe.push(nq.front());
            nq.pop();
        }
    }
 
    for (int i = 0;i <n;i++) {
        for (int j = 0;j < v[i].size();j++) {
 
        bool ba=false,bb=false;
        for(int k=0;k<danger.size();k++){
        if(danger[k]==i)ba=true;
        else if(danger[k]==v[i][j])bb=true;
        }
 
        if(ba||bb)continue;
 
 if(v[i][j]!=n-1){
            if ((ddis[i] == 10000000)&&(ddis[v[i][j]] == 10000000)) {
                G[i].push_back({ v[i][j],p });
            }
            else if(ddis[v[i][j]]==10000000){
                G[i].push_back({ v[i][j],p });
            }
            else {
                G[i].push_back({ v[i][j],q });
            }
        }
       else{
		   G[i].push_back({v[i][j],0});
		   } 
	}
    }
 
    dijkstra(0);
    cout << dis[n-1] << endl;

    return 0;
}

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

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

#define ll long long
#define pi pair<int, int>
#define pll pair<ll, ll>

#define MOD 1000000007
#define INF 1000000000000000LL

using namespace std;

int main(){
  int n;cin>>n;
  queue<int> schedules[1000];
  rep(i, n)rep(j, n-1){
    int t;cin>>t; t--;
    schedules[i].push(t);
  }

  int days=0;
  while(true){
    set<int> s;
    rep(i, n){
      if(schedules[i].empty())continue;

      int opp = schedules[i].front();
      if(schedules[opp].front() == i)s.insert(i);
    }
    if(s.empty())break;
    days++;
    for(auto t:s) schedules[t].pop();
  }

  bool f=true;
  rep(i, n)if(schedules[i].size())f=false;

  if(f) cout<<days<<endl;
  else cout<<-1<<endl;

  return 0;
}

Measured memory_bytes: 8068
#D
class UnionFind():
    # https://www.slideshare.net/chokudai/union-find-49066733
    # 作りたい要素数nで初期化
    # 使用するインスタンス変数の初期化
    def __init__(self, n):
        self.n = n
        # root[x]<0ならそのノードが根かつその値が木の要素数
        # rootノードでその木の要素数を記録する
        # root[x]>=0の場合は、特に直接的な意味を持たない気がする。計算に寄与するので意味はあるのだろうが。
        self.root = [-1]*(n+1)
        # 木をくっつける時にアンバランスにならないように調整する
        # 無結合の時はRank=0,結合して1つ木が深くなると根がRank+=1
        self.rnk = [0]*(n+1)

    # ノードxのrootノードを見つける
    #
    def Find_Root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            # ここで代入しておくことで、後の繰り返しを避ける
            self.root[x] = self.Find_Root(self.root[x])
            return self.root[x]

    # 木の併合、入力は併合したい各ノード
    def Unite(self, x, y):
        # 入力ノードのrootノードを見つける
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        # すでに同じ木に属していた場合
        if(x == y):
            return
        # 違う木に属していた場合rnkを見てくっつける方を決める
        # (1)xのランクの方が大きい(位置が深い)場合
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x

        # (2)yのランクの方が大きい(位置が深い)場合 or 等しい場合
        # また等しい場合、引数の2つめのyの方のランクを1つ増やす
        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            # rnkが同じ（深さに差がない場合）は1増やす
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1

    # xとyが同じグループに属するか判断
    # Return: True or False
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

    # ノードxが属する木のサイズを返す
    def Count(self, x):
        return -self.root[self.Find_Root(x)]
    
##################################################################
N,M=map(int,input().split())
A=[0]*M
B=[0]*M
UN=UnionFind(N)
for i in range(M):
    A[i],B[i] = map(int,input().split())
    A[i] -= 1
    B[i] -= 1
    UN.Unite(A[i],B[i])
    
#print(UN.root)
ans=0
for i in range(N):
    ans=max(ans,UN.Count(i))
print(ans)

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

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

typedef int _loop_int;
#define REP(i,n) for(_loop_int i=0;i<(_loop_int)(n);++i)
#define FOR(i,a,b) for(_loop_int i=(_loop_int)(a);i<(_loop_int)(b);++i)
#define FORR(i,a,b) for(_loop_int i=(_loop_int)(b)-1;i>=(_loop_int)(a);--i)

#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define DEBUG_VEC(v) cout<<#v<<":";REP(i,v.size())cout<<" "<<v[i];cout<<endl
#define ALL(a) (a).begin(),(a).end()

#define CHMIN(a,b) a=min((a),(b))
#define CHMAX(a,b) a=max((a),(b))

// mod
const ll MOD = 1000000007ll;
#define FIX(a) ((a)%MOD+MOD)%MOD

// floating
typedef double Real;
const Real EPS = 1e-11;
#define EQ0(x) (abs(x)<EPS)
#define EQ(a,b) (abs(a-b)<EPS)
typedef complex<Real> P;

string s;
ll l,r;

int z[430252];
void zalgo(string s){
  REP(i,s.size())z[i] = 0;
  // z algorithm
  // http://snuke.hatenablog.com/entry/2014/12/03/214243
  z[0] = s.size();
  {
    int i=1,j=0;
    while(i<s.size()){
      while(i+j<s.size() && s[j]==s[i+j]){
        j++;
      }
      z[i]=j;
      if(j==0){
        i++;
        continue;
      }
      int k=1;
      while(i+k<s.size() && k+z[k]<j){
        z[i+k] = z[k];
        k++;
      }
      i+=k;
      j-=k;
    }
  }
}

ll fibmemo[1252];
ll fib(int x){
  if(x==0)return 0;
  if(x==1)return 1;
  if(fibmemo[x]>0)return fibmemo[x];
  return fibmemo[x] = fib(x-1)+fib(x-2);
}

ll cnt[26];
ll ans[26];

void calc(string &X, string &Y, ll end){
  ll x = X.size();
  ll y = Y.size();
  if(end <= x+y){
    // greedy
    REP(i,end){
      if(i<x)cnt[X[i]-'a']++;
      else cnt[Y[i-x]-'a']++;
    }
    return;
  }
  ll xcnt = 1; int xi=1;
  ll ycnt = 0; int yi=0;
  while(x*xcnt+y*ycnt <= end){
    xcnt = fib(++xi);
    ycnt = fib(++yi);
  }
  xcnt = fib(--xi);
  ycnt = fib(--yi);
  REP(i,x)cnt[X[i]-'a']+=xcnt;
  REP(i,y)cnt[Y[i]-'a']+=ycnt;
  ll len = x*xcnt+y*ycnt;
  if(len==end)return;
  calc(X,Y,end-len);
}

string f(string s){
  zalgo(s);
  int n = s.size();
  int k = 0;
  REP(i,(n-1)/2){
    if(z[n-1-i]>=i+1)k=i+1;
  }
  string t = s.substr(0,n-k);
  return t+t;
}

int main(){
  cin>>s;
  int n = s.size();
  cin>>l>>r;
  // first step
  s = f(s);
  // second
  string t = f(s);

  string X = s.substr(0,s.size()/2);
  string Y = t.substr(X.size(),t.size()/2-X.size());
  calc(X,Y,r);
  REP(i,26)ans[i]=cnt[i];
  REP(i,26)cnt[i]=0;
  // if(l>1){
    calc(X,Y,l-1);
    REP(i,26)ans[i]-=cnt[i];
  // }
  REP(i,26)printf("%lld%c",ans[i],i==25?'\n':' ');
  return 0;
}


Measured memory_bytes: 3060
#include <bits/stdc++.h> //Andrei Alexandru a.k.a Sho10
#define ll long long int
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#define all(a) (a).begin(), (a).end()
#define sz size
#define f first
#define s second
#define pb push_back
#define er erase
#define in insert
#define mp make_pair
#define pi pair
#define rc(s) return cout<<s,0
#define endl '\n'
#define mod 1000000007
#define PI 3.14159265359
#define CODE_START  ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
ll n;
int32_t main(){
CODE_START;
cin>>n;
cout<<setprecision(8)<<double(2*PI*n);
}


Measured memory_bytes: 3796
#include <stdio.h>
#include <cstdio>
#include <queue>
#include <set>
#include <math.h>
using namespace std;

int main(){
  
  /* read input */
  int N;
  scanf("%d", &N); // read int
  
  /* preparation */
  int primes[25] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97};
  
  //for(int i = 0; i < 25; i++){
    //printf("%d\n", primes[i]);
  //}
  int count[100]; /* number of prime factors in N!*/
  for(int i = 0; i < 100; i++)count[i]=0;

  for(int i = 0; i < 25; i++){
    int N_tmp = N;
    while(N_tmp != 0){
      count[i] += N_tmp / primes[i];
      N_tmp /= primes[i];
    }
  }
  
  /*
  for(int n_ = 2; n_ <= N; n_++){
    int n = n_;
    while(n > 1){
      int roota = (int)sqrt((double)n) + 1;
      int a_tmp = n;
      for(int i = 2; i <= roota; i++){
        if(n%i == 0){
          count[i-1]++;
          n = n/i;
          i = roota+1; // get out of for loop
        }
      }
      // if a is prime
      if(n == n_){
        count[n-1]++;
        n=1;
      }
    }
  }*/
  
  /*for(int i = 0; i < 100; i++){
    printf("%d ", count[i]);
  }*/
  
  /*solve problem*/
  int ans = 0;
  
  // count x^74 type
  for(int i = 0; i < 100; i++){
    if(count[i] >= 74){
      ans++;
    }
  }
  
  // count x^2 y^24 type
  int n2 = 0;
  int n24 = 0;
  for(int i = 0; i < 100; i++){
    if(count[i] >= 2){
      n2++;
    }
    if(count[i] >= 24){
      n24++;
    }
  }
  ans += n24*(n2-1);
  
  // count x^4 y^14 type
  int n4 = 0;
  int n14 = 0;
  for(int i = 0; i < 100; i++){
    if(count[i] >= 4){
      n4++;
    }
    if(count[i] >= 14){
      n14++;
    }
  }
  ans += n14*(n4-1);

  // count x^2 y^4 z^4 type
  ans += (n4*(n4-1))/2 *(n2-2);
  
  printf("%d", ans);
  
  return 0;
}


Measured memory_bytes: 128
while True:
    x = input().split(" ")
    h = x[0]
    w = x[1]
    if int(h) == 0 and int(w) == 0:
        break
    else:
        for i in range(0, int(w)):
            print("#", end="")
        print()
        for i in range (0, int(h)-2):
            print("#", end="")
            for j in range(0, int(w)-2):
                print(".", end="")
            print("#")
        for i in range (0, int(w)):
                print("#", end="")
        print()
        print()
        


Measured memory_bytes: 7000
#include <stdio.h>

int main(void) {
	int a,n,f,ln,lf=0,i;
	scanf("%d",&a);
	ln = a + 1;
	for(i = 1;i <= a;i++){
		scanf("%d%d",&n,&f);
		if((lf < f) || ((lf == f) && (ln > n))){
			ln = n;
			lf = f;
		}
	}
	printf("%d %d\n",ln,lf);
	return 0;
}

Measured memory_bytes: 600
def solve(N, M, A):
    answer = [0] * (N+1)
    answer[0] = 1
    if 1 in A:
        answer[1] = 0
    else:
        answer[1] = 1

    for s in range(2, N+1):
        if s in A:
            answer[s] = 0
        else:
            answer[s] = (answer[s-2] + answer[s-1]) % 1000000007
    print(answer[N])

N, M = [int(x) for x in input().split()]
A = set()
for i in range(M):
    A.add(int(input()))
solve(N, M, A)



Measured memory_bytes: 11884
#include<stdio.h>
 
int main(void)
 
{
 
int W,H,x,y,r;
 
scanf("%d %d %d %d %d",&W,&H,&x,&y,&r);
 
if(!(-100<=x&&x<=100)){
 
return 0;
 
}
 
if(!(-100<=x&&x<=100)){
 
return 0;
 
}
 
if(!(-100<=y&&y<=100)){
 
return 0;
 
}
 
if(!(0<W&&W<=100)){
 
return 0;
 
}
 
if(!(0<H&&x<=100)){
 
return 0;
 
}
 
if(!(0<r&&r<=100)){
 
return 0;
 
}
 
if(y+r<=H &&  y-r>=0 && x+r<=W && x-r>=0){
 
printf("Yes\n");
 
}
 
else{
 
printf("No\n");
 
}
 
return 0;
 
}

Measured memory_bytes: 584
#include <stdio.h>

int main(int argc, char *argv[]){
      double x1, x2, y1, y2, xq, yq;
      double a, b, c, d;
      double x, y;

      while(~scanf("%lf,%lf,%lf,%lf,%lf,%lf",&x1,&y1,&x2,&y2,&xq,&yq)){
	   if(x1==x2) /* P1-P2ÌX« */
		x = x1, y = yq;

	   else if(y1==y2) /* Q-Q'ÌX« */
		x = xq, y = y1;

	   else{ /* otherwise */
		a = (y2-y1)/(x2-x1), b = y1-a*x1;
		c = -1/a, d = yq-c*xq;
		x = (d-b)/(a-c), y = a*x+b;
	   }
	   
	   printf("%lf %lf\n",x+(x-xq),y+(y-yq));
      }

      return 0;
 }

Measured memory_bytes: 0
//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,fma")
//#pragma GCC optimization("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define bit(i) (1<<(i))
#define set(mask,i) (mask |= (1<<(i)))
#define get(mask,i) (mask & (1<<(i)))
typedef long long ll;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const double PI = acos(-1);
const int64_t INF = (int64_t)1e18;

void solve() {
	int n;
	cin >> n;
	int64_t arr[n+1][3];
	for(int i = 1; i <= n; i++) {
		for(int j = 0; j < 3; j++) {
			cin >> arr[i][j];
		}
	}
	int64_t dp[n + 1][3];
	for(int i = 0; i <= n; i++) {
		for(int j = 0; j < 3; j++) {
			dp[i][j] = -INF;
		}
	}
	dp[0][0] = dp[0][1] = dp[0][2] = 0;
	for(int i = 1; i <= n; i++) {
		dp[i][0] = max(arr[i][1] + dp[i-1][1], arr[i][2] + dp[i-1][2]);
		dp[i][1] = max(arr[i][0] + dp[i-1][0], arr[i][2] + dp[i-1][2]);
		dp[i][2] = max(arr[i][0] + dp[i-1][0], arr[i][1] + dp[i-1][1]);
	}
	cout << max({dp[n][0], dp[n][1], dp[n][2]});
}

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

	solve();

	return 0;
}


Measured memory_bytes: 8328
#include<cstdio>
#include<vector>
#include<algorithm>
#include<utility>
#include<numeric>
#include<iostream>
#include<array>
#include<string>
#include<sstream>
#include<stack>
#include<queue>
#include<list>
#include<functional>
#define _USE_MATH_DEFINES

#include<math.h>
#include<map>

#define SENTINEL 1000000001

#define min(a,b) (a)>(b)?(b):(a)
#define max(a,b) (a)>(b)?(a):(b)

using namespace std;

typedef pair<int, int> pii;

using namespace std;

int D;

struct OwnNode
{
	int x, y;
	int index;
	int right;
	int left;

	OwnNode() :x(-1), y(-1), index(-1), right(-1), left(-1){}
	OwnNode(int x, int y) : x(x), y(y) {}

	bool operator<(const OwnNode& n)const
	{
		if (D % 2 == 0)
		{
			return x < n.x;
		}
		else
		{
			return y < n.y;
		}
	}
	bool operator>(const OwnNode& n)const
	{
		if (D % 2 == 0)
		{
			return x > n.x;
		}
		else
		{
			return y > n.y;
		}
	}
};

OwnNode nodes[500000];


void find(int index,OwnNode& ld, OwnNode& ru, int d, vector<int>& v)
{
	if (ld.x <= nodes[index].x&&nodes[index].x <= ru.x&&ld.y <= nodes[index].y&&nodes[index].y <= ru.y)
	{
		v.push_back(nodes[index].index);
	}

	if (d % 2 == 0)
	{
		if (ld.x <= nodes[index].x)
		{
			if (nodes[index].left != -1)
			{
				find(nodes[index].left, ld, ru, d + 1, v);
			}
		}
		if (nodes[index].x <= ru.x)
		{
			if (nodes[index].right != -1)
			{
				find(nodes[index].right, ld, ru, d + 1, v);
			}
		}
	}
	else
	{
		if (ld.y <= nodes[index].y)
		{
			if (nodes[index].left != -1)
			{
				find(nodes[index].left, ld, ru, d + 1, v);
			}
		}
		if (nodes[index].y <= ru.y)
		{
			if (nodes[index].right != -1)
			{
				find(nodes[index].right, ld, ru, d + 1, v);
			}
		}
	}
}

int BuildKDTree(int s, int e, int d)
{
	int m = (s + e) / 2;
	D = d;
	nth_element(nodes + s, nodes + m, nodes + e + 1);
	nodes[m].left = m == s ? -1 : BuildKDTree(s, m - 1, d + 1);
	nodes[m].right = m == e ? -1 : BuildKDTree(m + 1, e, d + 1);
	return m;
}

int main()
{
	int n, q;
	scanf("%d", &n);

	for (int i = 0; i < n; i++)
	{
		int x, y;
		scanf("%d %d", &x, &y);
		nodes[i].x = x;
		nodes[i].y = y;
		nodes[i].index = i;
	}

	int root = BuildKDTree(0, n - 1, 0);

	scanf("%d", &q);

	for (int i = 0; i < q; i++)
	{
		int x1, y1, x2, y2;
		scanf("%d %d %d %d", &x1, &x2, &y1, &y2);
		OwnNode n1(x1, y1), n2(x2, y2);
		vector<int> v;
		find(root,n1, n2, 0, v);
		sort(v.begin(), v.end());
		for (auto& n : v)
		{
			cout << n << endl;
		}
		cout << endl;
	}

	return 0;
}




Measured memory_bytes: 12984
import numpy as np

n, m = np.asarray(input().split(), dtype=np.int32)

if n == 1:
    ans = "0"
    check = "0"
elif n == 2:
    ans = "10"
    check = "00"
else:
    ans = "100"
    check = "000"

if m == 0:
    print(ans)

else:
    ans = list(ans)
    check = list(check)
    for i in range(m):
        s, c = np.asarray(input().split(), dtype=np.int32)
        s -= 1
        if check[s] == "0":
            ans[s] = str(c)
            check[s] = "1"
        else:
            if ans[s] != str(c):
                print(-1)
                break

        if i+1 == m:
            if n > 1 and ans[0] == "0":
                print(-1)
                break
            print("".join(ans))


Measured memory_bytes: 12504
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>



using std::max;
using std::priority_queue;
using std::vector;
using std::lower_bound;
using std::sort;

const int MAXN=100011;
const int INF=1034567890;


int N, M;

int A[MAXN], B[MAXN];
int C[MAXN];

struct Pair{
	int *p, v;
	Pair(){}
	Pair(int *_p, int _v){p=_p;v=_v;}
};

inline bool cmpv(const Pair &A, const Pair &B){
	return A.v<B.v;
}

Pair P[MAXN], Tmp;

int Sum[MAXN], Ans[MAXN];
bool Used[MAXN];
int Cnt;

struct Node{
	int l, r;
	int u;
} T[MAXN<<2];

void Build(int at, int l, int r){
	T[at].l=l;T[at].r=r;
	T[at].u=0;
	if(l==r)	return;
	int m=(l+r)>>1;
	Build(at<<1, l, m);
	Build((at<<1)|1, m+1, r);
}

void Update(int at, int l, int r){
	if(T[at].l>=l && T[at].r<=r){
		++T[at].u;
		return;
	}
	int m=(T[at].l+T[at].r)>>1;
	if(r>m)	Update((at<<1)|1, l, r);
	if(l<=m)	Update(at<<1, l, r);
}

int Ask(int p, int at=1){
	int m=(T[at].l+T[at].r)>>1;
	if(T[at].l==T[at].r)	return T[at].u+Sum[m];
	int ret=T[at].u;
	if(p<=m)	ret+=Ask(p, at<<1);
	else	ret+=Ask(p, (at<<1)|1);
	return ret;
}

struct Seg{
	int l, r, id;
	Seg(){}
	Seg(int _l, int _r, int _id){l=_l;r=_r;id=_id;}
};

struct Cmpl{
	bool operator () (Seg A, Seg B){
		return A.l>B.l;
	}
};

struct Cmpr{
	bool operator () (Seg A, Seg B){
		return A.r<B.r;
	}
};

vector<Seg> L[MAXN], R[MAXN];

int main(){
	
	scanf("%d", &N);
	for(int i=1;i<=N;++i)	scanf("%d%d", &A[i], &B[i]);
	for(int i=0;i<=N;++i)	scanf("%d", &C[i]);
	
	for(int i=0;i<=N;++i)	P[i]=Pair(&C[i], C[i]);
	
	sort(P, P+N+1, cmpv);
	
	for(int i=0;i<=N;++i)	(*P[i].p)=i;
	
	for(int i=1;i<=N;++i){
		Tmp=Pair(&A[i], A[i]);
		*Tmp.p=lower_bound(P, P+N+1, Tmp, cmpv)-P;
		Tmp=Pair(&B[i], B[i]);
		*Tmp.p=lower_bound(P, P+N+1, Tmp, cmpv)-P;
	}
	
	//for(int i=0;i<=N;++i)	printf("%d\n", C[i]);
	//for(int i=1;i<=N;++i)	printf("%d %d\n", A[i], B[i]);
	
	for(int i=0;i<=N;++i)	Sum[i]=-1;
	for(int i=1;i<=N;++i)	if(A[i]<=N)	Sum[A[i]]+=1;
	for(int i=1;i<=N;++i)	Sum[i]+=Sum[i-1];
	
	for(int i=1;i<=N;++i){
		if(B[i]>=A[i])	continue;
		Seg Tmp=Seg(B[i], A[i]-1, i);
		L[Tmp.r].push_back(Tmp);
		R[Tmp.l].push_back(Tmp);
	}
	
	Build(1, 0, N);
	
	//for(int i=0;i<=N;++i)	printf("%d\n", Sum[i]);
	{
		priority_queue<Seg, vector<Seg>, Cmpl> PQ;
		for(int i=N;i>=0;--i){
			for(Seg s:L[i]){
				PQ.push(s);
			}
			for(Seg s;Ask(i)<-1 && !PQ.empty();){
				s=PQ.top();PQ.pop();
				Update(1, s.l, s.r);
				Used[s.id]=true;
				++Cnt;
			}
			if(Ask(i)<-1)	Cnt=INF;
		}
	}
	
	{
		Ans[0]=Cnt;
		priority_queue<Seg, vector<Seg>, Cmpr> PQ;
		for(int i=0;i<=N;++i){
			for(Seg s:R[i]){
				if(!Used[s.id])	PQ.push(s);
			}
			for(Seg s;Ask(i)<0 && !PQ.empty();){
				s=PQ.top();PQ.pop();
				Update(1, s.l, s.r);
				Used[s.id]=true;
				++Cnt;
			}
			if(Ask(i)<0)	Cnt=INF;
			Ans[i+1]=Cnt;
		}
	}
	
	int ANS;
	scanf("%d", &M);
	for(int i=1, a, b;i<=M;++i){
		scanf("%d%d", &a, &b);
		Tmp=Pair(&a, a);
		*Tmp.p=lower_bound(P, P+N+1, Tmp, cmpv)-P;
		Tmp=Pair(&b, b);
		*Tmp.p=lower_bound(P, P+N+1, Tmp, cmpv)-P;
		ANS=max(N+1-Ans[a], N-Ans[b]);
		if(ANS<0)	puts("-1");
		else	printf("%d\n", ANS);
	}
	
	return 0;
}

Measured memory_bytes: 21344
#include<iostream>
#include<set>
using namespace std;
typedef long long ll;

int main() {
	set<ll>st;
	ll N, a;
	cin >> N;
	for (ll i = 0;i < N;i++) {
		cin >> a;
		if (st.count(a) != 1)st.insert(a);
		else st.erase(a);
	}
	cout << st.size() << endl;
	return 0;
}

Measured memory_bytes: 4864
A,B= input().split() 
A=int(A)
B=int(B)
seki=1
#print(A,B,seki)
if B>A:
  C=B
  B=A
  A=C
for i in range(2,A+1):
  while 1:
    wareru=0
    if round(int(A/i)*i,0)==A:
      wareru=1
      A/=i
    if round(int(B/i)*i,0)==B:
      wareru=1
      B/=i
    if wareru==0:
      break
    else:
      seki*=i
print(round(seki))

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

bool f(ll a,ll b){
return a>b;
}

int n;
int arr[100005][4];
int dp[100005][4];
 ll fact(int day,int choice){
	if(day==n+1)return 0;
	if(dp[day][choice] !=-1)
	return dp[day][choice];
	ll mx=0;
	bool b=false;
	 if(choice==0){
	 	b=true;
	 	mx=max(mx,arr[day][1]+fact(day+1,1));
	 	mx=max(mx,arr[day][2]+fact(day+1,2));
	 	mx=max(mx,arr[day][3]+fact(day+1,3));
	 }
	 if(choice==1){
	 	mx=max(mx,arr[day][2]+fact(day+1,2));
	 	mx=max(mx,arr[day][3]+fact(day+1,3));
	 }
	 if(choice==2){
	 	mx=max(mx,arr[day][1]+fact(day+1,1));
	 	mx=max(mx,arr[day][3]+fact(day+1,3));
	 }
	 if(choice==3){
	 	mx=max(mx,arr[day][1]+fact(day+1,1));
	 	mx=max(mx,arr[day][2]+fact(day+1,2));
	 }
	 return dp[day][choice]=mx; 
}

int main(){
int t=1;

while(t--){
cin>>n;
for(int i=1;i<=n;i++){
for(int j=1;j<=3;j++){
cin>>arr[i][j];
}}
memset(dp, -1, sizeof dp);
cout<<fact(0,0)<<endl;
}

return 0;
}


Measured memory_bytes: 14492
#include <stdio.h>
typedef long long ll;

int main(void) {
  ll i, n, a, m = 0, mn, m2 = 0, m2n;
  scanf("%lld", &n);
  for(i = 0; i < n; ++i) {
    scanf("%lld", &a);
    if(m <= a) m2 = m, m2n - mn, m = a, mn = i;
    else if(m2 <= a) m2 = a, m2n = i;
  }
  for(i = 0; i < n; ++i) printf("%lld\n", mn == i ? m2 : m);
  return 0;
}

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

using namespace std;
typedef long long ll;

#define rep(i,a,b) for(ll i=a;i<b;i++)
#define rrep(i,a,b) for(ll i=a;i>=b;i--)

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

   if (isupper(s))
   {
       cout << "A" << endl;
   }
   else
   {
       cout << "a" << endl;
   }

   return 0;
}


Measured memory_bytes: 3620
/*  HARD WORK FOREVER PAYS  */
#include<bits/stdc++.h>
#define turbo(){	\
	ios_base::sync_with_stdio(false); \
	cin.tie(NULL); \
}
using namespace std;
typedef long long ll;
int dp[100];
ll fib(ll n){
	if(n==1||n==0) return 1;
	if(dp[n]!=-1) return dp[n];
	return dp[n]=fib(n-1)+fib(n-2);
}
int main()
{
	turbo();
	ll n;
	cin>>n;
	memset(dp,-1,sizeof(dp));
	cout<<fib(n)<<endl;
	return 0;	
}



Measured memory_bytes: 3168
n,m = map(int,input().split())
L = []
R = []
for i in range(0,m):
  l,r = map(int,input().split())
  L.append(l)
  R.append(r)
if min(R)-max(L) >= 0:
  print(min(R)-max(L)+1)
else:
  print(0)

Measured memory_bytes: 11052
#include<iostream>
#include<vector>
#include<queue>

using namespace std;

void add(int node);

vector<int> children[200000];
int cnt[200000] = { 0 };

int main() {
	queue<int> dc;
	dc.push(0);
	int n, q;
	int tmp1, tmp2;
	cin >> n >> q;
	pair<int, int>*p = new pair<int, int>[n-1];
	pair<int, int>* pb = new pair<int, int>[n - 1];
	bool *flag = new bool[n - 1];
	for (int i = 0;i < n-1;i++) {
		cin >> tmp1 >> tmp2;
		tmp1--;
		tmp2--;
		p[i] = make_pair(tmp1, tmp2);
		pb[i] = make_pair(tmp2, tmp1);
		flag[i] = false;
	}
	flag[0] = true;
	sort(p, p + n - 1);
	sort(pb, pb + n - 1);
	while (!dc.empty()) {
		tmp1 = dc.front();
		dc.pop();
		for (int i = (lower_bound(p, p + n - 1, make_pair(tmp1, 0)) - p);i < lower_bound(p, p + n - 1, make_pair(tmp1 + 1, 0)) - p;i++) {
			if (!flag[p[i].second]) {
				dc.push(p[i].second);
				children[tmp1].push_back(p[i].second);
				flag[p[i].second] = true;
			}
		}
		for (int i = (lower_bound(pb, pb + n - 1, make_pair(tmp1, 0)) - pb);i < lower_bound(pb, pb + n - 1, make_pair(tmp1 + 1, 0)) - pb;i++) {
			if (!flag[pb[i].second]) {
				dc.push(pb[i].second);
				children[tmp1].push_back(pb[i].second);
				flag[pb[i].second] = true;
			}
		}
	}
	for (int i = 0;i < q;i++) {
		cin >> tmp1 >> tmp2;
		cnt[tmp1 - 1] += tmp2;
	}
	add(0);
	for (int i = 0;i < n-1;i++) {
		cout << cnt[i] << " ";
	}
	cout << cnt[n - 1] << endl;



}


void add(int node) {
	for (int i = 0;i < children[node].size();i++) {
		cnt[children[node][i]] += cnt[node];
		add(children[node][i]);
	}
}


Measured memory_bytes: 26880
object Main extends App {
  val Array(n, k) = io.StdIn.readLine().split(' ').map(_.toInt)
  val k2 = k * 2
  var (sum, white) = (0, 0)
  val matrix = Array.fill(k2)(Array.fill(k2)(0))
  (0 to k2-1).foreach(i => matrix(i) = new Array[Int](k2))
  (0 to n-1).foreach { i =>
    val temp = io.StdIn.readLine().split(' ')
      if (temp(2) == "B") {
        sum = sum + 1
        matrix(temp(0).toInt % k2)(temp(1).toInt % k2) += 1
      }
      else {
        sum = sum - 1
        white = white + 1
        matrix(temp(0).toInt % k2)(temp(1).toInt % k2) -= 1
      }
  }
  for {
    i <- (0 to k2-1)
    j <- (1 to k2-1)
  } matrix(i)(j) += matrix(i)(j-1)
  for {
    j <- (0 to k2-1)
    i <- (1 to k2-1)
  } matrix(i)(j) += matrix(i-1)(j)
  val cnt =
    (matrix(k-1)(k-1)) +
    (matrix(k2-1)(k2-1) - matrix(k-1)(k2-1) - matrix(k2-1)(k-1) + matrix(k-1)(k-1))
  var max = Math.max(cnt, sum - cnt)
  for { 
    i <- (0 to k-1)
    j <- (0 to k-1)
  } {
    val cnt = 
      (matrix(i)(j)) +
      (matrix(i+k)(j+k) - matrix(i+k)(j) - matrix(i)(j+k) + matrix(i)(j)) +
      (matrix(k2-1)(j) - matrix(i+k)(j)) +
      (matrix(i)(k2-1) - matrix(i)(j+k)) +
      (matrix(k2-1)(k2-1) - matrix(k2-1)(j+k) - matrix(i+k)(k2-1) + matrix(i+k)(j+k))
    max = Math.max(Math.max(cnt, sum - cnt), max)
  }
  print(max + white)
}


Measured memory_bytes: 91268
#include <stdio.h>

int main(void)
{
	int a, b, c;
		
	scanf("%d %d %d",&a, &b, &c);
	if(a == b)
	puts("No");
	else if(b == c)
	puts("No");
	else if(c == a)
	puts("No");
	else if(a == b == c)
	puts("No");
	else if(a > b)
	puts("No");
	else if(b > c)
	puts("No");
	else if(c < a)
	puts("No");
	else if(a < b < c)
	puts("Yes");
	else
	puts("No");
	
	return 0;
}

Measured memory_bytes: 580
#include <stdio.h>

int main(void)
{
  int a = 0;
  int b = 0;
  int area = 0;
  int cir = 0;

  scanf("%d %d", &a, &b);

  area = a * b;
  cir = 2 * a + 2 * b;

  printf("%d %d\n", area, cir);

  return 0;
}

Measured memory_bytes: 596
import java.util.*;

import static java.lang.System.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int C = sc.nextInt();

        int[][] D = new int[C + 1][C + 1];
        for (int i = 1; i <= C; i++) {
            for (int j = 1; j <= C; j++) {
                D[i][j] = sc.nextInt();
            }
        }

        int[][] c = new int[N + 1][N + 1];
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                c[i][j] = sc.nextInt();
            }
        }

        // カラーcが(i+j)%3の余りのポジションに存在する数
        int[][] colorNums = new int[C + 1][3];
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                colorNums[c[i][j]][(i + j) % 3]++;
            }
        }

        // (i+j)%3があるカラーである全組み合わせを列挙
        int minDSum = Integer.MAX_VALUE;
        for (int c1 = 1; c1 <= C; c1++) {
            for (int c2 = 1; c2 <= C; c2++) {
                if (c1 == c2) {
                    continue;
                }
                for (int c3 = 1; c3 <= C; c3++) {
                    if (c1 == c3 || c2 == c3) {
                        continue;
                    }

                    int tmp = 0;
                    for (int cOrg = 1; cOrg <= C; cOrg++) {
                        tmp += colorNums[cOrg][0] * D[cOrg][c1];
                        tmp += colorNums[cOrg][1] * D[cOrg][c2];
                        tmp += colorNums[cOrg][2] * D[cOrg][c3];
                    }
                    minDSum = Math.min(minDSum, tmp);
                }
            }
        }

        out.println(minDSum);
    }
}

Measured memory_bytes: 93392
q, h, s, d = gets.split.map(&:to_i)
n = gets.to_i
min_per_2l = [q * 8, h * 4, s * 2, d].min
div, mod = n.divmod(2)
price = min_per_2l * div
queue = [[price, mod]]
ans = []
until queue.empty?
  price, rest = queue.shift
  if rest <= 0
    ans << price if rest == 0
    next
  end
  queue << [price + q, rest - 0.25]
  queue << [price + h, rest - 0.5]
  queue << [price + s, rest - 1]
  queue << [price + d, rest - 2]
end
puts ans.min


Measured memory_bytes: 1788