akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
char s[200005];
ll a[200005];
ll mod[200005];
ll modrev[200005];
ll mod2[200005];
ll mod2rev[200005];
map<ll,ll> m;
int main(void)
{
	ll n,p;
	scanf("%lld%lld",&n,&p);
	scanf(" %s",s);
	for(ll i=0;i<n;i++)
	{
		a[n-i]=s[i]-'0';
	}
	mod[1]=1;
	for(ll i=2;i<=n;i++)
	{
		mod[i]=mod[i-1]*10%p;
	}
	mod2[1]=a[1]%p;
	for(ll i=2;i<=n;i++)
	{
		mod2[i]=(mod[i]*a[i]+mod2[i-1])%p;
	}
	if(p==2)
	{
		ll sum=0;
		for(ll i=1;i<=n;i++)
		{
			if(a[i]%2==0)
			{
				sum+=n-i+1;
			}
		}
		printf("%lld",sum);
	}
	else if(p==5)
	{
		ll sum=0;
		for(ll i=1;i<=n;i++)
		{
			if(a[i]==0||a[i]==5)
			{
				sum+=n-i+1;
			}
		}
		printf("%lld",sum);
	}
	else
	{
		for(ll i=1;i<=n;i++)
		{
			m[mod2[i]]++;
		}
		ll sum=0;
		map<ll,ll>::iterator ite;
		for(ite=m.begin();ite!=m.end();ite++)
		{
			ll num=ite->second;
			if(ite->first==0)
			{
				sum+=(num+1)*num/2;
			}
			else
			{
				sum+=(num-1)*num/2;
			}
		}
		printf("%lld",sum);
	}
}

Measured memory_bytes: 7296
#include <iostream>
#include <vector>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <iomanip>
#include <map>
#include <set>
#include <string>
#include <queue>

using namespace std;
typedef long long ll;
typedef long double ld;

int main()
{
	ll k;
	string s;
	cin >> s;
	cin >> k;
	for (char i : s)
	{
		if (i == '1')
			k--;
		else
		{
			cout << i;
			return 0;
		}
		if (k == 0)
		{
			cout << 1;
			return 0;
		}
	}
	return 0;
}


Measured memory_bytes: 256
while true
  a = gets
  break if a == nil
  n = a.to_i
y = 0
if n <= 36
    for a in 0..9 do
        if n <= a
            y += 1
            ;break
        end
        for b in 0..9 do
            if n <= a + b
                y += 1
                ;break
            end
           for c in 0..9 do
               if n <= a + b + c
                   y += 1
                   ;break
               end
              for d in 0..9 do
                  i = a + b + c + d
                  if n == i
                      y += 1
                  end
              end
           end
        end
    end
end
puts y
end



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

using namespace std;
int n,l,res=0,res1=0;
int main()
{
    //freopen("B.in","r",stdin);
    ios_base::sync_with_stdio(false);cin.tie(NULL);
    cin >> n >> l;
    for (int i=1;i<=n;i++) res1+=l+i-1;
    if (l>=0) for (int i=2;i<=n;i++) res+=l+i-1;
    else for (int i=1;i<=n;i++)
    {
        if (l+i-1==0)
        {
            cout << res1;
            return 0;
        }
        if (i<n) res+=l+i-1;
    }
    cout << res;
}


Measured memory_bytes: 256
N, Y = map(int, input().split())
res = []
for x in range(N + 1):
    for y in range(N + 1 - x):
        if N - x - y >= 0 and 10000*x + 5000*y + 1000*(N - x - y) == Y:
            res.append((x, y, N - x - y))
if res :
    print(res[0][0], res[0][1], res[0][2])
else:
    print(-1, -1, -1)

Measured memory_bytes: 3188
import java.util.Scanner;
public class Main{
    public static void main(String[]args){
        Scanner scan = new Scanner(System.in);
        int a,b;
        a=scan.nextInt();
        b=scan.nextInt();
        System.out.println(Math.max(Math.max(a+b, a-b),a*b));
    }
}

Measured memory_bytes: 23252
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    
    int n;
    string a,b;
    cin>>n;
    cin>>a>>b;
    for(int i=0;i<n;i++)
        cout<<a[i]<<b[i];
    
    return 0;
}


Measured memory_bytes: 256
import java.util.HashSet;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String g = sc.next();
        System.out.println(cal(g));
    }

    private static int cal(final String g) {
        char[] ch =
                g.toCharArray();
        int n = 0;
        for (char c : ch) {
            if (c == 'g') {
                n ++;
            } else {
                n --;
            }
        }
        return n <= 0 ? 0 : n/2;
    }
}


Measured memory_bytes: 14124
import java.util.*

fun main(args: Array<String>){
    val m = 1000000007
	val cin = Scanner(System.`in`)
    val n = cin.nextLong()
    val k = cin.nextInt()

    var ans : Long = 0
    
    for (i in k..n+1) {
        val j = i.toLong()
        val min = j*(j-1)/2
        val max = j * (2*n - j + 1) / 2
        ans += (max - min + 1)
        ans = ans % m
    }
    println(ans)
}

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

using namespace std;

int n,W;
int w[110],v[110];
long long f[100010];
int main(){
	scanf("%d%d",&n,&W);
	for(int i=1;i<=n;i++){
		scanf("%d%d",w+i,v+i);
	}
	for(int i=1;i<=n*1000;i++)
		f[i]=(long long)(1e9)*(long long)100LL;
	for(int i=1;i<=n;i++){
		for(int j=n*1000;j>=v[i];j--)
			f[j]=min(f[j],f[j-v[i]]+w[i]);
	}
	for(int i=n*1000;i>=0;i--){
		if(f[i]<=W){
			printf("%d\n",i);
			break;
		}
	}
	return 0;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
int main(){
  string s, t;
  cin >>s>>t;
  bool ans = true;
  if(t.size()-s.size() != 1) ans = false;
  t.pop_back();
  if(t != s) ans = false;
  if(ans) puts("Yes");
  else puts("No");
}

Measured memory_bytes: 3600
#include<iostream>
#include<string>
#include<algorithm>


using namespace std;

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

	if (C>=A && C<=B) {
			cout << "Yes" << endl;

		}
		else {
			cout << "No" << endl;
		}
	
	return 0;
}


Measured memory_bytes: 256
import Control.Applicative ((<$>))
import Control.Monad (unless, foldM)

import Data.IntMap (IntMap)
import qualified Data.IntMap as IM

main :: IO ()
main = do
  n <- readLn
  unless (n == 0) $ do
    solve n >>= putStrLn
    main

