akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
int n,m,rt,sz,val[888888],son[888888][3],tag[888888],ans[888888],all;
char s[222222];
void build(int &nw,int c,int dep,int sum)
{
	nw=++sz;
	if (dep==n)
	{
		val[nw]=sum;
		return;
	}
	build(son[nw][0],c*3,dep+1,sum);
	build(son[nw][1],c*3,dep+1,sum+c);
	build(son[nw][2],c*3,dep+1,sum+2*c);
}
void push(int node)
{
	swap(son[node][1],son[node][2]);
	tag[node]^=1;
}
void pushdown(int node)
{
	if (tag[node])
	{
		push(son[node][0]);
		push(son[node][1]);
		push(son[node][2]);
		tag[node]=0;
	}
}
void go(int nw,int dep)
{
	if (dep==n) return;
	pushdown(nw);int s1=son[nw][0],s2=son[nw][1],s3=son[nw][2];
	son[nw][0]=s3;son[nw][1]=s1;son[nw][2]=s2;
	go(son[nw][0],dep+1);
}
void cal(int nw,int c,int dep,int sum)
{
	if (dep==n)
	{
		ans[val[nw]]=sum;
		return;
	}
	pushdown(nw);
	cal(son[nw][0],c*3,dep+1,sum);
	cal(son[nw][1],c*3,dep+1,sum+c);
	cal(son[nw][2],c*3,dep+1,sum+2*c);
}
int main()
{
	scanf("%d",&n);
	scanf("%s",s);
	m=strlen(s);
	build(rt,1,0,0);
	for (int i=0;i<m;i++)
	{
		if (s[i]=='S')
		{
			push(rt);
		}
		else
		{
			go(rt,0);
		}
	}
	cal(rt,1,0,0);
	all=1;
	for (int i=1;i<=n;i++) all*=3;
	for (int i=0;i<all;i++) printf("%d ",ans[i]);
	printf("\n");
	return 0;
}

Measured memory_bytes: 21856
#include<stdio.h>
#define MAX 2000000
void maxHeapify(int);
int H,A[MAX+1];
int main(){
  int i;
  scanf("%d",&H);
  for(i=1;i<=H;i++)
    scanf("%d",&A[i]);
  for(i=H/2;i>=1;i--)
    maxHeapify(i);
  for(i=1;i<=H;i++)
    printf(" %d",A[i]);
  printf("\n");
  return 0;
}

void maxHeapify(int i){
  int l,r,largest,a;
  l=i*2;
  r=i*2+1;
  // 左の子、自分、右の子で値が最大のノードを選ぶ
  if(l <= H && A[l] > A[i])
    largest=l;
  else largest=i;
  if(r <= H && A[r] > A[largest])
    largest=r;
  if(largest != i) // i の子の方が値が大きい場合
    {
      a=A[i];
      A[i]=A[largest];
      A[largest]=a;
      maxHeapify(largest);
    }
}


Measured memory_bytes: 3752
s = list(input())
n = len(s)
result = 'Yes'
for i in range(n):
  if s[i] != s[n- 1 - i]:
    result = 'No'

for i in range(n):
  if i > (n - 1) // 2 - 1:
    break
  if s[i] != s[(n-1)//2 - 1 - i]:
    result = 'No'

for i in range(n):
  if (n+3)//2 - 1 >= i:
    pass
  if s[i] != s[n-1-i]:
    result = 'No'
print(result)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
int n;
int a[233];
int main(){
    cin>>n;
    for(int i=1;i<=2*n;i++){
        cin>>a[i];
    }
    sort(a+1,a+2*n+1);
    int sum=0;
    for(int i=1;i<=2*n;i++){
        if(i%2)
            sum+=a[i];
    }
    cout<<sum;
    return 0;
}


Measured memory_bytes: 256
// vvvvvvvvvvvv TEMPLATE vvvvvvvvvvvv
#include <bits/stdc++.h>
using namespace std; using ll = long long; using P = pair<ll, ll>;
const ll linf = 1e18; const double eps = 1e-12, pi = acos(-1);
#define FOR(i,a,b) for (ll i=(a),__last_##i=(b);i<__last_##i;i++)
#define RFOR(i,a,b) for (ll i=(b)-1,__last_##i=(a);i>=__last_##i;i--)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define __GET_MACRO3(_1, _2, _3, NAME, ...) NAME
#define each(i,a) for (auto&& i : a)
#define rep(...) __GET_MACRO3(__VA_ARGS__, FOR, REP)(__VA_ARGS__)
#define rrep(...) __GET_MACRO3(__VA_ARGS__, RFOR, RREP)(__VA_ARGS__)
#define pb push_back
#define eb emplace_back
#define all(a) begin(a),end(a)
#define chmin(x,v) x = min(x, v)
#define chmax(x,v) x = max(x, v)
#define min(x,y) (x < y ? x : y)
#define max(x,y) (x < y ? y : x)
template<typename Head> void out(Head h) { cout << h << endl; } template<typename Head, typename... Tail>void out(Head h, Tail... t) { cout << h << " "; out(t...); }
template<typename T> istream& operator>>(istream& is, vector<T>& v) { each(x,v) is >> x; return is; }
template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) { rep(i,v.size()) { if (i) os << " "; os << v[i]; } return os; }
template<typename T> ostream& operator<<(ostream& os, const vector<string>& v) { rep(i,v.size()) { if (i) os << endl; os << v[i]; } return os; }
template<typename T> ostream& operator<<(ostream& os, const vector<vector<T>>& v) { rep(i,v.size()) { if (i) os << endl; os << v[i]; } return os; }
struct yes_no : std::numpunct<char> { string_type do_truename() const { return "Yes"; } string_type do_falsename() const { return "No"; } };
void solve(); int main() {
  ios::sync_with_stdio(false); cin.tie(0); locale loc(locale(), new yes_no); cout.imbue(loc); cout << fixed << setprecision(10) << boolalpha;
  solve();
}
// ^^^^^^^^^^^^ TEMPLATE ^^^^^^^^^^^^

string S, T;
ll n, m;

bool m1[4010][4010] = {0};
ll m2[4010][4010];
ll nxtS[4010][2];
ll nxtT[4010][2];

P forward(ll i, ll j, ll k) {
  return P(nxtS[i][k], nxtT[j][k]);
}

ll dp(ll i, ll j) {
  if (m1[i][j]) return m2[i][j];
  if (i == n+1 && j == m+1) return 0;
  ll res = linf;
  rep(k, 2) {
    P p = forward(i, j, k);
    ll ni, nj; tie(ni, nj) = p;
    if (ni < 0) {
      res = 1;
      break;
    }
    chmin(res, dp(ni, nj)+1);
  }
  return m1[i][j] = true, m2[i][j] = res;
}

