akhauriyash/Code-Regression huggingface dataset:
using System;
using System.IO;
using System.Collections.Generic;
using System.Linq;

namespace ABC117D
{
    public class Program
    {
        void Solve(StreamScanner ss, StreamWriter sw)
        {
            //---------------------------------
            const int MAX = 50;

            var N = ss.Next(int.Parse);
            var K = ss.Next(long.Parse);
            var A = ss.Next(long.Parse, N);

            var pops = new long[MAX];
            foreach (var a in A)
            {
                for (long i = 0, t = a; t > 0; i++, t >>= 1)
                {
                    if ((t & 1) == 1) pops[i]++;
                }
            }

            var memo = new long[MAX];
            for (long i = 0, t = 1; i < MAX; i++, t <<= 1)
            {
                memo[i] += Math.Max(N - pops[i], pops[i]) * t;
                if (i > 0) memo[i] += memo[i - 1];
            }

            var ans = 0L;
            var calc = 0L;
            var kBase2 = Convert.ToString(K, 2);
            var kBase2Rev = (new string('0', MAX - kBase2.Length) + kBase2).Select(c => c - '0').Reverse().ToArray();

            for (long i = MAX - 1, t = 1L << (MAX - 1); i >= 0; i--, t >>= 1)
            {
                if (kBase2Rev[i] == 0)
                {
                    calc += pops[i] * t;
                }
                else
                {
                    if (i > 0) ans = Math.Max(ans, calc + pops[i] * t + memo[i - 1]);
                    calc += (N - pops[i]) * t;
                }
            }

            ans = Math.Max(ans, calc);
            sw.WriteLine(ans);
            //---------------------------------
        }

        static void Main()
        {
            var ss = new StreamScanner(new StreamReader(Console.OpenStandardInput()));
            var sw = new StreamWriter(Console.OpenStandardOutput()) {AutoFlush = false};
            new Program().Solve(ss, sw);
            sw.Flush();
        }

        static readonly Func<string, string> String = s => s;
    }

    public class StreamScanner
    {
        static readonly char[] Sep = {' '};
        readonly Queue<string> buffer = new Queue<string>();
        readonly TextReader textReader;

        public StreamScanner(TextReader textReader)
        {
            this.textReader = textReader;
        }

        public T Next<T>(Func<string, T> parser)
        {
            if (buffer.Count != 0) return parser(buffer.Dequeue());
            var nextStrings = textReader.ReadLine().Split(Sep, StringSplitOptions.RemoveEmptyEntries);
            foreach (var nextString in nextStrings) buffer.Enqueue(nextString);
            return Next(parser);
        }

        public T[] Next<T>(Func<string, T> parser, int x)
        {
            var ret = new T[x];
            for (var i = 0; i < x; ++i) ret[i] = Next(parser);
            return ret;
        }

        public T[][] Next<T>(Func<string, T> parser, int x, int y)
        {
            var ret = new T[y][];
            for (var i = 0; i < y; ++i) ret[i] = Next(parser, x);
            return ret;
        }
    }
}

Measured memory_bytes: 29532
use std::cmp::*;
use std::collections::*;
use std::io::*;
use std::str::FromStr;
fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}
fn main(){
    let s:String = read();
    let v:Vec<char> = s.chars().collect();
    let mut sum:Vec<usize> = vec![0;s.len() + 1];
    for i in 0..s.len(){
        let mut flag = 0;
        if(v[i] == '<'){
            flag += 1;
            sum[i + 1] = max(sum[i] + flag ,sum[i + 1]);
        }

    }
    for i in (0..s.len()).rev(){
        let mut flag = 0;
        if v[i] == '>'{
            flag += 1;
            sum[i] = max(sum[i + 1] + flag,sum[i]);
        }
        //sum_b[s.len() - 1 - i] = max(sum_b[s.len() - i] + flag,sum_b[s.len() - i - 1]);
    }
    let mut ans = 0;
    for i in 0..s.len() + 1{
        ans += sum[i];
    }
    //println!("{:?}",sum_a);
    //println!("{:?}",sum_b);
    println!("{}",ans);
}

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

using namespace std;

int main()
{
    int n;
    string str;
    cin >> n;
    cin >> str;
    int left = 0, right = n-1;
    int cnt = 0;
    
    while(left <= right){
        while(left < n && str[left] != 'W')
            left++;
        while(right >= 0 && str[right] != 'R')
            right--;
        if(left < n && right >= 0 && left < right){
            char tmp = str[right];
            str[right] = str[left];
            str[left] = tmp;
            left++;
            right--;
            cnt++;
        }
            
    }
    cout << cnt << '\n';
    return 0;
}



Measured memory_bytes: 3728
/**
*    created: 11.05.2020 23:48:44
**/
#include <bits/stdc++.h>
#define int long long
const int INF = 1e18L + 5;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
using namespace std;

signed main() {

    cin.tie(0);
    ios_base::sync_with_stdio(false);

    int n; cin >> n;
    cout << n*(n-1)/2 << endl;
    return 0;
}

Measured memory_bytes: 256
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 d = a / b;
        int r = a % b;
        double f = (double)a / b;
        System.out.println(String.format("%d %d %.5f", d, r, f));
    }
}

Measured memory_bytes: 26456
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <cstdio>
#include <cmath>
#include <limits.h>
using namespace std;
typedef long long LL;
const int N=2e5+5;
const LL M=1e9+7;

int n,u,v,sz[N];
LL cnt[N],ans[N];
vector<int> G[N];
LL p[N],inv[N];

LL exgcd(LL a,LL b,LL &x,LL &y) {
	LL d=a;
	if(b!=0) {
		d=exgcd(b,a%b,y,x);
		y-=(a/b)*x;
	}
	else {
		x=1;y=0;
	}
	return d;
}

LL mod_inv(LL a,LL m) {
	LL x,y;
	exgcd(a,m,x,y);
	return (m+x%m)%m;
}

LL C(int n, int m) {
	return p[n]*inv[n-m]%M*inv[m]%M;
}

void init() {
	p[0]=1;
	inv[0]=1;
	for(int i=1;i<=n;i++) {
		p[i]=p[i-1]*i%M;
		inv[i]=mod_inv(p[i],M);
	}
}

void dfs(int u,int f) {
	sz[u]=1;
	cnt[u]=1;
	for(int v:G[u]) {
		if(v==f) continue;
		dfs(v,u);
		sz[u]+=sz[v];
		cnt[u]=cnt[u]*cnt[v]%M*inv[sz[v]]%M;
	}
	cnt[u]=cnt[u]*p[sz[u]-1]%M;
}

