akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <math.h>
#include <algorithm>
#include <string>
#include <map>
#include <vector>
#include <cmath>

using namespace std;

void a_palindromic_number(void) {
	string n;
	cin >> n;

	if (n[0] == n[2]) cout << "Yes" << endl;
	else              cout << "No" << endl;
}

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

Measured memory_bytes: 3580
/*
─────────────────────
───────────████████──
──────────███▄███████
──────────███████████
──────────███████████
──────────██████─────
──────────█████████──
█───────███████──────
██────████████████───
███──██████████──█───
███████████████──────
███████████████──────
─█████████████───────
──███████████────────
────████████─────────
─────███──██─────────
─────██────█─────────
─────█─────█─────────
─────██────██────────
─────────────────────
*/
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>

#define int long long
#define read(a) int a; cin >> a;
#define readb(a, b) int a, b; cin >> a >> b;
#define readc(a, b, c) int a, b, c; cin >> a >> b >> c;
#define readarr(a, n) int a[(n) + 1] = {}; fori (i, 1, (n)) {cin >> a[i];}
#define readmat(a, n, m) int a[n + 1][m + 1] = {}; fori (i, 1, n) {fori (j, 1, m) cin >> a[i][j];}

#define print(a) cout << a << endl;
#define printarr(a, n) fori (i, 1, n) cout << a[i] << " "; cout << endl;
#define printv(v) for (int i: v) cout << i << " "; cout << endl;
#define printmat(a, n, m) fori (i, 1, n) {fori (j, 1, m) cout << a[i][j] << " "; cout << endl;} cout << endl;
#define all(v) v.begin(), v.end()
#define sz(s) (int)(s.size())
#define pb push_back
#define fi first
#define se second
#define rz resize
#define fori(i, a, b) for (int i = (a); i <= (b); i++)
#define ford(i, a, b) for (int i = (a); i >= (b); i--)
#define endl '\n'
#define setprec(x) cout << fixed << setprecision(x)
 
using namespace std;
using namespace __gnu_pbds; 
 
typedef tree<long long,null_type,less<long long>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef vector<pair <int, int>> vpi;
typedef vector < vector <int> > vvi;
 
const int INF = 4e18;
const int mod = 1e9+7; 

vvi adj(3e5);
     
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    //start from here

    readb(n, m);
    int x, y;

    fori (i, 1, m)
    {
    	cin >> x >> y;
    	adj[x].pb(y); adj[y].pb(x);
    }

    bool flag = false;

    for(int i : adj[1])
    {
    	for (int x : adj[i]) if(x == n) flag = true;
    }

	if(flag) cout << "POSSIBLE";
	else cout << "IMPOSSIBLE";

    return 0;
}


Measured memory_bytes: 15080
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#include<numeric>

using namespace std;

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

template<typename A, typename B> bool chmin(A &a, const B &b){ return b < a && (a = b, true); }
template<typename A, typename B> bool chmax(A &a, const B &b){ return a < b && (a = b, true); }

int main () {
  int l,r,d,cnt = 0;
  cin >> l >> r >> d;
  for (int i = l; i <= r; i++){
    if (i % d == 0){
      cnt++;
    }
    
  }
  cout << cnt << '\n';
  return 0;
}

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

//#define int long long
#define fi first
#define se second
#define rep(i,n) for(int i=0;i<(int)(n);++i)
#define rep1(i,n) for(int i=1;i<=(int)(n);++i)
#define rep11(i,n) for(int i=1;i<(int)(n);++i)
#define repo(i,o,n) for(int i=o;i<(int)(n);++i)
#define repm(i,n) for(int i=(int)(n)-1;i>=0;--i)
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define pb(n) push_back(n)
#define mp make_pair
#define MOD 1002000007
#define INF LONG_LONG_MAX

int main(){
    int h,n;
    cin>>h>>n;
    int a[n];
    int su=0;
    rep(i,n){
        cin>>a[i];
    }
    rep(i,n){
        su+=a[i];
    }
    if ((su>=h) ? cout<<"Yes"<<endl : cout<<"No"<<endl);

}


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using Pair = pair<int, int>;
using Graph = vector<vector<int>>;
#define MOD 1000000007
#define INF 1000000007
#define SEP " "

int     main()
{
	int n;
	cin >> n;
	vector<int> a(n, 0);
	for (int i = 0; i < n; i++)
		cin >> a[i];
	vector<int> b = a;
	sort(b.begin(), b.end(), greater<int>());
	if (b[0] == b[1])
	{
		for (int i = 0; i < n; i++)
			cout << b[0] << endl;
	}
	else
	{
		for(int i = 0; i < n; i++)
		{
			if (a[i] == b[0])
				cout << b[1] << endl;
			else
				cout << b[0] << endl;
		}
	}
}


Measured memory_bytes: 3200
import re

def main():
    N = str(input())
    if re.match("^.*keyence$", N) or re.match("^k.*eyence$", N) or re.match("^ke.*yence$", N) or re.match("^key.*ence$", N) or re.match("^keye.*nce$", N) or re.match("^keyen.*ce$", N) or re.match("^keyenc.*e$", N) or re.match("^keyence.*$", N):
        print("YES")
    else:
        print("NO")



if __name__ == "__main__":
    main()

Measured memory_bytes: 3188
n, k = map(int, input().split())
r,s,p = map(int, input().split())
t = input()
z = 0
kachi = dict({"r": "p", "s": "r", "p": "s"})
tt = []
for i in range(n):
    tt.append(kachi[t[i]])
#print(t)
#print(tt)
for i in range(n - k):
    if tt[i] == tt[i + k]:
        tt[i+k] = "z"
kachi = dict({"r": r, "s": s, "p": p, "z": 0})
res = 0
for i in range(n):
    res += kachi[tt[i]]
print(res)

Measured memory_bytes: 4212
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <math.h>
#include <iomanip>
#include <map>
using namespace std;

