akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define FOR(var, begin, end) for (int var = (begin); var <= (end); var++)
#define RFOR(var, begin, end) for (int var = (begin); var >= (end); var--)
#define REP(var, length) FOR(var, 0, length - 1)
#define RREP(var, length) RFOR(var, length - 1, 0)
#define EACH(value, var) for (auto value : var)
#define SORT(var) sort(var.begin(), var.end())
#define REVERSE(var) reverse(var.begin(), var.end())
#define RSORT(var) SORT(var); REVERSE(var)
#define OPTIMIZE_STDIO ios::sync_with_stdio(false);cin.tie(0);cout.precision(10);cout << fixed
#define endl '\n'

const ll MOD = 1e9 + 7;
struct mint {
    ll x;
    mint() : x(0) {}
    mint(ll x) : x((x % MOD + MOD) % MOD) {}
    mint& operator+=(const mint& r) { if ((x += r.x) >= MOD) { x -= MOD; } return *this; }
    mint& operator-=(const mint& r) { if ((x -= r.x) < 0) { x += MOD; } return *this; }
    mint& operator*=(const mint& r) { if ((x *= r.x) > MOD) { x %= MOD; } return *this; }
    mint& operator++() { if ((++x) >= MOD) { x -= MOD; } return *this; }
    mint operator++(int) { mint ret = x; if ((++x) >= MOD) { x-= MOD; } return ret; }
    mint& operator--() { if ((--x) < 0) { x += MOD; } return *this; }
    mint operator--(int) { mint ret = x; if ((--x) < 0) { x += MOD; } return ret; }
    mint operator+(const mint& r) { mint ret; return ret = x + r.x; }
    mint operator-(const mint& r) { mint ret; return ret = x - r.x; }
    mint operator*(const mint& r) { mint ret; return ret = x * r.x; }
    mint operator-() { return mint() - *this; }
    bool operator<(const mint& a) { return x < a.x; }
    bool operator>(const mint& a) { return x > a.x; }
    bool operator<=(const mint& a) { return x <= a.x; }
    bool operator>=(const mint& a) { return x >= a.x; }
    bool operator==(const mint& a) { return x == a.x; }
    bool operator!=(const mint& a) { return x != a.x; }
};
ostream& operator<<(ostream& os, const mint& r) { os << r.x; return os; }
ostream& operator>>(ostream& os, const mint& r) { os >> r.x; return os; }

int dp[3100][3100];

void solve(istream& cin, ostream& cout) {
  string s, t;
  cin >> s;
  cin >> t;
  int ns = s.size(), nt = t.size();
  // dp[i + 1][j + 1]: s の i 文字目までと t の j 文字目までの LCS の長さ
  REP(i, ns) {
    REP(j, nt) {
      if (s[i] == t[j])
        dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j] + 1);
      else
        dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1]);
    }
  }
  string ans;
  int i = s.size(), j = t.size();
  while(i > 0 && j > 0) {
    // (i-1, j) -> (i, j) と更新
    if (dp[i][j] <= dp[i - 1][j]) {
      --i;
    }
    // (i, j-1) -> (i, j) と更新
    else if (dp[i][j] == dp[i][j - 1]) {
      --j;
    }
    // (i-1, j-1) -> (i, j) と更新
    else {
      ans += s[i - 1];
      --i; --j;
    }
  }
  REVERSE(ans);
  cout << ans << endl;
}

#ifndef TEST
int main() {
  OPTIMIZE_STDIO;
  solve(cin, cout);
}
#endif


Measured memory_bytes: 37120
public class Main {
    public static void main(String[] args){
        java.util.Scanner scan = new java.util.Scanner(System.in);
        while(true){
            String str = scan.next();
            if("-".equals(str)){
                break;
            }
            int n = scan.nextInt();
            for(int i = 0; i < n;i++){
                int h = scan.nextInt();
                str = str.substring(h)+str.substring(0, h);
            }
            System.out.println(str);
 
        }
    }
 
}

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

//#define int long long
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define rep(i,n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<n;++i)
#define exrep(i, a, b) for(ll i = a; i < b; i++)
#define out(x) cout << x << endl
#define EPS (1e-7)
#define gearup ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
typedef long double ld;
typedef long long int ll;
typedef unsigned long long int ull;
typedef vector<int> vi;
typedef vector<char> vc;
typedef vector<bool> vb;
typedef vector<double> vd;
typedef vector<string> vs;
typedef vector<pair<int,int> > vpii;
typedef vector<vector<int> > vvi;
typedef vector<vector<char> > vvc;
typedef vector<vector<bool> > vvb;
typedef vector<vector<double> > vvd;
typedef vector<vector<string> > vvs;
typedef vector<ll> vl;
typedef vector<vector<ll> > vvl;
typedef vector<vector<vector<ll> > > vvvl;
ll MOD = 1000000007;
const long long L_INF = 1LL << 60;
const int INF = 2147483647; // 2^31-1
const double PI = acos(-1);
//cout<<fixed<<setprecision(10);

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> void debug(T v){rep(i,v.size()) cout<<v[i]<<" ";cout<<endl;}
const ll dx[8] = {1, 1, 0, -1, -1, -1, 0, 1};
const ll dy[8] = {0, 1, 1, 1, 0, -1, -1, -1};

signed main()
{   
    gearup;
    vs s(3);
    rep(i,3)cin>>s[i];
    rep(i,3)cout << s[i][i];
    cout << endl;
}


Measured memory_bytes: 256
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <vector>

using namespace std;
using ll = long long;

#define all(c) (c).begin(), (c).end()
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define pb(e) push_back(e)
#define mp(a, b) make_pair(a, b)
#define fr first
#define sc second

const ll INF = 1e9;
const ll MOD = 1e9 + 7;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

int cnt[26];
int main() {
    string S;
    cin >> S;

    rep(i, S.size()) cnt[S[i] - 'a']++;
    int ans = 0;
    rep(i, 26) if (cnt[i] % 2 == 1) ans++;
    if (ans == 0 || ans == 1) {
        cout << "0" << endl;
    } else {
        cout << (ans + 1) / 2 - S.size() % 2 << endl;
    }

    return 0;
}

Measured memory_bytes: 3140
import java.util.*;
import java.io.*;

public class Main {

