akhauriyash/Code-Regression huggingface dataset:
N = int(input())
red = [list(map(int, input().split())) for _ in range(N)]
blue = [list(map(int, input().split())) for _ in range(N)]
ans = 0
red = sorted(red, key = lambda x:x[1] * -1)
blue = sorted(blue)
for b in blue:
	for r in red:
		if b[0] > r[0] and b[1] > r[1]:
			ans += 1
			red.remove(r)
			break
print(ans)


Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
#define fol(i,n) for(int i=0;i<n;++i)
#define pb push_back
typedef long long ll;
typedef pair<int,int> P;
typedef vector<P> vip;

int main(){
  int n;cin>>n;
  int a[n];
  ll ans = 0;
  int c = 0;
  int b1 = 1000000001,b2 = -1000000001;
  fol(i,n){
    cin>>a[i];
    if(a[i] < 0){
      ans -= a[i];
      b2 = max(b2,a[i]);
      c++;
    }else{
      ans += a[i];
      b1 = min(b1,a[i]);
    }

  }
  // printf("%d %d %d\n",ans,b1,b2 );
  sort(a,a+n);
  if(c%2!=0){
    ans -= abs(b1)+abs(b2);
    if(-b2 > b1){
      ans += -(b1+b2);
    }else{
      ans += +(b1+b2);
    }
  }

  cout << ans << endl;
  return 0;
}


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

int N, M, K, ans[200006], cou, group[200006], hate[200006][2], num[200006];
vector<int> fri[200006];

void dfs(int T) {
	for (auto x:fri[T]) {
		if (group[x] == 0) {
			group[x] = group[T];
			num[group[T]]++;
			dfs(x);
		}
	}
}

int main() {
	scanf("%d %d %d", &N, &M, &K);
	cou = 1;
	for (int i = 0; i < M; i++) {
		int temp1, temp2;
		scanf("%d %d", &temp1, &temp2);
		fri[temp1].push_back(temp2);
		fri[temp2].push_back(temp1);
	}
	for (int i = 0; i < K; i++) {
		int temp1, temp2;
		scanf("%d %d", &temp1, &temp2);
		hate[i][0] = temp1;
		hate[i][1] = temp2;
	}
	for (int i = 1; i <= N; i++) {
		if (group[i] == 0) {
			group[i] = cou;
			num[cou] = 1;
			cou++;
			dfs(i);
		}
	}
	//cout << cou << endl;
	for (int i = 1; i <= N; i++) {
		ans[i] = num[group[i]] - 1 - fri[i].size();
	}
	for (int i = 0; i < K; i++) {
		if (group[hate[i][0]] == group[hate[i][1]]) {
			ans[hate[i][0]]--;
			ans[hate[i][1]]--;
		}
	}
	for (int i = 1; i <= N; i++) {
		printf("%d ", ans[i]);
	}
	printf("\n");
	return 0;
}

Measured memory_bytes: 12544
#include <bits/stdc++.h>
typedef long long ll;
#define rep(i,a,n) for(ll i = a;i < n;i++)
#define rrep(i,a,n) for(ll i = n; i >= a;i--)
#define LINF 1e18
#define INF 1e9
using namespace std;

#define P pair<ll,ll>
#define fs first
#define sc second

int main(){
    ll n,ans = 0,memo = 1;
    cin >> n;
    while(n > 0){   
        n = floor(n/2);
        ans += memo;
        memo *= 2;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cstring>
#include<stdlib.h>
using namespace std;

typedef struct _P
{
    char name[16];
    int t;
}P;

// queue def
#define QSIZ 100010
P Q[QSIZ];
int head=0, tail=0;

void Enque(P q){
    if((tail+1)%QSIZ == head) {
        printf("FULL!!\n");
        return;
    }
    
    strcpy(Q[tail].name, q.name);
    Q[tail].t = q.t;

    tail = (tail + 1) % QSIZ;
}

P Deque(){
    P nl = {"---", -1};
    if(head == tail) {
        printf("EMPTY!!\n");
        return nl;
    }
   
    P q = Q[head];
    head = (head + 1) % QSIZ;

    return q;
}

void show(P p)
{
    printf("%s %d\n", p.name, p.t);
}

int main(void)
{
    // inupt
    int n, q;
    scanf("%d %d", &n, &q);

    for(int i=0;i<n;i++){
        scanf("%s", Q[i].name);
        scanf("%d", &Q[i].t);
    }
    tail = n;

    int time = 0, cnt = 0;
    while(true){
        P p = Deque();
        p.t -= q;
        if(p.t > 0){
            time += q;
            Enque(p);
        }
        else{
            time += (q + p.t);
            p.t = time;
            show(p);
            cnt++;
            if(cnt == n) break;
        }
    }


    return 0;
}



Measured memory_bytes: 5164
N, Y = map(int,(input().split()))
ans = [-1,-1,-1]
for x in range(0,N+1):
  for y in range(0,N-x+1):
    z = N - x - y
    if 10000 * x + 5000 * y + 1000 * z == Y:
      ans[0] = x
      ans[1] = y
      ans[2] = z
print(ans[0],ans[1],ans[2])

Measured memory_bytes: 3064
N, M = map(int, input().split())
p = [list(map(str, input().split())) for _ in range(M)]
aclst = [0] * (N + 1)
walst = [0] * (N + 1)
cntw = 0
cnta = 0
for i in range(M):
    if aclst[int(p[i][0])] == 0:
        if p[i][1] == 'WA':
            walst[int(p[i][0])] += 1
        else:
            cnta += 1
            cntw += walst[int(p[i][0])]
            aclst[int(p[i][0])] = 1


print(cnta, cntw)

Measured memory_bytes: 33712
from fractions import gcd

N, M = map(int, input().split())
a = list(map(int, input().split()))
b = [0] * N
for i in range(N):
	tmp = a[i]
	while tmp & 1 == 0:
		tmp = tmp>>1
		b[i] += 1

same = True
ct = b[0]
for i in range(1, N):
	if b[i] != ct:
		same = False
if not same:
	print(0)
else:
	plcm = 1
	for i in range(N):
		if plcm > M:
			plcm = M+1
		else:
			a[i] //= 2
			plcm = plcm * (a[i] // gcd(plcm, a[i]))
	if plcm > M:
		print(0)
	else:
		ansd = M // plcm
		ans = (ansd + 1)//2
		print(ans)

Measured memory_bytes: 16320
import java.util.Arrays;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] a = new int[n];

		for (int i = 0; i < n; i++) {
			a[i] = sc.nextInt();
		}
		Arrays.sort(a);
		int alice, bob;
		alice = bob = 0;
		for (int i = 0; i < n; i++) {
			if (i % 2 == 0) {
				alice += a[i];
			} else {
				bob += a[i];
			}
		}
		if (alice > bob) {
			System.out.println(alice - bob);
		} else {
			System.out.println(bob - alice);
		}
	}
}

Measured memory_bytes: 23892
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