int main() {
    string s;
    cin >> s;
    if (s.at(5) == '0' && (s.at(6) <= '4')) cout << "Heisei" << endl;
    else cout << "TBD" << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
using namespace std;
int main(void){
  string s;
  cin>>s;
  if(s[0]=='a' || s[0]=='e' || s[0]=='i' || s[0]=='o' || s[0]=='u')cout<<"vowel"<<endl;
  else cout<<"consonant"<<endl;
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
    set<int> s;
    set<int>::iterator it;
    int n;
    cin>>n;

    while(n--)
    {
        int a;
        cin>>a;

        if(a==0)
        {
            int x;
            cin>>x;
            s.insert(x);
            cout<<s.size()<<endl;

        }

        else if(a==1)
        {
            int x;
            cin>>x;

            if(s.find(x)!=s.end())
              cout<<1<<endl;
            else
                cout<<0<<endl;

        }

        else if(a==2)
        {
            int x;
            cin>>x;
            s.erase(x);

        }

        else if(a==3)
        {
            int x,y;
            cin>>x>>y;
            for(it=s.lower_bound(x);it!=s.upper_bound(y);it++)
            {
                cout<<*it<<endl;
            }
        }

    }

    return 0;

}





Measured memory_bytes: 12368
#include<stdio.h>

int main(){
	int n,m;
	scanf("%d %d",&n,&m);
	int a[n],i,sum = 0;
	
	for(i = 0;i < n;i++){
		scanf("%d",&a[i]);
		sum += a[i];
	}
	
	double stand = sum/(4.0*(double)m);
	int count = 0;
	for(i = 0; i < n;i++){
		if((double)a[i] >= stand)
			count++;
	}
	
	if(count >= m )
		printf("Yes");
	else
		printf("No");
		
		
	
	return 0;
} 

Measured memory_bytes: 1704
#include <iostream>
#include <cmath>
#include <numeric>
#include <string>
#include <vector>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <algorithm>
using namespace std;

using ll = long long;

#define MOD 1000000007

#define FOR(i, m, n) for (ll i = m; i <= n; i++)
#define FORR(i, m, n) for (ll i = m; i >= n; i--)

ll gcd(ll a, ll b) { if (a < b) { a ^= b; b ^= a; a ^= b; } return b ? gcd(b, a % b) : a; }
ll lcm(ll a, ll b) { return a * b / gcd(a, b); }

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


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

using namespace std;
using ll =long long;
#define For(i, a, b)    for(int i = (a) ; i < (b) ; ++i)
#define rep(i, n)       For(i, 0, n)
#define debug(x)  cerr << #x << " = " << (x) << endl;
#define leftunique(a) {sort((a).begin(),(a).end());(a).erase(unique((a).begin(),(a).end()),(a).end());}
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
static const ll INF = 1LL << 60;
//Write From this Line

int main()
{
	int a, b;
	cin >> a >> b;
	cout << (a + b + 1) / 2 << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,cc,n) for(int i=cc;i<=n;++i)
#define drep(i,cc,n) for(int i=cc;i>=n;--i)
#define sz(s) (int)(s.size())
#define vecprint(v) rep(i,0,v.size()-1)cout << v[i] << " ";cout << endl;
#define mod 1000000007

using namespace std;

int main(){

  int a,n,m;
  long long ans=0;
  priority_queue<int> q;

  cin >> n >> m;
  
  rep(i,0,n-1){
    cin >> a;
    q.push(a);
  }

  rep(i,0, m-1){
    a = q.top();
    q.pop();
    q.push(a/2);
  }

  rep(i,0,n-1){
    a = q.top();
    q.pop();
    ans += a;
  }
  
  cout << ans << endl;
  return 0;
}


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

typedef long long ll;
typedef long double ld;
typedef vector<ll> vi;
typedef pair<ll, ll> pii;
typedef vector<pii> vii;
typedef map<ll, ll> mii;
const int MOD = 1e9 + 7;

#define fastIO() \
ios_base::sync_with_stdio(false); cin.tie(nullptr);
#define endl "\n"
#define pb push_back
#define ff first
#define ss second
#define mp make_pair 
template<typename T>
T minm(T x) { return x; }
template <typename T, typename... Args>
T minm(T a, Args... args) { return min(a, minm(args...)); }
template<typename T>
T maxm(T x) { return x; }
template <typename T, typename... Args>
T maxm(T a, Args... args) { return max(a, maxm(args...)); }



int main() {
    int n, x, y;
    cin >> n >> x >> y;
    --x, --y;
    vector<vi> d(n, vi(n));
    for (int i = 0; i < n; ++i) {
        for (int j = i; j < n; ++j)
            d[j][i] = d[i][j] = abs(j - i);
    }
    if (x > y)  swap(x, y);
    d[x][y] = 1;
    d[y][x] = 1;
    vi ans(n - 1);
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            d[i][j] = minm(d[i][j],
                        d[i][x] + d[x][y] + d[y][j],
                        d[i][y] + d[x][y] + d[x][j]);
            ++ans[d[i][j] - 1];
        }
    }
    for (auto i : ans)  cout << i << endl;
    
    return 0;
}


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

long long n, m = 0;
long long a[200000];

int main()
{
	cin >> n;

	for (int i = 0; i < n; i++)
		cin >> a[i];

	sort(a, a + n, greater<long long>());

	for (int i = 0; i < n - 1; i++)
		m += a[(i + 1) / 2];

	cout << m << endl;
}


