akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <sstream>
#include <functional>
#include <numeric>
#include <cmath>
#include <cstring>
#include <queue>
#include <stack>
#include <set>

using namespace std;

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

typedef long long LL;
typedef pair<int, int> P;
typedef pair<int, P> IP;
typedef pair<P, P> PP;
typedef vector<int> Array;
typedef vector<vector<int> > Array2;
typedef vector<int> LArray;

const int INF = 1 << 29;
const LL LINF = 1LL << 60;

int itiv;
inline int getInt() { return (cin >> itiv, itiv); }
void readAll(Array& vec, int n) { for (int i = 0; i < n; i++) cin >> vec[i]; }
inline bool between(int first, int last, int n) { return first <= n && n <= last; }
inline bool inRange(int begin, int end, int n) { return begin <= n && n < end; }
inline bool inRange(int size, int n) { return 0 <= n && n < size; }

int m, n;
int dx[] = { -1, 0, 1, 0 }, dy[] = { 0, -1, 0, 1 };
int dr[] = { 0, -1, 0, 1 }, dc[] = { -1, 0, 1, 0 };

const int MOD = 10007;

int toNum(char c)
{
	switch(c)
	{
	case 'J':
		return 1;
	case 'O':
		return 2;
	case 'I':
		return 4;
	}
	return 0;
}

int main(void)
{
	while(cin >> n && n)
	{
		int pre[8] = {0}, nex[8] = {0};
		string sch;
		cin >> sch;
		pre[1] = 1;
		for (int i = 0; i < n; i++)
		{
			for (int j = 1; j < 8; j++)
			{
				for (int k = 1; k < 8; k++)
				{
					if((j & k) && (k & toNum(sch[i])))
					{
						nex[k] += pre[j] % MOD;
					}
				}
			}

			for (int j = 0; j < 8; j++)
			{
				pre[j] = nex[j];
				nex[j] = 0;
			}
		}
		cout << accumulate(pre, pre + 8, 0) % MOD << endl;
	}
	return 0;
}

Measured memory_bytes: 1204
#include <iostream>

using namespace std ;

int main()
{
    int N,K ;
    while(cin >> N >> K)
    {
        int like[K] = {0} ;

        int people[N][K] ;
        for(int i = 0; i < N; i++)
        {
            for(int j = 0; j < K; j++)
            {
                people[i][j] = 0 ;
            }
        }

        int c[N] = {0} ;
        for(int i = 0; i < N; i++)
        {
            cin >> c[i] ;
            for(int j = 0; j < c[i]; j++)
            {
                cin >> people[i][j] ;

            }
        }

        for(int i = 0; i < N; i++)
        {
            for(int j = 0; j < c[i]; j++)
            {
                for(int p = 1;p < K || p == K; p++)
                {
                    if(people[i][j] == p)
                    {
                        like[p-1]++ ;
                    }
                }
            }
        }

        int ans = 0 ;
        if(N == 1)
        {
            for(int i = 0;i < K;i++)
            {
                if(like[i] != 0)
                {
                    ans++ ;
                }
            }
            cout << ans ;
        }
        else
        {
            for(int i = 0; i < K; i++)
            {
                if(like[i] == N)
                {
                    ans++ ;
                }
            }
            cout << ans ;
        }
    }

}

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

void solve() {
  int a, b;
  std::cin >> a >> b;
  std::string s1;
  std::string s2;
  for (int i = 0; i < a; i++) s1 += (char)('0'+b);
  for (int i = 0; i < b; i++) s2 += (char)('0'+a);
  if (s1 > s2) std::cout << s2;
  else std::cout << s1;
}

int main() {
  solve();
  return 0;
}

Measured memory_bytes: 256
h,w = map(int, input().split())
ch,hw = map(int, input().split())
dh,dw = map(int, input().split())

sy,sx=ch-1,hw-1
gx,gy=dw-1,dh-1

l = [None]*h
for i in range(h):
    l[i] = list(input())

dist = [[-1]*w for i in range(h)]
dist[sy][sx] = 0

from collections import deque
def walk(warped,cnt):
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]

    Q = deque(warped)
    walked=warped
    changed=False
    while Q:
        p = Q.popleft()
        for i in range(4):
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]

            if 0 <= nx < w and 0 <= ny < h:
                if l[ny][nx]=="." and dist[ny][nx]==-1:
                    changed=True
                    Q.append([nx, ny])
                    walked.append([nx,ny])
                    dist[ny][nx] = cnt
                    if nx==gx and ny==gy:
                        print(cnt)
                        exit()
    return walked,changed
def warp(walked,cnt):
    warped=[]
    changed=False

    for x,y in walked:
        for dx in [-2,-1,0,1,2]:
            for dy in [-2,-1,0,1,2]:
                if abs(dx)+abs(dy)<=1:
                    continue

                nx=x+dx
                ny=y+dy
                if 0 <= nx < w and 0 <= ny < h:
                    if l[ny][nx]=="." and dist[ny][nx]==-1:
                        changed=True
                        warped.append([nx,ny])
                        dist[ny][nx] = cnt
                        if nx==gx and ny==gy:
                            print(cnt)
                            exit()
    return warped,changed

cnt=0

warped=[[sx,sy]]

while True:
    walked,walkchange= walk(warped,cnt)
    cnt+=1
    warped,warpchange=warp(walked,cnt)
    if not walkchange and not warpchange:
        print(-1)
        exit()

Measured memory_bytes: 153516
#include<iostream>
using namespace std;
int main(){
  long long A,B,C,K;
  cin >> A>> B >>C >>K;
  if(A>=K)cout << K << endl;
  if(A<K && K<=(A+B))cout << A << endl;
  if((A+B)<K && K<=(A+B+C))cout << A-(K-A-B) << endl;
}

Measured memory_bytes: 3560
#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <map>
#include <stack>
#include <queue>
#include <algorithm>
#include <set>
 
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,j) FOR(i,0,j)
#define mp std::make_pair
 
const int INF = 1 << 24;
const int dx[8] = {0, 0, 1, -1, 1, 1, -1, -1}, dy[8] = {1, -1, 0, 0, 1, -1, 1, -1};
 
typedef unsigned long long ull;
typedef std::pair<int,int> P;
 
