akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define rep(i,m,n) for(int i=m; i<n; i++)
#define co(n) cout << n << endl
using namespace std;
int main(){
  string s;
  cin >> s;
  
  int c=0;
  rep(i,0,4) if(s.at(i)=='2') c++;
  co(c);
  
  
  return 0;
}


Measured memory_bytes: 256
<?php

$max = 1 - 10**9;
fscanf(STDIN, '%d', $count);
for ($i = 0; $i < $count; $i++) {
  fscanf(STDIN, '%d', $num);
  if($i == 0){
    $min = $num;
  }else{
    if($num - $min > $max){
      $max = $num - $min;
    }
  }
  
  if($min > $num){
    $min = $num;
  }
}

echo $max . PHP_EOL;



Measured memory_bytes: 9220
n=int(input())
s=list(map(int,input().split()))
m=int(input())
for i in range(m):
    b,e,t=map(int,input().split())
    for k in range(e-b):
        s[b+k],s[t+k]=s[t+k],s[b+k]
print(*s)


Measured memory_bytes: 5832
import java.util.*;
import java.io.*;
import java.math.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;
import static java.util.Collections.*;

public class Main{
    static long mod=1000000007;
    // static int dx[]={1,-1,0,0};
    // static int dy[]={0,0,1,-1};
    // static int dx[]={1,-1,0,0,1,1,-1,-1};
    // static int dy[]={0,0,1,-1,1,-1,1,-1};
    // PriorityQueue<Integer> que = new PriorityQueue<Integer>(); 
    //HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
    //ArrayList<Integer> lis = new ArrayList<Integer>();
    public  static void main(String[] args)   throws Exception, IOException{
        Reader sc = new Reader(System.in);
        PrintWriter out=new PrintWriter(System.out);

        int n=sc.nextInt();
        int d[]=new int[n];
        int e[]=new int[n];
        for( int i=0; i<n; i++ ){
            int x=sc.nextInt();
            while(x%2==0){d[i]++; x/=2;}
        }
        sort(d);
        String a="Yes";
        for( int i=0,c=0,t; i<n/2+n%2; i++ ){
            t=n-i-1;
            e[c++]=d[i];
            if(i!=t)e[c++]=d[t];
        }
        // db(d,e);
        for( int i=0; i+1<n; i++ ){
            if(e[i]+e[i+1]<2){a="No";break;}
        }    

       
        out.println(a); 
        out.flush();
    }

    static void db(Object... os){
        System.err.println(Arrays.deepToString(os));
    }

    static boolean validpos(int x,int y,int r, int c){
        return x<r && 0<=x && y<c && 0<=y;
    }
     
    static boolean bit(long x,int k){
        // weather k-th bit (from right) be one or zero
        return  ( 0 < ( (x>>k) & 1 )  )  ? true:false;
    }
}

class Pair implements Comparable<Pair>{
    int x,y,id;
    Pair(int x, int y,int id) {
        this.x=x;
        this.y=y;
        this.id=id;
    } 
    public int compareTo(Pair p){
        return p.x -     x;
    } 
}

// class Pair implements Comparable<Pair>{
//     int x,y;
//     Pair(int x, int y) {
//         this.x=x;
//         this.y=y;
//     } 
//     public int compareTo(Pair p){//descend
//         return p.x - x;
//     } 

// }

class P implements Comparable<P>{
    int diff,id1,id2;
    P(int diff, int id1,int id2) {
        this.diff=diff;
        this.id1=id1;
        this.id2=id2;
    } 
      
    public int compareTo(P p){//ascend
        return diff - p.diff;
    } 
}

class Reader
{ 
    private BufferedReader x;
    private StringTokenizer st;
    
    public Reader(InputStream in)
    {
        x = new BufferedReader(new InputStreamReader(in));
        st = null;
    }
    public String nextString() throws IOException
    {
        while( st==null || !st.hasMoreTokens() )
            st = new StringTokenizer(x.readLine());
        return st.nextToken();
    }
    public int nextInt() throws IOException
    {
        return Integer.parseInt(nextString());
    }
    public long nextLong() throws IOException
    {
        return Long.parseLong(nextString());
    }
    public double nextDouble() throws IOException
    {
        return Double.parseDouble(nextString());
    }
}

Measured memory_bytes: 35600
#include<bits/stdc++.h>
using namespace std;
void lcs(string X, string Y){
  int m = X.size();
  int n = Y.size();
  int L[m+1][n+1];
  for(int i=0;i<=m;i++){
    for(int j=0;j<=n;j++){
      if(i==0 || j==0){
        L[i][j]=0;
      }
      else if(X[i-1]==Y[j-1]){
        L[i][j]=1+L[i-1][j-1];
      }
      else{
        L[i][j]=max(L[i-1][j],L[i][j-1]);
      }
    }
  }
  int len = L[m][n];
  char lcs[len+1];
  lcs[len] = '\0';

  int i=m,j=n;
  while(i>0 && j>0){
    if(X[i-1]==Y[j-1]){
      lcs[len-1]=X[i-1];
      len--,i--,j--;
    }
    else if(L[i-1][j] > L[i][j-1]){
      i--;
    }
    else{
      j--;
    }
  }
  cout << lcs << "\n";
}
int main(){
  string a,b;
  cin >> a >> b;
  lcs(a,b);
}


Measured memory_bytes: 35456
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <math.h>

#define ll long long
#define ull unsigned long long

using namespace std;

const int inf = 1000000000;
const double eps = 1e-7;
const int mod = 1000000007;

int egcd(int a, int b, int &x, int &y) {
	if (a == 0) {
		x = 0;
		y = 1;
		return b;
	}
	int x1, y1;
	int g = egcd(b % a, a, x1, y1);
	x = y1 - (b / a) * x1;
	y = x1;
	return g;
}

int mod_inverse(int a, int m) {
	int x, y;
	int g = egcd(a, m, x, y);
	return g != 1 ? -1 : (x % m + m) % m;
}

int cnk(int n, int k) {
	int res = 1;
	for (int i = n - k + 1; i <= n; ++i)
		res = (res * 1ll * i) % mod;
	for (int i = 2; i <= k; ++i)
		res = res * 1ll * mod_inverse(i, mod) % mod;
	return res;
}

int binpow(int a, int p) {
	if (p == 0)
		return 1;
	if (p & 1)
		return binpow(a, p - 1) * 1ll * a % mod;
	else {
		int res = binpow(a, p / 2);
		return res * 1ll * res % mod;
	}
}

void solve() {
	int n, a, b;
	cin >> n >> a >> b;
	cout << ((binpow(2, n) - 1 - cnk(n, a) + mod) % mod - cnk(n, b) + mod) % mod << endl;
}

int main() {
	int t = 1;
	//cin >> t;
	for (int i = 0; i < t; ++i)
		solve();
	return 0;
}

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

