akhauriyash/Code-Regression huggingface dataset:
#include <cstdio>
#include <algorithm>

using namespace std;

const int MAXN=2e5+10;

typedef long long int ll;

ll A[MAXN],B[MAXN];

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

    for(int i=1;i<=N;i++) scanf("%lld%lld",A+i,B+i);

    sort(A+1,A+N+1);
    sort(B+1,B+N+1);

    if (N%2){
        printf("%lld\n",B[(N+1)/2]-A[(N+1)/2]+1);
    }else{
        printf("%lld\n",B[N/2]+B[N/2+1]-A[N/2]-A[N/2+1]+1);
    }

    return 0;
}

Measured memory_bytes: 4852
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bits/stdc++.h>
const int INF = 1000000010;
using namespace std;

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n,k,q;
    int ans=INF;
    cin>>n>>k>>q;
    vector<int>a(n);
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    for(int i=0;i<n;i++){
        vector<int>v;
        int l=0,r=0;
        while(l<n){
                priority_queue<int,vector<int>,greater<int> >que;
            while(r<n&&a[i]<=a[r]){
                que.push(a[r]);
                r++;
            }
            while((int)que.size()>=k){
                v.push_back(que.top());
                que.pop();
            }
            r++;
            l=r;
        }
            if((int)v.size()<q) continue;
            sort(v.begin(),v.end());
            ans=min(ans,v[q-1]-v[0]);
    }
    cout<<ans<<endl;
    return 0;
}


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

using namespace std;

#define N 100005
#define LL long long

int n, a, b, c, i, flag;
char s[3], st[N][3], Sol[N];

int main (void)
{
	scanf("%d%d%d%d",&n,&a,&b,&c);
	if ((LL)a+b+c>=3) {
		flag=0;
		for (i=1; i<=n; i++) {
			scanf("%s",s);
			if (s[0]=='A'&&s[1]=='B') {
				if (a>b) a--,b++,Sol[i]='B';
				else a++,b--,Sol[i]='A';
				if (a<0||b<0) flag=1;
			}
			else if (s[0]=='A'&&s[1]=='C') {
				if (a>c) a--,c++,Sol[i]='C';
				else a++,c--,Sol[i]='A';
				if (a<0||c<0) flag=1;
			}
			else {
				if (b>c) b--,c++,Sol[i]='C';
				else b++,c--,Sol[i]='B';
				if (b<0||c<0) flag=1;
			}
		}
		if (flag) puts("No");
		else {
			puts("Yes");
			for (i=1; i<=n; i++) printf("%c\n",Sol[i]);
		}
	}
	else {
	//	assert(0);
	    flag=0;
		for (i=1; i<=n; i++) scanf("%s",st[i]);
		for (i=1; i<=n; i++) {
			if (st[i][0]=='A'&&st[i][1]=='B') {
				if (!a) a++,b--,Sol[i]='A';
				else if (!b) a--,b++,Sol[i]='B';
				else {
					if (st[i+1][0]=='A'&&st[i+1][1]=='C') a++,b--,Sol[i]='A';
					else if (st[i+1][0]=='B'&&st[i+1][1]=='C') b++,a--,Sol[i]='B';
					else a++,b--,Sol[i]='A';
				}
				if (a<0||b<0) flag=1;
			}
			else if (st[i][0]=='A'&&st[i][1]=='C') {
				if (!a) a++,c--,Sol[i]='A';
				else if (!c) a--,c++,Sol[i]='C';
				else {
					if (st[i+1][0]=='A'&&st[i+1][1]=='B') a++,c--,Sol[i]='A';
					else if (st[i+1][0]=='B'&&st[i+1][1]=='C') c++,a--,Sol[i]='C';
					else a++,c--,Sol[i]='A';
				}
				if (a<0||c<0) flag=1;
			}
			else {
				if (!b) b++,c--,Sol[i]='B';
				else if (!c) b--,c++,Sol[i]='C';
				else {
					if (st[i+1][0]=='A'&&st[i+1][1]=='C') c++,b--,Sol[i]='C';
					else if (st[i+1][0]=='A'&&st[i+1][1]=='B') b++,c--,Sol[i]='B';
					else b++,c--,Sol[i]='B';
				}
				if (b<0||c<0) flag=1;
			}
		}
		if (flag) puts("No");
		else {
			puts("Yes");
		    for (i=1; i<=n; i++) printf("%c\n",Sol[i]);
		}
	}
	return 0;
}

Measured memory_bytes: 4220
#!/usr/bin/env python3
#ABC44 C

import sys
import math
import bisect
from heapq import heappush, heappop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
mod = 10**9 + 7

n,a = map(int, input().split())
X = list(map(int,input().split()))
Y = list(map(lambda x:x-a, X))
d = defaultdict(int)
d[0] = 1
for y in Y:
    for k,v in list(d.items()):
        d[k+y] += v
print(d[0]-1)


Measured memory_bytes: 39408
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define pb push_back
#define mp make_pair
#define Would
#define you
#define please


int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	
	int A, B, C, D;
	cin >> A >> B >> C >> D;
	
	co(max(A*B, C*D));

	Would you please return 0;
}

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

#define ll long long int 
#define ld long double 
#define pb push_back
#define mk make_pair
#define ii pair<int,int>

using namespace std;
double pi=2*acos(0.0);
ll M=1e18;

/*freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);*/

template<typename T> 
ostream& operator<<(ostream &os, const vector<T> &v) { 
    os << '{'; 
    for (const auto &x : v) os << " " << x;
        return os << '}'; 
}

void solve(){
    ll n,m,k; 
    cin>>n>>m>>k;

    vector<ll>a,b;  ll in;
    a.pb(0);b.pb(0);
    for (ll i=1;i<=n;i++){
        cin>>in; a.pb(in);
        a[i]+=a[i-1];
    } 
    for (ll i=1;i<=m;i++){
        cin>>in; b.pb(in);
        b[i]+=b[i-1];
    } 
    b.pb(M);

    ll kk,ix,nb; ll ans=0;
    for (ll i=0;i<=n;i++){
        kk=k-a[i];
        if (kk<0) break;
        ix=lower_bound(b.begin(),b.end(),kk)-b.begin();
        if (b[ix]>kk) ix--;
        nb=i+ix;
        ans=max(ans,nb);
    }    
    cout << ans << endl;
}

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

    int test_cases=1; 
    //cin>>test_cases;

    for (int tc=1;tc<=test_cases;tc++){
        
        solve();
        //cout << "Case " << tc << ": " << solve() <<endl;
        //printf("Case %d: %.10lf",tc,ans);
    }
    return 0;
}
/*
    problems are the sign of life
*/


Measured memory_bytes: 7936
#include <iostream>
#include <queue>

using namespace std;