// C<=15, D<=30, W<=50, X<=5
int C, D, W, X;
int E[15][31], F[15][31];
// dp[i][j][k]: i日目にコンサートを行い，負担がj，1日に2個以上ライブをしたのがkとなったときの最大利益
int dp[31][51][6];
 
P live(int day, int first, int last){
    P res = mp(0, 0);
    FOR(i, first, last+1){
        if(E[i][day] == 0){return mp(-INF, -INF);}
        res.first += E[i][day];
        res.second += F[i][day];
    }
    return res;
}
 
int main(){
    while(std::cin >> C >> D >> W >> X, C){
        REP(i, C){
            FOR(j, 1, D+1){
                std::cin >> E[i][j];
            }
        }
 
        REP(i, C){
            FOR(j, 1, D+1){
                std::cin >> F[i][j];
            }
        }
 
        REP(i, 31){
            REP(j, 51){
                REP(k, 6){
                    dp[i][j][k] = -INF;
                }
            }
        }
 
        dp[0][0][0] = 0;
 
        // int day, from, to;
        // while(std::cin >> day >> from >> to, day){
        //     auto p = live(day, from, to);
        //     printf("%d, %d\n", p.first, p.second);
        // }
         
        FOR(i, 1, D+1){
            REP(j, W+1){
                REP(k, X+1){
                    dp[i][j][k] = dp[i-1][j][k];
                    REP(l, C){
                        FOR(m, l, C){
                            P p = live(i, l, m);
                            int benefit = p.first, cost = p.second;
 
                            if(benefit == -INF && cost == -INF){continue;}
                            if(j - cost < 0){continue;}
 
                            if(l == m){ // 一箇所だけ
                                dp[i][j][k] = std::max(dp[i][j][k], dp[i-1][j-cost][k] + (benefit));
                            }else if(k-1 >= 0){ // 二箇所以上
                                dp[i][j][k] = std::max(dp[i][j][k], dp[i-1][j-cost][k-1] + (benefit));
                            }
                        }
                    }
                }
            }
        }
 
        int res = -INF;
        REP(j, W+1){
            REP(k, X+1){
                res = std::max(res, dp[D][j][k]);
            }
        }
 
        std::cout << res << std::endl;
    }
}

