akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <algorithm>
using namespace std;
const int Maxn = 4*111111;
namespace seqtree
{
    struct Tree
    {
        Tree *ch[2];
        long long _v, label;
        int Num, _l, _r, mid;
        Tree() { _v = label = 0; Num = 1; }
        void update();
        void maintain();
    }Node[Maxn], *null, *Root;
    int tot = 0, _k, _L, _R;
    long long v;
    void Tree::update()
    {
        if(!label) return;
        _v += Num*label;
        if(Num != 1) ch[0]->label += label, ch[1]->label += label;
        label = 0;
    }
    void Tree::maintain()
    {
        ch[0]->update(); ch[1]->update();
          _v = ch[0]->_v + ch[1]->_v;
    }
    void protect()
    {
       null = new Tree();
       null->ch[0] = null->ch[1] = null; null->Num = 0;
    }
    void insert(Tree *&o, int l, int r)
    {
        int mid = (l+r)/2;
        if(o == null)
        {
             o = &Node[tot++];
             o->ch[0] = o->ch[1] = null;
             o->_l = l; o->_r = r; o->mid = (l+r)/2;
        }
        if(l == r) { o->_v = v; return; }
        if(_k <= mid) insert(o->ch[0], l, mid);
        else insert(o->ch[1], mid+1, r);
        o->maintain(); o->Num = o->ch[1]->Num + o->ch[0]->Num;
    }
    Tree* Build(int n, long long *a)
    {
          protect(); Root = null;
           for(int i = 1; i <= n; i++) _k = i, v = a[i], insert(Root, 1, n);
           return Root;
    }
    long long query(Tree *o)
    {
        long long ans = 0;
        o->update();
        if(_L <= o->_l && o->_r <= _R) return o->_v;
        if(_L <= o->mid) ans += query(o->ch[0]);
        if(_R > o->mid) ans += query(o->ch[1]);
        return ans;
    }
    long long Query(int L, int R) { _L = L; _R = R; return query(Root); }
    void change(Tree *o)
    {
      o->update();
      if(_L <= o->_l && o->_r <= _R) { o->label += v; o->update(); return; }
      if(_L <= o->mid) change(o->ch[0]);   if(_R > o->mid) change(o->ch[1]);
      o->maintain();
    }
    void Change(int L, int R, int V) { _L = L; _R = R; v = V; change(Root); }
};
using namespace seqtree;

struct Data
{
    int l, r, v;
    bool operator < (const Data &B) const
    { return v < B.v; }
}A[Maxn];

int n, m, l, r;
long long a[Maxn], ANS[Maxn];
int main()
{
    cin.sync_with_stdio(false);
    cin>>n>>m;
    Build(m+1, a);
    for(int i = 0; i < n; i++)
    {
        cin>>A[i].l>>A[i].r;
        A[i].v = A[i].r - A[i].l + 1;
    }
    sort(A, A+n);
    int k = 0;
    for(int i = 1; i <= m; i++)
    {
        for(; A[k].v < i && k < n; k++)  Change(A[k].l, A[k].r, 1);
        int ans = n - k;
        for(int j = i; j <= m; j += i) ans += Query(j, j);
        cout<<ans<<endl;
    }
}


Measured memory_bytes: 25344
N = int(input())
X = [0]*N
for i in range(N):
    X[i] = [0]*2
    x, l = map(int, input().split())
    X[i][1] = x - l
    X[i][0] = x + l
X = sorted(X)
nowplace = X[0][0]
ans = 1
for j in range(1, N):
    if nowplace <= X[j][1]:
        ans += 1
        nowplace = X[j][0]

print(ans)


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

int b[501] = {0}, r[501] = {0};

bool augment(const vector<int> g[], int src,
    vector<int>& matchTo, vector<bool>& visited) {
  if (src < 0) return true;
  for(auto dst : g[src]) if (!visited[dst]) {
    visited[dst] = true;
    if (augment(g, matchTo[dst], matchTo, visited)) {
      matchTo[src] = dst;
      matchTo[dst] = src;
      return true;
    }
  }
  return false;
}

int bipartiteMatching(const vector<int> g[], int m, int n) {
  vector<int> matchTo(m + n, -1);
  int match = 0;
  for(int u=0;u<m;++u) {
    vector<bool> visited(m + n);
    if (augment(g, u, matchTo, visited)) ++match;
  }

  return match;
}

int gcd(int a, int b){
    return (b != 0 ? gcd(b, a % b) : a);
}

int main(){
    int m, n;
    while(cin >> m >> n, m != 0 || n != 0){
        for(int i=0;i<m;++i)cin >> b[i];
        for(int i=0;i<n;++i)cin >> r[i];
        vector<int> g[m+n];
        for(int i=0;i<m;++i){
            for(int j=0;j<n;++j){
                if(gcd(b[i], r[j]) != 1){
                    g[i].push_back(m + j);
                    g[m + j].push_back(i);
                }
            }
        }
        int ans = bipartiteMatching(g, m, n);
        cout << ans << endl;
    }

    return 0;
}


Measured memory_bytes: 4456
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<bitset>
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<deque>
#include<list>
#include<iomanip>
#include<cmath>
#include<cstring>
#include<functional>
#include<cstdio>
#include<cstdlib>
using namespace std;

#define repr(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define rep(i, n) repr(i, 0, n)
#define INF 2e9
#define MOD 1000000007
//#define MOD 998244353
#define LINF (long long)4e18
#define jck 3.141592

const double EPS = 1e-10;

using ll = long long;
using Pi = pair<int,int>;
using Pl = pair<ll,ll>;


int main(){
    int n; cin >> n;
    string s; cin >> s;
    string ans = s;
    int l = 0;
    int r = 0;
    rep(i,n){
        if(s[i] == '(') l++;
        else r++;
        if(l < r){
            ans = '('+ans;
            l++;
        }
    }
    int k = l-r;
    rep(i,k){
        ans += ')';
    }
    cout << ans << endl;
}



Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <algorithm>
#include <set>
#include <map>
#include <bitset>
#define vv(a, b, c, d) vector<vector<d> >(a, vector<d>(b, c))
#define vvi std::vector<std::vector<int> >
#define vvl std::vector<std::vector<ll> >
#define MODs 1000000007;
typedef long long int ll;
using namespace std;

int main(int argc, char const *argv[]) {
  ll N, a, b, ans = 0;
  std::cin >> N;
  std::vector<int> R, L;
  for(int i=0;i<N;i++){
    std::cin >> a >> b;
    R.push_back(a), L.push_back(b);
  }
  sort(R.begin(), R.end(), [](ll a, ll b){return a > b;});
  sort(L.begin(), L.end());
  ll now = 0;
  for(int i=0;i<N;i++){
    //std::cout << L[i] << " " << R[i] << '\n';
    ans = max(ans, now+2*R[i]);
    now += 2*R[i] - 2*L[i];
    ans = max(ans, now);
  }

  now = 0;
  for(int i=0;i<N;i++){
    //std::cout << now << " " << now - 2*L[i] << '\n';
    ans = max(ans, now-2*L[i]);
    now += 2*R[i] - 2*L[i];
    ans = max(ans, now);
  }
  std::cout << ans << '\n';
  return 0;
}