Measured memory_bytes: 5200
#define errOut(s) \
  { std::cerr << __LINE__ << ":" << #s << ":" << (s) << std::endl; }

#include <bits/stdc++.h>
#pragma clang diagnostic push
#pragma clang diagnostic ignored "-Weverything"
//#include <boost/multi_array.hpp>
//#include <boost/optional.hpp>
//#include <boost/range/adaptors.hpp>
//#include <boost/range/algorithm.hpp>
//#include <boost/range/irange.hpp>
#pragma clang diagnostic pop

using namespace std;

static constexpr int64_t MOD = 1000000007;

static int64_t table[100001];

int64_t solve(int64_t n, int64_t /*m*/, const std::bitset<100001>& as) {
  table[n] = 1;
  for (int i = n - 1; i >= 0; i--) {
    if (as.test(i)) {
      continue;
    }
    int64_t t = 0;
    if (i + 1 <= n) {
      t += table[i + 1];
      t %= MOD;
      if (i + 2 <= n) {
        t += table[i + 2];
        t %= MOD;
      }
    }
    table[i] = t;
  }
  return table[0];
}

int main() {
  std::cin.tie(nullptr);
  std::ios::sync_with_stdio(false);
  int64_t n;
  std::cin >> n;
  int64_t m;
  std::cin >> m;
  std::bitset<100001> as{0};
  for (int i = 0; i < m; i++) {
    int a;
    std::cin >> a;
    as.set(a);
  }
  auto const res = solve(n, m, std::move(as));
  std::cout << res << std::endl;
  return 0;
}


Measured memory_bytes: 4384
a=[0]*45

def Fib(n):
    if n == 0:
        a[0]=1
        return 1
    elif n == 1:
        a[1]=1
        return 1
    else:
        if a[n]==0:
            a[n]=Fib(n-1)+Fib(n-2)
            return a[n]
        else:
            return a[n]
    
n=int(input())
print(Fib(n))




Measured memory_bytes: 5600
#include<bits/stdc++.h>
#define int ll
//{ PXH612
using namespace std;
#define ll long long
#define db double
#define pp pair<int,int>
#define x first
#define y second

#define false(x) if(!(x))
template<typename A,typename B>bool Min(A &a,B b){if(a<=b) return 0;a=b;return 1;}
template<typename A,typename B>bool Max(A &a,B b){if(a>=b) return 0;a=b;return 1;}
#define in ({ll x=0;int o=0,c=char(),t=0;for(;!isdigit(c)&&t<1000;c=getchar(),t++) o=c=='-';for(;isdigit(c);c=getchar()) x=x*10+c-'0';o?-x:x;})
#define inchar ({char c=getchar();while(c==' '||c=='\n') c=getchar();c;})

#define FOR(i,a,b) for(int i=a,ENDFOR=b;i<=ENDFOR;i++)
#define ROF(i,a,b) for(int i=b,ENDFOR=a;ENDFOR<=i;i--)
#define RR(x,a,b) {cout<<#x<<": ";FOR(_,a,b) cout<<x[_]<<" ";cout<<"\n";}
#define rr(x) " "<<#x<<'='<<(x)<<" "

#define VEC(i,a) for(auto&i:a)
#define pb push_back
#define vn(a) (int)a.size()-1

#define bit(x,i) ((x>>(i-1))&1ll)
#define on(x,i) (x|(1ll<<(i-1)))
#define off(x,i) (x&~(1ll<<(i-1)))
#define mu(x) (1ll<<x)
#define bitnum(x) __builtin_popcountll(x)

#define segg(a,b) (abs(a-b)+1)
#define midd(a,b) (a+(b-(a))/2)
#define mems(x,a) memset(x,a,sizeof x)
#define open(a) freopen(a,"r",stdin)
#define shut(b) freopen(b,"w",stdout)
//}/////////////////////////////////////////////////////}

const int N=1e5+5;
int n;
int a[N],ans[N];
vector<int> e[N],v;

int low(int x){return lower_bound(v.begin(),v.end(),x)-v.begin();}
main()
{
  // open("frequency.inp");
    n=in;
    FOR(i,1,n) a[i]=in;
    FOR(i,1,n) v.pb(a[i]);

    v.pb(0);

    sort(v.begin(),v.end());
    v.erase(unique(v.begin(),v.end()),v.end());
    FOR(i,1,n) e[low(a[i])].pb(i);

    int cnt=0,mn=INT_MAX;
   // cout<<rr(v[0]) rr(v[1]) "\n";
    ROF(i,1,vn(v)) if(e[i].size())
    {
        VEC(j,e[i]) Min(mn,j);
        cnt+=e[i].size();
        ans[mn]+=cnt*(v[i]-v[i-1]);
    }
    FOR(i,1,n) cout<<ans[i]<<"\n";
}


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

using namespace std;

#define MAX 500
#define MAX_M 10000

int main(){
  int N,M;
  while(cin >> N >> M,(N | M)){
    bool F[MAX] = {0},C[MAX] = {0};
    int A[MAX_M],B[MAX_M],idx = 0;
    for(int i = 0 ; i < M ; i++){
      int a,b;
      cin >> a >> b; a--; b--;
      if(!a){
        F[b] = C[b] = true;
      }else{
        A[idx] = a; B[idx++] = b;
      }
    }
    for(int i = 0 ; i < idx ; i++){
      if(!F[A[i]] && F[B[i]]){
        C[A[i]] = true;
      }else if(F[A[i]] && !F[B[i]]){
        C[B[i]] = true;
      }
    }
    int ans = 0;
    for(int i = 0 ; i < N ; i++){
      ans += C[i];
    }
    cout << ans << endl;
  }
  return 0;
}

Measured memory_bytes: 1236
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

const int Max_n = 54;
long long a[Max_n], ans_arr[2* Max_n][2], ans=0;
vector<pair<int, int> > pairs(Max_n);
    
int main(){
    int N;
    cin >> N;

    //if(a[i-1] <= a[i]) //次に進む
    //if(min < a[i]) //もう一度最小値をたす
    //if(a[i-1] > a[i]) //最小値ををたす a[i] + min
    long long min = 10000000;
    int min_idx;
    long long max = -10000000;
    int max_idx;

    for(int i =0; i < N; i++){
        cin >> a[i];
        if(a[i] > max){
            max = a[i];
            max_idx = i;
        }
        if(a[i] < min){
            min = a[i];
            min_idx = i;
        }
    }
    

    if(abs(max) < abs(min)){
        for(int i =N-1; i > 0; i--){
            if(a[i-1] > a[i]){
                a[i-1] += min;
                ans_arr[ans][0] = i -1;
                ans_arr[ans][1] = min_idx;
                ans++;

                if(min > a[i-1]){
                    min = a[i-1];
                    min_idx = i -1;
                }

                if(a[i-1] > a[i]){
                    a[i-1] += min;
                    ans_arr[ans][0] = i - 1;
                    ans_arr[ans][1] = min_idx;
                    ans++;
                }

                if(min > a[i-1]){
                    min = a[i-1];
                    min_idx = i -1;
                }
            }
        }
    }
    else{
        for(int i =1; i < N; i++){
            if(a[i-1] > a[i]){
                a[i] += max;
               

                ans_arr[ans][0] = i;
                ans_arr[ans][1] = max_idx;
                ans++;
                

                if(max < a[i]){
                    max = a[i];
                    max_idx = i;
                }

                if(a[i-1] > a[i]){
                    a[i] += max;

                    ans_arr[ans][0] = i;
                    ans_arr[ans][1] = max_idx;
                    ans++;
                    }

                if(max < a[i]){
                    max = a[i];
                    max_idx = i;
                }
            }
        }

    }
    cout << ans << endl;
    for(int i =0; i < ans; i++){
        cout << ans_arr[i][1] + 1<< " " << ans_arr[i][0] +1  << endl;
    }
    
   

    return 0;
}

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

using namespace std;

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int n, m; cin >> n >> m;
	n *= 2;
	
	int arr[n]; for(int i = 0;i < n;i++) cin >> arr[i];
	sort(arr,arr+n);
	
	int low = -1;
	int high = n/2 + 1;
	
	while(true){
		if(low == high - 1) break;
		int s = (low + high) / 2;
		
		bool can = true;
		for(int x = 2*s;x < n/2 + s;x++){
			int y = n + 2*s - 1 - x;
			if(arr[x] + arr[y] < m) can = false;
		}
				
		if(can) high = s;
		else low = s;
	}
	
	int ans = 0;
	for(int x = 0;x < high;x++){
		int y = 2*high - 1 - x;
		ans = max(ans, arr[x] + arr[y]);
	}
	
	for(int x = 2*high;x < n/2 + high;x++){
		int y = n + 2*high - 1 - x;
		ans = max(ans, arr[x] + arr[y] - m);
	}
	
	cout << ans;
}


Measured memory_bytes: 1024
#include <iostream>
#include <string>
#include <sstream>
#include <iomanip> 
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <functional>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#include <bitset>

using namespace std;

#define MAXN 50000

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

	string s, t;
	int ans;

	cin >> s >> t;
	ans = 0;
	if (s[0] == t[0]) ans++;
	if (s[1] == t[1]) ans++;
	if (s[2] == t[2]) ans++;

	cout << ans << "\n";

	return 0;
}


