akhauriyash/Code-Regression huggingface dataset:
import Control.Applicative
import Control.Monad
import Control.Monad.ST
-- import qualified Data.ByteString as BS
import Data.Functor
import Data.Function
import Data.Monoid
import Data.Maybe
import Data.List
import qualified Data.Foldable as Foldable
import qualified Data.Set as Set
--import qualified Data.Sequence as Sequence
import Data.List.Split
import Data.Bits
import Data.Char
import Data.Ix
import Data.Ratio
import Data.Ord
import Data.Tuple
import Data.Array
--import Data.Array.Unboxed
--import Data.Array.IArray
import Data.Array.MArray
import Data.Array.IO
import Data.Array.ST
import Data.IORef
import Data.STRef
import GHC.ST
-- import System.IO.Unsafe
 
-- templete
readInt = read :: String -> Int
readInteger = read :: String -> Integer
readDouble = read :: String -> Double
getInt = readLn :: IO Int
getInts = map readInt . words <$> getLine
getInteger = readLn :: IO Integer
getIntegers = map readInteger . words <$> getLine
getDouble = readLn :: IO Double
getDoubles = map readDouble . words <$> getLine
sjoin :: (Show a) => [a] -> String
sjoin = unwords . map show
tjoin :: (Show a, Show b) => (a, b) -> String
tjoin (x, y) = show x ++ (' ' : show y)
cond :: a -> a -> Bool -> a
cond t f c = if c then t else f
apply2 :: (a -> a -> b) -> [a] -> b
apply2 f [x,y] = f x y
apply3 :: (a -> a -> a -> b) -> [a] -> b
apply3 f [x,y,z] = f x y z
apply4 :: (a -> a -> a -> a -> b) -> [a] -> b
apply4 f [x,y,z,w] = f x y z w
fnTuple :: (a -> b, a -> c) -> a -> (b, c)
fnTuple (f,g) a = (f a, g a)
replace :: (Eq a) => a -> a -> [a] -> [a]
replace x y = map (\z -> if z==x then y else z)
binMap :: (a -> a -> b) -> [a] -> [b]
binMap f (x:xs@(y:_)) = f x y : binMap f xs
binMap _ _ = []
splitRec :: Int -> [a] -> [[a]]
splitRec _ [] = []
splitRec n xs = let (y,ys) = splitAt n xs in y : splitRec n ys
infixl 7 `divCeil`
divCeil :: Integral a => a -> a -> a
x `divCeil` y = (x+y-1) `div` y
coverC :: Ord a => (a, a) -> a -> Bool
coverC (l,r) x = l<=x && x<=r
coverH :: Ord a => (a, a) -> a -> Bool
coverH (l,r) x = l<=x && x<r
ibsearch :: (Int -> Bool) -> (Int,Int) -> Int
ibsearch f (ok,ng) = if abs (ok-ng) <= 1 then ok else let mid = (ok + ng) `div` 2 in ibsearch f (if f mid then (mid,ng) else (ok,mid))
-- templete

edges :: Int -> [(Int,Int)] -> Array Int [Int]
edges n es = runSTArray $ do
    arr <- newArray (1,n) []
    forM_ es $ \(i,j) -> readArray arr i >>= writeArray arr i . (j:)
    return arr

calc ts es = search 1
  where
    search i = case ts!i of
        "E" -> product $ map search $ es!i
        "E?" -> (+1) $ product $ map search $ es!i
        "A" -> sum $ map search $ es!i
        "A?" -> (+1) $ sum $ map search $ es!i
        "R" -> subtract 1 $ product $ map (+1) $ map search $ es!i
        "R?" -> product $ map (+1) $ map search $ es!i


main = do
    n <- getInt
    types <- listArray (1,n) <$> replicateM n getLine
    es <- edges n . map (apply2 (,)) <$> replicateM (n-1) getInts
    print $ flip mod 1000000007 $ calc types es
    



Measured memory_bytes: 5276
# -*- coding: utf-8 -*- #

h, w = map(int, input().split())
s_list = [list(input()) for _ in range(h)]
xy = [[0, 1], [-1, 0], [1, 0], [0, -1]]
flag = False
ans = "Yes"

for i in range(h):
    for j in range(w):
        if s_list[i][j] == "#":
            for k in xy:
                if (i+k[1] < 0 or i+k[1] >= h or j+k[0] < 0 or j+k[0] >= w) == False:
                    if s_list[i+k[1]][j+k[0]] == "#":
                        flag = True
            if flag == False:
                ans = "No"
                break
            flag = False
    else:
        continue
    break

print(ans)

Measured memory_bytes: 3064
#include<iostream>
#include<stdio.h>
#include<vector>
#include<algorithm>
#include<set>
#include<string>
#include<map>
#include<string.h>
#include<complex>
#include<math.h>
#include<queue>
#include <functional>
#include<time.h>
#include <stack>
#include<iomanip>
using namespace std;
#define rep(i,a,n) for(ll i=(a);i<(n);i++)
#define ll long long
#define llint long long int
#define reverse(v)  reverse(v.begin(), v.end());
#define Yes(ans) if(ans)cout<<"Yes"<<endl; else cout<<"No"<<endl;
#define YES(ans) if(ans)cout<<"YES"<<endl; else cout<<"NO"<<endl;
#define hei(a) vector<a>
#define whei(a) vector<vector<a>>
#define UF  UnionFind 
#define Pint pair<int,int>
#define keta(a)  fixed << setprecision(a)
constexpr auto INF = 100000000000;
constexpr auto mod = 1000000007;
//辞書順はnext_permutation( begin( v ), end( v ) );やで！
struct edge { int to, cost; };