int main()
{
  int n,m,a[MAX],x,y;
  bool b[MAX];

  for(int i=0;i<MAX;i++){
    a[i]=1;
    b[i]=false;
  }
  b[0]=true;

  cin>>n>>m;

  for(int i=0;i<m;i++){
    cin>>x>>y;
    x--;y--;
    a[x]--;
    a[y]++;
    b[y]|=b[x];
    if(a[x]==0)b[x]=false;
  }
  int ans=0;
  for(int i=0;i<n;i++){
    if(b[i] && a[i])ans++;
  }
  cout<<ans<<endl;
  return 0;
}

Measured memory_bytes: 5120
// C++ 14
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <algorithm>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <unordered_map>
#include <math.h>

#define ll long long
#define Int ll
#define loop(x, start, end) for(Int x = start; x < end; x++)
#define loopdown(x, start, end) for(int x = start; x > end; x--)
#define rep(n) for(Int x = 0; x < n; x++)
#define span(a,x,y) a.begin()+x,a.begin()+y
#define span_all(a) a.begin(),a.end()
#define len(x) (x.size())
#define last(x) (x[x.size()-1])

using namespace std;

struct Point {
  Int x, y;
  Point(Int x, Int y): x(x), y(y) {}
  Point(): x(0), y(0) {}

  bool operator< (const Point &p1) {
    return x < p1.x && y < p1.y;
  }
};
ostream & operator << (ostream & out, Point const & v) {
  out << "Point(" << v.x << ", " << v.y << ')';
  return out;
}

istream & operator >> (istream & in, Point & v) {
  Int x, y;
  in >> x; in >> y; v.x = x; v.y = y;
  return in;
}

// Geometry

#define EPS 0.0000000001

class Vector2 {
public:
  double x, y;
  
  Vector2(double x = 0, double y = 0): x(x), y(y) {}
  
  Vector2 operator + (Vector2 v) { return Vector2(x + v.x, y + v.y); }
  Vector2 operator - (Vector2 v) { return Vector2(x - v.x, y - v.y); }
  Vector2 operator * (double k) { return Vector2(x * k, y * k); }
  Vector2 operator / (double k) { return Vector2(x / k, y / k); }
  
  double length() { return sqrt(norm()); }
  double norm() { return x * x + y * y; }
  double dot (Vector2 v) { return x * v.x + y * v.y; }
  double cross (Vector2 v) { return x * v.y - y * v.x; }
  
  bool operator < (const Vector2 &v) const {
    return x != v.x ? x < v.x : y < v.y;
  }
  
  bool operator == (const Vector2 &v) const {
    return fabs(x - v.x) < EPS && fabs(y - v.y) < EPS;
  }
};

ostream & operator << (ostream & out, Vector2 const & v) {
  out<< "Vector2(" << v.x << ", " << v.y << ')';
  return out;
}

istream & operator >> (istream & in, Vector2 & v) {
  double x, y;
  in >> x;
  in >> y;
  v.x = x;
  v.y = y;
  return in;
}

#define MAX_X 1001
#define INFTY 2000
string X, Y;

vector<vector<Int> > dp(MAX_X, vector<Int>(MAX_X, INFTY));

//   abc
// edabc
Int ed(Int x, Int y, Int depth) {
  if (x >= X.size() || y >= Y.size()) {
    if (x == X.size()) return Y.size() - y;
    else return X.size() - x;
  }
  if (dp.at(x).at(y) < INFTY) return dp.at(x).at(y);
  Int val;
  if (X.at(x) == Y.at(y)) {
    val = ed(x + 1, y + 1, depth + 1); // same
  }
  else {
    val = min(
      1 + ed(x + 1, y + 1, depth + 1), // edit
      min(
        1 + ed(x + 1, y, depth + 1), // remove X.at(x)
        1 + ed(x, y + 1, depth + 1) // remove Y.at(y)
      )
    );
  }
  dp.at(x).at(y) = val;
  return val;
}

void solve() {
  cout << ed(0, 0, 0) << endl;;
}

void input() {
  cin >> X >> Y;
}

int main() {
  input();
  solve();
  return 0;
}



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

int main(){
  string s,t;
  ll m,n;
  cin >> s >> t;
  m=s.size();
  n=t.size();
  ll i,j,c,r;
  r=1001;
  for(i=0;i<m-n+1;i++){
    c=0;
    for(j=0;j<n;j++){
      if(s.at(i+j)!=t.at(j)){
        c++;
      }
    }
    r=min(c,r);
  }
  cout << r << endl;
}


Measured memory_bytes: 3620
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		
		try (Scanner sc = new Scanner(System.in)) {
			int N = Integer.parseInt(sc.next());
			
			int[] V = new int[N];
			for(int i = 0; i < N; i++) {
				V[i] = Integer.parseInt(sc.next());
			}
			int[] C = new int[N];
			for(int i = 0; i < N; i++) {
				C[i] = Integer.parseInt(sc.next());
			}
			
			int ret = 0;
			for(int i = 0; i < N; i++) {
				if(V[i] > C[i]) ret += V[i] - C[i];
			}
			
			System.out.println(ret); 
		} // Scanner Close
	}
}

Measured memory_bytes: 23764
n = int(raw_input())
ax = []
bx = []
for _ in xrange(n):
    a,b = map(int,raw_input().split())
    ax.append(a)
    bx.append(b)

ax = ax[::-1]
bx = bx[::-1]
cnt = 0
for i in xrange(n):
    if (ax[i] + cnt) % bx[i] !=0:
        k = bx[i] - ((ax[i] + cnt) % bx[i])
        cnt += k

print cnt


Measured memory_bytes: 9796
N = int(input())
L = list(map(int,input().split()))

import itertools
ans = 0

C = itertools.combinations(L, 3)
for i in C:
  tmp = list(i)
  tmp.sort()
  if tmp[2] < tmp[0] + tmp[1]:
    if tmp[0] != tmp[1] and tmp[0] != tmp[2] and tmp[1] != tmp[2]:
      ans += 1

print(ans) 

Measured memory_bytes: 9192
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        // Your code here!
        Scanner sc = new Scanner(System.in);
        int N = Integer.parseInt(sc.next());
        int X = Integer.parseInt(sc.next());
        int Y = Integer.parseInt(sc.next());
        sc.close();
        
        int max1 = Y;
        if (X<Y) {
            max1 = X;
        }
        int min1 = 0;
        if (N<X+Y) {
            min1 = X+Y -N;
        }
        
        System.out.println(Integer.toString(max1) + " " + Integer.toString(min1));
    }
}

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

string words[4]={"dream","dreamer","erase","eraser"};