Measured memory_bytes: 1200
// input! macro is published in the following URLs.
// https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
// https://github.com/tanakh/competitive-rs.git
#[allow(unused_macros)]
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };

    ($next:expr, mut $var:ident : $t:tt $($r:tt)*) => {
        let mut $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, [ $t:tt ]) => {
        {
            let len = read_value!($next, usize);
            (0..len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
        }
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, bytes) => {
        read_value!($next, String).into_bytes()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

fn main() {
    input! {
        n: usize,
        a_s: [i64; n],
    }
    let mut max_diff = 0;
    for ai in a_s.iter() {
        for aj in a_s.iter() {
            let diff = (*ai - *aj).abs();
            max_diff = std::cmp::max(max_diff, diff);
        }
    }
    println!("{}", max_diff);
}


Measured memory_bytes: 4352
#include <iostream>

using namespace std;

int main() {
  long long a, b, x;
  cin >> a >> b >> x;
  long long r = b / x + 1;
  long long l = 0;
  if (a != 0) {
    l = (a-1) / x + 1;
  }
  long long count = r - l;
  //cout << r << "," << l << endl;
  cout << count << endl;
}


Measured memory_bytes: 256
while True:
    list = input().split()
    a = int(list[0])
    b = int(list[1])
    if a == 0 and b == 0:
        break
    for i in range(a):
        for j in range(b):
            if i == 0 or j == 0 or i == a - 1 or j == b - 1:
                print("#", end = "")
            else:
                print(".", end = "")
        print()
    print()


Measured memory_bytes: 7000
n = int(input())
a = list(map(int, input().split()))
avg_a = sum(a) // n
avg_b = avg_a + 1
total_one = 0
total_two = 0
for num in a:
    total_one += (num - avg_a) ** 2
    total_two += (num - avg_b) ** 2
print(min(total_one, total_two))


Measured memory_bytes: 9104
#include <bits/stdc++.h>
//#include <atcoder/all>
#define ll long long int
#define MOD 1000000007
#define P pair<ll,ll>
#define INF 1000000000000000000

//using namespace atcoder;
using namespace std;

int main(void){
  ll n, q;
  cin >> n >> q;
  
  vector<ll> a(n, n-2), b(n, n-2);

  ll ans = (n-2)*(n-2);

  ll x = n-1, y = n-1;
  for (ll i = 0; i < q; i++){
    ll c, d;
    cin >> c >> d;

    d--;
    
    if (c == 1){
      if (x < d){
        ans -= b[d] - 1;
      }
      else {
        for (ll i = d + 1; i < x; i++){
          b[i] = y;
        }

        x = d;
        ans -= y - 1;
      }
    }
    else {
      if (y < d){
        ans -= a[d] - 1;
      }
      else {
        for (ll i = d + 1; i < y; i++){
          a[i] = x;
        }

        y = d;
        ans -= x - 1;
      }
    }
  }

  cout << ans << endl;
  

  return 0;
}


Measured memory_bytes: 6372
#include<iostream>
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <vector>

using namespace std;

int main()
{
  int count,a,diff;
  cin >> count;
  vector<int> inList, master, tmp;
  for (int i=0;i<count;i++){
    cin >> a;
    inList.emplace_back(a);
    master.emplace_back(a);
  }
  sort(master.begin(),master.end());
  if(equal(inList.cbegin(), inList.cend(), master.cbegin())){
    cout << "YES";
    return 0;
  }
  for(int i=0;i<count;i++){
    if(inList[i] != master[i]){
      diff++;
    }
  }
  if(diff <= 2){
    cout << "YES";
  }else{
    cout << "NO";
  }
  return 0;
}


Measured memory_bytes: 256
n, m = map(int, input().split())
a = []
ans = [i for i in range(1, m+1)]

for i in range(n):
    a.append(list(map(int, input().split()))[1:])

#print(ans)

for i in range(n):
    for j in range(1, m+1):
        if j not in a[i] and j in ans:
            ans.remove(j)

#print(ans)
print(len(ans))


Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
template<typename T>inline void read(T&x)
{
	T f;register char ch;x=0;f=1;
	for(ch=getchar();!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
	for(;isdigit(ch);ch=getchar())x=(x*10)+(ch^48);
	x*=f;
}

const int MAXN=1e5+7;

static int n,m;

static char S[MAXN],T[MAXN];

inline void init()
{
	read(n);read(m);
	scanf("%s%s",S+1,T+1);
}

inline int gcd(int u,int v){return v?gcd(v,u%v):u;}

inline void solve()
{
	int d=gcd(n,m);
	for(int i=1,j=1;i<=n&&j<=m;i+=n/d,j+=m/d)
	{
		if(S[i]!=T[j])return(void)puts("-1");
	}
	printf("%lld\n",1ll*n*m/d);
}

int main()
{
	init();
	solve();
	return 0;
}

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

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

    int ans;

    if (a <= b * 2) {
        ans = 0;
    }
    else {
        ans = a - b * 2;
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 256
package main

import (
	"fmt"
	"sort"
)

func main() {
	var s, t string
	fmt.Scan(&s, &t)
	sa := make([]string, len(s))
	for i, v := range s {
		sa[i] = string(v)
	}
	ta := make([]string, len(t))
	for i, v := range t {
		ta[i] = string(v)
	}
	sort.Sort(sort.StringSlice(sa))
	sort.Sort(sort.Reverse(sort.StringSlice(ta)))
	for i := 0; i < Min(len(sa), len(ta)); i++ {
		if sa[i] < ta[i] {
			fmt.Println("Yes")
			return
		} else if sa[i] > ta[i] {
			fmt.Println("No")
			return
		}
	}
	if len(sa) < len(ta) {
		fmt.Println("Yes")
	} else {
		fmt.Println("No")
	}
}
func Min(a, b int) int {
	if b < a {
		return b
	}
	return a
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
#include <atcoder/all>
#define FOR(i, a, n) for(int (i) = (int)(a); (i) < (int)(n); ++(i))
#define FORe(i, a, n) for(int (i) = (int)(a); (i) <= (int)(n); ++(i))
#define rFOR(i, a, n) for(int (i) = (int)(n)-1; (i) >= (int)(a); --(i))
#define rFORe(i, a, n) for(int (i) = (int)(n); (i) >= (int)(a); --(i))
#define REP(i, n) FOR((i), 0, (n))
#define REPe(i, n) FORe((i), 1, (n))
#define REPo(i, n) FORe((i), 0, (n))
#define rREP(i, n) rFOR((i), 0, (n))
#define rREPe(i, n) rFORe((i), 1, (n))
#define rREPo(i, n) rFORe((i), 0, (n))
#define rep(i, n) FOR((i), 0, (n))
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define fi first
#define se second
#define dup(x, y) (((x)+(y)-1)/(y))
#define vc(T) vector<T>
#define vv(T) v(v(T))
using namespace std;
using namespace atcoder;
using ll = long long;
using P = pair<int,int>;
using pll = pair<ll,ll>;
using T = tuple<int,int,int>;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vs = vector<string>;
using vp = vector<P>;
using vt = vector<T>;

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

int main() {
  int n,q;
  cin >> n >> q;
  dsu uf(n);
  int t,u,v;
  REP(i, q){
    cin >> t >> u >> v;
    if (t) cout << uf.same(u,v) << endl;
    else uf.merge(u, v);
  }

  return 0;
}

Measured memory_bytes: 4032
#include <bits/stdc++.h>
#define syosu(x) fixed<<setprecision(x)
using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef pair<double,double> pdd;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<string> vs;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<pll> vpll;
typedef pair<int,P> pip;
typedef vector<pip> vip;
const int inf=1<<30;
const ll INF=1ll<<60;
const double pi=acos(-1);
const double eps=1e-9;
const ll mod=1e9+7;
const int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};



int main(){
	for(int i=0;i<10000;i++) cout<<-1<<endl;
}

Measured memory_bytes: 256
def ng():
    print(-1)
    exit()

def main():
    N,*P=map(int, open(0).read().split())
    ans=0
    pre=0
    if P[0]!=0: ng()
    for p in P[1:]:
        if pre+1<p: ng()
        ans+=1 if pre+1==p else p
        pre=p
    print(ans)

if __name__ == "__main__":
    main()

Measured memory_bytes: 25132
from collections import deque
H, W = map(int, input().split())
field = [input() for _ in range(H)]
ans = 0

# 4方向の移動
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]


for h in range(H):
    for w in range(W):
        # BFSのためのデータ構造
        if field[h][w] == "#":
            continue
        dist = [[-1] * W for _ in range(H)]
        que_x = deque()
        que_y = deque()
        dist[h][w] = 0
        que_x.append(h)
        que_y.append(w)

        # BFS開始
        while que_x and que_y:
            x = que_x[0]
            y = que_y[0]
            que_x.popleft()
            que_y.popleft()
            tmp_max = 0
            for direct in range(4):
                nx = x + dx[direct]
                ny = y + dy[direct]
                if nx < 0 or H <= nx or ny < 0 or W <= ny:      # 場外はスルー
                    continue
                if field[nx][ny] == "#":     # 壁はスルー
                    continue
                if dist[nx][ny] == -1:          # まだ見ていない時
                    que_x.append(nx)
                    que_y.append(ny)
                    dist[nx][ny] = dist[x][y] + 1   # 距離の更新
        for i in range(H):
            for k in range(W):
                tmp_max = max(dist[i][k], tmp_max)
        ans = max(tmp_max, ans)
print(ans)

Measured memory_bytes: 3316
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n,d;
	cin>>n>>d;
	int mat[n][d];
	double ans;
	int co=0;
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<d;j++)
		{
			cin>>mat[i][j];
		}
	}
	for(int i=0;i<n;i++)
	{
		for(int j=i+1;j<n;j++)
		{	
			int s=0;
			for(int k=0;k<d;k++)
			{
				s+=(mat[i][k]-mat[j][k])*(mat[i][k]-mat[j][k]);
			}
			for(int k=0;k<=s;k++)
			{
				if(k*k==s)
				{
					co++;
					break;
				}
			}
		}

	}
	cout<<co<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <boost/range/irange.hpp>

using namespace std;
using boost::irange;
typedef long long ll;
const ll mod = 1e9 + 7;

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

    int h = 0;
    for (int i: irange(1, N)) {
        if (S[i] == S[i - 1]) h++;
    }
    cout << min(h + 2 * K, N - 1) << endl;

    return 0;
}

