akhauriyash/Code-Regression huggingface dataset:
import java.util.*;
public class Main {
   public static void main(String[] args) {  
      Scanner sc = new Scanner(System.in);
      
      int N = sc.nextInt();
      int M = sc.nextInt();
      
      HashMap<Integer, ArrayList<Integer>> h = new HashMap<Integer, ArrayList<Integer>>();
      HashMap<Integer, Integer> hm = new HashMap<Integer, Integer>();
      
      for(int i = 0; i < M; i++) {
         int P = sc.nextInt();
         int Y = sc.nextInt();
         
         if(!h.containsKey(P)) {
            h.put(P, new ArrayList<Integer>());
         }
         h.get(P).add(Y);
         hm.put(Y, i);
      }
      
      for(int key : h.keySet()) {
         Collections.sort(h.get(key));
      }
      
      String[] ans = new String[M];
      for(int key : h.keySet()) {
         String first = key+"";
         for(int i = 0; i < 6 - (key+"").length(); i++) {
            first = "0" + first;
         }
         for(int i = 0; i < h.get(key).size(); i++) {
            int ind = hm.get(h.get(key).get(i));
            String second = (i+1)+"";
            for(int j = 0; j < 6 - ((i+1)+"").length(); j++) {
               second = "0" + second;
            }
            ans[ind] = first + second;
         }
      }
      
      for(String an : ans) {
         System.out.println(an);
      }
   }
}

Measured memory_bytes: 178980
#include <stdio.h>
#include <math.h>

int main(void) {
	double xa1,ya1,xa2,ya2,xb1,yb1,xb2,yb2;
	int ok;
	while(1) {
		if(scanf("%lf %lf %lf %lf %lf %lf %lf %lf",
			&xa1,&ya1,&xa2,&ya2,&xb1,&yb1,&xb2,&yb2)==-1)break;
		ok=0;
		if(xb1<=xa1 && xa1<=xb2)ok|=1;
		if(xb1<=xa2 && xa2<=xb2)ok|=1;
		if(xa1<=xb1 && xb1<=xa2)ok|=1;
		if(xa1<=xb2 && xb2<=xa2)ok|=1;
		if(yb1<=ya1 && ya1<=yb2)ok|=2;
		if(yb1<=ya2 && ya2<=yb2)ok|=2;
		if(ya1<=yb1 && yb1<=ya2)ok|=2;
		if(ya1<=yb2 && yb2<=ya2)ok|=2;
		if(ok==3)printf("YES\n"); else printf("NO\n");
	}
	return 0;
}

Measured memory_bytes: 0
#include <stdio.h>

int main()
{
	int a, b, c;
	scanf("%d %d %d", &a, &b, &c);
	if (a <= c && b <= c) printf("%d\n", a + b);
	else if (a <= b && c <= b) printf("%d\n", a + c);
	else printf("%d\n", b + c);
	fflush(stdout);
	return 0;
}

Measured memory_bytes: 1712
#include <stdio.h>
#include <iostream>
#include <algorithm>
#define ll longlong
using namespace std;

int main(void){
    int a, b, c;
    cin >> a >> b >> c;
    if ((100*a + 10*b + c) % 4 == 0){
        cout << "YES";
    } else {
        cout << "NO";
    }
    cout << endl;

    return 0;
}


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

class Procon
{
    public Procon() { }
    static void Main(string[] agrs)
    {
        new Procon().Do();
    }

    Scanner cin;

    public void Do()
    {
        cin = new Scanner();
        int N = cin.nextInt();
        int X = cin.nextInt();
        int min = 1000000;
        int ans = 0;
        for (int i = 0; i < N; i++)
        {
            int tmp = cin.nextInt();
            min = Math.Min(tmp, min);
            X -= tmp;
            ans++;
        }

        ans += X / min;
        Console.WriteLine(ans);
    }
}

class Scanner
{
    string[] s;
    int i;
    int max_i;

    public Scanner()
    {
        s = new string[0];
        max_i = 0;
        i = 0;
    }

    public string nextString()
    {
        if (i >= s.Length)
        {
            s = Console.ReadLine().Split(' ');
            max_i = s.Length;
            i = 0;
            if (max_i == 0)
            {
                return "";
            }
            return s[i++];
        }
        else
        {
            return s[i++];
        }
    }

    public int nextInt()
    {
        return int.Parse(nextString());
    }


    public long nextLong()
    {
        return long.Parse(nextString());
    }

    public double nextDouble()
    {
        return double.Parse(nextString());
    }

    public string[] arrayString()
    {
        return Console.ReadLine().Split(' ');
    }

    public int[] arrayInt()
    {
        string[] str = Console.ReadLine().Split(' ');
        int[] array = new int[str.Length];
        for (int i = 0; i < str.Length; i++)
        {
            array[i] = int.Parse(str[i]);
        }
        return array;
    }

    public long[] arrayLong()
    {
        string[] str = Console.ReadLine().Split(' ');
        long[] array = new long[str.Length];
        for (int i = 0; i < str.Length; i++)
        {
            array[i] = long.Parse(str[i]);
        }
        return array;
    }

    public double[] arrayDouble()
    {
        string[] str = Console.ReadLine().Split(' ');
        double[] array = new double[str.Length];
        for (int i = 0; i < str.Length; i++)
        {
            array[i] = double.Parse(str[i]);
        }
        return array;
    }
}

Measured memory_bytes: 11092
#include<iostream>
#include<algorithm>
using lint=int64_t;
using namespace std;