void solve() {
  cin >> S >> T;
  n = S.size(), m = T.size();
  rep(i, n+2) rep(j, 2) nxtS[i][j] = n+1;
  rep(i, m+2) rep(j, 2) nxtT[i][j] = m+1;
  rep(i, n) nxtS[i][S[i]-'0'] = i+1;
  rep(i, m) nxtT[i][T[i]-'0'] = i+1;
  rrep(i, n) rep(j, 2) chmin(nxtS[i][j], nxtS[i+1][j]);
  rrep(i, m) rep(j, 2) chmin(nxtT[i][j], nxtT[i+1][j]);
  const ll ans = dp(0, 0);
  // cout << ans << endl;
  string astr = "";
  ll i = 0, j = 0;
  rep(t, ans) rep(k, 2) {
    P p = forward(i, j, k);
    ll ni, nj; tie(ni, nj) = p;
    if (dp(ni, nj) == ans-t-1) {
      astr += char(k+'0');
      i = ni, j = nj;
      break;
    }
  }
  cout << astr << endl;
}



Measured memory_bytes: 99160
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.List;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.stream.Stream;

import java.util.Set;
import java.util.HashSet;

public class Main {

    private static Set<String> ans;
    private static ArrayList<Integer> arr;

    private static void hasArrayTwoCandidates(ArrayList<Integer> a, int arSize, int sum, int x) {
    Integer l = 0;
    Integer r = arSize - 1;

    while (l<r) {
        if (a.get(l) + a.get(r) == sum &&
        a.get(l)!=a.get(r) &&
        a.get(l)!=(x-sum)  &&
        a.get(r)!=(x-sum)
        ) {
        arr = null;
        arr = new ArrayList<Integer>();
        arr.add(x - sum);
        arr.add(a.get(l));
        arr.add(a.get(r));
        Collections.sort(arr);
        ans.add(arr.toString());
        //System.out.println(arr.toString());
        l++;
        } else if (a.get(l) + a.get(r) < sum) {
        l++;
        } else {
        r--;
        }
    }
    return;
    }

    public static void main(String[] args) {
    try {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        List<String> lines = new ArrayList<String>();
        String line = "";

        while((line = br.readLine()) != null){
        lines.add(line);
        }
        br.close();

        //lines.add("5 9");
        //lines.add("0 0");
        //lines.add("100 100");
        //lines.add("100 200");
        //lines.add("100 297");
        //lines.add("0 0");

        for (String e:lines) {
        if (e.equals("0 0")) {
            break;
        } else {
            int initial = Integer.parseInt(e.split(" ")[0]);
            ArrayList<Integer> n = new ArrayList<Integer>();
            for (Integer i = 1; i < initial+1; i++) {
            n.add(i);
            }
            Integer x = Integer.parseInt(e.split(" ")[1]);

            ans = null;
            ans = new HashSet<String>();
            for (Integer t : n) {
            hasArrayTwoCandidates(n, n.size(), x - t, x);
            }

            //for (String ansstr : ans) {
            //  System.out.println(ansstr);
            //};

            //Collections.sort(ans);
            System.out.println(ans.size());
        }
        }

        System.exit(0);

    } catch (Exception e) {
        System.out.println(e.getMessage());
        System.out.println(Arrays.toString(e.getStackTrace()));
        System.exit(0);
    }
    }
}


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

using namespace std;
typedef long long lint;

int main()
{
	int n;
	lint tbl[128][128];
	lint sum[128][128] = {0};
	
	scanf("%d", &n);
	
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			scanf("%lld", &tbl[i][j]);
	
	for (int i = 0; i < n; i++){
		for (int j = 0; j < n; j++){
			sum[i][j] += tbl[i][j];
			if (i) sum[i][j] += sum[i - 1][j];
			if (j) sum[i][j] += sum[i][j - 1];
			if (i && j) sum[i][j] -= sum[i - 1][j - 1];
		}
	}
	
	lint ma = -10000;
	
	for (int y1 = 0; y1 < n; y1++){
		for (int y2 = y1; y2 < n; y2++){
			lint trv = -10000;
			for (int x = 0; x < n; x++){
				lint v = sum[y2][x] - (x ? sum[y2][x - 1] : 0) - (y1 ? sum[y1 - 1][x] : 0) + (x && y1 ? sum[y1 - 1][x - 1] : 0);
				trv = max(trv + v, v);
				ma = max(ma, trv);
			}
		}
	}
	
	printf("%lld\n", ma);
	
	return (0);
}

Measured memory_bytes: 1268
class CSR:
    def __init__(self, n: int, edges: list):
        self.start = [0] * (n+1)
        self.elist = [0] * len(edges)
        for e in edges:
            self.start[e[0]+1] += 1
        
        for i in range(1, n+1):
            self.start[i] += self.start[i-1]
        
        counter = self.start[::] # copy
        for e in edges:
            self.elist[counter[e[0]]] = e[1]
            counter[e[0]] += 1


class SccGraph:
    def __init__(self, n: int = 0):
        self.__n = n
        self.__edges = []
    
    def __len__(self):
        return self.__n
    
    def add_edge(self, s: int, t: int):
        assert 0 <= s < self.__n and 0 <= t < self.__n
        self.__edges.append([s, t])
    
    def __scc_ids(self):
        g = CSR(self.__n, self.__edges)
        now_ord = group_num = 0
        visited = []
        low = [0] * self.__n
        order = [-1] * self.__n
        ids = [0] * self.__n
        parent = [-1] * self.__n
        for root in range(self.__n):
            if order[root] == -1:
                stack = [root, root]
                while stack:
                    v = stack.pop()
                    if order[v] == -1:
                        visited.append(v)
                        low[v] = order[v] = now_ord
                        now_ord += 1
                        for i in range(g.start[v], g.start[v+1]):
                            t = g.elist[i]
                            if order[t] == -1:
                                stack += [t, t]
                                parent[t] = v
                            else:
                                low[v] = min(low[v], order[t])
                    
                    else:
                        if low[v] == order[v]:
                            while True:
                                u = visited.pop()
                                order[u] = self.__n
                                ids[u] = group_num
                                if u == v:
                                    break
                                
                            group_num += 1
                        
                        if parent[v] != -1:
                            low[parent[v]] = min(low[parent[v]], low[v])
        
        for i, x in enumerate(ids):
            ids[i] = group_num - 1 - x
        
        return group_num, ids
    
    def scc(self):
        group_num, ids = self.__scc_ids()
        counts = [0] * group_num
        for x in ids:
            counts[x] += 1
        
        groups = [[] for _ in range(group_num)]
        for i, x in enumerate(ids):
            groups[x].append(i)
        
        return groups


N, M = map(int, input().split())
sg = SccGraph(N)

for _ in range(M):
    a, b = map(int, input().split())
    sg.add_edge(a, b)

scc = sg.scc()
print(len(scc))
for group in scc:
    print(*([len(group)] + group))

Measured memory_bytes: 203888
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <string>
#include <queue>
#include <fstream>
#include <string>
#include <math.h>
#include <set>
#include <string>
#include <bitset>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
//typedef pair<ll, P> T;