Measured memory_bytes: 1524
x,n=map(int,input().split())
p=list(map(int,input().split()))
q=p
s=0
for i in range(n):
    p[i]-=x
for i in range(100):
    t=0
    for j in range(n):
        if p[j]==i:
            t+=1
        if p[j]==-i:
            t+=2
    s=i
    if t!=3:
        break
if t==0 or t==1:
    print(x-s)
else:
    print(x+s)

Measured memory_bytes: 63332
import sys
def input(): return sys.stdin.readline().rstrip()
from collections import deque
def main():
    n,m=map(int,input().split())
    graph=[[] for _ in range(n)]
    for i in range(m):
        a,b=map(int,input().split())
        graph[a-1].append(b-1)
        graph[b-1].append(a-1)
    queue=deque([0])
    visited=[False]*n
    visited[0]=True
    ans=[0]*n
    while queue:
        node=queue.popleft()
        for xnode in graph[node]:
            if visited[xnode]:continue
            ans[xnode]=node+1
            visited[xnode]=True
            queue.append(xnode)
    print("Yes")
    for a in ans[1:]:
        print(a)


if __name__=='__main__':
    main()

Measured memory_bytes: 93356
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define fast ios::sync_with_stdio(false); cin.tie(NULL);
#define rep(n) for(int i=0; i<n; i++)
#define rep1(i,n) for(int i=0; i<n; i++)
const int INF = 2e18;

void solve(){
	int n;cin>>n;
	int l[n];rep(n)cin>>l[i];

	sort(l,l+n);
	int ans = 0;
	for(int i=0;i<n-2;i++){
		for(int j=i+1;j<n;j++){
			for (int k = j + 1; k < n; k++) 
                if (l[i] + l[j] > l[k] 
                    && l[i]!=l[j] && l[i]!=l[k] && l[j]!=l[k]) 
                    ans++; 
		}
	}
	cout<<ans<<endl;


}
	
signed main(){
    fast;    
    // int t;cin>>t;while(t--)
    solve();    
    return 0;
}

Measured memory_bytes: 3628
/*
このコード、と～おれ!
Be accepted!
∧＿∧　
（｡･ω･｡)つ━☆・*。
⊂　　 ノ 　　　・゜+.
　しーＪ　　　°。+ *´¨)
 　　　　　　　　　.· ´¸.·*´¨) ¸.·*¨)
		  　　　　　　　　　　(¸.·´ (¸.·'* ☆
					*/

#include <stdio.h>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstring>
#include <vector>
#include <numeric>
#include <iostream>
#include <random>
#include <map>
#include <unordered_map>
#include <queue>
#include <regex>
#include <functional>
					/*多倍長整数/cpp_intで宣言
					#include <boost/multiprecision/cpp_int.hpp>

					using namespace boost::multiprecision;
					*/

#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#define rep(i, n) for(int i = 0; i < (n); ++i)
#define rep1(i, n) for(int i = 1; i <= (n); ++i)
#define rep2(i, n) for(int i = 2; i < (n); ++i)
#define repr(i, n) for(int i = n; i >= 0; --i)
#define reprm(i, n) for(int i = n - 1; i >= 0; --i)
#define printynl(a) printf(a ? "yes\n" : "no\n")
#define printyn(a) printf(a ? "Yes\n" : "No\n")
#define printYN(a) printf(a ? "YES\n" : "NO\n")
#define printin(a) printf(a ? "possible\n" : "inposible\n")
#define printdb(a) printf("%.50lf\n", a)//少数出力
#define printdbd(a) printf("%.16lf\n", a)//少数出力(桁少なめ)
#define prints(s) printf("%s\n", s.c_str())//string出力
#define all(x) (x).begin(), (x).end()
#define allsum(a, b, c) ((a + b) * c / 2)//等差数列の和、初項,末項,項数
#define pb push_back
#define priq priority_queue
#define rpriq priq<int, vector<int>, greater<int>>
#define deg_to_rad(deg) (((deg)/360.0)*2.0*PI)
#define rad_to_deg(rad) (((rad)/2.0/PI)*360.0)
#define Please return
#define AC 0
#define addf(T) [](T a, T b){return (a + b);}
#define minf(T) [](T a, T b){return min(a, b);}
#define maxf(T) [](T a, T b){return max(a, b);}


using ll = long long;

constexpr int INF = 1073741823;
constexpr int MINF = -1073741823;
constexpr ll LINF = ll(4661686018427387903);
constexpr ll MOD = 1000000007;
const long double PI = acos(-1.0L);

using namespace std;

void scans(string& str) {
	char c;
	str = "";
	scanf("%c", &c);
	if (c == '\n')scanf("%c", &c);//最初の改行対策
	while (c != '\n' && c != -1) {
		str += c;
		scanf("%c", &c);
	}
}

void scanc(char& str) {
	char c;
	scanf("%c", &c);
	if (c == -1)return;
	while (c == '\n') {
		scanf("%c", &c);
	}
	str = c;
}

double acot(double x) {
	return PI / 2 - atan(x);
}

ll gcd(ll a, ll b) {
	if (b == 0) return a;
	return gcd(b, a % b);
}

ll lcm(ll number1, ll number2) {//lcmを求める
	return number1 / gcd(number1, number2) * number2;
}

ll LSB(ll n) { return (n & (-n)); }

/*-----------------------------------------ここからコード-----------------------------------------*/



int main() {

	char c;
	scanf("%c", &c);
	printf("%c\n", c + 1);

	Please AC;
}


Measured memory_bytes: 888
#include <iostream>
//#include <fstream>

using namespace std;

int main(int argc, const char * argv[]) {
//    ifstream in("input.txt");
//    cin.rdbuf(in.rdbuf());
    
    int N, K;
    string S;
    
    cin >> N >> K;
    cin >> S;
    
    int idx = K - 1;
    
    char s = S[idx];
    if (s == 'A')
    {
        S[idx] = 'a';
    }
    else if (s == 'B')
    {
        S[idx] = 'b';
    }
    else
    {
        S[idx] = 'c';
    }
    
    cout << S << endl;
    
    
    
    return 0;
}


Measured memory_bytes: 888
#include<iostream>
#include<map>
#include<vector>
#include<algorithm>
using namespace std;
long long modpow(long long a, long long b, long long m) {
	long long p = 1, q = a;
	for (int i = 0; i < 60; i++) {
		if ((b / (1LL << i)) % 2 == 1) { p *= q; }
		p %= m; q *= q; q %= m;
	}
	return p;
}
long long N, K, M[1500], mod = 1000000007; vector<long long>E;
int main() {
	cin >> N >> K;
	for (int i = 1; i*i <= N; i++) {
		if (N%i != 0)continue;
		E.push_back(i);
		E.push_back(N / i);
	}
	sort(E.begin(), E.end());
	E.erase(unique(E.begin(), E.end()), E.end());
	for (int i = 0; i < E.size(); i++) {
		long long cnt = modpow(K, (E[i] + 1) / 2, mod);
		for (int j = 0; j < i; j++) {
			if (E[i] % E[j] == 0)cnt -= M[j]; cnt += mod; cnt %= mod;
		}
		M[i] = cnt;
	}
	long long ret = 0;
	for (int i = 0; i < E.size(); i++) {
		long long G = E[i]; if (G % 2 == 0)G /= 2;
		ret += G*M[i]; ret %= mod;
	}
	cout << ret << endl;
	return 0;
}