Measured memory_bytes: 256
#include <cstdio>

using namespace std;

int main() {
    int n, prev, now, cnt = 1, f = 0;
    scanf("%d%d", &n, &prev);
    for (int i = 1; i < n; ++i) {
        scanf("%d", &now);
        if (prev == now) continue;
        if (f) {
            if ((f > 0 && prev > now) || (f < 0 && prev < now)) f = 0, ++cnt;
        } else f = (prev < now) * 2 - 1;
        prev = now;
    }
    printf("%d\n", cnt);
    return 0;
}


Measured memory_bytes: 128
import java.util.*;
public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
      
      //Aの入力を受け取る
      int A = sc.nextInt();
      //Bの入力を受け取る
      int B = sc.nextInt();
      
      //AとBをかけて表示する
      System.out.print(A * B);
    }
}


Measured memory_bytes: 27072
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

void solve(ll r, ll D, ll x){
    vector<ll> X(11, 0);
    X[0] = x;
    for(int i = 0; i < X.size() - 1; ++i){
        X[i+1] = r * X[i] - D;
    }
    for(int i = 1; i < X.size(); ++i) cout << X[i] << endl;
}

int main(){
    ll r, D, x;
    cin >> r >> D >> x;
    solve(r, D, x);
    return 0;
}


Measured memory_bytes: 256
#https://tjkendev.github.io/procon-library/python/range_query/rmq_segment_tree.html
# N: 処理する区間の長さ

#bit管理
#演算はor
N = int(input())
s = input()


N0 = 1
while N0<=N:
    N0*=2
INF = 0
data = [0]*(2*N0)
# a_k の値を x に更新
def update(k, x):
    k += N0-1
    data[k] = 1<<x
    while k >= 0:
        k = (k - 1) // 2
        data[k] =data[2*k+1]|data[2*k+2]
# 区間[l, r)の最小値
def query(l, r):
    L = l + N0; R = r + N0
    s = INF
    while L < R:
        if R & 1:
            R -= 1
            s = s|data[R-1]

        if L & 1:
            s = s|data[L-1]
            L += 1
        L >>= 1; R >>= 1
    return s

for i in range(N):
    update(i,ord(s[i])-ord("a"))
q = int(input())

for j in range(q):
    t,l,r = input().split( )
    if t=="1":
        update(int(l)-1,ord(r)-ord("a"))
        
    else:
        bit = bin(query(int(l)-1,int(r)))[2:]
        ans = 0
        for i in bit:
            ans += int(i)
        print(ans)

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

using namespace std;

int dp[1001][1001];

int main(void) {
  int W, n;
  int num = 1;
  while (cin >> W, W) {
    cin >> n;
    memset(dp, 0, sizeof(dp));
    
    vector<int> v(n), w(n);
    char c;
    for (int i = 0; i < n; i++) {
      cin >> v[i] >> c >> w[i];
    }

    for (int i = 1; i <= n; i++) {
      for (int j = 0; j <= W; j++) {
        dp[i][j] = dp[i - 1][j];
        if (j >= w[i - 1]) {
          dp[i][j] = max(dp[i][j], dp[i - 1][j - w[i - 1]] + v[i - 1]);
        }
      }
    }

    printf("Case %d:\n", num++);
    cout << dp[n][W] << endl;
    cout << lower_bound(dp[n], dp[n] + W, dp[n][W]) - dp[n] << endl;
  }

  return 0;
}


Measured memory_bytes: 7136
n = int(input())
A = list(map(int, input().split()))
ans1 = 0
acc = 0
d = 1
for a in A:
    if (acc + a) * d > 0:
        acc += a
    else:
        ans1 += abs(1 - (acc + a) * d)
        acc = d
    d *= -1
ans2 = 0
acc = 0
d = -1
for a in A:
    if (acc + a) * d > 0:
        acc += a
    else:
        ans2 += abs(1 - (acc + a) * d)
        acc = d
    d *= -1
print(min(ans1, ans2))

Measured memory_bytes: 14468
def slove():
    import sys
    input = sys.stdin.readline
    n = int(input().rstrip('\n'))
    if n == 25:
        print("Christmas")
    elif n == 24:
        print("Christmas Eve")
    elif n == 23:
        print("Christmas Eve Eve")
    elif n == 22:
        print("Christmas Eve Eve Eve")


if __name__ == '__main__':
    slove()


Measured memory_bytes: 38256
#include<bits/stdc++.h>
 
using namespace std;
 
int main()
{
 
	int n , x,y;
	cin>>n>>x>>y;

	x--;y--;
	map<int,map<int,int> > dis; 
	map<int,int> m;
	for(int i =0;i<n;i++)
	{
		for(int j=i+1;j<n;j++)
		{
			if(dis[i][j]==0)
				dis[i][j]= INT_MAX;
			dis[i][j] = min(abs(j-i) , min( abs(x-i)+abs(y-j)+1 , abs(x-j)+abs(y-i)+1));
			m[dis[i][j]]++;
		}
	}
	for(int i=1;i<n;i++)
		cout<<m[i]<<"\n";
}

Measured memory_bytes: 94208
import sys
input = sys.stdin.readline
S = input()
a = "WA"
count = 0
b = 0
if S[0] == 'A' :
    k = S[1]
    K = k.lower()
    if k == K :
        for i in range(2,len(S)-2) :
            if S[i] == "C" :
                count +=1
        for i in range(2,len(S)) :
            if S[i] != "C" :
                k = S[i]
                K = k.lower()
                if k != K :
                    b = 1
                    break
        if count == 1 and b == 0 :
            a = "AC"
print(a)

Measured memory_bytes: 3064
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.IO;
using System.Text;
using System.Globalization;
using System.Diagnostics;



class Myon
{
    public Myon() { }
    public static int Main()
    {
        new Myon().calc();
        return 0;
    }


    Scanner cin;
    

    void calc()
    {
        cin = new Scanner();
        int N = cin.nextInt();
        long[] A = cin.ArrayLong(N);
        long[] B = cin.ArrayLong(N);

        long needDec = 0;
        long needAdd = 0;
        for (int i = 0; i < N; i++)
        {
            long diff = A[i] - B[i];
            if (diff == 0) continue;
            if(diff > 0)
            {
                needDec += diff;
            }
            else
            {
                diff = -diff;
                long add = diff + diff % 2;
                needAdd += add;
                needDec += diff % 2;
            }
        }
        //Console.WriteLine(needAdd + " " + needDec);

        if (needAdd < needDec * 2) Console.WriteLine("No");
        else Console.WriteLine("Yes");

    }
    
}


class Scanner
{
    string[] s;
    int i;

    char[] cs = new char[] { ' ' };

    public Scanner()
    {
        s = new string[0];
        i = 0;
    }