int main(){

    int n,m;
    cin >> n >> m;
    char mat[n][m];
    queue<pair<int, pair<int,int>>> q;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            cin >> mat[i][j];
            if(mat[i][j] == '#'){
                q.push(make_pair(0,make_pair(i,j)));
            }
        }
    }
    int x[] = {0,0,1,-1};
    int y[] = {-1,1,0,0};
    int ans = 0;
    while(!q.empty()){
        pair<int,pair<int,int>> p = q.front();
        q.pop();
        ans = max(ans,p.first);
        for(int i = 0; i < 4; i++){
            int r = p.second.first + x[i];
            int s = p.second.second + y[i];
            if(r >= 0 && r < n && s >= 0 && s < m && mat[r][s] == '.'){
                mat[r][s] = '#';
                q.push(make_pair(p.first+1,make_pair(r,s)));
            }
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 13056
#include <math.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main(void) {
  int i, j, k;
  int N, M;
  int ii[100000 + 1] = {0};
  long cnt = 0;
  scanf("%d %d", &N, &M);
  int H[N];
  for (j = 0; j < N; j++) {
    scanf("%d", &H[j]);
  }
//   for (j = 0; j < N; j++) {
//     printf("%d ", H[j]);
//   }
//     printf("\n");
  for (j = 0; j < M; j++) {
    int a, b;
    scanf("%d %d", &a, &b);
    // printf("a%d b%d %d %d\n", a, b, H[a-1], H[b-1]);
    if (H[a-1] <= H[b-1]) {
      ii[a] = 1;
    }
    if (H[a-1] >= H[b-1]) {
      ii[b] = 1;
    }
    // for (i = 0; i <= N; i++) {
    //   printf("%d", ii[i]);
    // }
    // printf("\n");
  }
  for (j = 1; j <= N; j++) {
    if (ii[j] == 0) {
      cnt++;
    }
  }
    printf("%ld\n",cnt);
  return 0;
}


Measured memory_bytes: 2928
#include <bits/stdc++.h>
using namespace std;
int main() {
  int n;
  cin >> n;
  bool b = true;
  queue<int> num;
  for(int i = 0; i < n; i++) {
    int x;
    cin >> x;
    if(x%2==0) num.push(x);
  }
  while(num.empty() == false) {
    if(num.front()%3 != 0 && num.front()%5 != 0) {
      b = false;
      break;
    }
    else num.pop();
  }
  if(b) cout << "APPROVED";
  else cout << "DENIED";
}

Measured memory_bytes: 256
using System;

class Diverta_A{
  static void Main(){
    int[] Ar = Array.ConvertAll(Console.ReadLine().Split(' '), int.Parse);
    if (Ar[0] % Ar[1] == 0) Console.WriteLine("0");
    else Console.WriteLine(Ar[0] - Ar[1]);
  }
}

Measured memory_bytes: 11092
#include <bits/stdc++.h>
#define ll long long
#define FAST {ios_base::sync_with_stdio(false);cin.tie(NULL);}
#define f(i, a, b) for(ll i=a; i<b; i++)
#define fr(i,a,b) for(ll i=a;i>=b;i--)
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define pll pair<ll,ll>
#define LB lower_bound
#define UB upper_bound
#define endl "\n"
using namespace std;

ll M=1e9+7;
int main()
{
    FAST
    ll n,k;cin>>n>>k;
    ll a[n];f(i,0,n) cin>>a[i];
    sort(a,a+n);
    ll l=0,r=n-k;
    while(l<r && r+1<=n-1)
    {
        if(a[l]*a[l+1]>=a[r]*a[r+1]) l+=2,r+=2;
        else break;
    }
    ll ans=1;
    if(a[n-1]<0 && k&1LL) l=0,r=n-k;
    f(i,0,l) ans=(ans*a[i])%M;
    f(i,r,n) ans=(ans*a[i])%M;
    ans=(ans+M)%M;
    cout<<ans<<endl;
}


Measured memory_bytes: 5136
#include <bits/stdc++.h>
using namespace std;
int main() {
     int A,B;
     cin >> A >> B;
     if(A == B) cout << "Draw" << endl;
     else if(A == 1) cout << "Alice" << endl;
     else if(B == 1) cout << "Bob" << endl;
     else if(A > B) cout << "Alice" << endl;
     else cout << "Bob" << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define INF 1e9
#define llINF 1e18
#define MOD 1000000007
#define pb push_back
#define mp make_pair 
#define F first
#define S second
#define ll long long
#define vi vector<ll>
#define vvi vector<vi>
#define BITLE(n) (1LL<<((ll)n))
#define SHIFT_LEFT(n) (1LL<<((ll)n))
#define SUBS(s,f,t) ((s).substr((f),(t)-(f)))
#define ALL(a) (a).begin(),(a).end()
using namespace std;
//vi rui;
int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  ll n,p;cin>>n>>p;
  string s;
  cin>>s;
  vi rui(n+1);
  reverse(ALL(s));
  //cout<<s<<endl;
  if(p == 2){
    ll ans = 0;
    for(int i=0;i<n;i++)
      if((s[i]-'0')%2 == 0)
	ans += n-i;
    cout<<ans<<endl;
  }else if(p == 5){
    ll ans = 0;
    for(int i=0;i<n;i++){
      if(s[i] == '0' || s[i] == '5')
	ans += n-i;
    }
    cout<<ans<<endl;
  }else{
    ll kake = 1;
    for(int i=0;i<n;i++){
      rui[i+1] = rui[i]+(s[i]-'0')*kake;
      kake *= 10;
      kake %= p;
      rui[i+1] %= p;
      //   cout<<rui[i+1]<<endl;
    }
    ll now = -1;
 
    sort(ALL(rui));
    map<ll,ll>cnt;

    for(int i=0;i<=n;i++){
	cnt[rui[i]]++;
    }
    ll ans = 0;
    for(auto a:cnt){
      if(a.F != -llINF)
      ans += a.S*(a.S-1)/2;
      // break;
    }
    cout<<ans<<endl;
  }
  return 0;
}

Measured memory_bytes: 2580
from collections import defaultdict

N = int(input())
A = list(map(int, input().split()))
Q = int(input())
Counter = defaultdict(int)
for a in A:
    Counter[a] += 1
sum_val = sum(A)
ans = []
for _ in range(Q):
    B, C = map(int, input().split())
    sum_val += (C - B) * Counter[B]
    Counter[C] += Counter[B]
    Counter[B] = 0
    ans.append(sum_val)
print(*ans, sep='\n')

Measured memory_bytes: 27124
//hinagata.cpp
/*includes*/
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <stdio.h>
#include <numeric>
#include <iomanip>
#include <limits>
/*namespace*/
using namespace std;
using ll= long long;
/*define macro*/
#define REP(i,n) for(int i=0;i<(n);i++)
#define REPi(i,a,b) for(int i=(a);i<(b);i++)
#define REPRi(i,a,b) for(int i=(a);i>(b);i--)
#define ALL(x) (x).begin(),(x).end()

int main(){
    long long int L,R;
    cin>>L>>R;
    long long int counter1,counter2;
    long long int culc;
    int min=2019;
    if(L%2019+(R-L)>=2019||L%2019==0){
        cout<<0<<endl;
    }else{
        REPi(i,L,R){
            REPi(j,i+1,R+1){
                counter1=i;
                counter2=j;
                culc=counter1*counter2%2019;
                if(culc<min){
                    min=culc;
                }
            }
        }
        cout<<min<<endl;
    }
}

Measured memory_bytes: 256
#include<stdio.h>
int main(void)
{
  int W,H,x,y,r,flag=0;
  scanf("%d %d %d %d %d",&W,&H,&x,&y,&r);
  if(r<=x&&x<=(W-r))
  {
    if(r<=y&&y<=(H-r))
    {
      flag=1;
    }
  }
  if(flag==1)
    printf("Yes\n");
  else
    printf("No\n");
  return 0;
}



Measured memory_bytes: 2112
in = readline()
in = split(in)

a = similar(in, Int)

for i = 1:length(in)
    a[i] = parse(Int, in[i])
end

times = div(a[1], a[2])
if a[1] % a[2] != 0
    times += 1
end

println(times * a[3])


Measured memory_bytes: 157292
#include <iostream>
#include <vector>
#include <map>
using namespace std;

int main(){
    string S;
    cin >> S;
    int N = S.size();
    vector<int> X(N+1,0);
    for(int i=1;i<=N;i++){
        X[i] = X[i-1]^(1<<((S[i-1]-'a')));
    }
    map<int,int> memo;
    vector<int> dp(N+1,1e9);
    memo[0] = 0;
    dp[0] = 0;
    for(int i=1;i<=N;i++){
        int val = X[i];
        if(memo.count(val)){
            dp[i] = memo[val]+1;
        }
        for(int j=0;j<26;j++){
            int key = (1<<j);
            int pre = val^key;
            if(memo.count(pre)){
                dp[i] = min(dp[i],memo[pre]+1);
            }
        }
        if(!memo.count(val)) memo[val] = dp[i];
        else memo[val] = min(memo[val],dp[i]);
    }
    cout << dp[N] << endl;
}

Measured memory_bytes: 11396
#include<cstdio>
#include<iostream>
#include<algorithm>
#define N 200005
using namespace std;
int n;
long long ans,k,U,a[N],l,r,mid;
long long Judge(long long mid)
{
	int L,R,Mid;
	long long Nans=0,Zans=0;
	for (int i=1;i<=n;i++)
	{
		if (a[i]==0)
		{
			if (mid>0)
				Zans+=n-1;
			continue;
		}
		if (a[i]>0)
		{
			L=1;
			R=n;
			Nans=0;
			while (L<=R)
			{
				Mid=(L+R) >> 1;
				if (a[i]*a[Mid]<mid)
				{
					Nans=Mid;
					L=Mid+1;
				} else
					R=Mid-1;
			}
			//cout << Nans << endl;
			if (Nans>=i)
				Nans--;
			Zans+=Nans;
			//cout << Nans << endl;
		} else
		{
			L=1;
			R=n;
			Nans=n+1;
			while (L<=R)
			{
				Mid=(L+R) >> 1;
				if (a[i]*a[Mid]<mid)
				{
					Nans=Mid;
					R=Mid-1;
					//cout << "Right" << endl;
				} else
					L=Mid+1;
			}
			//cout << Nans << endl;
			if (Nans<=i)
				Nans++;
			Nans=n-Nans+1;
			//cout << Nans << endl;
			Zans+=Nans;
		}
	}
	return Zans/2;
}
int main()
{
	scanf("%d%lld",&n,&k);
	for (int i=1;i<=n;i++)
		scanf("%lld",&a[i]);
	sort(a+1,a+n+1);
	l=-1000000000000000000;
	r=1000000000000000000;
	/*for (int i=1;i<=n;i++)
		printf("%lld ",a[i]);
	putchar('\n');*/
	//printf("%lld %lld\n",l,r);
	//printf("%lld\n",Judge(-6));
	while (l<=r)
	{
		mid=(l+r) >> 1;
		U=Judge(mid);
		//printf("%lld %lld %lld\n",l,r,U);
		if (U<=k-1)
		{
			ans=mid;
			l=mid+1;
		} else
			r=mid-1;
	}
	printf("%lld\n",ans);
}

Measured memory_bytes: 5308
#![allow(unused, non_snake_case, dead_code, non_upper_case_globals)]
#![macro_use]

use std::cmp::*;
use std::collections::*;
use std::io::*;
use std::mem::*;
use std::num::*;
use std::slice::*;

fn main() {
    let (r, w, e) = (stdin(), stdout(), stderr());
    let mut io = IO::new(r.lock(), w.lock(), e.lock());
    // =============================================== //

    let (n, k): (usize, usize) = (io.read(), io.read());
    let a = io.readn::<i64>(n);

    let mut dp = vec![vec![0i64; 101010]; 105];
    let mut dp_sum = vec![vec![0i64; 101010]; 105];

    for j in 0..k + 1 {
        dp_sum[0][j] = 1;
    }

    let MOD = 1e9 as i64 + 7;
    for i in 1..n + 1 {
        for j in 0..k + 1 {
            dp[i][j] = dp_sum[i - 1][j];
            if j as i64 >= a[i - 1] + 1 {
                dp[i][j] -= dp_sum[i - 1][j - a[i - 1] as usize - 1];
            }
            if j >= 1 {
                dp_sum[i][j] = dp_sum[i][j - 1] + dp[i][j];
            } else {
                dp_sum[i][j] = dp[i][j];
            }
            dp[i][j] %= MOD;
            dp_sum[i][j] %= MOD;
        }
    }
    io.writeln((dp[n][k] + MOD) % MOD);
}

// IO
struct IO<R: Read, W: Write, E: Write> {
    Read: R,
    Write: BufWriter<W>,
    Error: BufWriter<E>,
}
impl<R: Read, W: Write, E: Write> IO<R, W, E> {
    fn new(r: R, w: W, e: E) -> IO<R, W, E> {
        IO {
            Read: r,
            Write: BufWriter::new(w),
            Error: BufWriter::new(e),
        }
    }
    fn read<T>(&mut self) -> T
    where
        T: std::str::FromStr,
    {
        let next: String = self
            .Read
            .by_ref()
            .bytes()
            .map(|c| c.unwrap() as char)
            .skip_while(|c| c.is_whitespace())
            .take_while(|c| !c.is_whitespace())
            .collect();
        next.parse().ok().unwrap()
    }
    fn chars(&mut self) -> Vec<char> {
        self.read::<String>().chars().collect()
    }
    fn readn<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
        (0..n).map(|_| self.read::<T>()).collect::<Vec<_>>()
        // a.append(&mut b)
    }
    fn readmat<T: std::str::FromStr>(&mut self, n: usize, m: usize) -> Vec<Vec<T>> {
        (0..n).map(|_| self.readn(m)).collect()
    }
    fn write<S: ToString>(&mut self, val: S) {
        self.Write.write(val.to_string().as_bytes());
    }
    fn writeln<S: ToString>(&mut self, val: S) {
        self.Write.write(val.to_string().as_bytes());
        self.Write.write(b"\n");
    }
    fn debug<S: std::fmt::Debug>(&mut self, val: S) {
        writeln!(self.Error, "(debug ) {:?}", &val);
    }
    fn debug2<S: std::fmt::Debug, T: std::fmt::Debug>(&mut self, val1: S, val2: T) {
        writeln!(self.Error, "(debug2) {:?} -> {:?}", val1, val2);
    }
}