solve :: Int -> IO String
solve n = do
  im <- foldM (\im _ -> do
                  [m, a, b] <- map read <$> words <$> getLine
                  let tm = IM.insertWith (+) a m im
                  return $ IM.insertWith (+) b (-m) tm
                  ) IM.empty [1..n]
  return . maybe "NG" (const "OK") . IM.foldl f (Just 0) $ im
  where f a b = do
          x <- a
          if x + b > 150 then Nothing else return (x + b)



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

#include <stdio.h>

#define rep(i, n) for (int i = 0; i < (n); i++)
#define pb push_back
#define vec vector
#define ref(a) &(a)

typedef long long ll;

using namespace std;

int n, d;
vec<vec<int> > v;

int solve() {
  int res = 0;
  rep(i, n) for (int j = i+1; j < n; j++) {
    double s = 0;
    vec<int> x = v[i];
    vec<int> y = v[j];
    rep(k, d) {
      s += pow(x[k] - y[k], 2);
    }
    s = sqrt(s);
    if (s - floor(s) == 0.f)
      res++;
  }
  return res;
}

int main() {
  cin >> n >> d;
  rep(i, n) {
    vec<int> x;
    rep(j, d) {
      int y; cin >> y;
      x.pb(y);
    }
    v.pb(x);
  }
  cout << solve() << endl;
  return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <bits/stdc++.h>
#define rep(i,n) for(ll i=0, i##_len=(n); i<i##_len; ++i)
#define REP(i,num,n) for(ll i=num, i##_len=(n); i<i##_len; ++i)
#define all(x) (x).begin(),(x).end()
#define len(x) ((ll)(x).size())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
#define MEMSET(v, h) memset((v), h, sizeof(v))
#define y0 y3487465
#define y1 y8687969
#define j0 j1347829
#define j1 j234892
typedef long long ll;
ll INF = 1e18;
using namespace std;

int main(){
  cout<<fixed<<setprecision(10);

  ll N;
  cin >> N;

  vector<ll> L(N);
  rep(i,N) cin >> L[i];
  sort(L.begin(),L.end());

  
  ll ans = 0;

  for(ll i=0;i<N-1;++i){
    ll a = L[i];
    for(ll j=i+1; j<N; ++j){
      ll b = L[j];
      ll t1 = upper_bound(L.begin(),L.end(),a+b-1)-L.begin();
      ll t2 = upper_bound(L.begin(),L.end(),a-b)-L.begin();
      ll t3 = upper_bound(L.begin(),L.end(),b-a)-L.begin();
      
      ll t4 = max(t2,t3);
      
      if (t1!=t4)
          ans += t1-t4;
          
      if (t4<=i and i<=t1)
          ans -= 1;
      if (t4<=j and j<=t1)
          ans -= 1;
      
    }
  }
  
  ans = ans/3;
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main(void){
    // Your code here!
    int n, x, sum = 0, sma;
    cin >> n >> x;
    for (int i = 0; i < n; i++) {
        int m;
        cin >> m;
        sum += m;
        if (i == 0) sma = m;
        else sma = min(sma, m);
    }
    cout << n + (x - sum) / sma << endl;
}


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

#define lli long long int
#define REP(i,s,l) for(lli i=s;i<l;i++)
#define DEBUG 0
#define INF (1LL<<50)
#define MOD 1000000007

int main(){
    int a, b;
    cin >> a >> b;

    cout << (a-1)*(b-1) << endl;
    return 0;
}

Measured memory_bytes: 256
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())


s = str(input())

ans = []
for i in range(len(s)):
    if s[i] == "0":
        ans.append("0")
    elif s[i] == "1":
        ans.append("1")
    else:
        if len(ans) > 0:
            ans.pop(-1)

print("".join(ans))


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

class disjoinset {
	public:
		vector<int> rank,p,w;
	disjoinset (){}
	disjoinset(int size){
	rank.resize(size,0);
	p.resize(size,0);
	w.resize(size,0);
	for(int i=0; i<size;i++)makeSet(i);
	}
	void makeSet(int x){
	p[x] = x;
	rank[x] =0;
	w[x] = 0;
	}
	bool same(int x,int y){
	return findSet(x) == findSet(y);
	}
	void unite(int x,int y,int cost){
		int px = findSet(x);
		int py = findSet(y);
		link(px,py,cost-w[x]+w[y]);
	}
	void link(int x,int y,int cost){
		if(rank[x] > rank[y]){
		 p[y] = x;
		 w[y] = -cost;
		}else{
		 p[x] = y;
		 w[x] = cost;
		 if(rank[x]==rank[y] )rank[y]++;
		}
	}

	int rsum(int x){
		int sum = 0;
		int now = x;
		while(now!=p[now]){
			sum+=w[now];
			now=p[now];
		}
		return sum;
	}
	int findSet(int x){
		if(x!=p[x]){
		int tmp = findSet(p[x]);
		w[x]+=w[p[x]];
		p[x] = tmp;
		}
		return p[x];
	}

};
 
int main(){
	int n,a,b,c,q;
	int t;
	cin>>n>>q;
	disjoinset ds  = disjoinset(n);
	for(int i=0;i<q;i++){
		cin>>t;
		if(t==0){
		cin>>a>>b>>c;
		 ds.unite(a,b,c);
		}else if(t==1){
		cin>>a>>b;
		if(!ds.same(a,b) ) cout<<'?'<<endl;
		else {
			//cout<<ds.rsum(a)<<' '<<ds.rsum(b)<<endl;
			cout<<ds.rsum(a)-ds.rsum(b)<<endl;
			}
		}
	}

	return 0;
}



Measured memory_bytes: 3888
#include<bits/stdc++.h>
typedef long long int ll;
using namespace std;
#define endl '\n'
int main(){
    ios_base::sync_with_stdio(false),cin.tie(NULL);
    ll k,n;
    cin>>k>>n;
    ll a[n];
    ll maxi=0;
    for(ll i=0;i<n;i++){
            cin>>a[i];
            if(i)maxi=max(maxi,a[i]-a[i-1]);
    }
    maxi=max(maxi,k-a[n-1]+a[0]);
    k-=maxi;
    cout<<k<<endl;


return 0;
}


Measured memory_bytes: 1920
///In the name of GOD
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll MXN = 2e5 + 10;
ll n, ans, now;
ll A[MXN], cnt[MXN];
int main(){
    ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
    cin >> n;
    for(int i = 1; i <= n; i ++){
        cin >> A[i];
        cnt[A[i]] ++;
    }
    for(int i = 1; i < MXN; i ++){
        if(cnt[i] >= 2){
            ans += (cnt[i] * (cnt[i] - 1)) / 2;
        }
    }
    for(int i = 1; i <= n; i ++){
        now = cnt[A[i]] - 1;
        cout << ans - now << '\n';
    }
    return 0;
}
/*!
    Be careful who you share your weaknesses with.
    Some people can't wait for the opportunity to use them against you!!
*/
//! N.N


Measured memory_bytes: 4736
#include <bits/stdc++.h>
using namespace std;
#include <atcoder/all>
using namespace atcoder;
#define rep(i,n) for (long long i = 0; i < (n); ++i)
using ll = long long;
using P = pair<ll,ll>;
using vec = vector<ll>;
using vecp = vector<P>;
using mat = vector<vec>;
using matp = vector<vecp>;
const ll MOD = 1e9+7;
const ll INF = 1e18;
#define all(v) v.begin(), v.end()

vector<ll> par(1e6);
vector<ll> ran(1e6);
vector<ll> siz(1e6);
void init(ll n){
  rep(i,n){
    par.at(i)=i;
    ran.at(i)=0;
    siz.at(i)=1;
  }
}
ll find(ll x){
  if(par.at(x)==x){
    return x;
  }else{
    return par.at(x)=find(par.at(x));
  }
}
void unite(ll x,ll y){
  x=find(x);
  y=find(y);
  if(x==y) return;
  if(ran.at(x)<ran.at(y)){
    siz.at(y)+=siz.at(x);
    par.at(x)=y;
  }else{
    siz.at(x)+=siz.at(y);
    par.at(y)=x;
    if(ran.at(x)==ran.at(y)) ran.at(x)++;
  }
}

int main(){
  ll N,M,ans;
  cin >> N >> M;
  ans=N-1;
  init(N);
  rep(i,M){
    ll a,b;
    cin >> a >> b;
    a--;
    b--;
    if(find(a)!=find(b)){
      ans--;
      unite(a,b);
    }
  }
  cout << ans << endl;
    
}

Measured memory_bytes: 26596
w = gets.to_i
n = gets.to_i

ans = (1..w).map(&:to_i)

(1..n).each{|i|
    a,b = gets.split(",").map{|num| num.to_i - 1 }
    ans[a],ans[b] = ans[b],ans[a]
}

puts ans.join("\n")

Measured memory_bytes: 6100
#include <iostream>
#include <iomanip>
#include <string>
#include <stack>
#include <vector>
#include <complex>
#include <math.h>
#include <stdio.h>
#include <algorithm>
#include <utility>
#include <functional>
#include <iterator>
#include <map>
#include <set>
#include <queue>
#include <list>
#include <regex>
#include <limits>
#include <time.h>
#include <cstdint>
using namespace std;
using pii  = pair<int,int>;
using ll=long long;
using ld=long double;
#define pb push_back
#define mp make_pair
#define sc second
#define fr first
#define stpr setprecision
#define cYES cout<<"YES"<<endl
#define cNO cout<<"NO"<<endl
#define cYes cout<<"Yes"<<endl
#define cNo cout<<"No"<<endl
#define rep(i,n) for(ll i=0;i<(n);++i)
#define Rep(i,a,b) for(ll i=(a);i<(b);++i)
#define rrep(i,n) for(ll i=n-1;i>=0;i--)
#define rRep(i,a,b) for(ll i=a;i>=b;i--)
#define crep(i) for(char i='a';i<='z';++i)
#define psortsecond(A,N) sort(A,A+N,[](const pii &a, const pii &b){return a.second<b.second;});
#define ALL(x) (x).begin(),(x).end()
#define debug(v) cout<<#v<<":";for(auto x:v){cout<<x<<' ';}cout<<endl;
#define endl '\n'
int ctoi(const char c){
  if('0' <= c && c <= '9') return (c-'0');
  return -1;
}
ll gcd(ll a,ll b){return (b == 0 ? a : gcd(b, a%b));}
ll lcm(ll a,ll b){return a*b/gcd(a,b);}
constexpr ll MOD=1000000007;
constexpr ll INF=1000000011;
constexpr ll MOD2=998244353;
constexpr ll LINF = 1001002003004005006ll;
constexpr ld EPS=10e-8;
template <class T, class U> inline bool chmax(T& lhs, const U& rhs) { if (lhs < rhs) { lhs = rhs; return 1; } return 0; }
template <class T, class U> inline bool chmin(T& lhs, const U& rhs) { if (lhs > rhs) { lhs = rhs; return 1; } return 0; }
template<typename T> istream& operator>>(istream& is,vector<T>& v){for(auto&& x:v)is >> x;return is;}
template<typename T,typename U> istream& operator>>(istream& is, pair<T,U>& p){ is >> p.first; is >> p.second; return is;}
template<typename T,typename U> ostream& operator>>(ostream& os, const pair<T,U>& p){ os << p.first << ' ' << p.second; return os;}
template<class T> ostream& operator<<(ostream& os, vector<T>& v){
  for(auto i=begin(v); i != end(v); ++i){
    if(i !=begin(v)) os << ' ';
    os << *i;
  }
  return os;
}

vector<ll> V; 

int main(){
  ll N;
  cin >> N;
  while(N>0){
    ll X=N%26;
    if(X==0){
      X=26;
      V.pb(X);
      if(N==26){
        break;
      }
    }
    else{
      V.pb(X);
    }
    N--;
    N/=26;
  }
  reverse(ALL(V));
  rep(i,V.size()){
    char X='a'-1+V[i];
    cout << X ;
  }
  cout << endl;
}


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

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

long long MOD = 1000000000 + 7;

int main(){
  cout << setprecision(10);
  ll K;
  cin >> K;
  queue<ll> q;
  for(int i = 1; i <= 9; i++) q.push(i);

  ll num = 0;
  ll ans;
  ll now;
  while(true){
    now = q.front();
    q.pop();

    num++;
    if(num == K){
      ans = now;
      break;
    }

    if(now%10 == 0){
      q.push(now*10 + 0);
      q.push(now*10 + now%10 + 1);
    } else if(now %10 == 9){
      q.push(now*10 + now%10 - 1);
      q.push(now*10 + now%10);
    } else { 
      q.push(now*10 + now%10 - 1);
      q.push(now*10 + now%10);
      q.push(now*10 + now%10 + 1 );
    }
  }
  cout << ans << endl;

}


Measured memory_bytes: 1792
#include "iostream"
#include "climits"
#include "list"
#include "queue"
#include "stack"
#include "set"
#include "functional"
#include "algorithm"
#include "string"
#include "map"
#include "unordered_map"
#include "unordered_set"
#include "iomanip"
#include "cmath"
#include "random"
#include "bitset"
#include "cstdio"
#include "numeric"
#include "cassert"

using namespace std;

const long long int MOD = 1000000007;
//const int MOD = 998244353;
//const long long int MOD = 998244353;
const double EPS = 1e-8;

//int N, M, K, H, W, L, R;
long long int N, M, K, H, W, L, R;


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

	string s;
	cin >> s;
	if (s[0] == s[1] || s[1] == s[2] || s[2] == s[3])cout << "Bad\n";
	else cout << "Good\n";
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<iomanip>
#include<cmath>
#include<vector>
#include<algorithm>
#include<utility>
#include<queue>

using namespace std;

#define int long long
#define endl "\n"

constexpr long long INF = (long long)1e18;
constexpr long long MOD = 1'000'000'007; 

struct fast_io {
	fast_io(){
		std::cin.tie(nullptr);
		std::ios::sync_with_stdio(false);
	};
} fio;

void dijkstra(int s, vector<int> &d, vector<vector<pair<int,int>>> &G){
	priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> q;
	
	d.clear();
	d.resize(G.size(),INF);
	d[s] = 0;
	q.push(make_pair(0,s));
	
	while(!q.empty()){
		pair<int,int> p = q.top();q.pop();
		int v = p.second;
		
		if(d[v] < p.first) continue;
		
		for(pair<int,int> e : G[v]){
			if(d[e.first] > d[v] + e.second){
				d[e.first] = d[v] + e.second;
				q.push(make_pair(d[e.first],e.first));
			}
		}
	}	
}


signed main(){
	cout<<fixed<<setprecision(10);
	
	int N, M;
	vector<int> d;
	vector<int> ans;
	vector<vector<pair<int,int>>> G;
	vector<vector<pair<int,int>>> G2;
	
	cin>>N>>M;
	
	G.resize(N);
	// G2.resize(N);
	ans.resize(N);
	
	// edge.resize(M);
	
	for(int i = 0; i < M; i++){
		int A, B;
		
		cin>>A>>B;
		
		A--, B--;
		
		G[A].push_back({B,1});
		G[B].push_back({A,1});
		
		// G2[A].push_back({B,i});
		// G2[B].push_back({A,i});
		
		// edge[i] = {A, B};
	}
	
	dijkstra(0, d, G);
	
	for(int i = 1; i < N; i++){
		for(pair<int,int> p : G[i]){
			if(d[i]-1 == d[p.first]) {
				ans[i] = p.first;
				break;
			}
		}
	}
	
	cout<<"Yes"<<endl;
	
	for(int i = 1; i < N; i++){
		cout<<ans[i]+1<<endl;
	}
	
	
	return 0;
}

Measured memory_bytes: 19048
#include <iostream>
#include<sstream>
#include<vector>
#include<iterator>
using namespace std;

int main(void)
{
	string S;
	cin >> S;

	string s;
	s.push_back(S[0]);

	for(int i=1; i<S.size(); i++)
		if(S[i] != s.back())
			s.push_back(S[i]);

	int ret = s.size() - 1;

	cout << ret << endl;

	return 0;
}


Measured memory_bytes: 640
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>
#include <stdbool.h>
#include <tgmath.h>
#include <time.h>
#define ll long long
#define min(a, b) ((a) > (b) ? (b) : (a))
#define max(a, b) ((a) > (b) ? (a) : (b))
#define miin(a, b, c) min((a), min((b), (c)))
#define maax(a, b, c) max((a), max((b), (c)))
int n;
ll sum = 0;

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        if (i % 3 * i % 5)
        {
            sum += i;
        }
    }
    printf("%lld\n", sum);
    return 0;
}