#define rep(i, n) for (ll i = 0; i < (n); i++)
#define revrep(i, n) for (ll i = (n) - 1; i >= 0; i--)
#define f first
#define s second
#define pb push_back

ll mod = 1000000007;
const ll INF = 100000000000010000;
//const ull B = 998244353;

//ll bit[200010];
//ll kai[3010];
//ll Cnt[10010];

//void pres(double A, ll x = 20) { printf("%.20f\n", x); }



/*ll sum(ll i)
{
	i += 1;
	ll t = 0;
	while (i > 0)
	{
		t += bit[i];
		i -= i & -i;
	}
	return t;
}

void add(ll i, ll x)
{
	i += 1;
	while (i <= 200005)
	{
		bit[i] += x;
		i += i & -i;
	}
}*/

/*`ll SAIKI(ll S) {
	for (ll T = S; ; T = (T - 1) & S) {

	}
}*/



void test() {
	cout << "888888888888888888888888" << endl;
}

ll gcd(ll x, ll y) {
	if (y == 0) return x;
	return gcd(y, x % y);
}

ll pow_mod(ll x, ll k) {
	x %= mod;
	ll res = 1;
	while (k > 0) {
		if (k % 2) {
			res *= x; res %= mod;
		}
		x *= x; x %= mod;
		k /= 2;
	}
	return res;
}

ll div_mod(ll x) {
	return pow_mod(x, mod - 2);
}

//コンビネーション
const int MAXcomb = 200010;
ll fac[MAXcomb], finv[MAXcomb], inv[MAXcomb];
//facはn!,finvは1/n!
//invは逆元
void COMinit() {
	fac[0] = fac[1] = 1;
	finv[0] = finv[1] = 1;
	inv[1] = 1;
	for (int i = 2; i < MAXcomb; i++) {
		fac[i] = fac[i - 1] * i % mod;
		inv[i] = mod - inv[mod%i] * (mod / i) % mod;
		finv[i] = finv[i - 1] * inv[i] % mod;
	}
}
ll comb(int n, int k) {
	if (n < k) return 0;
	if (n < 0 || k < 0) return 0;
	return fac[n] * finv[k] % mod * finv[n - k] % mod;
}


/*map<ll, ll> pres;
ll ct;

void makePrimeList(ll x) {
	ll X = x;
	for (ll j = 2; j * j <= x; j++) {
		ll cnt = 0;
		while (X % j == 0) {
			cnt++;
			X /= j;
		}
		if (cnt) {
			if (pres[j] == 0) {
				ct++;
				pres[j] = ct;
			}
			Cnt[pres[j]] += cnt;
		}
	}
	if (X != 1) {
		if (pres[X] == 0) {
			ct++;
			pres[X] = ct;
		}
		Cnt[pres[X]] += 1;
	}
}*/

ll N, K;
double p[200010], sum[200010], ans;

void solve() {
	cin >> N >> K;
	rep(i, N) {
		cin >> p[i];
		sum[i + 1] = sum[i] + (p[i] + 1) / 2;
	}
	rep(i, N) {
		if (i + K > N) break;
		ans = max(ans, sum[i + K] - sum[i]);
	}
	printf("%.10lf\n", ans);
}

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	solve();
	ll N;
	cin >> N;
}

Measured memory_bytes: 4352
#include <bits/stdc++.h>
#define rep(i,n) for(int64_t i=0;i < (int64_t)(n);i++)
#define invrep(i,n) for(int64_t i=n-1;i >= 0L;i--)
#define prep(i,n) for(int64_t i=1;i <= (int64_t)(n);i++)
using namespace std;

//////全探索したいときに開けよ////////
vector<vector<int>> fspattern;
vector<int> fspattern_draft;
int fspcnt = 0;

void setfspattern_core(int floor,int number,int degree){
  if(floor==degree){
    fspattern.at(fspcnt) = fspattern_draft;
    fspcnt++;
  }else{
    rep(i,number){
      fspattern_draft.at(floor) = i;
      setfspattern_core(floor+1,number,degree);
    }
  }
}

void setfspattern(int number,int degree){
  int64_t array_num = 1;
  fspcnt = 0;
  rep(i,degree){
    array_num *= number;
  }
  fspattern = vector<vector<int>>(array_num,vector<int>(degree));
  fspattern_draft = vector<int>(degree);
  setfspattern_core(0,number,degree);
}

//////nCrのmodを求めたいときに開けよ/////////
//int64_t univMod = 1000000007;
//int64_t factnum = 100000
//vector<int64_t> modfact(factnum);
//vector<int64_t> modinvfact(factnum);

/*void setmodfact(){
  for(int i=0;i<factnum;i++){
    if(i == 0){
      modfact.at(i) = 1;
    }else{
      modfact.at(i) = (modfact.at(i-1)*i)%univMod;
    }
  }
}

int64_t calcmodpower(int64_t a,int64_t n){
  int64_t res = 1;
  while(n != 0){
    if(n & 1){
      res = (res * a) % univMod;
    }
    a = (a*a) % univMod;
    n = n >> 1;
  }
  return res;
}

int64_t calcinverse(int64_t n){
	return calcmodpower(n,univMod-2);
}

void setmodinvfact(){
  for(int i=0;i<factnum;i++){
    if(i==0){
      modinvfact.at(i) = 1;
    }else{
      modinvfact.at(i) = calcmodpower(modfact.at(i),univMod-2);
    }
  }
}

int64_t calcmodcomb(int64_t n,int64_t r){
  return (((modfact.at(n)*modinvfact.at(r))%univMod)*modinvfact.at(n-r))%univMod;
}

int64_t calcmodpositive(int64_t n){
  return (n + ((abs(n)+univMod-1)/univMod)*univMod)%univMod;
}
  
    */


/*
int64_t calcGCD(int64_t a,int64_t b){
	int64_t p = a;
	int64_t q = b;
	int64_t c = a%b;
	while(c != 0){
		p = q;
		q = c;
		c = p%q;
	}
	return q;
}
*/

int main(){
  int n,m;
  cin >> n >> m;
  vector<int> x(m),y(m),z(m);
  vector<vector<int>> conn(n);
  rep(i,m){
    cin >> x.at(i) >> y.at(i) >> z.at(i);
    conn.at(x.at(i)-1).push_back(y.at(i)-1);
    conn.at(y.at(i)-1).push_back(x.at(i)-1);
  }
  
  vector<int> belonging(n);
  int belongingcnt = 0;
  queue<int> que;
  
  rep(i,n){
    if(belonging.at(i) == 0){
      belongingcnt++;
      que.push(i);
      while(!que.empty()){
        int hoge = que.front();
        belonging.at(hoge) = belongingcnt;
        rep(j,conn.at(hoge).size()){
          if(belonging.at(conn.at(hoge).at(j)) == 0){
            que.push(conn.at(hoge).at(j));
          }
        }
        que.pop();
      }
    }
  }
  cout << belongingcnt << endl;
  
  
  
  
    
}