int main(){
  int N, K;
  cin >> N >> K;
  int a[N];
  int locate;
  for(int i=0;i<N;i++){
  	cin >> a[i];
  }

  int ans;
  ans = ((N-1)+(K-1)-1)/(K-1);

  cout << ans <<endl;

  return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
 
 
#define FAST_IO ios_base::sync_with_stdio(false), cin.tie(nullptr)
using namespace std;
 
signed main() {
    FAST_IO;
 
    int n;
    cin >> n;
    int a[n], b[n], c[n];
    for (int i = 0; i < n; i++) cin >> a[i] >> b[i] >> c[i];

    int dp[n][3]; // dp[i][j] : i represents the day and j represents the activity
    				         // j is 0 for activity A, 1 for activity B and 2 for activity C

  	// Set the base values
    dp[0][0] = a[0]; // If you swim in the sea in sea on the first day, you cannot get more than a[0] points.
    dp[0][1] = b[0]; // If you catch bugs in the mountains on the first day, you cannot get more than b[0] points.
    dp[0][2] = c[0]; // If you do homework at home on the first day, you cannot get more than c[0] points.

    // i represents what day it is (0 based indexing)
    for (int i = 1; i < n; i++) { 
        dp[i][0] = a[i] + max(dp[i - 1][1], dp[i - 1][2]); // If we do activity A today, we have to have done activities B or C on the previous day.
        dp[i][1] = b[i] + max(dp[i - 1][0], dp[i - 1][2]); // If we do activity B today, we have to have done activities A or C on the previous day.
        dp[i][2] = c[i] + max(dp[i - 1][1], dp[i - 1][0]); // If we do activity C today, we have to have done activities A or B on the previous day.
    }

  	// Our answer is the maximum of all the points gained by doing activity A, B, or C on the last day.
    cout << max({dp[n - 1][0], dp[n - 1][1], dp[n - 1][2]}); 
    return 0;
}

Measured memory_bytes: 2560
#include <bits/stdc++.h>
#ifdef DEMETRIO
#define deb(...) fprintf(stderr,__VA_ARGS__)
#define deb1(x) cerr << #x << " = " << x << endl
#else
#define deb(...) 0
#define deb1(x) 0
#endif
#define pb push_back
#define mp make_pair
#define fst first
#define snd second
#define fore(i,a,b) for(int i=a,ThxDem=b;i<ThxDem;++i)
#define SZ(x) ((int)(x).size())
#define mset(a,v) memset(a,v,sizeof(a))
#define mcpy(a,b) memcpy(a,b,sizeof(a))
using namespace std;
typedef long long ll;

int n;ll m;
ll f[100005];

int main(){
	scanf("%d%lld",&n,&m);
	fore(i,1,100005)f[i]=1LL<<60;
	f[0]=0;
	fore(i,0,n){
		ll w,v;
		scanf("%lld%lld",&w,&v);
		for(int i=100004;i>=v;--i	)f[i]=min(f[i],f[i-v]+w);
	}
	int r=100004;
	while(f[r]>m)r--;
	printf("%d\n",r);
	return 0;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < (n) ; i++)
#define rrep(i,n) for(int i = n-1; i >= 0 ; i--)
typedef long long ll;
constexpr auto INFI = 2147483647;
const ll INFL = 9223372036854775807;

int main(){
    const ll MOD = 1000000007;
    ll n, k;
    ll ans;
    ll cumsum[200001];
    cin >> n >> k;
    cumsum[0] = 0;
    rep(i,200000){
        cumsum[i+1] = cumsum[i] + i + 1;
    }
    ans = 1;
    for(int i = k; i<= n; i++){
        ans += cumsum[n] - cumsum[n - i] - cumsum[i - 1] + 1;
        ans %= MOD;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 5180
//do not think about past and stay in this moment
//organize and work - Abhinav IIITA
#include <bits/stdc++.h>
#include <ctime>
using namespace std;
#define int long long
#define ld long double
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(),(v).end() 
const ld pi = acos(-1.0);
const int day[12] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());



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

int arr[3000000];
void input(int n){
	for(int i=0;i<n;++i)
	cin>>arr[i];
}

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



void solve(){
	
    int n;
    cin>>n;
    n--;
    int l,r;
    cin>>l>>r;
    while(n--){
        int a,b;    cin>>a>>b;
        //let number be ax, bx;
        int a1=(l+a-1)/a;
        int a2=(r+b-1)/b;   // upper ceiled
        int x=max(a1,a2);
        l=a*x;
        r=b*x;
    }
    cout<<l+r;
}


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


int32_t main()
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0); 	
	int t=1;
	//cin>>t;
	while(t--)
	solve();
	return 0;
}


Measured memory_bytes: 256
#include <stdio.h> //heaps
#define MAX 500000
 
int n, A[MAX];
 
int left(int i)
{
  return 2*i;
}
 
int right(int i)
{
  return 2*i+1;
} 
 
void maxHeapify(int A[], int i)
{
 
  int temp, largest, l, r;
 
  l  = left(i);
  r = right(i);
 
  if(l<=n && A[l]>A[i])
    {
      largest = l;
    }else{
    largest = i;
  }
 
  if(r<=n && A[r]>A[largest])
    {
      largest = r;
    }
 
  if(largest != i)
    {
      temp = A[i];
      A[i] = A[largest];
      A[largest] = temp;
     
      maxHeapify(A, largest);
    }
}
 
void buildMaxHeap(int A[])
{
 
  int i;
  for(i=n/2;i!=0;i--)
    {
      maxHeapify(A,i);
    }
}
 
 
int main()
{
 
  int j,k;
 
  scanf("%d",&n);
   
  for(j=1;j<=n;j++)
    {
      scanf("%d",&A[j]);
    }
 
  buildMaxHeap(A);
 
  for(k=1;k<=n;k++)
    {
      printf(" %d",A[k]);
    }
  printf("\n");
  return 0;
}

Measured memory_bytes: 2548
#include<bits/stdc++.h>
#include<vector>
#include<list>
#include<stack>
#include<queue>
#include<algorithm>
using namespace std;

int main(){
    int mod=1000000007;
    int n;
    int ans;
    double xa,ya,ra,xb,yb,rb;
    scanf("%d",&n);
    for (int i=0;i<n;i++) {
        scanf("%lf %lf %lf %lf %lf %lf",&xa,&ya,&ra,&xb,&yb,&rb);
        double tmp=sqrt((xa-xb)*(xa-xb)+(ya-yb)*(ya-yb));
        if ((tmp+rb)<ra) {
            printf("2\n");
        } else if ((tmp+ra)<rb) {
            printf("-2\n");
        } else if ((tmp)>(ra+rb)) {
            printf("0\n");
        } else {
            printf("1\n");
        }
    }
    return 0;
}

Measured memory_bytes: 3192
#include<bits/stdc++.h>
using namespace std;
typedef string::const_iterator state;
map<char,char>conv;
int N,K;

vector<int>A[26];

vector<int>expression(state &);


vector<int>add(vector<int>&a,vector<int>&b){
    vector<int>ret(N);
    for(int i=0;i<N;i++){
        ret[i]=a[b[i]];
    }
    return ret;
}


vector<int>mul(vector<int>&a,int m){
    vector<int>ret(N);
    for(int i=0;i<N;i++)ret[i]=i;

    while(m){
        if(m&1)ret=add(ret,a);
        a=add(a,a);
        m>>=1;
    }
    return ret;
}