Measured memory_bytes: 1732
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<queue>
#include<map>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
using namespace std;

char a,b;
 
int main(){
  ios_base::sync_with_stdio(false);

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

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define MOD 1000000007
using namespace std;
typedef long long LL;

LL powmod(LL a, int n){
	if(n == 0) return 1;
	if(n % 2 == 1) return (a*powmod(a,n-1)) % MOD;
	LL c = powmod(a,n/2);
	return (c*c) % MOD;
}

LL inv(LL a){
	return powmod(a,MOD-2);
}

int par[220000];
int __rank[220000];
int sz[220000];
int find(int a){
	if(a != par[a]) par[a] = find(par[a]);
	return par[a];
}
void join(int a, int b){
	int pa = find(a);
	int pb = find(b);
	if(pa == pb) return;
	if(__rank[pa] < __rank[pb]){
		par[pa] = pb;
		sz[pb] += sz[pa];
	} else if(__rank[pb] < __rank[pa]){
		par[pb] = pa;
		sz[pa] += sz[pb];
	} else {
		par[pb] = pa;
		sz[pa] += sz[pb];
		__rank[pa]++;
	}
}


int n, x, y;
int c[220000];
int w[220000];
vector<int> id[220000]; // list of balls of color
vector<int> wgt[220000]; // list of balls of color
int m[220000]; //min wgt id of color

vector<pair<int,int> > f;
LL ans = 1;

LL cnt[220000];
int main(){
	cin >> n >> x >> y;
	for(int i = 0; i < 220000; i++){
		m[i] = -1;
		cnt[i] = 0;
	}
	for(int i = 0; i < n; i++){
		par[i] = i;
		sz[i] = 0;
		__rank[i] = 0;

		cin >> c[i] >> w[i];
		c[i]--;
		id[c[i]].push_back(i);
		wgt[c[i]].push_back(w[i]);
	}
	for(int i = 0; i < n; i++){
		if(m[c[i]] == -1 || w[m[c[i]]] > w[i]){
			m[c[i]] = i;
		}
	}
	for(int i = 0; i < 220000; i++){
		if(m[i] != -1){
			f.push_back(make_pair(w[m[i]], m[i]));
		}
	}
	sort(f.begin(), f.end());

	for(int i = 0; i < n; i++){
		if(w[m[c[i]]] + w[i] <= x){
			join(i,m[c[i]]);
		}
		for(int j = 0; j < f.size(); j++){
			if(j >= 4) break;
			if(c[f[j].second] != c[i]){
				if(w[m[c[f[j].second]]] + w[i] <= y){
					join(m[c[f[j].second]], i);
				}
			}
		}
	}
	for(int i = 0; i < n; i++){
		find(i);
		//cout << par[i] << " " << c[i] << endl;
	}
	for(int i = 0; i < 220000; i++){
		for(int j = 0; j < id[i].size(); j++){
			cnt[par[id[i][j]]]++;
			ans *= inv(cnt[par[id[i][j]]]);
			ans %= MOD;
		}
		for(int j = 0; j < id[i].size(); j++){
			cnt[par[id[i][j]]]--;
		}
	}
	for(int i = 0; i < n; i++){
		cnt[par[i]]++;
		ans *= (LL)cnt[par[i]];
		ans %= MOD;
	}
	cout << ans % MOD << endl;
}

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

int main() {
	int n; cin >> n;
	tuple<double, double, double> t[2 * n];
	for(int i = 0; i < n; ++i) {
		double x, y; cin >> x >> y;
		double arg = atan2(y, x);
		t[i] = t[i + n] = make_tuple(arg, x, y);
	}
	sort(t, t + n);
	sort(t + n, t + 2 * n);
	// for(int i = 0; i < 2 * n; ++i) {
	// 	double _arg, x, y;
	// 	tie(_arg, x, y) = t[i];
	// 	cerr << _arg << " " << x << " " << y << endl;		
	// }
	double ans = 0;
	for(int l = 0; l < n; ++l) {
		for(int r = l; r <= 2 * n; ++r) {
			if(r - l > n) continue;
			double xsum = 0, ysum = 0;
			for(int i = l; i < r; ++i) {
				double _arg, x, y;
				tie(_arg, x, y) = t[i];
				xsum += x;
				ysum += y;
			}
			ans = max(ans, xsum * xsum + ysum * ysum);
		}
	}
	printf("%.15f\n", sqrt(ans));
	return 0;
}

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

using namespace std;

typedef long long ll;

int main()
{
    int n;

    string s;
    cin>>n>>s;
    int c1=0,c2=0,sum,m;
    int t=s.length();
    for(int i=0;i<t;i++)
    {
        if(s[i]=='W') c1++;
        else c2++;
    }
    m=10000000;
    int b1=0,b2=0;
    if(s[0]=='W') m=c2;
    else m=c2-1;
    for(int i=1;i<t;i++)
    {
        sum=0;
        if(s[i-1]=='W') b1++;
        else b2++;

        sum+=b1;//left W
        sum+=c2-b2; //right E
        if(s[i]=='E')
        {
            sum--;
        }

        if(m>sum)
            m=sum;
    }
    cout<<m<<endl;


    return 0;
}


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

const ll MAXN = 200000;

ll N, K, ans=0, tmp=0, tmp2=0, pre=1;
vector<ll> A, B;
string S;

signed main(){
    cin >> N >> K >> S;
    for(int i=0;i<N;i++) {
        if(pre==S[i]-'0') {
            tmp++;
        }
        else {
            A.push_back(tmp);
            pre = 1-pre;
            tmp=1;
        }
    }
    A.push_back(tmp);
    if(pre==0) A.push_back(0);
    /*
    for(int i=0;i<A.size();i+=2) {
        //cout << A[i] << endl;
        ans = max(ans, A[i]);
    }
    */
    for(int i=1;i<A.size();i++) {
        A[i] = A[i] + A[i-1];
    }
    for(int i=2*K;i<A.size();i+=2) {
        if(i==2*K) ans = max(ans, A[i]);
        else ans = max(ans, A[i]-A[i-2*K-1]);
    }
    if(2*K>=A.size()) ans = A.back();
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 1528
#include<bits/stdc++.h>
#define rep(a,b,c) for(int a=b;a<=c;a++)
#define per(a,b,c) for(int a=b;a>=c;a--)
#define ios; ios::sync_with_stdio(false); cin.tie(0);
#define pb push_back
#define mk make_pair
#define fi first
#define se second
#define mem(a,b) memset(a,b,sizeof(a))
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define ls(x) (x<<1)
#define rs(x) (ls(x)|1)
#define eps 1e-11
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
typedef vector<int> VI;
typedef double db;
mt19937 rnd(random_device{}());
const int mod = 1e9 + 7;
const int N = 5;
const int M = 1e3 + 5;
inline ll gcd(ll a,ll b){ return b?gcd(b,a%b):a; }
inline ll lcm(ll a,ll b){ return a*b/gcd(a,b); }
inline ll ksm(ll x,ll y){ ll res=1; while(y){if(y&1) res=res*x%mod;
x=x*x%mod; y>>=1;} return res; }
int n,m;

int main(){
    ios;
    cin>>n>>m;
    cout<<n*m;
    return 0;
}

Measured memory_bytes: 3652
#include<iostream>
#include<string>
#include<algorithm>
#include <string.h>
#include <stdio.h>
#include <math.h>
#include <set>
#include <queue>
#include <stack>
#include <map>


using namespace std;
#define lson l , m , rt << 1
#define rson m + 1 , r , rt << 1 | 1
typedef int status;
typedef long long ll;
typedef unsigned long long ull;
const ull base = 343;
const int INF = int(1e9);
const ll INF1 = ll(1e18);
const int MAX = 1000002;

int N;
int a[MAX];
int b[MAX];

int main()
{
    ios_base::sync_with_stdio(0);
    cin>>N;
    int max1 = -1;

    for(int i = 1;i <= N;i++)cin>>a[i];
    for(int i = 1;i <= N;i++){
        b[a[i]] = b[a[i]-1]+1;
        max1 = max(max1,b[a[i]]);
    }
    cout<<N - max1<<endl;


    return 0;
}


Measured memory_bytes: 5120
using System;
using System.Collections.Generic;
using System.Linq;

class F
{
	static void Main()
	{
		var n = int.Parse(Console.ReadLine());
		var m = n - 1;
		map = new int[n + 1].Select(_ => new List<int>()).ToArray();
		foreach (var r in new int[m].Select(_ => Console.ReadLine().Split().Select(int.Parse).ToArray()))
		{
			map[r[0]].Add(r[1]);
			map[r[1]].Add(r[0]);
		}

		tour = new int[n + 1].Select(_ => new List<int>()).ToArray();
		Dfs(1, 0);

		Console.WriteLine((tour.Select(l => Hole(l, m)).Aggregate((x, y) => x + y) / 2).V);
	}

	static List<int>[] map;
	static List<int>[] tour;
	static int c;
	static void Dfs(int p, int p0)
	{
		foreach (var x in map[p])
		{
			if (x == p0) continue;
			tour[x].Add(++c);
			Dfs(x, p);
			tour[p].Add(++c);
		}
	}

	static MInt Hole(List<int> l, int m)
	{
		if (l.Count < 2) return 0;

		MInt allWhite = 1, bSum = 0;
		for (int i = 0; i < l.Count; i++)
		{
			var c = ((l[(i + 1) % l.Count] - l[i]) / 2 + m) % m;
			var w = 1 / ((MInt)2).Pow(c);

			allWhite *= w;
			bSum += 1 / w - 1;
		}
		return 1 - allWhite * (1 + bSum);
	}
}

struct MInt
{
	const int M = 1000000007;
	public long V;
	public MInt(long v) { V = (v %= M) < 0 ? v + M : v; }

	public static implicit operator MInt(long v) => new MInt(v);
	public static MInt operator +(MInt x) => x;
	public static MInt operator -(MInt x) => -x.V;
	public static MInt operator +(MInt x, MInt y) => x.V + y.V;
	public static MInt operator -(MInt x, MInt y) => x.V - y.V;
	public static MInt operator *(MInt x, MInt y) => x.V * y.V;
	public static MInt operator /(MInt x, MInt y) => x * y.Inv();

	public MInt Pow(int i) => MPow(V, i);
	public MInt Inv() => MPow(V, M - 2);

	static long MPow(long b, int i)
	{
		for (var r = 1L; ; b = b * b % M)
		{
			if (i % 2 > 0) r = r * b % M;
			if ((i /= 2) < 1) return r;
		}
	}
}


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

#define uint unsigned int
#define ll long long
#define ull unsigned long long
#define ld long double
#define rep(i, l, r) for (int i = l; i < r; i++)
#define repb(i, r, l) for (int i = r; i > l; i--)
#define sz(a) (int)a.size()
#define fi first
#define se second
#define mp(a, b) make_pair(a, b)

using namespace std;

const int N = 1000000;
const int inf = (int)1e9 + 1;
const ll big = (ll)1e18 + 1;
const int P = 31;
const int MOD = (int)1e9 + 7;
const int MOD1 = (int)1e9 + 9;
const double eps = 1e-9;
const double pi = atan2(0, -1);

int get(ll x)
{
	int res = 0;
	while (x)
	{
		res++;
		x /= 2;
	}
	return res;
}

ll solve(ll A, ll B)
{
	if (A == B)
		return 1;
	int b = get(B) - 1;
	if ((A >> b) & 1)
		return solve(A ^ (1LL << b), B ^ (1LL << b));
	ll C = (1LL << b);
	return (C - A) + min(C, (C - A) + (1LL << get(B - C)));
}

int main()
{
    //freopen("a.in", "r", stdin);
    //freopen("a.out", "w", stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.precision(20);
    //ll TL = 0.95 * CLOCKS_PER_SEC;
    //clock_t time = clock();
    ll A, B;
    cin >> A >> B;
    cout << solve(A, B) << endl;
    return 0;
}

Measured memory_bytes: 256
fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().split_whitespace().map(|e| e.parse().ok().unwrap()).collect()
}

fn main(){
    //W,H,x,y,r
    let mut i:Vec<i32> = read_vec();
    let a = i[0];
    let b = i[1];
    let c = i[2];
    let mut count:i32 = 0;
    for i in a..(b+1) {
        if c%i == 0 {
            count+=1;
        }
    }
    println!("{}", count);
}


Measured memory_bytes: 5032
import java.util.*;

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

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

//#pragma GCC target("sse,sse2,sse3,ssse3,sse4")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
// #include <algorithm>
using namespace std;

#define f first
#define s second
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define eb emplace_back

#define all(v) (v).begin(), (v).end()
#define sz(v) ((int)(v).size())
#define sqr(x) ((x) * (x))

#define ADD_OPERATORS_IN(T, COMP) \
    bool operator < (const T& ot) const { return COMP(ot) == -1; } \
    bool operator > (const T& ot) const { return COMP(ot) == 1; } \
    bool operator == (const T& ot) const { return COMP(ot) == 0; } \
    bool operator != (const T& ot) const { return COMP(ot) != 0; }

#define ADD_OPERATORS_OUT(T, COMP) \
    bool operator < (const T& a, const T& b) const { return COMP(a, b) == -1; } \
    bool operator > (const T& a, const T& b) const { return COMP(a, b) == 1; } \
    bool operator == (const T& a, const T&b) const { return COMP(a, b) == 0; } \
    bool operator != (const T& a, const T&b) const { return COMP(a, b) != 0; }


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

mt19937_64 mt_rand(chrono::system_clock::now().time_since_epoch().count());

template<typename T1, typename T2> inline bool upmax(T1& a, T2 b) { return (a < b ? (a = b, true) : false); }
template<typename T1, typename T2> inline bool upmin(T1& a, T2 b) { return (b < a ? (a = b, true) : false); }

const int maxn = (int) 3e5 + 20;
const int maxlog = 21;
const int base = (int) 1e9 + 7;
const ld eps = (ld) 1e-7;
const ld PI = acos(-1.);
//const int pp = 41;
const int inf = 2e9;

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

    long long ans = 0;
    vector<int> a(n);

    for (int i = 0; i < n; i++) {
        cin >> a[i];
        for (int j = 0; j < i; j++) {
            if (a[j] > a[i]) {
                ans += k % base;
                ans %= base;
            }
        }
    }

    for (int i = 0; i < n; i++) {
        int cnt = 0;
        for (int j = 0; j < n; j++)
            if (a[j] > a[i])
                cnt++;
        ans += 1ll * k * (k - 1) / 2 % base * cnt % base;
        ans %= base;
    }
    cout << ans;
    return 0;
}

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