    public string next()
    {
        if (i < s.Length) return s[i++];
        string st = Console.ReadLine();
        while (st == "") st = Console.ReadLine();
        s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
        if (s.Length == 0) return next();
        i = 0;
        return s[i++];
    }

    public int nextInt()
    {
        return int.Parse(next());
    }
    public int[] ArrayInt(int N, int add = 0)
    {
        int[] Array = new int[N];
        for (int i = 0; i < N; i++)
        {
            Array[i] = nextInt() + add;
        }
        return Array;
    }

    public long nextLong()
    {
        return long.Parse(next());
    }

    public long[] ArrayLong(int N, long add = 0)
    {
        long[] Array = new long[N];
        for (int i = 0; i < N; i++)
        {
            Array[i] = nextLong() + add;
        }
        return Array;
    }

    public double nextDouble()
    {
        return double.Parse(next());
    }


    public double[] ArrayDouble(int N, double add = 0)
    {
        double[] Array = new double[N];
        for (int i = 0; i < N; i++)
        {
            Array[i] = nextDouble() + add;
        }
        return Array;
    }
}


Measured memory_bytes: 12768
import std.stdio;
import std.string;
import std.conv;
import std.typecons;
import std.algorithm;
import std.functional;
import std.bigint;
import std.numeric;
import std.array;
import std.math;
import std.range;
import std.container;

void main() {
    long[] ary = [6000, 4000, 3000, 2000];
    foreach(int i; 0..4) {
        int[] input = readln.split.to!(int[]);
        writeln(ary[input[0]-1]*input[1]);
    }
}

Measured memory_bytes: 2468
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<math.h>
#include<complex>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<functional>
#include<assert.h>
#include<numeric>
using namespace std;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
using ll = long long;
const int inf=1e9+7;
const ll longinf=1LL<<60 ;
const ll mod=1e9+7 ;

int main(){
	int n,k;
	cin>>n>>k;
	vector<int> nxt(n);
	rep(i,n){
		cin>>nxt[i];
		--nxt[i];
	}
	vector<int> dp(n,inf);
	for(int i=n-1;i>=0;--i){
		if(dp[i]==inf)dp[i]=0;
		if(~nxt[i])dp[nxt[i]]=min(dp[nxt[i]],dp[i]+1);
		else dp[i]=0;
	}
	int ans=0;
	rep(i,n){
		if(dp[i]<k)++ans;
	}
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 3616
import java.util.Scanner;

public class Main{
	public static void main(String[] args){
		Scanner scan = new Scanner(System.in);
		
		int[] teishutu = new int[31]; 
		
		for(int i = 0;i < 28 ;i++){
			int a = scan.nextInt();
			
			teishutu[a] = 1;
		}
		
		for(int i = 1;i < 31;i++){
			if(teishutu[i] == 0){
				System.out.println(i);
			}
		}
		
	}
}

Measured memory_bytes: 26404
#include <bits/stdc++.h>
#include<vector>
using namespace std;
#define rep(i, n)        for(int i=0; i<(int)(n); ++i)
int main() {
  int b,c;
  string a;
  cin>>a;
  b=(a.size()+3)/2;
  c=(a.size()-1)/2;
  for(int i=0;i<a.size();i++){
    if(a.at(i)!=a.at(a.size()-i-1)){
      cout<<"No";
      return 0;
    }
  }
  for(int i=0;i<(a.size()-1)/2;i++){
    if(a.at(i)!=a.at(c-1-i)){
      cout<<"No";
      return 0;
    }
    if(a.at(i+b-1)!=a.at(a.size()-i-1)){
      cout<<"No";
      return 0;
    }
  }
  cout<<"Yes";
}

Measured memory_bytes: 256
#include<iostream>
#include<math.h>
#include<algorithm>
using namespace std;
int main(){
    int A, B, C;
    cin >> A >> B >> C;
    int K;
    cin >> K;
    for(int i = 1;i <= K;i++){
    if(max({A, B, C}) == A)A *= 2;
    if(max({A, B, C}) == B)B *= 2;
    if(max({A, B, C}) == C)C *= 2;
    }
    cout << A + B + C;
}


Measured memory_bytes: 256
def c_1d_reversi(S):
    # 端の同じ色の石は1個の石を置けばひっくり返せる
    # 連続した石をひとまとめにしたとき、何個の石があるかが解を導く
    from itertools import groupby
    return len(list(groupby(S))) - 1

S = input()
print(c_1d_reversi(S))

Measured memory_bytes: 15860
#include<bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
	ll a, b, c, k;
	cin >> a >> b >> c >> k;
	while (a >= b) {
		b *= 2;
		--k;
	}
	while (b >= c) {
		c *= 2;
		--k;
	}
	cout << (k >= 0 ? "Yes" : "No") << endl;
}


Measured memory_bytes: 3628
H, W, K = map(int, input().split())
colors = []
for _ in range(H):
    colors.append(list(input()))
black_cnt = 0
for i in range(H):
    for j in range(W):
        if colors[i][j] == '#':
            black_cnt += 1

ans = 0
for i in range(2 ** H):
    # 行方向の黒の個数を列挙
    tmp_black_cnt = black_cnt
    for j in range(H):
        if (i >> j) & 1:
            for k in range(W):
                if colors[j][k] == '#':
                    tmp_black_cnt -= 1
    # print(i, tmp_black_cnt)
    for l in range(2 ** W):
        row_tmp_black_cnt = tmp_black_cnt
        for m in range(W):
            if l == 4:
                a = 1
            if (l >> m) & 1:
                for n in range(H):
                    if colors[n][m] == '#':
                        row_tmp_black_cnt -= 1
        for j in range(H):
            for m in range(W):
                if (l >> m) & 1 and (i >> j) & 1 and colors[j][m] == '#':
                    row_tmp_black_cnt += 1
        # print(i, l, row_tmp_black_cnt)
        if row_tmp_black_cnt == K:
            ans += 1
print(ans)

Measured memory_bytes: 9252
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>
#include <stack>
#include <set> 
#include <map>
#include <bitset>
#include <cctype>
#include <cmath>
#include <cstring>
#include <iomanip>
#include <cctype>
#define REP(i,n) for(int i=0; i<(n); ++i)
#define FOR(i,a,b) for(int i=(a); i<(b); ++i)
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const int INF = 100100100;
const ll INFLL = 1001001001001001001;  // > 10^18
const int MOD = (int)1e9 + 7;
const ll MODLL = (ll)1e9 + 7;
const double EPS = 1e-9;