vector<int>fact(state &b){
    vector<int>ret;
    if(*b=='('){
        b++;
        ret=expression(b);
        b++;
    }
    else{
        ret=A[*b-'A'];
        b++;
    }
    return ret;
}

vector<int>number(state &b){
    vector<int>ret;
    int num=0;
    while(isdigit(*b)){
        num=num*10+*b-'0';
        b++;
    }
    if(num==0)num=1;
    vector<int>x=fact(b);
    return mul(x,num);
}

vector<int>expression(state &b){
    vector<int>ret=number(b);
    while(true){
        if(*b=='+'){
            b++;
            vector<int>x=number(b);
            ret=add(ret,x);
        }
        else break;
    }
    return ret;
}

int main(){
    scanf("%d%d",&N,&K);

    for(int i=0;i<K;i++){
        char p;int h;
        scanf(" %c%d",&p,&h);
        conv[p]=i+'A';
        A[i].resize(N);
        for(int j=0;j<N;j++)A[i][j]=j;
        for(int j=0;j<h-1;j++){
            for(int k=0;k<N-1;k++){
                int f;scanf("%d",&f);
                if(f)swap(A[i][k],A[i][k+1]);
            }
        }
    }

    int Q;
    scanf("%d",&Q);
    while(Q--){
        string str;
        cin>>str;str+="=";
        for(int i=0;i<str.size();i++){
            if(isupper(str[i]))str[i]=conv[str[i]];
        }

        state b=str.begin();
        vector<int>ans=expression(b);
        for(int i=0;i<N;i++){
            if(i)cout<<" ";
            cout<<ans[i]+1;
        }cout<<endl;
    }
    return 0;
}

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

using namespace std;

#define eb emplace_back
#define ii pair<int, int>
#define OK (cerr << "OK" << endl)
#define debug(x) cerr << #x " = " << (x) << endl
#define ff first
#define ss second
#define int long long
#define tt tuple<int, int, int>
#define all(x) x.begin(), x.end()
#define Matrix vector<vector<int>>
#define Mat(n, m, v) vector<vector<int>>(n, vector<int>(m, v))
#define endl '\n'

constexpr int INF = 2e18;
constexpr int MOD = 1e9 + 7;
constexpr int MAXN = 2e5 + 3;

// #define MULTIPLE_TEST_CASES
void solve() {
  int n;
  cin >> n;

  // vector<ii> arr;
  vector<ii> v1;
  vector<ii> v2;
  for (int i = 0; i < n; ++i) {
    int l, r;
    cin >> l >> r;
    v1.eb(l, r);
    v2.eb(r, l);
  }

  sort(all(v1));
  sort(all(v2), greater<ii>());

  int mid1 = v1[(n - 1) / 2].ff;
  int mid2 = v2[(n - 1) / 2].ff;

  // debug(mid1);
  // debug(mid2);
  if (n & 1)
    cout << max(0ll, mid2 - mid1 + 1) << endl;
  else {
    int m = n / 2 - 1;
    cout << max(0ll, v2[m].ff + v2[m + 1].ff - v1[m].ff - v1[m + 1].ff + 1)
         << endl;
  }
}

signed main() {

  ios_base::sync_with_stdio(false);
  cin.tie(NULL);

  int t = 1;

#ifdef MULTIPLE_TEST_CASES
  cin >> t;
#endif
  while (t--)
    solve();
}

Measured memory_bytes: 9776
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
using namespace std;
 
#define mod 1000000007
#define FOR(x,to) for(int x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
#define long long long
inline int rei(){int x;cin>>x;return x;}
inline long rel(){long x;cin>>x;return x;}
inline string res(){string x;cin>>x;return x;}
//------------------------------------------------------- 
void Calc(){
	int K = rei();
	if(K == 1){
		cout << 1 << endl;
		cout << 1 << endl;
		return;
	}
	int N = (K+1)/2;
	if(N % 2){
		N++;
	}
	cout << N << endl;
	for(int i=0;i<N;i++){
		if(i % 2 == 0){
			for(int j=0;j<N;j++){
				cout << (i+j) % N + 1;
				if(j != N-1){
					cout << " ";
				}
				else{
					cout << endl;
				}
			}
		}	
		else{
			for(int j=0;j<N;j++){
				int c = (i+j) % N;
				if(c+N < K){
					c += N;
				}
				cout << c + 1;
				if(j != N-1){
					cout << " ";
				}
				else{
					cout << endl;
				}
			}
		}
	}
}
int main(int argc,char** argv){
	ios::sync_with_stdio(false), cin.tie(0);
	cout.tie(0); Calc(); return 0;
}

Measured memory_bytes: 1152
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, input().split()))
def inpl_s(): return list(input().split())

N,M,Q = inpl()
kukan = []

for i in range(M):#加算
	l,r = inpl()
	kukan.append([r,-1,l])


for i in range(Q):#クエリ
	p,q = inpl()
	kukan.append([q,i,p])

kukan.sort()

li = [0]*(N+1)
ans = [0]*Q
for t,flag,s in kukan:
	if flag == -1: #加算
		li[s] += 1
	else:#クエリ
		ans[flag] = sum(li[s:t+1])

for a in ans:
	print(a)


Measured memory_bytes: 53616
#include <stdio.h>

int main(){
    int n, q, l, r, a[100000], i, cnt=0, ans[100000];
    char s[100000];

    scanf("%d %d", &n, &q);
    scanf("%s", s);

    for(i=0; i<n; i++){
        if(s[i-1] == 'A' && s[i] == 'C')
            cnt++;
        a[i] = cnt;
    }

    for(i=0; i<q; i++){
        scanf("%d %d", &l, &r);
        ans[i] = a[r-1] - a[l-1];
    }

    for(i=0; i<q; i++){
        printf("%d\n", ans[i]);
    }

    return 0;
}

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

int main(){
  int n;
  cin>>n;
  unsigned long long a[n];
  for(int i=0;i<n;i++){
  	cin>>a[i];
  }
  if(n<3) {cout<<0;
  return 0;}
  unsigned long long count=0;
  for(int i=0;i<n-2;i++){
  	for(int j=i+1;j<n-1;j++){
    	for(int k=j+1;k<n;k++){
        	if(a[i]==a[k] || a[i]==a[j] || a[k]==a[j])
              continue;
          	if(a[i]+a[j]<=a[k] || a[k]+a[j]<=a[i] || a[i]+a[k]<=a[j])
              continue;
          	count++;
        }
    }
  }
  cout<<count;
  return 0;
}

Measured memory_bytes: 3624
#include<iostream>
#include<algorithm>
#include<climits>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<string>
#include<cstring>
#include<vector>
#include<stack>
#include<queue>
#include<set>
#include<bitset>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> i_i;