Measured memory_bytes: 219388
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define Rep(i,a,n) for (int i=a;i<=n;i++)
#define Per(i,a,n) for (int i=n;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
typedef double db;
mt19937 mrand(random_device{}()); 
const ll mod=1000000007;
int rnd(int x) { return mrand() % x;}
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
// head

signed main(){
   int n;cin>>n;
   map<string,int> a;
   int mx=0;
   rep(i,0,n){
       string s;cin>>s;a[s]++;
        mx=max(mx,a[s]);
   }
   for(auto i=a.begin();i!=a.end();i++){
       if(i->second==mx){
           cout<<(i->first)<<endl;
       }
   }
    return 0;
}

Measured memory_bytes: 25216
#include <cstdio>
#include <string>
#include <iostream>
#include <cmath>
#include <vector>
#include <stack>
#include <algorithm>


using namespace std;
typedef long long LL;

int main(void) {
	int i = 0, N, tmp, min, max;

	cin >> N;

	cin >> tmp;
	i++;
	min = tmp;
	max = tmp;

	while (i < N) {
		cin >> tmp;
		if (min > tmp) {
			min = tmp;
		}
		else if(max < tmp){
			max = tmp;
		}
		i++;
	}
	
	cout << abs(min - max) << endl;


	return 0;
}