Measured memory_bytes: 8056
#include <bits/stdc++.h>
using namespace std;
#define mod 100000007
#define SIZE 500006
vector<int>A;

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

      int t,i,n,a,b,sum=0,j,count=0;
      cin>>t;
      for(i=0;i<t;i++)
      {
          cin>>a;
          A.push_back(a);
      }

        n=A.size();

     sort(A.begin(), A.end());



    for( int i = n-1; i >= 1; i--){
        int l = 0, r = i-1;
        while( l < r){
            if( A[l] + A[r] > A[i]){

                count += r - l ;


                r--;
            }
            else


                l++;
        }
    }

     cout<<count<<"\n";

    return 0;
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
#define Rep(i,n) for(int i=0;i<n;i++)
#define For(i,n1,n2) for(int i=n1;i<n2;i++)
#define REP(i,n) for(ll i=0;i<n;i++)
#define FOR(i,n1,n2) for(ll i=n1;i<n2;i++)
#define put(a) cout<<a<<endl;
#define all(a)  (a).begin(),(a).end()
#define SORT(c) sort((c).begin(),(c).end())
#define TDARRAY(int,a,n,m) vector<vector<int>> a(n,vector<int>(m,0));
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
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 n,m;

class UnionFind{
private:
    vector<int> par,height,size;
public:
    UnionFind(int n){
        par.resize(n);
        REP(i,n){
            par[i] = i;
        }
        height.resize(n,0);
        size.resize(n,1);
    }
    int root(int x){
        if(par[x]==x){
            return x;
        }else{
            par[x] = root(par[x]);
            return par[x];
        }
    }
    bool same(int x,int y){
        return root(x)==root(y);
    }
    void unite(int x,int y){
        x = root(x);
        y = root(y);
        if(x==y)return;
        if(height[x]<height[y]){
            par[x]=y;
            size[y]+=size[x];
        }else{
            par[y]=x;
            size[x]+=size[y];
            if(height[x]==height[y])height[x]++;
        }
    }
    int cnt(int x){
        x=root(x);
        return size[x];
    }
};

int main(){
    cin >> n >> m;
    vector<int> p(m);
    vector<int> a(m);
    vector<int> b(m);
    
    REP(i,m){
        cin >> a[i] >> b[i];
        a[i]--;
        b[i]--;
    }
    vector<ll> res(m);
    res[m-1]=(ll)n*(n-1)/2;
    
    UnionFind uf(n);
    for(int i=m-1;i>=1;--i){
        int r1 = uf.root(a[i]);
        int r2 = uf.root(b[i]);
        if(r1!=r2){
            res[i-1] = res[i]-(ll)uf.cnt(a[i])*uf.cnt(b[i]);
            uf.unite(a[i],b[i]);
        }else{
            res[i-1] = res[i];
        }
    }
    REP(i,m){
        put(res[i]);
    }
    return 0;
}


Measured memory_bytes: 4480
N, M = map(int, input().split())
P = []
s = []
for i in range(M):
    p, S = input().split()
    p = int(p) - 1
    P.append(p)
    s.append(S)
A = [[0, 0] for _ in range(N)]
for i in range(M):
    if s[i] == 'AC':
        A[P[i]][0] = 1
    if s[i] == 'WA' and A[P[i]][0] != 1:
        A[P[i]][0] = 2
        A[P[i]][1] += 1

print(len([a for a in A if a[0] == 1]), sum([a[1] for a in A if a[0] == 1]))


Measured memory_bytes: 76248
#include <bits/stdc++.h>
#include <vector>
#include <queue>
#include <iostream>
#include <iomanip>
using namespace std;
typedef long long LL;
#define REP(i,n) for(int i=0;i<n;i++)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)

LL gcd(LL val1, LL val2);

int main(){
    LL A, B, C, D;
    cin >> A >> B >> C >> D;

    LL min_gcd = 0;
    if(C < D){
        min_gcd = gcd(C, D);
    }else{
        min_gcd = gcd(D, C);
    }
    LL common = min_gcd * (C/min_gcd) * (D/min_gcd);

    LL count_1 = B - (B/C) - (B/D) + (B/(common));
    LL count_2 = (A-1) - ((A-1)/C) - ((A-1)/D) + ((A-1)/(common));

    LL ans = count_1 - count_2;
    cout << ans << endl;
    return 0;


}

LL gcd(LL min_val, LL max_val){
    LL r = max_val % min_val;
    if(r == 0){
        return min_val;
    }
    return gcd(r, min_val);
}

Measured memory_bytes: 3612
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define fi first
#define se second
#define UP(a,b,c) for(ll (a)=(b);(a)<(c);(a)++)
#define UU(a,b,c) for(ll (a)=(b);(a)<=(c);(a)++)
#define DN(a,b,c) for(ll (a)=(b);(a)>(c);(a)--)
#define DU(a,b,c) for(ll (a)=(b);(a)>=(c);(a)--)
#define MOD 1000000007

ll n;
pair<ll,ll> p[200005];

void reset()
{
}


void input()
{
	cin>>n;
	UU(i,1,n) cin>>p[i].fi>>p[i].se;
}

/*

xj - xi + yj - yi
xj + yj - xi - yi;

(xj + yj) - (xi + yi);

xj - xi + yi - yj
xj - yj + yi - xi

max((xj + yj) - (xi + yi), (xj - yj) - (xi - yi))
*/

void solve()
{
	ll mnxy = LLONG_MAX;
	ll mnx_y = LLONG_MAX;
	ll mxxy = LLONG_MIN;
	ll mxx_y = LLONG_MIN;
	ll a, b, c, d;
	
	UU(i,1,n)
	{
		ll vxy = p[i].fi + p[i].se;
		ll vx_y = p[i].fi - p[i].se;
		if(mnxy > vxy)
		{
			mnxy = vxy;
			a = i;
		}
		if(mxxy < vxy)
		{
			mxxy = vxy;
			c = i;
		}
		if(mnx_y > vx_y)
		{
			mnx_y = vx_y;
			b = i;
		}
		if(mxx_y < vx_y)
		{
			mxx_y = vx_y;
			d = i;
		}
	}
	cout<<max(abs(p[a].fi - p[c].fi) + abs(p[a].se - p[c].se), abs(p[b].fi - p[d].fi) + abs(p[b].se - p[d].se))<<endl;
}

void LetsRock()
{
	solve();
}

int main()
{
	ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
		
		reset();
		input();
		LetsRock();
	
	return 0;
}

/*

4 5 6 7

*/


Measured memory_bytes: 6752
import java.util.Scanner;

public class Main {
	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		int L = sc.nextInt();
		int R = sc.nextInt();
		int d = sc.nextInt();
		int res = 0;
		for (int i = L; i <= R; i++) {
			if (i % d == 0) {
				res++;
			}
		}
		System.out.println(res);
	}
}

Measured memory_bytes: 35584
#include <algorithm>
#include <iostream>
#include <string>
#include <random>
#include <cassert>
#include <cstring>
#include <chrono>
#include <set>
#include <map>