#define PI 3.141592653589793238462643383279
#define mod 1000000007LL
#define rep(i, n) for(i = 0;i < n;++i)
#define rep1(i, n) for(i = 1;i < n;++i)
#define per(i, n) for(i = n - 1;i > -1;--i)
#define int(x) int x; scanf("%d",&x)
#define int2(x, y) int x, y; scanf("%d%d",&x, &y)
#define int3(x, y, z) int x, y, z; scanf("%d%d%d",&x, &y, &z)
#define int4(v, x, y, z) int v, x, y, z; scanf("%d%d%d%d", &v, &x, &y, &z)
#define int5(v, w, x, y, z) int v, w, x, y, z; scanf("%d%d%d%d%d", &v, &w, &x, &y, &z)
#define ll2(x, y) ll x, y; cin >> x >> y;
#define scn(n, a) rep(i, n)cin >> a[i]
#define sc2n(n, a, b) rep(i, n)cin >> a[i] >> b[i]
#define pri(x) cout << (x) << "\n"
#define pri2(x, y) cout << (x) << " " << (y) << "\n"
#define pri3(x, y, z) cout << (x) << " " << (y) << " " << (z) << "\n"
#define pb push_back
#define mp make_pair
#define all(a) (a).begin(),(a).end()
#define endl "\n"
#define kabe puts("---------------------------")
#define kara puts("")
#define debug(x) cout << " --- " << (x) << "\n"
#define debug2(x, y) cout << " --- " << (x) << " " << (y) << "\n"
#define debug3(x, y, z) cout << " --- " << (x) << " " << (y) << " " << (z) << "\n"
#define X first
#define Y second
#define eps 0.0001
#define prid(x) printf("%.15lf\n", x)

int x[50] = {0};
ll dp[51][51][2501] = {0};

signed main(void){
  int i, j, k;
  for(int testcase = 0;testcase >= 0;testcase++){
    int2(n, a);
    scn(n, x);

    dp[0][0][0] = 1;
    rep(i, n)rep(j, n)per(k, 2501){
      //pri3(i, j, k);
      dp[i + 1][j][k] += dp[i][j][k];
      if(k - x[i] >= 0)dp[i + 1][j + 1][k] += dp[i][j][k - x[i]];
    }

    ll res = 0;
    rep(i, n + 1){
      //pri2(i, dp[n][i][i * a]);
      res += dp[n][i][i * a];
    }
    pri(res - 1);


/*/

//*/ break;
  }
  return 0;
}


Measured memory_bytes: 50048
use std::io::*;
use std::str::FromStr;

fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char) 
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

fn main() {
    let mut c_ij: Vec<i32> = (0..9).map(|_| read()).collect();
    // println!("{:?}", c_ij);

    let mut ai: Vec<i32> = vec![-1; 3];
    let mut bj: Vec<i32> = vec![-1; 3];

    let mut min = c_ij[0];
    let mut argmin = 0;
    for i in 0..9 {
        if c_ij[i] < min {
            min = c_ij[i];
            argmin = i;
        }
    }

    // println!("{}", argmin);
    // println!("{}", min);

    for n in 0..9 {
        c_ij[n] -= min;
    }

    let i = argmin % 3;
    let j = argmin / 3;
    ai[i] = 0;
    bj[j] = 0;

    for n in 0..9 {
        let i = n % 3;
        let j = n / 3;
        if i != argmin % 3 && ai[i] == -1 && bj[j] != -1 {
            ai[i] = c_ij[n] - bj[j];
        }
        if j != argmin / 3 && ai[i] != -1 && bj[j] == -1 {
            bj[j] = c_ij[n] - ai[i];
        }
    }

    // println!("{:?}", ai);
    // println!("{:?}", bj);

    let mut ans = "Yes";
    for n in 0..9 {
        let i = n % 3;
        let j = n / 3;
        if ai[i] + bj[j] != c_ij[n] {
            ans = "No";
            break;
        }
    }

    println!("{}", ans);
}


Measured memory_bytes: 4352
#include<stdio.h>
int main(void){
    int H,W;
    int i,j;
    while(1){
        scanf("%d %d",&H,&W);
        if(H==0&&W==0)break;
        for(j=0;j<W;j++)printf("#");
        printf("\n");
        for(i=1;i<H-1;i++){
            printf("#");
            for(j=1;j<W-1;j++){
                printf(".");
            }
            printf("#");
            printf("\n");
        }
        for(j=0;j<W;j++)printf("#");
        printf("\n");
        printf("\n");
    }
    return 0;
}



Measured memory_bytes: 2032
#include <bits/stdc++.h>
using namespace std;
///////////////////////////////////////////
const long long int INF = 1LL<<60;
const long long int Mod = 1000000007;
using ll = long long int; using ci = const int;
using vi = vector<int>;  using Vi = vector<long long int>;
using P = pair<int, int>;  using PLL = pair<ll, ll>;
using matrix = vector<vector<ll>>;
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define all(x) (x).begin(),(x).end()
#define rp(i,N) for(ll i = 0; i < (ll)N; i++)
#define repi(i,a,b) for(ll i = ll(a); i < ll(b); ++i)
template<class T>bool chmax(T &former, const T &b) { if (former<b) { former=b; return true; } return false; }
template<class T>bool chmin(T &former, const T &b) { if (b<former) { former=b; return true; } return false; }
template<class T>T sqar(T x){ return x*x; }//sqrt(x)は平方根;
#define Sort(v) std::sort(v.begin(), v.end(), std::greater<decltype(v[0])>()) //降順でVをソート
#define p_queue(v) priority_queue<v, vector<v>, greater<v> >
template<class T> inline void princ(T x){cout<<x<<" ";}; 
template<class T> inline void print(T x){cout<<x<<"\n";};
template<class T> inline void Yes(T condition){ if(condition) cout << "Yes" << endl; else cout << "No" << endl; }
template<class T> inline void YES(T condition){ if(condition) cout << "YES" << endl; else cout << "NO" << endl; }
///////////////////////////////////////////////////////////////////////////////////

void solve(){
    int a,b;
    cin >> a >> b;
    print((a+b+1)/2);
    return;
}
int main(){
    cin.tie(0);ios::sync_with_stdio(false);
    std::cout<<std::fixed<<std::setprecision(30);
    solve();
    return 0;
}

Measured memory_bytes: 3604
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int INF = 100100100;