Measured memory_bytes: 256
n = int(input())
coordinates = []
for _ in range(n):
    x, L = map(int, input().split())
    coordinates.append((x-L, x+L))
coordinates.sort(key=lambda x: x[1])

INF = 10**18
X = -INF
ans = 0
for L, R in coordinates:
    if L < X:
        continue
    X = R
    ans += 1
print(ans)

Measured memory_bytes: 23916
#pragma GCC optimize ("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse4")
#include"bits/stdc++.h"
using namespace std;
typedef long long ll;
#define int ll
#define sz(x) (int)(x).size();
#define all(x) x.begin(), x.end()
#define trav(i,a) for(auto &i:a) 
inline int in(){int x;scanf("%lld",&x);return x;}
int32_t main()
{
	int n=in();
	vector<int> a(5);
	trav(i,a)i=in();
	int ans=0;
	for(auto i:a)ans=max(ans,(n-1)/i);
	cout<<ans+5;
	
}

Measured memory_bytes: 3684
ma = lambda :map(int,input().split())
lma = lambda :list(map(int,input().split()))
tma = lambda :tuple(map(int,input().split()))
ni = lambda:int(input())
yn = lambda fl:print("Yes") if fl else print("No")
ips = lambda:input().split()
import collections
import math
import itertools
import heapq as hq
n,q = ma()
black = [[n-2]*(n+1) for i in range(2)] #変えられる黒の個数 1 idx
inner =[n,n] #最も内側の白の位置 1 idx
innerbl = [n-2,n-2] #最も内側で変えられる黒
ans=(n-2)**2
for _ in range(q):
    t,x = ma();t-=1
    if x>inner[t]:
        ans-=black[t][x]
    elif x<inner[t]:
        ans-=innerbl[t]
        innerbl[1-t]=x-2
        for i in range(x,inner[t]):
            black[t][i]=innerbl[t]
        inner[t]=x
print(ans)


Measured memory_bytes: 73412
#include <iostream>
#include <algorithm>
#include <functional>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <string>

#define rep(i, n) for (int i = 0; i < n; i++)
using namespace std;
typedef long long ll;
typedef vector<int> vec;
typedef vector<vector<int>> mat;
using P = pair<ll, ll>;

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;}

const ll mod = 1000000007;
const int INF = 1<<29;

int main(){
  int N, M; cin >> N >> M;
  int res = 0;
  if (N >= 2){
    res += N * (N - 1) / 2;
  }
  if (M >= 2){
    res += M * (M - 1) / 2;
  }
  cout << res << endl;
}


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

int main() {
  int N,K;
  cin >> N>>K;
  int count = 0;
  
  for (int i = 0; i < N; i++){
    int x;
    cin >> x;
    if (K/2 >= x){
      count += x*2;
    }
    else{
      count += (K - x)*2;
    }
  }

  cout << count << endl;
}



Measured memory_bytes: 3644
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define all(x) (x).begin(), (x).end()
using namespace std;

int		main(void)
{
	int n, x;

	cin >> n >> x;
	vector<int> d(n);

	for (int i = 0; i < n; i++)
		cin >> d[i];
	int ans = 0, sum = 0;

	for (int i = 0; i < n; i++)
		sum += d[i];
	sort(all(d));
	while (sum < x)
	{
		sum += d[0];
		ans++;
	}
	if (sum > x)
		ans--;
	cout << ans + n << endl;
}


Measured memory_bytes: 256
#include <iostream>

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

void solve(ll N, ll K) {
  int d{};
  while(N) {
    N/=K;
    ++d;
  }
  cout << d << endl;
}

int main() {
  ll N;
  cin >> N;
  ll K;
  cin >> K;
  solve(N, K);
  return 0;
}


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

typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
const ull mod = 1e9 + 7;
#define REP(i,n) for(int i=0;i<(int)n;++i)

//debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

template<class S, class T> ostream& operator << (ostream& os, const pair<S, T> v){
  os << "(" << v.first << ", " << v.second << ")"; return os;
}
template<class T> ostream& operator << (ostream& os, const vector<T> v){
  for(int i = 0; i < (int)v.size(); i++){if(i > 0){os << " ";} os << v[i];} return os;
}
template<class T> ostream& operator << (ostream& os, const vector<vector<T>> v){
  for(int i = 0; i < (int)v.size(); i++){if(i > 0){os << endl;} os << v[i];} return os;
}

ll factorial(ll x){
	if(x==1) return 1;
	return x * factorial(x-1);
}

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

    ll N;
    cin >> N;
    vector<ll> x(N), y(N);
    REP(i, N) cin >> x[i] >> y[i];

    vector<ll> perm2;
    REP(i, N) perm2.push_back(i);

	bool flag = true;
	double res = 0;
	while(flag){
		//vprint(perm2);
		REP(i, N-1){
			double dx = (x[perm2[i+1]] - x[perm2[i]]);
			double dy = (y[perm2[i+1]] - y[perm2[i]]);
			res += sqrt(dx * dx + dy * dy);
		}
		flag = next_permutation(perm2.begin(), perm2.end());
	}
	printf("%.10f\n", res/factorial(N));

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
 
using namespace std;
int main()
{

   string s,t;
  cin>>s>>t;
  int n=s.size();
  int m=t.size();
  int dp[n+1][m+1];
  
  
  for(int i=0;i<=n;i++)
  {
    for(int j=0;j<=m;j++)
    {
      if(i==0 || j==0)
      dp[i][j]=0;
      else if(s[i-1]==t[j-1])
       dp[i][j]=dp[i-1][j-1]+1;
      else
        dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
      
      
       }
   }
  int sz=dp[n][m];
  string str(sz,'0');
  int i=n,j=m;
  int k=sz;
  while(i>0 && j>0)
  {
     if(s[i-1]==t[j-1])
     {
       str[k-1]=s[i-1];
       i--,j--,k--;
      }
    else if(dp[i-1][j]>dp[i][j-1])
    {
      i--;
    }
    else
    {
      j--;
      
    }
    
    
  }
  cout<<str;
  return 0;
  
  
  
}

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

int main(){
    char a;
    cin >> a;

    if(a == 'A') cout << 'T' << endl;
    else if(a == 'T') cout << 'A' << endl;
    else if(a == 'C') cout << 'G' << endl;
    else cout << 'C' << endl;
}

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

#define DBG(a)	cerr << #a << "  = " << a << endl;
int main(){
	int n;	cin >> n;
	int k;	cin >> k;
	int h[n];
	for (int i = 0; i < n; ++i){
		cin >> h[i];
	}
	int dp[n+k+10];
	fill(dp, dp+n+10, 1e9+10);
	dp[0] = 0;
	for (int i = 0; i < n; ++i){
		for (int j = 1; j <= k; ++j){
			dp[i+j] = min(dp[i+j], dp[i]+abs(h[i+j]-h[i]));
		}
	}
	cout << dp[n-1] << endl;
	return 0;
}