int main(void){
    int i,j,k;
    int n;
    int p[22];
    int count = 0;
    
    scanf("%d",&n);
    for(i = 0;i < n-1;i++){
        scanf("%d\n",&p[i]);
    }
    scanf("%d",&p[i]);
    
    for(i = 1;i < n-1;i++){
        if(p[i] < p[i-1] && p[i] > p[i+1]){
            count++;
        }else if(p[i] > p[i-1] && p[i] < p[i+1]){
            count++;
        }
    }
    
    printf("%d\n",count);
    return 0;
}





Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
int sod(int c){
     int sum = 0;
     while(c!=0){
          sum+=(c%10);
          c=c/10;
          
     }
     return sum;
}
int main() {
     long long int N;
     cin >> N;
     int digits = 0;
     int c = N;
     int mina = 9999;
     for(int i=1;i<N;i+=9){
          
          int A = i;
          int B = N-A;
          int ans = sod(A)+sod(B);
          if((ans)<mina){
               mina = ans;
          }
     }
     cout << mina;
}

Measured memory_bytes: 3628
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxm=1e5+5;
vector<int>x[maxm];
vector<int>y[maxm];
pair<int,int>p[maxm];
set<int>xx[maxm];
set<int>yy[maxm];
int pre[maxm];
int cnt[maxm];
int n;
int ffind(int x){
    return pre[x]==x?x:pre[x]=ffind(pre[x]);
}
void add(int a,int b){
    int x=ffind(a),y=ffind(b);
    if(x==y)return ;
    int ma1=max(xx[x].size(),yy[x].size());
    int ma2=max(xx[y].size(),yy[y].size());
    if(ma1<ma2)swap(x,y),swap(a,b);
    pre[y]=x;
    cnt[x]+=cnt[y];
    for(auto i:xx[y]){
        xx[x].insert(i);
    }
    for(auto i:yy[y]){
        yy[x].insert(i);
    }
}
signed main(){
    ios::sync_with_stdio(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>p[i].first>>p[i].second;
        x[p[i].first].push_back(i);
        y[p[i].second].push_back(i);
    }
    for(int i=1;i<=n;i++){
        pre[i]=i;
        cnt[i]=1;
        xx[i].insert(p[i].first);
        yy[i].insert(p[i].second);
    }
    for(int i=1;i<=1e5;i++){
        int len=x[i].size();
        for(int j=1;j<len;j++){
            add(x[i][0],x[i][j]);
        }
        len=y[i].size();
        for(int j=1;j<len;j++){
            add(y[i][0],y[i][j]);
        }
    }
    int ans=0;
    for(int i=1;i<=n;i++){
        if(pre[i]==i){
//            cout<<xx[i].size()<<' '<<yy[i].size()<<' '<<cnt[i]<<endl;
            ans+=(int)(xx[i].size()*yy[i].size())-cnt[i];
        }
    }
    cout<<ans<<endl;
    return 0;
}
/*

*/


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

using namespace std;

typedef long long ll;

int main() {
	int N, S;
	ll dp[11][11][101] = {0}; dp[0][0][0] = 1;
	for (int i = 0; i < 10; ++i) {
		for (int j = 0; j <= 10; ++j) {
			for (int k = 0; k <= 100; ++k) {
				if (dp[i][j][k]) {
					dp[i+1][j][k] += dp[i][j][k];
					int nj = j + 1;
					int nk = k + i;
					if (nj <= 10 && nk <= 100) {
						dp[i+1][nj][nk] += dp[i][j][k];
//						cout << i+1 << " " << nj << " " << nk << endl;
					}
				}
			}
		}
	}
	while (cin >> N >> S, N || S) {
		cout << dp[10][N][S] << endl;
	}
}

Measured memory_bytes: 1256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
typedef vector<vector<ll> > Graph;
const ll INF = 100000000;
#define rep1(i, n) for (ll i=0; i<(n); i++) 
#define rep2(i, k, n) for (ll i=k; i<(n); i++)
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }


vector<bool> seen;
void dfs(const Graph &G, ll v, P rm) {
    seen[v] = true;

    for (auto next_v : G[v]) {
        if (seen[next_v]) continue;
        if (rm==make_pair(min(v, next_v), max(v, next_v))) continue;
        dfs(G, next_v, rm);
    }
}


int main() {
    ll N, M; cin >> N >> M;

    Graph G(N);
    vector<P> r;
    for (ll i = 0; i < M; ++i) {
        ll a, b;
        cin >> a >> b;
        a--; b--;
        G[a].push_back(b);
        G[b].push_back(a);
        r.push_back(make_pair(min(a, b), max(a, b)));
    }
    ll ans = 0;
    for (ll i = 0; i < M; ++i) {
        seen.assign(N, false);
        dfs(G, 0, r[i]);
        bool check = true;
        for (ll j = 0; j < N; ++j) if (!seen[j]) check = false;
        if (!check) ans++;
    }
    cout << ans << endl;
}

Measured memory_bytes: 3600
#include <iostream>

int main(void){

	double th1, th2, temp, answer;

	std::cin >> th1 >> th2;
	
	if(th1>th2){
		temp = th1;
		th1 = th2;
		th2 = temp;
	}

	if(th2 - th1 < 180.0){
		answer = (th1+th2) / 2.0;
	}else{
		answer = ( th1+(th2-360) ) / 2.0;
	}
	if(answer<0) answer = 360.0 + answer;

	std::cout << answer << std::endl;

	return 0;
}



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

#define ll long long int
#define mp make_pair
#define pb push_back
#define fi first
#define si second
#define fastIO ios_base::sync_with_stdio(false); cin.tie(NULL);
#define F(a,n) for(int i=0;i<n;i++){cin>>a[i];}
#define F1(a,n) for(int i=1;i<=n;i++){cin>>a[i];}
#define P(a,n) for(int i=0;i<n;i++){cout<<a[i]<<' ';}cout<<endl;
#define P1(a,n) for(int i=1;i<=n;i++){cout<<a[i]<<' ';}cout<<endl;
#define NF(a,n,m) for(int i=0;i<n;i++){for(int j=0;j<m;j++){cin>>a[i][j];}}
#define NF1(a,n,m) for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cin>>a[i][j];}}
#define PNF(a,n,m) for(int i=0;i<n;i++){for(int j=0;j<m;j++){cout<<a[i][j]<<' ';}cout<<endl;}cout<<endl;
#define PNF1(a,n,m) for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cout<<a[i][j]<<' ';}cout<<endl;}cout<<endl;
#define AS 200001
#define mod 1000000007
#define inf (1LL<<60)
ll dp[3001][3001];
ll sum[3001][3001];
ll solve(vector<int>&v, int i, int j) {
	if (i == j)
		return 0;
	if (dp[i][j] != -1)
		return dp[i][j];
	ll minCost=inf;
	for (int k = i; k < j; k++) {
		minCost = min(minCost, sum[i][j] + solve(v, i, k) + solve(v, k + 1, j));
	}
	return dp[i][j] = minCost;
}
void preprocess(vector<int>&v, int n) {
	for (int i = 1; i <= n; i++) {
		for (int j = i; j <= n; j++) {
			sum[i][j] = v[j] + ((j == i) ? 0 : sum[i][j - 1]);
		} 
	}
}
int main() {
	fastIO
	int n;
	cin >> n;
	vector<int>v;
	memset(dp, -1, sizeof dp);
	v.resize(n + 1);
	
	F1(v, n);
	preprocess(v, n);
	// P1(v, n);
	cout << solve(v, 1, n);
}