using namespace std;

typedef long long ll;

int main()
{
  vector<int> a(4);
  for (int i = 0; i < 4; ++i) cin >> a[i];
  sort(a.begin(), a.end());
  cout << (a == vector<int>({1, 4, 7, 9}) ? "YES" : "NO") << endl;
  return 0;
}


Measured memory_bytes: 256
import fractions
a,b,c,d = map(int, input().split())
lcm_cd = (c*d)//fractions.gcd(c,d)
ans = b - (b//c) - (b//d) + (b//lcm_cd)
ans -= (a - 1 - ((a-1)//c) - ((a-1)//d) + ((a-1)//lcm_cd))
print(ans)

Measured memory_bytes: 5048
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int p = Integer.parseInt(sc.next());
        int m = Integer.parseInt(sc.next());
        int c = Integer.parseInt(sc.next());

        System.out.println(p + m + c);
    }
}



Measured memory_bytes: 26136
#include <bits/stdc++.h> 
using namespace std;
typedef long long ll;
typedef pair<ll,ll> p;
const int inf=(1<<30);
#define rep(i,a,n)	for(int i=a;i<n;i++)
#define rrep(i,a,n) for(int i=(a-1);i>=n;i--)
	int main(){
		ll x,n,p[102]={0};
		cin>>x>>n;
		rep(i,0,n){
			ll a;
			cin>>a;
			p[a]=1;
		}
		ll m=inf;
		ll ans=-1;
		rrep(i,102,0){
			if(p[i]==0&&abs(x-i)<=m){
				ans=i;
				m=abs(x-i);
			}
			else continue;
		}
		cout<<ans<<endl;
	}

Measured memory_bytes: 3616
#include <iostream>
#include <cstdlib>
#include <vector>
#include <algorithm>
#include <cstring>
#include <iomanip>
#include <cmath>
#include <tuple>
#include <map>
#include <unordered_map>
#include <queue>
#include <deque>
using namespace std;
typedef long long ll;

int main(int argc, char *argv[])
{
	int n, i;
	int ac, wa, tle, re;
	string tmp;

	ac = wa = tle = re = 0;
	cin >> n;
	for (i = 0; i < n; i++) {
		cin >> tmp;
		if (tmp == "TLE")
			tle++;
		if (tmp == "RE")
			re++;
		if (tmp == "AC")
			ac++;
		if (tmp == "WA")
			wa++;
	}

	cout << "AC x " << ac << endl;
	cout << "WA x " << wa << endl;
	cout << "TLE x " << tle << endl;
	cout << "RE x " << re << endl;
	
	return 0;
}


Measured memory_bytes: 3628
import java.io.IOException
import java.io.InputStream
import java.util.NoSuchElementException

fun main(args: Array<String>) {
    val sc = Scanner(System.`in`)
    val n = sc.nextInt()
    val a = sc.nextIntArray(n)
    println(if (a.any { it % 2 == 1 }) "first" else "second")
}

class Scanner(private val `in`: InputStream) {
    private val buffer = ByteArray(1024)
    private var ptr = 0
    private var buflen = 0

    companion object {
        private fun isPrintableChar(b: Byte): Boolean = b in 33..126
        private fun isNumericChar(b: Byte): Boolean = b in 48..57
        private fun digit(b: Byte): Int = b - 48
    }

    fun hasNextByte(): Boolean {
        if (ptr < buflen) return true
        ptr = 0
        try {
            buflen = `in`.read(buffer)
        } catch (e: IOException) {
            e.printStackTrace()
        }
        return 0 < buflen
    }

    private fun readByte(): Byte = if (hasNextByte()) buffer[ptr++] else -1

    private fun skipUnprintable() {
        while (hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++
    }

    fun hasNext(): Boolean {
        skipUnprintable()
        return hasNextByte()
    }

    fun next(): String {
        if (!hasNext()) throw NoSuchElementException()
        return buildString {
            var b = readByte()
            while (isPrintableChar(b)) {
                appendCodePoint(b.toInt())
                b = readByte()
            }
        }
    }

    fun nextInt(): Int {
        if (!hasNext()) throw NoSuchElementException()
        var n = 0
        var b = readByte()
        val minus = b.toChar() == '-'
        if (minus) b = readByte()
        if (!isNumericChar(b)) throw NumberFormatException()
        do {
            n *= 10
            n += digit(b)
            b = readByte()
        } while (isNumericChar(b))
        return if (minus) -n else n
    }

    fun nextInts(n: Int): Array<Int> = Array(n) { nextInt() }

    fun nextIntArray(n: Int): IntArray = IntArray(n) { nextInt() }

    fun nextIntArrays(n: Int, m: Int): Array<IntArray> {
        val arrays = Array(m) { IntArray(n) }
        repeat(n) { i -> repeat(m) { j -> arrays[j][i] = nextInt() } }
        return arrays
    }

    fun nextLong(): Long {
        if (!hasNext()) throw NoSuchElementException()
        var n = 0L
        var b = readByte()
        val minus = b.toChar() == '-'
        if (minus) b = readByte()
        if (!isNumericChar(b)) throw NumberFormatException()
        do {
            n *= 10
            n += digit(b)
            b = readByte()
        } while (isNumericChar(b))
        return if (minus) -n else n
    }

    fun nextLongs(n: Int): Array<Long> = Array(n) { nextLong() }

    fun nextLongArray(n: Int): LongArray = LongArray(n) { nextLong() }

    fun nextLongArrays(n: Int, m: Int): Array<LongArray> {
        val arrays = Array(m) { LongArray(n) }
        repeat(n) { i -> repeat(m) { j -> arrays[j][i] = nextLong() } }
        return arrays
    }

}

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

int main() {
  int A, B, C, X, cnt=0;
  cin >> A >> B >> C >> X;
  
  for(int i=0; i<=A; i++){
    for(int j=0; j<=B; j++){
      for(int k=0; k<=C; k++){
        if(X == 500*i + 100*j + 50*k)
          cnt++;
      }
    }
  }
  
  cout << cnt << endl;
  
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define X first
#define Y second
#define mp make_pair
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int N = 200010;
int n,x,y;
vector<int> v[N];
bool pd[N],flag;
int d[N];

bool dfs(int x,int fa){
	//cout<<x<<endl;
	int t;
	pd[x] = false;
	for(int i = 0;i<v[x].size();i++) if((t=v[x][i])!=fa){
		dfs(t,x);
		if(!pd[t]) pd[x] =true;
	}
}
bool dfs2(int x,int fa,int s){
	//cout<<x<<endl;
  	int t;
  	int cnt = 0;
	if(s==0) cnt++;
	for(int i = 0;i<v[x].size();i++) if((t=v[x][i])!=fa){
		if(!pd[t]) cnt++;
	}
	if(cnt>=2) flag =true;
	for(int i = 0;i<v[x].size();i++) if((t=v[x][i])!=fa){
		int s2;
		if(cnt-(1-pd[t])>0) s2 = 1; else s2 = 0;
		dfs2(t,x,s2);
	}
  
}
int main(){
	scanf("%d",&n);
	if(n==2){
		puts("Second");
		return 0;
	}
	for(int i =0;i<n-1;i++){
		scanf("%d%d",&x,&y);
		v[x].push_back(y),v[y].push_back(x);
	}
	dfs(1,0);
	flag =false;
	dfs2(1,0,1);
	
	if(flag) puts("First");else puts("Second");
	return 0;
}

Measured memory_bytes: 8320
x, k, d = map(int, input().split())
if x < 0:
    x *= -1
a = x // d
if x == d:
    if k % 2 == 0:
        print(x)
    else:
        print(0)
elif a <= k:
    b = k - a
    if b % 2 == 0:
        print(x % d)
    else:
        c = x % d
        print(min(abs(c + d), abs(c - d)))
else:
    print(x - k * d)


Measured memory_bytes: 9140
var lines = [];
var readline = require('readline');

var rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout,
});

rl.on('line', function (x) {
    lines.push(x);
})

rl.on('close', function () {

    var tmp = lines.shift().split(" ");
    var N = Number(tmp[0]); var Q = Number(tmp[1]);

    var S = lines.shift();

    var l = Array(Q); var r = Array(Q);
    for (var i = 0; i < Q; i++) {
        tmp = lines[i].split(" ");
        l[i] = Number(tmp[0]);
        r[i] = Number(tmp[1]);
    }

    var sum = Array(N + 1).fill(0);
    for (var i = 1; i < N; i++) {
        sum[i + 1] = sum[i];
        if (S[i - 1] === "A" && S[i] === "C") { sum[i + 1]++; }
    }

    for (var i = 0; i < Q; i++) {
        console.log(sum[r[i]] - sum[l[i]]);
    }
});

Measured memory_bytes: 52952
import operator as op
from functools import reduce
 
def ncr(n, r):
    r = min(r, n-r)
    numer = reduce(op.mul, range(n, n-r, -1), 1)
    denom = reduce(op.mul, range(1, r+1), 1)
    return numer // denom
 
 
N, K = list(map(int, input().split()))
 
def num(i):
    if i > N - K + 1:
        return 0
    else:
        num1 = ncr(N-K+1, i) % (10**9 + 7)
        num2 = ncr(K-1, i-1) % (10**9 + 7)
        num = (num1 * num2) % (10**9 + 7)
        return num
 
 
for i in range(1, K+1):
    print(num(i))

Measured memory_bytes: 3944
n,k = map(int,input().split())
a = [0]+list(map(int,input().split()))
for i in range(n):
    a[i+1] += a[i]
    a[i+1] %=k
cnt = {}
ans = 0
for i in range(n+1):
    left = i-k
    if left >=0:
        ldiff = (a[left] - left)%k
        cnt[ldiff] -= 1
    x = (a[i] - i)%k
    if x <0:x+=k
    if x not in cnt:cnt[x] = 0
    ans+= cnt[x]    
    cnt[x] +=1
print(ans)



Measured memory_bytes: 38376
#include<cstdio>
#define MAXN 100

int n,res,ans;
int a[MAXN+5];

int main() {
	scanf("%d",&n);
	for(int i=1;i<=n;i++) {
		scanf("%d",&a[i]);
		res+=a[i];
	}
	double k=res*1.0/n;
	if(k-res/n>=0.5) res=res/n+1;
	else res=res/n;
	for(int i=1;i<=n;i++)
		ans+=(a[i]-res)*(a[i]-res);
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i = (a); i < (b); ++i)
#define rrep(i,a,b) for(int i = (b); i --> (a);)
#define all(v) (v).begin(),(v).end()
#define trav(x,v) for(auto &x : v)
#define sz(v) int(v.size())
typedef vector<int> vi;
typedef long long ll;
typedef pair<int,int> pii;

int main(){
	cin.sync_with_stdio(0);
	cin.tie(0);

	int n;
	cin >> n;

	vi l(n), r(n);
	rep(i,0,n) cin >> l[i] >> r[i];

	vi p(n), q(n);
	rep(i,0,n) p[i] = q[i] = i;

	sort(all(p), [&](int x, int y){
		return l[x] > l[y];
	});

	sort(all(q), [&](int x, int y){
		return r[x] < r[y];
	});

	ll ans = 0;

	rep(t,0,2){
		ll res = 0;
		vector<bool> alive(n, true);

		int pos = 0;
		int dir = t ? 1 : -1;
		int pix = 0, qix = 0;

		while(true){
			if(dir == 1){
				while(pix < n && !alive[p[pix]]) ++pix;
				if(pix == n){
					res += abs(pos);
					pos = 0;
					break;
				}
				if(l[p[pix]] > pos){
					res += l[p[pix]] - pos;
					pos = l[p[pix]];
				}
				alive[p[pix]] = false;
				++pix;
			} else {
				while(qix <n &&	!alive[q[qix]]) ++qix;
				if(qix == n){
					res += abs(pos);
					pos = 0;
					break;
				}
				if(r[q[qix]] < pos){
					res += pos - r[q[qix]];
					pos = r[q[qix]];
				}
				alive[q[qix]] = false;
				++qix;
			}
			dir = -dir;
		}

		ans = max(ans, res);
	}
	cout << ans << endl;
}

Measured memory_bytes: 1920
#include <iostream>
#include <vector>
#include <stack>
#include <unordered_set>
#include <numeric>
#include <iterator>
#include <unordered_map>
#include <array>
#include <map>
#include <cstring>
#include <iomanip>
#include <string>
#include <algorithm>
#include <cmath>
#include <ctgmath>
#include <set>
#include <queue>
#include <fstream>
#include <ostream>
#include <random>
#include <chrono>

using namespace std;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	vector<int> all;
	for (int i = 0; i < 5; i++)
	{
		int x;
		cin >> x;

		all.push_back(x);
	}
	int k;
	cin >> k;

	sort(all.begin(), all.end());
		
	if (abs(all[0] - all[4]) <= k)
	{
		cout << "Yay!\n";
	}
	else
	{
		cout << ":(\n";
	}
}


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