Measured memory_bytes: 1024
def popcount_parity(x):
    x ^= x >> 1
    x ^= x >> 2
    x ^= x >> 4
    x ^= x >> 8
    x ^= x >> 16
    return -1 if x & 1 else 1

N, K, S, T = map(int, input().split())
if S & T != S:
    print(0)
    exit()

C = [[1]]
CC = [0] * 51
for i in range(1, 51):
    C.append([1] * (i + 1))
    for j in range(1, i):
        C[i][j] = C[i-1][j-1] + C[i-1][j]
for i in range(51):
    CC[i] = sum(C[i][1:K+1])

A = [int(a) for a in input().split()]
aa, oo = - 1, 0
for i in range(N)[::-1]:
    a = A[i]
    if a & S != S or a | T != T:
        del A[i]
        continue
    aa &= a
    oo |= a
aa ^= oo

i = aa
ans = 0
while 1:
    D = {}
    for a in A:
        t = i & a
        if t not in D: D[t] = 1
        else: D[t] += 1
    c = 0
    for t in D.values():
        c += CC[t]
    ans += c * popcount_parity(i)
    if not i: break
    i = (i - 1) & aa
print(ans)

Measured memory_bytes: 68724
#include "bits/stdc++.h"
using namespace std;

typedef long long ll;


int main() {
    int n;
    ll k;
    cin >> n >> k;
    map<int, ll> mp;
    for(int i = 0; i < n; i++) {
        int a, b;
        cin >> a >> b;
        mp[a] += b;
    }

    ll s = 0;
    for(auto&& e : mp) {
        s += e.second;
        if(s >= k) {
            cout << e.first << endl;
            break;
        }
    }


    return 0;
}

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

struct Point {
  int x,y;
  bool operator < (const Point& p) const {
    if( y != p.y ) return y < p.y;
    return x > p.x;
  }
};
ostream& operator << (ostream& os,const Point& p) {
  os << p.x <<" "<< p.y;
}

int score[100001];
int t[1000000];
int time_[1000000];
int main(){
  priority_queue<Point> Q;
  priority_queue<Point> T;
  int N,R,L;
  int d,x;
  int a=1,b=0;

  cin >>N>>R>>L;


  for(int i=0;i<R;i++){
    cin >>d>>t[i]>>x;    
    score[d]+=x;
    Q.push((Point){d,score[d]});  
    while(!Q.empty() && score[Q.top().x] != Q.top().y){
      Q.pop();
    }
    time_[a]+=t[i]-b; 
    T.push((Point){a,time_[a]});
    a=Q.top().x;
    b=t[i];
    //time_[a]+=t[i]-b;
    
  }
  
  while( !Q.empty() && score[Q.top().x] != Q.top().y){
    Q.pop();
  }
  time_[a]+=L-b;
  if( !Q.empty() ) a=Q.top().x;
  else a = 1;
  b=L;
  T.push((Point){a,time_[a]});
 
  cout <<T.top().x<<endl;

  while( !T.empty() ){
    //cout <<T.top()<<endl;
    T.pop();
  }
  return 0;
}



    

	    


    

Measured memory_bytes: 21976
from itertools import permutations


def dfs(p, bit):
    res = 0
    for k in range(n):
        if bit >> k & 1:
            continue
        d = ((x[k] - x[p]) ** 2 + (y[k] - y[p]) ** 2) ** 0.5
        res += d + dfs(k, bit | (1 << k))
    return res


n = int(input())
x = [0] * n
y = [0] * n
for i in range(n):
    x[i], y[i] = map(int, input().split())

ans = 0
# for i in range(n):
#     ans += dfs(i, 1 << i)
# for i in range(n):
#     ans /= i + 1
for li in list(permutations(range(n), n)):
    tmp = 0
    for i in range(n - 1):
        p = li[i]
        k = li[i + 1]
        tmp += ((x[k] - x[p]) ** 2 + (y[k] - y[p]) ** 2) ** 0.5
    ans += tmp
for i in range(n):
    ans /= i + 1

print(ans)


Measured memory_bytes: 13848
import os
import sys
import math
if os.environ.get("DEBUG") is not None:
    sys.stdin = open("in.txt", "r")
rl = sys.stdin.readline

n, s = rl().rstrip("\n"), rl().rstrip("\n")
x = 0
ans = 0
for it in s:
    if it == "I":
        x += 1
    else:
        x -= 1
    ans = max(ans, x)
print(ans)

Measured memory_bytes: 9124
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define space " "
#define MOD (long long) 1000000007
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename T> void __f(const char* variable_name, T&& value){cout << variable_name << ": " << value << endl;}
template <typename T1, typename... T2> void __f(const char* names, T1&& arg1, T2&&... args){const char* comma = strchr(names + 1, ',');cout.write(names, comma - names) << ": " << arg1 << " |";__f(comma + 1, args...);}

const ll N = 5e5 + 5;
ll *v;
ll n, r;

void solve(){
    cin >> n >> r;
    ll ans = 0;
    while(n > 0){
        ans++;
        n /= r;
    }
    cout << ans << endl;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    ll t = 1;
    // cout << "\n\nBLAH BLAH BLAH\n\n";
    // cin >> t;
    while(t--){
        solve();
    }
    return 0;
}

Measured memory_bytes: 256
x,k,d = gets.split.map(&:to_i)
tmp = (x.abs - (k * d))
tmp2 = x.abs % d
step = x.abs / d
if tmp < 0
  if (k - step).odd?
    puts (tmp2 - d).abs > tmp.abs ? tmp.abs : (tmp2 - d).abs
  else
    puts tmp2 > tmp.abs ? tmp.abs : tmp2
  end
else
  puts tmp
end

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

using namespace std;


typedef unsigned long long ULL;


const int N = 2e5 + 10;


char str[N];
int n;


int main()
{
	scanf("%s", str+1);
	n = strlen(str + 1);
	
	int cnt = 0;
	
	int lastl = 0, lastr = 0; ULL num = 0;
	for (int i = 1; i <= n; i = lastr + 1)
	{
		int pos = 1;
		ULL x = 1, h = str[i];
		while (i + pos - 1 <= n && num == h)
		{
			pos++;
			h += x * str[i + pos - 1];
			x *= 233;
		}
		lastl = i;
		lastr = i + pos - 1;
		num = h;
		if (lastr <= n) cnt++;
	}
	
	printf("%d\n", cnt);
	
	return 0;
}

Measured memory_bytes: 384
#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>

using namespace std;

int main(){
    int N;
    cin >> N;
    vector< pair<int, int> > R(N), B(N);
    for(int i = 0; i < N; i++){
        cin >> R[i].second >> R[i].first;
    }
    for(int i = 0; i < N; i++){
        cin >> B[i].first >> B[i].second;
    }

    sort(R.begin(), R.end());
    sort(B.begin(), B.end());
    reverse(R.begin(), R.end());


    int ans = 0;
    map<int, bool> M;
    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            if(M[j] == true){
                continue;
            }
            if(R[j].first < B[i].second && R[j].second < B[i].first){
                ans++;
                M[j] = true;
                break;
            }
        }
    }

    cout << ans << endl;


    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,N) for(int i=0;i<int(N);++i)