int main() {
    
    int n,d; cin >>n>>d;

    int cov = d*2+1;

    if (n % cov == 0) {
        cout << n /cov << endl;
    } else {
        cout << (n/ cov) + 1 << endl;
    } 

    return 0;

}




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

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n, k, q;
  cin >> n >> k >> q;
  vector<int> a(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  int ans = 2e9;
  for (int& bound : a) {
    vector<int> t;
    vector<int> s;
    for (int i = 0; i <= n; i++) {
      if (i == n || a[i] < bound) {
        sort(t.begin(), t.end());
        for (int i = 0; i <= (int) t.size() - k; i++) {
          s.push_back(t[i]);
        }
        t.clear();
      } else {
        t.push_back(a[i]);
      }
    }
    if ((int) s.size() < q) {
      continue;
    }
    sort(s.begin(), s.end());
    ans = min(ans, s[q - 1] - bound);
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < n; i++)
#define all(x)(x).begin(), (x).end() // 昇順ソート
#define rall(v)(v).rbegin(), (v).rend() // 降順ソート
#define INF 1LL << 60
typedef long long int LL;
typedef long long int ll;
#define pll pair < ll, ll >
#define F first
#define S second
const int MOD = 1000000007;
template < class T > bool chmax(T & a,const T & b) { if (a < b) { a = b; return true; } return false; }
template < class T > bool chmin(T & a,const T & b) { if (a > b) { a = b; return true; } return false; }
// 任意のlogは　対数の底の変換を使う    log(N) / log(任意の底)

int main() {
    double R;cin >> R;
    double ans = 2*R*M_PI;
    cout << std::fixed << std::setprecision(15) << ans << endl;
}

Measured memory_bytes: 3752
#include <stdio.h>

int main(){
  int i,flag=0;
  char a;
  char b[5] ="aiueo";
  scanf("%c",&a);
  
  for(i=0;i<5;i++){
    if(a==b[i])flag=1;
  }
  if(flag==1)printf("vowel");
  else printf("consonant");
  return 0;
}

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

#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define FOR(i,n,m) for(int i=(int)(n); i<=(int)(m); i++)
#define RFOR(i,n,m) for(int i=(int)(n); i>=(int)(m); i--)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define RITR(x,c) for(__typeof(c.rbegin()) x=c.rbegin();x!=c.rend();x++)
#define setp(n) fixed << setprecision(n)

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

#define ll long long
#define vll vector<ll>
#define vi vector<int>
#define pll pair<ll,ll>
#define pi pair<int,int>

#define all(a) (a.begin()),(a.end())
#define rall(a) (a.rbegin()),(a.rend())
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define ins insert

using namespace std;

void dfs(int v, int p, vector<vi> &G, vi &ord, vi &low, int &idx)
{
    ord[v] = low[v] = idx++;
    for(auto u:G[v]){
        if (u==p) continue;
        if (ord[u]!=-1){
            chmin(low[v],ord[u]);
            continue;
        }
        dfs(u,v,G,ord,low,idx);
        chmin(low[v],low[u]);
    }
}

//-------------------------------------------------

int main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N,M; cin>>N>>M;
    vector<vi> G(N);
    rep(i,M){
        int a,b; cin>>a>>b;
        G[a].pb(b);
        G[b].pb(a);
    }
    vi ord(N,-1),low(N);
    int idx=0;
    dfs(0,-1,G,ord,low,idx);
    vector<pi> ans;
    rep(v,N){
        for(auto u:G[v]){
            if (ord[v]<low[u]){
                int a = min(v,u);
                int b = max(v,u);
                ans.pb({a,b});
            }
        }
    }
    sort(all(ans));
    for(auto e:ans){
        cout<<e.fi<<" "<<e.se<<"\n";
    }
    return 0;
}



Measured memory_bytes: 4908
def gcd(a,b):
    while b > 0:
        a, b = b, a % b
    return a
    
def lcm(a, b):
    return a * b / gcd(a, b)
  
a = [int(i) for i in input().split()]
k = a[1]//a[2] - (a[0] - 1)//a[2]
r = a[1]//a[3] - (a[0] - 1)//a[3]
s = a[1]//(int(lcm(a[2],a[3]))) - (a[0] - 1)//int((lcm(a[2],a[3])))
print((a[1] - a[0] + 1 - (k + r - s)))

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

int main()
{
    long long int n, m;
    cin >> n >> m;

    long long int res = 0;
    if(2*n <= m)
    {
        res += n;
        m -= 2*n;
        n = 0;
        //cout << "a" << endl;
        //cout << n <<" " << m << endl;
    }
    else if(m/2 <= n)
    {
        res += m / 2;
        n -= m / 2;
        m -= (m / 2) * 2;
        //cout << "b" << endl;
    }
    
    if(m >= 4)
    {
        res += m/4;
        //cout << "c" << endl;
    }

    cout << res << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define MOD 1000000007
#define INF 1061109567
#define bp __builtin_popcountll
#define pb push_back
#define in(s) freopen(s,"r",stdin);
#define out(s) freopen(s,"w",stdout);
#define fi first
#define se second
#define bw(i,r,l) for (int i=r-1;i>=l;i--)
#define fw(i,l,r) for (int i=l;i<r;i++)
#define fa(i,x) for (auto i:x)
using namespace std;
const int N = 2005;
int n, k, q, a[N];
set<pair<int, int>> s;
vector<int> v;
int get(int x) {
	int l = -1, r = -1;
	s.clear();
	fw (i, 0, n) if (a[i] >= x) {
		if (i == 0 || a[i - 1] < x) l = i, r = -1;
		if (i == n - 1 || a[i + 1] < x) r = i;
		if (r != -1) s.insert({l, r});
	}
	priority_queue<int, vector<int>, greater<int>> val;
	fa (i, s) {
		int le = i.fi, ri = i.se, pick = max(0, ri - le + 2 - k);
		priority_queue<int, vector<int>, greater<int>> cur;
		fw (j, le, ri + 1) cur.push(a[j]);
		while (pick--) {
			val.push(cur.top());
			cur.pop();
		}
	}
	int cur = q, mx;
	while (cur--) {
		if (val.empty()) return INF;
		mx = val.top(), val.pop();
	}
	return mx - x;
}
signed main() {
	#ifdef BLU
	in("BLU.inp");
	#endif
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n >> k >> q;
	fw (i, 0, n) cin >> a[i], v.pb(a[i]);
	/*
	Fix the minimum as x. Now we obtain a few continuous segments (delete all numbers smaller than x)
	Call a range [l...r]. Then we can erase max(0, r - l + 2 - k) smallest numbers from it. Save all
	of these into a set and the task is easy.
	Iterate through all possible minimums (array elements only). Simulating takes O(NlogN), and
	iterating through the minimum takes O(N). So total complexity is O(N ^ 2logN)
	*/
	sort(v.begin(), v.end());
	v.resize(unique(v.begin(), v.end()) - v.begin());
	int ans = INF;
	fa (i, v) ans = min(ans, get(i));
	cout << ans;
	return 0;
}

Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
#define ALL(v) (v).begin(),(v).end()
#define REP(i,p,n) for(int i=p;i<(int)(n);++i)
#define rep(i,n) REP(i,0,n)
#define SZ(x) ((int)(x).size())
#define debug(x) cerr << #x << ": " << x << '\n'
#define INF 999999999
typedef long long int Int;
using ll = long long;
using VI = vector<int>;

int main(){
  int a,b,c,x;cin >> a >> b >> c >> x;
  int ans = 0;
  for(int i=0;i<=a;i++){
    for(int j=0;j<=b;j++){
      for(int k=0;k<=c;k++){
        if((500*i+100*j+50*k)==x) ans++;
      }
    }
  }
  cout << ans << endl;
}


Measured memory_bytes: 256
n=gets.to_i
a=Array.new(n+1)
a[0]=0
a[1]=1
for i in 2..n do
  d=6
  list=[]
  while d<=i do
    list.push(a[i-d])
    d*=6
  end
  d=9
  while d<=i do
    list.push(a[i-d])
    d*=9
  end
  list.push(a[i-1])
  a[i]=list.min+1
end
p a[n]

Measured memory_bytes: 2812
#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(void){
  int n;
  cin >> n;
  vector<int> ans(n+5,0);
  for(int i = 0; i < n-1; i++){
    int a;
    cin >> a;
    ans[a]++;
  }
  for(int i = 1; i <= n; i++){
    cout << ans[i] << endl;
  }
  return 0;
}