using namespace std;

int main()
{
	// 入力
	int N;
	cin >> N;
	
	int answer = 0;
	for (int i = 1; i <= N; i++)
	{
		// 数値を文字列に変換し、長さを求めると、値自身の桁数が求められる
		// 桁数が奇数の場合のみ個数を数える
		if (to_string(i).length() % 2 == 1)
		{
			answer++;
		}
	}
	
	cout << answer << endl;
	return 0;
}

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

#define REP(i, n) for(int64_t i = 0; i < n; i++)
#define REPR(i, n) for(int64_t i = n; i >= 0; i--)
#define FOR(i, m, n) for(int64_t i = m; i < n; i++)
#define FORR(i, m, n) for(int64_t i = m; i >= n; i--)
#define ALL(v) v.begin(), v.end()
typedef long long ll;
template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    fill( (T*)array, (T*)(array+N), val );
}
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;}
const ll INF= 1ll << 60;
const ll MOD = 1000000007;
double EPS = 1e-10;
//----------------------------------------------------------

string s;

int main(){
    cin >> s;
    if(s=="ABC")cout << "ARC" << endl;
    else cout << "ABC" << endl;
    return 0;
}

Measured memory_bytes: 3628
from collections import deque

n = int(input())
A = list(map(int,input().split()))
que = deque()