int main()
{
	const int INF=2e9;

	int N;
	int Ma,Mb;
	int A[50]={};
	int B[50]={};
	int C[50]={};

	cin >> N;
	cin >> Ma >> Mb;
	for(int i=1;i<=N;i++)
		cin >> A[i] >> B[i] >> C[i];

	int dp[50][410][410]={};
	for(int i=0;i<50;i++)
		for(int a=0;a<=400;a++)
			for(int b=0;b<=400;b++)
				dp[i][a][b]=INF;
	dp[0][0][0]=0;

	for(int i=1;i<=N;i++)
	{
		for(int a=0;a<=400;a++)
		{
			for(int b=0;b<=400;b++)
			{
				dp[i][a][b]=dp[i-1][a][b];
				int pa=a-A[i];
				int pb=b-B[i];
				if(pa>=0 && pb>=0)
					dp[i][a][b]=min(dp[i][a][b],dp[i-1][pa][pb]+C[i]);
			}
		}
	}

	int ans=INF;
	for(int i=1;i*Ma<=400 && i*Mb<=400;i++)
		ans=min(ans,dp[N][i*Ma][i*Mb]);

	if(ans==INF)
		ans=-1;
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 33024
#include<bits/stdc++.h>
using namespace std;
 
map<long long, long long> prime_map;

long long  cal_gcd(long long A,long long B){
  if(B==0){return A;}
  return cal_gcd(B,A%B);
}
 
void prime_factor(long long bak){
	for(int i = 2; i*i <= bak; i++){
		while(bak % i == 0){
			prime_map[i]++;
			bak /= i;
		}
	}
	if(bak > 1){
		prime_map[bak]++;
	}
}

void prime_list(int64_t n){
  for(int64_t i=2;i*i<=n;++i){
    while(n%i==0){
      ++prime_map[i];
      n=n/i;
    }
  }
  if(n!=1){
    ++prime_map[n];
  }
}

 
int main(){
	long long  A, B;
	cin >> A >> B;
	long long gcd = cal_gcd(A, B);
	//prime_factor(gcd);
	prime_list(gcd);
 
	cout << prime_map.size() + 1 << endl;
}

Measured memory_bytes: 256
#include<stdio.h>

int main(){
	int a,b;
	while(scanf("%d", &a) != EOF){
		scanf("%d", &b);
		int res = a+b;
		int digit = 0;
		while(res != 0){
			digit++;
			res = (res - (res % 10)) / 10;
		}
		printf("%d\n", digit);
	}
	return 0;
}

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

#define REP(i,s,n) for(int i=s;i<n;++i)
#define rep(i,n) REP(i,0,n)
#define fst first
#define snd second
#define pb push_back
#define ALL(x) x.begin(),x.end()
#define EPS (1e-9)
#define equals(a,b) (fabs((a)-(b))<EPS)

using namespace std;

bool LT(double a,double b) { return !equals(a,b) && a < b; }
bool LTE(double a,double b) { return equals(a,b) || a < b; }

const string YES = "";
const string NO  = "";

typedef long long ll;

void solve() {

}

struct Data {
  int A,B;
  const bool operator < ( const Data &d ) const {
    if( B != d.B ) return B > d.B;
    return A < d.A;
  }
};

int main() {
  int n;
  cin >> n;
  int a,b;
  priority_queue<Data> Q;
  rep(i,n) {
    cin >> a >> b;
    Q.push((Data){a,b});
  }
  bool ok = true;
  int cur = 0;
  while( !Q.empty() ) {
    Data d = Q.top(); Q.pop();
    if( cur + d.A > d.B ) {
      ok = false;
      break;
    }
    cur += d.A;
  }
  puts(ok?"Yes":"No");
  return 0;
}


Measured memory_bytes: 2420
A, B, C = map(int, input().split())
min_v, med_v, max_v = sorted([A, B, C])
count = 0
i = 0
while i != 10:
    i += 1
    #print(max_v, med_v, min_v, count)
    if min_v == med_v and med_v == max_v:
        print(count)
        break
    elif min_v != med_v and med_v != max_v and max_v != min_v:
        count += max_v - med_v
        min_v += max_v - med_v
        med_v = max_v
    elif min_v == med_v:
        count += max_v - med_v
        min_v = max_v
        med_v = max_v
    elif med_v == max_v and max_v - min_v != 1:
        count += int((max_v - min_v) / 2)
        min_v += int((max_v - min_v) / 2) * 2
    else:
        count += 1
        min_v = max_v
        max_v += 1


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

#define int long long

#define ii pair<int,int>
#define fi first
#define sc second
#define lwb lower_bound
#define upb upper_bound
#define all(x) (x).begin(),(x).end()

signed main() {
#ifdef _DEBUG
  // freopen("in", "r", stdin);
#endif
  ios::sync_with_stdio(0); cin.tie(0);
  vector<int> cnt(11);
  for (int i = 0; i < 3; i++) {
    int t; cin >> t;
    cnt[t]++;
  }
  if (cnt[5] == 2 && cnt[7] == 1) cout << "YES" << '\n';
  else cout << "NO" << '\n';
}


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

using namespace std;

#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((int)((x).size()))

typedef pair<int, int> PII;
typedef vector<int> VI;
typedef long long int64;
typedef unsigned int uint;
typedef unsigned long long uint64;

#define gi(x) ((x) = F())
#define gii(x, y) (gi(x), gi(y))
#define giii(x, y, z) (gii(x, y), gi(z))

int F()
{
	char ch;
	int x, a;
	while (ch = getchar(), (ch < '0' || ch > '9') && ch != '-');
	if (ch == '-') ch = getchar(), a = -1;
	else a = 1;
	x = ch - '0';
	while (ch = getchar(), ch >= '0' && ch <= '9')
		x = (x << 1) + (x << 3) + ch - '0';
	return a * x;
}

const int mod = 1e9 + 7;

const int N = 2e5 + 10;

int n;

PII t[N];

int id[N];

int L[N], R[N];

VI q[N];

bool comp(const int &i, const int &j)
{
	return t[i].se < t[j].se;
}

int tr[N];

void add(int x, int v)
{
	++x;
	for (; x < N; x += x & -x) (tr[x] += v) %= mod;
}

int sum(int x)
{
	++x;
	int v = 0;
	for (; x; x -= x & -x) (v += tr[x]) %= mod;
	return v;
}

int query(int l, int r)
{
	return (sum(r) - sum(l - 1) + mod) % mod;
}

int main()
{
	gi(n);
	for (int i = 1; i <= n; ++i)
		gii(t[i].se, t[i].fi), id[i] = i;
	sort(t + 1, t + n + 1);
	sort(id + 1, id + n + 1, comp);
	int mi = n, mx = 0;
	for (int i = n; i; --i)
	{
		mi = min(mi, id[i]);
		L[i] = mi;
	}
	for (int i = 1; i <= n; ++i)
	{
		mx = max(mx, id[i]);
		R[i] = mx;
		q[R[i]].pb(L[i]);
		//cerr << L[i] << ", " << R[i] << endl;
	}
	add(0, 1);
	for (int r = 1; r <= n; ++r)
		for (auto l : q[r])
			add(r, query(l - 1, r));
	printf("%d\n", query(n, n));
	return 0;
}

Measured memory_bytes: 15872
#include "bits/stdc++.h"
#include<unordered_map>
#include<unordered_set>
#pragma warning(disable:4996)
using namespace std;
using ld = long double;
template<class T>
using Table = vector<vector<T>>;
const ld eps=1e-9;

//// < "D:\D_Download\Visual Studio 2015\Projects\programing_contest_c++\Debug\a.txt" > "D:\D_Download\Visual Studio 2015\Projects\programing_contest_c++\Debug\b.answer"

int main() {
	int A, B; cin >> A >> B;
	vector<int>as(A), bs(B);
	for (int i = 0; i < A; ++i) {
		cin >> as[i];
	}
	for (int i = 0; i < B; ++i) {
		cin >> bs[i];
	}
	int ans = 0;
	for (int f = 0; f < B; ++f) {
		int na = 0;
		int nans = 0;
		for (int nb = f; nb < B; ++nb) {
			bool ok = false;
			while (1) {
				if (na == A) {
					break;
				}else if (as[na] == bs[nb]) {
					na++;
					ok = true;
					break;
				}
				else {
					na++;
				}
			}
			if (!ok)break;
			else {
				nans += 1;
			}
		}
		ans = max(ans, nans);
		
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 3104
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Iterator;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		DequeOrder ord = new DequeOrder();
		try (Scanner sc = new Scanner(System.in)) {
			int q = sc.nextInt();
			for(int i = 0; i < q; i++) {
				int order_number = sc.nextInt();
				if(order_number == 0) {
					ord.push(sc.nextInt(), sc.nextInt());
				}else if(order_number == 1) {
					ord.randomAccess(sc.nextInt());
				}else if(order_number == 2) {
					ord.pop(sc.nextInt());
				}
			}
		}
	}
}
class DequeOrder {
	public Deque<Integer> array = new ArrayDeque<>();
	public void push(int d, int x){
		if(d == 0) {
			array.addFirst(x);
		}else if(d == 1) {
			array.addLast(x);
		}
	}
	public void randomAccess(int p) {
		Iterator<Integer> i = array.iterator();
		for(int j = 0; j < p; j++) {
			i.next();
		}
		System.out.println(i.next());
	}
	public void pop(int d) {
		if(d == 0) {
			array.removeFirst();
		}else if(d == 1) {
			array.removeLast();
		}
	}
	public Deque<Integer> getArray() {
		return array;
	}
}




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

struct UnionFind {
    vector<int> d;
    UnionFind(int n = 0) : d(n,-1) {}
    int find(int x) {
        if (d[x] < 0) return x;
        return d[x] = find(d[x]);
    }
    bool unite(int x, int y) {
        x = find(x); y = find(y);
        if (x == y) return false;
        if (d[x] > d[y]) swap(x,y);
        d[x] += d[y];
        d[y] = x;
        return true;
    }
    bool same(int x, int y) { return find(x) == find(y); }
    int size(int x) { return -d[find(x)]; }
};


int main() {
    int n, q;
    cin >> n >> q;
    UnionFind uf(n);
    for (int i = 0; i < q; ++i) {
        int t, x, y;
        cin >> t >> x >> y;
        if (t == 0) uf.unite(x, y);
        else cout << uf.same(x, y) << endl;
    }
}



Measured memory_bytes: 3136
#include <iostream>

using namespace std;

constexpr int nums[] {1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};

int main() {
  int K;
  cin >> K;
  cout << nums[K - 1] << endl;
  
  return 0;
}


Measured memory_bytes: 256
// OK that is my fault.
// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=900000+10;

const int mod=1e9+7;
inline int qpow(int a,int b) { int c=1;
    for (;b;b>>=1,a=1ll*a*a%mod) if (b&1) c=1ll*c*a%mod;
    return c;
}

int fac[N],ifac[N],pw[N];
inline void init(int n) {
    fac[0]=1;
    for (re int i=1;i<=n;++i) fac[i]=1ll*fac[i-1]*i%mod;
    ifac[n]=qpow(fac[n],mod-2);
    for (re int i=n;i;--i) ifac[i-1]=1ll*ifac[i]*i%mod;
    for (re int i=pw[0]=1;i<=n;++i) pw[i]=3ll*pw[i-1]%mod;
}

inline int C(int n,int m) {
    return 1ll*fac[n]*ifac[m]%mod*ifac[n-m]%mod;
}

int main() { init(900000);
    int n=read(),m=read(),k=read(); if (m<k) swap(m,k);
    int ans=0,lst=1;
    for (re int i=0;i<=m+k;++i) {
        ans=(ans+1ll*C(n+i-1,n-1)*pw[m+k-i]%mod*lst)%mod;
        if (i<k) lst=2ll*lst%mod;
        else if (i<m) lst=(2ll*lst+mod-C(i,k))%mod;
        else lst=(2ll*lst+mod-C(i,k)+mod-C(i,i-m))%mod;
    }
    printf("%d\n",ans);
    return 0;
}


Measured memory_bytes: 10752
#include<cstdio>

using int64=long long;
using uchar=unsigned char;

constexpr int maxn(3000);

// inline int io(){
// 	static int _;
// 	return scanf("%d",&_),_;
// }

namespace IOManager{
	constexpr int FILESZ(131072);
	char buf[FILESZ];
	const char*ibuf=buf,*tbuf=buf;

	struct IOManager{
		inline char gc()
			{return(ibuf==tbuf)&&(tbuf=(ibuf=buf)+fread(buf,1,FILESZ,stdin),ibuf==tbuf)?EOF:*ibuf++;}

		template<class _Tp>
			inline operator _Tp(){
				_Tp s=0u;char c=gc();
				for(;c<48;c=gc());
				for(;c>47;c=gc())
					s=(_Tp)(s*10u+c-48u);
				return s;
			}
	};
}IOManager::IOManager io;

int cnt[10];

int main(){
	++cnt[(int)io];
	++cnt[(int)io];
	++cnt[(int)io];
	++cnt[(int)io];

	puts(cnt[1]==1&&cnt[9]==1&&cnt[7]==1&&cnt[4]==1?"YES":"NO");

	return 0;
}


Measured memory_bytes: 128
ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))