int main() {
    //ll N; cin >> N;
    //ll N,M; cin >> N >> M;
    string S; cin >> S;
    //ll H,W; cin >> H >> W;
    int N;
    N=S.length();
    int nu[N][13];
    for(int i=0;i<13;i++){
        for(int j=0;j<N;j++){
            nu[j][i]=0;
        }
    }
  	int p;
    if(S[0]=='?'){
        int dig=N%6;
        if(dig==1){
            for(int j=0;j<10;j++){
                nu[0][j]++;
            }
        }
        if(dig==2){
            for(int j=0;j<10;j++){
                nu[0][(j*10)%13]++;
            }
        }
        if(dig==3){
            for(int j=0;j<10;j++){
                nu[0][(j*9)%13]++;
            }
        }
        if(dig==4){
            for(int j=0;j<10;j++){
                nu[0][(j*12)%13]++;
            }
        }
        if(dig==5){
            for(int j=0;j<10;j++){
                nu[0][(j*3)%13]++;
            }
        }
        if(dig==0){
            for(int j=0;j<10;j++){
                nu[0][(j*4)%13]++;
            }
        }
    }
    else{
        int x=S[0]-'0';
        int dig=(N-1)%6;
        p=pow(10,dig);
        p=p%13;
        nu[0][(x*p)%13]++;
    }
    for(int i=1;i<N;i++){
        int dig=(N-i-1)%6;
        p=pow(10,dig);
        p=p%13;
        if(S[i]=='?'){
            for(int j=0;j<10;j++){
                for(int k=0;k<13;k++){
                    nu[i][(k+p*j)%13]+=nu[i-1][k];//ココアyたしい
                  	nu[i][(k+p*j)%13]=nu[i][(k+p*j)%13]%mod;
                }
            }
        }
        else{
            int x=S[i]-'0';
            for(int j=0;j<13;j++){
                nu[i][(j+p*x)%13]+=nu[i-1][j];
              	nu[i][(j+p*x)%13]=nu[i][(j+p*x)%13]%mod;
            }
        }
    }
    cout << nu[N-1][5];
}

/*

観自在菩薩・行深般若波羅蜜多時、照見五蘊皆空、度一切苦厄。舎利子。色不異空、空不異色、色即是空、空即是色。受・想・行・識・亦復如是。舎利子。是諸法空相、不生不滅、不垢不浄、不増不減。是故空中、無色、無受・想・行・識、無眼・耳・鼻・舌・身・意、無色・声・香・味・触・法。無眼界、乃至、無意識界。無無明・亦無無明尽、乃至、無老死、亦無老死尽。無苦・集・滅・道。無智、亦無得。以無所得故、菩提薩埵、依般若波羅蜜多故、心無罜礙、無罜礙故、無有恐怖、遠離・一切[注 6]・顛倒夢想、究竟涅槃。三世諸仏、依般若波羅蜜多故、得阿耨多羅三藐三菩提。故知、般若波羅蜜多、是大神呪、是大明呪、是無上呪、是無等等呪、能除一切苦、真実不虚。故説、般若波羅蜜多呪。
即説呪曰、羯諦羯諦、波羅羯諦、波羅僧羯諦、菩提薩婆訶。般若心経

 */



Measured memory_bytes: 5504
using static System.Math;
using System;

public class Hello
{
    public static void Main()
    {
        var n = int.Parse(Console.ReadLine().Trim());
        if (n == 1 | n == 2) { Console.WriteLine(0); goto exit; }
        string[] line = Console.ReadLine().Trim().Split(' ');
        var a = Array.ConvertAll(line, int.Parse);
        var a2 = Array.ConvertAll(line, int.Parse);
        var ans1 = getAnsUp(a, n);
        var ans2 = getAnsDown(a2, n);
        Console.WriteLine(Min(ans1, ans2));
        exit:;
    }
    static void swap(int[] a, int p)
    {
        var w = a[p];
        a[p] = a[p + 1];
        a[p + 1] = w;
    }
    static int getAnsDown(int[] a, int n)
    {
        var count = 0; var p = 1;
        var st = "dwn";
        if (a[0] < a[1]) { swap(a, 0); count++; }
        while (p < n - 2)
        {
            if (st == "up" && a[p + 1] > a[p])
            {
                if (p + 2 <= n - 1 && a[p + 2] < a[p] && a[p + 2] < a[p + 1]) { swap(a, p + 1); count++; p += 2; }
                else { swap(a, p); count++; p++; st = "dwn"; }
            }
            else if (st == "dwn" && a[p + 1] < a[p])
            {
                if (p + 2 <= n - 1 && a[p + 2] > a[p] && a[p + 2] > a[p + 1]) { swap(a, p + 1); count++; p += 2; }
                else { swap(a, p); count++; p++; st = "up"; }
            }
            else if (st == "up" && a[p + 1] < a[p]) { st = "dwn"; p++; }
            else { st = "up"; p++; }
        }
        return count;

    }
    static int getAnsUp(int[] a, int n)
    {
        var count = 0; var p = 1;
        var st = "up";
        if (a[0] > a[1]) { swap(a, 0); count++; }
        while (p < n - 2)
        {
            if (st == "up" && a[p + 1] > a[p])
            {
                if (p + 2 <= n - 1 && a[p + 2] < a[p] && a[p + 2] < a[p + 1]) { swap(a, p + 1); count++; p += 2; }
                else { swap(a, p); count++; p++; st = "dwn"; }
            }
            else if (st == "dwn" && a[p + 1] < a[p])
            {
                if (p + 2 <= n - 1 && a[p + 2] > a[p] && a[p + 2] > a[p + 1]) { swap(a, p + 1); count++; p += 2; }
                else { swap(a, p); count++; p++; st = "up"; }
            }
            else if (st == "up" && a[p + 1] < a[p]) { st = "dwn"; p++; }
            else { st = "up"; p++; }
        }
        if (st == "up" && a[p + 1] > a[p]) { swap(a, p); count++; p++; st = "dwn"; }
        else if (st == "dwn" && a[p + 1] < a[p]) { swap(a, p); count++; p++; st = "up"; }
        else if (st == "up" && a[p + 1] < a[p]) { st = "dwn"; p++; }
        else { st = "up"; p++; }
        return count;
    }
}



Measured memory_bytes: 33772
#include<iostream>
using namespace std;
int main()
{
    int n;
    scanf("%d",&n);
    int num=n%10;
    if(num==3)
        printf("bon");
    else if(num==0||num==1||num==6||num==8)
        printf("pon");
    else
        printf("hon");
    return 0;
}


Measured memory_bytes: 3196
#include<cstdio>
using namespace std;
int main()
{
    int n,i,res;
    double t,v,h;
    while(scanf("%lf", &v)==1)
    {
        t=(v/9.8);
        h=4.9*t*t;
        for(n=1;;n++)
        {
            res=5*n-5;
            if(res>h)
                break;
        }
        printf("%d\n",n);
    }
    return 0;
}

Measured memory_bytes: 1056
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

n = int(input())
A = list(map(int,input().split()))
dp0 = [0] * (n+11)
dp1 = [0] * (n+11)
dp2 = [0] * (n+11)
for i,ai in enumerate(A):
  dp2[i+11] = (max(dp0[i+7] + ai, dp1[i+8] + ai, dp2[i+9] + ai) if i >= 2 else 0)
  dp1[i+11] = (max(dp0[i+8] + ai, dp1[i+9] + ai) if i >= 1 else 0)
  dp0[i+11] = dp0[i+9] + ai 
if n % 2 == 0:
  print(max(dp0[n + 9], dp1[n + 10]))
else:
  print(max(dp0[n + 8], dp1[n + 9], dp2[n + 10]))

# debug
# print(dp0,dp1,dp2,sep="\n")




Measured memory_bytes: 51120
// 3 3 - 4