Measured memory_bytes: 256
// DSL_2_B.cpp
// Range Query - Range Sum Query
#include <iostream>
#include <stack>
#include <vector>
using namespace std;
const int INF = (1 << 31) - 1;
struct SegmentTreeNode {
    int val;
    int start, end;
    SegmentTreeNode *left, *right;
    SegmentTreeNode() {}
    SegmentTreeNode(int start, int end) :
            start(start), end(end), val(INF), left(NULL), right(NULL) {}
};

SegmentTreeNode* buildTree(int start, int end) {
    if (start > end) return NULL;
    SegmentTreeNode* head = new SegmentTreeNode(start, end);
    if (start < end) {
        int mid = start + (end - start) / 2;
        head->left = buildTree(start, mid);
        head->right = buildTree(mid + 1, end);
    }
    return head;
}

void update(SegmentTreeNode* node, int i, int x) {
    int lt, rt, mid;
    stack<SegmentTreeNode* > ms;
    while (node) {
        lt = node->start;
        rt = node->end;
        mid = lt + (rt - lt) / 2;
        ms.push(node);
        if (i <= mid) {
            node = node->left;
        }
        else {
            node = node->right;
        }
    }
    while (!ms.empty()) {
        node = ms.top();
        ms.pop();
        if (!node->left && !node->right) node->val = x;
        else node->val = min(node->left->val, node->right->val);
    }
}

int find(SegmentTreeNode* node, int s, int t) {
    if (!node) return INF;
    if (node->start == s && node->end == t)
        return node->val;
    int mid = (node->start + node->end) / 2;
    if (t <= mid) {
        return find(node->left, s, t);
    }
    else if (s > mid) {
        return find(node->right, s, t);
    }
    else {
        return min(find(node->left, s, mid), find(node->right, mid + 1, t));
    }
}

int main()
{
    int n, q;
    cin >> n >> q;
    SegmentTreeNode* st = buildTree(0, n-1);
    int com, x, y;
    while (q--) {
        cin >> com >> x >> y;
        if (com) {
            cout << find(st, x, y) << endl;
        }
        else {
            update(st, x, y);
        }
    }
    return 0;
}

Measured memory_bytes: 12476
#include<bits/stdc++.h>
using namespace std;
const int mod=998244353;
typedef long long ll;
ll ksm(ll x,ll k){ll re=1;for(;k;k>>=1,x=x*x%mod)if(k&1)re=re*x%mod;return re;}
int pls(int x,int y){return x+y>=mod?x+y-mod:x+y;}
int mns(int x,int y){return x-y<0?x-y+mod:x-y;}
const int N=310,K=45010;
int n,a[N],s;
int dp[2][K],cnt[2][K],ret;
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]),s+=a[i];
	s/=2;
	int nw=0;
	dp[0][0]=cnt[0][0]=1;
	for(int i=1;i<=n;i++)
	{
		nw^=1;
		for(int j=s;j>=a[i];j--) dp[nw][j]=pls(dp[nw^1][j],pls(dp[nw^1][j-a[i]],dp[nw^1][j-a[i]])),cnt[nw][j]=pls(cnt[nw^1][j],cnt[nw^1][j-a[i]]);
		for(int j=a[i]-1;~j;j--)dp[nw][j]=dp[nw^1][j],cnt[nw][j]=cnt[nw^1][j];
	}
	for(int i=1;i<=s;i++)ret=pls(ret,mns(dp[nw][i],pls(cnt[nw][i],cnt[nw][i])));
	ret=(ksm(3,n)-3*ksm(2,n)+3-(ll)ret*3)%mod;ret=(ret+mod)%mod;
	printf("%d\n",ret);
}


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

int main(){
  int l,r,d;
  cin >> l >> r >> d;
  int count = 0;
  
  for(int i = l;i < r + 1;i ++){
    if((i + d) % d == 0)count ++;
  }
  
  cout << count << endl;
}

Measured memory_bytes: 3616
#include <iostream>
#include <numeric>
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
struct fast_ios { fast_ios(){ cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(20); }; } fast_ios_;


int main(){
    // input
    lint N;
    cin >> N;
    vector<int> a(N);
    for( int n=0; n<N; n++ ){
        cin >> a[n];
    }

    // calc
    int p = 1; 
    int ans = 0;
    for( int n=0; n<N; n++ ){
        if(a[n] == p){
            p++;
        }else{
            ans++;
        }
    }
    if( ans==N ){
        ans = -1;
    }

    // out
    cout << ans << endl;
} 

Measured memory_bytes: 1024
//Simple Calculator
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

class Main {