int main() {
  int n; cin >> n;
  int l; cin >> l;
  vector<int> arr(n);
  int sum_apple = 0;
  for (int i = 0; i < n; ++i) {
    arr[i] = l + i;
    sum_apple += arr[i];
  }
  sort(arr.begin(), arr.end(), [](int a, int b){return abs(a) < abs(b);});
  cout << sum_apple - arr[0] << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

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

int cou[5][4][11];

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

    rep(i, n) {
        int b, f, r, v;
        cin >> b >> f >> r >> v;
        cou[b][f][r] += v;
    }


    for (int tou = 1; tou <= 4; tou++) {
        for (int kai = 1; kai <= 3; kai++) {
            for (int ban = 1; ban <= 10; ban++) {
                cout << ' ' << cou[tou][kai][ban];
            }
            cout << endl;
        }
        if(tou!=4)cout << "####################" << endl;
    }
}


Measured memory_bytes: 3080
#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...);}

#define fo(i, n) for(int i=0; i<n; i++)
#define Fo(i, k, n) for(int i=k; i<n; i++)
#define w(x)  int x; cin>>x; while(x--)
#define watch(x) cout << (#x) << " is " << (x) << "\n"
#define watch2(x,y) cout <<(#x)<<" is "<<(x)<<" and "<<(#y)<<" is "<<(y)<<"\n"
#define watch3(x,y,z) cout <<(#x)<<" is "<<(x)<<" and "<<(#y)<<" is "<<(y)<<" and "<<(#z)<<" is "<<(z)<<"\n"
#define watch4(x,y,z,q) cout <<(#x)<<" is "<<(x)<<" and "<<(#y)<<" is "<<(y)<<" and "<<(#z)<<" is "<<(z)<<" and "<<(#q)<<" is "<<(q)<<"\n"
#define MOD 1000000007
#define INF 1000000007;
#define F first
#define S second
#define pb(x) push_back(x);