  void solve(InputReader in, PrintWriter out) {
    int n = in.nextInt();
    int d = in.nextInt();
    int a = in.nextInt();
    
    Pair[] arr = new Pair[n];
    for (int i = 0; i < n; ++i)
      arr[i] = new Pair(in.nextInt(), in.nextInt());

    Arrays.sort(arr);
    ArrayDeque<Pair> q = new ArrayDeque<>();
    int i = 0; 
    long ans = 0;
    long cnt = 0;
    while (i < n) {
      while (!q.isEmpty()) {
        Pair p = q.peek();
        if (p.f >= arr[i].f) break;
        cnt -= p.s;
        q.poll();
      }

      arr[i].s -= cnt;
      if (arr[i].s > 0) {
        int attacks = arr[i].s / a;
        attacks += arr[i].s % a != 0 ? 1 : 0;
        ans += attacks;
        q.offer(new Pair(arr[i].f + d + d, attacks * a));
        cnt += attacks * a;
      }
      ++i;
    }

    out.println(ans);
  }

  public static void main(String[] args) throws Exception {
    InputReader in = new InputReader(System.in);
    PrintWriter out = new PrintWriter(System.out);
    Main solver = new Main();
    solver.solve(in, out);
    out.close();
  }

  static class Pair implements Comparable<Pair> {
    int f, s;

    public Pair(int f, int s) {
      this.f = f;
      this.s = s;
    }

    @Override
    public int compareTo(Pair p) {
      return this.f - p.f;
    }
  }

  static class InputReader {
    BufferedReader in;
    StringTokenizer st;

    public InputReader(InputStream is) {
      in = new BufferedReader(new InputStreamReader(is));
    }

    public String next() {
      try {
        while (st == null || !st.hasMoreTokens()) {
          st = new StringTokenizer(in.readLine());
        }
        return st.nextToken();
      } catch (Exception e) {
        throw new RuntimeException(e);
      }
    }

    public int nextInt() {
      return Integer.parseInt(next());
    }

    public long nextLong() {
      return Long.parseLong(next());
    }
  }
}


Measured memory_bytes: 61948
while 1:
    n = int(input())
    if n == 0:
        break
    a = []
    for _ in range(n):
        a.append(int(input()))

    dp = []
    dp.append(a[0])
    for i in range(1,len(a)):
        dp.append(max(dp[i-1] + a[i], a[i]))

    print(max(dp))

Measured memory_bytes: 6860
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <string>
using namespace std;
typedef vector<int> vint;
typedef vector<long long> vll;
typedef pair<int,int> pint;
typedef long long ll;
#define range(i,a,b) for(int i=a;i<b;++i)
#define rep(i,n) range(i,0,n)
#define INF 10000000000 //10^10
#define PI 3.141592

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



Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define FOR(i, a, b) for (int i= (a); i < (b); ++i)
typedef long long ll;
typedef pair<int,int> P;
const int INF = 100100100;
const int MOD = (int)1e9 + 7;
const double EPS = 1e-9;
int main() { int a, b, c, d;
  cin >> a >> b >> c >> d;
  if(a+b==c+d){
    puts("Balanced");
  }else if(a+b<c+d){
    puts("Right");
  }else{
    puts("Left");
  }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define N 1000000007;

using namespace std;
int main()
{
 ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
 int n;
 double d;
 cin>>n>>d;
 long long  x[n];
 long long  y[n];
 for(int i=0;i<n;i++)
 {
    cin>>x[i];
    cin>>y[i];
 }
 int nb=0;
 for(int i=0;i<n;i++)
 {
     if((long long)(x[i]*x[i]+y[i]*y[i])<=(long long)d*d)
         nb++;
 }
 cout<<nb;

 return(0);
}


Measured memory_bytes: 6824
#include "bits/stdc++.h"
#define rep(i,n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
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; }

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int h, w;
	cin >> h >> w;
	vector<vector<char>> c(h, vector<char>(w));
	rep(i,h)rep(j,w) cin >> c[i][j];
	vector<bool> tate(h, false), yoko(w, false);
	rep(i,h){
		bool none = true;
		rep(j,w){
			if(c[i][j] == '#') none = false;
		}
		if(none) tate[i] = true;
	}
	rep(j,w){
		bool none = true;
		rep(i,h){
			if(c[i][j] == '#') none = false;
		}
		if(none) yoko[j] = true;
	}
	rep(i,h){
		if(tate[i]) continue;
		rep(j,w){
			if(yoko[j]) continue;
			cout << c[i][j];
		}
		cout << endl;
	}
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <string>
#include <iostream>
#include <iomanip>
#include <map>
#include <algorithm>
#include <vector>
#include <math.h>
#include <queue>
#define MOD (long long)1000000007
#define INF (long long)998244353
using namespace std;