n=ni()
x=nl()

sx = sorted(x)[::-1]

c = n//2

for i in range(n):
  if x[i] > sx[c]:
    print(sx[c])
  else:
    print(sx[c-1])


Measured memory_bytes: 95292
/* 
シーザー暗号文の解読
cout << str[i] + 1;
とすると文字が出力されないので注意。配列を書き換えて文字コードをずらす。
*/

#include <iostream>
#include <cstring>
using namespace std;

int main(void) {
    string str;
    int size;
    int f = string::npos;
    
    while(getline(cin, str)) {
        size = str.size();
        while(str.find("the") == f && str.find("this") == f && str.find("that") == f) {
            for(int i = 0; i < size; ++i) {
                if('a' <= str[i] && str[i] < 'z') {
                    str[i]++;
                } else if(str[i] == 'z') {
                    str[i] = 'a';
                }
            }
        }
        cout << str << endl;
    }
}


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

#define PI 3.1415926535897932
#define MOD 1000000007
#define INF 1e9

#define REP(i, n) for(int i = 0; i < (n); i++)
#define REP1(i, n) for(int i = 1; i <= (n); i++)
#define FOR(i, start, end) for(int i = (start); i < (end); i++)
#define ALL(v) (v).begin(), (v).end()

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vi> vvi;
typedef vector<string> vs;
typedef vector<bool> vb;


vb prime;
bool isPrime(int n)
{
    return prime[n];
}
bool like2017(int n)
{
    if(n % 2 == 0) return false;
    return isPrime(n) && isPrime((n+1)/2);
}

void solve()
{
    prime = vb(100001, true);
    prime[0] = prime[1] = false;
    for(int i = 2; i * i <= 100000; i++)
    {
        if(prime[i])
        {
            for(int j = 2 * i; j <= 100000; j += i) prime[j] = false;
        }
    }

    vi num2017(100001, 0);
    int count = 0;
    for(int i = 3; i <= 100000; i++)
    {
        if(like2017(i)) count++;
        num2017[i] = count;
    }

    int Q; cin >> Q;
    vector<pii> lr(Q);
    REP(i, Q) cin >> lr[i].first >> lr[i].second;

    REP(i, Q)
    {
        int l = lr[i].first;
        int r = lr[i].second;

        cout << num2017[r] - num2017[l-1] << endl;
    }
}

int main()
{
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(20);

    solve();

    return 0;
}

Measured memory_bytes: 1792
#include<bits/stdc++.h>
#define REP(i, n) for(int i=0; i<(int)(n); i++)
#define RREP(i, n) for(int i=0; i>(int)(n); i--)
#define ALL(v) v.begin(), v.end()
#define INF 2e9
typedef long long ll;
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(a>b){a=b; return 1;}return 0;}

using namespace std;

int a[1000][1000];
ll dp[1000][1000];
ll radix = (ll)1e9+7;