#define ll  long long
#define all(c) (c).begin(),(c).end()
#define endl "\n"

typedef vector<int> vl;
typedef vector< vl > vvl;
typedef pair< int, int> pll;
typedef map< int, int> mll;


#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif





void c_p_c()
{
#ifndef ONLINE_JUDGE
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
}
void parray(int a[], int n) {
	for (int i = 0; i < n; i++) {
		cout << a[i] << " ";
	}
	cout << endl;
}
int no = 1, n1;
int recu(int n, int k, int val) {


	if (n == n1) {
		return min(val * 2, val + k);
	}
	return min( recu(n + 1, k, 2 * val), recu(n + 1, k, val + k)              );


}
int digit(int n) {

	int temp = 0;
	while (n) {
		// temp += n % 10;
		n = n / 10;
		temp++;
	}



	return temp;
}

bool check(int a[], int n) {
	for (int i = 0; i < n; ++i)
	{
		/* code */
		if (a[i] % 2)
			return false;
	}
	return true;
}
bool ispalin(int n) {


	string  str = to_string(n);
	// cout<<str<<endl;


	for (int i = 0; i < str.size() / 2; ++i)
	{
		/* code */
		// watch2(str[i],str[str.size()-i-1]);
		if (str[i] != str[str.size() - i - 1]) {
			return false;
		}
	}


	return true;


}