Measured memory_bytes: 80128
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m+1;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define llong long long
#define pb(a) push_back(a)
#define INF 999999999
using namespace std;
typedef pair<int, int> P;
typedef pair<llong, llong> LP;
typedef pair<int, P> PP;
typedef pair<llong, LP> LPP;

llong mod = 1000000007;
int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};

int main(){
  string S;cin >>S;
  char tem= S[0];
  int a=1;
  REP(i,3){
    tem =S[i];
    if(S[i+1]==tem)a=0;
  }
  if(a){
    std::cout << "Good" << '\n';
  }else{

    std::cout << "Bad" << '\n';
  }
}


Measured memory_bytes: 256
node = Struct.new(:key, :parent, :left, :right)
root = nil

insert = ->(z) {
  y = nil
  x = root
  while x
    y = x
    x = (z.key < x.key) ? x.left : x.right
  end
  z.parent = y
  
  if y.nil?
    root = z
  elsif z.key < y.key
    y.left = z
  else
    y.right = z
  end
}

inorder = ->(x) {
  a = x.left
  inorder.(a) if a
  print " " + x.key.to_s
  a = x.right
  inorder.(a) if a
}

preorder = ->(x) {
  print " " + x.key.to_s
  a = x.left
  preorder.(a) if a
  a = x.right
  preorder.(a) if a
}

gets.to_i.times do
  command = gets.split(" ")
  case command[0]
  when "insert"
    z = node.new
    z.key = command[1].to_i
    insert.(z)
  when "print"
    inorder.(root)
    puts
    preorder.(root)
    puts
  end
end


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

int main() {
  string s; cin >>s;
  int n = s.size();
  int cnt0 = 0, cnt1 = 0;
  for (int i=0; i<n; i++){
    if (s.at(i)=='0') cnt0++;
    else cnt1++;
  }
  int ans = min(cnt0,cnt1)*2;
  
  cout <<ans;
  cout <<endl;
}

Measured memory_bytes: 512
import bisect


def calc_pairs(p, A):
    # （Aは昇順にソート済であることが前提）
    # 和の値がp以上となる組の個数を返す
    pairs = 0
    N = len(A)
    for a in A:
        j = bisect.bisect_left(A, p - a)
        pairs += N - j
    return pairs


def main():
    N, M = list(map(int, input().split(' ')))
    A = list(map(int, input().split(' ')))
    A.sort()
    cumsum_A = [a for a in A]
    for i in range(1, N):
        cumsum_A[i] += cumsum_A[i - 1]
    # 次を満たす最大のpを求める：「和がp以上となる組の数がM以上」
    ok, ng = 0, 2 * A[-1] + 1
    while ng - ok > 1:
        mid = (ok + ng) // 2
        if calc_pairs(mid, A) >= M:
            ok = mid
        else:
            ng = mid
    # 和がp(=ok)以上となる組の値の合計を出す
    ans = 0
    for a in A:
        index = bisect.bisect_left(A, ok - a)
        v = (N - index) * a + cumsum_A[N - 1] - (0 if index == 0 else cumsum_A[index - 1])
        ans += v
    # M組を超えてしまった分を差し引く
    pairs = calc_pairs(ok, A)
    ans -= (pairs - M) * ok
    print(ans)


if __name__ == '__main__':
    main()

Measured memory_bytes: 90968
#include<iostream>

using namespace std;

int J[1001][1001], O[1001][1001], I[1001][1001];
int main(){
    int M, N;
    cin>> M>> N;
    int K;
    cin>> K;
    string fld[M];
    for(int i=0; i<M; i++){
        cin>> fld[i];
    }

    for(int i=1; i<=M; i++){
        for(int j=1; j<=N; j++){
            if(fld[i-1][j-1]=='J') J[i][j]=1;
            if(fld[i-1][j-1]=='O') O[i][j]=1;
            if(fld[i-1][j-1]=='I') I[i][j]=1;
        }
    }
    for(int i=0; i<M; i++){
        for(int j=0; j<N; j++){
            J[i+1][j+1]+=J[i+1][j];
            O[i+1][j+1]+=O[i+1][j];
            I[i+1][j+1]+=I[i+1][j];
        }
    }
    for(int i=0; i<M; i++){
        for(int j=0; j<N; j++){
            J[i+1][j+1]+=J[i][j+1];
            O[i+1][j+1]+=O[i][j+1];
            I[i+1][j+1]+=I[i][j+1];
        }
    }

    for(int k=0; k<K; k++){
        int a, b, c, d;
        scanf("%d %d %d %d", &a, &b, &c, &d);
        int j=J[c][d]-J[a-1][d]-J[c][b-1]+J[a-1][b-1];
        int o=O[c][d]-O[a-1][d]-O[c][b-1]+O[a-1][b-1];
        int i=I[c][d]-I[a-1][d]-I[c][b-1]+I[a-1][b-1];
        printf("%d %d %d\n", j, o, i);
    }

    return 0;
}

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

char chess(int h, int w) {
  if((h+w)%2==0) {
    return '#';
  }
  return '.';
}

int main()
{
  int H, W;
  while(true) {
    cin >> H >> W;
    if (H == 0 && W == 0) {
      break;
    }
    for(int i = 0; i < H; i++) {
      for(int j = 0; j < W; j++) {
        cout << chess(i,j);
      }
      cout << endl;
    }
    cout << endl;
  }
}



Measured memory_bytes: 3096
#include <iostream>
#include <algorithm>
#define INF 1000000000
#define int long long
using namespace std;
int n,W;
int w[105],v[105];
int dp[105][100005];
signed main(){
  cin.tie(NULL);
  ios::sync_with_stdio(false);
  cin>>n>>W;
  for(int i=0;i<n;i++){
    cin>>w[i]>>v[i];
  }
  for(int i=0;i<=W;i++){
    dp[0][i]=0;
  }
  for(int i=0;i<n;i++){
    for(int j=0;j<=W;j++){
      if(w[i]<=j){
	dp[i+1][j]=max(dp[i][j-w[i]]+v[i],dp[i][j]);
      }
      else{
	dp[i+1][j]=dp[i][j];
      }
    }
  }
  cout<<dp[n][W]<<"\n";
  
  return 0;
}


Measured memory_bytes: 82484
N = int(input())
S = list(input())

ans = 0
for i in range(1,N-1):
    X = set(S[:i])
    Y = set(S[i:])
    tmp = 0
    for j in X:
        if j in Y:
            tmp += 1
    ans = max(ans,tmp)

print(ans)


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

#define BR "\n"
#define SP " "
#define SHOW(x) for(int i = 0; i < x.size(); i++) { cout << x[i] << SP; } cout << BR;
#define SHOW2(x) for(int j = 0; j < x.size(); j++) { SHOW(x[j]); } cout << BR;