using i64 = int64_t;
using ll = long long;
int main() {
  int A,B,X;
  cin >> A >> B >> X;
  if(X >= A && X <= A+B){
    cout << "YES" << endl;
  }
  else{
    cout << "NO" << endl;
  }
  return 0;
}

Measured memory_bytes: 3520
N = gets.to_i
CHARS = ['A', 'C', 'G', 'T']
dp = Array.new(N + 10)
dp[0] = { '' => 1 }

def agc_include?(str)
  [/AGC/, /ACG/, /GAC/, /A.GC/, /AG.C/].any? do |pat|
    (str =~ pat) != nil
  end
end

(1..N).each do |i|
  prev = dp[i - 1]
  CHARS.each do |ch|
    prev.each do |(prev_str, count)|
      next if agc_include?(prev_str + ch)
      if dp[i].nil?
        dp[i] = Hash.new { 0 }
      end
      last2 = (prev_str.size == 3 ? prev_str[1..-1] : prev_str)
      new_str = last2 + ch
      dp[i][new_str] += count
    end
  end
end
puts dp[N].values.reduce(&:+) % (10 ** 9 + 7)


Measured memory_bytes: 4220
#include "bits/stdc++.h"
using namespace std;
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
*this << "[";
for (auto it = d.b; it != d.e; ++it)
*this << ", " + 2 * (it == d.b) << *it;
ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
#define cool ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define int  long long int
#define pb push_back
#define fe first
#define lb lower_bound 
#define ub upper_bound
#define pii pair<pair<int,int>,pair<int,int> >
#define se second
#define endl "\n"
#define pi pair<int, int>
#define mi          map<int,int>
#define mii         map<pi,int>
#define vi vector<int> 
#define vvi vector<vi>
#define bs   binary_search
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rep1(i,a,b) for(int i=a;i<=b;i++)	
#define all(c) (c).begin(),(c).end()
#define sz(x)       (int)x.size() 
#define PI 3.14159265358979323846

 const int N=2e3+5;

 int mod= 1e9+7;
 int dx[4]={0,0,+1,-1};
 int dy[4]={+1,-1,0,0};  
 
 
int po(int a, int b) {
	a %= mod;
	int res = 1;
	while (b > 0) {
		if (b & 1)
			res = (res * a) % mod;
		a =(a*a) % mod;
		b >>= 1;
	}
	 return res;	
   }


  int ispalin(string s) {
	     int len=sz(s);
	     
	     for(int i=0,j=len-1;i<j;i++,j--) {
			     if(s[i]!=s[j]) {
					    return 0;
					  }					  
			 }
			 return 1;
	  }

	void solve(){
       string s;
       cin>>s;
       int len=sz(s);
       string p1=s.substr(0,(len-1)/2);
       string p2=s.substr((len+3)/2-1,len);
       //~ cout<<p1<<" "<<p2<<endl;
       if(ispalin(s) && ispalin(p1) && ispalin(p2)) {
		       cout<<"Yes\n";
		   }
	   else 
	      cout<<"No\n";	   
										 
	 
	}

int32_t main() {
	cool;
	int t=1;
	//cin>>t;
	while(t--)
	solve();


return 0;	   
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 7;
struct aa{
	int first,second;
}P;
aa arr[N];
int minnore[N];
aa S[N];

bool cmp1(aa a, aa b){
	return a.first > b.first;
}
 
 
int main(){
	int q, L, R, mxL = 0, mnR = 1e9 + 7, RR, LL;
	int flag1 = 0, flag2 = 0, maxlen = 0;
	scanf("%d", &q);
	for(int i = 0; i < q; i ++ ){
		scanf("%d%d", &L, &R);
		arr[i].first = L;
		arr[i].second = R;
		if(L > mxL){
			mxL = L;
			RR = R;
			flag1 = i;
		}
		if(R < mnR){
			mnR = R;
			LL = L;
			flag2 = i;
		} 
		maxlen = max(maxlen, R - L + 1);
	}
	int ans1 = maxlen;
	if(mnR >= mxL)	ans1 += mnR - mxL + 1;
	if(flag1 == flag2){
		cout << ans1 << endl;
		return 0;
	}
	for(int i = 0; i < q; i ++ ){
		S[i].first = max(arr[i].second - mxL + 1, 0);
		S[i].second = max(mnR - arr[i].first + 1, 0);
	}
	sort(S, S + q, cmp1);
	minnore[q-1] = S[q - 1].second;
	for(int i = q - 2; i >= 0; i --){
		minnore[i] = min(minnore[i + 1], S[i].second);
	}
	int ans2 = 0;
	for(int i = 0; i < q; i ++ ){
		ans2 = max(ans2, S[i].first + minnore[i+1]);
	}
	cout << max(ans2,ans1) <<endl;
	
	
	
	return 0;
} 

Measured memory_bytes: 2176
#include <stdio.h>
int gcd(int a,int b)
{
	int r;
	/* ユークリッドの互除法 */
	r = a % b;
	while(r!=0)
	{
		a = b;
		b = r;
		r = a % b;
	}
	return b;
}

int div(int a, int b, int c)
{
	int tmp;
	int d;

	if(a<b)
	{
		tmp = a;
		a = b;
		b = tmp;
	}
	d = gcd(a, b);
	if(c<d)
	{
		tmp = c;
		c = d;
		d = tmp;
	}
	return (gcd(c,d));
}

// int div(int a, int b, int c)
// {
// 	int max;
// 	int i = 1;
// 	int ans = 1;
// 	if (a < b)
// 		max = b;
// 	else
// 		max = a;
// 	if (max < c)
// 		max = c;
// 	while (i <= max)
// 	{
// 		if (a % i == 0 && b % i == 0 && c % i == 0)
// 		{
// 			ans = i;
// 		}
// 		i++;
// 	}
// 	return (ans);
// }

int		main(void)
{
	int k;
	scanf("%d", &k);
	int a,b,c;
	long sum = 0;
	a = 1;
	while (a <= k)
	{
		b = 1;
		while (b <= k)
		{
			c = 1;
			while (c <= k)
			{
				if (div(a,b,c))
					sum += div(a, b, c);
				c++;
			}
			b++;
		}
		a++;
	}
	printf("%ld", sum);
	return (0);
}


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

using namespace std;
typedef long long ll;
const int INF = 1e9;
const int MOD = 1e9 + 7;
const ll LINF = 1e18;

int main() {

    int h, w, k; cin >> h >> w >> k;

    vector<string> s(h);
    for (int i = 0; i < h; ++i) {
        cin >> s[i];
    }

    vector<int> cnt(h);

    for (int i = 0; i < h; ++i) {
        for (int j = 0; j < w; ++j) {
            if (s[i][j] == '#') cnt[i]++;
        }
    }

    vector<vector<int>> ans(h);

    int idx = 1;
    bool one = false;

    for (int i = 0; i < h; ++i) {
        if (cnt[i] == 0) continue;

        for (int j = 0; j < w; ++j) {
            int k = j;
            while (k < w) {
                if (one && s[i][k] == '#') {
                    break;
                } else if (!one && s[i][k] == '#') {
                    ans[i].push_back(idx);
                    one = true;
                } else {
                    ans[i].push_back(idx);
                }

                ++k;
            }

            j = k - 1;
            one = false;
            ++idx;
        }
    }

    for (int i = 0; i < h; ++i) {
        int tmp = i;

        while (ans[tmp].empty() && tmp < h) {
            ++tmp;
        }

        if (tmp == h) {
            --tmp;
            
            while (ans[tmp].empty() && tmp > 0) {
                --tmp;
            }
        }

        for (int j = 0; j < w; ++j) {
            cout << ans[tmp][j] << " ";
        }

        cout << endl;
    }
}

Measured memory_bytes: 1536
import numpy as np

s = input().strip()
t = 0
counts = np.array([0] * 2019)
counts[0] += 1
m = 1

for a  in reversed(s):
    t = (t + m * int(a)) % 2019
    counts[t] += 1
    m = m * 10 % 2019
    
print(int(np.sum(counts * (counts - 1) /2)))

Measured memory_bytes: 27328
import math
n, d = map(int, input().split())
x = [[] for i in range(n)]
for i in range(n):
    x[i] = list(map(int, input().split()))
count = 0
for i in range(n):
    for j in range(i+1, n):
        norm2 = 0
        for k in range(d):
            norm2 += (x[i][k]-x[j][k])**2
        norm = math.sqrt(norm2)
        if int(norm)**2 == norm2:
            count += 1
print(count)


Measured memory_bytes: 38384
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int x,y,n,k;
	cin>>n>>k>>x>>y;
	n<=k?cout<<(unsigned long long)(n*x)<<endl:cout<<(unsigned long long)(x*k+y*(n-k))<<endl;
	return 0;
}