int main() {
	int i,  n, m,c=0, k, sum = 0;
	c_p_c();
	cin>>n;
	string s,t;
	cin>>s>>t;
	for (int i = 0; i < n; ++i)
	{
		/* code */
		cout<<s[i]<<t[i];
	}
	cout<<endl;
}


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

#define FOR(i,b,e) for(int i=(b); i <= (e); ++i)
#define FORD(i,b,e) for(int i=(b); i >= (e); --i)
#define REP(i,n) for(int i=0; i < (n); ++i)
#define SIZE(c) (int) (c).size()
#define ALL(c) (c).begin(), (c).end()
#define PB push_back
#define MP make_pair
#define ST first
#define ND second
#define FWD(i,a,b) for (int i=(a); i<(b); ++i)
#define BCK(i,a,b) for (int i=(a); i>(b); --i)
#define PI 3.14159265358979311600
#define pb push_back
#define mp make_pair
#define st first
#define nd second

using namespace std;

typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;

typedef vector < int > VI;
typedef vector<ll> VL;

typedef long double K;

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

	ll a[4];
	REP(i, 4) cin >> a[i];
	REP(i, 4) {
		int pw = 2;
		FOR (j, i + 1, 3) a[j] = min(a[j], pw * a[i]), pw *= 2;
	}

	ll n;
	cin >> n;
	n *= 4;

	ll result = 0;
	int pw[] = {8, 4, 2, 1};

	REP(i, 4) {
		result += (n / pw[i]) * a[3 - i];
		n %= pw[i];
	}

	cout << result << '\n';


	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <unordered_set>