int main(void)
{
	int H, W;
	cin >> H >> W;
	REP(i, H){
		REP(k, W){
			char x;
			cin >> x;
			if(x == '.'){
				a[i][k] = 1;
			}else{
				a[i][k] = 0;
			}
		}
	}
	dp[0][0] = 1;
	REP(i,W-1){
		dp[0][i+1] = dp[0][i] & a[0][i+1];
	}
	REP(i, H-1){
		dp[i+1][0] = dp[i][0] & a[i+1][0];
	}

	REP(i, H-1){
		REP(k, W-1){
			if(a[i+1][k+1]==0){
				dp[i+1][k+1] = 0;
			}else{
				dp[i+1][k+1] = (dp[i+1][k] + dp[i][k+1])%radix;
			}
		}
	}
	cout << dp[H-1][W-1] << "\n";
	return 0;
}


Measured memory_bytes: 11904
import std;
import core.bitop;

ulong MAX = 100_100, MOD = 1_000_000_007, INF = 1_000_000_000_000;
alias sread = () => readln.chomp();
alias lread(T = long) = () => readln.chomp.to!(T);
alias aryread(T = long) = () => readln.split.to!(T[]);
alias Pair = Tuple!(long, "x", long, "y");
alias PQueue(T, alias less = "a>b") = BinaryHeap!(Array!T, less);

void main()
{
    long h, w;
    scan(h, w);
    auto s = new string[](h);
    foreach (ref e; s)
    {
        e = sread();
    }
    auto costs = new long[][](h, w);
    costs.each!(x => x[] = INF);

    void bfs()
    {
        bool intoBlack(Pair from, Pair to)
        {
            return s[from.x][from.y] == '.' && s[to.x][to.y] == '#';
        }

        auto q = DList!(Pair)(Pair(0, 0));
        auto flag = new bool[][](h, w);
        flag[0][0] = true;
        costs[0][0] = s[0][0] == '#' ? 1 : 0;
        while (!q.empty())
        {
            auto p = q.front();
            q.removeFront();

            costs[p.x][p.y] = min(costs[p.x > 0 ? p.x - 1 : p.x][p.y] + intoBlack(Pair(p.x > 0
                    ? p.x - 1 : p.x, p.y), p), costs[p.x][p.y > 0
                    ? p.y - 1 : p.y] + intoBlack(Pair(p.x, p.y > 0 ? p.y - 1 : p.y), p));

            if (p.x + 1 < h && !flag[p.x + 1][p.y])
            {
                q.insertBack(Pair(p.x + 1, p.y));
                flag[p.x + 1][p.y] = true;
            }
            if (p.y + 1 < w && !flag[p.x][p.y + 1])
            {
                q.insertBack(Pair(p.x, p.y + 1));
                flag[p.x][p.y + 1] = true;
            }
        }
    }

    bfs();
    // costs.each!(x => x.writeln());
    writeln(costs[h - 1][w - 1]);
}

void scan(TList...)(ref TList Args)
{
    auto line = readln.split();
    foreach (i, T; TList)
    {
        T val = line[i].to!(T);
        Args[i] = val;
    }
}


Measured memory_bytes: 3880
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <deque>
#include <list>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>

using namespace std;

//typedef
typedef long long LL;
typedef vector<LL> VL;
typedef vector<VL> VVL;
typedef vector<string> VS;
typedef pair<LL, LL> PLL;

//conversion
inline LL toLong(string s) {LL v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}

//math
//-------------------------------------------
template<class T> inline T sqr(T x) {return x*x;}

//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) LL((a).size())
#define EACH(i,c) for(auto i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())

//repetition
#define FOR(i,a,b) for(LL i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define UNTIL(p) while(!(p))

//constant
const double EPS = 1e-5;
const double PI  = acos(-1.0);

//debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

#define PUTS(x) cout << (x) << endl;

int main(void){
    cin.tie(0);
    ios::sync_with_stdio(false);
    LL n,k;
    cin>>n>>k;
    VL a(n);
    REP(i,n)cin>>a[i];
    REP(i,n)a[i]--;
    LL now = 0;
    LL loop_st = 0;
    LL cnt = 0;
    VL visited(n,0);
    REP(i,n+1){
        if(visited[now]){
            loop_st = now;
            break;
        }
        visited[now] = 1;
        now = a[now];
        cnt++;
    }

    now = 0;
    LL loop_pre_cnt = 0;
    REP(i,n+1){
        if(now == loop_st){
            break;
        }
        now = a[now];
        loop_pre_cnt++;
    }

    now = 0;
    if(k >= loop_pre_cnt){
        k -= loop_pre_cnt;
        LL loop_cnt = cnt - loop_pre_cnt;
        k = k % loop_cnt;
        now = loop_st;
    }

    REP(i,k){
        now = a[now];
    }
    PUTS(now + 1);
}

Measured memory_bytes: 6352
#include <bits/stdc++.h>
using namespace std;
//型名省略
typedef long long ll;
typedef vector<long long> vl;
typedef vector<vector<long long>> vvl;
typedef vector<char> vc;
typedef vector<vector<char>> vvc;
typedef vector<string> vs;
//定数
const ll MOD = 1e9+7;
//マクロ
#define rep(i,n) for(ll i = 0; i < (ll) n; i++)
#define rep2(i,x,n) for(ll i = (ll) x; i < (ll) n; i++)
#define all(A) A.begin(), A.end()
//正誤判定
void Yes(bool ans){cout << (ans? "Yes" : "No") << endl;}
void YES(bool ans){cout << (ans? "YES" : "NO") << endl;}


//main関数
int main() {
    ll h,w,m; cin >> h >> w >> m;
    vector<pair<ll,ll>> obj(m);
    vl row(h,0),col(w,0); //各行、列の爆破対象の個数
    rep(i,m) {
        cin >> obj[i].first >> obj[i].second;
        obj[i].first--;
        obj[i].second--;
        row[obj[i].first]++;
        col[obj[i].second]++;
    }

    ll mrow = 0, mcol = 0; //爆破対象数が最大である行、列の爆破対象数
    vl mrowIndex = {}, mcolIndex = {}; //↑のインデックス
    rep(i,h){
        if(mrow < row[i]) {
            mrow = row[i];
            mrowIndex = {i};
        }
        else if(mrow == row[i]) {
            mrowIndex.push_back(i);
        }
    }
    rep(i,w){
        if(mcol < col[i]) {
            mcol = col[i];
            mcolIndex = {i};
        }
        else if(mcol == col[i]) {
            mcolIndex.push_back(i);
        }
    }

    ll mrs = mrowIndex.size();
    ll mcs = mcolIndex.size();
    // // 確認
    // rep(i,mrs) cout << "mrowIndex[" << i <<"]: " << mrowIndex[i] << endl;
    // rep(i,mcs) cout << "mcolIndex[" << i <<"]: " << mcolIndex[i] << endl;

    ll maxcount = 0; //重なる点の個数
    rep(i,m){
        if(row[obj[i].first] == mrow && col[obj[i].second] == mcol){
            maxcount++;
        }
    }
    if(maxcount == mrs * mcs) {
        cout << mrow + mcol - 1 << endl;
    }
    else {
        cout << mrow + mcol << endl;
    }
}