	public static void main(String[] args) throws IOException {

		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

		String input;
		while (!(input = in.readLine()).equals("0 ? 0")) {
			String[] aOpb = input.split(" ");
			// String[] aOpb = "1 ? 2".split(" ");
			int a = Integer.parseInt(aOpb[0]);
			String op = aOpb[1];
			int b = Integer.parseInt(aOpb[2]);

			if (op.equals("?")) {
				break;
			}

			int ans = 0;

			if (op.equals("+")) {
				ans = a+b;
			} else if (op.equals("-")) {
				ans = a-b;
			} else if (op.equals("*")) {
				ans = a*b;
			} else if (op.equals("/")) {
				ans = a/b;
			}
			System.out.println(ans);
		}

	}
}

Measured memory_bytes: 17060
#include <iostream>
#include <cstdio>
#include <vector>

using namespace std;
#define uint unsigned int

int main(void){
    int n;
    cin >> n;
    while (n--) {
        vector<uint> d(8);
        for (int i = 0; i < 8; i++) cin >> hex >> d[i];
        uint t;
        cin >> hex >> t;
        
        uint bit = 0;
        for (int i = 0; i < 32; i++) {
            uint sum = 0;
            for (int j = 0; j < 8; j++) sum += d[j];
            
            uint a = 1<<i;
            if ((sum & a) == (t & a)) { // a==0
                for (int j = 0; j < 8; j++) ;
            }
            else { // a==1
                bit += a;
                for (int j = 0; j < 8; j++) {
                    if (d[j] & a) d[j] -= a;
                    else d[j] += a;
                }
            }
        }
        cout << hex << bit << endl;
    }
}

Measured memory_bytes: 3020
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//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; }

//long longのシフト演算には気をつけよう

int main(){
    int N, Q; cin >> N >> Q;
    string s; cin >> s;
    vector<int> l(Q), r(Q);
    for(int i=0; i<Q; i++){
        int L, R; cin >> L >> R;
        L--; R--;
        l[i] = L;
        r[i] = R;
    }

    int f[s.size()+5];
    for(int i=0; i<s.size(); i++) f[i] = 0;

    for(int i=1; i<s.size(); i++){
        if(s[i] == 'C' && s[i-1] == 'A') f[i] = f[i-1]+1;
        else f[i] = f[i-1];
    }

    for(int i=0; i<Q; i++){
        if(l[i] == 0) cout << f[r[i]] << endl;
        else if(s[l[i]] == 'C' && s[l[i]-1] == 'A'){
            cout << f[r[i]] - f[l[i]-1] -1 << endl;
        }
        else cout << f[r[i]] - f[l[i]-1] << endl;
    }
}

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

int main()
{
    long long x;
    scanf("%lld", &x);
    if ((x - 1) % 11 + 1 <= 6) printf("%lld\n", (x - 1) / 11 * 2 + 1);
    else printf("%lld\n", (x + 10) / 11 * 2);

    return 0; 
}

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

int main() {
  int N,M;
  cin >> N >> M;
  int sum = 0;
  
  vector<int>A(N);
  for (int i = 0; i < N; i++) {
    cin >> A.at(i);
    sum += A.at(i);
  }
  
  int count = 0;
  for (int i = 0; i < N; i++) {
    if ((sum + 4*M - 1) / (4*M) <= A.at(i) ){
      count++;
    }
  }
  if (count >= M){
    cout << "Yes" << endl;
  }
  else {
    cout << "No" << endl;
  }
}
      



Measured memory_bytes: 3608
program main
  implicit none
  integer :: N, i
  integer(8) :: out 
  read(*,*) N
  out = 0
  do i = 1,N
     if ( mod(i,3) == 0 .or. mod(i,5) == 0 ) then
        continue
     else
        out = out + i
     end if
  end do
  write(*,'(i0)') out
end program main

Measured memory_bytes: 2924
#include <stdio.h>

int main() {
  int x1, y1, x2, y2, x3, y3, x4, y4, dx, dy;
  scanf("%d %d %d %d", &x1, &y1, &x2, &y2);

  if (x1 < x2) {
    if (y1 < y2) {
      dx = x2 - x1;
      dy = y2 - y1;
      x3 = x2 - dy;
      y3 = y2 + dx;
      x4 = x1 - dy;
      y4 = y1 + dx;
    } else {
      dx = x2 - x1;
      dy = y1 - y2;
      x3 = x2 + dy;
      y3 = y2 + dx;
      x4 = x1 + dy;
      y4 = y1 + dx;
    }
  } else {
    if (y1 < y2) {
      dx = x1 - x2;
      dy = y2 - y1;
      x3 = x2 - dy;
      y3 = y2 - dx;
      x4 = x1 - dy;
      y4 = y1 - dx;
    } else {
      dx = x1 - x2;
      dy = y1 - y2;
      x3 = x2 + dy;
      y3 = y2 - dx;
      x4 = x1 + dy;
      y4 = y1 - dx;
    }
  }
  printf("%d %d %d %d\n", x3, y3, x4, y4);
  return 0;
}


Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pdd pair<ld,ld>
#define x first
#define y second
#define pb push_back
#define N 100000
#define LOGN 16
typedef long long ll;
typedef long double ld;
const ll mod = 1000000007;

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n;
    cin>>n;
    int count_total = 0, count = 0;
    int prev_h = 0, h;
    for(int i=0;i<n;i++){
        cin>>h;
        if(h==0){
            count_total += count;
            count = 0;
        }
        else{
            if(prev_h <= h)
                count += h-prev_h;
        }
        prev_h = h;
    }
    count_total += count;
    cout<<count_total;
    return 0;
}

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

int int_len(int n) {
  int s=0;
  while(n!=0) s++, n/=10;
  return s;
}

int int_sum(int n) {
  int m=0,s=0,a=n;
  while(a!=0) s++, a/=10;
  for(int i=s-1;i>=0;i--) m+=n/((int)pow(10,i))-(n/((int)pow(10,i+1)))*10;
  return m;
}

int vec_sum(vector<int> v){
  int n=0;
  for(int i=0;i<v.size();i++) n+=v[i];
  return n;
}