Measured memory_bytes: 256
#include<iostream>

using namespace std;

int main (){

    int i,n,sum = 0,m;
    cin >> i >> n;
    for(int l = 0; l < n; l++){
        cin >> m;
        sum =+ m + sum;
    }

    if(i < sum) cout << -1 << endl;
    else cout << i - sum << endl; 

    return 0;
}

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

int main() {
  int a, b, c, d; cin >> a >> b >> c >> d;
  int x = abs(a-b);
  int y = abs(b-c);
  if(a<b&&b<c){
    if(x<=d&&y<=d) cout << "Yes";
    else cout << "No";
  }
  else {
    if(abs(a-c)<=d) cout << "Yes";
    else cout << "No";
  }
}

Measured memory_bytes: 256
using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Linq;
using System.Linq.Expressions;
using System.Text;
class Simple {
    int N, M;
    int[] a, b, c;
    void Solve() {
        //input
        N = io.Int;
        M = io.Int;
        a = new int[M];
        b = new int[M];
        c = new int[M];
        for (int i = 0; i < M;++i){
            a[i] = io.Int;
            b[i] = io.Int;
            c[i] = io.Int;
            a[i]--;
            b[i]--;
        }
        //cal
        int INF = (int)1e9;
        int[,] shortestPath = new int[N, N];
        for (int i = 0; i < N; ++i)
            for (int j = 0; j < N; ++j)
                shortestPath[i, j] = INF;
        for (int i = 0; i < N; ++i)
            shortestPath[i, i] = 0;

        for (int i = 0; i < M; ++i)
            shortestPath[a[i], b[i]] = shortestPath[b[i], a[i]] = c[i];

        for (int i = 0; i < N; ++i)
            for (int j = 0; j < N; ++j)
                for (int k = 0; k < N; ++k)
                    shortestPath[j, k] = 
                        Math.Min(shortestPath[j, k],shortestPath[j, i] + shortestPath[i, k]);

        int ans = M;

        for (int i = 0; i < M; ++i)
            for (int j = 0; j < N; ++j)
                if (shortestPath[j, a[i]] + c[i] == shortestPath[j, b[i]]) {
                    ans--;
                    break;
                }
        //res
        Console.WriteLine(ans);

    }

    SimpleIO io = new SimpleIO();
    public static void Main(string[] args) { new Simple().Stream(); }
    void Stream() {
        Solve();
        io.writeFlush();
    }
}

class SimpleIO {
    string[] nextBuffer;
    int BufferCnt;
    char[] cs = new char[] { ' ' };
    StreamWriter sw = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
    public SimpleIO() {
        nextBuffer = new string[0];
        BufferCnt = 0;
        Console.SetOut(sw);
    }
    public string Next() {
        if (BufferCnt < nextBuffer.Length)
            return nextBuffer[BufferCnt++];
        string st = Console.ReadLine();
        while (st == "")
            st = Console.ReadLine();
        nextBuffer = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
        BufferCnt = 0;
        return nextBuffer[BufferCnt++];
    }
    public string String => Next();
    public char Char => char.Parse(String);
    public int Int => int.Parse(String);
    public long Long => long.Parse(String);
    public double Double => double.Parse(String);
    public void writeFlush() { Console.Out.Flush(); }
}


Measured memory_bytes: 11220
#include<iostream>
using namespace std;
int main(){
int a,b;
cin>>a>>b;
while(1)
{
if(a%3==0)
{
cout<<"Possible"<<endl;
break;
}
else if(b%3==0)
{
cout<<"Possible"<<endl;
break;
}
else if((a+b)%3==0)
{
cout<<"Possible"<<endl;
break;
}
else{
cout<<"Impossible"<<endl;
break;
}
}
return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int64_t i=0;i < (int64_t)(n);i++)
using namespace std;
//////全探索したいときに開けよ////////
vector<vector<int>> fspattern;
vector<int> fspattern_draft;
int fspcnt = 0;

void setfspattern_core(int floor,int number,int degree){
  if(floor==degree){
    fspattern.at(fspcnt) = fspattern_draft;
    fspcnt++;
  }else{
    rep(i,number){
      fspattern_draft.at(floor) = i;
      setfspattern_core(floor+1,number,degree);
    }
  }
}

void setfspattern(int number,int degree){
  int64_t array_num = 1;
  rep(i,degree){
    array_num *= number;
  }
  fspattern = vector<vector<int>>(array_num,vector<int>(degree));
  fspattern_draft = vector<int>(degree);
  setfspattern_core(0,number,degree);
}

//////nCrのmodを求めたいときに開けよ/////////
//int64_t univMod = 1000000007;
//int64_t factnum = 100000
//vector<int64_t> modfact(factnum);
//vector<int64_t> modinvfact(factnum);

/*void setmodfact(){
  for(int i=0;i<factnum;i++){
    if(i == 0){
      modfact.at(i) = 1;
    }else{
      modfact.at(i) = (modfact.at(i-1)*i)%univMod;
    }
  }
}

int64_t calcmodpower(int64_t a,int64_t n){
  int64_t res = 1;
  while(n != 0){
    if(n & 1){
      res = (res * a) % univMod;
    }
    a = (a*a) % univMod;
    n = n >> 1;
  }
  return res;
}

int64_t calcinverse(int64_t n){
	return calcmodpower(n,univMod-2);
}

void setmodinvfact(){
  for(int i=0;i<factnum;i++){
    if(i==0){
      modinvfact.at(i) = 1;
    }else{
      modinvfact.at(i) = calcmodpower(modfact.at(i),univMod-2);
    }
  }
}*/