Measured memory_bytes: 20948
#include <bits/stdc++.h>
#include <algorithm>
#include <limits>
#include <stdlib.h> 
using namespace std;


 
int main(){
    int N,M;
    cin>>N>>M;
    int A[M+1];
    for(int i=0;i<=M;i++)A[i]=0;
    for(int i=0;i<N;i++){
        int K;
        cin>>K;
        for(int j=0;j<K;j++){
            int a;
            cin>>a;
            A[a]++;
        }
    }
    int ans=0;
    for(int i=0;i<=M;i++){
        if(A[i]==N)ans++;
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
#define pi 3.14159265359
#define all(i) i.begin(),i.end()
using namespace std;
const long long INF=1e9+7;
const string alp="abcdefghijklmnopqrstuvwxyz"; //26
const string ALP="ABCDEFGHIJKLMNOPQRSTUVWXYZ";
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef pair<ll,ll> P;
typedef tuple<ll,ll,ll> T;
//const ll MOD=998244353LL;
//const ll MOD=1777777777LL;


int main() {
  ll N;
  cin>>N;
  vl a(N);
  ll sum=0;
  rep(i,N){
    cin>>a[i];
    sum+=a[i];
  }
  sort(all(a));
  sum-=a[N-1];
  if(a[N-1]<sum) cout<<"Yes"<<endl;
  else cout<<"No"<<endl;
}

Measured memory_bytes: 3644
#include<iomanip>
#include<limits>
#include<thread>
#include<utility>
#include<iostream>
#include<string>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<stack>
#include<queue>
#include<cmath>
#include<numeric>
#include<cassert>
#include<random>
#include<chrono>
#include<unordered_map>
#include<fstream>
#include<list>
#include<functional>
#include<bitset>
#include<complex>
using namespace std;
typedef unsigned long long int ull;
typedef long long int ll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pi;
typedef pair<double,double> pd;
typedef pair<double,ll> pdl;
#define F first
#define S second
const ll E=1e18+7;
const ll MOD=1000000007;





int main(){
    ll h,w,n;
    cin>>h>>w>>n;
    swap(h,w);
    vector<vector<ll>> A(h);
    set<pll> S;
    for(int i=0;i<n;i++){
        ll x,y;
        cin>>x>>y;
        x--; y--;
        A[y].push_back(x);
        S.insert({x,y});
    }
    for(int i=0;i<h;i++){
        sort(A[i].begin(),A[i].end());
        A[i].push_back(w);
    }
    pll W={0,0};
    ll count=0;
    ll ans=E;
    while(1){
        if(W.F+1>=w || S.count({W.F+1,W.S})){ans=min(ans,count+2); break;}
        W.F++;
        count++;
        auto I=upper_bound(A[W.S].begin(),A[W.S].end(),W.F);
        ans=min(ans,count+((*I)-W.F)*2+1);
        if(W.S+1>=h){
            break;
        }
        count++;
        if(S.count({W.F,W.S+1})==0){W.S++;}
    }
    cout<<ans/2<<endl;
    
    
    
    return 0;
}


Measured memory_bytes: 24704
#include <bits/stdc++.h>
 
using namespace std;
#define fr(i,a,b) for (long long int i = (a), _b = (b); i <= _b; i++)
// #define frr(i,a,b) for (int i = (a), _b = (b); i >= _b; i--)
 
// #define repr(i,n) for (long long i = (n) - 1; i >= 0; i--)
// #define foreach(it,ar) for ( typeof(ar.begin()) it = ar.begin(); it != ar.end(); it++ )
// #define fill(ar,val) memset(ar, val, sizeof(ar))
// #define fill0(ar) fill((ar), 0)
// #define fillinf(ar, n) fr(i,0,(n)) ar[i] = INF
// #define debug(x) cout<<#x<<": "<<x<<endl
// #define arr1d(a,n) cout << #a << " : "; fr(,1,n) cout << a[] << ' '; cout << endl;
// #define arr1d0(a,n) cout << #a << " : "; rep(,n) cout << a[] << ' '; cout << endl;
// #define arr2d(a,n,m) cout << #a << " :" << endl; fr(,1,n) {fr(,1,m) cout << a[][__] << ' '; cout << endl;}
// #define arr2d0(a,n,m) cout << #a << " :" << endl; rep(,n) {rep(,m) cout << a[][__] << ' '; cout << endl;}
// #define ull unsigned long long
// #define ll long long int
// #define ld double
// #define ui unsigned int
// #define all(ar) ar.begin(), ar.end()
// #define pb push_back
// #define mp make_pair
// #define ff first
// #define ss second
 
 
// #define PI 3.1415926535897932385
// #define INF 1000111222
// #define EPS 1e-7
// #define MAXN 1000001
// #define MOD 998244353
 
 
//  #include<iostream>
//      #include<vector>
// #include <stdio.h>
// #include<algorithm>
// #include<math.h>
// #include <iomanip>  
// #include <algorithm> 
// #include<bits/stdc++.h>
// #include <iterator>
// using std::string;
// //#include <boost/algorithm/string.hpp> 
#include<bits/stdc++.h>
#include<ratio>
#include <set> 
#include <iterator>
using namespace std;
#define ll long long
#define VV vector
#define pb push_back
#define bitc  __builtin_popcountl
#define m_p make_pair
#define inf 200000000000000
#define MAXN 1000001
#define eps 0.0000000001
#define prime 1000000007
#define ll long long
using namespace std;
#define S second
#define F first
ll MOD=1e9+7;
#define rep(i,n) for (long long i = 0, _n = (n); i < _n; i++)
long long StringToInteger(string NumberAsString)
{
  long long NumberAsInteger;
  stringstream ss;
  ss << NumberAsString;
  ss >> NumberAsInteger;
  return NumberAsInteger;
}
 int32_t main()
{   
        int n;
        cin>>n;
        int k;
        cin>>k;
        // cout<<k;
        vector<int> hs(n);
        for(int i=0;i<n;i++)
        {
            cin>>hs[i];  
        }
        VV<int> mini(n);
        mini[0]=0;
        mini[1]=abs(hs[1]-hs[0]);
        // cout<<mini[1];
        for(int i=2;i<n;i++)
        {
            int var=MOD;
            for(int j=1;(j<=k)&&(i>=j);j++){
                int temp=mini[i-j]+abs(hs[i]-hs[i-j]);
                var=min(temp,var);
            }
            mini[i]=var;
            // cout<<mini[i]<<" ";
        }
        cout<<mini[n-1];
    return 0;
}

Measured memory_bytes: 1024
import scala.annotation.tailrec

object Main extends App {
  import scala.collection.mutable
  import scala.io.StdIn._

  val n = readInt
  val words = Array.tabulate(n){_ ⇒ readLine.trim}
  println(minLength(words))

  def minLength(words: Array[String]): Int = {
    @tailrec
    def sub(current: Int = 0, prevLength: Int = 0, minWithChar: IndexedSeq[Int] = mutable.IndexedSeq.tabulate(26){_ ⇒ -1}): Int = {
      if (current == words.length) prevLength
      else {
        if (minWithChar(words(current).head - 'a') != -1) {
          val minLen: Int = math.min(prevLength + 1, minWithChar(words(current).head - 'a'))
          sub(current + 1, minLen, minWithChar.updated(words(current).head - 'a', minLen))
        }else {
          sub(current + 1, prevLength + 1, minWithChar.updated(words(current).head - 'a', prevLength + 1))
        }
      }
    }
    sub()
  }
  implicit class Scope[T](val value: T) extends AnyVal {
    @inline def also(@inline func: T ⇒ Unit): T = {
      func(value)
      value
    }
    @inline def let[A](@inline func: T ⇒ A): A = func(value)
  }
}


Measured memory_bytes: 131144
// E - Who Says a Pun?

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
// const int INF = 2147483647;
// const ll INF = 9223372036854775807;
// const ll MOD = 1e9 + 7;

int dp[5000][5000];

int main() {
	int N;
	string S;

	cin >> N;
	cin >> S;

	for (int i=S.size()-1; i>=0; i--) {
		for (int j=S.size()-1; j>=0; j--) {
			if (S[i] ==S[j]) {
				dp[i][j]++;
				if (i != 0 && j != 0) {
					dp[i-1][j-1] += dp[i][j];
				}
			}
		}
	}

	int ans = 0;
	for (int i=0; i < S.size(); i++) {
		for (int j=i; j < S.size(); j++) {
			if (i + dp[i][j] <= j) {
				ans = max(ans, dp[i][j]);
			}
		}
	}

	cout << ans << endl;

	/*
	// **** debug ****
	for (int i=0; i < S.size(); i++) {
		for (int j=0; j < S.size(); j++) {
			cout << dp[i][j] << " ";
		}
		cout << endl;
	}
	*/

	return 0;
}

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

typedef long long LL;
int Mod;
const int MN = 105, MK = 105;

int Binom[MN][MN], Pow[MK][MN];
int N, M, K;
int f[2][MN][MN];

int main() {
	scanf("%d%d%d%d", &N, &M, &K, &Mod);
	for (int i = 0; i <= std::max(N, M); ++i) {
		Binom[i][0] = 1;
		for (int j = 1; j <= i; ++j)
			Binom[i][j] = (Binom[i - 1][j - 1] + Binom[i - 1][j]) % Mod;
	}
	for (int i = 0; i <= K; ++i) {
		Pow[i][0] = 1;
		for (int j = 1; j <= std::max(N, M); ++j)
			Pow[i][j] = (LL)Pow[i][j - 1] * i % Mod;
	}
	int o = 0;
	f[0][0][0] = 1;
#define Z0(x) for (int i = 0; i <= N; ++i) for (int j = 0; j <= M; ++j) f[x][i][j] = 0;
	for (int t = 1; t <= K; ++t) {
		Z0(o ^ 1);
		for (int i = 0; i <= N; ++i) for (int j = 0; j <= M; ++j) if (f[o][i][j]) {
			int x = f[o][i][j], y = (LL)Pow[K - t + 1][j] * Pow[t][M - j] % Mod;
			for (int a = 0; i + a <= N; ++a, x = (LL)x * y % Mod)
				f[o ^ 1][i + a][j] = (f[o ^ 1][i + a][j] + (LL)Binom[N - i][a] * x) % Mod;
		} o ^= 1;
		Z0(o ^ 1);
		for (int i = 0; i <= N; ++i) for (int j = 0; j <= M; ++j) if (f[o][i][j]) {
			int x = f[o][i][j], y = (LL)Pow[K - t + 1][i] * Pow[t][N - i] % Mod;
			for (int b = 0; j + b <= M; ++b, x = (LL)x * y % Mod)
				f[o ^ 1][i][j + b] = (f[o ^ 1][i][j + b] + (LL)Binom[M - j][b] * x) % Mod;
		} o ^= 1;
		Z0(o ^ 1);
		for (int i = 0; i <= N; ++i) for (int j = 0; j <= M; ++j) if (f[o][i][j]) {
			int x = f[o][i][j], y = (LL)(Mod - Pow[K - t][j]) * Pow[t][M - j] % Mod;
			for (int c = 0; i + c <= N; ++c, x = (LL)x * y % Mod)
				f[o ^ 1][i + c][j] = (f[o ^ 1][i + c][j] + (LL)Binom[N - i][c] * x) % Mod;
		} o ^= 1;
		Z0(o ^ 1);
		for (int i = 0; i <= N; ++i) for (int j = 0; j <= M; ++j) if (f[o][i][j]) {
			int x = f[o][i][j], y = (LL)(Mod - Pow[K - t][i]) * Pow[t][N - i] % Mod;
			for (int d = 0; j + d <= M; ++d, x = (LL)x * y % Mod)
				f[o ^ 1][i][j + d] = (f[o ^ 1][i][j + d] + (LL)Binom[M - j][d] * x) % Mod;
		} o ^= 1;
	}
	printf("%d\n", f[o][N][M]);
	return 0;
}

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

inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}

typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<long long> VL;
typedef vector<vector<long long>> VVL;
typedef vector<string> VS;
typedef pair<int, int> P;
typedef tuple<int,int,int> tpl;

#define ALL(a)  (a).begin(),(a).end()
#define SORT(c) sort((c).begin(),(c).end())
#define REVERSE(c) reverse((c).begin(),(c).end())
#define EXIST(m,v) (m).find((v)) != (m).end()
#define LB(a,x) lower_bound((a).begin(), (a).end(), x) - (a).begin()
#define UB(a,x) upper_bound((a).begin(), (a).end(), x) - (a).begin()

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

#define en "\n"

constexpr double EPS = 1e-9;
constexpr double PI  = 3.1415926535897932;
constexpr int INF = 2147483647;
constexpr long long LINF = 1LL<<60;
constexpr long long MOD = 1000000007; // 998244353;

#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

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

void Main(){
    int r;
    cin >> r;
    cout << 2 * PI * r << en;
    return;
}

int main(void){
    cin.tie(0);cout.tie(0);ios_base::sync_with_stdio(0);cout<<fixed<<setprecision(15);
    int t=1; //cin>>t;
    REP(_,t) Main();
    return 0;
}


Measured memory_bytes: 3780
# ABC049 C - 白昼夢 / Daydream
S = input()
S = S.replace('dream','A').replace('erase','B')
S = S.replace('Aer','C').replace('Br','D')

E = set()

for s in S:
    E.add(s)

ans = 'YES'
for e in E:
    if not e in ('A','B','C','D'):
        ans = 'NO'
        break
print(ans)

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

#define REP(i, n) for (int i = 0; i < (int)(n); ++i)
#define FOR(i, k, n) for (int i = (k); i < (int)(n); ++i)
typedef long long int ll;

using namespace std;

ll f(ll n) {
  if (n % 2 == 0) {
    if (n % 4 == 0)
      return n;
    else
      return n ^ 1;
  } else {
    if ((n + 1) % 4 == 0)
      return 0;
    else
      return 1;
  }
}

int main() {
  ll A, B;
  cin >> A >> B;
  cout << (f(A - 1) ^ f(B)) << endl;
}

Measured memory_bytes: 256
n=int(input())
s=input()
a=n*(n-1)*(n-2)//6
r=s.count("R")
g=s.count("G")
b=s.count("B")
ra=r*(r-1)*(r-2)//6+(r*(r-1)//2)*(n-r)
ga=g*(g-1)*(g-2)//6+(g*(g-1)//2)*(n-g)
ba=b*(b-1)*(b-2)//6+(b*(b-1)//2)*(n-b)
sum=0
for i in range((n-3)//2+1):
	#print(i)
	for j in range(n-(2*i+3)+1):
		#print(s[j],s[j+i+1],s[j+2*(i+1)] )
		if not (s[j]==s[j+i+1] or s[j]==s[j+2*(i+1)] or s[j+i+1]==s[j+2*(i+1)] ):
			sum+=1
#print(r,g,b,ra,ga,ba,sum,a)
print(a-(ra+ga+ba)-sum)

Measured memory_bytes: 9260
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int k = sc.nextInt();
		int x = sc.nextInt();
		int ans[] = new int[2*k-1];
		int index=0;
		for(int i = k-1; i>0;i--) {
			ans[index]=x-i;
			index++;
		}
		for(int i = 0; i < k; i++) {
			ans[index]=x+i;
			index++;
		}
		for(int i = 0; i<ans.length;i++) {
			System.out.print(ans[i]+" ");
		}


	}

}