int main() {
  ll M, D;
  cin >> M >> D;

  ll ans = 0;
  for (int i = 20; i <= D; i++) {
    ll d1 = i / 10;
    ll d2 = i % 10;
    if (d1 >= 2 && d2 >= 2 && d1 * d2 <= M) {
      // cout << d1 << SP << d2 << BR;
      ans++;
    }
  }
  
  cout << ans << BR;
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <stack>
#include <queue>
#include <numeric>
#include <iomanip>
#include <map>
#include <set>
#include <deque>
#include <utility>
using namespace std;
using ll = long long;
#define rep(i, n) for (int i = 0; i < n; i++)
#define repk(i, k, n) for (int i = k; i < n; i++)
#define MOD 1e9 + 7
#define INF 1e9
#define SENTINEL 2e9
#define PIE 3.14159265358979323

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;}
template <class T>
inline T GCD(T a, T b){if (b == 0) return a; else return GCD(b, a % b);}
template <class T>
inline T LCM(T a, T b) {return (a * b) / GCD(a, b);}

void ans(bool flag){
    if (flag)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
}

int main(){
    int n,k,x,y;
    cin>>n>>k>>x>>y;
    if(n<=k)
        cout << n * x << endl;
    else
        cout << x * k + (n - k) * y << endl;
}

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

using namespace std;

#define fst(t) std::get<0>(t)
#define snd(t) std::get<1>(t)
#define thd(t) std::get<2>(t)
#define unless(p) if(!(p))
#define until(p) while(!(p))

using ll = long long;
using P = std::tuple<int,int>;

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

int N, M;
P ps[100100];

int rec(int l, int r, int idx, int numBrokenBridge){
    if(idx == M){
        return numBrokenBridge + 1;
    }

    int a = fst(ps[idx]), b = snd(ps[idx]);
    if(l <= a && b <= r){
        return rec(a, b, idx + 1, numBrokenBridge);
    }else if(l <= a && a <= r){
        return rec(a, r, idx + 1, numBrokenBridge);
    }

    return rec(a, b, idx + 1, numBrokenBridge + 1);
}

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

    std::cin >> N >> M;

    for(int i=0;i<M;++i){
        std::cin >> fst(ps[i]) >> snd(ps[i]);
        snd(ps[i]) -= 1;
    }

    sort(ps, ps+M);

    int res = rec(fst(ps[0]), snd(ps[0]), 1, 0);
    std::cout << res << std::endl;
}


Measured memory_bytes: 1024
#include <iostream>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <utility>
#include <algorithm>
#include <numeric>
#include <cassert>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
using namespace std;

typedef vector<int> vi;
typedef pair<int,int> ii;
#define sz(a) int((a).size())
#define all(c) (c).begin(), (c).end()

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

	string s;
	cin >> s;
	for (int i = 0; i < s.length(); i += 2) {
		if (s[i] != 'R' && s[i] != 'U' && s[i] != 'D') {
			cout << "No\n";
			return 0;
		}
	}
	for (int i = 1; i < s.length(); i += 2) {
		if (s[i] != 'L' && s[i] != 'U' && s[i] != 'D') {
			cout << "No\n";
			return 0;
		}
	}
	cout << "Yes\n";
}


Measured memory_bytes: 256
#include <stdio.h>
#include <cstdio>
#include <iostream>
#include <iomanip>
#include <queue>
#include <set>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <complex>

using ll = long long int;
using namespace std;