/*
int64_t calcGCD(int64_t a,int64_t b){
	int64_t p = a;
	int64_t q = b;
	int64_t c = a%b;
	while(c != 0){
		p = q;
		q = c;
		c = p%q;
	}
	return q;
}
*/

int main(){
  int a,b;
  cin >> a >> b;
  if(a > 8 || b > 8){
    cout << ":(" << endl;
  }else{
    cout << "Yay!" << endl;
  }
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>
#include <string>
#include <cctype>
#include <cstdlib>
#include <set>
//#include <map>
#include <sstream>
using namespace  std;
#define  ll long long
#define mINF(a) memset(a,INF,sizeof(a))
#define m0(a) memset(a,0,sizeof(a))
#define mf1(a) memset(a,-1,sizeof(a))
#define lson i<<1,l,l+r>>1
#define rson i<<1|1,((l+r)>>1)+1,r
typedef pair<ll,ll>P;
static const ll INF=1e18;
static const ll len=1e4+7;
ll res[4][2]={-1,0,0,1,0,-1,1,0};
char map[60][60];
ll step[60][60];
ll n,m;
ll bfs()
{
	map[0][0]='#';
	step[0][0]=0;
	queue<ll>qu;
	qu.push(0);
	qu.push(0);
	while(!qu.empty())
	{
		ll x=qu.front();qu.pop();
		ll y=qu.front();qu.pop();
		if(x==n-1&&m-1==y)return step[x][y];
		for(ll i=0;i<4;++i)
		{
			ll dx=x+res[i][0];
			ll dy=y+res[i][1];
			if(dx>=0&&dx<n&&dy>=0&&dy<m&&map[dx][dy]=='.')
			{
				map[dx][dy]='#';
				step[dx][dy]=1+step[x][y];
				qu.push(dx);
				qu.push(dy);  	
			}	
		}	
	}
	return -1; 
}
int main()
{
	while(cin>>n>>m)
	{
		for(ll i=0;i<n;++i)
			cin>>map[i];
		ll sum=0;
		for(ll i=0;i<n;++i)
		{
			for(ll j=0;j<m;++j)
				if(map[i][j]=='.')
					sum++;
		}
		ll ss=bfs();
		if(ss==-1)puts("-1");
		else printf("%lld\n",sum-ss-1);
	}
    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#define P(s,t) printf("%d"s,t);
#define F(i,c) for(i=0;i<c;i++)
int main(void) {
	int r,c,i,j,v;
	int sr, *sc;
	scanf("%d %d", &r, &c); 
	sc = (int *)calloc(c + 1, sizeof(int));
	F(i,r){
		sr = 0;
		F(j,c) {
			scanf("%d", &v);
			sr += v;
			sc[j] += v;
			P(" ",v)
		}
		sc[c] += sr;
		P("\n",sr)
	}
	F(j,c) {
		P(" ",sc[j])
	}
	P("\n",sc[c])
	return 0;	
}

Measured memory_bytes: 612
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include <math.h>
#include <limits.h>
char lowcmp[26]="abcdefghijklmnopqrstuvwxyz";
char upcmp[26]="ABCDEFGHIJKLMNOPQRSTUVWXYZ";
long long mod=1000000007;
int max(int a, int b){return a>b?a:b;}
int min(int a, int b){return a<b?a:b;}
int gcd(int a, int b){return min(a,b)==0?max(a,b):gcd(min(a,b),max(a,b)%min(a,b));}
long long llmax(long long a, long long b){return a>b?a:b;}
long long llmin(long long a, long long b){return a<b?a:b;}
long long llgcd(long long a, long long b){return llmin(a,b)==0?llmax(a,b):llgcd(llmin(a,b),llmax(a,b)%llmin(a,b));}
int assort(const void *a, const void *b){return *(int*)a-*(int*)b;}
int dessort(const void *a, const void *b){return *(int*)b-*(int*)a;}
int llassort(const void *a, const void *b){return *(long long*)a-*(long long*)b;}
int lldessort(const void *a, const void *b){return *(long long*)b-*(long long*)a;}
int charassort(const void *a, const void *b){return strcmp((char*)a ,(char*)b);}
int chardessort(const void *a, const void *b){return strcmp((char*)b ,(char*)a);}
int ntoi(char c){return c-'0';}
int ltoi(char c){return c-'a';}
int utoi(char c){return c-'A';}
long long ncr(int a,int b){long long ans=1;for(int i=0;i<b;i++){ans=ans*(a-i)/(i+1);}return(ans);}
long long npr(int a,int b){long long ans=1;for(int i=0;i<b;i++){ans=ans*(a-i);}return(ans);}


int main(void){
    char s[5];
    scanf("%s",s);
    if (strlen(s)==2){
        printf("%s\n",s);
    } else {
        printf("%c%c%c\n",s[2],s[1],s[0]);
    }
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
	return 0 ;
}

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

const int maxn = 1e5+5;
int N, M;
int indegree[maxn];
vector<int> dir[maxn], rev[maxn];
int order[maxn];
int par[maxn];

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    cin >> N >> M;
    for (int i = 0; i < N - 1 + M; i++) {
        int a, b; cin >> a >> b;
        dir[a].push_back(b);
        rev[b].push_back(a);
        indegree[b]++;
    }
    queue<int> q;
    for (int i = 1; i <= N; i++) if (indegree[i] == 0) q.push(i);
    int ta = 1;
    while (!q.empty()) {
        int f = q.front(); q.pop();
        order[f] = ta++;
        for (int j: dir[f]) {
            if (--indegree[j] == 0) {
                q.push(j);
            }
        }
    }
    for (int i = 1; i <= N; i++) {
        pair<int,int> best = {-1,0};
        for (int j: rev[i]) {
            if (best.first < order[j]) {
                best.first = order[j];
                best.second = j;
            }
        }
        par[i] = best.second;
    }

    for (int i = 1; i <= N; i++) {
        cout << par[i] << '\n';
    }


    return 0;
}


Measured memory_bytes: 12928
/*
00:42 - 01:17
 */

#include<iostream>
#include<algorithm>
#include<climits>
#include<cstdio>

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)
#define IINF (INT_MAX)
#define MAX 31
using namespace std;

int H,W;
bool used[MAX][MAX];
char G[MAX][MAX];
int sp,mincost;
int dx[] = {0,1,0,-1};
int dy[] = {1,0,-1,0};

inline bool isValid(int x,int y){ return ( 0 <= x && x < W && 0 <= y && y < H); }