ll gcd(ll a, ll b) {
	if (a < b)swap(a, b);
	if (b == 0)return a;
	return gcd(b, a % b);
}
int main() {
	llint a, b, c, k;
	cin >> a >> b >> c >> k;
	llint ans = 0;
	if (k <= a)ans = k;
	else {
		k -= a;
		ans += a;
		if (k > b) {
			k -= b;
			ans -= min(c, k);
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 3632
import sys
#import numpy as np

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

tin=lambda : map(int, input().split())
lin=lambda : list(IN())
mod=1000000007

#+++++
def ii(v, n):
	v += 2 ** 15
	ret = bin(v)[-n:]
	return ret

def v_sum(a,b):
	return [av+bv for av,bv in zip(a,b)]

def get_n(rr, mm, k, limit):
	ret = sum([int(c) for c in rr])
	o = mm[0]
	pp = []
	for index_i, is_cut in enumerate(rr):
		if is_cut == '1':
			pp.append(o)
			o = mm[index_i+1]
		else:
			o = v_sum(o, mm[index_i+1])
			
		if max(o) > k:
			return mod, None
			
	pp.append(o)
	
	ll = [pp[j][0] for j in range(len(pp))]
	for v in ll:
		if v > k:
			return mod, None
	
	cc = [0]*(len(mm[0]))
	for i in range(1, len(mm[0])):
		for il, v in enumerate(ll):
			if ll[il] + pp[il][i] > k:
				ret += 1
				if ret >= limit:
					return limit+1, None
				ll = [pp[j][i] for j in range(len(pp))]
				cc[i] = 1
				break
			else:
				ll[il] += pp[il][i]
	return ret, cc

def main():
	h, w, k = tin()
	mm=[]
	for _ in range(h):
		s = input()
		s = [int(c) for c in s]
		#s = np.array(s)
		mm.append(s)
		
	n = (h-1)*(w-1) + 1
	for i in range(2 ** (h-1)):
		rr = ii(i, h-1)
		tt, cut_info = get_n(rr, mm, k, n)
		if tt < n:
			n = tt
		
	print(n)
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Measured memory_bytes: 45916
/*
    Mbak Sana Dong
    Mbak Chaeyoung Dong
*/
#include<bits/stdc++.h>
#define ll long long
using namespace std;

int main()
{
    int n,i,j,k,x,y,ans,curr,temp,m;
    int tc;
    string s;
    cin >> s;
    ans = 0;
    for(auto x : s) ans += x-'0';
    if(ans%9==0) cout << "Yes";
    else cout << "No";
    return 0;
}


Measured memory_bytes: 3716
import java.util.Scanner;

class Main {
 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
 
        int a = sc.nextInt();
        int b = sc.nextInt();
        int sum = a + b;
        if(sum >=24){
        	sum = sum - 24;
        }
        System.out.println(sum);
        }
}

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


public class Main{
    public static void main(String[] args){
        Scanner sc =new Scanner(System.in);
        int red = sc.nextInt();
        int green = sc.nextInt();
        int blue = sc.nextInt();
        int limit = sc.nextInt();
        for(int i=0; i<limit; i++){
            if(red<green && green<blue){
                break;
            }else if(red>=green){
                green=green*2;
            }else if(green>=blue){
                blue=blue*2;
            }
       }
       if(red<green &&green<blue){
           System.out.println("Yes");
       }else{
           System.out.println("No");
       }
    }
}

Measured memory_bytes: 35684
s = gets.chomp
N = s.size
ans = Array.new(N, 0)
["R","L"].each{ |f|
  x = 0
  (0...N).each{ |i|
    if s[i] == f
      x += 1
    else
      ans[i-1] += (x+1)/2      
      ans[i] += x/2
      x = 0
    end
  }
  s.reverse!
  ans.reverse!
}
puts ans * " "


Measured memory_bytes: 5244
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <map>
#include <vector>
#include <math.h>
#include <algorithm>
#include <queue>
using namespace std;

#define rep(i,a) for(int i=0; i<a; i++)
#define rrep(i,a) for(int i=a; i>=0; i--)
#define loop3(i,j,k,a) for(int i=0; i<a; i++)for(int j=0; j<a; j++)if(i!=j)for(int k=0; k<a; k++)if(i!=k&&j!=k)
#define loop4(i,j,k,l,a) for(int i=0; i<a; i++)for(int j=0; j<a; j++)if(i!=j)for(int k=0; k<a; k++)if(i!=k&&j!=k)for(int l=0; l<a; l++)if(i!=l&&j!=l&&k!=l)
#define rep1(i,a) for(int i=1; i<=a; i++)

#define scnd1(a) scanf("%d", &a)
#define scnd2(a,b) scanf("%d%d", &a,&b)
#define scnd3(a,b,c) scanf("%d%d%d", &a,&b,&c)
#define scnd4(a,b,c,d) scanf("%d%d%d%d", &a,&b,&c,&d)

#define cin1(a) cin >> a;
#define cin2(a,b) cin >> a >> b;
#define cin3(a,b,c) cin >> a >> b >> c;
#define cin4(a,b,c,d) cin >> a >> b >> c >> d;
#define cout1(a) cout << a << endl;
#define cout2(a,b) cout << a << " " << b << endl;
#define cout3(a,b,c) cout << a << " " << b << " " << c << endl;
#define cout4(a,b,c,d) cout << a << " " << b << " " << c << " " << d << endl;
#define prtd1(a) printf("%d\n", a)
#define prtd2(a,b) printf("%d %d\n", a,b)
#define prtd3(a,b,c) printf("%d %d %d\n", a,b,c)
#define prtd4(a,b,c,d) printf("%d %d %d %d\n", a,b,c,d)

#define mem(a,n) memset( a, n, sizeof(a))
#define INF 1000000000
typedef long long ll;

int main() {
    int N;
    cin >> N;
    
    int nowt=0, nowx=0, nowy=0, nxtt, nxtx, nxty;
    rep(i,N) {
        cin >> nxtt >> nxtx >> nxty;
        int too = ( nxtt-nowt ) - abs( nxtx-nowx ) - abs( nxty-nowy );
        if ( too<0 || too%2 == 1 ) {
            cout1("No");
            return 0;
        }
    }
    cout1("Yes");
}

Measured memory_bytes: 888
n, m = map(int, input().split())
l = [int(input())-1 for _ in range(m)]
res = [0, 1]
skip = 0

if m != 0:
  for i in range(n):
    if i == l[skip]:
      res[0] = res[1]
      res[1] = 0
      if skip < m-1:
        skip += 1
    else:
      tmp = res[1]
      res[1] += res[0]
      res[0] = tmp
      res[1] %= 10**9 + 7
      res[0] %= 10**9 + 7
else:
  for i in range(n):
    tmp = res[1]
    res[1] += res[0]
    res[0] = tmp
    res[1] %= 10**9 + 7
    res[0] %= 10**9 + 7
      
print(res[1])

Measured memory_bytes: 7080
def solve():
    L, R = map(int, input().split())
    if L + 2019 <= R:
        print(0)
    elif L % 2019 > R % 2019:
        print(0)
    else:
        l = L % 2019
        r = R % 2019
        min_mod = 2019
        for i in range(l, r):
            for j in range(i + 1, r + 1):
                min_mod = min(min_mod, (i * j) % 2019)
        print(min_mod)


if __name__ == '__main__':
    solve()


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

using namespace std;

typedef long long ll;
typedef vector<ll> vll;
typedef pair<int, int> P;
const int INF = 0x3f3f3f3f;
const int MAXN = 200000;

int N, M;

struct Edge {
    int to;
    int weight;
    int next;
};

vector<Edge> edges(MAXN);
vector<int> head(MAXN, -1);
vector<int> matchingx(MAXN, -1);
vector<int> matchingy(MAXN, -1);
vector<bool> check(MAXN);
vector<int> dis(MAXN);
vector<bool> vis(MAXN, false);

int cnt = 1;

void addEdge(int from, int to, int weight) {
    edges[cnt].to = to;
    edges[cnt].weight = weight;
    edges[cnt].next = head[from];
    head[from] = cnt++;
}

bool dfs(int u) {
    for (int i = head[u]; i != -1; i = edges[i].next) {
        int v = edges[i].to;
        if (!check[v]) {
            check[v] = true;
            if (matchingy[v] == -1 || dfs(matchingy[v])) {
                matchingy[v] = u;
                matchingx[u] = v;
                return true;
            }
        }
    }
    return false;
}

int hungarian() {
    int ans = 0;
    fill(matchingx.begin(), matchingx.end(), -1);
    fill(matchingy.begin(), matchingy.end(), -1);
    for (int u = 1; u <= N; ++u) {
//        if (matchingx[u] == -1) {
        {
            fill(check.begin(), check.end(), false);
            if (dfs(u)) {
                ++ans;
            }
        }
    }
    return ans;
}

void dijkstra(int s) {
    priority_queue<P, vector<P>, greater<>> que;
    fill(dis.begin(), dis.end(), INF);
    dis[s] = 0;
    que.push(P(0, s));
    while (!que.empty()) {
        P p = que.top();
        que.pop();
        int u = p.second;
        if (vis[u]) continue;
        vis[u] = true;
        for (int i = head[u]; i != -1; i = edges[i].next) {
            int v = edges[i].to;
            if (dis[v] > dis[u] + edges[i].weight && !vis[v]) {
                dis[v] = dis[u] + edges[i].weight;
                que.push(P(dis[v], v));
            }
        }
    }
}

struct TreeNode {
    int val;
    TreeNode* left = nullptr;
    TreeNode* right = nullptr;
    TreeNode(int val_) : val(val_) {}
};

int main() {
    ll A, B, Q;
    cin >> A >> B >> Q;
    vll numsA(A);
    vll numsB(B);
    for (int i = 0; i < A; ++i) {
        cin >> numsA[i];
    }
    numsA.push_back(-100000000000LL);
    numsA.push_back(100000000000LL);
    for (int i = 0; i < B; ++i) {
        cin >> numsB[i];
    }
    numsB.push_back(-100000000000LL);
    numsB.push_back(100000000000LL);
    sort(numsA.begin(), numsA.end());
    sort(numsB.begin(), numsB.end());
    ll x;
    for (int i = 0; i < Q; ++i) {
        cin >> x;
        auto uba = upper_bound(numsA.begin(), numsA.end(), x);
        auto ubb = upper_bound(numsB.begin(), numsB.end(), x);
        auto lba = uba - 1;
        auto lbb = ubb - 1;
        vll tmpA = {*lba, *uba};
        vll tmpB = {*lbb, *ubb};

        ll ans = 0;

        ans = tmpA[1] - tmpB[0] + min(tmpA[1] - x, x - tmpB[0]);
        ans = min(ans, tmpB[1] - tmpA[0] + min(tmpB[1] - x, x - tmpA[0]));
        ans = min(ans, x - min(tmpA[0], tmpB[0]));
        ans = min(ans, max(tmpA[1], tmpB[1]) - x);

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

Measured memory_bytes: 10208
S = input()
n = int(S)

d = {}
for i in range(1, n+1):
    if (int(str(i)[0]), int(str(i)[-1])) in d:
        d[(int(str(i)[0]), int(str(i)[-1]))] += 1
    else:
        d[(int(str(i)[0]), int(str(i)[-1]))] = 1

ans = 0
for (a,b), v in d.items():
    if (b, a) in d:
        ans += d[(a, b)] * d[(b, a)]
print(ans)

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

using namespace std;

string s;
int n,m,minn=0x3f3f3f3f,ans,sum,a,b,c,x,y;

int main(){
	scanf("%d%d%d%d%d",&a,&b,&c,&x,&y);
	if(c*2<a+b) {
		int tt=min(x,y);
		ans+=tt*2*c;
		x-=tt,y-=tt;	
	}
	a=min(a,2*c),b=min(b,2*c);
	ans+=x*a+y*b;
	printf("%d",ans);
	return 0;	
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
long long a,b,c,d,e,i,j,zx,xc,f[1009];
int main(){
	ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>a>>b;
	for(i=1; i<=a; i++){
		cin>>f[i];
		c+=f[i];
	}
	e=4*b;
	if(c%e==0) c=c/e; else c=c/e+1;
	for(i=1; i<=a; i++){
		if(f[i]>=c) d++;
	}
	if(d>=b){
		cout<<"Yes";
	}else{
		cout<<"No";
	}
	return 0;
}

Measured memory_bytes: 3660
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>


using namespace std;

vector<int>v;
#define pb push_back

int main(){
	int a, b, c, d;

	cin >> a >> b >> c >> d;

	v.pb(a);
	v.pb(b);
	v.pb(c);
	v.pb(d);

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

	if(v[0] == 1 && v[1] == 4 && v[2] == 7 && v[3] == 9){
		cout << "YES";
		return 0;
	}
	cout << "NO";

	return 0;



}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
struct Fast {Fast(){std::cin.tie(0);ios::sync_with_stdio(false);cout.precision(20);}} fast;

/* define */
#define FOR(I,X,Y) for(long long (I)=(X);(I)<(Y);(I)++)
#define REP(I,X,Y) for(long long (I)=(Y)-1;(I)>=(X);(I)--)
#define ALL(X) (X).begin(),(X).end()
#define pb push_back
#define COUNT(V,X) (upper_bound((V).begin(),(V).end(),X)-lower_bound((V).begin(),(V).end(),X))
#define debug(x) cerr<<#x<<':'<<x<<endl;
#define DEBUG(v) cerr<<#v<<':';for(auto xXx:v)cerr<<xXx<<' ';cerr<<endl;
#define Yes(X) if(X){cout<<"Yes"<<endl;}else{cout<<"No"<<endl;}
#define YES(X) if(X){cout<<"YES"<<endl;}else{cout<<"NO"<<endl;}
#define ctoi(C) (C-'0')
#define pow2(x) ((long long)((long long)1<<x))

/* alias */
using ll = long long;
using ld = long double;
using vi = vector<int>;
using vii = vector<vector<int>>;
using vl = vector<long long>;
using vll = vector<vector<long long>>;
using pi = pair<int,int>;
using pl = pair<long long,long long>;
template<typename T> using PQ = priority_queue<T>;
template<typename T> using minPQ = priority_queue<T, vector<T>, greater<T>>;

/* const */
const long long dx[] = {1,0,-1,0};
const long long dy[] = {0,1,0,-1};
const long long dx8[] = {1,1,0,-1,-1,-1,0,1};
const long long dy8[] = {0,1,1,1,0,-1,-1,-1};
const long long dx9[] = {1,1,0,-1,-1,-1,0,1,0};
const long long dy9[] = {0,1,1,1,0,-1,-1,-1,0};
const int INF = 1000000007;
const long long LINF = 1000000000000000007;

/* func */
template <typename T> inline bool chmin(T& a, const T& b) {if (a > b) a = b; return a > b;}
template <typename T> inline bool chmax(T& a, const T& b) {if (a < b) a = b; return a < b;}
long long max(long long x,int y){return max(x,(long long)y);}
long long max(int x,long long y){return max((long long)x,y);}
long long min(long long x,int y){return min(x,(long long)y);}
long long min(int x,long long y){return min((long long)x,y);}

/* liblary */



/* main */

signed main(){
    ll N,K;
    cin >> N >> K;
    vl A(N);
    FOR(i,0,N)cin >> A[i];
    map<int,int> m;
    set<int> s;
    FOR(i,0,N){
        m[A[i]] += 1;
        s.insert(A[i]);
    }
    vl v;
    for(auto x:s)v.push_back(m[x]);
    sort(ALL(v));
    ll ans = 0;
    FOR(i,0,(int)s.size()-K){
        ans += v[i];
    }
    cout << ans << endl;
}


Measured memory_bytes: 22772
#include <iostream>
#include <bitset>
using namespace std;
#define rp(i, s, e) for(int i = s; i < e; i++)

int x[15][15], y[15][15], a[15];

int count_allp(int k, int n){
	bitset<15> temp(k);
	rp(i, 0, n){
		if(temp[i]){
			rp(j, 0, a[i]){
				if(temp[x[i][j]] != y[i][j])
					return 0;
			}
		}
	}
	return temp.count();
}

int main() {
	int n, temp1, temp2, ans=0;
	cin >> n;
	rp(i, 0, n){
		cin >> a[i];
		rp(j, 0, a[i]){
			cin >> temp1 >> temp2;
			temp1--;
			x[i][j] = temp1;
			y[i][j] = temp2;
		}
	}

	rp(number, 1, 1<<n){
		ans = max(ans, count_allp(number, n));
	}
	cout << ans << endl;
}



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

using namespace std;

int h,w;

int main() {
	//freopen("input.txt","r",stdin);
	while(1) {
		scanf("%d%d",&h,&w);
		if(h+w==0) break;
		int d = h*h + w*w;

		int ad=1<<30,ah=1<<30,aw=1<<30;
		for(int nw=1;nw<=d/nw+10;++nw) {
			int th = sqrt(1.0*d-nw*nw);
			for(int nh=1;nh<nw;++nh) {
				if(nh <= 0 || nh >= nw) continue;
				if(nh*nh + nw*nw > d || (nh*nh + nw*nw == d && nh >h)) {
					if(nh*nh + nw*nw < ad || (nh*nh + nw*nw == ad && nh<ah)) {
						ad = nh*nh + nw*nw;
						ah = nh;
						aw = nw;
					}
				}
			}
		}

		printf("%d %d\n",ah,aw);
	}
}

Measured memory_bytes: 1036
import sys
input = sys.stdin.readline
import numpy as np
from heapq import heappush, heappop

N = int(input())
A = np.array(input().split(), dtype=np.int32)
a_to_i = {a:i for i,a in enumerate(A)}

# sparse table を使ってRMQ
# parityの同じところだけを見るようにしておく

U = len(A).bit_length()
sp = [None,A]
for i in range(2,U):
    L = 1 << (i-1)
    sp.append(np.minimum(sp[-1][:-L], sp[-1][L:]))

def RMQ(x,y):
    # x番目から偶数番目だけ見て[x,y]での最小値を返す
    d = y - x
    if d <= 1:
        return A[x]
    n = d.bit_length()
    return min(sp[n-1][x], sp[n-1][y+2-(1<<(n-1))])

def F(x,y):
    # 辞書式で最小の2つ組をとる
    # そのあと、今後調べないといけない区間の一覧を返す
    x1 = RMQ(x,y-1)
    i1 = a_to_i[x1]
    x2 = RMQ(i1+1,y)
    i2 = a_to_i[x2]
    task = ((x,y) for x,y in ((x,i1-1), (i1+1,i2-1), (i2+1,y)) if y > x)
    return x1,x2,task

q = [(None,None,((0,N-1),))]
answer = []
while q:
    x,y,task = heappop(q)
    answer.append(x)
    answer.append(y)
    for left,right in task:
        heappush(q,F(left,right))

print(' '.join(map(str,answer[2:])))

Measured memory_bytes: 108752
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <iomanip>
#include <utility>
using namespace std;

int main(int argc, char const *argv[]) {
  int A, B;
  char op;
  cin >> A >> op >> B;
  if(op == '+'){
    cout << (A+B) << endl;
  }else{
    cout << (A-B) << endl;
  }
}


Measured memory_bytes: 888
#include <bits/stdc++.h>
using ll = long long;
using namespace std;
#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 < int(b); ++i)
#define rep(...) _overload3(__VA_ARGS__, repi, _rep, )(__VA_ARGS__)
const long long INFLL = 1LL << 60;
const int INFINT = 1 << 30;
const long long MOD = 1e9 + 7;

template <class T> void vecout(T V) {
    auto t = V.begin();
    while(t != V.end()) {
        cout << *t++;
        if(t != V.end()) cout << " ";
    }
    cout << endl;
};

template <typename T> T modpow(T a, T n, T mod) { // a^n % mod
    T res = 1;
    while(n > 0) {
        if(n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}

template <typename T> T gcd(T a, T b) {
    if(a > b) gcd(b, a);
    T r;
    while(r = a % b) {
        a = b;
        b = r;
    }
    return b;
}

pair<int, int> extgcd(int a, int b) {
    int x0 = 1, x1 = 0, y0 = 0, y1 = 1, r0 = a, r1 = b;
    int q1, x2, y2, r2;
    while(r1 > 0) {
        q1 = r0 / r1;
        r2 = r0 % r1;
        x2 = x0 - q1 * x1;
        y2 = y0 - q1 * y1;
        r0 = r1;
        r1 = r2;
        x0 = x1;
        x1 = x2;
        y0 = y1;
        y1 = y2;
    }
    return make_pair(x0, y0);
}

template <typename T> T lcm(T a, T b) { return a * b / gcd(a, b); }

template <typename T> T EP(T n) {
    T r = floor(sqrt(n));
    T m = n;
    set<T> p;
    if(((n % 2) == 0) && 2 <= r) {
        p.insert(2);
        while(n % 2 == 0) {
            n /= 2;
        }
    }
    for(int i = 3; i <= r; i += 2) {
        if(n % i == 0) {
            p.insert(i);
            while(n % i == 0) {
                n /= i;
            }
        }
    }
    if(r < n) p.insert(n);
    for(auto e : p)
        m = m / e * (e - 1);
    return m;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n, m;
    cin >> n >> m;
    pair<int, int> a;
    a = extgcd(n, m);
    cout << a.first << " " << a.second << endl;
}


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

namespace AtCoder
{
    class Program
    {
        static void Main(string[] args)
        {
            var N = int.Parse(Console.ReadLine());
            var harray = Console.ReadLine().Split(' ').Select(x => int.Parse(x)).ToArray();
            var hmax = harray.Max();
            var result = 0;

            for(var height =1; height<=hmax; height++)
            {
                var lastCell = false;
                foreach(var i in Enumerable.Range(0, N))
                {
                    if(!lastCell && harray[i]>=height)
                    {
                        result++;
                    }
                    lastCell = harray[i] >= height;
                }
            }
            Console.WriteLine(result);
        }

    }
}
//A

Measured memory_bytes: 13396
#include<iostream>
#include<stdio.h>
#include<string>
#include<cmath>
#include<vector>
#pragma warning(disable: 4996)
#define rep(i,n) for(int i = 0; i < (n); i++)
using namespace std;;
using ll = long long;
ll choose2(ll n) {

	return (n * (n - 1)) / 2;
}

int main() {
	int N;
	cin >> N;

	vector<int> a(N);

	rep(i, N) cin >> a[i];
	rep(i, N) a[i]--;
	vector<ll> c(N,0);

	rep(i, N) c[a[i]]++;

	ll tot=0;

	rep(i, N) {
		
		tot += choose2(c[i]);

	}
	
	rep(i, N) {
		ll ans = tot;
		ans -= choose2(c[a[i]]);
		ans += choose2(c[a[i]] - 1) ;
		cout << ans << endl;

	}

	return 0;
}

Measured memory_bytes: 5500
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <cmath>
#include <complex>
#include <map>
#include <set>
#include <vector>
#include <stack>
#include <queue>
#include <bitset>
#include <algorithm>
#include <numeric>
#include <functional>
#include <cassert>
#include <iomanip>
using namespace std;

#define Rep(b, e, i) for(int i = b; i <= e; i++)
#define Repr(e, b, i) for(int i = e; i >= b; i--)
#define rep(n, i) Rep(0, n-1, i)
#define repr(n, i) Repr(n-1, 0, i)
#define all(v) (v).begin(), (v).end()
#define pb(v) push_back(v)
#define uniq(v) (v).erase(unique(all(v)),(v).end())
#define bitcnt(x) __builtin_popcount(x)
#define fst first
#define snd second
#define Pqaz(T) priority_queue<T,vector<T>,greater<T>>
#define Pqza(T) priority_queue<T>
#define put(x) cout << x;
#define putsp(x) cout << x << ' ';
#define putbd cout << "---------------------------------------------" << endl;
#define putln(x) cout << x << endl;
#define debug(x) cerr << #x << "=" << x << endl;
#define ENJYU std::ios::sync_with_stdio(false);std::cin.tie(0);

typedef long long ll;
typedef pair<ll, ll> llP;
typedef pair<int, int> intP;
typedef complex<double> comp;
typedef vector <int> vec;
typedef vector <ll> vecll;
typedef vector <double> vecd;
typedef vector <vec> mat;
typedef vector <vecll> matll;
typedef vector <vecd> matd;

//vector の中身を出力
template <class T>ostream &operator<<(ostream &o,const vector<T>&v)
{o<<"{";for(int i=0;i<(int)v.size();i++)o<<(i>0?", ":"")<<v[i];o<<"}";return o;}

const int MAX = 200020;
const double PI = 3.14159265358979323846;
const double EPS = 1e-12;
const int INF = 1<<29;
const ll INFL = 1e18;
const int MOD = 1000000007;

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

//********************************template END****************************************//

void solve(void){
	string S;
	cin >> S;
	int l = S.size();
	matll dp(2, vecll(4, 0));
	dp[0][0] = 1;
	rep(l, i)
	{
		rep(4, j)
		{
			dp[(i&1)^1][j] += dp[i&1][j] * (S[i] == '?' ? 3 : 1) % MOD;
			dp[(i&1)^1][j] %= MOD;
		}
		if (S[i] == '?')
		{
			rep(3, j)
			{
				dp[(i&1)^1][j+1] += dp[i&1][j];
				dp[(i&1)^1][j+1] %= MOD;
			}
		}
		if (S[i] == 'A')
		{
			dp[(i&1)^1][1] += dp[i&1][0];
			dp[(i&1)^1][1] %= MOD;
		}
		if (S[i] == 'B')
		{
			dp[(i&1)^1][2] += dp[i&1][1];
			dp[(i&1)^1][2] %= MOD;
		}
		if (S[i] == 'C')
		{
			dp[(i&1)^1][3] += dp[i&1][2];
			dp[(i&1)^1][3] %= MOD;
		}
		rep(4, j)
		{
			dp[i&1][j] = 0;
		}
	}

	cout << dp[l&1][3] << endl;
}

int main(void){
	solve();
	//cout << "yui(*-v・)yui" << endl;
	return 0;
}


Measured memory_bytes: 512
n = int(input())
a,b=[],[]
for i in range(1,int(n**0.5)+1):
    if n%i==0:
        a.append(i)
        b.append(int(n/i))
ans=[]
for i in range(len(a)):
    ans.append(max(len(str(a[i])),len(str(b[i]))))
print(min(ans))

Measured memory_bytes: 3188
#include <bits/stdc++.h>
#include <algorithm>
using namespace std;
 
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep1(i, n) for (int i = 1; i < (int)(n); i++)
#define print(a) cout << (a) << endl; 
typedef long long ll;
const int MOD = 1000000007; 
 
int main() {
    int n;
    unordered_map<int, int> as;
    vector<int> c(10, 0);
    for (int i = 1; i < 10; ++i) {
        int a;
        cin >> a;
        as[a] = i;
    }
    cin >> n;
    for (int i = 0; i < n; ++i) {
        int b;
        cin >> b;
        if (as[b]) {
            c[as[b]] = 1; 
        }
    }
    if ((c[1] * c[2] * c[3]) 
     || (c[4] * c[5] * c[6])  
     || (c[7] * c[8] * c[9])  
     || (c[1] * c[4] * c[7])  
     || (c[2] * c[5] * c[8])  
     || (c[3] * c[6] * c[9])  
     || (c[1] * c[5] * c[9])  
     || (c[3] * c[5] * c[7])  
    ){
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
    //for (int i = 1; i < 10; ++i) cout << i << "," << c[i] << endl;
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<stdio.h>
//#include <bits/stdc++.h>
#include<vector>
#include<float.h>
#include<iomanip>
#include<algorithm>
#include<string>
#include<cstring>
#include<math.h>
#include<cmath>
#include<sstream>
#include<set>
#include<map>
#include<queue>
#include <cassert>
#include <cmath>
#include<cstdint>

#define INF 1e9
#define rep(i,n)for(int i=0;(i)<(int)(n);i++)
#define REP(i,a,b)for(int i=(int)(a);(i)<=(int)(b);i++)
#define VEC(type, c, n) std::vector<type> c(n);for(auto& i:c)std::cin>>i;
#define vec(type,n) vector<type>(n)
#define vvec(m,n) vector<vector<int>> (int(m),vector<int>(n))
#define ALL(a)  (a).begin(),(a).end()

using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
using P = pair<int,int>;

vector<int>bitSearch(int bit,int n){
    vector<int>S;
    rep(i,n)if(bit&(1<<i))S.push_back(i);
    return S;
}


int main(){
    ll x;cin>>x;
    ll dist = 0;
    int i = 0;
    while(x>dist){
        i++;
        dist += i;
    }
    cout<<i;
}



Measured memory_bytes: 256
/*
        ***Fresher***
    Md Mahfujur Rahman Khan
    Dept. of CSE
    CSE-28 Batch
    JU-48 Batch
    Jahangirnagar University

*/
#include<iostream>
#include<cstdio>
#include<string>
#include<vector>
#include<queue>
#include<cmath>
#include<algorithm>
#include<iomanip>
#include<functional>
#include<set>
#include<map>
#include<climits>
#include<numeric>
#include<utility>
using namespace std;
#define V_ vector
#define Q_ queue
#define S_ set
#define ST_ stack
#define M_ map
#define DQ_ deque

#define pii pair<ll,ll>
#define pci pair<char,ll>
#define psi pair<string, ll>
#define pis pair<ll,string>
#define pic pair<ll, char>

#define mii map<ll,ll>
#define msi map<string, ll>
#define mis map<ll, string>
#define mib map<ll,bool>
#define msb map<string,bool>

#define vi vector<ll>
#define vs vector<string>

#define ivi vector<ll> :: iterator
#define ivs vector<string> :: iterator
#define imii map<ll,ll> :: iterator
#define imsi map<string,ll> :: iterator
#define imis map<ll, string> :: iterator
#define imib map<ll, bool> :: iterator
#define imsb map<string, bool> :: iterator

#define FAST ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

#define F first
#define S second
#define pi 2*acos(0.0)
#define PB(x) push_back(x)
#define PP(x) push(x)
#define RSZ(n) resize(n)
#define POB pop_back()
#define P_ pop()
#define CL_ clear()
#define LEN_ length()
#define SZ_ size()
#define CNT_ count()
#define FF first.first
#define FS first.second
#define SF second.first
#define SS second.second
#define B_ begin()
#define E_ end()
#define F_ front()
#define t_ top()
#define IN_ insert
#define ER_  erase
#define GL_ getline
#define NL_   "\n"
#define SP_ " "

#define fr(i, n) for(i = 0; i < n; i++)
#define fe(x, n) for(i = x; i <= n; i++)

#define ul unsigned long long int
#define ll long long int
#define  MAX 250000
vi v;


ll N, T, tc = 0, i, j, k;
bool check(ll n)
{
    ll x,a = 0, b = 0, c = 0;
    while(n)
    {
        x = n%10;
        if(x==3) a = 1;
       else if(x==5) b = 1;
        else if(x==7) c = 1;
        n/= 10;
    }
    return (a&&b&&c);
}

void make(ll n)
{
    if(n>1000000000) return;
    if(check(n))
    {
        v.PB(n);
    }
     make(n*10+3);
     make(n*10+5);
     make(n*10+7);
     return ;
}

int main()
{
    make(3);
    make(7);
    make(5);
    sort(v.B_, v.E_);

    ll c = 0;
    cin >> N;
    while(c < v.SZ_  and v[c]<=N) c++;
    cout << c;

}


Measured memory_bytes: 640
#include "bits/stdc++.h"

using namespace std;

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

#define dump(x)  cerr << #x << " = " << (x) << endl
#define rep(i,n) for(int i=0;i<(n);i++)
#define all(a)  (a).begin(),(a).end()
#define pb push_back

int edge[50][50];

int main(){
	int n;
	while(cin>>n){
		if(n==0)break;

		rep(i,50)rep(j,50){
			if(i==j)edge[i][j]=0;
			else edge[i][j]=99999999;
		}

		int m=-1;
		rep(i,n){
			int a,b,c;
			cin>>a>>b>>c;
			m=max( m , max(a,b) );
			edge[a][b]=edge[b][a]=c;
		}
		m++;
		rep(k,m){
			rep(i,m){
				rep(j,m){
					edge[i][j]=min( edge[i][j] , edge[i][k]+edge[k][j] );
				}
			}
		}
		int mini=9999999;
		int num;
		rep(i,m){
			int sum=0;
			rep(j,m){
				sum+=edge[i][j];
			}
			if(mini>sum){
				mini=sum;
				num=i;
			}
		}
		cout<<num<<" "<<mini<<endl;
	}
	return 0;
}

Measured memory_bytes: 1172
//i ll be the king
#include<bits/stdc++.h>
#define ll long long int
#define sync ios_base::sync_with_stdio(false); cin.tie(NULL) 
#define input(arr,n) for(ll i1=0;i1<n;i1++ )cin>>arr[i1]
#define rep(n) for(ll i2=0;i2<n;i2++)
#define vmp(v,a,b) v.push_back(make_pair(a,b))
#define si(a) scanf("%lld",&a)
#define pi(a) printf("%lld",a)
#define aset(a,n,k) for(ll i3=0;i3<n;i3++)a[i3]=k; 	
#define mod 1000000007
#define mp(a,b) make_pair(a,b)
#define f first
#define s second 
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<ll, null_type,greater_equal<ll>, rb_tree_tag,tree_order_statistics_node_update>//s.order_of_key(val) *s.find_by_orde(ind)
using namespace std;
int main()
{
	sync;
	ll n,k;
	cin>>n>>k;
	long double ans=0.0;
	for(ll i=1;i<=n;i++)
	{
		ll j=i;long double val=1.0;
		while(j<k)
		{
			j*=2;
			val/=2.0;
		}
		ans+=val;
	}
	ans/=(long double)n;
	cout<<fixed<<setprecision(10)<<ans;
}

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

#define REP(i, m, n) for (int i = (m); i < (int)(n); i++)
#define REPS(i, m, n) for (int i = (m); i <= (int)(n); i++)
#define rep(i, n) REP(i, 0, n)
#define reps(i, n) for (int i = 0; i <= (int)(n); i++)
#define rrep(i, x) for (int i = ((int)(x)-1); i >= 0; i--)
#define rreps(i, x) for (int i = (int)(x); i >= 0; i--)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pb push_back
#define fi first
#define se second
typedef long long ll;
typedef pair<int, int> P;
const int inf = INT_MAX;
const ll INF = 1LL << 60;
const ll mod = 1e9 + 7;
const double EPS = 1e-10;
const double PI = acos(-1.0);
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<typename A, size_t N, typename T> void Fill(A (&array)[N], const T &val) { fill( (T*)array, (T*)(array+N), val ); }


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

    vector<string> d {"SUN", "MON", "TUE", "WED", "THU", "FRI", "SAT"};
    string s; cin >> s;
    rep(i, d.size()) if (s == d[i]) {
        cout << d.size() - i << endl;
        return 0;
    }
    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<string.h>
#define LEN 100005

typedef struct pp{
  char name[100];
  int t;
}P;

P Q[LEN+1];
int head, tail, n;

void enqueue(P x){
  Q[tail] = x;
  tail = (tail + 1) % LEN;
}

P dequeue(){
  P x = Q[head];
  head = (head + 1) % LEN;
  return x;

}

int min(int a, int b){
  if(a < b){
    return a;
  }
  if(a > b){
    return b;
  }
  else return a;
}

int main(){
  int elaps = 0, c;
  int i, q;
  P u;
  scanf("%d %d", &n, &q);

  for ( i = 1; i <= n; i++){
    scanf("%s", Q[i].name);
    scanf("%d", &Q[i].t);
  }
  head = 1;
  tail = n + 1;

  while(head != tail){
    u = dequeue();
    c = min(q,u.t);
    u.t = u.t - c;
    elaps += c;
    if(u.t > 0){
      enqueue(u);
    }
    else printf("%s %d\n",u.name, elaps);
  }
  
  
  return 0;
}



Measured memory_bytes: 11852
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG
#define rep2(i, m, n) for(int i=int(m); i<int(n); i++)
#define rep(i, n) rep2(i, 0, n)
#define ALL(a) a.begin(), a.end()
using ll = long long;
using ld = long double;
using V = vector<int>;
using Vll = vector<ll>;
using Vld = vector<ld>;
using VV = vector<V>;
using VVll = vector<Vll>;
using VVld = vector<Vld>;
using P = pair<int, int>;
using Pll = pair<ll, ll>;
using Pld = pair<ld, ld>;
const int INF = 1<<30;
const ll INFll = 1ll<<62;
const ld EPS = 1e-10;
const int MOD = int(1e9)+7;
template<typename T> inline bool chmin(T& a, T b) {if(a>b) {a=b; return true;} return false;}
template<typename T> inline bool chmax(T& a, T b) {if(a<b) {a=b; return true;} return false;}


int main() {
  ll k; cin >> k;
  k--;
  V a = {1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};
  cout << a[k] << endl;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>

using namespace std;

typedef struct Node {
	int val;
	Node *parent = NULL;
	Node *left = NULL;
	Node *right = NULL;
} Node;


Node *Tree = NULL; //树 

void insert(int key) {
	Node *cur = Tree;
	Node *parent = NULL;
	while (cur != NULL) {
		parent = cur;
		if (key < cur->val) {
			cur = cur->left;
		} else {
			cur = cur->right;
		}
	}
	if (parent == NULL) {
		Tree = new Node;
		Tree->val = key;
		return;
	}
	Node *t = new Node;
	t->val = key;
	t->parent = parent;
	if (key < parent->val) {
	   parent->left = t;
    } else {
    	parent->right = t;
	}
}


void printPre(Node * node) {
	cout  << " " << node->val;
	if (node->left != NULL) {
		printPre(node->left);
	}
	
	if (node->right != NULL) {
		printPre(node->right);
	}
}

void printIn(Node * node) {

	if (node->left != NULL) {
		printIn(node->left);
	}
	cout  << " " << node->val;
	if (node->right != NULL) {
		printIn(node->right);
	}
}

int main() {
	int n;
	cin >> n;
	for (int i=0;i<n;i++) {
		string s;
		cin >> s;
		if (s[0] == 'i') {
			long long key;
			cin >> key;
			insert(key);
		} else if (s[0] == 'p') {
			printIn(Tree);
			cout << endl;
			printPre(Tree);
			cout << endl;
		}
	}
	return 0;
	
}


Measured memory_bytes: 26564
import sys
from heapq import heappop, heappush

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, M = lr()
# 3*N頂点あるとする
edges = [[] for _ in range(3*N + 4)] # 3-indexed
for _ in range(M):
    u, v = lr()
    u *= 3; v *= 3
    edges[u].append(v+1)
    edges[u+1].append(v+2)
    edges[u+2].append(v)

INF = 10 ** 18

def dijkstra(start):
    dist = [INF] * (3*N+4)
    dist[start] = 0
    que = [(0, start)]
    while que:
        d, v = heappop(que)
        if dist[v] < d:
            continue
        for next in edges[v]:
            d1 = d + 1
            if dist[next] > d1:
                dist[next] = d1
                heappush(que, (d1, next))
    return dist

S, T = lr()
dist = dijkstra(S*3)
if dist[T*3] == INF:
    print(-1)
else:
    print(dist[T*3] // 3)


Measured memory_bytes: 89764
n = int(input())
arr = list(map(int, input().split(" ")))

# Sort arr, firstly
arr.sort(reverse=True)

a_arr = []
b_arr = []

for (i, ele) in enumerate(arr):
    # Alice
    if i % 2 == 0:
        a_arr.append(ele)
    # Bob
    else:
        b_arr.append(ele)

print(sum(a_arr) - sum(b_arr))

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

int main() {
    int n, l;
    cin >> n >> l;
    vector<string> ss(n);
    rep(i, n) { cin >> ss[i]; }

    sort(ss.begin(), ss.end());
    rep(i, n) { cout << ss[i]; }
    cout << endl;
}

Measured memory_bytes: 3644
import sys
from collections import deque
import copy
import math
def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline

def is_fall(S, start, end_point, magic_list):
    i = start
    for ml in magic_list:
        if i == -1 or i == len(S):
            break
        if S[i] == ml[0]:
            if ml[1] == 'L':
                i -= 1
            else:
                i += 1
        if i == end_point:
            return True
    return False




def bin_search(S,  magic_list, end_point):
    L = -1
    R = len(S)
    while 1:
        if R - L <= 1:
            if end_point == len(S):
                return R
            else:
                return L
        M = (L + R)/2
        res = is_fall(S, M, end_point, magic_list)
        if res == True:
            if end_point == len(S):
                R = M
            else:
                L = M
        else:
            if end_point == len(S):
                L = M
            else:
                R = M





def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [N, Q] = [int(input_raw[0]), int(input_raw[1])]
    input_raw = read_func().strip().split()
    S = input_raw[0]

    magic_list = []
    for i in range(Q):
        input_raw = read_func().strip().split()
        [t, s] = [(input_raw[0]), (input_raw[1])]
        magic_list.append((t, s))
    L_end = bin_search(S, magic_list, -1) + 1
    R_end = N - bin_search(S, magic_list, len(S))
    print N - L_end - R_end




if __name__ == '__main__':
    main()


Measured memory_bytes: 66204
#include<iostream>
using namespace std;
int main() {
    int N,T,H,cnt=1;
    cin >> N;
    for (int i=0; i<N; i++) {
        if (i == 0) {
            cin >> T;
        } else {
            cin >> H;
            if (H == T) cnt++;
            if (H > T) {
                cnt++;
                T = H;
            }
        }
    }
    cout << cnt << endl;
    return 0;
}


Measured memory_bytes: 256
N, T = map(int, input().split())
ts = list(map(int, input().split()))

total = 0
for i in range(1, len(ts)):
    if ts[i] - ts[i-1] >= T:
        total += T
    else:
        total += ts[i] - ts[i-1]
total += T

print(total)

Measured memory_bytes: 25196
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<cctype>
using namespace std;
int main()
{
	int a,w=0,s=0;
	for(int i=1;i<=3;i++)
	{
		cin>>a;
		if(a==5)w++;
		if(a==7)s++;
	}
	if(w==2&&s==1)cout<<"YES"<<endl;
	else cout<<"NO"<<endl;
	return 0;
}


Measured memory_bytes: 256
using namespace std;
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <bitset>
#include <iterator>
#include <set> 
#include <unordered_set>
#include <string>
#include <functional>
#include <limits.h>
//#include <bits/stdc++.h> 
//#include <list>
#include <stack>
#include <stdio.h>
typedef signed long long ll; //watch out ll= int*int will not become ll, rather (ll)ini*int casting will work
#include <queue>
#include <math.h>
#include <deque>
#define ffor(i,n) for(int i = 0;i < (n); ++i)
#define all(v) v.begin(),v.end()
#define vi vector<int>
#define vvi vector<vi>
#define pii pair<int,int>
#define vpii vector<pii>
//typedef long float lf;
#include <cmath>
#include <iomanip>
#include <numeric>
#include <stdio.h>
const long double PI = 3.141592653589793238L;
/*struct CustomCompare
{
	bool operator()(pii& p1, pii& p2)
	{
		if (p1.second - p1.first == p2.second - p2.first)
			return p1.first > p2.first;

		return p1.second - p1.first < p2.second - p2.first;
	}
};*/
int tt, n, k, inp, a, b, x,m;
void pv(vector<int> a) {
	for (auto i : a)
		cout << i<< ' ';
	cout << '\n';
}
void pv(vector<char> a) {
	for (auto i : a)
		cout << i;
	cout << '\n';
}
void pp (vector<pair<int, int>> a) {
	for (auto i : a)
		cout << i.first << ' ' << i.second<<'\n';
}
void copy(vector<long long>& a, vector<long long>& b) {
	b[0] = a[0];
	for (unsigned i = 1; i < a.size(); i++) {
		b[i] = b[i - 1] + a[i];
	}

}
int tryy(vector<int>& a, int start, int end, int fireball, int berzerk, int k) {
	int counter = start + 1, extra = 0, ans = 0;
	while (counter < end) {
		cout << "yeah";
		if (a[counter] < max(a[start], a[end])) {
			counter++; extra++;
		}
		else {
			if (end - counter >= k) {
				counter += k;
				ans += fireball;
			}
			else {
				extra -= berzerk * (k - (end - counter));
				counter = end;
			}
		}
	}
	cout << "counter extra ans " << counter << ' ' << extra << ' ' << ans << endl;
	//int waste = extra % k;
	//return ans+ extra*min(berzerk*k,fireball)+berzerk;
	return ans + extra / k * min(k * berzerk, fireball) + (extra % k) * berzerk;

}
int main() {
	int n;
	cin >> n; 
	vector<ll>a(n), pref(n);
	for (int i = 0; i < n; i++)
		cin >> a[i];
	pref[0] = a[0];
	for (int i = 1; i < n; i++) {
		pref[i] = pref[i - 1] + a[i];
	}
	vector<vector<ll>> dp(n);
	for (int i = 0; i < n; i++)
		dp[i] = vector<ll>(n);
	for (int i = 0; i < n; i++)
		dp[i][i] = 0;//a[i];
	for (int k = 1; k <= n-1; k++) {
		for (int i = 0; i + k < n; i++) {
			dp[i][i + k] = LLONG_MAX;
			for (int part = 0; part < k; part++) {
				dp[i][i + k] = min(dp[i][i + k], dp[i][i + part] + dp[i + part + 1][i + k] + pref[i + k] - pref[i] +a[i]);
			}
		}
	}
	cout << dp[0][n - 1];
}

Measured memory_bytes: 4872
#ifdef LOCAL
#include "libs/debug/print_list.hpp"
#define debug(x) (cout << # x ": " << x << endl)
#define dev(v, m, n) for(int i=0;i<n;++i){for(int j=0;j<m;++j){cout<<"|"<<v[j][i];}cout<<"|"<<endl;}
#else
#define debug(x) ;
#define dev(v, m, n) ;
#endif

// :----------------------------------------

#include <algorithm>
#include <cassert>
#include <cmath>
#include <deque>
#include <iomanip>
#include <iostream>
#include <list>
#include <numeric>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>

using namespace std;

#define int long long int
#define rep(i, n) for (int i = 0; i < n; ++i)
#define all(x) (x).begin(), (x).end()
#define capi(x) int x;cin>>x
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

using vi = vector<int>;
using pi = pair<int, int>;
using vp = vector<pi>;

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

#define P (1'000'000'007)

signed main() {
    capi(n);

    vi va;
    
    rep(i, n) {
        capi(a);
        va.push_back(a);
    }

    int ans = 1;
    int sum = va[0];

    int l = -1; int r = 0;

    while (r < n - 1) {
        if ((sum xor va[r + 1]) == sum + va[r + 1]) {
            ++r;
            sum += va[r];
            ans += r - l;
        } else {
            ++l;
            sum -= va[l];
        }
        // debug(r);
        // debug(l);
        // debug(sum);
    }

    cout << ans;

    return 0;
}


Measured memory_bytes: 4960
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <tuple>
#include <queue>
#include <stack>
#include <set>
#include <map>

using namespace std;

class Solver {
};

int main() {
	while (true) {
		int m, t, p, r;
		cin >> m >> t >> p >> r;
		if (m == 0)break;

		vector<vector<int>> status(t, vector<int>(p));
		vector<tuple<int, int, int>> results;
		for (int i = 0; i < t; i++)results.emplace_back(make_tuple(0, i, 0));

		for (int i = 0; i < r; i++) {
			int mi, ti, pi, ji;
			cin >> mi >> ti >> pi >> ji;
			if (ji == 0) {
				get<0>(results[ti - 1]) += mi + status[ti - 1][pi - 1] * 20;
				get<2>(results[ti - 1])++;
			}
			else {
				status[ti - 1][pi - 1]++;
			}
		}

		stable_sort(results.begin(), results.end(),
			[](auto a,auto b) {
				int delta0 = get<0>(a) - get<0>(b);
				int delta1 = get<1>(a) - get<1>(b);
				int delta2 = get<2>(a) - get<2>(b);
				if (delta2 == 0) {
					if (delta0 == 0)return delta1 > 0;
					else return delta0 < 0;
				}
				else return delta2 > 0;
			}); 
		for (int i = 0; i < t; i++) {
			if (i > 0) {
				if (get<0>(results[i]) == get<0>(results[i - 1]))cout << '=';
				else cout << ',';
			}
			cout << get<1>(results[i]) + 1;
		}
		cout << endl;
	}
}


Measured memory_bytes: 3144