void dfs2(int u,int f) {
	if(u==1) {
		ans[u]=cnt[u];
	}
	else {
		//cout<<"gou "<<u<<endl;
		//printf("ans[%d]=%lld\n", f,ans[f]);
		ans[u]=ans[f]*mod_inv(C(n-1,sz[u])*cnt[u]%M,M)%M*inv[n-sz[u]]%M;
		//printf("aaa %lld %lld %lld %lld %lld\n",ans[f],C(n-1,sz[u]),cnt[u],mod_inv(C(n-1,sz[u])*cnt[u]%M,M),inv[n-sz[u]]);
		for(int v:G[u]) {
			if(v==f) continue;
			ans[u]=ans[u]*cnt[v]%M*inv[sz[v]]%M;		
		}
		ans[u]=ans[u]*p[n-1]%M;
	}
	for(int v:G[u]) {
		if(v==f) continue;
		dfs2(v,u);
	}
}

int main() {
	scanf("%d",&n);
	init();
	for(int i=1;i<n;i++) {
		scanf("%d %d",&u,&v);
		G[u].push_back(v);
		G[v].push_back(u);
	}
	dfs(1,0);
	dfs2(1,0);
	for(int i=1;i<=n;i++) {
		printf("%lld\n",ans[i]);
	}
}


Measured memory_bytes: 20980
#include<iostream>
#include<vector>
using namespace std;
int N;
vector<pair<int,int> >ans;
main()
{
	cin>>N;
	for(int i=1;i<N;i+=3)
	{
		for(int j=0;j<N;j++)
		{
			if((i+j)%2==1)ans.push_back(make_pair(i,j));
		}
	}
	if(N%3==1)
	{
		for(int j=0;j<N;j++)
		{
			if((N-1+j)%2==1)ans.push_back(make_pair(N-1,j));
		}
	}
	for(int i=0;i<N;i++)
	{
		if(i%2==1&&i%6!=1&&(N%6!=4||i!=N-1))ans.push_back(make_pair(i,0));
	}
	cout<<ans.size()<<endl;
	for(pair<int,int>p:ans)cout<<p.first<<" "<<p.second<<endl;
}

Measured memory_bytes: 2928
# import numpy as np
import math
# import copy
# from collections import deque
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(10000)


def main():
    N,M = map(int,input().split())

    res = 0

    if N >= 2:
        res += math.factorial(N) // (math.factorial(N-2) * math.factorial(2))

    if M >= 2:
        res += math.factorial(M) // (math.factorial(M-2) * math.factorial(2))

    print(res)



main()


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

int main(){
	int a, b;

	while(1){
		cin >> a >> b;

		if(a == 0 && b == 0) break;

		if(a < b){
			cout << a << " " << b << endl;
		}else{
			cout << b << " " << a << endl;
		}
	}

	return 0;
}


Measured memory_bytes: 3016
#include <set>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>

#define x first
#define y second

using namespace std;

typedef long long LL;
typedef pair<int,int>PII;

const int maxn = 2e5 + 10;

int t,n,m;

vector<int>G[maxn];

int value[maxn];

int main(void) {
	int n,m;
	cin >> n >> m;
	int u,v,a;
	for(int i = 1; i <= n; i ++) {
		scanf("%d",&a);
		value[i] = a;
	}
	for(int i = 1; i <= m; i ++) {
		scanf("%d%d",&u,&v);
		G[u].push_back(v);
		G[v].push_back(u);
	}
	int ans = 0;
	for(int i = 1; i <= n; i ++) {
		bool flag = true;
		for(int j = 0; j < G[i].size(); j ++) {
			if(value[i] <= value[G[i][j]]) {
				flag = false;
				break;
			}
		}
		if(flag || G[i].size() == 0) ans ++;
	}
	cout << ans << endl;
	return 0;	
} 

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

using namespace std;
typedef long long ll;
typedef long double lb;
#define rep(i,j,n) for (ll i = j; i < (n); i++)
#define repr(i,j,n) for(ll i = j; i >= (n); i--)
#define all(x) (x).begin(),(x).end()
#define CLR(mat,f) memset(mat, f, sizeof(mat))
#define IN(a, b, x) (a<=x&&x<b)
#define out(ans) cout << ans << endl
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; }
typedef pair<ll,ll>P;
const ll mod=1e9+7;
const ll INF = 1LL<<60;
const ll m=1LL<<32;

int main(){

  ll n,x,y;cin>>n>>x>>y;

  ll res[n+1];CLR(res,0);
  rep(i,1,n){
    ll ans=0;
    rep(j,1,n-i+1){
      ll mi=min(i,abs(j-x)+1+abs(y-(j+i)));
      res[mi]++;
    }
  }

  rep(i,1,n){
    out(res[i]);
  }

  return 0;
}


Measured memory_bytes: 256
import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main{

	Scanner sc=new Scanner(System.in);

	int INF=1<<28;
	double EPS=1e-9;

	void run(){
		int n=sc.nextInt();
		int k=sc.nextInt();
		for(int i=0; i<k; i++){
			int x=sc.nextInt()-1;
			int y=sc.nextInt()-1;
			int xx=min(x, n-1-x);
			int yy=min(y, n-1-y);
			println((min(xx, yy)%3+1)+"");
		}
	}

	void debug(Object... os){
		System.err.println(Arrays.deepToString(os));
	}

	void print(String s){
		System.out.print(s);
	}

	void println(String s){
		System.out.println(s);
	}

	public static void main(String[] args){
		// System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
		new Main().run();
	}
}

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

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

inline bool out(int x, int y) {
	return x < 0 || y < 0 || x >= SIZE || y >= SIZE;
}

void dfs(int x, int y, array<string, SIZE> &field) {
	field[y][x] = '0';

	for(int d = 0; d < 4; ++d) {
		const int nx = x + dx[d];
		const int ny = y + dy[d];

		if(out(nx, ny)) continue;
		if(field[ny][nx] == '1') dfs(nx, ny, field);
	}
}

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

	array<string, SIZE> field;

	while(cin >> field[0]) {
		for(int i = 1; i < SIZE; ++i) {
			cin >> field[i];
		}

		int cnt = 0;
		for(int y = 0; y < SIZE; ++y) {
			for(int x = 0; x < SIZE; ++x) {
				if(field[y][x] == '1') {
					++cnt;
					dfs(x, y, field);
				}
			}
		}

		cout << cnt << "\n";
	}

	return 0;
}