#include <stdio.h>
#include <string.h>

int main(void)
{
	int n;
	int out;
	int run;
	int score;
	int i, j;
	char str[10];
	
	scanf("%d", &n);
	
	for (i = 0; i < n; i++){
		out = 0;
		score = 0;
		run = 0;
		while (out != 3){
			scanf("%s", str);
			if (strcmp(str, "HIT") == 0){
				run++;
				if (run > 3){
					score++;
					run = 3;
				}
			}
			else if(strcmp(str, "HOMERUN") == 0){
				score += run + 1;
				run = 0;
			}
			else if(strcmp(str, "OUT") == 0){
				out++;
			}
		}
		printf("%d\n", score);
	}
	return (0);
}
			
//なんでや！阪神関係ないやろ！

Measured memory_bytes: 596
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
#include<bitset>
using namespace std;
typedef long long ll;
typedef unsigned int ui;
const ll MOD = (1e+9)+7;
const ll INF = (ll)1000000007 * 1000000007;
typedef pair<int, int> P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
typedef long double ld;
typedef complex<ld> Point;
const ld eps = 1e-11;
const ld pi = acos(-1.0);
typedef pair<ll, ll> LP;
typedef pair<ld, ld> LDP;
typedef pair<ll,P> PP;
int main() {
	string s; cin >> s; string t = s; reverse(t.begin(), t.end());
	if (s == t)cout << "Yes" << endl;
	else cout << "No" << endl;
	return 0;
}

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

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}

fn read_vec2<T: std::str::FromStr>(n: usize) -> Vec<Vec<T>> {
    (0..n).map(|_| read_vec()).collect()
}

fn read_col<T: std::str::FromStr>(n: usize) -> Vec<T> {
    (0..n).map(|_| read()).collect()
}

fn main() {
    let nkq: Vec<usize> = read_vec();
    let av: Vec<usize> = read_col(nkq[2]);
    let mut ans: Vec<usize> = vec![0; nkq[0]];
    for a in av {
        ans[a - 1] += 1;
    }
    for tmp in ans {
        if tmp + nkq[1] > nkq[2] {
            println!("Yes");
        } else {
            println!("No");
        }
    }
}


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

int main(){
  string S;
  cin >> S;
  int p=0;
  for(int i=1; i<S.size(); i++){
    if(S.at(i)=='p') p++;
  }
  int ans= S.size()/2-p;
  
  cout << ans << endl;
}


Measured memory_bytes: 512
#include <iostream>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <algorithm>
#include <set>
#include <map>
#include <bitset>
#include <cmath>
#include <functional>
#define vv(a, b, c, d) vector<vector<d> >(a, vector<d>(b, c))
#define vvi vector<vector<int> >
#define vvl vector<vector<ll> >
#define vll vector<ll>
#define rep(c, a, b) for(ll c=a;c<b;c++)
#define re(c, b) for(ll c=0;c<b;c++)
#define all(obj) (obj).begin(), (obj).end()
typedef long long int ll;
typedef long double ld;
using namespace std;

int main(int argc, char const *argv[]) {
  ll n;std::cin >> n;
  ll a = 1, b = 1, c;
  re(i,n) a*=3;
  re(i, n){
    std::cin >> c;
    if(c%2==0) b*=2;
    else b*=1;
  }
  std::cout << a - b << '\n';
}


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

int beki(int a, int b){
  int ans = 1;
  for(int i = 0; i < b; i++){
    ans *= a;
  }
  return ans;
}

int main() {

  int H, W, K;
  cin >> H >> W >> K;

  char c[H][W];

  for(int i = 0; i < H; i++){
    for(int j = 0; j < W; j++){
      cin >> c[i][j];
    }
  }

  int tmp;
  int ans = 0;

  for(int i = 0; i < beki(2, H); i++){
    for(int j = 0; j < beki(2, W); j++){
      tmp = 0;
      for(int k = 0; k < H; k++){
        for(int l = 0; l < W; l++){
          if(i & (1 << k) && j & (1 << l)){
            if(c[k][l] == '#'){
              tmp++;
            }
          }
        }
      }
      if(tmp == K){
        ans++;
      }
    }
  }
  cout << ans << endl;
}

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

P s[100000], p[200000];
int main() {
	int n, m; scanf("%d%d", &n, &m);
	rep(i, m)scanf("%d%d", &s[i].first, &s[i].second);
	rep(i, n)p[i] = { i,i };
	sort(s, s + m);
	rep(i, m) {
		int a = min(p[s[i].second - 1].first, p[s[i].second].first);
		int b = max(p[s[i].second - 1].second, p[s[i].second].second);
		p[s[i].second - 1] = p[s[i].second] = { a,b };
	}
	rep(i, n) {
		if (i)printf(" ");
		printf("%d", p[i].second - p[i].first + 1);
	}
	printf("\n");
}

Measured memory_bytes: 5556
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <cmath>

using namespace std;

typedef long long int ll;
typedef unsigned long long int ull;
typedef vector<int> vii;
typedef vector<pair<int,int>> vip;

#define ZOOM ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define pb push_back
#define fi first
#define se second
#define all(v) (v).begin(),(v).end()
#define loop for(int i=0;i<n;++i)
#define LOOP_IT(s) for(auto it=(s).begin();it!=(s).end();++it)


int main(int argc,char* argv[])
{
    ZOOM

    ull r,c,i1=0,i2,ans;
    cin>>r>>c;

    if(!(r&1)) i1=r/2;
    else i1=r/2+1;


    if(r&1) i2=i1-1;
    else i2=i1;

    if(c&1) ans=(1ull*(r)*(c/2))+i1;
    else ans=r*(c/2)*1ull;

    if(r==1||c==1)
        ans=1;


    cout<<ans<<"\n";



    return 0;
}



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

using namespace std;

long long sum, cnt, mom;
char s[202020];

int main()
{
	scanf("%s", s + 1);
	int len = strlen(s + 1);
	for (int i = 1; i <= len; ++i) if (s[i] == 'W') ++cnt, sum += i;
	for (int i = 1; i <= cnt; ++i) mom += i;
	printf("%lld\n", sum - mom);
	return 0; 
}

Measured memory_bytes: 384
from collections import Counter

N, *A = map(int, open(0).read().split())

C = Counter(A)
A.sort(reverse=True)

ans = 0
for a in A:
    if C[a] == 0:
        continue
    C[a] -= 1

    b = 2 ** a.bit_length() - a
    if C[b] > 0:
        C[b] -= 1
        ans += 1

print(ans)