Measured memory_bytes: 4064
import sys
sys.setrecursionlimit(10**9)

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

class Union_Find:
    def __init__(self,n):
        self.parent = [i for i in range(n)]
        self.rank = [1 for i in range(n)]
    
    def find(self,x):
        if self.parent[x] == x:
            return x
        else:
            return self.find(self.parent[x])
    
    def unite(self, x, y):
        px = self.find(x)
        py = self.find(y)
        if px == py:
            return
        else:
            if self.rank[px] == self.rank[py]:
                self.parent[py] = px
                self.rank[px] += 1
            elif self.rank[px] > self.rank[py]:
                self.parent[py] = px
            else:
                self.parent[px] = py
uftree = Union_Find(N+1)

for i in range(M):
    x, y, _ = map(int, input().split())
    uftree.unite(x, y)

result = 0
for i in range(1, N+1):
    if uftree.find(i) == i:
        result += 1

print(result)



Measured memory_bytes: 13792
main :: IO()
main = do
  n <- readLn
  checkNum n 1
  putStrLn ""

checkNum :: Int -> Int -> IO ()
checkNum n i
    | n < i = return ()
    | i `mod` 3  == 0
        = do putStr $  " " ++ show i
             checkNum n (i+1)
    | otherwise
        = do include3 n i i

include3 :: Int -> Int -> Int -> IO ()
include3 n i x
    | x == 0
      = do checkNum n (i+1)
    | x `mod` 10 == 3
      = do putStr $  " " ++ show i
           checkNum n (i+1)
    | otherwise
        = include3 n i (x `div` 10)

Measured memory_bytes: 4116
/*----------------by syr----------------*/
/*

         iii                  ii
     rBQBBBBBBE       BBR iBBBBQBBL     XBBBBBBQBBBBB
   iBBQJ    7BBB      BBsSBBr   BBQ      i      cBBB
  rBBU       iBBw     BBBQi     HBBi           KBBi
  BBH         BB5    iBBB       isL          wBB5
 GBB         iBBi    6BB                   iBBB
 BBQ         BQB     BBD                  QBBi
 BBB        BQB     iQBi                1BBv
 sBBg     wBBB      QBB               iBBB
  7BBBBBBBBBi       BBR              wBBBBBBBBBBBBB
     irvi           ii               ii    i i iii
                i5U
               BBB
               BB7
              1BB
      iPBBBBBKBBR    JBR1       rQBO   BR  UBQP  iBBQi
    7BBBGs7sXBBBi     QBBr     gBBE   rBB BB2BB7HBZQBB
   QBBi      sBQ       BBB   iBBB     SQBBR  BBBB  cBQ
  gBQ        BBg        BBB KBBi      MBBH   BBB   BBs
 iBBv       iBBi         QBBBL        BBR   pBB   iBB
 pBB        BBB         iBBBB        iBB    BBL   KBB
 MBB       BBBR        BBB JBBi      DBR   iBQ    BBL
 GBB     7BBBB2      PBBH   BBBi     BQr   DBB   iBB
  BQBXwgBBP BB7    1BBB      BBQ7   1BB    BBc   BBB
   2BBBBw   BB    EBBS        QBBi  HBa   iBB    BB7
*/
#include<bits/stdc++.h>

using namespace std;

#define PH push
#define MP make_pair
#define PB push_back
#define fst first
#define snd second
#define FOR(i, x, y) for(int i = (x); i < (y); ++i)
#define REP(i, x, y) for(int i = (x); i <= (y); ++i)
#define x0 x0123456789
#define y0 y0123456789
#define x1 x1234567890
#define y1 y1234567890
#define x2 x2345678901
#define y2 y2345678901
typedef double db;
typedef long long ll;
typedef long double ldb;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int INF = 1e9 + 7;
const int maxn = 1e5 + 5;

int n, m;
int a[maxn];
ll ans;

class SegmentTree{
private:
	int siz;
	ll fir[maxn << 2], dif[maxn << 2];
public:
	int size(){return siz;}
	void init(int _siz){
		for(siz = 1; siz < _siz; siz <<= 1);
		return;
	}
	void update(int x, int l, int r, int s, int t, int f, int d){
		if(s > t)
			return;
		if(l >= s && r <= t){
			fir[x] += f + 1ll * d * (l - s);
			dif[x] += d;
			return;
		}
		int md = l + r >> 1;
		if(s <= md)
			update(x << 1, l, md, s, t, f, d);
		if(t > md)
			update(x << 1 | 1, md + 1, r, s, t, f, d);
		return;
	}
	ll query(int x, int l, int r, int y){
		if(l == r)
			return fir[x];
		int md = l + r >> 1;
		if(y <= md)
			return query(x << 1, l, md, y) + fir[x] + dif[x] * (y - l);
		else
			return query(x << 1 | 1, md + 1, r, y) + fir[x] + dif[x] * (y - l);
	}
}seg;

int main(){
	scanf("%d%d", &n, &m);
	seg.init(m + 1);
	FOR(i, 0, n)
		scanf("%d", a + i);
	FOR(i, 1, n){
		int x = a[i - 1], y = a[i];
		if(y >= x){
			seg.update(1, 0, seg.size() - 1, x + 1, y, 0, 1);
		}
		else{
			seg.update(1, 0, seg.size() - 1, x + 1, m, 0, 1);
			seg.update(1, 0, seg.size() - 1, 1, y, m - x, 1);
		}
	}
	REP(i, 1, m){
		ans = max(ans, seg.query(1, 0, seg.size() - 1, i));
	}
	ans = - ans;
	FOR(i, 1, n){
		if(a[i - 1] <= a[i])
			ans += a[i] - a[i - 1];
		else
			ans += m - a[i - 1] + a[i];
	}
	printf("%lld\n", ans);
	return 0;
}