int main(void){
    int n;
    cin >> n;
    for(int i=1; i<=n; i++){
        if((int)(i*1.08)==n){
            cout << i << endl;
            return 0;
        }
    }
    cout << ":(" << endl;
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
int L;
int ch(string s){
  int t=0;
  for(int i=L-1,j=1;i>=0;i--,j*=10)t+=(s[i]-'0')*j;
  return t;
}
int main(){
  string a[32],b,c,z;
  while(cin>>a[0]>>L){
    if(L==0)break;
    for(int j=0;j<L-a[0].size();j++)z+='0';
    a[0]=z+a[0];
    z.clear();
    int i=0,k=1;
    while(k){
      b=a[i];
      sort(b.begin(),b.end());
      c=b;
      reverse(c.begin(),c.end());
      i++;
      for(int j=0;j<L;j++){
	int t=b[j],u=c[j];
	if(t-u<0)b[j+1]--,a[i]+=t-u+10+'0';
	else a[i]+=t-u+'0';
      }
      reverse(a[i].begin(),a[i].end());
      for(int j=0;j<i;j++)
	if(a[i]==a[j])cout<<j<<' '<<ch(a[i])<<' '<<i-j<<endl,k=0;
      if(k==0)for(int j=0;j<=i;j++)a[j].clear();
    }
  }
  return 0;
}

Measured memory_bytes: 1232
#include <stdio.h>

int n, A[50];

// 入力値のMから選んだ要素を引いていく再帰関数
int solve(int i, int m) {
    if(m==0) return 1;
    if(i>=n) return 0;
    int res = solve(i+1,m) || solve(i+1,m-A[i]);
    return res;
}

int main(void) {
    int q, M, i;

    scanf("%d", &n);
    for(i=0;i<n;i++) scanf("%d",&A[i]);
    scanf("%d",&q);
    for(i=0;i<q;i++) {
        scanf("%d", &M);
        if(solve(0,M)) printf("yes\n");
        else printf("no\n");
    }
    return 0;
}



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


int main(){
	long long int  a,b[120],c[10],d;
  cin >> a ;
  
  for(int i=0;i<a;i++)
    cin >> b[i];
  
  for(int i=0;i<9;i++){
    c[i] =0;
  }
 
  for(int i=0;i<a;i++){
    if(b[i] < 400){
      c[0]++;
    }
    else if(b[i] <800){
      c[1]++;
    }
    else if(b[i] < 1200){
      c[2]++;
    }
    else if(b[i] <1600){
      c[3]++;
    }
    else if(b[i] <2000){
      c[4]++;
    }
    else if(b[i] <2400){
      c[5]++;
    }
    else if(b[i] < 2800){
      c[6]++;
    }
    else if(b[i] < 3200){
      c[7]++;
    }
    else if( 3200<= b[i]){
      c[8]++;
    }
  }
 d =0;
  for(int i=0;i<8;i++){
    if(c[i] >0){
      d++;
    }
  }
  if(d!=0){
  cout << d <<" "<<d+c[8]<<endl;
    
    return 0;
}
  else{
    cout << "1" << " " << c[8] << endl;
    
    return 0;
  }
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <utility>
#include <cmath>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <numeric>
#include <functional>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef pair<ll, ll> P;
#define rep(i, n) for(ll i = 0; i < n; i++)
#define exrep(i, a, b) for(ll i = a; i <= b; i++)
#define out(x) cout << x << endl
#define exout(x) printf("%.10f\n", x)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define pb push_back
#define re0 return 0
const ll mod = 1000000007;
const ll INF = 1e16;
const ll MAX_N = 100010;
 
int main() {
    ll h, w, a, b;
    cin >> h >> w >> a >> b;

    rep(i, h) {
        if(i < b) {
            rep(j, w) {
                if(j < a) {
                    cout << 0;
                }
                else {
                    cout << 1;
                }
            }
        }
        else {
            rep(j, w) {
                if(j < a) {
                    cout << 1;
                }
                else {
                    cout << 0;
                }
            }
        }
        cout << "\n";
    }
    
    re0;
}

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

int main(){
    char x;
    cin>>x;
    if(x>='A'&&x<='Z')cout<<'A'<<endl;
    else cout<<'a'<<endl;
}

Measured memory_bytes: 3628
def getime(n):
    h = m = s = int()
    while n >= 3600:
        n -= 3600
        h += 1
    while n >= 60:
        n -= 60
        m += 1
    s = n
    return h, m, s

n = int(input())
h,m,s = getime(n)
print("{}:{}:{}".format(h,m,s))


Measured memory_bytes: 5600
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int a[N];
int gcd(int a,int b){
    return a%b==0? b:gcd(b,a%b);
}
int main()
{
    int a,b,k;
    scanf("%d%d%d",&a,&b,&k);
    int t=gcd(a,b);
    int cur=k,ans;
    for(int i=t;cur&&i>=1;i--){
        if(t%i==0){
            cur--;
            ans=i;
        }
    }
    printf("%d\n",ans);
    return 0;
}


Measured memory_bytes: 256
import java.util.Scanner

fun main(args:Array<String>){
    val scanner=Scanner(System.`in`)

    var a=IntArray(3)
    var x:Int=0
    var y=0
    var z=0
    var n=0
    var sum=0

    for (i in 0..2){
        a[i]=scanner.nextInt()
    }

    for (j in 0..2){
        if (x<a[j]){
            x=a[j]
            n=j
        }
    }

    var d=(n+2)%3
    var e=(n+1)%3

    if (a[d]<a[e]){
        y=a[e]
        z=a[d]
    }
    else{
        y=a[d]
        z=a[e]
    }

    var sa1=x-y
    var sa2=y-z

    if (sa1<0) sa1=sa1*-1
    if (sa2<0) sa2=sa2*-1

    sum=sa1+sa2
    println(sum)
}

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

long gcd(long x,long y){
    if (x < y) {
        swap(x, y);
    }
    long z;
    while (y) {
        z = x;
        x = y;
        y = z % y;
    }
    return x;
}

int main() {
    long n, x;
    cin >> n >> x;
    vector<long> c(n);
    vector<long> d(n);
    for (int i = 0; i < n; i++) {
        cin >> c[i];
       d[i] = abs(x - c[i]); 
    }
    long ans = d[0];
    for (int i = 1; i < n; i++) {
        ans = gcd(ans,d[i]);
    }
    cout << ans << endl;
}


Measured memory_bytes: 1792
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author anand.oza
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        ARedOrNot solver = new ARedOrNot();
        solver.solve(1, in, out);
        out.close();
    }

    static class ARedOrNot {
        public void solve(int testNumber, InputReader in, PrintWriter out) {
            int a = in.nextInt();
            String s = in.next();

            if (a < 3200)
                out.println("red");
            else
                out.println(s);
        }

    }

    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

    }
}



Measured memory_bytes: 21332
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Main d = new Main();
        d.solve();
    }


    public void solve() {
        Scanner scan = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
        int n = scan.nextInt();
        int m = scan.nextInt();
        UnionTree edges = new UnionTree(n);
        int[] data = new int[n];
        for (int i = 0; i < n; i++) {
            data[i] = scan.nextInt() - 1;
        }
        for (int i = 0; i < m; i++) {
            int x = scan.nextInt() - 1;
            int y = scan.nextInt() - 1;
            edges.unite(x, y);
        }
        System.out.println(solve(n, data, edges));
    }

    public static int solve(int n, int[] data, UnionTree edges) {
        int[] check = new int[n];
        for(int i = 0; i < n; i++) {
            check[data[i]] = i;
        }
        int count = 0;
        for(int i = 0; i < n; i++) {
            if (i == data[i]) {
                count++;
                continue;
            }
            if (edges.same(i, check[i])) {
                count++;
            }
        }
        return count;
    }

    class UnionTree {
        private int[] parents;
        public UnionTree(int n) {
            this.parents = new int[n];
            Arrays.fill(parents, -1);
        }
        public boolean same(int x, int y) {
            return this.root(x) == this.root(y);
        }

        public void unite(int x, int y) {
            int parent_x = root(x);
            int parent_y = root(y);
            if (parent_x == parent_y) {
                return;
            }
            if (this.parents[parent_x] < this.parents[parent_y]) {
                this.parents[parent_x] += this.parents[parent_y];
                this.parents[parent_y] = parent_x;
            } else {
                this.parents[parent_y] += this.parents[parent_x];
                this.parents[parent_x] = parent_y;
            }
        }

        public int root(int x) {
            if (this.parents[x] < 0) {
                return x;
            }
            int root = this.root(this.parents[x]);
            this.parents[x] = root;
            return root;
        }
    }
}


Measured memory_bytes: 88004
#include<iostream>
#include<cmath>
#include<cstdio>
using namespace std;

int main()
{
	int a, b, c;
	cin >> a >> b >> c;
	const double pi = atan(1.0) * 4;
	double rad = pi*(double)c / 180.0;
	double S = 0.5*(double)a*(double)b*sin(rad);
	double L = (double)a + (double)b + sqrt(a*a + b*b - 2 * (double)a*(double)b*cos(rad));
	double h = (double)b * sin(rad);
	printf("%.5f %.5f %.5f\n", S, L, h);
	return 0;
}

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