Measured memory_bytes: 21844
using namespace std;

using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
#include <iostream>
#include <string>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cmath>
#include <climits>
#include <bitset>
#include <array>
#include <deque>
#include <queue>
#include <map>
#define all(x) (x).begin(),(x).end()

void solve(){

}
int main(){
    int N;
    cin >> N;
    if (N <= 999){
        cout << "ABC" << endl;
    } else {
        cout << "ABD" << endl;
    }

    return 0;
}


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

#define INF (1<<29)

struct segtree{

  //テヲツ慊?・ツーツ湘・ツ?、テ」ツつ津ヲツアツづ」ツつ?」ツつ凝ァツ板ィ
  vector<int> datamin;
  //テゥツ??・ツサツカテァツ板ィ
  vector<int> delay;
  int n;

  //テ・ツ按敕ヲツ慊淌・ツ個?
  void init(int _n){
    n = 1;
    while( n < _n ) n*=2;
    datamin.resize( 2 * n );
    delay.resize( 2 * n );
  }

  //テァツーツ。テヲツ伉禿ァツ可暗ッツシツ暗ァツキツ湘・ツ陳古」ツ?ォテ・ツッツセテ」ツ?凖」ツつ凝・ツ?ヲテァツ青?ァツ?。テ」ツ?預nd0テ・ツ按敕ヲツ慊淌・ツ個姪ァツ?。テ」ツ?要er)
  void delaycalc(int k){
    datamin[k] = datamin[k]+delay[k];
    if( k+1 < n )
      for(int i=1;i<=2;i++)
        delay[2*k+i] = delay[2*k+i]+delay[k];
    delay[k] = 0;
  }
  