Measured memory_bytes: 33712
#include<stdio.h>
int main()
{
	int a,b,t,i,sum=0;
	scanf("%d %d %d",&a,&b,&t);
	for(i=1;i<=t;i++)
	{
		if(i%a==0)
		{
			sum+=b;
		}
	}
	printf("%d\n",sum);
	return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
int main(){
    int N,M;
    cin>>N>>M;
    vector<string> A(N),B(M);
    for(int i=0;i<N;i++){
        cin>>A[i];
    }
    for(int i=0;i<M;i++){
        cin>>B[i];
    }
    for(int i=0;i<N-M+1;i++){//点の座標
        for(int j=0;j<N-M+1;j++){
            for(int k=0;k<M;k++){
                if(A[j+k].substr(i,M)!=B[k]){break;}
                if(k==M-1){cout<<"Yes"<<endl;exit(0);}
            }
        }
    }
    cout<<"No"<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define REP(i,m,n) for(int i=(int)(m); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define RREP(i,m,n) for(int i=(int)(m); i>=(int)(n); i--)
#define rrep(i,n) RREP(i,n-1,0)
#define all(v) v.begin(), v.end()
const int inf = 1e9+7;
const ll longinf = 1LL<<60;
const ll mod = 1e9+7;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int H, W, K;
  cin >> H >> W >> K;
  vector<string> A(H);
  rep(i, H) cin >> A[i];
  int s = -1;
  rep(i, H) rep(j, W) if(A[i][j] == 'S') s = i*W+j;
  int dx[] = {0, -1, 0, 1};
  int dy[] = {-1, 0, 1, 0};
  vector<int> dist(H*W);
  vector<int> S;
  auto bfs = [&]() {
    queue<int> q;
    q.push(s);
    vector<int> vis(H*W);
    while(!q.empty()) {
      int cur = q.front();
      q.pop();
      if(vis[cur]) continue;
      S.push_back(cur);
      vis[cur] = true;
      int x = cur/W;
      int y = cur%W;
      rep(k, 4) {
        int nx = x+dx[k];
        int ny = y+dy[k];
        int ne = nx*W+ny;
        if(nx < 0 || nx >= H || ny < 0 || ny >= W) continue;
        if(vis[ne]) continue;
        if(A[nx][ny] == '#') continue;
        if(dist[cur]+1 > K) continue;
        dist[ne] = dist[cur]+1;
        q.push(ne);
      }
    }
  };
  bfs();
  int ans = inf;
  for(int s: S) {
    int x = s/W;
    int y = s%W;
    ans = min((min({x, y, H-1-x, W-1-y})+K-1)/K, ans);
  }
  cout << ans+1 << endl;
  return 0;
}


Measured memory_bytes: 13040
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>

using namespace std;

int main(void) {
    string S, T;
    cin >> S >> T;
    int N = S.size();
    int M = T.size();

    vector<int> s(N+1), t(M+1);
    for(int i=0; i<N; i++) {
        if(S[i] == 'A') {
            s[i+1] = 1;
        } else {
            s[i+1] = 2;
        }
    }
    for(int i=0; i<M; i++) {
        if(T[i] == 'A') {
            t[i+1] = 1;
        } else {
            t[i+1] = 2;
        }
    }

    partial_sum(s.begin(), s.end(), s.begin());
    partial_sum(t.begin(), t.end(), t.begin());

    int q;
    cin >> q;
    while(q--) {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        if((s[b] - s[a-1])%3 == (t[d] - t[c-1])%3) {
            cout << "YES" << endl;
        } else {
            cout << "NO" << endl;
        }
    }
    return 0;
}


Measured memory_bytes: 1664
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int main() {
    LL n;
    cin>>n;
    vector<pair<LL, int> > dvs;//配对<质数, 幂次>
    //质因数分解
    for (LL i=2; i*i<=n; i++) {
        if (0==n%i) {
            dvs.push_back(make_pair(i, 0));
            while (0==n%i) {
                dvs.back().second++;
                n /= i;
            }
        }
    }
    if (n>1) {
        dvs.push_back(make_pair(n, 1));
    }
    //遍历
    int ans = 0;
    for (pair<LL, int> &p:dvs) {
        int i=sqrt(p.second*2);
        if (i*(i+1)>p.second*2) {
            i--;
        }
        ans += i;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3612
#include<cmath>
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<map>
#include<queue>
#include<set>
#include<vector>
#include<bitset>
#define int unsigned long long
#define hh putchar('\n')
#define kg putchar(' ')
#define lowbit(x) ((x)&(-x))
using namespace std;
const int maxn=3005,mod=998244353;
int jia[maxn],cheng[maxn],a,b,n;
inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
		if(ch=='-')
			f=-1;
		ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
    }
    return x*f;
}
inline void write(int a)
{
    if(a<0)
    {
		putchar('-');
		putchar('1');
//		write(-a);
    }
    else
    {
		if(a>=10)
			write(a/10);
		putchar(a%10+'0');
    }
}
int quickmi(int a,int b)
{
	int kotae=1;
	while(b)
	{
		if(b&1)
			kotae=kotae*a%mod;
		a=a*a%mod;
		b>>=1;
	}
	return kotae;
}
signed main()
{
	int a=read()%10;
	if(a==2||a==4||a==5||a==7||a==9)
		puts("hon");
	else if(a==3)
		puts("bon");
	else
		puts("pon");
    return 0;
}





Measured memory_bytes: 3596
#include <bits/stdc++.h>
using ll = long long;
using namespace std;
#define rep(i,n) for(int i=0, i##_len=(int)(n); i<i##_len; i++)
#define reps(i,n) for(int i=1 , i##_len=(int)(n);i<=i##_len;i++)
#define rrep(i,n) for(int i=((int)(n)-1);i>=0;i--)
#define rreps(i,n) for(int i=((int)(n));i>0;i--)
#define repi(i,x) for(auto i=(x).begin(),i##_fin=(x).end();i!=i##_fin;i++)
#define all(x) (x).begin(), (x).end()
#define F first
#define S second
#define mp make_pair
#define pb push_back
#define solve(a) ((a)?"Yes":"No")
typedef vector<int> Vi;
typedef vector<Vi> VVi;
typedef pair<int , int> Pi;
typedef vector<Pi> VPi;
typedef vector<long long> V;
typedef vector<V> VV;
typedef pair<long long , long long> P;
typedef vector<P> VP;
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;}
const long long INFLL = 1LL<<60;
const int INF = 1<<30;
const double PI=acos(-1);
int main(){
	int n;
	bool  ans=true;
	cin >>n;
	Vi h(n);
	rep(i,n){
		cin>>h[i];
	}
	rep(i,n){
		if(i==0){
			h[i]--;
		}else if(h[i-1] >h[i]){
			ans=false;
		}else if(h[i-1]< h[i]){
			h[i]--;
		}
	}
	cout<<solve(ans)<<endl;
}

Measured memory_bytes: 3776
n=int(input())
arr=list(map(int,input().split()))
flag=False
for i in range(1,n):
  if arr[i]<arr[i-1]:
    break
else:
  flag=True
for i in range(n):
  for j in range(i+1,n):
    tmp=arr[:]
    tmp[i],tmp[j]=tmp[j],tmp[i]
    for k in range(1,n):
      if tmp[k]<tmp[k-1]:
        break
    else:
      flag=True
if flag==True:
  print('YES')
else:
  print('NO')

Measured memory_bytes: 3064