int main() {
  int n;
  cin>>n;
  vector<string> v(n);
  rep(i,n) cin>>v[i];
  for(int i=0;i<n;i++){
    for(int j=i+1;j<n;j++){
      if(v[i]==v[j]){
        cout<<"No"<<endl;
        return 0;
      }
    }
  }
  for(int i=0;i<n-1;i++){
    if(v[i][v[i].size()-1]!=v[i+1][0]){
      cout<<"No"<<endl;
      return 0;
    }
  }
  
  
  cout<<"Yes"<<endl;
  
  
  
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define sz 100002
#define pb push_back
#define ff first
#define ss second
#define ll long long
#define P push
#define VEC(n) ll int x; vector<ll int>v;for(int i=0;i<n;i++){cin>>x;v.pb(x);}
#define TEST() int test;cin>>test; while(test--)
#define FAST() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
using namespace std;
//https://codeforces.com/contest/1215/problem/A
//ll int LCM(ll int a,ll int b) { ll int gcd=__gcd(a,b);ll int lcm=a*b/gcd;return lcm;}
//ll int bigmod(ll int b, ll int p, ll int m){if(p==0)return 1;if(p%2!=0) return b%m*fun(b,p-1,m)%m;if(p%2==0){ ll int res=fun(b,p/2,m);return (res%m*res%m)%m;}}
//void seive() { prime[np++]=2;for(i=3; i<=sz; i+=2){if(mark[i]==0){ prime[np++]=i;for(j=i*i; j<=sz; j+=i) mark[j]=1; } }}
//string add(string s1,string s2) {string s;int j=s1.size()-1,c=0,m; for(int i=s2.size()-1; i>=0; i--) {if(j>=0)m=s2[i]-'0'+s1[j]-'0'+c;else m=s2[i]-'0'+c; if(m>9) { s+=m%10+'0';c=m/10; } else {  c=0;s+=m+'0'; }j--; } if(c!=0) {s+=c+'0'; }reverse(s.begin(),s.end());return s;}
//int pos;string mul(int n) {string s;for(int i=0; i<pos; i++) { s+="0"; }pos++;int c=0,m; for(int i=s1.size()-1; i>=0; i--) { m=(s1[i]-'0')*n+c;if(m>9) { s+=m%10+'0';c=m/10;} else { c=0; s+=m+'0';} }while(c!=0) { s+=c%10+'0';c=c/10;}    reverse(s.begin(),s.end());return s;}


int main()
{
    int a,b,c,cnt=0,x;
    cin>>a>>b>>c;
    x=c;

    for(int i=0;i<100;i++)
    {
        if(c>=a&&c<=b)
        {
            cnt++;

        } c+=x;
    }
    cout<<cnt<<endl;
}




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

#define pb         push_back

typedef long long ll;
const ll INF = 1000000000000000000ll;
const ll MOD = 1000000007ll;
const double EPS = 1e-8;

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

    ll n;
    cin >> n;

    map<ll, ll> ma;
    for(int i=0; i<n; i++){
        ll d;
        cin >> d;
        if(ma.find(d) == ma.end()){
            ma[d] = 1;
        }else{
            ma[d]++;
        }
    }

    ll m;
    cin >> m;
    bool f = true;
    for(int i=0; i<m; i++){
        ll t;
        cin >> t;
        if(ma.find(t) == ma.end()){
            f = false;
            break;
        }else{
            if(ma[t] == 0){
                f = false;
                break;
            }else{
                ma[t]--;
            }
        }
    }

    if(f){
        puts("YES");
    }else{
        puts("NO");
    }

    
    return 0;
}


Measured memory_bytes: 12800
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include <functional>
#include <utility>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstdio>
using namespace std;

int main(){
  int a, b, n;
  cin >> n >> a >> b;
  cout << min(a,b) << " "<< max(a+b-n,0)<< endl;

  return 0;
}


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

using namespace std;

void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif

#define lp(i, a, b) for (int i=a; i<(b); i++)
#define lpd(i,a,b) for (int i = (b)-1; i >= a; i--)
	
#define sz(x) (int)(x).size()
#define all(x) x.begin(), x.end()
#define mp make_pair
#define pb push_back

typedef long long ll;
typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef vector<int> vi;
typedef vector<ll> vl;

vector<int> parent;
vector<ll> size;

int find_set(int v){
    if (v == parent[v]) return v;
    return parent[v] = find_set(parent[v]);
}

void union_sets(int a, int b){
    a = find_set(a);
    b = find_set(b);
    if (a == b) return;
    if (size[a] < size[b])
        swap(a, b);
    size[a] += size[b];
    parent[b] = a;
}

int main() {
    //freopen("in.txt", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n, m;
    cin>>n>>m;
    
    parent.resize(n+1);
    lp(i, 0, n+1) parent[i] = i;
    size.assign(n+1, 1LL);

    vector<pi> v(m);
    vector<ll> ans;

    int a, b;
    lp(i, 0, m){
        cin>>a>>b;
        v[i] = mp(a, b);
    }

    ll res = (ll)n*(n-1)/2;

    lpd(i, 0, m){
        ans.pb(res);
        int x = find_set(v[i].first);
        int y = find_set(v[i].second);

        if (x != y){
            res -= (size[x]*size[y]);
            union_sets(x, y);
        }
    }

    lpd(i, 0, m) cout<<ans[i]<<endl;

    return 0;
}

Measured memory_bytes: 4212
#include <bits/stdc++.h>
  
using namespace std;
  
#define rep(i,n) REP(i,0,n)
#define REP(i,s,e) for(int i=(s); i<(int)(e); i++)
#define pb push_back
#define all(r) (r).begin(),(r).end()
#define rall(r) (r).rbegin(),(r).rend()
#define fi first
#define se second
  
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
const int INF = 1e9;
const ll LINF = 1e18;
const ll MOD = 1e9 + 7;
double EPS = 1e-8;

ll d[21][21][21][21];

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

bool isOutOfRange(int x, int y, int h, int w) {
	return x < 0 || x >= w || y <0 || y >=h;
}

ll dp[11][(1<<11)];

int main(){
	int w, h;
	while(cin >> w >> h && w && h) {
		vector<string> s(h);
		rep(i, h) cin >> s[i];
		rep(i, h) rep(j, w) rep(k, h) rep(l, w) d[i][j][k][l] = ((i == k && j == l)? 0LL : (ll)1e18);
		int _sx, _sy, n = 0;
		vi X, Y;
		rep(y, h) rep(x, w) {
			if(s[y][x] == '*') {
				n++;
				X.pb(x);
				Y.pb(y);
				//continue;
			}
			else if(s[y][x] == 'x') continue;
			else if(s[y][x] == 'o') _sx = x, _sy = y;
			rep(i, 4) {
				int nx = x + dx[i], ny = y + dy[i];
				if(isOutOfRange(nx, ny, h, w) || s[ny][nx] == 'x') continue;
				d[y][x][ny][nx] = 1LL;
			}
		}
		rep(ky, h) rep(kx, w) {
			rep(sy, h) rep(sx, w) {
				rep(gy, h) rep(gx, w) {
					d[sy][sx][gy][gx] = min(d[sy][sx][gy][gx], d[sy][sx][ky][kx] + d[ky][kx][gy][gx]);
				}
			}
		}
		rep(i, n) rep(j, (1<<n)) dp[i][j] = 1e18;
		rep(i, n) dp[i][(1<<i)] = d[_sy][_sx][Y[i]][X[i]];//, cout<<" i : "<<i<<" "<<d[_sy][_sx][Y[i]][X[i]];
		REP(mask, 1, (1<<n)) {
			rep(i, n) {
				if((mask & (1 << i)) == 0) continue;
				rep(j, n) {
					if((mask & (1 << j))) continue;
					int nxt = mask | (1 << j);
					dp[j][nxt] = min(dp[j][nxt], dp[i][mask] + d[Y[i]][X[i]][Y[j]][X[j]]);
				}
			}
		}
		ll ans = 1e18;
		int gl = (1<< n) -1;
		rep(i, n) {
			ans = min(ans, dp[i][gl]);
		}
		cout<<(ans==1e18?-1:ans)<<endl;
		// cout<<_sx<<" "<<_sy<<endl;
		// rep(i, n) cout << " "<<X[i]<<" "<<Y[i]<<" "<<d[_sy][_sx][Y[i]][X[i]]<<endl;
		// rep(sy, h) rep(sx, w) {
		// 	rep(gy, h) rep(gx, w) {
		// 		cout<<" ("<<sx<<", "<<sy<<") -> ("<<gx<<", "<<gy<<") "<<d[sy][sx][gy][gx]<<endl;
		// 	}
		// }
	}
}