  //テ・ツ個コテゥツ鳴禿」ツ??a,b)テ」ツ??」ツ?ォテ、ツクツ?ヲツァツ佚」ツ?ォテ」ツ??テ」ツ??」ツつ津ィツカツウテ」ツ??
  void add(int a,int b,int x,int k,int l,int r){
    delaycalc(k);
    if( r<=a || b<=l ) return;
    else if( a<=l && r<=b ){
      delay[k] = x;
      delaycalc(k);
    } else {
      add( a, b, x, 2*k + 1, l, (l+r)/2 );
      add( a, b, x, 2*k + 2, (l+r)/2, r );
      datamin[k] = min( datamin[2*k+1], datamin[2*k+2] );
    }
  }

  //テ」ツ?づ」ツつ凝・ツ個コテゥツ鳴禿」ツ?ョテヲツ慊?・ツーツ湘・ツ?、テ」ツつ津ヲツアツづ」ツつ?」ツつ?
  int querymin(int a,int b,int k,int l,int r){
    delaycalc(k);
    if( r<=a || b<=l ) return INF;
    if( a<=l && r<=b ){
      return datamin[k]+delay[k];
    } else {
      int vl = querymin( a, b, 2*k+1, l,(l+r)/2 );
      int vr = querymin( a, b, 2*k+2, (l+r)/2,r );
      return min(vl,vr);
    }
  }


  void add( int a,int b,int x){ add( a, b, x, 0,0,n); }//テ・ツ環?」ツ?暗」ツつ?
  int querymin(int a,int b){ return querymin(a,b,0,0,n); }//テヲツ慊?・ツーツ湘・ツ?、テ・ツ渉姪・ツセツ?
};

int N,Q;
string str;
segtree S;
int main(){
  cin >> N >> Q;
  cin >> str;
  S.init(N);
  int cnt = 0;
  for(int i=0;i<N;i++){
    if( str[i] == '(' ) cnt++;
    else cnt--;
    S.add(i,i+1,cnt);
  }

  for(int i=0;i<Q;i++){
    int id; cin >> id; --id;
   
    if( str[id] == ')' ){
      str[id] = '(';
      S.add(id,id+N,2);

      int st = 0,ed = id;
      int res = id;
      while( st <= ed ){
        int h = (st + ed)/2;
        int mini = S.querymin(h,id+1);
        if( mini >= 2 ){
          ed = h-1; res = min( res, h );
        }
        else st = h+1;
      }
      str[res]  = ')';
      cout << res+1 << endl;
      S.add(res,id+N,-2);
    } else {// ( -> )
      str[id] = ')';
      S.add(id,id+N,-2);

      int st = 0,ed = id;
      int res = id;
      while( st <= ed ){
        int h = (st + ed)/2;
        int mini = S.querymin(h,h+1);       
        if( h+1 == mini) st = h + 1;
        else{
          ed = h-1; res = min( res, h );
        }
      }
      str[res]  = '(';
      cout << res+1 << endl;
      S.add(res,id+N,2);
      
    }    
  
  }

}

Measured memory_bytes: 9596
///
// File:  c.go
// Author: ymiyamoto
//
// Created on Sun Jan 28 21:05:02 2018
//
package main

import (
	"fmt"
)

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

func main() {
	var N int
	fmt.Scan(&N)

	upper := make([]int, N)
	lower := make([]int, N)

	for i := range upper {
		fmt.Scan(&upper[i])

	}

	for i := range lower {
		fmt.Scan(&lower[i])
	}

	for i := 0; i < len(upper)-1; i++ {
		upper[i+1] += upper[i]
		lower[i+1] += lower[i]
	}

	count := 0
	for i := 0; i < len(upper); i++ {
		if i > 0 {
			count = max(count, upper[i]+lower[len(lower)-1]-lower[i-1])
		} else {
			count = max(count, upper[0]+lower[len(lower)-1])
		}
	}

	fmt.Println(count)
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
#define N 101
using namespace std;
int h,w,A;
string mp[101];
int dx[]={0,0,1,-1};//V^><
int dy[]={1,-1,0,0};

int ans=1e9,used[101][101][11][11][4];
void dfs(int x,int y,int p,int q,int dir){
  if(ans<=2*A-(p+q)||used[x][y][p][q][dir]++)return;
  vector<int> X,Y,ch;
  while(1){
    x+=dx[dir];
    y+=dy[dir];
    if(x<0||y<0||x>=w||y>=h||mp[y][x]=='#')break;
    if(mp[y][x]=='S')continue;
    if(mp[y][x]=='G')ans=min(ans,2*A-(p+q));
    X.push_back(x);
    Y.push_back(y);
    ch.push_back(mp[y][x]);
    mp[y][x]='#';
    if(p){
      if(dir==0)dfs(x,y,p-1,q,2); //>
      if(dir==1)dfs(x,y,p-1,q,3); //<
      if(dir==2)dfs(x,y,p-1,q,0); //V
      if(dir==3)dfs(x,y,p-1,q,1); //^
    }
    if(q){
      if(dir==0)dfs(x,y,p,q-1,3); //>
      if(dir==1)dfs(x,y,p,q-1,2); //<
      if(dir==2)dfs(x,y,p,q-1,1); //^
      if(dir==3)dfs(x,y,p,q-1,0); //V
    }
  }
  for(int i=0;i<X.size();i++)mp[Y[i]][X[i]]=ch[i];
}

int main(){
  cin>>h>>w>>A;
  for(int i=0;i<h;i++)cin>>mp[i];
  for(int i=0;i<h;i++)
    for(int j=0;j<w;j++)
      if(mp[i][j]=='S')dfs(j,i,A,A,0);

  cout<<(ans==1e9? -1:ans)<<endl;
  return 0;
}

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

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))

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