void dfs(int cur,int cost,int pdir){

  if(cost >= 10)return;
  if(mincost <= cost)return;
  int x = cur % W, y = cur / W;

  if(G[y][x] == '>'){
    mincost = min(mincost,cost);
    return;
  }

  if(used[y][x])return;

  rep(i,4){
    if(i == pdir)continue;

    int rnx = x + dx[(i+2)%4], rny = y + dy[(i+2)%4];//テヲツャツ。テ」ツ?ォテゥツ?イテ」ツつ?ヲツ鳴ケテ・ツ青妥」ツ?ョテゥツ??
    if( G[rny][rnx] == '#' ){

      used[y][x] = true;
      int nx = x + dx[i], ny = y + dy[i];
      while( G[ny][nx] == '_' ){ 
	if( G[ny+dy[i]][nx+dx[i]] == '^' )break;
	if( G[ny+dy[i]][nx+dx[i]] == '_'){
	  G[ny+dy[i]][nx+dx[i]] = '#';
	  dfs(nx+ny*W,cost+1,(i+2)%4);
	  G[ny+dy[i]][nx+dx[i]] = '_';
	}
	  nx += dx[i], ny += dy[i];
      }
      if( G[ny][nx] == '>' )dfs(nx+ny*W,cost,(i+2)%4);
      if( G[ny][nx] == '#'){
	nx -= dx[i], ny -= dy[i];
	dfs(nx+ny*W,cost,(i+2)%4);
      }
      used[y][x] = false;
    } else if( rnx+rny*W != sp && G[rny][rnx] == '_' ) {
      G[rny][rnx] = '#';
      dfs(cur,cost+1,pdir);
      G[rny][rnx] = '_';
    }
  }
}

int main(){
  int T;
  scanf("%d",&T);
  while(T--){
    scanf("%d %d",&H,&W);
    rep(y,H)rep(x,W){
      cin >> G[y][x];
      if(G[y][x] == 'A')sp = x + y * W, G[y][x] = '_';
      used[y][x] = false;
    }
    
    mincost = IINF;
    dfs(sp,0,IINF);
    if(mincost == IINF)puts("10");
    else               printf("%d\n",mincost);

  }
  return 0;
}

Measured memory_bytes: 1232
import sys
input = sys.stdin.readline
N = int(input())
R = []
B = []
ans = 0
for i in range(N):
  a,b = map(int,input().split())
  R.append((a,b))
for i in range(N):
  c,d = map(int,input().split())
  B.append((c,d))
R.sort(key=lambda x:x[0])
B.sort(key=lambda x:x[0])
H = []
l = 0
for i in range(N):
  for j in range(l,N):
    if R[j][0] > B[i][0]:
      l = j
      break
    H.append(R[j])
  H.sort(key=lambda x:x[1], reverse=True)
  for k in range(len(H)):
    if H[k][1] < B[i][1]:
      H.pop(k)
      ans += 1
      break
print(ans)

Measured memory_bytes: 3064
def count_a(A, x):
    low = -1
    high = N
    while high - low > 1:
        mid = (high + low) // 2
        if A[mid] < x:
            low = mid
        else:
            high = mid
    return low + 1

def count_c(C, y):
    low = -1
    high = N
    while high - low > 1:
        mid = (high + low) // 2
        if C[mid] > y:
            high = mid
        else:
            low = mid
    return N - high

N = int(input())

A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

A.sort()
B.sort()
C.sort()

ans = 0
A_min = A[0]
C_max = C[-1]

for b in B:
    if b <= A_min or b >= C_max:
        continue

    ans += count_a(A, b) * count_c(C, b)

print(ans)

Measured memory_bytes: 24180
//#define _GLIBCXX_DEBUG

#include<bits/stdc++.h>
#define PI 3.14159265359
using namespace std;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
const int INF= 1e9+5;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll> >vvl;
typedef pair<ll,ll> P;
typedef tuple<ll,ll,ll> T;
const ll MOD=1000000007LL;
ll comb(ll n,ll r){
  if(r>n)return 0;
  ll res=1;
  for(ll i=n;i>=n-r+1;i--)res*=i;
  for(ll i=1;i<=r;i++)res/=i;
  return res;
}
int main(){
  int n;
  cin>>n;
  vvl count(10,vl(10,0));
  for(int i=1;i<=n;i++){
    string s=to_string(i);
    count[s[0]-'0'][i%10]++;
  }
  //rep(i,10){
    //rep(j,10)cout<<count[i][j]<<" ";
    //cout<<endl;
  //}
  ll ans=0;
  for(int i=0;i<9;i++){
    for(int j=i+1;j<10;j++){
      ans+=count[i][j]*count[j][i]*2;
      //cout<<count[i][j]*count[j][i]<<endl;
    }
  }
  for(int i=0;i<10;i++){
      ans+=count[i][i]*count[i][i];
  }
  cout<<ans<<endl;
}
                        
            

Measured memory_bytes: 256
my ($x, $n) = glob <>;
my @p = glob <>;

my $minus_cursor = $x;
my $plus_cursor = $x;
my $ans;

while(1) {
    unless (grep { $minus_cursor == $_ } @p) {
        $ans = $minus_cursor;
        last;
    };

    unless (grep { $plus_cursor == $_ } @p) {
        $ans = $plus_cursor;
        last;
    };
    --$minus_cursor;
    ++$plus_cursor;
}

print $ans;

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

#define For(i, l, r) for(register int i = (l), i##end = (int)(r); i <= i##end; ++i)
#define Fordown(i, r, l) for(register int i = (r), i##end = (int)(l); i >= i##end; --i)
#define Set(a, v) memset(a, v, sizeof(a))
#define Cpy(a, b) memcpy(a, b, sizeof(a))
#define debug(x) cout << #x << ": " << (x) << endl
#define DEBUG(...) fprintf(stderr, __VA_ARGS__)

using namespace std;

template<typename T> inline bool chkmin(T &a, T b) { return b < a ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, T b) { return b > a ? a = b, 1 : 0; }

inline int read() {
	int x(0), sgn(1); char ch(getchar());
	for (; !isdigit(ch); ch = getchar()) if (ch == '-') sgn = -1;
	for (; isdigit(ch); ch = getchar()) x = (x * 10) + (ch ^ 48);
	return x * sgn;
}

void File() {
#ifdef zjp_shadow
	freopen ("duliu.in", "r", stdin);
	freopen ("duliu.out", "w", stdout);
#endif
}

const int N = 1e5 + 1e3;

int n, a[N], b[N], va[N], vb[N], fa[N];

int find(int x) { return x == fa[x] ? x : fa[x] = find(fa[x]); }

int tot;
inline int find_pos(int x) {
	return lower_bound(va + 1, va + tot + 1, x) - va;
}

bitset<N> vis;

int main () {

	File();

	n = read() + 1;

	For (i, 1, n - 1)
		a[i] = read(), a[n] ^= a[i];
	For (i, 1, n - 1)
		b[i] = read(), b[n] ^= b[i];

	For (i, 1, n)
		va[i] = a[i], vb[i] = b[i];
	sort(va + 1, va + n + 1);
	sort(vb + 1, vb + n + 1);

	For (i, 1, n)
		if(va[i] != vb[i]) return puts("-1"), 0;

	tot = unique(va + 1, va + n + 1) - va - 1;
	For (i, 1, tot) fa[i] = i;

	For (i, 1, n) {
		a[i] = find_pos(a[i]); b[i] = find_pos(b[i]);
		int rtx = find(a[i]), rty = find(b[i]);
		if (rtx != rty) fa[rtx] = rty;
	}

	int ans = 0, sum = 0;
	For (i, 1, n - 1) if (a[i] != b[i])
		++ ans, vis[a[i]] = vis[b[i]] = true;
	vis[a[n]] = vis[b[n]] = true;

	For (i, 1, n) if (vis[i] && find(i) == i) ++ sum;

	printf ("%d\n", ans + max(0, sum - 1));

	return 0;

}


Measured memory_bytes: 3840