Measured memory_bytes: 1188
#include "bits/stdc++.h"
using namespace std;
const int N = 1e5 + 5;
int main()
{
    int h,n,sum = 0;
    cin>>h>>n;
    int a[n];
    for(int i = 0; i < n; ++i){
        cin>>a[i];
        sum += a[i];
    }
    cout<<(sum>=h ? "Yes" : "No")<<endl;
    return 0;
}


Measured memory_bytes: 640
MOD = 1000000007

n, m = map(int, input().split())
broken = [False] * (n + 1)
for _ in range(m):
    broken[int(input())] = True
dp = [0] * (n + 1)
dp[0] = 1 if not broken[0] else 0
dp[1] = 1 if (dp[0] and not broken[1]) else 0
for i in range(2, n + 1):
    if broken[i]:
        continue
    dp[i] = (dp[i - 2] + dp[i - 1]) % MOD
print(dp[n])

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

int main() {
	int a, b, k;
	cin >> a >> b >> k;
	int ans=0;
	for (int i = 0;i < k&&a+i<=b;i++) {
		ans = a + i;
		cout << ans << endl;
	}
	for (int j = k - 1;j >= 0;j--) {
		if (b - j > ans) {
			cout << b - j << endl;
		}
	}
	return 0;
}

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

int main(){
  int a,b,c,s=0;
  cin >> a >> b >> c;
  
  s = max(max(a,b),c);
  
  if ( a+b+c - s == s){
    cout << "Yes" << endl;
  }else{
    cout << "No" << endl;
  }
  
  
    
    
  
  
   

  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<string>
#include<algorithm>
#include<utility>
#include<numeric>
#include<vector>
#include<map>
#include<unordered_map>
#include<set>
#include<tuple>
#include<stack>
#include<queue>
#include<functional>
#include<iterator>
#include<cmath>
#include<cctype>

using namespace std;

typedef long long ll;
typedef pair<int,int> P;

const int INF = 1e9;
const ll LINF = 1e18;

struct edge{int to,cost;};

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

	int sx,sy,tx,ty;
	cin >> sx >> sy >> tx >> ty;

	int w=tx-sx,h=ty-sy;

	for(int i=0;i<w;i++) cout<<"R";
	for(int i=0;i<h;i++) cout<<"U";
	for(int i=0;i<w;i++) cout<<"L";
	for(int i=0;i<h;i++) cout<<"D";

	cout<<"D";
	for(int i=0;i<w+1;i++) cout<<"R";
	for(int i=0;i<h+1;i++) cout<<"U";
	cout<<"LU";
	for(int i=0;i<w+1;i++) cout<<"L";
	for(int i=0;i<h+1;i++) cout<<"D";
	cout <<"R\n";
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
template<class L, class R> ostream& operator<<(ostream &os, pair<L,R> P) {
    return os << "(" << P.first << "," << P.second << ")"; }
template<class T> ostream& operator<<(ostream &os, vector<T> V) {
    os << "[ "; for(auto v : V) os << v << " "; return os << "]"; }
template<class T> ostream& operator<<(ostream &os, set<T> S){
    os << "{ "; for(auto s:S) os<<s<<" "; return os<<"}"; }
template<class T> ostream& operator<<(ostream &os, multiset<T> S){
    os << "{ "; for(auto s:S) os<<s<<" "; return os<<"}"; }
template<class L, class R> ostream& operator<<(ostream &os, map<L,R> M) {
    os << "{ "; for(auto m:M) os<<"("<<m.F<<":"<<m.S<<") "; return os<<"}"; }
    #define db(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1) { cout << name << " : " << arg1 << '\n'; }
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args) {
    const char* comma = strchr(names + 1, ',');
    cout.write(names, comma - names) << " : " << arg1 << " |"; __f(comma + 1, args...); }
#define rng(x) x.begin(), x.end()
#define pb push_back
#define F first
#define S second
#define el '\n'
 
typedef long long ll;
typedef pair<int,int> pi;
typedef pair<ll,ll> pl;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef vector<bool> vb;
 
/*-----------------------------Code begins----------------------------------*/

void solve(){
    int n; cin>>n;
    int mx = 0;
    ll sm = 0;
    for (int i = 0; i < n; ++i){
        int h; cin>>h;
        mx = max(mx, h);
        sm += (mx - h);
    }
    cout<<sm<<el;
}
 
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int T=1, tc = 1;
    // cin>>T; 
    while(T--){
        solve();
    }
    return 0; 
}

Measured memory_bytes: 3612
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <iostream>
#include <map>
#include <string>
#include <utility>
#include <vector>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int, int>;

int main() {
  int h, w;
  while (1) {
    cin >> h >> w;
    if (h == 0 && w == 0) break;
    rep(i, h) {
      rep(j, w) cout << "#";
      cout << endl;
    }
    cout << endl;
  }
  return 0;
}


Measured memory_bytes: 3080
import java.util.*;
  
public class Main {
    public static void main( String args[] ) {
        Scanner scan = new Scanner( System.in );
         
        double a = scan.nextDouble();
        double b = scan.nextDouble();
        double C = scan.nextDouble();
         
        double sinC = Math.sin( Math.toRadians( C ) );
        double cosC = Math.cos( Math.toRadians( C ) );
         
         
        // S
        double S = a * b * sinC / 2;
         
        // L
        double L = a + b + Math.sqrt( a * a + b * b - 2 * a * b * cosC );
         
        // h
        double h = b * sinC;
         
        System.out.print(S + "\n" + L + "\n" + h + "\n");
         
    }
     
}

Measured memory_bytes: 18184
#include <iostream>
#include <algorithm>
#include <map>
#include <vector>
using namespace std;
int main() {
	char x, y; cin >> x >> y;
	if(x<y){
		cout << '<' << endl;
		return 0;
	}
	if(x==y){
		cout << '=' << endl;
	}
	if(x>y){
		cout << '>' << endl;
	}
	return 0;
}

Measured memory_bytes: 256
N = int(input())
time = tuple(map(int,input().split()))
M = int(input())
time_2 = list(time)

for i in range(M):
    p, x = list(map(int,input().split()))
    time_2[p-1] = x
    ans = sum(time_2)
    print(ans)
    time_2[p-1] = time[p-1]


Measured memory_bytes: 3060
def examA():
    N = DI()/dec(7)
    ans = N
    print(N)
    return

def examB():
    ans = 0
    print(ans)
    return

def examC():
    ans = 0
    print(ans)
    return

def examD():
    ans = 0
    print(ans)
    return