Measured memory_bytes: 6272
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main(int argc, char *argv[]) {
  ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
  int x,a,b;cin>>x>>a>>b;
  if(abs(x-a)<abs(x-b)){
    cout<<"A"<<endl;
  }else{
    cout<<"B"<<endl;
  }

  return 0;
}


Measured memory_bytes: 256
N,C,K = gets.chomp.split(" ").map(&:to_i)
t = N.times.map{gets.to_i}
t = t.sort
num = 0
ans = 0
while num <= N-1
  time = t[num] + K
  cnt = 0
  while cnt < C && num+cnt <= N-1
    if t[num+cnt] <= time
      cnt += 1
    else
      break
    end
  end
  num += cnt
  ans += 1
end
puts ans

Measured memory_bytes: 16888
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <algorithm>
#include <cctype>
#include <cmath>
#include <queue>
#include <map>
#include <numeric>
#include <unordered_map>
#include <iomanip>
#include <functional>
#include <bitset>
#include <complex>

#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)
#define repi(i,a,b) for(ll i=ll(a);i<ll(b);i++)
#define all(x) (x).begin(),(x).end()

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

typedef long long ll;

using namespace std;
ll n;
ll sa=0,sa2=0;
ll f(ll x)
{
  return (ll)n*x*x-2*sa*x+sa2;
}
int  main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin>>n;
  rep(i,n)
  {
    ll a;
    cin>>a;
    sa+=a;
    sa2+=a*a;
  }
  if(sa%n==0)
  {
    cout<<f(sa/n)<<endl;
    return 0;
  }
  ll x=sa/n;
  if(f(x)>f(x+1))x++;
  cout<<f(x)<<endl;
  return 0;

}


Measured memory_bytes: 256
#include<cstdio>
#include<algorithm>
int n,m,a[200050],ret,ans;
int pd(int mid){
	ret=0;
	for (int i=mid*2;i>mid;i--)if (a[i]+a[mid*2-i+1]>=m)return 0;
	else ret=std::max(ret,a[i]+a[mid*2-i+1]);
	int k=n-mid;
	for (int i=mid*2+1+k;i<=n*2;i++)if (a[i]+a[n*2-i+1+mid*2]<m)return -1;
	else ret=std::max(ret,a[i]+a[n*2-i+1+mid*2]-m);
	return 1;
} 
int main(){
	scanf("%d%d",&n,&m);
	for (int i=2*n;i>=1;i--)scanf("%d",&a[i]);
	std::sort(a+1,a+n*2+1);
	int l=0,r=n;
	while (l<=r){
		int mid=(l+r)>>1;int t=pd(mid);
		if (t==1)ans=mid,r=mid-1;
		else if (!t)r=mid-1;
		else l=mid+1;
	}
	pd(ans);printf("%d\n",ret);
} 

Measured memory_bytes: 896
//・グラフに変換する
//・候補を絞る
#include <iostream>
#include <algorithm>
#include <vector>
#include <tuple>
using namespace std;
typedef pair<int, int> P;
typedef tuple<int, int, int> T;

int n;
P px[100000], py[100000];
vector<T> edges;
struct UF {
	int par[100000];
	UF() { for (int i = 0; i < 100000; i++) par[i] = i; }
	int root(int x) { if (par[x] == x) return x; return par[x] = root(par[x]); }
	void marge(int x, int y) { x = root(x); y = root(y); par[x] = y; }
	bool same(int x, int y) { return root(x) == root(y); }
}uf;

int main() {
	int i;
	
	cin >> n;
	for (i = 0; i < n; i++) {
		int x, y;
		cin >> x >> y;
		px[i] = P(x, i);
		py[i] = P(y, i);
	}
	sort(px, px + n);
	sort(py, py + n);
	
	for (i = 0; i < n - 1; i++) {
		edges.push_back(T(px[i + 1].first - px[i].first, px[i].second, px[i + 1].second));
		edges.push_back(T(py[i + 1].first - py[i].first, py[i].second, py[i + 1].second));
	}
	
	sort(edges.begin(), edges.end());
	int ans = 0;
	for (i = 0; i < edges.size(); i++) {
		int u = get<1>(edges[i]);
		int v = get<2>(edges[i]);
		if (uf.same(u, v)) continue;
		uf.marge(u, v);
		ans += get<0>(edges[i]);
	}
	cout << ans << endl;
	return 0;
}

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

using namespace std;
int main() {
  int a, b;
  cin >> a >> b;
  string s;
  cin >> s;
  if (s.length() != a + b + 1) {
    cout << "No" << endl;
    return 0;
  }
  int haihun = 0;
  for (int i = 0; i < s.length(); i++) {
    if (s[i] == '-')
      haihun++;
    else if (s[i] < '0' || '9' < s[i]) {
      cout << "No" << endl;
      return 0;
    }
  }

  if (s[a] != '-' || haihun != 1) {
    cout << "No" << endl;
    return 0;
  }
  cout << "Yes" << endl;
  return 0;
}

Measured memory_bytes: 256
import std.stdio, std.algorithm, std.conv, std.array, std.string, std.math, std.typecons, std.numeric;

void main()
{
    auto N = readln.chomp.to!int;
    auto as = readln.split.to!(int[]);

    long[][] DP;
    DP.length = N;
    foreach (ref dp; DP) dp.length = N;

    auto x = (N-1)%2;
    long solve(int i, int j) {
        if (i > j) return 0;
        if (DP[i][j]) return DP[i][j];

        if ((i+j)%2 == x) {
            return DP[i][j] = max(solve(i+1, j) + as[i], solve(i, j-1) + as[j]);
        } else {
            return DP[i][j] = min(solve(i+1, j) - as[i], solve(i, j-1) - as[j]);
        }
    }

    writeln(solve(0, N-1));
}

Measured memory_bytes: 74492
#include <vector>
#include <stack>
#include <queue>
#include <list>
#include <bitset>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <numeric>
#include <iostream>
#include <iomanip>
#include <string>
#include <chrono>
#include <random>
#include <cmath>
#include <cassert>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <functional>
#include <sstream>

using namespace std;


int main(int argc, char** argv) {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cout << fixed << setprecision(16);

    int n, k;
    cin >> n >> k;
    long double res = 0;
    long double p = 1;
    long long x = 1;
    for (int i = n, j = 0; i >= 1; --i) {
        if (i < k) {
            while (i * x < k) {
                x <<= 1;
                p /= 2;
            }
            res += p;
        } else {
            res += 1;
        }
    }
    res /= n;
    cout << res << "\n";

    return 0;
}

Measured memory_bytes: 256