for i in range(n):
    if i % 2 == 0:
        que.appendleft(A[i])
    else:
        que.append(A[i])
else:
    if n % 2 == 0:
        que.reverse()
    print(*que)

Measured memory_bytes: 25412
#include <bits/stdc++.h>
// #include <atcoder/all> // NOTE: AtCoderライブラリ
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
// using namespace atcoder; // NOTE: AtCoderライブラリ
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<long long> vl;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef pair<int, int> pii;
// #define INF __INT32_MAX__
#define INF 1e9
#define LINF __LONG_LONG_MAX__

long long modpow(long long a, long long n, long long mod) {
    long long res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;

        a = a * a % mod;
        n >>= 1;
    }
    return res;
}


const int MOD = 1e9 + 7;
vector<vl> dp;

void f(int i, int curr) {
    for (int j = 0; j < 13; j++) {
        // 遷移先
        int x = (j + curr) % 13;

        dp[i][x] += dp[i - 1][j];
        dp[i][x] %= MOD;
    }
}

int main() {
    string S; cin >> S;
    // NOTE: reverseしたら0の扱いが面倒そう (途中に0が出てくるやつ)
    int N = S.size();

    dp.resize(N + 1, vl(13, 0));
    dp[0][0] = 1;

    for (int i = 1; i <= N; i++) {
        ll digit = modpow(10, N - i, 13);

        if (S.at(i - 1) == '?') {
            for (int j = 0; j < 10; j++) {
                int curr = (j * digit) % 13;
                f(i, curr);
            }
        } else {
            int curr = ((S.at(i - 1) - '0') * digit) % 13;
            f(i, curr);
        }
    }

    // rep(i, N + 1) {
    //     rep(j, 13) {
    //         cout << dp[i][j] << " ";
    //     }
    //     cout << endl;
    // }

    cout << dp[N][5] << endl;
}


Measured memory_bytes: 16652
N, P = map(int, input().split())
S = list(input())

if P != 2 and P != 5:
    count = [0] * P
    ans = 0
    tmp = 0
    for i in range(N - 1, -1, -1):
        tmp += int(S[i]) * pow(10, (N - 1 - i), P)
        tmp %= P
        ans += count[tmp]
        count[tmp] += 1
    ans += count[0]

    # print (count)
    print (ans)

if P == 2:
    count = 0
    for index, s in enumerate(S):
        if int(s) % 2 == 0:
            count += (index + 1)
    print (count)

if P == 5: 
    count = 0
    for index, s in enumerate(S):
        if int(s) % 5 == 0:
            count += (index + 1)
    print (count)

Measured memory_bytes: 4968
#include <vector>
#include <math.h>
#include <string>
#include <ios>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <string>

#define LL long long
using namespace std;
int main() {
	LL K, X;

	cin >> K >> X;

	for (int i = X - K + 1; i < X + K; i++) {
		cout << i << " ";
	}
	return 0;
}

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

#ifdef LOCAL
#define dbg(...) fprintf(stderr, __VA_ARGS__)
#define dbgv(x) cerr << #x << " = " << x << endl
#define dbga(arr, len) {cerr << #arr << " = "; for (int _ = 0; _ < len; _++)\
cerr << arr[_] << " "; cerr << endl;}
#define dbgi(it) {cerr << #it << " = "; for (const auto& _ : it)\
cerr << _ << " "; cerr << endl;}
#else
#define dbg(...) (void)0
#define dbgv(x) (void)0
#define dbga(arr, len) (void)0
#define dbgi(it) (void)0
#endif

using ll = long long;
using dbl = long double;
using pii = pair<int, int>;

const int MOD = (int)1e9 + 7;
const int N = 100500;

int add(int a, int b) {
    a += b;
    if (a >= MOD) {
        a -= MOD;
    }
    return a;
}
int mul(int a, int b) {
    return (ll)a * b % MOD;
}

int n;
int a[N];
vector<int> pos[N];
vector<int> cnt[N];

void solve() {
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        scanf("%d", &a[i]);
    }

    int zero_cnt = 0;
    for (int i = 0; i < n; ++i) {
        pos[a[i]].push_back(i);
        zero_cnt += a[i] == 0;
    }
    if (zero_cnt == 0 || zero_cnt > 3) {
        puts("0");
        return;
    }
    for (int i = 0; i < n; ++i) {
        int c = 0;
        for (int j : pos[a[i] + 1]) {
            c += i < j;
        }
        cnt[a[i]].push_back(c);
    }

    int ans = zero_cnt == 1 ? 3 : 6;
    for (int x = 0; x + 1 < N; ++x) {
        int nxt_sz = cnt[x + 1].size();
        if (nxt_sz == 0) {
            continue;
        }
        int sz = cnt[x].size();
        int glob_ways = 0;
        for (int skip_mask = 0; skip_mask < (1 << sz); ++skip_mask) {
            int passed = 0;
            int ways = 1;
            for (int i = 0; i < sz; ++i) {
                if (skip_mask & (1 << i)) {
                    continue;
                }
                ++passed;
                int delta = cnt[x][i] - (nxt_sz - passed);
                delta = max(0, delta);
                ways = mul(ways, delta);
            }
            if (passed == nxt_sz) {
                glob_ways = add(glob_ways, ways);
            }
        }
        ans = mul(ans, glob_ways);
    }

    printf("%d\n", ans);
}

int main() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
#endif

    solve();

    dbg("\n\ntime = %.3lf\n", (double)clock() / CLOCKS_PER_SEC);
}


Measured memory_bytes: 11648
#include <bits/stdc++.h>
using namespace std;
#define maxn 100005

#define ll long long
#define mod 1000000007

typedef pair<int, int> P;

int n;
int l[maxn], r[maxn];
vector<P> v;
int _min[maxn];