Measured memory_bytes: 512
#include "bits/stdc++.h"
#define _overload3(_1,_2,_3,name,...)name
#define _rep(i,n)repi(i,0,n)
#define repi(i,a,b)for(int i=int(a),i##_len=(b);i<i##_len;++i)
#define MSVC_UNKO(x)x
#define rep(...)MSVC_UNKO(_overload3(__VA_ARGS__,repi,_rep,_rep)(__VA_ARGS__))
#define all(c)c.begin(),c.end()
#define write(x)cout<<(x)<<'\n'
using namespace std; typedef long long ll; template<class T>using vv = vector<vector<T>>;
template<class T>auto vvec(int n, int m, T v) { return vv<T>(n, vector<T>(m, v)); }
constexpr int INF = 1 << 29, MOD = int(1e9) + 7; constexpr ll LINF = 1LL << 60;
struct aaa { aaa() { cin.tie(0); ios::sync_with_stdio(0); cout << fixed << setprecision(10); }; }aaaa;

struct UnionFindTree {
    vector<int> parent, rank;
    int operator [](int x) { return find(x); }
    void build(int n) { parent.assign(n, -1); rank.assign(n, 0); }
    int find(int x) { return parent[x] < 0 ? x : (parent[x] = find(parent[x])); }
    bool same(int x, int y) { return find(x) == find(y); }
    int size(int x) { return -parent[find(x)]; }
    bool unite(int x, int y) {
        if ((x = find(x)) == (y = find(y))) return 0;
        rank[x] = max(rank[x], rank[y] + 1); parent[x] += parent[y]; parent[y] = x; return 1;
    }
    bool uniteByRank(int x, int y) {
        if ((x = find(x)) == (y = find(y))) return 0;
        else if (rank[x] < rank[y]) swap(x, y);
        else if (rank[x] == rank[y]) rank[x]++;
        parent[x] += parent[y]; parent[y] = x; return 1;
    }
    bool uniteBySize(int x, int y) {
        if ((x = find(x)) == (y = find(y))) return 0;
        else if (size(x) < size(y)) swap(x, y);
        rank[x] = max(rank[x], rank[y] + 1); parent[x] += parent[y]; parent[y] = x; return 1;
    }
};

int main() {
    int N, M, K;
    cin >> N >> M >> K;
    vector<int> A(M), B(M), C(K), D(K);
    rep(i, M) {
        cin >> A[i] >> B[i];
        A[i]--; B[i]--;
    }
    rep(i, K) {
        cin >> C[i] >> D[i];
        C[i]--; D[i]--;
    }

    UnionFindTree frtree;
    frtree.build(N);
    rep(i, M) {
        frtree.uniteByRank(A[i], B[i]);
    }
    vector<int> fr(N), bl(N);
    rep(i, M) {
        fr[A[i]]++;
        fr[B[i]]++;
    }
    rep(i, K) {
        if (frtree.same(C[i], D[i])) {
            bl[C[i]]++;
            bl[D[i]]++;
        }
    }

    rep(i, N) {
        cout << (frtree.size(i) - fr[i] - bl[i] - 1) << (!--N ? '\n' : ' ');
    }
}

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

const int N = 105;
int f[N][15];
int p[N][15];
int main()
{
	int n; 
	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < 10; j++) {
			cin >> f[i][j];
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < 11; j++) {
			cin >> p[i][j];
		}
	}

	int ans = -1e9;
	for (int i = 1; i < (1 << 10); i++) {
		int profit = 0;
		for (int j = 0; j < n; j++) {
			int open = 0;
			
			for (int k = 0; k < 10; k++) {
				
				if (i >> k & 1 && f[j][k]) {
					open++;
				}
			}

			profit += p[j][open];
		}
		if (profit > ans) {
			ans = profit;
		}
		
	}

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


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

int S[100100] = {};
int T[50100] = {};

int isContain(int x, int S[], int left, int right){//二分探索
    while(left <= right){//左端が右端以下の場合に繰り返す
        int mid = (left + right) / 2; //真ん中の値を求める
        if(x == S[mid]) return 1;
        else if(x > S[mid]) left = mid + 1; //真ん中の値の左隣にある値をleftとする
        else right = mid - 1; //真ん中の値の右隣にある値をrightとする
    }
    return 0; //while文の条件が不成立の場合０を返す
}

int main(void){
    int n, q; //配列Sの個数と配列Tの個数
    int C = 0; //SかつTの要素であるものの個数

    cin >> n;
    for(int i = 0; i < n; i++)
        cin >> S[i];
    cin >> q;
    for(int i = 0; i < q; i++)
        cin >> T[i];
    
    for(int i = 0; i < q; i++){
        if(isContain(T[i], S, 0, n - 1)) C++;
    }
    cout << C << endl;
}



Measured memory_bytes: 3688
#include <iostream>
#include <vector>
#include <map>
#include <utility>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <stack>
#include <queue>
#include <set>
#include <unordered_map>
#include <unordered_set>

#define REP(i,a,n) for(int i=a;i<n;++i)
#define rep(i,n) REP(i,0,n)
#define REV(i,a,n) for(int i=n;i>=a;--i)
#define all(e) e.begin(),e.end()
#define rall(e) e.rbegin(),e.rend()
#define pb push_back
#define mp make_pair
#define fs first
#define sc second
#define mod 1000000007
#define show(n) cerr<<#n<<" = "<<n<<endl
#define shows(n) for(auto z:n){cerr<<z<<", ";}cerr<<endl

//ここからAtCoder向けdefine
#define yes cout << "YES" << endl
#define no cout << "NO" << endl

using namespace std;

using ll = long long;
using ull = unsigned long long;
using vi = vector<int>;
using pint = pair<int,int>;

const int INF = (1 << 30);

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

    ull n;
    cin>>n;
    ull t=1;
    ll c=1;
    int cnt=1;
    int ans=1;
    while(true){
        //show(t);
        if(cnt==9){
            c*=10;
            cnt=0;
        }
        if(t<=n&&n<t+c){
            cout<<ans<<endl;
            return 0;
        }
        t+=c;
        cnt++;
        ans++;
    }

    return 0;
}