def examE():
    ans = 0
    print(ans)
    return

def examF():
    # xとyに分けるとなんか二部グラフが見えてくる
    # 違うんか。。
    def bfs(V,used,s=0):
        W = {}
        W[s] = 1
        que = deque([s])
        while(que):
            now = que.pop()
            used[now] = True
            ne = W[now]*(-1)
            for v in V[now]:
                if v not in W:
                    W[v] = ne
                    que.append(v)
                elif W[v]!=ne:
                    return False
        return W,used
    y_shift = 10**5 + 1
    N = I()
    V = defaultdict(set)
    for _ in range(N):
        x, y = LI()
        y += y_shift
        V[x].add(y)
        V[y].add(x)

    ans = 0
    used = defaultdict(lambda:False)
    for i in V.keys():
        if used[i]:
            continue
        W,used = bfs(V,used,i)
        x = 0
        for w in W.values():
            if w==1:
                x += 1
        y = len(W)-x
        #print(W,x,y)
        ans += x*y
    ans = max(0,ans-N)
    print(ans)
    return

from decimal import getcontext,Decimal as dec
import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def DI(): return dec(input())
def LDI(): return list(map(dec,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = dec("0.000000000001")
alphabet = [chr(ord('a') + i) for i in range(26)]
alphabet_convert = {chr(ord('a') + i): i for i in range(26)}

getcontext().prec = 28

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examF()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
"""

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

int main(){
    int n;
    cin>>n;
    int ans = 0;
    vector<bool>cnt(MX,true);
    vector<int>p(n);
    vector<int>b(MX);
    set<int>s;
    rep(i,n){
        cin>>p[i];
        b[p[i]]++;
        s.insert(p[i]);
    }
    for (int x:s){
            if(cnt[x]){
            for(int j=2*x;j<MX;j+=x) cnt[j]=false;
        }
    }
    for(int y:p){
        if(cnt[y]&&b[y]==1) ans++;
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 17424
#include "bits/stdc++.h"
 
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
#define int ll
typedef pair<int,int> pii;
#define fi first
#define se second
#define Sort(a) sort(a.begin(),a.end())
#define rep(i,n) for(int i = 0;i < (n) ; i++) 
#define REP(i,n) for(int i = 0;i < (n) ; i++) 
#define MP(a,b) make_pair(a,b)
#define pb(a) push_back(a)
#define INF LLONG_MAX/4
#define INTINF INT_MAX/2
#define all(x) (x).begin(),(x).end()
#define debug(x) cerr<<#x<<": "<<x<<endl
#define debug_vec(v) cerr<<#v<<":";rep(i,v.size())cerr<<" "<<v[i];cerr<<endl
template<class T> inline bool chmax(T &a, T b){if(a < b){a = b;return true;}return false;}
template<class T> inline bool chmin(T &a, T b){if(a > b){a = b;return true;}return false;}
/*----------------------------------------------------------------*/
// const int MOD = 998244353;
const int MOD = 1000000007;
int n;


/*----------------------------------------------------------------*/
signed main(){
	
	cin >> n;

	vll f(n+1,1);
	for(int i = 2;i <= n;i++){
		int x = i;
		while(1){
			f[x]++;
			x += i;
			if(x > n)break;
		}
	}
	int ans = 0;
	for(int i = 1;i <= n;i++)ans += i*f[i];
	cout << ans << endl;

	

	return 0;
}
/*----------------------------------------------------------------*/

// g++ -std=gnu++17 code1.cpp
// sudo pip3 install --upgrade online-judge-tools
// rm -r -f test;oj dl https://code-festival-2017-qualb.contest.atcoder.jp/tasks/code_festival_2017_qualb_b
// rm -r -f test;oj dl https://abc172.contest.atcoder.jp/tasks/abc172_d

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

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

typedef long long ll;
typedef pair<int, int> P;

#define MAX 1000000020
#define INF 1001001001

int main(int, char**)
{
  int n, k;
  cin >> n >> k;
  vector<int> a(n);
  rep(i,n) cin >> a[i];

  rep(i,n-k) {
    if (a[i] < a[k+i]) cout << "Yes" << endl;
    else cout << "No" << endl;
  }

  return 0;
}


Measured memory_bytes: 4048
#include<iostream>
#include<string>
#include<vector>

using namespace std;

int main()
{
	int a, b;
	cin >> a >> b;
	if (a != 1 && a < b)cout << "Bob" << endl;
	if (b != 1 && a > b)cout << "Alice" << endl;
	if (a == b)cout << "Draw" << endl;
	if (a == 1 && b != 1)cout << "Alice" << endl;
	if (a != 1 && b == 1)cout << "Bob" << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define int long long int
#define endl "\n"
const int MOD=1e9+7;
#ifndef HOME
#define cerr if(0)cerr
#endif

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int r,d,x2;
    cin>>r>>d>>x2;
    vector<int>v(11);
    v[0]=x2;
    for(int i=1;i<11;i++){
        v[i]=(r*v[i-1])-d;
    }
    for(int i=1;i<11;i++){
        cout<<v[i]<<endl;
    }
    return 0;
    
}



Measured memory_bytes: 256
import sys

input = sys.stdin.readline


def main():
    N = int(input())
    X = [int(x) for x in input().split()]

    X_sorted = sorted(X)
    a = X_sorted[N // 2]
    b = X_sorted[(N // 2) - 1]
    for i in range(N):
        if X[i] >= a:
            print(b)
        else:
            print(a)



if __name__ == '__main__':
    main()


Measured memory_bytes: 25476
#include <algorithm>
#include <cmath>
#include <climits>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <fstream>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <cassert>
#include <functional>

using namespace std;

#define LOG(...) printf(__VA_ARGS__)
#define FOR(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
#define REP(i,n) for(int i=0;i<(int)(n);++i)
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(),(a).rend()
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())
#define RSORT(c) sort((c).rbegin(),(c).rend())
#define CLR(a) memset((a), 0 ,sizeof(a))
#define WRAP(y,x,h,w) (0<=y && y<h && 0<=x && x<w)

typedef long long ll;
typedef unsigned long long ull;
typedef string str;
typedef vector<bool> vb;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<double> vd;
typedef vector<vb> vvb;
typedef vector<vi> vvi;
typedef vector<vll> vvll;
typedef vector<vd> vvd;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

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


struct Node {
	int val;
	Node *l;
	Node *r;
};
const Node Ni= { 0,NULL,NULL };

void dfs(Node* a,string s) {
	int cnt = 0;
	*a = Ni;
	REP(i, s.length()) {
		if (s[i] == '(') {
			cnt++;
		}
		if (s[i] == ')') {
			cnt--;
		}
		if (s[i] == '['&&cnt == 0) {
			int llastidx = i-1;
			i++;
			while (isdigit(s[i])) {
				a->val *= 10;
				a->val += s[i] - '0';
				i++;
			}
			string s2;
			s2 = s.substr(1, llastidx - 1);
			if (s2!=""){
				a->l = (Node*)malloc(sizeof(Node));
				dfs(a->l, s.substr(1, llastidx - 1));
			}
			s2 = s.substr(i + 2, s.length() - (i + 2) - 1);
			if (s2 != "") {
				a->r = (Node*)malloc(sizeof(Node));
				dfs(a->r, s.substr(i + 2, s.length() - (i + 2) - 1));
			}
			break;
		}
	}
	return;
}
string add(Node *a, Node *b) {
	string ret = "";
	int val = a->val + b->val;
	ret += "(";
	if ((a->l != NULL)&&(b->l != NULL))
		ret += add(a->l, b->l);
	ret += ")[" + to_string(val) + "](";
	if ((a->r != NULL)&&(b->r != NULL))
		ret += add(a->r, b->r);
	ret += ")";
	return ret;
}
void nd(Node* a) {
	if (a->l != NULL)
		nd(a->l);
	if (a->r != NULL)
		nd(a->r);
	free(a);
}
int main() {
	string s1, s2;
	cin >> s1 >> s2;
	Node *a;
	a = (Node*)malloc(sizeof(Node));
	dfs(a,s1);
	Node *b; 
	b = (Node*)malloc(sizeof(Node));
	dfs(b,s2);
	cout << add(a, b) << endl;
	nd(a);
	nd(b);
	return 0;
}

Measured memory_bytes: 3424
n = int(input())
x = list(map(int, input().split()))
s = min(x)
e = max(x)

f_inf = float("inf")
ans = f_inf
for j in range(s, e + 1):
    res = 0
    for i in range(n):
        res += (x[i] - j) ** 2

    ans = min(ans, res)

print(ans)

Measured memory_bytes: 38640
#include<stdio.h>

int main(){
  int i,n,m,c,j;
  int a[5002];
  
  for(;;){
    scanf("%d",&n);
    if(n==0){
      break;
    }
    for(i=0;i<n;i++){
      scanf("%d",&a[i]);
    }
    m=-100001;
    for(i=0;i<n;i++){
      c=0;
      for(j=i;j<n;j++){
	c=c+a[j];
	if(c>m){
	  m=c;
	}
      }
    }
    printf("%d\n",m);
  }
  return 0;
}

Measured memory_bytes: 0
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <math.h>
#include <stdlib.h>
#include <string.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> P;
typedef priority_queue<int, vector<int>, greater<int> > minpq;

int main() {
    while (true) {
        int b; cin >> b;
        if (b == 0) break;
        b *= 2;
        int start = (int)sqrt(b);
        for(int i=start;i>0;i--){
            if(b%i==0){
                int c = b/i;
                if(i%2 != c%2){
                    if(i == 1){
                        cout << b/2 << " "<<1<<endl;
                        break;
                    }
                    cout << (c-i+1)/2 << " "<<i << endl;
                    break;
                }
            }
        }
    }
    return 0;
}



Measured memory_bytes: 3084
n, y = map(int, input().split())
for i in range(n+1):
    for j in range(n+1-i):
        if 10000*i + 5000*j + 1000*(n-i-j) == y:
            print(i, j, n-i-j)
            break
    else:
        continue
    break
else:
    print("-1 -1 -1")

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

int main(){
  int a, b;
  cin>> a >> b;
    
  if ( a < b ) cout << "a < b" << endl;
  else if ( a > b ) cout << "a > b" << endl;
  else cout << "a == b" << endl;
    
     return 0;
}

Measured memory_bytes: 1156
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<(n); i++)
#define int long long
#define double long double
#define mod 1000000007
#define F first
#define S second
#define P pair<long long,long long>
#define all(a) a.begin(),a.end()
#define INF 10000000000000000
#define endl '\n'
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; }
using namespace std;

int N,K;
int grid[2005][2005];

signed main(void){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin>>N>>K;
    rep(i,N){
        int x,y; char c;
        cin>>x>>y>>c;
        if(c=='W')y+=K;
        x%=2*K; y%=2*K;
        grid[x+1][y+1]++;
    }
    rep(i,2*K)rep(j,2*K)grid[i+1][j+1]+=grid[i][j+1]+grid[i+1][j]-grid[i][j];
    // rep(i,2*K+1){
    //     rep(j,2*K+1)cout<<grid[i][j];
    //     cout<<endl;
    // }
    int ans=-1;
    rep(i,K+1)rep(j,K+1){
        int a=grid[i][j];
        int b=grid[i+K][j+K]-grid[i+K][j]-grid[i][j+K]+grid[i][j];
        int c=grid[2*K][j]-grid[i+K][j];
        int d=grid[i][2*K]-grid[i][j+K];
        int e=grid[2*K][2*K]-grid[2*K][j+K]-grid[i+K][2*K]+grid[i+K][j+K];
        chmax(ans,a+b+c+d+e);
        chmax(ans,N-a-b-c-d-e);
    }
    cout<<ans<<endl;
    return 0;
}

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

int main(){
    int n,m;
    cin >> n >> m;
    vector<pair<int,int>> data(m);
    rep(i,m){
        cin >> data[i].second >> data[i].first;
    }
    sort(data.begin(),data.end());
    int ans=0;
    int now=0;
    rep(i,m){
        if(now>data[i].second) continue;
        ans++;
        now=data[i].first;
    }
    cout << ans << endl;
}






/*

うーん。。。
int main(){
    int n,m;
    cin >> n >> m;
    vector<pair<double,double>> island(n);
    rep(i,n) island[i].first=n+2, island[i].second=-4;
    rep(i,m){
        double a,b;
        cin >> a >> b;
        a--; b--;
        island[a].first=min(island[a].first,b);
        island[b].second=max(island[b].second,a);
    }
    rep(i,n){
        if(island[i].first==n+2) island[i].first=i;
        else island[i].first-=0.1;
        if(island[i].second==-4) island[i].second=i;
        else island[i].second+=0.1;
    }
    sort(island.begin(),island.end());
    
    rep(i,n){
        cout << "i " << i+1 << endl;
        cout << " " << island[i].first+1 << " " << island[i].second+1 << endl;
    }
    
    sort(island.begin(),island.end());
    double now=-1;
    double ans=0;
    rep(i,n){
        if(now>=island[i].second) continue;
        ans++;
        now=i;
        cout << "now   " << now+1 << endl;
    }
    cout << ans << endl;
}

*/

Measured memory_bytes: 4064
#include<stdio.h>
#define MAX 100001
typedef unsigned long long llong;
int datanum,k;
llong T[MAX];
int check(llong P){
  int i=0,j=0;
  for(j=0;j<k;j++){
    llong s = 0;
    while(s + T[i] <= P){
      s += T[i];
      i++;
      if(i == datanum)return datanum;
    }
  }
  return i;
}

int solve(){
  llong left = 0;
  llong right = 100000 * 10000;
  llong mid;
  while(right - left > 1){
    mid = (left + right)/2;
    int v = check(mid);
    if(v >= datanum)right = mid;
    else left = mid;
  }
  return right;
}

void print(llong i){
  printf("%lld\n",i);
}

int main(){
  llong ans;
  int i;
  scanf("%d %d",&datanum,&k);
  for(i=0;i<datanum;i++)scanf("%lld",&T[i]);
  ans = solve();
  print(ans);
  return 0;
}



Measured memory_bytes: 2576
n, m, l = map(int, raw_input().split())

A = [map(int, raw_input().split()) for i in range(n)]
B = [map(int, raw_input().split()) for i in range(m)]

C = [[sum(A[i][k]*B[k][j] for k in range(m)) for j in range(l)] for i in range(n)]

for row in C:
    print " ".join(map(str, row))

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

int main()
{
    int N;
    cin >> N;
    vector<char> S(N);
    long long  count_r = 0;
    long long  count_g = 0;
    long long  count_b = 0;

    for (int i = 0; i < N; i++)
    {
        cin >> S.at(i);
        if(S.at(i) == 'R') {count_r++;}
        if(S.at(i) == 'G') {count_g++;}
        if(S.at(i) == 'B') {count_b++;}
    }

    long long sum = count_r * count_g * count_b;

    
    for (int i = 0; i < N; i++)
    {
        for (int j = i + 1; j + (j - i) < N; j++)
        {
            //jはiの一つ隣から探索
            int k = j + (j - i); //j+(j-i) = i+1+(i+1-i) = i+2 kはiの二つ隣から探索
            if(S.at(i) != S.at(j) && S.at(j) != S.at(k) && S.at(k) != S.at(i))
            {
                sum--;
            }
        }
        
    }

    cout << sum << endl;
}

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

int main() {
  string S, T, U;
  cin >> S >> T;
  int A, B;
  cin >> A >> B >> U;

  if (U == S) {
    cout << A - 1 << " " << B << endl;
  } else {
    cout << A << " " << B - 1 << endl;
  }

  return 0;
}

Measured memory_bytes: 256
N = int(input())
L = [[float('inf')]*N for i in range(N)]


def dijkstra(s):
    S = set()
    d = [float('inf')] * N
    d[s] = 0
    p = [None]*N

    while len(S) != N:
        minv = float('inf')
        u = None
        for i in range(N):
            if d[i] < minv and i not in S:
                u = i
                minv = d[i]
        S.add(u)
        for u in S:
            for v in range(N):
                if d[u] + L[u][v] < d[v] and v not in S:
                    d[v] = d[u] + L[u][v]
                    p[v] = u

    for i in range(N):
        print('{} {}'.format(i, d[i]))
        # print(S)


for i in range(N):
    Q = list(map(int, input().split()))
    for j in range(Q[1]):
        L[Q[0]][Q[2+2*j]] = Q[3+2*j]
dijkstra(0)



Measured memory_bytes: 5828
#include <iostream>

int main(int argc, const char * argv[]) {
    char basicstr[80];
     int sum = 0;
    
    while(scanf("%s",basicstr) != EOF){
        int x  = 0;
        for(int i = 0;basicstr[i];i++){
            if(isdigit(basicstr[i])){
                x = x * 10 + (basicstr[i] - '0');
            }else{
                sum += x;
                x = 0;
            }
        }
        sum += x;
    }
    
    printf("%d\n",sum);
    return (0);
}

Measured memory_bytes: 3072
import java.util.*;

class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int k = sc.nextInt();
        if(k % 2 == 0){
            System.out.println(k/2*k/2);
        }else{
            System.out.println(k/2*(k+1)/2);
        }
        
    }
}

Measured memory_bytes: 21844
#include <bits/stdc++.h>
using namespace std;
#define M 100010
#define LL long long
#define rep(i, x, y) for(int i = (x); i <= (y); ++ i)
inline int read() {
	char ch = getchar(); int x = 0, f = 1;
	while(ch < '0' || ch > '9') {
		if(ch == '-') f = -1;
		ch = getchar();
	}
	while('0' <= ch && ch <= '9') {
		x = x * 10 + ch - '0';
		ch = getchar();
	}
	return x * f;
}
int n, m;
inline int calc(int x) {
	int o = (n + 1) / x;
	int ret = o * (x - m);
	int ex = n + 1 - o * x;
	ret += max(ex - m, 0);
	if(m == 0) ret --;
	return ret;
}
int main() {
	//freopen("in.txt", "r", stdin);
	n = read(), m = read();
	LL res = 0;
	rep(i, m + 1, n) {
		res += calc(i);
	}
	cout << res;
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define all(v) (v).begin(), (v).end()
#define lp(i, n) for (int i = 0; i < (n) ; ++i)
#define lpp(i, n) for (int i = 1; i <= (n) ; ++i)
#define sz(v) (int)(v).size()
#define int long long
#define mod 100000007

string x ;


int32_t main() {
    int n, k;
    cin >> n >> k ;
    int arr[n];
    lp(i,n)cin>>arr[i];
    int dp[n];
    dp[0]=0;
    for (int j = 0; j < n; ++j) {
        dp[j+1]=1000000000l;
        for (int i = 1; i <= k && (j-i)>=0; ++i) {
            dp[j]=min(dp[j],dp[j-i]+abs(arr[j]-arr[j-i]));
        }
    }
    cout << dp[n-1];
}


Measured memory_bytes: 1792
#include<stdio.h>
#include<string.h>

typedef struct{
    char name[10];
    int time;
} Data;

int main(){

  int i, n, q, cnt = 0, now = 0, tail, cumulative_cnt = 0;
  Data data[100000];
  
  scanf("%d%d",&n,&q);

  tail = n;

  for(i = 0; i < n; i++)scanf("%s%d",data[i].name,&data[i].time);

  while(1)
    {
      
      if(data[now].time < q)
	{
	  cumulative_cnt += data[now].time;
	  data[now].time = 0;
	}
      
      else
	{
	  cumulative_cnt += q;
	  data[now].time -= q;
	}
      
      if(data[now].time == 0)
	{
	  printf("%s %d\n",data[now].name, cumulative_cnt);

	  if(now == tail - 1)break;

	  now++;
	  
	  continue;
	}

      data[tail].time = data[now].time, strcpy(data[tail].name,data[now].name);

      now++, tail++;

      if(tail == 100000)tail = 0;
      if(now == 100000)now = 0;
      
    }

  return 0;
}
































/*
#include<stdio.h>
#include<string.h>

typedef struct{
    char name[10];
    int time;
} Data;

int main(){

  int i, n, q, cnt = 0, now = 0, cumulative_cnt = 0;
  Data data[100000];
  
  scanf("%d%d",&n,&q);

  for(i = 0; i < n; i++)scanf("%s%d",data[i].name,&data[i].time);

  while(1)
    {
      if(now == n - cnt)now = 0;
      if(cnt == n)break;
      if(data[now].time <= q && data[now].time > 0)
	{
	  cumulative_cnt += data[now].time;
	  printf("%s %d\n",data[now].name,cumulative_cnt);

	  cnt++;
	  
	  for(i = now; i < n - cnt; i++)
	    {
	      strcpy(data[i].name,data[i + 1].name);
	      data[i].time = data[i + 1].time; 
	    }
	  continue;
	}
      data[now].time -= q;
      cumulative_cnt += q;
      now++;
    }

  return 0;
}
*/



Measured memory_bytes: 3360
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <limits>
#include <cassert>
#include <random>
#include <stack>
#include <ctime>
#define REP(i,n) for(long (i)=0;(i)<(n);(i)++)
#define REPI(i,a,b) for(long (i)=(a);(i)<(b);(i)++)
#define INF numeric_limits<double>::infinity()
constexpr long MOD = 1e9 + 7;
using namespace std;
using P = pair<long, long>;
using VI = vector<long>;

int hoge[26];

int main() {
    string s;
    cin >> s;
    REP(i,s.size()) {
        hoge[s[i] - 'a']++;
    }
    REP(i,26) {
        if (!hoge[i]) {
            cout << char('a' + i) << endl;
            return 0;
        }
    }
    cout << "None" << endl;
}


Measured memory_bytes: 512
X, K, D = map(int, input().split())
if X <= 0:
    X *= -1

if X//D >= K:
    print(X - D*K)
else:
    if (K - X//D)%2 == 0:
        print(X - D*(X//D))
    else:
        print(abs(X-D*((X//D)+1)))


Measured memory_bytes: 9172
n,x,*a=map(int,open(0).read().split())
ans=sum(a)
for i in range(n-1):
    tyouka=a[i]+a[i+1]-x
    if tyouka>0:
        if tyouka<=a[i+1]:
            a[i+1]=a[i+1]-tyouka
        else:
            a[i]=a[i]+a[i+1]-tyouka
            a[i+1]=0
print(ans-sum(a))

Measured memory_bytes: 14092
#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int,int> P;
typedef pair<int,P> PP;
int A,B,C,n;
set<PP> erased;

bool isTouchSpace(int x,int y,int z){
  if(x<0 || y<0 || z<0 || x>=A || y>=B || z>=C) return 1;
  return erased.count(PP(x,P(y,z)));
}

bool isTouchCube(int x,int y,int z){
  if(x<0 || y<0 || z<0 || x>=A || y>=B || z>=C) return 0;
  return !erased.count(PP(x,P(y,z)));
}


signed main(){
  cin>>A>>B>>C>>n;
  int ans = 2*(A*B + B*C + C*A);

  int dx[] = {1,-1,0,0,0,0};
  int dy[] = {0,0,1,-1,0,0};
  int dz[] = {0,0,0,0,1,-1};
  
  while(n--){
    int x,y,z;
    cin>>x>>y>>z;
    for(int i=0;i<6;i++){
      int nx = x+dx[i],ny = y+dy[i],nz = z+dz[i];
      ans -= isTouchSpace(nx,ny,nz);
      ans += isTouchCube(nx,ny,nz);
    }
    erased.insert(PP(x,P(y,z)));
  }
  
  cout<<ans<<endl;
  return 0;
}

Measured memory_bytes: 3132
let n = read_int ()

let rec read_ints accu = function
  | 0 -> List.rev accu
  | k -> read_ints ((Scanf.scanf " %d" (fun x -> x)) :: accu) (k-1)

let a = Array.of_list (read_ints [] (2*n-1))

let check x =
  let rec find next p i =
    if p i && (a.(next i) >= x) != (a.(i) >= x) then find next p (next i)
    else i
  in
  let i = find (fun x -> x-1) (fun x -> x > 0) (n-1) in
  let j = find (fun x -> x+1) (fun x -> x < 2*n-2) (n-1) in
  if n-1-i < j-n+1 then a.(i)>=x else a.(j)>=x

let rec bsearch l r = if r = l+1 then l else let m = (l+r)/2 in if check m then bsearch m r else bsearch l m

let () = print_int (bsearch 1 (2*n))

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

#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++)
#define FORR(i, a, b) for (long long i = (a); i >= (b); i--)
#define REPR(i, N) for (long long i = n; i >= 0; i--)
#define SORT(v, n) sort(v, v + n);
#define VSORT(v) sort(v.begin(), v.end());
#define ALL(s) (s).begin(), (s).end()
#define pb(a) push_back(a)

#define fi first
#define se second

#define PI acos(-1.0)
#define INF 1000000007
#define EPS 1e-10
#define MAX_M 100100

typedef long long ll;
typedef pair<ll, ll> P;
typedef pair<double, double> PD;
typedef pair<string, ll> PS;
typedef vector<ll> V;
typedef pair<P, char> PC;

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

int main()
{
    ll N;
    string s;
    cin >> N;
    cin >> s;
    string ans;
    string init_pattern[4] = {"SS", "SW", "WS", "WW"};
    for(string p: init_pattern){
        ans = "";
        ans += p;
        FOR(i,2,N+2){
            if(s[(i-1)%N] == 'o'){
                if(ans[i-1] == 'S'){
                    ans += ans[i-2];   
                }else{
                    ans += (ans[i-2] == 'S') ? 'W' : 'S';
                }
            }else {
                if(ans[i-1] == 'S'){
                    ans += (ans[i-2] == 'S') ? 'W' : 'S';
                }else{
                    ans += ans[i-2]; 
                }
            }
        }
        if (ans[0] == ans[N] && ans[1] == ans[N+1]){
            break;
        }
        ans = "-1";
    }
    cout << ans.substr(0,N) << endl;
}


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

using ll = long long;

int a,b;
// const int C = ~(1<<31);
const int C = (1<<30) + ((1<<30) - 1);
const int M = (1<<16)-1;
int r() {
	a = 36969 * (a & M) + (a >> 16);
	b = 18000 * (b & M) + (b >> 16);
	return (C & ((a << 16) + b)) % 1000000;
}

using pii = pair<int,int>;

pair<int,pii> points[325252];

int main(){
	while(true){
		int n,m;
		scanf("%d%d%d%d",&n,&m,&a,&b);
		if(n+m+a+b==0)break;
		REP(i,n){
			int x,y,z;
			scanf("%d%d%d",&x,&y,&z);
			x++; y++; z++;
			points[i] = make_pair(x,pii(y,z));
		}
		REP(i,m){
			int x = r();
			int y = r();
			int z = r();
			x++; y++; z++;
			points[i+n] = make_pair(x,pii(y,z));
		}
		n += m;
		sort(points, points+n, [&](pair<int,pii> a, pair<int,pii> b){
			if(a.first != b.first)return a.first < b.first;
			return a.second > b.second;
		});
		const int N = 1000025;
		std::unordered_map<int,std::map<int,int>> bit;
		auto add = [&](int y, int z, int v){
			for(; y<N; y+=y&-y){
				// add to y
				if(bit.count(y)==0){
					bit[y] = std::map<int,int>();
					bit[y][-1] = -252521;
				}
				std::map<int,int> &mp = bit[y];
				auto it = mp.upper_bound(z); it--;
				if(it->second >= v)continue;
				mp[z] = v;
				it = mp.upper_bound(z);
				while(it != mp.end() && it->second <= v){
					mp.erase(it++);
				}
			}
		};
		auto query = [&](int y, int z){
			int ans = 0;
			for(; y>0; y-=y&-y){
				// get from y
				if(bit.count(y)==0)continue;
				std::map<int,int> &mp = bit[y];
				auto it = mp.upper_bound(z); it--;
				ans = max(ans, it->second);
			}
			return ans;
		};
		int ans = 0;
		REP(i,n){
			int x = points[i].first;
			int y = points[i].second.first;
			int z = points[i].second.second;
			int v = query(y-1, z-1) + 1;
			ans = max(ans, v);
			add(y,z,v);
		}
		printf("%d\n",ans);
	}
	return 0;
}



Measured memory_bytes: 110408
#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <iomanip>
#include <cassert>
#include <random>
#include <tuple>
#include <cstdint>

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

using namespace std;
typedef long long ll;

const int INF = INT32_MAX;
const int MOD = 1e9 + 7;

vector<vector<int>> g;
vector<int> memo;

void dfs(int v) {
    memo[v] = 1;
    for (auto nv: g[v]) {
        if (memo[nv]) continue;
        dfs(nv);
    }
}

int main() {
    int n, m; cin >> n >> m;
    g.resize(n);
    rep(i, m) {
        int x, y, z; cin >> x >> y >> z;
        x--; y--;
        g[x].push_back(y);
        g[y].push_back(x);
    }

    memo.assign(n, 0);
    int ans = 0;
    rep(i, n) {
        if (memo[i]) continue;
        ans++;
        dfs(i);
    }

    cout << ans << endl;


    return 0;
}

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

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define REP(i, s, e) for (int i = (int)(s); i < (int)(e); i++)
#define _rep(i, n) for (int i = (int)(n - 1); i >= 0; i--)
#define _REP(i, e, s) for (int i = (int)(e - 1); i >= (int)(s); i--)

#define yes cout << "yes" << endl;
#define Yes cout << "Yes" << endl;
#define YES cout << "YES" << endl;

#define no cout << "no" << endl;
#define No cout << "No" << endl;
#define NO cout << "NO" << endl;

#define AC cout << "AC" << endl;
#define WA cout << "WA" << endl;

#define out(s) cout << s << endl;

#define ll long long
#define ull unsigned long long

const unsigned int BIT_FLAG_0 = (1 << 0);  // 0000 0000 0000 0001
const unsigned int BIT_FLAG_1 = (1 << 1);  // 0000 0000 0000 0010
const unsigned int BIT_FLAG_2 = (1 << 2);  // 0000 0000 0000 0100
const unsigned int BIT_FLAG_3 = (1 << 3);  // 0000 0000 0000 1000
const unsigned int BIT_FLAG_4 = (1 << 4);  // 0000 0000 0001 0000
const unsigned int BIT_FLAG_5 = (1 << 5);  // 0000 0000 0010 0000
const unsigned int BIT_FLAG_6 = (1 << 6);  // 0000 0000 0100 0000
const unsigned int BIT_FLAG_7 = (1 << 7);  // 0000 0000 1000 0000

const double PI = 3.14159265358979323846;

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

#define H_MAX 500
#define W_MAX 500
#define INF 1e9 + 7

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

    if (x) {
        cout << 0 << endl;
    } else {
        cout << 1 << endl;
    }
}


Measured memory_bytes: 3632
N, A, B = map(int, input().split())
 
if N < A:
  print(N)
 
elif A <= N <= A + B:
  print(A)
  
else:
  count = N // (A+B)
  amari = N % (A + B)
  if amari < A:
    print(A*count + amari)
  else:
    print(A*count + A)

Measured memory_bytes: 3060
n, m, c = [int(elem) for elem in input().split()]
b = [int(elem) for elem in input().split()]

a_lst = []
cnt = 0
for i in range(0, n):
    a = [int(elem) for elem in input().split()]
    res = 0
    for a_i, b_i in zip(a, b):
        res += a_i * b_i
    res += c
    if res > 0:
        cnt += 1
print(cnt)
        


Measured memory_bytes: 3060
a,b,c = map(int,input().split())

if a <= b <= c:
    print(a ,b ,c)
elif b <= a <= c:
    print(b ,a ,c)
    
elif b <= c <= a:
    print(b ,c ,a)
elif c <= b <= a:
    print(c ,b, a)

elif a <= c <= b:
    print(a, c, b)
else:# c < a < b:
    print(c, a, b)
    


Measured memory_bytes: 5596