int main(){
  
  ll H, W, K;
  string sttrtmp;
  vector<string> S;

  cin >> H >> W >> K;
  for(ll i = 0; i < H; i++){
    cin >> sttrtmp;
    S.push_back(sttrtmp);
  }

  // solve problem
  vector<int> group(H);
  vector<int> count(H);

  ll tmp_group, tmp_ans;
  ll ans = 1e9;
  ll flag;
  ll last_cut;

  for(ll i = 0; i < (1 << (H-1)); i++){

    tmp_ans = 0;
    last_cut = -2;

    // make group
    tmp_group = 0;
    group[0] = 0;
    for(ll j = 0; j < H-1; j++){
      if((i>>j)&1){
        tmp_group++;
        tmp_ans++;
      }
      group[j+1] = tmp_group;
    }

    // reset count
    for(ll j = 0; j < H; j++){
      count[j] = 0;
    }

    for(ll j = 0; j < W; j++){
      // update count
      for(ll k = 0; k < H; k++){
        if(S[k][j] == '1'){
          count[group[k]]++;
        }
      }
      // check current count
      flag = 0;
      for(ll k = 0; k <= tmp_group; k++){
        if(count[k] == K){
          flag = max(flag, 1LL);
        }
        if(count[k] > K){
          flag = max(flag, 2LL);
          break;
        }
      }
      /*if(flag == 1 && j != W-1){
        tmp_ans++;
        // reset count
        for(ll k = 0; k < H; k++){
          count[k] = 0;
        }
        last_cut = j;
      }*/
      if(flag == 2){
        if(j == last_cut+1){
          tmp_ans = 1e9;
          break;
        }
        tmp_ans++;
        for(ll k = 0; k < H; k++){
          count[k] = 0;
        }
        j--;
        last_cut = j;
      }
    }

    ans = min(ans, tmp_ans);
  }

  cerr << "Answer:" << endl;
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#pragma warning(disable:4786)
#pragma warning(disable:4996)
#include<list>
#include<bitset>
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<functional>
#include<string>
#include<cstring>
#include<cstdlib>
#include<queue>
#include<utility>
#include<fstream>
#include<sstream>
#include<cmath>
#include<stack>
#include<assert.h>
using namespace std;

#define MEM(a, b) memset(a, (b), sizeof(a))
#define CLR(a) memset(a, 0, sizeof(a))
#define MAX(a, b) ((a) > (b) ? (a) : (b))
#define MIN(a, b) ((a) < (b) ? (a) : (b))
#define ABS(X) ( (X) > 0 ? (X) : ( -(X) ) )
#define S(X) ( (X) * (X) )
#define SZ(V) (int )V.size()
#define FORN(i, n) for(i = 0; i < n; i++)
#define FORAB(i, a, b) for(i = a; i <= b; i++)
#define ALL(V) V.begin(), V.end()
#define IN(A, B, C)  ((B) <= (A) && (A) <= (C))

typedef pair<int,int> PII;
typedef pair<double, double> PDD;
typedef vector<int> VI;
typedef vector<PII > VP;

#define AIN(A, B, C) assert(IN(A, B, C))

//typedef int LL;
typedef long long int LL;
//typedef __int64 LL;

int mark[1003];
LL MOD = 1000000007;

int main()
{
	int n;
	scanf("%d", &n);
	LL ans = 1;
	for (int i = 2; i <= 1000; i++) {
		if (mark[i]) continue;
		for (int j = 2 * i; j <= 1000; j += i) {
			mark[j] = 1;
		}

		int cnt = 0;
		for (int j = i; j <= n; j += i) {
			int temp = j;
			while (temp % i == 0) {
				temp /= i;
				cnt++;
			}
		}

		ans *= (cnt + 1);
		ans %= MOD;

	}

	printf("%lld\n", ans);
	return 0;
}


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

int A[200005];

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

    int X;
    cin >> X;

    for(int i = 2; i <= 200000; i++) A[i] = i;

    for(int i = 2; i <= 200000; i++) {
        if(A[i] == 0) continue;
        for(int j = 2 * i; j <= 200000; j += i) {
            A[j] = 0;
        }
    }

    for(int i = X; ; i++) {
        if(A[i] != 0) {
            cout << i;
            break;
        }
    }

    return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for (int i = a; i < (int)(b); i++)
#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define REP1(i, n) for (int i = 1; i <= (int)(n); i++)
#define all(x) (x).begin(), (x).end()
#define SZ(x) ((int)(x).size())
using ll = long long;
int pow(int a, int b, int mod) {
  if (b == 0) {
    return 1;
  } else if (b % 2 == 1) {
    return pow(a, b - 1, mod) * a % mod;
  }
  int c = pow(a, b / 2, mod);
  return c * c % mod;
}
int main() {
  string s;
  cin >> s;
  int n = SZ(s);
  vector<int> mod(n + 1, 0);
  REP(i, n) {
    int num = s[n - 1 - i] - '0';
    mod[n - 1 - i] = (mod[n - i] + num * pow(10, i, 2019)) % 2019;
  }
  map<int, int> cnt;
  REP(i, n + 1) { cnt[mod[i]]++; }
  ll ans = 0;
  for (auto itr = cnt.begin(); itr != cnt.end(); itr++) {
    ll c = itr->second;
    ans += c * (c - 1) / 2;
  }
  cout << ans << endl;
  return 0;
}


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

int main() {
	int n,i,m,res;
	cin >> n;
	vector<string> s(n),ans={},bla={};
	string cur;
	for(i=0; i<n; i++){
		cin >> s[i];
	}
	sort(s.begin(), s.end());
	cur=s[0]; m=1; res=1;
	ans.push_back(cur);
	for(i=1; i<n; i++){
		if(s[i]!=s[i-1]){
			cur=s[i]; res=1;
		}else{
			res++;
		}
		
		if(m==res){
			ans.push_back(cur);
		}else if(m<res){
			m=res;
			ans=bla;
			ans.push_back(cur);
		}
	}
	
	for(i=0; i<ans.size(); i++){
		cout << ans[i] << endl;
	}
	
	return 0;
}

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

int main()
{
	int N;
	cin >> N;
	int A[N];
	for(int i = 0; i < N; i++){
		cin >> A[i];
	}

	int v, j;

	for(int m = 0; m < N; m++){
		if(m == N-1)
			cout << A[m] << endl;
		else
			cout << A[m] << " ";
	}

	for(int i = 1; i < N; i++){
		v = A[i];
		j = i - 1;
		while(j >= 0 && A[j] > v){
			A[j + 1] = A[j];
			j--;
		}
		A[j + 1] = v;
		for(int m = 0; m < N; m++){
			if(m == N-1)
				cout << A[m] << endl;
			else
				cout << A[m] << " ";
		}
	}

}

Measured memory_bytes: 1164
N,M,X = map(int,input().split())
C = []
A = []
for i in range(N):
    t = list(map(int,input().split()))
    C.append(t[0])
    A.append(t[1:])

result = -1
# 1 << N 2^N
#There are 2^N possible ways of choosing books
for i in range(1 << N):
    #keep all the understanding level in u
    u = [0]*M
    c = 0
    for j in range(N):
        #move j bit from i
        if (i>>j)&1 == 0:
            continue
        c+= C[j]
        #listwise sum
        for k in range(M):
            u[k] += A[j][k]
        #X is the desired understanding level    
    if all(x >= X for x in u):
        if result == -1:
            result = c
        else:
            result = min(result,c)
            
print(result)

Measured memory_bytes: 9160
#include <bits/stdc++.h>
#define ll long long
#define MODV 1000000007
#define INFLL LLONG_MAX // 9223372036854775807
#define EPS 1e-9
#define rep(i, n) for(ll i=0, i##_len=(ll)(n); i<i##_len; i++)
#define repf(i, n) for(ll i=1, i##_len=(ll)(n+1); i<i##_len; i++)
#define all(v) v.begin(), v.end()
#define endl "\n"
#define vi vector<ll>
#define vvi vector<vector<ll>>
#define Yes() cout << "Yes" << endl
#define YES() cout << "YES" << endl
#define No() cout << "No" << endl
#define NO() cout << "NO" << endl
#define Init() std::ios::sync_with_stdio(false); std::cin.tie(0); std::cout<<fixed<<setprecision(15);
template<class T>bool chmax(T &a, const T &b){ if(a<b){ a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b){ if(b<a){ a=b; return 1; } return 0; }
using namespace std;

// 引数nの各桁の和を返す。
long long sumDigit(string s){
    long long ret = 0;
    for(long long i=0; i<s.size(); i++) ret += s[i]-'0';
    return ret;
}

int main(){
    Init();
    string s; cin >> s;
    ll ans = (s[0]-'0'-1) + 9*(s.size()-1);
    chmax(ans, sumDigit(s));
    cout << ans << endl;
}

Measured memory_bytes: 3632
#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp> 
const double PI=4*atan(1);
using namespace std;
using boost::multiprecision::cpp_int;
#define ll long long
#define ull unsigned long long
#define ci cpp_int
#define MOD 1000000007

long findmin(long a,long b) {
    return a<b?a:b;
}
long findmax(long a,long b) {
    return a>b?a:b;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int a;
    cin>>a;
    cout<<(ll)(a+a*a+a*a*a)<<"\n";
    cout.flush();
    return 0;
}


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

int main() {
 int N,M,sum,c;
  c = 0;
  sum = 0;
  cin >> N >> M;//種類、選ぶ個数
  vector<int> vote(N);
  for(int i=0;i<N;i++){
    cin >> vote.at(i);
  }
  for(int i=0;i<N;i++){
    sum += vote.at(i);
  }
  for(int i=0;i<N;i++){
    if( sum <= vote.at(i)*4*M){
	c++;
    }   
  }
  if(c >= M){
    cout << "Yes" << endl;
  }
  else{
    cout << "No" << endl;
  }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const ll MOD = 1'000'000'007;
const ld PI = acos(-1);  
const ld EPS = 0.0000000001;
const ll LINF = 1001002003004005006ll;
const int INF = 1001001001;
#define REP(i, n) for(ll i=0; i<(ll)(n); i++)
#define REPD(i, n) for(ll i=n-1; 0<=i; i--)
#define FOR(i, a, b) for(ll i=a; i<(ll)(b); i++)
#define FORD(i, a, b) for(ll i=a; (ll)(b)<=i; i--)
#define ALL(x) x.begin(), x.end()
#define MAX(x) *max_element(ALL(x))
#define MIN(x) *min_element(ALL(x))
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

int main(){
    map<string, ll> key;
    ll n;   cin >> n;
    REP(i, n){
        string s;   cin >> s;
        key[s] += 1;
    }
    cout << "AC x " << key["AC"]<< endl;
    cout << "WA x " << key["WA"]<< endl;
    cout << "TLE x " << key["TLE"]<< endl;
    cout << "RE x " << key["RE"]<< endl;
}


Measured memory_bytes: 3628
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#define ll long long
#define mod 1000000007
#define max(p,q)((p)>(q)?(p):(q))
ll powe(ll a,ll n,int m){ll x=1;for(a%=m;n;n/=2)n&1?x=x*a%m:0,a=a*a%m;return x;}
int upll(const void*a, const void*b){return*(ll*)a<*(ll*)b?-1:*(ll*)a>*(ll*)b?1:0;}
void sortup(ll*a,int n){qsort(a,n,sizeof(ll),upll);}
ll n;
ll a[212345],b[212345];
ll c[212345];

int main(){
  scanf("%lld",&n);
  for(int i=0;i<n;i++){
    scanf("%lld",&a[i]);}
  for(int i=0;i<n;i++){
    scanf("%lld",&b[i]);}

  int indb=0,maxc=0,maxd=0;
  for(int i=0;i<n;i++){
    while(indb<n && a[i]>=b[indb]) indb++;
    maxc=max(indb-i,maxc);}
  indb=n-1;
  for(int i=n-1;i>=0;i--){
    while(indb>=0 && a[i]<=b[indb]) indb--;
    maxd=max(maxd,i-indb);}
  if(maxc+maxd>n) puts("No");
  else{
    puts("Yes");
    for(int i=maxc;i<n;i++){
      printf("%lld ",b[i]);}
    for(int i=0;i<maxc;i++){
      printf("%lld ",b[i]);}
    puts("");
  }

  
  return 0;
}


Measured memory_bytes: 4868
from __future__ import print_function
# import numpy as np
# import numpypy as np
import sys
input = sys.stdin.readline

def eprint(*args, **kwargs):
    print(*args, file=sys.stderr, **kwargs)
    return

import math
import string
import fractions
from fractions import Fraction
from fractions import gcd

def lcm(n,m):
    return int(n*m/gcd(n,m))

import re
import array
import copy
import functools
import operator

import collections
import itertools
import bisect
import heapq


from heapq import heappush
from heapq import heappop
from heapq import heappushpop
from heapq import heapify
from heapq import heapreplace

from queue import PriorityQueue as pq

def reduce(p, q):
    common = fractions.gcd(p, q)
    return (p//common , q//common )
# from itertools import accumulate
# from collections import deque

from operator import mul
from functools import reduce

def combinations_count(n, r):
    if n<r:
        return 0
    else:
        r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom

import random

def main():
    n = int(input().strip())
    dict_S = {}
    for i in range(n):
        S = input().strip()
        # S = str(sorted(S))      # こうしてしまうと，"[" や "]"まで入った，謎の文字列になってしまう
        S="".join(sorted(S))
        # eprint(type(S))         # 普通に文字列をsortすると，list型に勝手に変換されてしまう

        
        if S in dict_S:
            dict_S[S]+=1
        else: 
            dict_S[S]=1
    
    ans=0
    # SSS="asdfasdfa"
    # eprint(SSS)
    # eprint("dict_S.items()",end="\n")
    # eprint(dict_S.items())
    # for key,value in dict_S.items():
    #     eprint(type(key))
    #     eprint(key)
    #     eprint(value)
        
    for key,value in dict_S.items():
        ans+=combinations_count(value,2)
    print(ans)
    return

if __name__ == '__main__':
    main()

    

'''
#+TITLE: Mathematical Formulation
given N (2<=N<=10^5)
given [s_{i}] 
	(0<=i<=N-1)
	(\forall i \in {0...(N-1)}, len(s_{i})==10 )
	
	( \forall (i,j) \in {0...(N-1)}^{2} and 0<=i<j<=(N-1), s_{i} != s_{j} )
	
	

'''

# ### 
# dict_name = {key: value, key: value, ...}

# if pair in dict_1:
#     dict_1[pair]+=1
# else: 
#     dict_1[pair]=0

# for key, value in dict_1.items():
#     print(key, value)


Measured memory_bytes: 85080
#include <stdio.h>
#include <iostream>
#include <string>
#include <vector>
#include <utility>
#include <algorithm>
#include <queue>
#include <list>
#include <stack>
#include <math.h>
#include <map>
#include <unordered_map>
#include <set>
using namespace std;

#define ll long long
#define ull unsigned long long

#define	max	1000000007

ll gcd(ll a, ll b) {
	if (a < b)
		swap(a, b);
	while (ll r = a % b)
		a = b, b = r;
	return b;
}

class mod
{
public:
	ll val;

	mod(ll v)
	{
		val = v % max;
	}

	mod()
	{
		val = 0;
	}

	void operator -=(const mod &v)
	{
		val -= v.val;

		if (val < 0)
			val += max;
	}

	void operator +=(const mod &v)
	{
		if (val + v.val >= max)
			val -= max;
		val += v.val;
	}

	void operator +=(ll &v)
	{
		if (val + v >= max)
			val -= max;
		val += v;
	}

	void operator *=(const mod &v)
	{
		val *= v.val;
		val %= max;
	}

	void operator *=(ll &v)
	{
		val *= v;
		val %= max;
	}

	ll modinv(ll a)
	{
		ll b = max, u = 1, v = 0;
		while (b)
		{
			ll t = a / b;
			a -= t * b; swap(a, b);
			u -= t * v; swap(u, v);
		}
		u %= max;
		if (u < 0)
			u += max;
		return u;
	}

	void operator /=(const mod &v)
	{
		val *= modinv(v.val);
		val %= max;
	}

	void operator /=(ll &v)
	{
		val *= modinv(v);
		val %= max;
	}
};

int n, m, q;
vector<int> a, b, c, d;

vector<int> A;
ll r = 0;

void culc()
{
	ll t = 0;
	for (int i = 0; i < q; i++)
		if (A[b[i] - 1] - A[a[i] - 1] == c[i])
			t += d[i];
	if (t > r)
		r = t;
}

void func(int now, int bef)
{
	if (now == n)
	{
		culc();
		return;
	}
	for (int i = bef; i <= m; i++)
	{
		A[now] = i;
		func(now + 1, i);
	}
}

int main()
{
	cin >> n >> m >> q;
	A.resize(n);
	a.resize(q);
	b.resize(q);
	c.resize(q);
	d.resize(q);
	for (int i = 0; i < q; i++)
		cin >> a[i] >> b[i] >> c[i] >> d[i];
	func(0, 1);
	printf("%lld", r);

	return 0;
}

Measured memory_bytes: 3252
/**
*author: Ritchie Zhang
*date:
**/
#include <bits/stdc++.h> 
using namespace std; 
int main()
{
	string a;
	cin >> a;
	if (a == "ABC")
	{
		cout << "ARC" << endl;
	}

	if (a == "ARC")
	{
		cout << "ABC" << endl;
	}
	return 0;
}

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

int main()
{
    ll N, K, Q;
    cin >> N >> K >> Q;
    vector<ll> A(N+1, 0);
    for(int i = 0; i < Q; i++)
    {
        ll a; cin >> a;
        A[a]++;
    }
    for(int i = 1; i < N+1; i++)
    {
        if(K - (Q-A[i]) <= 0) cout << "No" << endl;
        else cout << "Yes" << endl;
    }
    return 0;
}

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

int main() {
  ll n,cnt = 0,k;
  cin >> n >> k;
  vector<int>a(n);
  rep(i,n){
    cin >> a[i];
    a[i]--;
  }
  vector<int>seen(n,0);
  ll p = 0,rl,cnt0 = 0,s = 0;
  bool tf = true;
  while(true){
    seen[p]++;
    if(seen[p] == 3){
      rl = cnt-cnt0;
      break;
    }
    if(seen[p] == 2 && tf){
      tf = false;
      cnt0 = cnt;
      s = p;
    }
    cnt++;
    p = a[p];
  }
  cnt0 = 2*cnt0-cnt;
  if(k <= cnt0){
    p = 0;
    rep(i,k) p = a[p];
    cout << p+1 << endl;
    return 0;
  }
  k -= cnt0;
  k %= rl;
  p = s;
  rep(i,k) p = a[p];
  cout << p+1 << endl;
}

Measured memory_bytes: 4804
n = int(input())
A = list(map(int,input().split()))
B = [0]*(n+1)
C = [0]*(n+1)
for a in A:
    B[a] += 1
    C[B[a]] += 1

X = [0]
for i in range(1,n+1):
    X.append(X[i-1] + C[i])
for j in range(1,n+1):
    X[j] = X[j] // j

ind = n
k = 1
while k<=n:
    if ind<0:
        for _ in range(n-k+1):
            print(0)
        break
    if k<=X[ind]:
        print(ind)
        k += 1
    else:
        ind -= 1

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

#define MAXN 2010
typedef long long ll;
const int mod = 1000000;

int a[MAXN];



int main()
{
 	//freopen("input", "r", stdin);
	//freopen("output", "w", stdout);
	
	int n, w, z;
	cin >> n >> z >> w; 
    for (int i = 1; i <= n; ++i)
    	cin >> a[i];
   	if (n == 1)
   	{
   	   cout << abs(w - a[1]) << endl;	
    }
    else cout << max(abs(a[n] - w), abs(a[n - 1] - a[n])) << endl;
   	
 	return 0;
} 

Measured memory_bytes: 256
#include <iostream>

using namespace std;

void trace(int A[], int N){
    for(int i = 0; i < N;i++){
        if(i)printf(" ");
        printf("%d", A[i]);
    }
    printf("\n");
}

int bubble_sort(int A[], int N){
    int nsw = 0;
    for(int i = 0;i < N;i++){
        for(int j = N-1;j >= i+1;j--){
            if(A[j] < A[j-1]){
                swap(A[j], A[j-1]);
                nsw++;
            }
        }
    }
    return nsw;
}

int main(){
    int n,A[100], nsw;
 
    cin >> n;
    for(int i = 0;i< n;i++){
        cin >> A[i];
    }

    nsw = bubble_sort(A, n);

    trace(A, n);
    cout << nsw << endl;
    return 0;
}


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

#define INF64 1LL << 60;
#define INF32 1 << 29;

using namespace std;

void execute()
{
	int left1, left2, right1, right2;
	cin >> left1 >> left2 >> right1 >> right2;

	if (left1 + left2 > right1 + right2)
		cout << "Left" << endl;
	else if (left1 + left2 < right1 + right2)
		cout << "Right" << endl;
	else
		cout << "Balanced" << endl;

	return;
}

int main()
{
	std::cout << std::fixed << std::setprecision(15);
	execute();

	int stop;
	cin >> stop;

	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <stdio.h>
#include <cstring>
#include <math.h>
#include <algorithm>
#include <vector>
#include <string>
#include <stdlib.h>
#include <queue>
#include <utility>
#define rep(i,n) for(int i=0;i<n;i++)
#define rrep(i,n) for(int i=n-1;i>=0;i--)
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define ll long long
#define LL long long
#define INF 1000000001
#define mod 1000000007
using namespace std;
int keta(int n,int k){return (n/int(pow(10,double(k-1)))) % 10;} //nの下からk桁目
ll gcd(ll n,ll m){
	if(n<m){ll a=m;m=n;n=a;}
	ll r=n%m;
	while(r!=0){
		n=m;
		m=r;
		r=n%m;
	}
	return m;
}
ll lcm(ll n,ll m){
	return n*m/gcd(n,m);
}

int main(){
	
	int n,m;
	cin>>n>>m;
	vector<int> a,b,c;
	a.resize(m);
	b.resize(m);
	c.resize(n);
	rep(i,m){
		cin>>a[i]>>b[i];
	}
	rep(i,n){
		c[i]=0;
	}
	rep(i,m){
		if(a[i]==1){
			c[b[i]-1]=1;
		}
	}
	rep(i,m){
		if(b[i]==n){
			rep(j,n){
				if(c[a[i]-1]==1){
					cout<<"POSSIBLE"<<endl;
					return 0;
				}
			}
		}
	}
	cout<<"IMPOSSIBLE"<<endl;


}

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

using ll = long long;
#define FOR(i, m, n) for (int i = (m); i < (n); i++)
#define REP(i, n) FOR(i, 0, n)
#define REP1(i, n) FOR(i, 1, (n) + 1)
#define ALL(c) (c).begin(), (c).end()
template<class T> inline bool chmin(T& a, T b) {if (a > b) {a = b; return true;} return false;}
template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b; return true;} return false;}
const int MOD = 1000000007;

int main() {
    int n;
    cin >> n;
    int h;
    int p;
    cin >> p;
    int mx = 0;
    int c = 0;
    REP(i, n - 1) {
        cin >> h;
        if (p >= h) {
            c++;
        } else {
            chmax(mx, c);
            c = 0;
        }
        p = h;
    }
    chmax(mx, c);
    cout << mx << endl;
}


Measured memory_bytes: 256
import java.util.*;
class Main{
  public static void main(String[] args){
Scanner sc=new Scanner(System.in);
		    int n=sc.nextInt();
		    long sum=0;
      Long f=new Long(1);
		    Map<Integer,Long> m=new HashMap<>();
		    for(int i=0;i<n;i++){
		    		int c=sc.nextInt();
		    		sum+=c;
            
		    		if(!m.containsKey(c)) {
		    			m.put(c,f);
		    		}else {
		    			m.put(c,m.get(c)+f);
		    		}
		    }int k=sc.nextInt();
		    for(int i=0;i<k;i++) {
		    	 int prev=sc.nextInt();
				    int fill=sc.nextInt();
				    if(m.containsKey(prev)) {
				    long g=m.get(prev);
				    sum=sum-prev*g;
				    sum=sum+fill*g;
				  				    m.remove(prev);
				    
				    if(!m.containsKey(fill)) {
		    			m.put(fill,g);
		    		}else {
		    			m.put(fill,m.get(fill)+g);
		    		}
				    
                    }
				    System.out.println(sum);
		    }
		    
		   
		 

  }
    
  }


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

#define lld long long int
#define llu unsigned long long

int main()
{
    //freopen("input.txt", "w", stdin);

    int a,b,c,res;

    while(cin>>a>>b>>c)
    {
        res = max(a,max(b,c));
        res -= a+b+c;

        cout<<abs(res)<<endl;
    }
    return 0;
}


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

int main() {
  string n;
  cin >> n;
  char c = n[n.size()-1];
  string ans = "hon";
  if ( c == '3' ) { ans = "bon"; }
  if ( c == '0' || c == '1' || c == '6' || c == '8') { ans = "pon"; }
  cout << ans << endl;
  return 0;
}


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

int main() {
  int64_t H, W;
  cin >> H >> W;
  
  if(H == 1 || W == 1){
    cout << 1 << endl;
  }
  else{
  int64_t A =((H+1)/2)*((W+1)/2);
  int64_t B =(H/2)*(W/2);
  cout << A+B << endl;
  }
}


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

#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define BIT(X,i) ((X>>i)&1)
#define REP(i,a,b) for(int i = (a); i < (b); ++i)
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define SORT(a) sort(all(a))
#define RSORT(a) sort(rall(a))
#define ina(x,n) rep(x_i,n) cin>>x[x_i]
#define outa(x,n) rep(x_i,n) cerr<<x[x_i]<<" \n"[x_i==n-1]

using ll  = long long int;
using vl  = vector<ll>;
using vvl = vector<vl>;
using pll = pair<ll, ll>;
using vll = vector<pll>;

const int inf = (1<<28);
const ll infl = (1LL<<60);
const int mod = 1e9+7;

int main() {
    int n, t; cin >> n >> t;
    vll ab(n);
    rep(i,n) {
        cin >> ab[i].ff >> ab[i].ss;
    }
    sort(all(ab));

    vvl dp(n+1, vl(t, -1));
    ll ans = 0;
    dp[0][0] = 0;
    rep(i,n) {
        rep(j,t) {
            if (dp[i][j] == -1) continue;
            dp[i+1][j] = max(dp[i+1][j], dp[i][j]);
            ans = max(ans, dp[i][j] + ab[i].ss);
            int jj = j + ab[i].ff;
            if (jj >= t) continue;
            dp[i+1][jj] = max(dp[i][jj], dp[i][j] + ab[i].ss);
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 70784
#include <algorithm>
#include <climits>
#include <cmath>
#include <cstdio>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
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 vector<vector<ll>> vvl;
#define REP(var, a, b) for (int var = (a); var < (b); var++)
#define rep(var, n) for (int var = 0; var < (n); ++var)
#define ALL(c) (c).begin(), (c).end()
#define rALL(c) (c).rbegin(), (c).rend()
ll MOD = 1000000007;
const ll INF = 1LL << 62;

int getidx(char ch) {
  if ('a' <= ch && ch <= 'z') return ch - 'a';
  return ch - 'A' + 26;
}

int main() {
  //
  ll n;
  cin >> n;
  vector<string> data(2);
  rep(i, 2) { cin >> data[i]; }
  ll ans = 1;
  int type = 0;
  int j = 1;
  if (data[0][0] == data[1][0]) {
    type = 1;
    ans = 3;
  } else {
    j = 2;
    ans = 3 * 2;
  }

  while (j < data[0].size()) {
    if (data[0][j] != data[1][j]) {
      if (type == 1) {
        ans = ans * 2 % MOD;
      } else {
        ans = ans * 3 % MOD;
      }
      j += 2;
      type = 0;
    } else {
      if (type == 1) {
        ans = ans * 2 % MOD;
      } else {
        // ans remains the same
      }
      j++;
      type = 1;
    }
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
n = int(input())
b = list(map(int, input().split()))

a = []
b = [10**6] + b
for i in range(1, len(b)):
    b0, b1 = b[i - 1], b[i]
    if b0 > b1:
        a.append(b1)
    else:
        a.append(b0)
a.append(b[-1])
print(sum(a))

Measured memory_bytes: 3064
#include <iostream>
#include <iomanip>
#include <string>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <stack>
#include <queue>
#include <bitset>

#define FOR(i, b, e) for(ll i = (ll)(b); i < (ll)(e); ++i)
#define RFOR(i, b, e) for(ll i = (ll)(e-1); i >= (ll)(b); --i)
#define REP(i, n) FOR(i, 0, n)
#define RREP(i, n) RFOR(i, 0, n)
#define REPC(x,c) for(const auto& x:(c))
#define VS vector<string>
#define VL vector<long long>
#define VI vector<int>
#define VVI vector<vector<int>>
#define VVL vector<vector<ll>>
#define ALL(x) (x).begin(),(x).end()
#define SORT(x) sort(ALL(x))
#define RSORT(x) sort((x).rbegin(),(x).rend())
#define PAIR pair<ll,ll>
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );

using  ll = long long;
constexpr ll MOD = 1000000007;
using std::cout;
using std::endl;
using std::cin;
using std::sort;
using std::pair;
using std::string;
using std::stack;
using std::queue;
using std::vector;
using std::list;
using std::map;
using std::unordered_map;
using std::multimap;
using std::unordered_multimap;
using std::set;
using std::unordered_set;
using std::multiset;

ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }
ll pow(ll a, ll b) {
	ll ans = 1;
	while (b > 0) {
		if (b % 2 == 1) {
			ans *= a;
			ans %= MOD;
		}
		b /= 2;
		a *= a;
		a %= MOD;
	}
	return ans;
}
ll comb(ll a, ll b) {
	if (a - b < b) { return comb(a, a - b); }
	static unordered_map<ll, ll> memo;

	ll c = 1;
	FOR(i, a - b + 1, a + 1) {
		c *= i;
		c %= MOD;
	}
	if (memo.find(b) == memo.end()) {
		ll k = 1;
		FOR(i, 2, b + 1) {
			k *= i;
			k %= MOD;
		}
		memo[b] = pow(k, MOD - 2);
	}
	c *= memo[b];
	return c % MOD;
}
multiset<ll> prime_decomposition(ll n) {
	ll i = 2;
	multiset<ll> table{};
	while (i * i <= n) {
		while (n % i == 0) {
			n /= i;
			table.emplace(i);
		}
		++i;
	}
	if (n > 1) {
		table.emplace(n);
		return table;
	}
	return table;
}
/*
-- bit --
REP(i, (1 << n)) {
	REP(j, n) {
		cout << (1 & (i >> j));
	}
	cout << endl;
}
*/

int main() {
	ll n;
	cin >> n;
	ll ans = 0;
	REP(i, n) {
		ll l, r;
		cin >> l >> r;
		ans += r - l + 1;
	}
	cout << ans << endl;

}

Measured memory_bytes: 256