Measured memory_bytes: 256
from collections import defaultdict
N,K = map(int, input().split())
dic = defaultdict(int)
for i in range(N):
    a,b = map(int, input().split())
    dic[a] += b
dic = sorted(dic.items(),reverse=True)

tmp = 0
while tmp < K:
    ans = dic.pop()
    tmp += ans[1]
print(ans[0])

Measured memory_bytes: 14936
#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#define pb push_back
#define mp make_pair
using namespace std;
int main()
{
    bool f = false;
    while (true) {
        int n; cin >> n; if (n == 0) break;
        if (f) cout << endl;
        else f = true;
        vector<pair<pair<int, int>, string> > v;
        for (int i = 0; i < n; ++i) {
            string t;
            int a, b, c;
            cin >> t >> a >> b >> c;
            v.pb(mp(mp(3*a+c, -i), t));
        }
        sort(v.rbegin(), v.rend());
        for (int i = 0; i < n; ++i)
            cout << v[i].second << "," << v[i].first.first << endl;
    }
    return 0;
}

Measured memory_bytes: 0
import Data.List

combinations :: Int -> [a] -> [[a]]
combinations n xs = comb n (length xs) xs where
  comb 0 _ _ = [[]]
  comb r n a@(x:xs)
    | n == r    = [a]
    | otherwise = map (x:) (comb (r - 1) (n - 1) xs) ++ comb r (n - 1) xs

solve :: [[Int]] -> Int -> Int
solve a ini
 | null a = ini
 | (headA !! 0 == headA !! 1) = solve (tail a) ini
 | (headA !! 1 == headA !! 2) = solve (tail a) ini
 | (headA !! 2 == headA !! 0) = solve (tail a) ini
 | ((headA !! 0) + (headA !! 1)) > (headA !! 2) = solve (tail a) (ini + 1)
 | otherwise = solve (tail a) ini
 where headA = (head a)

main = do
 n <- read <$> getLine :: IO Int
 lk <- map read . words <$> getLine :: IO [Int]
 let lcomb = map sort $ combinations 3 lk
 print $ if(n < 3) then 0 else solve lcomb 0

Measured memory_bytes: 6788
D = int(input())
c = list(map(int, input().split()))
s_tbl = [list(map(int, input().split())) for _ in range(D)]
ans = 0
last = [0] * 26

for d in range(1, D+1):
    t = int(input()) - 1
    c_sum = 0
    for i in range(26):
        c_sum = c_sum + c[i] * (d-last[i])
    ans = ans + s_tbl[d-1][t] + (-c_sum) + c[t] * (d-last[t])
    last[t] = d
    print(ans)

Measured memory_bytes: 9312
n, x = map(int, input().split())
a = [int(an) for an in input().split()]
a.sort()
ans = 0
num_candy = 0
for an in a:
  num_candy += an
  if num_candy <= x:
    ans += 1
if num_candy < x:
  ans -= 1
print(ans)

Measured memory_bytes: 61972
#include<bits/stdc++.h>
using namespace std;
using ll  = long long;
using vl  = vector<ll>;
using vi  = vector<int>;
#define _GLIBCXX_DEBUG
#define IO_STREAM cin.tie(0);ios::sync_with_stdio(false)
#define all(x) x.begin(),x.end()
#define rep(i,sta,end) for(int i=sta;i<end;++i)
#define lcm(a,b) (a)/__gcd((a),(b))*(b)
#define pb push_back
const ll INF = 1000000000000000;
const ll MOD = 1000000007;
const double PI = acos(-1);
//||
#define DBG(a,b,c,d) //cout<<a<<" "<<b<<" "<<c<<" "<<d<<" "<<endl
//DBG("","","","");

int main(){
	IO_STREAM;
	string S;	cin>>S;
	int m=0;
	int p=0;
	rep(i,0,S.size()){
		if(S[i]=='+') p++;
		else m++;
	}
	cout<<p-m<<endl;
	return 0;
}


Measured memory_bytes: 3624
const input = require("fs").readFileSync("/dev/stdin", "utf8")

;(input => {

    const X = input - 0

    if (X === 0) {
        console.log('1 1')
        return
    }

    const dp = [0]

    let i = 0
    while (1) {
        i++
        dp[i] = Math.pow(i, 5)
        for (let j = 0; j <= dp.length; j++) {
            let hit = -1
            if ((hit = dp.indexOf(X - dp[j])) !== -1) {
                console.log(hit + ' ' + -j)
                return
            }
            if ((hit = dp.indexOf(X + dp[j])) !== -1) {
                console.log(hit + ' ' + j)
                return
            }
        }
    }
    
})(input)



Measured memory_bytes: 29856
import sys
sys.setrecursionlimit(100000)

def ins(): return input().split()
def ii(): return int(input())
def iil(): return list(map(int,ins()))
def lin(): return list(input())
def iin(): return map(int,ins())

n = ii()
a = iil()
b = iil()
c = iil()
ans = b[a[0]-1]
for i in range(1,n):
    if a[i]-a[i-1]==1:
        ans += c[a[i-1]-1]
    ans += b[a[i]-1]
print(ans)

Measured memory_bytes: 3064
import java.util.Arrays;
import java.util.Scanner;

class Main{
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		boolean[] isPrime = new boolean[1000000];
		Arrays.fill(isPrime, true);
		for(int i = 2; i < isPrime.length; i++) {
			if(isPrime[i]) {
				for(int j = 2 * i; j < isPrime.length; j += i) isPrime[j] = false;
			}
		}
		int X = sc.nextInt();
		for(int i = X; i < isPrime.length; i++) {
			if(isPrime[i]) {
				System.out.println(i);
				break;
			}
		}
	}
}

Measured memory_bytes: 25428
#include <iostream>
#include <math.h>
#include <vector>
#include <stack>
#include <cstdio>
#include <string>
#include <bitset>
#include <list>
#include <set>
#include <algorithm>
#include <numeric>