int main() {
  int N;
  cin>>N;
  int a=0,b=0,c=0,d=0;
  for(int i=0;i<N;i++){
    string S;
    cin>>S;
    if(S=="AC"){
      a++;
    }
    if(S=="WA"){
      b++;
    }
    if(S=="TLE"){
      c++;
    }
    if(S=="RE"){
      d++;
    }
  }
  cout<<"AC x "<<a<<endl;
  cout<<"WA x "<<b<<endl;
  cout<<"TLE x "<<c<<endl;
  cout<<"RE x "<<d<<endl;
}



Measured memory_bytes: 3624
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(ll i = 0, i##_len = (n); i < i##_len; ++i)
#define rep2(i, x, n) for(ll i = x, i##_len = (n); i < i##_len; ++i)
#define all(n) begin(n), end(n)
using ll = long long;
using P = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vs = vector<string>;
using vc = vector<char>;
using vb = vector<bool>;
using vd = vector<double>;
vi dir = {-1, 0, 1, 0, -1, -1, 1, 1, -1};

ll t(string s) {
  set<char> st;
  for(char c : s) st.insert(c);
  return st.size();
}

vs dfs(ll n) {
  if(n == 1) return {"a"};
  vs ss = dfs(n - 1);
  vs res;
  for(auto s : ss) {
    ll m = t(s) + 1;
    rep(i, m) res.push_back(s + char(i + 'a'));
  }
  return res;
}

int main() {
  ll n;
  cin >> n;
  vs ans = dfs(n);
  for(auto v : ans) cout << v << '\n';
}

Measured memory_bytes: 8040
"""
    こんにちは。これはクシャルです
    
    Author : thekushalghosh (クシャル)
    Team   : CodeDiggers
 
    I prefer Python language over the C++ language :p :D
        
    Visit my website : thekushalghosh.github.io
"""
import sys,math,cmath,time,itertools
start_time = time.time()
##########################################################################
################# ---- THE ACTUAL CODE STARTS BELOW ---- #################
    
def solve():
    n = inp()
    q = 2199 - n
    q = q // 200
    print(q)
    
################## ---- THE ACTUAL CODE ENDS ABOVE ---- ##################
##########################################################################
 
def main():
    global tt
    if not ONLINE_JUDGE:
        sys.stdin = open("input.txt","r")
        sys.stdout = open("output.txt","w")
    t = 1
    for tt in range(t):
        solve()
    if not ONLINE_JUDGE:
        print("Time Elapsed :",time.time() - start_time,"seconds")
        sys.stdout.close()
    
#---------------------- USER DEFINED INPUT FUNCTIONS ----------------------#
def inp():
    return(int(input()))
def inlt():
    return(list(map(int,input().split())))
def insr():
    return(input().strip())
def invr():
    return(map(int,input().split()))
 
#------------------ USER DEFINED PROGRAMMING FUNCTIONS ------------------#
def counter(a):
    q = [0] * max(a)
    for i in range(len(a)):
        q[a[i] - 1] = q[a[i] - 1] + 1
    return(q)

def counter_elements(a):
    q = dict()
    for i in range(len(a)):
        if a[i] not in q:
            q[a[i]] = 0
        q[a[i]] = q[a[i]] + 1
    return(q)

def string_counter(a):
    q = [0] * 26
    for i in range(len(a)):
        q[ord(a[i]) - 97] = q[ord(a[i]) - 97],1
    return(q)
 
def factors(n):
    q = []
    for i in range(1,int(n ** 0.5) + 1):
        if n % i == 0: q.append(i); q.append(n // i)
    return(list(sorted(list(set(q)))))
 
def prime_factors(n):
    q = []
    while n % 2 == 0: q.append(2); n = n // 2
    for i in range(3,int(n ** 0.5) + 1,2):
        while n % i == 0: q.append(i); n = n // i
    if n > 2: q.append(n)
    return(list(sorted(q)))

def transpose(a):
    n,m = len(a),len(a[0])
    b = [[0] * n for i in range(m)]
    for i in range(m): 
        for j in range(n): 
            b[i][j] = a[j][i]
    return(b)

#-----------------------------------------------------------------------#
        
ONLINE_JUDGE = __debug__
if ONLINE_JUDGE:
    input = sys.stdin.readline
main()

Measured memory_bytes: 62912
N=gets.to_i
A=gets.split.map(&:to_i)
D=[*0..10**6]
s=0
2.upto(N-2){|i|
	s+=A[i]
	1.upto(A[i]){|j|
		D.unshift(D[j*2-1])
	}
}
gets.to_i.times{
	x=gets.to_i
	p (D[x]||(x-s))+A[0]-A[1]
}

Measured memory_bytes: 49988
#include<stdio.h>

typedef struct{
  int parent;
  int left;
  int right;
}Tree;

Tree t[100000];
int num,dep[100000];

void print(int);
void rec(int,int);

int main(){
  int volume,k,l,r,c,i,j;

  scanf("%d",&num);
  for(i = 0; i< num; i++){
    t[i].parent = -1;
    t[i].left = -1;
    t[i].right = -1;
  }

  for(i = 0; i< num; i++){
    scanf("%d%d",&volume,&k);
  
    for(j = 0;j < k; j++){
      scanf("%d",&c);
      if(j == 0)t[volume].left = c;
      else t[l].right = c;
      l = c;
      t[c].parent = volume;
    }
  }

  for(i = 0; i < num; i++){
    if(t[i].parent == -1)r = i;
  }
  rec(r,0);

  for(i = 0; i < num; i++){
    print(i);
  }

  return 0;
}


void print(int u){

  int i,c;
  printf("node %d: parent = %d, depth = %d, ",u,t[u].parent,dep[u]);
  if(t[u].parent == -1)printf("root, ");
  else if(t[u].left == -1)printf("leaf, ");
  else printf("internal node, ");
  printf("[");
  for(i = 0, c = t[u].left; c != -1; i++,c = t[c].right){
    if(i)printf(", ");
    printf("%d",c);
  }
  printf("]\n");
}


void rec(int u,int p){

  dep[u] = p;

  if(t[u].right != -1)rec(t[u].right,p);
  if(t[u].left != -1)rec(t[u].left,p+1);


}

Measured memory_bytes: 5296
#include<bits/stdc++.h>
#include<stdlib.h>
#include<iostream>
using namespace std;
typedef unsigned long long int   ull;
typedef long long int            ll;
#define pi                 acos(-1);
int main()
{
    int n,a,b,i,s=0,e,j=0;
    cin>>n>>b;
    int c[n+1]={0};
    while(b--)
    {
        cin>>a;
        for(i=0;i<a;i++)
        {
            cin>>e;
            c[e]++;
        }
    }
    for(i=1;i<=n;i++)
    {
        if(c[i]==0)
        {
            s++;
        }
    }
    cout<<s<<endl;
    return 0;
}


Measured memory_bytes: 3620
#include <bits/stdc++.h>
using namespace std;
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#define ms(s, n) memset(s, n, sizeof(s))
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define FORd(i, a, b) for (int i = (a) - 1; i >= (b); --i)
#define FORall(it, a) for (__typeof((a).begin()) it = (a).begin(); it != (a).end(); it++)
#define sz(a) int((a).size())
#define present(t, x) (t.find(x) != t.end())
#define all(a) (a).begin(), (a).end()
#define uni(a) (a).erase(unique(all(a)), (a).end())
#define pb push_back
#define pf push_front
#define mp make_pair
#define fi first
#define se second
#define prec(n) fixed<<setprecision(n)
#define bit(n, i) (((n) >> (i)) & 1)
#define bitcount(n) __builtin_popcountll(n)
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pi;
typedef vector<int> vi;
typedef vector<pi> vii;
const int MOD = (int) 1e9 + 7;
const int FFTMOD = 119 << 23 | 1;
const int INF = (int) 1e9 + 23111992;
const ll LINF = (ll) 1e18 + 23111992;
const ld PI = acos((ld) -1);
const ld EPS = 1e-9;
inline ll gcd(ll a, ll b) {ll r; while (b) {r = a % b; a = b; b = r;} return a;}
inline ll lcm(ll a, ll b) {return a / gcd(a, b) * b;}
inline ll fpow(ll n, ll k, int p = MOD) {ll r = 1; for (; k; k >>= 1) {if (k & 1) r = r * n % p; n = n * n % p;} return r;}
template<class T> inline int chkmin(T& a, const T& val) {return val < a ? a = val, 1 : 0;}
template<class T> inline int chkmax(T& a, const T& val) {return a < val ? a = val, 1 : 0;}
inline ull isqrt(ull k) {ull r = sqrt(k) + 1; while (r * r > k) r--; return r;}
inline ll icbrt(ll k) {ll r = cbrt(k) + 1; while (r * r * r > k) r--; return r;}
inline void addmod(int& a, int val, int p = MOD) {if ((a = (a + val)) >= p) a -= p;}
inline void submod(int& a, int val, int p = MOD) {if ((a = (a - val)) < 0) a += p;}
inline int mult(int a, int b, int p = MOD) {return (ll) a * b % p;}
inline int inv(int a, int p = MOD) {return fpow(a, p - 2, p);}
inline int sign(ld x) {return x < -EPS ? -1 : x > +EPS;}
inline int sign(ld x, ld y) {return sign(x - y);}
mt19937 mt(chrono::high_resolution_clock::now().time_since_epoch().count());
inline int myrand() {return abs((int) mt());}
#define db(x) cerr << #x << " = " << (x) << " ";
#define endln cerr << "\n";

void chemthan() {
    int n; cin >> n;
    vector<pair<long long, long long>> pts(n);
    for (auto& e : pts) cin >> e.fi >> e.se;
    long long res = 0;
    FOR(i, 0, 62) {
        long long x = (1LL << 61);
        long long y = (1LL << 62) - 1 ^ (1LL << i);
        int t = 0;
        FOR(i, 0, n) {
            t ^= (pts[i].se + y & x - pts[i].fi) == x - pts[i].fi;
        }
        if (!t) {
            res |= 1LL << i;
        }
    }
    cout << (1LL << 61) - res << "\n";
}

int main(int argc, char* argv[]) {
    ios_base::sync_with_stdio(0), cin.tie(0);
    if (argc > 1) {
        assert(freopen(argv[1], "r", stdin));
    }
    if (argc > 2) {
        assert(freopen(argv[2], "wb", stdout));
    }
    chemthan();
    cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
    return 0;
}


Measured memory_bytes: 1792
#include <algorithm>
#include <iostream>

using namespace std;

const int N = 500000, Q = 500000;

int aa[N], ll[Q], rr[Q], iia[N], iiq[Q], ft[N], ans[Q];

void update(int i, int n, int x) {
	while (i < n) {
		ft[i] += x;
		i |= i + 1;
	}
}

int query(int i) {
	int x = 0;
	while (i >= 0) {
		x += ft[i];
		i &= i + 1, i--;
	}
	return x;
}

int main() {
	int n, q; cin >> n >> q;
	for (int i = 0; i < n; i++)
		cin >> aa[i];
	for (int h = 0; h < q; h++) {
		int l, r; cin >> l >> r, l--, r--;
		ll[h] = l, rr[h] = r;
	}
	for (int ha = 0; ha < n; ha++)
		iia[ha] = ha;
	sort(iia, iia + n, [] (int i, int j) { return aa[i] < aa[j] || aa[i] == aa[j] && i > j; });
	for (int ha1 = 0, ha2; ha1 < n; ha1 = ha2) {
		int a = aa[iia[ha1]];
		aa[iia[ha1]] = n;
		ha2 = ha1 + 1;
		while (ha2 < n && aa[iia[ha2]] == a) {
			aa[iia[ha2]] = iia[ha2 - 1];
			ha2++;
		}
	}
	for (int hq = 0; hq < q; hq++)
		iiq[hq] = hq;
	sort(iiq, iiq + q, [] (int h1, int h2) { return ll[h1] > ll[h2]; });
	for (int i = n - 1, hq = 0; hq < q; hq++) {
		int h = iiq[hq];
		int l = ll[h], r = rr[h];
		while (i >= l) {
			update(aa[i], n, -1);
			update(i, n, 1);
			i--;
		}
		ans[h] = query(r);
	}
	for (int h = 0; h < q; h++)
		cout << ans[h] << '\n';
	return 0;
}


Measured memory_bytes: 17436
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cstring>
#include <cstdlib>
#include <utility>
#include <map>
#include <vector>
#define llong long long
#define For(i,a,b) for(int i=(a);i<(b);i++)
#define Rep(i,n) for(int i=0;i<(n);i++)
using namespace std;

int main(){
  int n; cin >> n;
  int A[n];
  Rep(i, n){
    cin >> A[i];
  }
  int i=0;
  int cnt=0;
  while(i!=n-1){
    if (A[i]!=A[i+1]){
    i++;
    } else {
      int j=1;
      while(i!=n-1&&A[i]==A[i+1]){
        j++;
        i++;
      }
      cnt += j/2;
    }
  }
  cout << cnt << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define double long double
#define rep(i,n) for(int i=0;i<n;i++)
#define mod 1000000007 // 10^9+7
int n,m;
int a[60],b[60],c[60],d[60];
signed main(){
    cin>>n>>m;
    rep(i,n)cin>>a[i]>>b[i];
    rep(i,m)cin>>c[i]>>d[i];
    rep(i,n){
        int minl=999999999;
        int ans;
        rep(j,m){
            int l=abs(a[i]-c[j])+abs(b[i]-d[j]);
            if(l<minl){
                ans=j+1;
                minl=l;
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}

Measured memory_bytes: 256
x, y, z, k = map(int, input().split())
a_array = sorted([int(x) for x in input().split()], reverse=True)
b_array = sorted([int(x) for x in input().split()], reverse=True)
c_array = sorted([int(x) for x in input().split()], reverse=True)


def solver1():
    ab_array = sorted([x + y for x in a_array for y in b_array], reverse=True)[:3000]
    abc_array = sorted([ab + c for ab in ab_array for c in c_array], reverse=True)
    for abc in abc_array[:k]:
        print(abc)


solver1()


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


using namespace std;

int main(){
    long long N,A,B,C,D;
    long long ans=0;

    string S;

    cin>>N>>A;

    vector<long long> v(N);

    for(int i=0;i<N;++i){
        v[i]=A+i;
    if(i==0){
        B=v[i];
    }else if(abs(B)>abs(v[i])){
        B=v[i];
    }
    
    }


    cout<<accumulate(v.begin(),v.end(),0)-B<<endl;


}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;

#define inf 1013161010
#define ninf -1013161010
#define mod 1000000007
#define ll long long
#define lf long double
#define in(x) scanf("%d",&x);
#define sz(x) ((int)x.size())
#define lld l64d
#define rep(i,n) for(i=0;i<n;i++)
#define rrep(i,n) for(i=n-1;i>=0;i--)
#define rep1(i,a,b) for(i=a;i<=b;i++)
#define rrep1(i,a,b) for(i=a;i>=b;i--)
#define stlfor(i,t) for(auto i =t.begin();i!=t.end();i++)
#define fr freopen("x.txt","r",stdin)
#define frc freopen("y.txt","w",stdout)
#define all(x) x.begin(),x.end()
#define set0(x) memset(x,0,sizeof(x))
#define dbg cout<<"yo "<<endl;
#define pset(n) fixed<<showpoint<<setprecision(n)

#define pii pair<int,int>
#define pll pair<ll,ll>
#define min_pq priority_queue<pll, vector<pll>, greater<pll> >
#define vpii vector<pair<int,int> >
#define vll vector<ll>
#define vpll vector<pair<ll,ll> >
#define si set<int>
#define mii map<int,int>
#define umii unordered_map<int,int>
#define vi vector<int>
#define pb push_back
#define ff first
#define ss second
#define mp make_pair
#define modulo %
#define moduloe %=

typedef tree<pii,null_type,less<pii>,rb_tree_tag,tree_order_statistics_node_update> OST;

ll toint(const string &s) { stringstream ss; ss << s; ll x; ss >> x; return x; }
ll add(ll a, ll b) {a+=b; while(a >= mod) a-= mod; while(a<0) a+= mod;}
ll mul(ll a, ll b) {return (a * 1LL *b % mod);}
string tostring ( ll number ){  stringstream ss; ss<< number; return ss.str();}

const lf pi = 2*acos(0);
const int nn = 500006;
const lf EPS = 0.000000001;

ll gcd(ll a,ll b){return (b==0)? a:gcd(b,a%b); }
void nope(int num = 0){ if(num==0) cout<<"NO"; else cout<<"-1"; exit(0); }

ll seg[200010*4];
int h[nn];
ll a[nn];
ll dp[nn];

ll rmq(int low,int high,int pos,int x,int y)
{
    if(x>high||y<low)
        return 0;
    else if(x<=low&&y>=high)
        return seg[pos];
    int mid=(low+high)/2;
    return max(rmq(low,mid,2*pos+1,x,y), rmq(mid+1,high,2*pos+2,x,y));
}

void update(int low,int high,ll val,int pla,int pos)
{
    if(low==high)
    {
        seg[pos]=val;
        return ;
    }

    int mid=(low+high)/2;
    if(pla<=mid)
    {
        update(low,mid,val,pla,2*pos+1);
        seg[pos]=max(seg[2*pos+1], seg[2*pos+2]);
    }
    else
    {
        update(mid+1,high,val,pla,2*pos+2);
        seg[pos]=max(seg[2*pos+1], seg[2*pos+2]);
    }
}


int main()
{
    ios_base::sync_with_stdio(false); cin.tie(0);
    ll i,j,n,tt;
    tt=1;
    //cin>>tt;
    while(tt--)
    {
        cin>>n;
        rep(i, n)
            cin>>h[i];
        rep(i, n)
            cin>>a[i];


        rep(i, n)
        {
            ll ans = rmq(0, 200001, 0, 0, h[i]) + a[i];
            update(0, 200001, ans, h[i], 0);
            dp[i] = ans;
        }

        ll ans = 0;
        rep(i, n)
            ans = max(dp[i], ans);
        cout<<ans<<endl;

    }
    return 0;
}

// read the question correctly (is y a vowel? what are the exact constraints?)
// look out for SPECIAL CASES (n=1?) and overflow (ll vs int?)


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

typedef long long ll;
typedef pair<int, int> P;
typedef pair<ll, ll> Pl;

const int INT_INF = 2147483646;
const ll LL_INF = 9223372036854775807;

bool SecondCompare(const pair<int,int> &a,const pair<int,int> &b)
{
       return a.second<b.second;
}
 
bool SecondCompareDes(const pair<int,int> &a,const pair<int,int> &b)
{
       return a.second>b.second;
}

ll minll(ll a, ll b){
    if(a >= b)  return b;
    else    return a;
}

ll maxll(ll a, ll b){
    if(a >= b)  return a;
    else    return b;
}

ll n,c,k;
ll t[100010];
ll ans;

/*
void solve(int ind){
    ll st = t[ind];
    ll num = 1;
    ++ind;
    while(ind < n){
        if(st+k >= t[ind] && num <= c){
            ++num;
        }
        else{
            ++ans;
            break;
        }
        ++ind;
    }
    if(ind < n) solve(ind);
    else{
        ++ans;
        return;
    }
}
*/

int main(){
    cin >> n >> c >> k;
    for(int i = 0; i < n; i++){
        cin >> t[i];
    }

    sort(t,t+n);

    ll nn = 0,tmp = 0;

    for(int i = 0; i < n; i++){
        if(nn == 0){
            tmp = t[i];
            ++nn;
            ++ans;
        }
        if(t[i+1] - tmp <= k && nn < c){
            ++nn;
        }
        else{
            nn = 0;
        }
    }


    //solve(0);

    cout << ans << endl;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define ll long long int
using namespace std;
map<ll,ll>m;
int main() {
	ll n;
	cin>>n;
	ll a[n],ans=0ll;
	for(ll i=0ll;i<n;i++)
		cin>>a[i];
	for(ll i=n-1ll;i>=0ll;i--){
		ans+=m[i+a[i]];
		m[i-a[i]]++;
	}
	cout<<ans<<'\n';
	return 0;
}

Measured memory_bytes: 27704
#include <iostream>
#include <vector>
#include <limits.h>
#include <algorithm>
#include <string>
#include <math.h>
#include <limits.h>
#include <queue>
#include <map>
#include <set>
#include <iomanip>
#include <bitset>
#include <cassert>
#include <random>
#include <functional>
#include <stack>
#include <iomanip>
using namespace std;

int N;
typedef pair<int, int> pii;
vector<pii> A;   //中身、順番(0-indexed)
vector<int> AA;   //1～Nの大きさ順でAを表したもの

int main() {
	cin >> N;
	for (int n = 0; n < N; n++) {
		int a;
		cin >> a;
		A.push_back(pii(a, n));
	}
	sort(A.begin(), A.end(), [](pii a, pii b) {
		return a.first < b.first;
	});
	AA.resize(N);
	for (int n = 0; n < N; n++) {
		AA[A[n].second] = n;
	}
	long long ans = 0;
	for (int n = 1; n < N; n += 2) {
		if (AA[n] % 2 == 0)ans++;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 1400
#include <inttypes.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define BUF_SIZE 0x10
#define EXPR_BUF_SIZE (BUF_SIZE*2)

int toint(char ch)
{
  return ch - '0';
}

void print_expr(const char* buf)
{
  for(size_t i = 0; i < strlen(buf); i += 2) {
    putchar(buf[i]);
    switch(buf[i+1]) {
      case ' ':
        break;
      case '+':
        putchar('+');
        break;
      case '\0':
        putchar('\n');
        break;
    }
  }
}

long long eval_expr(const char* buf)
{
  long long tmp = 0;
  long long total = 0;
  for(size_t i = 0; i < strlen(buf); i += 2) {
    if(buf[i+1] == ' ') {
      tmp = 10 * (tmp + toint(buf[i]));
      continue;
    } else if(buf[i+1] == '+' || buf[i+1] == '\0') {
      total += tmp + toint(buf[i]);
      tmp = 0;
    } else {
      fprintf(stderr, "eval: Unknown operator found: %c\n", buf[i+1]);
      exit(1);
    }
  }
  if(tmp != 0) {
    fprintf(stderr, "Invalid expression found: %s\n", buf);
    exit(1);
  }
  //print_expr(buf);
  //printf("%lld\n", total);
  return total;
}

int next_expr(char* buf)
{
  for(size_t i = 1; i < strlen(buf); i += 2) {
    if(buf[i] == ' ') {
      buf[i] = '+';
      return 0;
    } else if(buf[i] == '+') {
      buf[i] = ' ';
      continue;
    } else {
      fprintf(stderr, "next: Unknown operator found: %c\n", buf[i]);
      exit(1);
    }
  }
  return 1;
}

int main()
{
  char buf[BUF_SIZE];
  fgets(buf, sizeof(buf), stdin);
  // delete LF
  buf[strlen(buf)-1] = '\0';

  char expr_buf[EXPR_BUF_SIZE];
  memset(expr_buf, 0, sizeof(expr_buf));
  for(size_t i = 0; i < strlen(buf); i++) {
    expr_buf[2*i] = buf[i];
    expr_buf[2*i+1] = ' ';
  }
  // delete last operator
  expr_buf[strlen(expr_buf)-1] = '\0';

  uint64_t total = eval_expr(expr_buf);
  while(!next_expr(expr_buf)) {
    total += eval_expr(expr_buf);
  }
  printf("%" PRIu64 "\n", total);
  return 0;
}


Measured memory_bytes: 128
/**
*	  Name: Ajay Subhash Jadhav
*	  Institute: International Institute of Technology Hyderabad 
*/

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <deque>
#include <vector>
#include <cstdlib>
#include <iomanip>
#include <cmath>
#include <queue>
#include <map>
#include <set>
#include <ctime>
#include <string.h>
#define LL long long
#define inf 0x7fffffff
#define mod 1000000007
#define pb push_back
#define ppi pair<int,int>
#define vi vector<int>
#define vii vector<ppi>
#define vll vector<LL>
#define mp make_pair
using namespace std;

void fastio()
{
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
}
void inputread()
{
  #ifndef ONLINE_JUDGE
  freopen("input.txt","r",stdin);
  freopen("output.txt","w",stdout);
  #endif
}

int main(){
      
  fastio();
  int n,m,i,j,t;
  cin>>n>>m;
  vi a(n+1,0);  
  for(i=0;i<m;i++)
  {
  	int x,y;
  	cin>>x>>y;
  	x--;
  	y--;
  	a[x]++;
  	if(y!=n-1)
  		a[y+1]--;
  }
  

  for(i=1;i<n;i++)
  {
  	a[i]+=a[i-1];
  }

  int ans=0;
  for(i=0;i<n;i++)
  {
  	if(a[i]==m)
  		ans++;
  }
  cout<<ans;
  return 0;
}

Measured memory_bytes: 640
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<utility>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<ll, ll> P;
int main() {
	int n;
	cin >> n;
	string s;
	string t;
	cin >> s;
	cin >> t;
	int ans = n;
	for (int i = 0; i < n; i++) {
		int flag = 1;
		for (int j = i; j < n; j++) {
			if (s[j] != t[j - i])flag = 0;
		}
		if (flag == 1) {
			ans = i;
			break;
		}
	}
	cout << n + ans << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
using Int = long long;
//INSERT ABOVE HERE
signed main(){
  Int r;
  cin>>r;
  if(r>=2800) cout<<"AGC"<<endl;
  else if(r>=1200) cout<<"ARC"<<endl;
  else cout<<"ABC"<<endl;
  return 0;
}


Measured memory_bytes: 256
N, M = map(int,input().split()) 
P= [["." for _ in range(M+2)] for i in range(N+2)]

for i in range(1,N+1):
    P[i][1:M+1] = list(input())


def rep(a,b):#aたて
    ans = 0
    for i in range(-1,2,1):
        for j in range(-1,2,1):
            if P[a+i][b+j]=="#":
                ans += 1
    P[a][b] = ans


for i in range(1,M+1):
    for j in range(1,N+1):
        if P[j][i] == ".":
          rep(j,i)

for i in range(1,N+1):
    print(''.join([str(i) for i in P[i][1:M+1]]))




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

typedef long long ll;
typedef short int sh;

const int inf=0x3f3f3f3f;
const int MAX=2e5+10;
const int mod=1e9+7;

ll prime[MAX],num_prime=0;
ll fac[MAX]={0,1};

void Init()
{
    for(int i=2;i<MAX;i++)
    {
        fac[i]=fac[i-1]*i%mod;
    }
}

ll Qmul(ll a,ll n)
{
    ll ans=1;
    while(n)
    {
        if(n&1)
            ans=(ans*a)%mod;
        a=a*a%mod;
        n>>=1;
    }
    return ans;
}

ll C(ll n,ll m)
{
    if(!m||!n||n<=m)
        return 1;
    ll m_1,n_m_1;
    m_1=Qmul(fac[m],mod-2);
    n_m_1=Qmul(fac[n-m],mod-2);
    ll ans;
    ans=fac[n]*m_1%mod*n_m_1%mod;
    return ans;
}

int main()
{
    Init();
    ll ans,h,w,a,b;
    while(scanf("%lld%lld%lld%lld",&h,&w,&a,&b)!=EOF)
    {
        ans=0;
        for(ll i=b+1;i<=w;i++)
        {
            ans+=(C(h-a+i-2,i-1)*C(w-i+a-1,a-1))%mod;
            ans%=mod;
        }
        printf("%lld\n",ans);
    }
    return 0;
}


Measured memory_bytes: 4768
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<queue>
using namespace std;
#define REP(i, limit) for(int i=0; i< limit; ++i)
#define LINT long long

int main(){
  int N;
  cin >> N;
  LINT a[N];
  LINT sum1=0, sum2 = 0;
  LINT ans;
  REP(i, N){
    cin >> a[i];
    if(i) sum2 += a[i];
    else sum1 += a[i];
  }
  ans = abs(sum1 - sum2);
  if(N == 2){
    cout << ans << endl;
    return 0;
  }
  REP(i, N-2){
  sum1 += a[i+1];
  sum2 -= a[i+1];
    ans = min(ans, abs(sum1-sum2));
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 1792
#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#include <cmath>
#include <limits>
#include<set>
#include <iomanip>
#include <queue>
#pragma GCC optimize("Ofast")
using namespace std;
const long long INF=20000000000;
//setprecision(2) <<

int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n;
	cin>>n;
	int a[n+1];
	int b[n+1];
	for(int i=1;i<=n;i++){
		cin>>a[i];
		b[i]=0;
	}
	
	int m=0;
	for(int i=n;i>=1;i--){
		if(i*2>n){
			//only 1
			b[i]=a[i];
		}
		else{
			int other=0;
			int now=2;
			while(now*i<=n){
				other+=b[now*i];
				now++;
			}
			if((other-a[i]+2)%2==0)b[i]=0;
			else b[i]=1;
		}
		if(b[i]!=0)m++;
	}
	cout<<m<<endl;
	for(int i=1;i<=n;i++){
		if(b[i]!=0)cout<<i<<endl;
	}
	
}
	


Measured memory_bytes: 2560
n = gets.to_i
s = gets.chomp

tally = s.chars.tally
tally.default = 0
answer = tally['R'] * tally['G'] * tally['B']

(0...n).each do |i|
  (1..n).each do |d|
    break if (i + 2 * d) >= n

    if s[i] != s[i + d] && s[i + d] != s[i + 2 * d] && s[i + 2 * d] != s[i]
      answer -= 1
    end
  end
end

puts answer


Measured memory_bytes: 14696
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		long X = sc.nextLong();
		long t = sc.nextLong();
		if(X>t) {
			System.out.println(X-t);
		} else {
			System.out.println(0);
		}
	}

}

Measured memory_bytes: 21716
import numpy as np

N = int(input())
H = list(map(int, input().split()))

# DP
cost = list()
cost.append(0) # start
cost.append(abs(H[1]-H[0]))

for n in range(2,N):
  MIN = min(
    cost[-1] + abs(H[n]-H[n-1]),
    cost[-2] + abs(H[n]-H[n-2])
  )
  cost.append(MIN)
  
print(cost[-1])

Measured memory_bytes: 22836
from bisect import bisect_left
N=int(input())
A=sorted(list(map(int,input().split())))
cnt=0
for i in range(N-1):
    for j in range(i+1,N):
        a=bisect_left(A,A[i]+A[j])
        if j<a:
            cnt+=a-j-1
print(cnt)

Measured memory_bytes: 3188
#include <bits/stdc++.h>
using namespace std;
#define _MACRO(_1, _2, _3, NAME, ...) NAME
#define _repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define _rep(i,n) _repl(i,0,n)
#define rep(...) _MACRO(__VA_ARGS__, _repl, _rep)(__VA_ARGS__)
#define pb push_back
#define all(x) begin(x),end(x)
#define uniq(x) sort(all(x)),(x).erase(unique(all(x)),end(x))
#ifdef LOCAL
#define dbg(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
void _dbg(string){cerr<<endl;}
template<class H,class... T> void _dbg(string s,H h,T... t){int l=s.find(',');cerr<<s.substr(0,l)<<" = "<<h<<", ";_dbg(s.substr(l+1),t...);}
template<class T,class U> ostream& operator<<(ostream &o, const pair<T,U> &p){o<<"("<<p.first<<","<<p.second<<")";return o;}
template<class T> ostream& operator<<(ostream &o, const vector<T> &v){o<<"[";for(T t:v){o<<t<<",";}o<<"]";return o;}
#else
#define dbg(...) {}
#endif

int main(){
  string s;
  cin>>s;

  if(s.size()==2) cout << s << endl;
  else reverse(all(s)), cout << s << endl;

  return 0;
}


Measured memory_bytes: 256
#include<cstdio>
#define ri register int
#define rc register char
#define ll long long int
#define rl register long long int
#define in inline
#define gc getchar
#define N 200005
in ll read()
{
	rl x=0,p=1;
	rc ch=gc();
	while(ch<'0' || ch>'9')
	{
		if(ch=='-')
		{
			p=-1;
		}
		ch=gc();
	}
	while(ch>='0' && ch<='9')
	{
		x=x*10+ch-'0',ch=gc();
	}
	return x*p;
}
ll n,a[N],book[N],ans;
int main()
{
	n=read();
	for(ri i=1;i<=n;++i)
	{
		a[i]=read(),++book[a[i]];
	}
	for(ri i=1;i<=n;++i)
	{
		ans+=book[i]*(book[i]-1)/2;
	}
	for(ri i=1;i<=n;++i)
	{
		printf("%lld\n",ans-book[a[i]]+1);
	}
	return 0;
}

Measured memory_bytes: 4608