Measured memory_bytes: 4624
#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)   FOR(i,0,n)
#define ALL(obj)   (obj).begin(),(obj).end()

#define debug(var)  do{std::cout << __LINE__ << "> " << #var << ": ";view(var);}while(0)
template<typename T> void view(T e){std::cout << e << std::endl;}
template<typename T> void view(const std::vector<T>& v){for(const auto& e : v){ std::cout << e << " "; } std::cout << std::endl;}
template<typename T> void view(const std::vector<std::vector<T> >& vv){ for(const auto& v : vv){ view(v); } }

using namespace std;
using ll = long long;
using vi = vector<int>;
using vl = vector<ll>;
using vvi = vector<vector<int>>;
using vvl = vector<vector<ll>>;

struct Dijkstra {
    struct edge{
        int to;
        long long cost;
        edge(int to, long long cost) : to(to), cost(cost) { }
    };
    typedef pair< long long, int > P;
    const long long INF = 1LL<<60;
    int v;
    int s;
    vector< vector < edge > > g;
    vector< long long > dist;
    priority_queue< P, vector< P >, greater< P > > que;
    Dijkstra(int v, int s) : v(v), s(s), g(v), dist(v, INF) {
        dist[s] = 0;
        que.push(P(0, s));
    }
    void add_edge(int start, int to, long long cost) {
        g[start].emplace_back(to, cost);
    }
    void build() {
        while (!que.empty()) {
            P p = que.top(); que.pop();
            int current = p.second;
            if (dist[current] < p.first) continue;
            for (edge& e : g[current]) {
                if (dist[e.to] > dist[current] + e.cost) {
                    dist[e.to] = dist[current] + e.cost;
                    que.push(P(dist[e.to], e.to));
                }
            }
        }
    }
    long long shortest_path_value(int t) {
        return dist[t];
    }
};

void Main() {
	int N, M; cin >> N >> M;
    Dijkstra dijkstra(N, 0);
    REP(i, M) {
        int L, R, C; cin >> L >> R >> C;
        --L; --R;
        dijkstra.add_edge(L, R, C);
    }
    REP(i, N - 1) {
        dijkstra.add_edge(i + 1, i, 0);
    }
    dijkstra.build();
    if (dijkstra.shortest_path_value(N - 1) == (1LL<<60)) cout << -1 << endl;
    else cout << dijkstra.shortest_path_value(N - 1) << endl;
}

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


Measured memory_bytes: 9336
#include <algorithm>
#include <climits>
#include <functional>
#include <iterator>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>

using namespace std;

#ifdef _MSC_VER
using ll = __int64;
using ull = unsigned __int64;
#else
using ll = long long int;
using ull = unsigned long long int;
#endif

// 二乗を計算する。
ll sq(ll x) { return x * x; }

// 領域内にいるか。
bool within(ll x, ll min, ll max) {
	return min <= x && x <= max;
}

// container の中から key より小さい値を見つける。
// 見つからない場合は container.end() を返す。
template<typename T>
typename T::iterator less_than(T& container, typename T::key_type& key) {
	typename T::iterator prev = container.lower_bound(key);
	if (prev == container.begin()) prev = container.end();
	else prev--;
	return prev;
}

// container の中から key より大きい値を見つける。
// 見つからない場合は container.end() を返す。
template<typename T>
typename T::iterator greater_than(T& container, typename T::key_type& key) {
	return container.upper_bound(key);
}

// b^e (mod m) を求める
ll modpow(ll b, ll e, ll m) {
	ll result = 1;
	while (e > 0) {
		if ((e & 1) == 1) result = (result * b) % m;
		e >>= 1;
		b = (b * b) % m;
	}
	return result;
}


// ここから解法

int main(void) {
	std::ios_base::sync_with_stdio(false);

	int H, W;
	cin >> H >> W;
	vector<string> S(H);
	for (int i = 0; i < H; ++i) cin >> S[i];

	vector<vector<int>> wmap; wmap.resize(W);
	for (int i = 0; i < W; ++i) wmap[i].resize(H);
	vector<vector<int>> hmap; hmap.resize(H);
	for (int i = 0; i < H; ++i) hmap[i].resize(W);

	for (int i = 0; i < W; ++i) {
		int num = 0;
		for (int j = 0; j < H; ++j) {
			if (S[j][i] == '#') num = 0;
			else num++;
			wmap[i][j] = num;
		}
		num = wmap[i][H - 1];
		for (int j = H - 1; j >= 0; --j) {
			if (S[j][i] == '#') num = 0;
			else if (num == 0) num = wmap[i][j];
			wmap[i][j] = num;
		}
	}

	for (int i = 0; i < H; ++i) {
		int num = 0;
		for (int j = 0; j < W; ++j) {
			if (S[i][j] == '#') num = 0;
			else num++;
			hmap[i][j] = num;
		}
		num = hmap[i][W - 1];
		for (int j = W - 1; j >= 0; --j) {
			if (S[i][j] == '#') num = 0;
			else if (num == 0) num = hmap[i][j];
			hmap[i][j] = num;
		}
	}

	int result = 0;
	for (int i = 0; i < H; ++i) {
		for (int j = 0; j < W; ++j) {
			result = max(result, hmap[i][j] + wmap[j][i] - 1);
		}
	}

	cout << result << endl;

	return 0;
}



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

int main()
{
    vector<vector<char>> c(2, vector<char>(3));
    int count = 0;
    for (int i = 0; i < 2; i++)
    {
        for (int j = 0; j < 3; j++)
        {
            cin >> c.at(i).at(j);
        }
    }
    if (c.at(0).at(0) == c.at(1).at(2))
        count++;
    if (c.at(0).at(1) == c.at(1).at(1))
        count++;
    if (c.at(0).at(2) == c.at(1).at(0))
        count++;
    if(count == 3)
        cout << "YES" << endl;
        else
            cout << "NO" << endl;
}

Measured memory_bytes: 256
# abc160 c
k, n = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
a.sort()
a = [i - a[0] for i in a]
d = []
for i in range(len(a)):
    if i == len(a)-1:
        d.append(k - a[i])
    else:
        d.append(a[i+1] - a[i])
print(k - max(d))

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