using namespace std;
//debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
int main() {
	int a,b;
	cin >> a>>b;
	int n = b - a-1;
	cout << n*(n + 1) / 2 - a;


	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main() {
  int N,ans=0,x=1;
  cin>>N;
  vector<int> a(N);
  for(int i=0;i<N;i++)
    cin>>a.at(i);
  
  for(int i=0;i<N;i++){
    x=a.at(x-1);
    ans++;
    if(x==2)
      break;
  }
  if(x==2)	cout<<ans<<endl;
  else	cout<<-1<<endl;
}


Measured memory_bytes: 640
import java.io.*;
import java.util.*;

public class Main {
  private static int solve(int x, int[] as) {
    int count = 0;
    Arrays.sort(as);
    for (int a : as) {
      if (x >= a) {
        x -= a;
        count++;
      } else {
        x = 0;
        break;
      }
    }
    if (x > 0) {
      return count - 1;
    } else {
      return count;
    }
  }
  
  private static void execute(ContestReader reader, PrintWriter out) {
    int n = reader.nextInt();
    int x = reader.nextInt();
    int[] as = reader.nextIntArray(n);
    out.println(solve(x, as));
  }
  
  public static void main(String[] args) {
    ContestReader reader = new ContestReader(System.in);
    PrintWriter out = new PrintWriter(System.out);
    execute(reader, out);
    out.flush();
  }
}

class ContestReader {
  private BufferedReader reader;
  private StringTokenizer tokenizer;
  
  ContestReader(InputStream in) {
    reader = new BufferedReader(new InputStreamReader(in));
  }
  
  public String next() {
    while (tokenizer == null || !tokenizer.hasMoreTokens()) {
      try {
        tokenizer = new java.util.StringTokenizer(reader.readLine());
      } catch (Exception e) {
        throw new RuntimeException(e);
      }
    }
    return tokenizer.nextToken();
  }
  
  public int nextInt() {
    return Integer.parseInt(next());
  }
  
  public long nextLong() {
    return Long.parseLong(next());
  }
  
  public double nextDouble() {
    return Double.parseDouble(next());
  }
  
  public int[] nextIntArray(int n) {
    int[] array = new int[n];
    for (int i = 0; i < n; i++) {
      array[i] = nextInt();
    }
    return array;
  }
  
  public long[] nextLongArray(int n) {
    long[] array = new long[n];
    for (int i = 0; i < n; i++) {
      array[i] = nextLong();
    }
    return array;
  }
}

class Algorithm {
  private static void swap(Object[] list, int a, int b) {
    Object tmp = list[a];
    list[a] = list[b];
    list[b] = tmp;
  }
  
  public static <T extends Comparable<? super T>> boolean nextPermutation(T[] ts) {
    int rightMostAscendingOrderIndex = ts.length - 2;
    while (rightMostAscendingOrderIndex >= 0 &&
        ts[rightMostAscendingOrderIndex].compareTo(ts[rightMostAscendingOrderIndex + 1]) >= 0) {
      rightMostAscendingOrderIndex--;
    }
    if (rightMostAscendingOrderIndex < 0) {
      return false;
    }
    
    int rightMostGreatorIndex = ts.length - 1;
    while (ts[rightMostAscendingOrderIndex].compareTo(ts[rightMostGreatorIndex]) >= 0) {
      rightMostGreatorIndex--;
    }
    
    swap(ts, rightMostAscendingOrderIndex, rightMostGreatorIndex);
    for (int i = 0; i < (ts.length - rightMostAscendingOrderIndex - 1) / 2; i++) {
      swap(ts, rightMostAscendingOrderIndex + 1 + i, ts.length - 1 - i);
    }
    return true;
  }
}



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

int main() {
  long A, B, K;
  cin >> A >> B >> K;
  int cnt = 0;
  for(int i= max(A,B); i>0; i--){
    if(A%i==0 && B%i==0){
      cnt++;
      if(cnt==K){
        cnt = i;
        break;
      }
    }
  }
  cout << cnt;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>

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

using namespace std;

int main()
{
  vector<int> v;
  int t;

  for ( int i = 0; i < 10; i++ ) {
    cin >> t;
    v.push_back(t);
  }

  sort(ALL(v));

  for ( int i = 0; i < 3; i++ ) {
    cout << v[9-i] << endl;
  }

  return 0;
}

Measured memory_bytes: 1216
#include <bits/stdc++.h>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
using namespace std;
int main() {

    cout << fixed << setprecision(20);

    int N, M;
    cin >> N >> M;
    double ans=0;
  
    for(int i=1;i<=N;i++) {
        double rate = 1.0/N;
        int k=i;
        while(k<M){
            k *= 2;
            rate /= 2;
        }

        ans += rate;
    }

    cout << ans << endl;
  

	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main()
{
    ll D,N,i,p,c=0;
    double q;
    cin>>N>>D;
    ll X[N],Y[N];
    for(i=0;i<N;i++){
        cin>>X[i]>>Y[i];
        p=(((X[i])*(X[i]))+((Y[i])*(Y[i])));
        q=(sqrt(double(p)));
        if(q<=D) c++;
    }
    cout<<c<<endl;
}

Measured memory_bytes: 6800
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
	int N, K;
	cin >> N;
	cin >> K;
	int *array = new int[N];
	int *array2 = new int[K];
	
	for (int i = 0; i < N; i++)
	{
		cin >> array[i];
	}
	sort(array, array + N);
	int ANS = 0;
	for (int i = 0; i < K; i++)
	{
		ANS += array[i];
	}
	cout << ANS;

	delete[] array; 
	delete[] array2;

}

Measured memory_bytes: 3096
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstdlib>
using namespace std;
#define INF 1e9

static const int seed=6;
static const int D=365;
static const int ntype=26;
static int ans[D+1];
static int max_score=-INF;
static int t=105000;
class Contest{
public:
    Contest(){
        last=0;
    }
    int s[D+1];
    int c;
    int last;
};

static Contest contest[ntype+1];

void Input(){
    int d;
    cin>>d;
    for(int i=1;i<=ntype;++i){
        int t;
        cin>>t;
        contest[i].c=t;
    }
    for(int day=1;day<=D;++day){
        for(int type=1;type<=ntype;++type){
            int t;
            cin>>t;
            contest[type].s[day]=t;
        }
    }
}

int evaluate(){
    int sum=0;
    vector<int> l(ntype+1,0);
    for(int day=1;day<=D;++day){
        int type=ans[day];
        sum+=contest[type].s[day];
        l[type]=day;
        for(int t=1;t<=ntype;++t){
            sum-=contest[t].c*(day-l[t]);
        }
    }
    return sum;   
}

void Output(){
    for(int d=1;d<=D;++d) cout<<ans[d]<<endl;
}

void Init(){
    for(int d=1;d<=D;++d) ans[d]=rand()%ntype+1;
}

void Greedy(){
    vector<int> l(ntype+1,0);
    int score=0;
    for(int d=1;d<=D;++d){
        for(int i=1;i<=ntype;++i) score-=contest[i].c*(d-l[i]);
        int temp=score;
        int t=-1;
        for(int i=1;i<=ntype;++i){
            int k=contest[i].s[d]+contest[i].c*(d-l[i])+score;
            if(k>temp){
                temp=k;
                t=i;
            }
        }
        ans[d]=t;
        l[t]=d;
    }
}

void change(){
    int p=rand()%D+1;
    int temp=ans[p];
    ans[p]=rand()%ntype+1;
    int temp_score=evaluate();
    if(max_score<temp_score) max_score=temp_score;
    else ans[p]=temp;
}

void swap(){
    int p1=rand()%D+1;
    int p2=rand()%D+1;
    while(p1==p2) p2=rand()%D+1;
    int temp=ans[p1];
    ans[p1]=ans[p2];
    ans[p2]=temp;
    int temp_score=evaluate();
    if(max_score<temp_score) max_score=temp_score;
    else{
        ans[p2]=ans[p1];
        ans[p1]=temp;
    }
}

void solve(int times){
    max_score=evaluate();
    for(int i=0;i<times;++i){
        swap();
        change();
    }
}

int main(){
    srand(seed);
    Input();
    Greedy();
    solve(t);
    Output();
}


Measured memory_bytes: 3660
#include<cstdio>
#include<iostream>
#include<string>
#include<set>
#include<map>
#include<vector>
#include<deque>
#include<tuple>
#include<algorithm>
#include<numeric>
#include<limits>
#include<boost/multiprecision/cpp_int.hpp>
using namespace boost::multiprecision;
using namespace std;
#define BEGIN ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define END return EXIT_SUCCESS
#define rep(I,N) for(auto I=0;I<(N);++I)
#define up(I,A,B) for(auto I=(A);I<=(B);++I)
#define dw(I,A,B) for(auto I=(A);I>=(B);--I)
#define all(C) (C).begin(),(C).end()
#define rall(C) (C).rbegin(),(C).rend()
#define ft first
#define sd second
#define mp make_pair
#define mt make_tuple
#define pf push_front
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define rs resize
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
template<class T>inline bool chmax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
template<class T>inline bool chmin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<class T>inline void                                      in(T &p){cin>>p;}
template<class T1,class T2>inline void                            in(T1 &p1,T2 &p2){cin>>p1>>p2;}
template<class T1,class T2,class T3>inline void                   in(T1 &p1,T2 &p2,T3 &p3){cin>>p1>>p2>>p3;}
template<class T1,class T2,class T3,class T4>inline void          in(T1 &p1,T2 &p2,T3 &p3,T4 &p4){cin>>p1>>p2>>p3>>p4;}
template<class T1,class T2,class T3,class T4,class T5>inline void in(T1 &p1,T2 &p2,T3 &p3,T4 &p4,T5 &p5){cin>>p1>>p2>>p3>>p4>>p5;}
template<class T>inline void                                      ins(T &p){for_each(all(p),in<decltype(p[0])>);}
template<class T>inline void                             out(T p){cout<<p<<endl;}
template<class T1,class T2>inline void                   out(T1 p1,T2 p2){cout<<p1<<" "<<p2<<endl;}
template<class T1,class T2,class T3>inline void          out(T1 p1,T2 p2,T3 p3){cout<<p1<<" "<<p2<<" "<<p3<<endl;}
template<class T1,class T2,class T3,class T4>inline void out(T1 p1,T2 p2,T3 p3,T4 p4){cout<<p1<<" "<<p2<<" "<<p3<<" "<<p4<<endl;}
inline                                              void out(double p){printf("%.10f\n",p);}
template<class T>inline                             void outs(T p){for_each(all(p),out<decltype(p[0])>);}
template<class T>inline void outs(vector<T> V){int n=V.size();rep(i,n)cout<<V[i]<<" \n"[i==n-1];}
vector<long>r;
void rec(long n,long d,long l){
  if(l==11)return;
  for(int i=max(d-1,0L);i<=min(d+1,9L);i++){
    long t=n;
    t*=10;
    t+=i;
    r.pb(t);
    rec(t,i,l+1);
  }
}
inline void solve(void){
  int K;in(K);
  up(i,1,9){
    r.pb(i);
    rec(i,i,2);
  }
  sort(all(r));
  out(r[K-1]);
}
int main(int argc,char**argv){
  BEGIN;
  solve();
  END;
}


Measured memory_bytes: 2420
from math import gcd

class SegmentTree:
    """Segment Tree

    Attributes:
        n (int):       要素数
        num (int):     n以上の最小の2の累乗
        ide_ele (int): 単位元
            - RmQ(Range Minimum Query): inf
            - RMQ(Range Maximum Query): -1
            - RSQ(Range Sum Query):     0
            - RPQ(Range Product Query): 1
            - RGQ(Range GCD Query):     0
        seg (list):    要素の格納先
    """
    def __init__(self, a):
        """初期化 O(N)
        
        Args:
            a (list): 対象の配列
        """
        self.n = len(a)
        self.num = 2 ** (self.n - 1).bit_length()
        self.ide_ele = 0
        self.seg = [self.ide_ele] * (2*self.num-1)

        for i in range(self.n):
            self.seg[self.num+i-1] = a[i]    
        for i in range(self.num-2, -1, -1) :
            self.seg[i] = self.st_func(self.seg[2*i+1], self.seg[2*i+2])

    def query(self, l, r):
        """区間クエリの計算 O(logN)

        Args:
            l (int): 区間の左端
            r (int): 区間の右端
        
        Returns:
            int: [l, r)についての区間クエリ
        """
        if r <= l:
            return self.ide_ele
        
        l += self.num - 1
        r += self.num - 2
        res = self.ide_ele

        while r - l > 1:
            if l % 2 == 0:
                res = self.st_func(res, self.seg[l])
            if r % 2 == 1:
                res = self.st_func(res, self.seg[r])
                r -= 1
            l = l // 2
            r = (r - 1) // 2
        
        if l == r:
            res = self.st_func(res, self.seg[l])
        else:
            res = self.st_func(res, self.st_func(self.seg[l], self.seg[r]))
        
        return res

    def update(self, i, v):
        """値の更新 O(logN)

        Args:
            i (int): 更新対象のindex
            v (int): 更新値
        """
        i += self.num - 1
        self.seg[i] = v
        while i > 0:
            i = (i - 1) // 2
            self.seg[i] = self.st_func(self.seg[i*2+1], self.seg[i*2+2])
    
    def st_func(self, x, y):
        """問題に応じた処理

        Returns:
            int: 問題に応じた値
                - RmQ(Range Minimum Query): min(x, y)
                - RMQ(Range Maximum Query): max(x, y)
                - RSQ(Range Sum Query):     x + y
                - RPQ(Range Product Query): x * y
                - RGQ(Range GCD Query):     gcd(x, y)
        """
        return gcd(x, y)


n = int(input())
a = list(map(int, input().split()))

st = SegmentTree(a)

res = 0
for i in range(n):
    res = max(res, gcd(st.query(0, i), st.query(i+1, n)))

print(res)

Measured memory_bytes: 84692
#include<stdio.h>
#include<stdlib.h>
#define NIL NULL

struct node{
  struct node *right;
  struct node *left;
  struct node *parent;
  int key;
};
typedef struct node * Node;
Node root;

Node treeMinimum(Node x){
  while(x->left != NIL){
    x = x->left;
  }
  return x;
}

Node treeMaximum(Node x){
  while(x->right != NIL){
    x = x->right;
  }
  return x;
}

Node treeSearch(Node u,int k){
  if(u == NIL || k == u->key) return u;
  if(k < u->key) return treeSearch(u->left,k);
  else return treeSearch(u->right,k);
}

Node treeSuccessor(Node x){
  Node y;
  if(x->right != NIL) return treeMinimum(x->right);
  y = x->parent;
  while(y != NIL && x == y->right){
    x = y;
    y = y->parent;
  }
  return y;
}

void treeDelete(Node z){
  Node y;
  Node x;
  if(z->left == NIL || z->right == NIL) y = z;
  else y = treeSuccessor(z);
  if(y->left != NIL) x = y->left;
  else x = y->right;
  if(x != NIL) x->parent = y->parent;
  if(y->parent == NIL) root = x;
  else if(y == y->parent->left) y->parent->left = x;
  else y->parent->right = x;
  if(y != z) z->key = y->key;
}

void insert(int k){
  Node y = NIL;
  Node x = root;
  Node z;

  z = malloc(sizeof(struct node));
  z -> key = k;
  z -> left = NIL;
  z -> right = NIL;

  while(x != NIL){
    y = x;
    if(z->key < x->key) x = x->left;
    else x = x->right;
  }
  z->parent = y;
  if(y == NIL) root = z;
  else if(z->key < y->key) y->left = z;
  else y->right = z;
}

void inorder(Node u){
  if(u == NIL) return;
    inorder(u->left);
    printf(" %d",u->key);
    inorder(u->right);
}


void preorder(Node u){
  if(u == NIL) return;
    printf(" %d",u->key);
    preorder(u->left);
    preorder(u->right);
}

int main(){
  int n,i,x;
  char com[20];
  scanf("%d",&n);

  for ( i = 0; i < n; i++ ){
    scanf("%s", com);
    if ( com[0] == 'f' ){
      scanf("%d", &x);
      Node t = treeSearch(root, x);
      if ( t != NIL ) printf("yes\n");
      else printf("no\n");
    } else if ( com[0] == 'i' ){
      scanf("%d", &x);
      insert(x);
    } else if ( com[0] == 'p' ){
      inorder(root);
      printf("\n");
      preorder(root);
      printf("\n");
    } else if ( com[0] == 'd' ){
      scanf("%d", &x);
      treeDelete(treeSearch(root, x));
    }
  }

  return 0;
}



Measured memory_bytes: 20460
#include <bits/stdc++.h>
using namespace std;
 
typedef long double ld;
typedef pair<ld, int> ld_i;
 
int main() {
    ld PI = acosl(-1);
    int N; cin >> N;
    vector<int> x(N), y(N);
    for (int i = 0; i < N; i++)
        cin >> x[i] >> y[i];
    for (int k = 0; k < N; k++) {
        vector<ld_i> v;
        for (int i = 0; i < N; i++) {
            if (i == k) continue;
            ld a = atan2l(x[i] - x[k], y[i] - y[k]);
            v.push_back(ld_i(a, i < k));
        }
        int n = v.size();
        sort(v.begin(), v.end());
        for (int i = 0; i < n; i++) {
            v.push_back(v[i]);
            v.back().first += PI*2;
        }
        int a = 0, b = 0, j = 0;
        bool ok = false;
        for (int i = 0; i < n; i++) {
            for (; v[j].first < v[i].first + PI; j++)
                if (v[j].second) a++;
                else b++;
            if ((a == k && b == 0) || (a == 0 && b == N - 1 - k))
                ok = true;
            if (v[i].second) a--;
            else b--;
        }
        if (!ok) {
            cout << "Impossible" << endl;
            return 0;
        }
    }
    cout << "Possible" << endl;
}


Measured memory_bytes: 3284
#include<bits/stdc++.h>
#define V vector
#define VI vector<int>
#define VVI vector<vector<int>>
#define REP(i,n) for(int i=0;i<(n);i++)
#define REPR(i,n) for(int i=n;i>=0;i--)
#define FOR(i,m,n) for(int i=m;i<n;i++)
#define MOD 1000000007
#define INF 1e9
#define F first
#define S second
#define All(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;

int main(void){
    int N,K,ans=0;
    cin>>N>>K;
    REP(i,N){
        int a;cin>>a;
        if(a>=K)ans++;
    }
    cout<<ans<<endl;

}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define int long long
using namespace std;
constexpr int inf=1e9+7;
signed main(){
    int a,b,k;
    cin>>a>>b>>k;
    cout<<max(0ll,a-k)<<' '<<max(0ll,b-max(0ll,k-a))<<endl;
}


Measured memory_bytes: 256