using namespace std;
#define ll long long
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define repeat(i,s,n) for(int (i)=s; (i)<(n); (i)++)
#define revrep(i,n) for(int (i)=(n)-1;i>=0; i--)

const int SZ = 3000000;
vector<ll> BIT(SZ+1);
ll sum(int a) {
  ll ans=0;
  while(a) {
    ans+=BIT[a];
    a-=a&-a;
  }
  return ans;
}
ll sum(int a,int b) {
  return sum(b)-sum(a-1);
}

void add(int a,ll x) {
  while(a<=SZ) {
    BIT[a]+=x;
    a+=a&-a;
  }
}

void reset() {
  fill(BIT.begin(),BIT.end(),0);
}

const int offset=1000000;

bool check(int x, int n, vector<int>& a) {
  vector<int> A(n+1);
  A[0]=0;
  rep(i,n) {
    if(a[i]>=x) A[i+1]=A[i]+1;
    else A[i+1]=A[i]-1;
  }
  add(0+offset, 1);
  ll c=0;
  repeat(i,1,n+1) {
    //BIT[A[i]+offset]++;
    //c+=BIT[A[i]+offset];
    c+=sum(A[i]+offset);
    add(A[i]+offset,1);
  }
  //cout << "x="<<x<<",c="<<c<<endl;
  reset();
  return c>=(1LL*n*(n-1)/2+n+1)/2;
}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout<<setprecision(std::numeric_limits<float>::max_digits10);
  int n;
  cin>>n;
  vector<int> a(n);
  rep(i,n)cin>>a[i];
  int ok=0;
  int ng=1e9+1;
  bool b = check(20,n,a);
  while(abs(ok-ng)>1) {
    int m = (ok+ng)/2;
    if(check(m,n,a)) {
      ok=m;
    } else {
      ng = m;
    }
  }
  cout << ok << endl;
  return 0;
}


Measured memory_bytes: 24452
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;

public class Main {

	public static void main(String[] args) throws IOException {
		// 標準入力用のオブジェクトを用意（コンソールの入力を受け取る用）
		BufferedReader input = new BufferedReader(new InputStreamReader(System.in));

		String inputStr = null;  // 入力値の文字列を受け取る用の変数
		char[] charNumber = null;  // 入力値の文字列を受ける用の文字配列
		Map<Integer, Integer> strNumberArr = new HashMap<>();  // 文字配列の合計値を保持用のマップ
		int index = 0;  // マップのkey用
		// 無限ループ
		while (true) {
			inputStr = input.readLine();  // 入力値を文字列として受け取る
			// 入力された文字が、"0"の場合
			if ("0".equals(inputStr)) {
				// "0"が入力されるまでに入力された文字列の数値としての合計
				for (Map.Entry<Integer, Integer> entry : strNumberArr.entrySet()) {
					System.out.println(entry.getValue());
				}
				break; // while文を抜ける。無限ループからの脱出
				
			} else {
				// 入力された文字列を文字配列に
				charNumber = inputStr.toCharArray();
				// 文字数だけループ
				for (int i = 0, sum = 0; i < charNumber.length; i++) {
					// 文字を数値として合計する
					sum += Character.getNumericValue(charNumber[i]);
					// ループの最後に、マップに保存
					if (i == charNumber.length - 1) {
						strNumberArr.put(index, sum);
						index++;  // マップのkeyをインクリメンタルジャーニー（+1加算してます）
					}
				}
			}

		}
	}

}



Measured memory_bytes: 24304
#include <iostream>
#include <queue>
#include <stack>
#include <vector>
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <string>
#include <cmath>
#include <complex>
#include <map>
using namespace std;
 
#define rep(i,n) for(int i=0;i<int(n);++i)
 
static const double PI=6*asin(0.5);
typedef complex<double> P;
typedef long long ll;
static const double eps = 1e-8;
 
vector<int> a;
int t;

int main(){
	while(cin>>t){
		a.push_back(t);
	}
	sort(a.begin(),a.end());
	int n=a.size();
	cout<<a[(n--)-1];
	a.pop_back();
	while(!a.empty()){
		cout<<" "<<a[(n--)-1];
		a.pop_back();
	}
	cout<<endl;
	return 0;
}