int main()
{
    cin >> n;
    scanf("%d%d", &l[1], &r[1]);
    int p = 1, q = 1;
    for (int i = 2; i <= n; i++)
    {
        scanf("%d%d", &l[i], &r[i]);
        if (l[i] > l[p])
            p = i;
        if (r[i] < r[q])
            q = i;
    }
    int ans = 0;
    for (int i = 1; i <= n; i++)
    {
        if (i != p && i != q)
        {
            ans = max(ans, r[i] - l[i] + 1);
            v.push_back(P(max(0, r[i] - l[p] + 1), max(0, r[q] - l[i] + 1)));
        }
    }
    ans += max(0, r[q] - l[p] + 1);
    //printf("%d\n", ans);
    sort(v.begin(), v.end());
    int ans2 = 0;
    _min[0] = r[q] - l[q] + 1;
    for (int i = 0; i < v.size(); i++)
        _min[i + 1] = min(_min[i], v[i].second);
    for (int i = 1; i <= v.size(); i++)
        ans2 = max(ans2, v[i - 1].first + _min[i - 1]);
    ans2 = max(ans2, max(0, r[p] - l[p] + 1) + _min[v.size()]);
    ans = max(ans, ans2);
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 2292
a,b,c,k = map(int,input().split())
count  = k

if a < count:
    a_n = a
else:
    a_n = count    
count -= a_n

if b < count:
    b_n = b
else:
    b_n = count
count -= b_n

if c < count:
    c_n = c
else:
    c_n = count
count -= c_n

print(a_n-c_n)

Measured memory_bytes: 9192
import sys
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
mod = 10**9 + 7
inf = float('inf')
ans = int(0)

N = I()
A = LI()
k = int(1)
for i in A:
    if i<0:
        k *=(-1)
    elif i==0:
        k = 0

for i in range(N):
    A[i] = abs(A[i])
sumA = sum(A)
if k<0:
    ans = sumA-min(A)*2
else:
    ans = sumA

print(ans)


Measured memory_bytes: 14412
#include<bits/stdc++.h>
using ll = int_fast64_t;

int main(){
        ll n, k;
        scanf("%ld %ld", &n, &k);
        std::vector<ll> a(n), f(n);
        for(ll i=0; i<n; i++) scanf("%ld", &a[i]);
        sort(a.begin(), a.end());
        for(ll i=0; i<n; i++) scanf("%ld", &f[i]);
        std::sort(f.begin(), f.end(), std::greater<ll>());

        ll l=-1, r=1e12+1;
        while(r-l>1){
                ll mid = (r-l)/2 + l, cnt = 0;
                for(ll i=0; i<n; i++){
                        cnt += std::max(0l, a[i]*f[i]-mid+f[i]-1) / f[i];
                }

                if(cnt<=k) r = mid;
                else l = mid;
        }

        printf("%ld\n", r);
        return 0;
}

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

int main( void ){
    int n, m, i, j, ans, end, count;
    scanf("%d", &n);
    count = 0;
    for(i = 0; i < n; i++){
        scanf("%d", &m);
        if(m == 2){
            ans = 1;
        }
        else if(m % 2 == 0){
            ans = 0;
        }
        else{
            end = 0;
            for(j = 3; j <= sqrt(m); j = j + 2){
                if(m % j == 0){
                    ans = 0;
                    end = 1;
                    break;
                }
            }
            if(end == 0){
                ans = 1;
            }
        }
        if(ans == 1){
            count++;
        }
    }
    printf("%d\n", count);
    return 0;
}



Measured memory_bytes: 2032
#include <stdio.h>

using namespace std;

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

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

    int t = 0;
    int x = 0;
    int y = 0;
    REP(i, N) {
        int tt = t;
        int xx = x;
        int yy = y;

        scanf("%d %d %d", &t, &x, &y);

        int dt = t - tt;
        int dx = x - xx;
        int dy = y - yy;

        if (dx + dy > dt) {
            printf("No\n");
            return 0;
        }

        if ((dt - dx - dy) % 2 != 0) {
            printf("No\n");
            return 0;
        }
    }

    printf("Yes\n");
    return 0;
}


Measured memory_bytes: 128
# -*- coding: utf-8 -*-
modelmap = list(input())
S1 = []
S2 = []
A = 0

for i, l in enumerate(modelmap):
    if l == "\\":
        S1.append(i)
    elif l == "/" and len(S1) > 0:
        ip = S1.pop()
        A += i - ip
        L = i - ip
        while len(S2) > 0 and S2[-1][0] > ip:
            L += S2.pop()[1]
        S2.append([ip, L])

print(A)
text2 = "{}".format(len(S2))
for s in S2:
    text2 += " " + str(s[1])
print(text2)            

Measured memory_bytes: 8168
#include <bits/stdc++.h>
#define FOR(i, a, b) for(long long i = (a); i <= (b); i++)
#define rep(i, n) for(long long i = 0; i < (n); i++)
using namespace std;
typedef long long ll;

long long gcd(long long a, long long b)
{
	if (b == 0) return a;
	return gcd(b, a % b);
}

vector<pair<ll, int>> factarize(ll n)
{
	vector<pair<ll, int>> res;
	for(ll i = 2; i * i <= n; i++)
	{
		if (n % i) continue;
		res.emplace_back(i, 0);
		while (n % i == 0)
		{
			n /= i; 
			res.back().second++;
		}
	}
	if (n != 1) res.emplace_back(n, 1);
	return res;
}

signed main(void)
{
	long long a, b;
	vector<long long> v;
	cin >> a >> b;

	ll g = gcd(a, b);
	auto f = factarize(g);
	int ans = f.size() + 1;
	cout << ans << endl;
	return 0;
}


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

int main(){
  
  double W,H,x,y;
  cin >> W >> H >> x >> y;
  double ans = (W * H) / 2;
  cout << ans;
  if (x == W / 2 && y == H / 2) cout << " " << 1 << endl;
  else cout << " " << 0 << endl;
  
}

Measured memory_bytes: 256
def matrix_chain_multiplication(n):
    m = [[0 for x in range(n+1)] for y in range(n+1)]
    for l in range(2, n+1):
        for i in range(1, n-l+2):
            j = i + l - 1
            m[i][j] = float('inf')
            for k in range(i, j):
                m[i][j] = min(m[i][j], m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j])
    print(m[1][n])

p = []
n = int(input())

for i in range(n):
    listed_input = input().split()
    p.append(int(listed_input[0]))

p.append(int(listed_input[1]))

matrix_chain_multiplication(n)




Measured memory_bytes: 5712
import sys
import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N = int(read())

U = 10**6
is_prime = np.zeros(U, np.bool_)
is_prime[2] = 1
is_prime[3::2] = 1
for p in range(3, U, 2):
    if p * p >= U:
        break
    if is_prime[p]:
        is_prime[p * p::p + p] = 0

primes = is_prime.nonzero()[0]

def factor(N):
    div = primes[N % primes == 0]
    for p in div:
        e = 0
        while N % p == 0:
            e += 1
            N //= p
        yield (p, e)
    if N != 1:
        yield (N, 1)

A = np.zeros(100, np.int32)
for i in range(14):
    k = i * (i + 1) // 2
    A[k] = i
np.maximum.accumulate(A, out=A)

x = 0
for p, e in factor(N):
    x += A[e]
print(x)

Measured memory_bytes: 29124
n, m, x = map(int, input().split(' '))
As = list(map(int, input().split(' ')))

left = 0
for i in range(1, x):
    if i in As:
        left += 1

right = 0
for i in range(x+1, n):
    if i in As:
        right += 1

if left < right:
    print(left)
else:
    print(right)

Measured memory_bytes: 3064