typedef long long ll;

void solve(long long A, long long B, long long K)
{
    if (A - K < 0)
    {
        K = K - A;
        if (B - K < 0)
        {
            cout << "0 0" << endl;
        }
        else
        {
            cout << "0 " << B - K << endl;
        }
    }
    else
    {
        cout << A - K << " " << B << endl;
    }
}

int main()
{
    long long A;
    scanf("%lld", &A);
    long long B;
    scanf("%lld", &B);
    long long K;
    scanf("%lld", &K);
    solve(A, B, K);
    return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
int ta[10010],to[60010],nt[60010];
int id[10010],rid[10010],cmp[100010],r=0,f[10010]={0};
void sdfs(int e,int s,int k){
  int i;
  f[s]++;
  if(k>=0)cmp[s]=k;
  for(i=ta[s];i+1;i=nt[i]){
    if(i<e&&k<0&&f[to[i]]==0||i>=e&&k>=0&&f[to[i]]==1)sdfs(e,to[i],k);
  }
  if(k<0)id[rid[s]=r++]=s;
}
void scc(int v,int e,int *a,int *b){
  int i,k;
  for(i=0;i<v;i++)ta[i]=-1;
  for(i=0;i<e;i++){
    nt[i  ]=ta[to[i+e]=a[i]];
    nt[i+e]=ta[to[i  ]=b[i]];
    ta[a[i]]=i;
    ta[b[i]]=i+e;
  }
  for(i=k=0;i<v;i++){
    if(f[i]==0)sdfs(e,i,-1);
  }
  for(i=r;i;i--){
    if(f[id[i-1]]==1)sdfs(e,id[i-1],id[i-1]);
  }
}
int main(){
  int v,e,a[100010],b[100010],s,t,i;
  scanf("%d %d",&v,&e);
  for(i=0;i<e;i++)scanf("%d %d",&a[i],&b[i]);
  scc(v,e,a,b);
  scanf("%d",&v);
  while(v--){
    scanf("%d %d",&s,&t);
    printf("%d\n",cmp[s]-cmp[t]?0:1);
  }
  return 0;
}

Measured memory_bytes: 2068
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#define rep(i,x,y) for(int i=x;i<=y;++i)

const int INF=1<<30;
using namespace std;

typedef long long ll;
const int maxn=200000+10;

ll sum[maxn],t[maxn];

int n;
#define lowbit(i) ((i)&(-(i)))
int C[maxn];
void updata(int pos,int val){
	for(int i=pos;i<=n;i+=lowbit(i)) C[i]+=val;
}
int query(int pos){
	int ret=0;
	for(int i=pos;i;i-=lowbit(i)) ret=ret+C[i];
	return ret;
}

int main()
{
	ll k;cin>>n>>k;
	rep(i,1,n) 
	{
		scanf("%lld",sum+i);
		sum[i]-=k;sum[i]+=sum[i-1];t[i]=sum[i];
	}

	sort(t+1,t+n+1);
	int len=unique(t+1,t+n+1)-t-1;
	rep(i,1,n) sum[i]=lower_bound(t+1,t+len+1,sum[i])-t;

	ll ans=0;
	rep(i,1,n)
	{
		ans+=query(sum[i]);
		updata(sum[i],1);
		if(t[sum[i]]>=0) ++ans;
	}

	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 4096
#include <algorithm>
#include <boost/optional.hpp>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <functional>
#include <iostream>
#include <limits>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <tuple>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

#define REP(i, n) for(int i = 0, i##_MACRO = (n); i < i##_MACRO; i++)
#define RANGE(i, a, b) for(int i = (a), i##_MACRO = (b); i < i##_MACRO; i++)
#define EACH(e, a) for(auto&& e : a)
#define ALL(a) std::begin(a), std::end(a)
#define RALL(a) std::rbegin(a), std::rend(a)
#define FILL(a, n) memset((a), n, sizeof(a))
#define FILLZ(a) FILL(a, 0)
#define INT(x) (static_cast<int>(x))

using namespace std;

using ll = long long;
using VI = vector<int>;
using VI2D = vector<vector<int>>;

constexpr int INF = 2e9;
constexpr double EPS = 1e-10;
constexpr double PI = acos(-1.0);

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

template <typename T>
constexpr int sign(T x) {
	return x < 0 ? -1 : x > 0 ? 1 : 0;
}

template <>
constexpr int sign(double x) {
	return x < -EPS ? -1 : x > EPS ? 1 : 0;
}

template <typename T, typename U>
constexpr void chmax(T& m, U x) {
	m = max(m, x);
}

template <typename T, typename U>
constexpr void chmin(T& m, U x) {
	m = min(m, x);
}

template <typename T>
constexpr T square(T x) {
	return x * x;
}

int main() {
	int n;
	cin >> n;
	int x = n % 10;
	switch (x) {
		case 2:
		case 4:
		case 5:
		case 7:
		case 9:
			cout << "hon" << endl;
			break;
		case 3:
			cout << "bon" << endl;
			break;
		default:
			cout << "pon" << endl;
			break;
	}
	return 0;
}


Measured memory_bytes: 3632
#include<iostream>
#include<string>
#include<vector>
#include<numeric>
#include<math.h>
#include<algorithm>
#include<iomanip>
using namespace std;


int main() {

	long M, N;
	cin >> N >> M;

	vector<long> A(N, 0);
	long sum = 0;

	for (long i = 0; i < N; i++) {
		cin >> A[i];
		sum += A[i];
	}

	sort(A.begin(), A.end(), greater<long>());

	if ((A[M - 1]*4*M) >= sum) {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}

	return 0;
}



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

using namespace std;
using ll = long long;

int main() {
  int N, Q; cin >> N >> Q;
  vector<int> v(N);
  for (int i = 0; i < N; i++) cin >> v[i];
  vector<ll> sum(N+1), sum2(N+1);
  sum[1] = sum2[1] = v[0];
  for (int i = 2; i < N+1; i++) {
    sum[i] = sum[i-1] + v[i-1];
    sum2[i] = sum2[i-2] + v[i-1];
  }
  map<int, ll> m;
  m[0] = sum[N/2];
  int l = 0, r = N/2;
  for (; l < r;) {
    if (r - l > N - 1 - r) {
      l++; continue;
    }
    int thr = (v[r] + v[l]) / 2 + 1;
    ll s = sum[r+1] - sum[l+1];
    s += sum2[l];
    m[thr] = s;
    r++;
  }
  while (Q--) {
    int x; cin >> x;
    cout << sum[N] - (--m.upper_bound(x))->second << endl;
  }
}

Measured memory_bytes: 6784