Measured memory_bytes: 1216
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("unroll-loops")
#pragma warning(disable : 4996)
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<math.h>
#include<iomanip>
#include<set>
#include<numeric>
#include<cstring>
#include<cstdio>
#include<functional>
#include<bitset>
#include<limits.h>
#include<cassert>
#include<iterator>
#include<complex>
#include<stack>
#include<unordered_map>
#include<unordered_set>
#include<time.h>
#include<random>
#include<array>


using namespace std;

#define REP(i, n) for(int i = 0;i < n;++i)
#define REPR(i, n) for(int i = n-1;i >= 0;--i)
#define FOR(i, m, n) for(int i = m;i < n;++i)
#define FORR(i, m, n) for(int i = m-1;i >= n;--i)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define REVERSE(v,n) reverse(v,v+n);
#define VREVERSE(v) reverse(v.begin(), v.end())
#define ll long long
#define pb push_back
#define print(x) cout<<(x)<<'\n'
#define pe(x) cout<<(x)<<" "
#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define lb(v,n) lower_bound(v.begin(), v.end(), (n))
#define ub(v,n) upper_bound(v.begin(), v.end(), (n))
#define int long long
//#define double long double
#define all(x) (x).begin(), (x).end()
#define print_space(v) REP(i,v.size())cout << v[i] << ((i == v.size() - 1) ? "\n" : " ")
template<typename T1, typename T2> inline void chmin(T1 & a, T2 b) { if (a > b) a = b; }
template<typename T1, typename T2> inline void chmax(T1& a, T2 b) { if (a < b) a = b; }
//typedef pair<int, int>P;
const int MOD = 1e9 + 7; const int MAX = 500020;
const double pi = acos(-1); const double EPS = 1e-8;
const ll INF = 1e12;

struct SegmentTree {
	int n;
	vector<int>node;
	SegmentTree(vector<int>v) {
		int sz = v.size();
		n = 1;
		while (n < sz)n *= 2;
		node.resize(2 * n - 1, INT_MAX);
		for (int i = 0; i < sz; i++) {
			node[i + n - 1] = v[i];
		}
		for(int i = n - 2; i >= 0; i--) {
			node[i] = min(node[2 * i + 1], node[2 * i + 2]);
		}
	}

	void update(int x, int val) {
		x += n - 1;//最下段のノード
		node[x] = val;
		while (x > 0) {
			x = (x - 1) / 2;
			node[x] = min(node[2 * x + 1], node[2 * x + 2]);
		}
	}
	int query(int a, int b, int k = 0, int l = 0, int r = -1) {
		if (r < 0)r = n;
		if (r <= a || b <= l)return INF;
		if (a <= l && r <= b)return node[k];
		int vl = query(a, b, 2 * k + 1, l, (l + r) / 2);
		int vr = query(a, b, 2 * k + 2, (l + r) / 2, r);
		return min(vl, vr);
	}
};

void solve() {
	int N, Q; cin >> N >> Q;
	vector<int>v(N,INT_MAX);
	SegmentTree seg(v);
	while (Q--) {
		int f, a, b; cin >> f >> a >> b;
		if (f == 1) {
			b++;
			print(seg.query(a, b));
		}
		else {
			seg.update(a, b);
		}
	}
}

signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	//int q; cin >> q;
	//while (q--)
	solve();
}





Measured memory_bytes: 6500
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#define rep(i,n) for(int i=0;i<n;i++)
int gcd(int a, int b){
    int r=1;
    while(r!=0){
        r=a%b;
        a=b;
        b=r;
    }
    return a;
}
void revStr(char* str){
    int size = strlen(str);
    int i,j;
    char tmp = {0};
    for(i = 0, j = size - 1; i < size / 2; i++, j--){
        tmp = str[i];
        str[i] = str[j];
        str[j] = tmp;
    }return;
}
struct data{
    int a,b,c;
};

//降順
int compare_int(const void *a, const void *b)
{
    return *(int*)b - *(int*)a;
}
#define MAXSIZE 200000
int list[MAXSIZE];
int tail;

void Init(void){
    tail=0;
}
int Top(void){
    return 0;
}

int Next(int pos){
    if(pos<tail-1){
        return pos+1;
    }else{
        return -1;
    }
}
int Count(void){
    return tail;
}

int Item(int pos){
    if((pos>=0)&&(pos<tail)){
        return list[pos];
    }else{
        return 0;
    }
}
void Add(int value){
    if(tail<MAXSIZE){
        list[tail]=value;
        tail++;
    }
}
void Delete(int pos){
    if((pos>=0)&&(pos<tail)){
        int i;
        for(i=pos;i<tail-1;i++){
            list[i]=list[i+1];
        }
        tail--;
    }
}

int main(){
    int N;
    scanf("%d",&N);
    int pos[N];
    rep(i,N){
        scanf("%d",&pos[i]);
    }
    int sum1=0,sum2=0;
    qsort(pos,N,sizeof(int),compare_int);
    rep(i,N){
        if(i%2==0){
            sum1+=pos[i];
        }else{
            sum2+=pos[i];
        }
    }
    printf("%d",sum1-sum2);
}


Measured memory_bytes: 1732
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <vector>
#define SZ(x) ((int) (x).size())
using namespace std;

int gcd(int a, int b) {
    while (b) {
        int c = a % b;
        a = b;
        b = c;
    }
    return a;
}

int main() {
    #ifdef LOCAL_RUN
    freopen("E.in", "r", stdin);
    freopen("E.out", "w", stdout);
    //freopen("task.err", "w", stderr);
    #endif // ONLINE_JUDGE
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;

    vector<int> a(n);
    for (int& x: a) {
        cin >> x;
    }
    sort(a.begin(), a.end());
    const int MOD = 998244353;
    int ans = a[0] % MOD;
    for (int i = 1; i < n; ++i) {
        ans = ans * (int64_t) gcd(a[i], i) % MOD;
    }
    cout << ans << '\n';
}


Measured memory_bytes: 640
//↓template↓

#include "bits/stdc++.h"
using namespace std;
#define Would
#define you
#define all(n)  n.begin(),n.end()
const long long INF = 1e18;
const long long MOD = 1e9 + 7;
const double pi = acos(-1);
const int SIZE = 1 << 17;
int dx[] = { 1,0,-1,0 }, dy[] = { 0,1,0,-1 }, alp[30];
long long fac[200005], finv[200005], inv[200005];
vector<long long>dij;
struct edge { long long to, cost; };
vector<vector<edge> >G;

long long mod_pow(long long a, long long b) {
	long long res = 1;
	while (b) {
		if (b & 1) { res = res * a%MOD; }
		a = a * a%MOD;
		b >>= 1;
	}
	return res;
}

void addedge(int from, int to, int cost) {
	G[from].push_back({ to,cost });
	G[to].push_back({ from,cost });
}

//↑template↑

int main() {
	long long a, b;
	cin >> a >> b;
	cout << max((long long)0, a - b) << endl;
}

Measured memory_bytes: 256