#ifdef _DEBUG
inline void dump() { cerr << endl; }
template<typename Head> void dump(Head&& head) { cerr << head; dump(); }
template<typename Head, typename... Tail> void dump(Head&& head, Tail&&... tail) { cerr << head << ", "; dump(forward<Tail>(tail)...); }
#define debug(...) do {cerr << __LINE__ << ":\t" << #__VA_ARGS__ << " = "; dump(__VA_ARGS__); } while (false)
#else
#define dump(...)
#define debug(...)
#endif

template<typename T>
struct edge {
  int src, to;
  T cost;
  edge(int to, T cost) : src(-1), to(to), cost(cost) {}
  edge(int src, int to, T cost) : src(src), to(to), cost(cost) {}
  edge &operator=(const int &x) {
    to = x;
    return *this;
  }
  operator int() const { return to; }
};
template<typename T>
using Edges = vector<edge<T>>;
template<typename T>
using WeightedGraph = vector<Edges<T>>;
using UnWeightedGraph = vector<vector<int>>;
template<typename T>
using Matrix = vector<vector<T>>;

/////////////////////////////////////////////////////////////////////

const ll inf = 1LL<<60;
const string yes = "Yes";
const string no = "No";

int main()
{
  ll a; cin >> a;
  ll b; cin >> b;
  ll c; cin >> c;
  ll k; cin >> k;

  ll x = 0;
  while (a >= b) {
    b *= 2;
    x++;
  }
  while (b >= c) {
    c *= 2;
    x++;
  }

  if (x > k) cout << no << endl;
  else cout << yes << endl;

  return 0;
}


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

int main()
{
 int x;
 int y;

 while (cin >> x >> y ) {
   if ( (x == 0) && ( y == 0 ) ){
    break;
   }

  if ( x < y ) {
    cout << x << " " << y << endl;
  } else {
    cout << y << " " << x << endl;
  }
 }
}

Measured memory_bytes: 1160
#include <cstdio>
#include <cstdlib>
#include <string>
#include <iostream>
using namespace std;

struct Node {
	int key;
	Node *right, *left, *parent;
};

Node *root, *NIL;

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

	z = (Node*)malloc(sizeof(Node));
	z->key = k;
	z->left = NIL;
	z->right = NIL;

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

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

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

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

int main() {
	int n, i, x;
	string com;

	scanf("%d", &n);

	for (i = 0; i < n; i++) {
		cin >> com;
		if (com == "insert") {
			scanf("%d", &x);
			insert(x);
		}
		else if (com == "print") {
			inorder(root);
			printf("\n");
			preorder(root);
			printf("\n");
		}
	}

	return 0;
}


Measured memory_bytes: 26628
#include <bits/stdc++.h>
using namespace std;
template<class t> inline t read(t &x){
    x=0;char c=getchar();bool f=0;
    while(!isdigit(c)) f|=c=='-',c=getchar();
    while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
    if(f) x=-x;return  x;
}
template<class t> inline void write(t x){
    if(x<0){putchar('-'),write(-x);}
    else{if(x>9)write(x/10);putchar('0'+x%10);}
}

#define int long long

const int mod=1e9+7;
const int N=2e6+5;
int x,y,xx,yy,fac[N],inv[N],n;

int fpow(int x,int y){
	int res=1;
	for(;y;y>>=1,x=x*x%mod) if(y&1) res=res*x%mod;
	return res;
}

int C(int n,int m){
	return fac[n]*inv[m]%mod*inv[n-m]%mod;
}

int calc(int n,int m){
	int tot=0;
	for(int j=1;j<=m;j++){
		int l=1+j,r=n+j;
		tot=((tot+C(r+1,j+1)-C(l,j+1))%mod+mod)%mod;
	}
	return tot;
}

signed main(){
	read(x);read(y);read(xx);read(yy);
	n=max(xx,yy)*2+1;
	fac[0]=1;
	for(int i=1;i<=n;i++) fac[i]=fac[i-1]*i%mod;
	inv[n]=fpow(fac[n],mod-2);
	for(int i=n-1;i>=0;i--) inv[i]=inv[i+1]*(i+1)%mod;
	write(((calc(xx,yy)-calc(x-1,yy)-calc(xx,y-1)+calc(x-1,y-1))%mod+mod)%mod);
}

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

int main()
{
    int A, B, C;
    std::cin >> A >> B >> C;

    int cnt = 0;
    if (A == B)
        cnt++;
    if (A == C)
        cnt++;
    if (B == C)
        cnt++;

    if (cnt == 1)
        std::cout << "Yes" << std::endl;
    else
        std::cout << "No" << std::endl;

    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
    string s;
    cin>>s;
    long long int sum=0;
    for(int i=0;i<s.size();i++)
    {
      int x=(int)(s[i]-'0');
      sum+=x;
    }

    if(sum%9==0)
        cout<<"Yes"<<endl;
    else
        cout<<"No"<<endl;

    return 0;

}


Measured memory_bytes: 3684
#include "bits/stdc++.h"
using namespace std;
int main() {
	int N;
	cin >> N;
	long long X;
	cin >> X;
	vector<long long>A(N);
	for (int i = 0; i < N; i++) {
		cin >> A.at(i);
	}
	sort(A.begin(), A.end());
	long long ans = 0;
	for (int i = 0; i < N; i++) {
		if (i == N - 1 && X > A.at(i)) {
			continue;
		}
		if (A.at(i) <= X) {
			ans++;
			X -= A.at(i);
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define _ ios_base::sync_with_stdio(0);cin.tie(0);
#define REP(i,n) for(int i=0;i<(int)(n);i++)

using namespace std;

int main(){ _;
  int n,q,eby,wy,query;
  string en;
  while(cin>>n>>q,(n|q)!=0){
    map<int,pair<int,string> > era;
    REP(i,n){
      cin>>en>>eby>>wy;
      era[wy]=make_pair(eby,en);
    }
    REP(i,q){
      cin>>query;
      auto l=era.lower_bound(query);
      if(l==era.end())cout<<"Unknown"<<endl;
      else{
	int offset=query-((*l).first-(*l).second.first);
	if(offset>0){
	  cout<<(*l).second.second<<" "<<offset<<endl;
	}else{
	  cout<<"Unknown"<<endl;
	}
      }
    }
  }
}

Measured memory_bytes: 1324
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 c = sc.nextInt();
        int cnt = 0;
        for (int i=a; i<=b; i++) {
            if (c%i==0) cnt++;
        }
        System.out.println(cnt);
    }
}


Measured memory_bytes: 26220
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < n; i++)
#define vi vector<int>
#define vvi vector<vi>
#define pii pair<int, int>
#define mod 1000000007
using ll = long long;
using namespace std;
int main(){
  int x,a,b;
  cin >> x >> a >> b;
  x -= a;
  int n = x / b;
  cout << x - n*b << endl;
}

Measured memory_bytes: 256