akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <string>
using namespace std;

int main(){
	int alph[26] = {};
	string inp, inpline;
	do{
		getline(cin, inpline);
		inp += inpline;
	}while(inpline != "\0");
	cout << inpline;
	for (unsigned int i = 0; i < inp.length(); i++){
		if (inp[i] >= 'a' && inp[i] <= 'z'){
			alph[inp[i] - 'a']++;
		}
		if (inp[i] >= 'A' && inp[i] <= 'Z'){
			alph[inp[i] - 'A']++;
		}
	}
	for (int i = 0; i < 26; i++){
		cout << (char)('a' + i) << " : " << alph[i] << endl;
	}
}

Measured memory_bytes: 3176
#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
#include <string>
#include <bitset>
#include <utility>
#include <numeric>
#include <queue>
#include <stack>

using ll = long long;
using namespace std;

constexpr int MOD = 1e9 + 7;
constexpr ll MOD_LL = ll(1e9) + 7;

int main(void) {
	int n, k;
	cin >> n >> k;
	
	int ans = 0;
	while( n ) {
		n /= k;
		ans++;
	}
	
	cout << ans << endl;
	
	return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<cmath>
using namespace std; 

typedef long long ll;
const ll INF =1LL<<60;

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

  int A[100000];
  for(int i=0;i<n;i++){
    cin>>A[i];
  }
  vector<ll>dp(n,INF);
  dp[0]=0;
  
  for(int i=1;i<n;i++){
    for(int j=1;j<=2;j++){
      dp[i]=min(dp[i],dp[i-j]+abs(A[i]-A[i-j]));
    }
  }
  cout<<dp.back()<<endl;
}


Measured memory_bytes: 1408
#pragma comment(linker, "/STACK:128777216")
#define _USE_MATH_DEFINES
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <stdio.h>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <bitset>
#include <stack>
#include <deque>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <algorithm>
#include <math.h>
#include <cmath>
#include <climits>
#include <ctime>
#include <random>
using namespace std;

#define forx(_name,_from, to, value) for (int name = from; name < to; name += value)
#define rforx(_name, from, to, value) for (int name = from; name > to; name -= _value)
#define all(_STL_NAME) _STL_NAME.begin(), _STL_NAME.end()
#define rall(_STL_NAME) _STL_NAME.rbegin(), _STL_NAME.rend()
#define mp(_FIRST,_SECOND) make_pair(_FIRST,_SECOND)

typedef long long ll;
typedef unsigned long long llu;
typedef long double ld;
const ld eps = 1e-12;
mt19937 rndm;

void start() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cout.precision(20); cout.setf(ios::fixed);
	string FILENAME = "navalny";
	rndm.seed(time(0));
#ifdef _DEBUG
	freopen("input.txt", "rt", stdin);
	freopen("output.txt", "wt", stdout);
#else
	//freopen((FILENAME + ".in").c_str(), "rt", stdin);
	//freopen((FILENAME + ".out").c_str(), "wt", stdout);
#endif
}

int main() {
	start();
	int n;
	cin >> n;
	vector<ll> v;
	for (int i = 0; i < n; ++i) {
		int q;
		cin >> q;
		v.emplace_back(q);
	}
	ll val = v[0] + v[1];
	for (int i = 2; i < n; ++i)
		if (i % 2)
			val += v[i];
		else
			val -= v[i];
	vector<ll> ans(n);
	ans[1] = val;
	ans[0] = 2 * v[0] - val;
	for (int i = n - 1; i > 1; --i) {
		ans[i] = 2 * v[i] - ans[(i + 1) % n];
	}
	for (int i = 0; i < n; ++i)
		cout << ans[i] << ' ';
#ifdef _DEBUG
	cout << "\nTime: " << 1.0 * clock() / CLOCKS_PER_SEC << endl;
#endif
	return 0;
}

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

int main(void) {
	string name;
	cin >> name;
	int L = name.size();
	string Ans;
	for (int i = 0; i < L; i++) {
		Ans += name.substr(L-i-1, 1);
	}
	cout << Ans << endl;
	return 0;
}

Measured memory_bytes: 1180
#include<iostream>
#include<string>
#include<algorithm>
#include <stdio.h>
#include<iostream>
#include<iomanip>
#include<cmath>
#include<array>
#include<vector>
#include<set>
#include <utility>
#include <map>
using namespace std;

int main(){
int a[5];
for(int i=0;i<5;i++)
cin >>a[i];
int k; cin >>k;

if(a[4]-a[0]>k) cout << ":("<<endl;
else cout << "Yay!"<<endl;
}


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

namespace ABC134
{
    class D
    {
        static void Main(string[] args)
        {
            int N = int.Parse(Console.ReadLine());
            int[] a = Console.ReadLine().Split().Select(int.Parse).ToArray();

            int[] b = new int[N + 1];
            for (int i = N; 0 < i; i--)
            {
                int count = 0;
                int j = 1;
                while (i * j <= N)
                {
                    count += b[i * j];
                    j++;
                }

                if (count % 2 != a[i - 1]) { b[i] = 1; }
                else { b[i] = 0; }
            }

            List<int> list = new List<int>();
            int index = 0;
            foreach (var item in b)
            {
                if (item == 1) { list.Add(index); }
                index++;
            }

            Console.WriteLine(list.Count());
            foreach (var item in list)
            {
                Console.Write(item);
                Console.Write(' ');
            }
            if (list.Count != 0) Console.WriteLine();
        }
    }
}


Measured memory_bytes: 31452
#include<stdio.h>

int main() {
	int result=0;
	char s[101];
	int i=0;
	while(scanf("%c", &s[i]),s[i]!='\n') {
		if(((i+1)%2!=0)&&(s[i]=='R'||s[i]=='U'||s[i]=='D')||((i+1)%2==0)&&(s[i]=='L'||s[i]=='U'||s[i]=='D')) {
		}else{
			result=1;
		}
		i++;
	}
	
	if(result==0){
		printf("Yes");
	}else{
		printf("No");
	}
	
	return 0;
}

Measured memory_bytes: 128
N, W = map(int, input().split())

dp = [[0 for _ in range(W)] for _ in range(N + 1)]
weight = []
value = []
for _ in range(N):
    w, v = map(int, input().split())
    weight.append(w)
    value.append(v)

dp = [[0 for i in range(W + 1)] for j in range(N + 1)]

for i in range(W + 1):
    dp[0][i] = 0

for i in range(N):
    for w in range(W + 1):
        if weight[i] <= w:
            dp[i + 1][w] = max(dp[i][w - weight[i]] + value[i], dp[i][w])
        else:
            dp[i + 1][w] = dp[i][w]

print(dp[N][W])


Measured memory_bytes: 259208
#include <iostream>
#include <string>
#include <vector>
#include <utility>
#include <set>
#include <map>
#include <unordered_map>

using namespace std;
const int maxn = 102;

int n, m, X, Y, x, y;

int main()
{
	cin >> n >> m >> X >> Y;

	int maxx = -101;

	for (int i = 1; i <= n; ++i) {
		cin >> x;
		if (x > maxx)
			maxx = x;
	}

	if (maxx >= Y) {
		cout << "War" << endl;
		return 0;
	}

	int miny = 101;
	for (int i = 1; i <= m; ++i) {
		cin >> y;
		if (y < miny)
			miny = y;
	}

	if (miny <= X || maxx >= miny)
		cout << "War" << endl;
	else 
		cout << "No War" << endl;
	

	return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<string.h>

#define M 20000000 /* your task*/
#define L 14

char H[M][L]; /* Hash Table */

int getChar(char ch){
  if ( ch == 'A') return 1;
  else if ( ch == 'C') return 2;
  else if ( ch == 'G') return 3;
  else return 4;
}

/* convert a string into an integer value */
long long getKey(char str[]){
  long long sum = 0, p = 1, i;
  for ( i = 0; i < strlen(str); i++ ){
    sum += p*(getChar(str[i]));
    p *= 5;
  }
  return sum;
}

int find(char str[]){
if(H[getKey(str)][0] == 0) return 0;
else return 1;
}

void insert(char str[]){
  int key;
  key=getKey(str);
strcpy(H[key], str);
}

int main(){
    int i, n, h;
    char str[L], com[9];

    scanf("%d", &n);

    for ( i = 0; i < n; i++ ){
	      scanf("%s %s", com, str);

        if (com[0] == 'i' ){
	         insert(str);
	      } else {
	         if (find(str)){
		          printf("yes\n");
	            } else {
		             printf("no\n");
	            }
	      }
    }

    return 0;
}

Measured memory_bytes: 118548
#include <iostream>
#include <string>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    string s, t;
    cin >> s >> t;
    for (int i = s.size() - t.size(); i >= 0; --i) {
        string ns = s;
        int f = 1;
        for (int j = 0; j < t.size(); ++j) {
            if (ns.at(i + j) == '?') ns.at(i + j) = t.at(j);
            f &= (ns.at(i + j) == t.at(j));
        }
        if (f) {
            for (auto i = ns.begin(); i != ns.end(); ++i) if (*i == '?') *i = 'a';
            printf("%s\n", ns.c_str());
            return 0;
        }
    }
    printf("UNRESTORABLE\n");
    return 0;
}


Measured memory_bytes: 256
<?php
while(true){
    list($n,$m) = explode(" ",trim(fgets(STDIN)));
    if($n == 0 && $m == 0) break;
    $p = array_fill(0,$n,0);
    $s = $m;
    $t = 0;
    while(true){
        if($s > 0){
            $p[$t]++;
            $s--;
        } elseif($s == 0){
            $s = $p[$t];
            $p[$t] = 0;
        }
        if($p[$t] == $m){
            echo $t."\n";
            break;
        }
        $t = ($t + 1) % $n;
    }
}

Measured memory_bytes: 15216
#if !defined(__clang__) && defined(__GNUC__)
#include <bits/stdc++.h>
#else
#include <cstdlib>
#include <climits>
#include <iostream>
#include <cstdint>
#include <vector>
#include <string>
#include <complex>
#include <bitset>
#include <queue>
#include <deque>
#include <stack>
#include <utility>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <regex>
#endif //  !defined(__clang__) && defined(__GNUG__)
#include <boost/lexical_cast.hpp>
#include <boost/algorithm/string.hpp>
#include <boost/multi_array.hpp>
#include <boost/optional.hpp>
#include <boost/math/common_factor_rt.hpp>

using namespace std;

int main()
{
    int64_t N;
    std::cin >> N;

    int64_t sum = 0;

    std::vector<int64_t> A;
    for (int64_t i = 0; i < N; ++i) {
        int64_t a;
        std::cin >> a;
        A.push_back(a);
    }


    int64_t count = 0;
    sum = 0;
    for (int64_t i = 0; i < N; ++i) {
        sum += A[i];
        if (i%2 == 0) {
            if (sum >= 0) {
                // -1までにする
                count += sum + 1;
                sum = -1;
            }
        }
        else {
            if (sum <= 0) {
                // 1までにする
                count += (-1 * sum) + 1;
                sum = 1;
            }
        }
    }

    int64_t count2 = 0;
    sum = 0;
    for (int64_t i = 0; i < N; ++i) {
        sum += A[i];
        if (i%2 == 1) {
            if (sum >= 0) {
                // -1までにする
                count2 += sum + 1;
                sum = -1;
            }
        }
        else {
            if (sum <= 0) {
                // 1までにする
                count2 += (-1 * sum) + 1;
                sum = 1;
            }
        }
    }

    std::cout << std::min(count, count2) << std::endl;

    return 0;
}


Measured memory_bytes: 1400
#include <bits/stdc++.h>
 
#define rep(i,n) for(ll i=0;i<n;++i)
#define all_map(itr,mp) for(auto itr=mp.begin();itr!=mp.end();itr++)
#define ALL(a) (a).begin(),(a).end()

using namespace std;
using ll  = long long;
using pll = pair<ll, ll>;

const ll MOD  = 1e9 + 7;
const ll LINF = 1LL << 62;
const int INF = 1e9 + 7;

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

    vector<ll> a(n);
    rep(i, n)cin >> a[i];

    sort(ALL(a));

    ll ans = 0;
    rep(i, k)ans += a[i];

    cout << ans << endl;
}

Measured memory_bytes: 3596
// https://ei1333.github.io/luzhiled/
// http://beet-aizu.hatenablog.com/entry/2017/01/04/113233
// http://www.prefield.com/algorithm/
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using vl = vector<ll>;
using vd = vector<ld>;
using vs = vector<string>;
using vb = vector<bool>;
using vvl = vector<vector<ll>>;
using vvd = vector<vector<ld>>;
using vvs = vector<vector<string>>;
using vvb = vector<vector<bool>>;
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
template<class T> using vc = vector<T>;
template<class T> using vvc = vector<vector<T>>;
using Graph = vector<vector<ll>>;
const ll INF = 1LL << 60;
void init() {cin.tie(0);ios::sync_with_stdio(false);cout << fixed << setprecision(15);}
#define tl 1'000'000'007
#define REP(i, n) for (ll i = 0; i < n; i++)
#define REREP(i, n) for (ll i = n; i >= 0; i--)
#define FOR(i, a, n) for (ll i = a; i < n; i++)
#define REFOR(i, n, a) for (ll i = n; i >= a; i--)
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() ) //被り削除
#define debug cout << "line : " << __LINE__ << " debug" << endl;
#define ini(...) int __VA_ARGS__; in(__VA_ARGS__)
#define inl(...) long long __VA_ARGS__; in(__VA_ARGS__)
#define ind(...) long double __VA_ARGS__; in(__VA_ARGS__)
#define ins(...) string __VA_ARGS__; in(__VA_ARGS__)
#define inc(...) char __VA_ARGS__; in(__VA_ARGS__)
void in(){} template <typename T,class... U> void in(T &t,U &...u){ cin >> t; in(u...);}
void out(){cout << endl;} template <typename T,class... U> void out(const T &t,const U &...u){ cout << t; if(sizeof...(u)) cout << " "; out(u...);}
template<typename T>void die(T x){out(x); exit(0);}
#define in1(A) REP(i,A.size()) in(A[i]);
#define in2(A,B) REP(i,A.size()) in(A[i],B[i]);
#define in3(s,t,u) REP(i,sz(s)){in(s[i] , t[i] , u[i]);}
#define in4(s,t,u,v) REP(i,sz(s)){in(s[i] , t[i] , u[i] , v[i]);}
#define each(x,v) for(auto& x : v)
#define all(v) (v).begin(),(v).end()
#define sz(v) ((int)(v).size())
struct Point{ ld x,y; };
ld dist(Point a, Point b){return sqrt(abs(a.x-b.x)*abs(a.x-b.x)+abs(a.y-b.y)*abs(a.y-b.y));} // ２点間の距離 
ll gcd(ll a, ll b) { return b != 0 ? gcd(b, a % b) : a; }
ll lcm(ll a,ll b){ return a / gcd(a,b) * b;} 
ll fact(ll n){ if(n < 2) return 1; return (n * fact(n-1))%tl; } //階乗
inline ll updiv(ll a,ll b){ return (a + b - 1) / b; } //切り上げ
template<typename T,typename U>ll ceil(T a,U b){return (a + b - 1) / b;}
template <class A, class B> inline bool chmax(A &a, const B &b) { return b > a && (a = b, true); }
template <class A, class B> inline bool chmin(A &a, const B &b) { return b < a && (a = b, true); }
//-------------------------------------------------------------------------------------------------
int main(){
    init();
    inl(s,l,r);

    out(s+l+r-max(s,max(l,r)));
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
#define int int64_t
#define mod 1000000007
#define t() int tst;cin>>tst;for(int test=1;test<=tst;++test)
#define rep(i,a,b) for(i=a;i<b;++i)
#define repr(i,a,b) for(i=a;i>=b;--i)
typedef pair<int,int> pii;
#define F first
#define S second
#define pb push_back
#define all(p) p.begin(), p.end()
#define MAX 10000005

int powG(int x,int y)
{

  if(y==1)return x;
  if(y==0)return 1;

  int temp=powG(x,y/2);

  temp*= temp;

  if(y&1)
    temp*=x;
  
    return temp;
}


int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    //t()
    {
        int x,y;
        cin>>x>>y;
        int flag = 0;
        if(y%2 == 0)
        {
            if(y/2 >= x && 2*x >= y/2)
            {
                flag = 1;
            }
        }
        flag ? cout << "Yes" : cout << "No";
    }
    return 0; 
} 





Measured memory_bytes: 3692
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while(true) {
            int h = sc.nextInt();
            int w = sc.nextInt();

            if(h == 0 && w == 0) {
                break;
            }

            for(int i=0; i<h; i++) {
                StringBuilder sb = new StringBuilder();
                for(int j=0; j<w; j++) {
                    if(i == 0 || i == h-1) {
                        sb.append("#");
                    } else if(j == 0 || j == w-1) {
                        sb.append("#");
                    } else if(j != 0 && j != w-1) {
                        sb.append(".");
                    }
                }
                System.out.println(sb);
            }
            System.out.println("");
        }
        sc.close();
    }
}



Measured memory_bytes: 28860
#include <iostream>

#include <iomanip>
using namespace std;
int main(){

   int a;
    cin>>a;
if(a==22){
  cout<<"Christmas Eve Eve Eve";
}

else if(a==23){
  cout<<"Christmas Eve Eve";
}
else if(a==24){
  cout<<"Christmas Eve";
}
else if(a==25){
  cout<<"Christmas";
}





    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define rep(i,x,y) for(int i=x;i<y;i++)
#define print(A,x,n) rep(i,0,n){cout<<(i ? " ":"")<<A[i]x;}cout<<endl;
#define pprint(A,y,m,n) rep(j,0,m){print(A[j],y,n);}
const long mod=1e9+7;
const int size=1e7;
const int inf=1e9;
int main(){
	int H,W,K;cin>>H>>W>>K;
	string s[H];
	int cnt[H+1][W+1] = {};
	rep(i,0,H){
		cin>>s[i];
		rep(j,0,W){
			cnt[i+1][j+1] = cnt[i][j+1] + cnt[i+1][j] - cnt[i][j] + (s[i][j] == '1');
		}
	}
	int ans = H+W-2;int res;
	rep(i,0,(1<<(H-1))){
		set<int> st;
		rep(j,0,H-1){
			if(i&(1<<j)) st.insert(j+1);
		}st.insert(H);
		res = st.size() - 1;
		int a = 0,b;
		rep(c,1,W+1){
			b = 0;
			bool flag = true;
			for(int d:st){
				if(cnt[d][c] - cnt[d][a] - cnt[b][c] + cnt[b][a] > K){
                    flag = false;
                    if(a + 1 == c) res=inf;
                }
				b = d;
			}
			if(!flag){ a = c - 1; res++; }
		}ans = min(ans , res);
	}cout<<ans<<endl;
}

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

string s;

int main() {
  cin >> s;
  cin >> s;
  
  int r = 0, b = 0;
  for (char c: s) {
    if (c == 'R') ++r;
    if (c == 'B') ++b;
  }
  
  if (r > b) printf("Yes\n");
  else printf("No\n");
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
using namespace std;
static const int MAX = 100;
static const int INFTY = (1<<21);
static const int WHITE = 0;
static const int GRAY = 1;
static const int BLACK = 2;

int n, M[MAX][MAX];

int prim() {
  int u, minv;
  int d[MAX], p[MAX], color[MAX];

  for (int i = 0; i < n; i++) {
    d[i] = INFTY;
    p[i] = -1;
    color[i] = WHITE;
  }

  d[0] = 0;

  while ( 1 ) {
    minv = INFTY;
    u = -1;
    for (int i = 0; i < n; i++) {
      if(minv > d[i] && color[i] != BLACK) {
        u = i;
        minv = d[i];
      }
    }
    if (u == -1) break;
    color[u] = BLACK;
    for (int v = 0; v < n; v++) {
      if (color[v] != BLACK && M[u][v] != INFTY) {
        if (d[v] > M[u][v]) {
          d[v] = M[u][v];
          p[v] = u;
          color[v] = GRAY;
        }
      }
    }
  }

  int sum = 0;
  for (int i = 0; i < n; i++) {
    if(p[i] != -1) sum += M[i][p[i]];
  }

  return sum;
}

int main() {
  cin >> n;

  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      int e; cin >> e;
      M[i][j] = (e == -1) ? INFTY : e;
    }
  }

  cout << prim() << endl;

  return 0;
}


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

using namespace std;

#define ll long long
#define ull unsigned long long

ll nC3(int n) {
    return (ll) n * (n - 1) * (n - 2) / 6;
}

ll nC2(int n) {
    return (ll) n * (n - 1) / 2;
}

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

    int n;
    string s;
    cin >> n >> s;
    map<char, int> cnt;
    for (char c : s) cnt[c]++;
    ll ans = nC3(n);
    ans -= nC3(cnt['R']) + nC3(cnt['G']) + nC3(cnt['B']);
    ans -= nC2(cnt['R']) * (cnt['B'] + cnt['G']) + nC2(cnt['B']) * (cnt['R'] + cnt['G']) + nC2(cnt['G']) * (cnt['B'] + cnt['R']);
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            int k = 2 * j - i;
            if (s[i] != s[j] && s[j] != s[k] && s[k] != s[i] && k < n) ans--;
        }
    }
    cout << ans << '\n';
}

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

#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds; 

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int getRand(int l, int r)
{
    uniform_int_distribution<int> uid(l, r);
    return uid(rng);
}
  
#define int long long 
#define pb push_back
#define S second
#define F first
#define f(i,n) for(int i=0;i<n;i++)
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define vi vector<int>
#define pii pair<int,int>
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> 
#define precise(x) fixed << setprecision(x) 

const int MOD = 1e9+7;

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


void solve()
{
   int n;
    cin >> n;
    
   int a[n];
   int b[n];
   f(i,n) cin >> a[i] >> b[i];
   
   f(i,n) a[i]*=2,b[i]*=2;
   
   sort(a,a+n);
   sort(b,b+n);
    
   int m1 = 0;
   int m2 = 0;
    
   if(n%2 == 1)
   {
       m1 = a[n/2];
       m2 = b[n/2];
   }
   else
   {
       m1 = a[n/2] + a[(n/2) - 1];
       m1/=2;
       
       m2 = b[n/2] + b[(n/2) - 1];
       m2/=2;
   }
    
   int rr = m2 - m1 + 1;
      
   if(n%2 == 1) 
   {
       rr/=2;
       rr++;
   }
    
    
   cout << rr;
    
}

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

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

int main(){
  int N,A;
  cin >> N >> A;
  if(N % 500 == 0){
  cout << "Yes" << endl;
  }
  else if((N % 500 != 0) && (N % 500<= A)){
  cout << "Yes" << endl;
  }
  else{
   cout << "No" << endl; 
  }
  
}

Measured memory_bytes: 256
x = int(input())
if 400 <= x <= 599:
    print(8)
elif 600 <= x <= 799:
    print(7)
elif 800 <= x <= 999:
    print(6)
elif 1000 <= x <= 1199:
    print(5)
elif 1200 <= x <= 1399:
    print(4)
elif 1400 <= x <= 1599:
    print(3)
elif 1600 <= x <= 1799:
    print(2)
elif 1800 <= x <= 1999:
    print(1)

Measured memory_bytes: 61640
#include <iostream>
#include <iomanip>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <algorithm>
#include <sstream>
#include <cstdlib>
#include <cstring>
#include <functional>
#include <numeric>
#include <cmath>
#include <climits>
#include <limits>
#include <cfloat>
#include <fstream>
using namespace std;

int main()
{
//	cut here before submit 
//	freopen("testcase.diff", "r", stdin);
	string str = "";
	vector <double> high;

	while (getline (cin, str ) ){
		if (str.empty() ){
			break;
		} // end if
		stringstream ss(str);
		double h;
		ss >> h;
		high.push_back(h);
	} // end while
	
	sort (high.begin(), high.end() );

	double res = high[high.size() - 1] - high[0];

	cout << res << endl;	
		
	return 0;
}

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

using namespace std;
using ll = long long;

#define INF (1LL << 60)

#define REP(i,m,n) for(ll (i)=(m),i##_len=(n);(i)<(i##_len);++(i))
#define FORR(i,v) for(auto (i):v)
#define ALL(x) (x).begin(), (x).end()
#define _PR(x) cout << (x) << endl
#define _PS(x) cout << (x) << " "
#define SZ(x) ((int)(x).size())
#define MAX(a,b) (((a)>(b))?(a):(b))
#define MIN(a,b) (((a)<(b))?(a):(b))
#define pb push_back

int main()
{
    ll L, R;
    cin >> L >> R;

    ll m = INF;
    if((R - L) >= 2019) _PS(0);
    else {
        REP(i,L%2019,L%2019+(R-L)%2019) {
            REP(j,i+1,L%2019+(R-L)%2019+1) {
                m = MIN((i*j)%2019,m);
            }
        }
        _PS(m);
    }

    return 0;
}

/*



*/

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define Set(a,b) memset(a,b,sizeof(a))
using namespace std;
const int N=2e5+10;
const int mod=1e9+7;
template <typename T> inline void init(T&x){
	x=0;char ch=getchar();bool t=0;
	for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') t=1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<1)+(x<<3)+(ch-48);
	if(t) x=-x;return;
}
typedef long long ll;
typedef unsigned long long ull;
template <typename T>inline void Inc(T&x,int y){x+=y;if(x>=mod) x-=mod;return;}
template <typename T>inline void Dec(T&x,int y){x-=y;if(x <  0) x+=mod;return;}
template <typename T>inline int fpow(int x,T k){int ret=1;for(;k;k>>=1,x=(ll)x*x%mod) if(k&1) ret=(ll)ret*x%mod;return ret;}
int Sum(int x,int y){x+=y;if(x>=mod) return x-mod;return x;}
int Dif(int x,int y){x-=y;if(x < 0 ) return x+mod;return x;}
int dp[N];
int C[N];
int n;int lst[N];
int main()
{
	init(n);dp[1]=1;
	for(int i=1;i<=n;++i) init(C[i]);
	lst[C[1]]=1;
	for(int i=2;i<=n;++i) {
		if(C[i-1]==C[i]) dp[i]=dp[i-1];
		else dp[i]=Sum(dp[i-1],dp[lst[C[i]]]);
		lst[C[i]]=i;
	}
	cout<<dp[n]<<endl;
	return 0;
}


Measured memory_bytes: 2560
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n - 1; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i <= n; i++)
#define FORR(i, m, n) for(int i = m; i >= n; i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
 
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
using P = pair<ll, ll>;

int main(){
    ll n;
    cin >> n;
    vll a(n + 2);
    a[0] = 0, a[n + 1] = 0;
    REP(i, n) cin >> a[i + 1];
    vll vec(n + 1, 0);
    ll sum = 0;
    REP(i, n + 1){
        sum += abs(a[i + 1] - a[i]);
        if(a[i + 1] >= a[i]) vec[i] = 1;
        else vec[i] = -1;
    }
    ll res;
    REP(i, n){
        res = 0;
        if(vec[i] * vec[i + 1] < 0){
            if(min(a[i], a[i + 1]) <= a[i + 2] && a[i + 2] <= max(a[i], a[i + 1])) res = 2 * abs(a[i + 2] - a[i + 1]);
            else res = 2 * abs(a[i + 1] - a[i]);
        }
        cout << sum - res << endl;
    }
    return 0;
}

Measured memory_bytes: 2816
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <string>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define REP(i, n) for (int i = 0; i < (n); i++)
#define RREP(i, n) for (int i = (n) - 1; i >= 0; i--)
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define RFOR(i, a, b) for (int i = (a); i > (b); i--)
#define ALL(a) (a).begin(), (a).end()

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

Measured memory_bytes: 3632
/* include */
#include <stdio.h>

/* define */
#define MAX 100
#define WHITE 0
#define GRAY 1
#define BLACK 2

/* prototype define */
void dfs();
void visit(int);

/* global */
int n, MATRIX[MAX][MAX], COLOR[MAX], GO[MAX], BACK[MAX], stamp;

int main(){
  int from, to, deg, i, j;

  /* input size */
  scanf("%d", &n);

  /* initialize */
  for(i=0;i<n;i++){
    for(j=0;j<n;j++){
      MATRIX[i][j] =0;
    }
  }
  
  /* create matrix */
  for(i=0;i<n;i++){
    scanf("%d %d", &from, &deg);
    from--;
    for(j=0;j<deg;j++){
      scanf("%d", &to);
      to--;
      MATRIX[from][to] = 1;
    }
  }
  dfs();
  return 0;
}

void dfs() {
  int from;
  
  /* initialize */
  for(from=0;from<n;from++){
    COLOR[from] = WHITE;
  }
  stamp = 0;
  
  /* ??¢?´¢ */
  for(from=0;from<n;from++){
    if(COLOR[from]==WHITE){
      visit(from);
    }
  }
  
  /* print */
  for(from=0;from<n;from++){
    printf("%d %d %d\n", from+1, GO[from], BACK[from]); //from+1: 0????????????????????????
  }
}

void visit(int from){
  int to;
  COLOR[from] = GRAY;
  GO[from] = ++stamp; //??????????¨????
  for(to=0;to<n;to++){
    if(MATRIX[from][to] == 0){ //????????????(?????????)
      continue;
    }
    if(COLOR[to] == WHITE) {
      visit(to); //?????°
    }
  }
  COLOR[from] = BLACK; //?????£???
  BACK[from] = ++stamp; //?¨?????????????
}

Measured memory_bytes: 636
while true
  h,w = gets.split.map(&:to_i)
  if h == 0 && w == 0 then break end
  t = w-2
  h.times do |i|
    if i == 0 || i == h-1
      puts "#"*w
    else
      puts "#"+ "."*t + "#"
    end
  end
    puts "\n"
end


Measured memory_bytes: 6964
process.stdin.resume();
process.stdin.setEncoding('utf8');
// 自分の得意な言語で
// Let's チャレンジ！！

var lines = [];
var reader = require('readline').createInterface({
  input: process.stdin,
  output: process.stdout
});
reader.on('line', (line) => {
  lines.push(line);
});
reader.on('close', () => {
  const N = parseInt(lines[0]); lines.shift();  // N: 取引の数
  const R = lines; // R: 時系列に並んだ価格
  
  var minv = parseInt(R[0]);  // 最小値
  var maxv = parseInt(R[1]) - parseInt(R[0]);  // 最大利益
  for(var i = 1; i <= N - 1; i++) {
    var v = parseInt(R[i]);
    if (v - minv > maxv) maxv = v - minv;
    if (minv > v) minv = v;
  }
  console.log(maxv);
});


Measured memory_bytes: 36140
#include<cstdio>
#include<string>
#include<cstring>
#include<utility>
#include<cmath>
#include<map>
#include<queue>
#include<set>
#include<algorithm>
#include<vector>
#include<iostream>
#define ll long long
#define pii pair<int,int>
#define mp make_pair
#define fi first
#define se second
#define inf 0x7fffffff
using namespace std;
int main()
{
	int i,j,k,n,m,x,y,z,la=0,lx=0,ly=0,dt,dx,dy;
	scanf("%d",&n);
	for(i=0;i<n;i++)
	{
		scanf("%d%d%d",&z,&x,&y);
		dt=z-la;
		dx=abs(lx-x);
		dy=abs(ly-y);
		if(dt%2!=(dx+dy)%2||dx+dy>dt)
		{
			printf("No");
			return 0;
		}
	}
	printf("Yes");
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 10;

int dp[MAXN], h[MAXN];
int n, k;

int solve(int i)
{
	if(dp[i] != -1) return dp[i];

	if(i == n) return 0;

	int best = 1e9;

	for(int j = 1; j + i <= n and j <= k; j++)
	{
		best = min(best, solve(i + j) + abs(h[i] - h[i + j]));
	}

	return dp[i] = best;
}

int main()
{
	cin >> n >> k;
	for(int i = 1; i <= n; i++)
	{
		cin >> h[i];
	}

	memset(dp, -1, sizeof(dp));

	cout << solve(1) << "\n";
}

Measured memory_bytes: 5760
#include<bits/stdc++.h>
using namespace std;
long long x,b,c,d=1;
int G(long long a)
{
	if(a%b==c)
		return 1;
	if(d==100000)
		return 0;
	d++;
	G(x*d);
}
int main()
{
	cin>>x>>b>>c;
	if(G(x))cout<<"YES";else cout<<"NO";
	cout<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
template<class T> void ckmin(T &a, T b) { a = min(a, b); }
template<class T> void ckmax(T &a, T b) { a = max(a, b); }
#define pb push_back
#define mp make_pair
#define Red ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define F first
#define S second
#define sz(x) (int)x.size()
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for(int i = 0; i < n; ++i)
#define repr(i,n) for(int i = n - 1; i >= 0; --i)
#define Rep(i, a, n) for(int i = (a); i <=(n); ++i)
#define repst(i, n) for(auto it = n.begin(); it != n.end(); ++it)
#define Repr(i, a, n) for(int i = (n); i >= (a); --i)
typedef long long ll;
 
const int inf = int(1e9);
const int mod = 1e9 + 7;
const int N = 1e6 + 555;
const long double PI = acos(-1.0);
void solve()
{	
	int a;
	string s;
	cin >> a >> s;
	if(a >= 3200) cout << s;
	else cout << "red";
}
int main()
{
	Red;
	solve();
	return 0;
}

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

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

	long long int reduced = n % k;
	long long int ans = reduced;

	while (true)
	{
		reduced = abs(reduced - k);
		if (reduced > ans)
			break;
		else
			ans = reduced;
	}
	cout << ans << endl;

	//wait it's C so no brute force oops
	/*long long int n, k;
	cin >> n >> k;

	long long int lowest = 1000000000000000001;
	while (true)
	{
		n = abs(n - k);
		if (lowest < n)
		{
			break;
		}
		else
		{
			lowest = n;
		}
	}

	cout << lowest << endl;*/
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> l_l;
typedef pair<int, int> i_i;
template<class T>
inline bool chmax(T &a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}

template<class T>
inline bool chmin(T &a, T b) {
    if(a > b) {
        a = b;
        return true;
    }
    return false;
}

const long double EPS = 1e-10;
const long long INF = 1e18;
const long double PI = acos(-1.0L);
const ll mod = 1000000007;

ll inv[10000100];
ll FactorialInv[10000100];
ll Factorial[10000100];
ll beki(ll a, ll b){
    if(b == 0){
        return 1;
    }
    ll ans = beki(a, b / 2);
    ans = ans * ans % mod;
    if(b % 2 == 1){
        ans = ans * a % mod;
    }
    return ans;
}
void init_combination(){
    const int MAX = 10000002;
    Factorial[0] = 1;
    inv[0] = 1;
    for(int i = 1; i <= MAX; i++){
        Factorial[i] = Factorial[i - 1] * i % mod;
    }
    FactorialInv[MAX] = beki(Factorial[MAX], mod - 2);
    for(ll i = MAX - 1; i >= 0; i--) {
        FactorialInv[i] = FactorialInv[i+1] * (i+1) % mod;
    }
    for(int i = 1; i <= MAX; i++) {
        inv[i] = FactorialInv[i] * Factorial[i-1] % mod;
    }
}
ll combination(ll a, ll b){
    if((a == b) || (b == 0)){
        return 1;
    }
    if(a < b) return 0;
    ll ans = Factorial[a] * FactorialInv[b] % mod;
    ans = ans * FactorialInv[a - b] % mod;
    return ans;
}
ll N;
ll x[105000];
ll ans;
int main() {
    //cout.precision(10);
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> N;
    for(int i = 0; i < N; i++) cin >> x[i];
    ll factor = 0;
    for(int i = 1; i < N; i++) {
        factor += beki(i, mod - 2);
        factor %= mod;
        ans += factor * (x[i] - x[i-1]);
        //cerr << i << " " << factor << " " << x[i] - x[i-1] << endl;
        ans %= mod;
    }
    for(int i = 1; i <= N - 1; i++) {
        ans = ans * i % mod;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define Max(xx,yy) (xx > yy ? xx : yy);
#define Min(xx,yy) (xx < yy ? xx : yy);

using namespace std;
 
bool isDebug;
 
template<typename... T>
void dbg(T... args){
	if(!isDebug)
		return;
	
	#ifdef LOCAL
		((cout << args << " "),...) << "\n";
	#endif
}
               
long long n;
    
int main(int argc, char* argv[]){
	ios_base :: sync_with_stdio(false);
	cout.tie(NULL), cin.tie(NULL);
	isDebug = (argc > 1 && string(argv[1]) == "debug");
	                        
	cin >> n;
	
	long long inc = 1;
	long long val = 100;
	
	for(int i = 1;i <= 4000;i++){
		if(val >= n) {
		 	cout << i-1;
			return 0;
		}
		val += (val / 100);		
	}             	
}


Measured memory_bytes: 3636
#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>
#include <iterator>
#include <numeric>
#include <bitset>
#include <cassert>
#include <functional>

using namespace std;
typedef long long int ll;

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << (x) << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)

int main() {
	int N;
	cin >> N;
	vector<ll> H(N);
	rep(i, N) cin >> H[i];
	int cnt = 0, mx = 0;
	rep(i, N - 1) {
		if (H[i] >= H[i + 1]) {
			cnt++;
			if (i + 1 == N - 1) {
				chmax(mx, cnt);
			}
		}
		else {
			chmax(mx, cnt);
			cnt = 0;
		}
	}
	cout << mx << endl;

	return 0;
}

Measured memory_bytes: 1024
import java.util.Scanner;

/**
 * 解説通りに作成したソースコード
 */
public class Main {

	public static void main(String[] args) {
		try (Scanner scanner = new Scanner(System.in)) {
			long x = scanner.nextLong(), y = scanner.nextLong();
			System.out.println((Math.abs(x - y) <= 1) ? "Brown" : "Alice");
		}
	}
}


Measured memory_bytes: 35696
#define _USE_MATH_DEFINES

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <string>
#include <utility>
#include <climits>
#include <vector>
#include <map>
#include <queue>
using namespace std;

#define ll long long
const int MOD = 1000000007;//10^9+7
const string SPACE = " ";

ll max(ll a, ll b) {

	if (a > b)return a;
	else return b;

}
double max(double a, double b) {

	if (a > b)return a;
	else return b;

}
//a??¨b?????§?????????

ll min(ll a, ll b) {

	if (a < b)return a;
	else return b;

}
//a??¨b????°??????????

ll avd_i(ll a, ll b) {

	if (a > b)return a - b;
	else return b - a;

}
double avd_d(double a, double b) {

	double re;
	if (a > b)re = a - b;
	else re = b - a;
	return re;

}
//a??¨b???????????¶??????

ll powsur(ll a, ll b, ll p) {

	if (b == 0) {

		return 1;

	}
	else if (b % 2 == 0) {

		ll d = powsur(a, b / 2, p);
		return ((d%p)*(d%p)) % p;

	}
	else {

		return ((a%p)*powsur(a, b - 1, p) % p) % p;

	}

}
//p????´???°,a???b??????p??§?????£?????????

ll CMOD(ll n, ll r, ll p) {

	ll a = 1, b = 1, c = 1, re;
	for (int i = 1; i <= n; i++) {

		a *= i;
		a = a%p;

	}
	for (int i = 1; i <= r; i++) {

		b *= i;
		b = b%p;

	}
	for (int i = 1; i <= n - r; i++) {

		c *= i;
		c = c%p;

	}
	b = powsur(b, p - 2, p);
	c = powsur(c, p - 2, p);
	re = ((a%p)*(b%p)) % p;
	re = ((re%p)*c%p) % p;

	return re;

}
//p????´???°,(nCr)%p

ll gcd(ll a, ll b) {

	if (a > b) {

		ll tmp = a;
		a = b;
		b = tmp;

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

}
//?????§??¬?´???°

ll lcm(ll a, ll b) {

	return (a / gcd(a, b))*b;

}
//????°???¬?????°

int main() {
	
	int n, m, a[105][105], b[105], ans[105];

	cin >> n >> m;
	for (int i = 1; i <= n; i++) {

		for (int j = 1; j <= m; j++) {

			cin >> a[i][j];

		}

	}
	for (int i = 1; i <= m; i++) {

		cin >> b[i];

	}

	for (int i = 1; i <= n; i++) {

		ans[i] = 0;
		for (int j = 1; j <= m; j++) {

			ans[i] += a[i][j] * b[j];

		}
		cout << ans[i] << endl;

	}

	return 0;
}

Measured memory_bytes: 3168
#include <iostream>
#include <cmath>
#include <vector>

using namespace std;

int main() {
    int n, k; 
    cin >> n >> k;
    vector<int> vec(n);
    for (int i = 0; i < n; i++) {
        cin >> vec.at(i);
    }
    sort(vec.begin(), vec.end());
    bool success = true;
    int min = 0; 
    int max = vec[n-1];
    while(max != min) {
        int k_sum = 0;
        success = true;
        int target = (min+max)/2;
        if(target == 0) {
            cout << '1' << '\n'; return 0;
        }
        for(int i=0; i<n; i++) {
            k_sum += vec[i] / target;
            if(vec[i] % target == 0) k_sum -= 1;
            if(k_sum > k) {
                success = false;
                break;
            }
        }
        if(max-min == 1) {
            if(success) { cout << min << '\n'; } else { cout << max << '\n'; }
            return 0;
        }
        if(success) { max = target; } else { min = target; }
    }
    return 0;
}

Measured memory_bytes: 3696
n = int(input())
if 400<= n <=599:
  ans=8
elif 600<=n<=799:
  ans=7
elif 800<=n<=999:
  ans=6
elif 1000<=n<=1199:
  ans=5
elif 1200<=n<=1399:
  ans=4
elif 1400<=n<=1599:
  ans=3
elif 1600<=n<=1799:
  ans=2
elif 1800<=n<=1999:
  ans=1
print(ans)

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

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

using namespace std;
typedef long long ll;
typedef pair<int, int> pint;

const int INF = 1 << 30;
const ll LINF = 1LL << 60;
const int MOD = 1e9 + 7;

template<typename T>
struct LazySegmentTree {
private:
    int n;
    vector<T> node, lazy;
    
public:
    LazySegmentTree(vector<T> v) {
        int sz = (int)v.size();
        n = 1; while(n < sz) n *= 2;
        node.resize(2*n-1);
        lazy.assign(2*n-1, 0);
        
        for(int i=0; i<sz; i++) node[i+n-1] = v[i];
        for(int i=n-2; i>=0; i--) node[i] = node[i*2+1] + node[i*2+2];
    }   
    
    void eval(int k, int l, int r) {
        if(lazy[k] != 0) {
            node[k] += lazy[k];
            if(r-l > 1) {
                lazy[2*k+1] += lazy[k] / 2;
                lazy[2*k+2] += lazy[k] / 2;
            }   
            lazy[k] = 0;
        }   
    }   
    
    void add(int a, int b, T x, int k=0, int l=0, int r=-1) {
        if(r < 0) r = n;
        eval(k, l, r);
        if(b <= l || r <= a) return;
        if(a <= l && r <= b) {
            lazy[k] += (r - l) * x;
            eval(k, l, r);
        }   
        else {
            add(a, b, x, 2*k+1, l, (l+r)/2);
            add(a, b, x, 2*k+2, (l+r)/2, r);
            node[k] = node[2*k+1] + node[2*k+2];
        }   
    }   
    
    T getsum(int a, int b, int k=0, int l=0, int r=-1) {
        if(r < 0) r = n; 
        eval(k, l, r);
        if(b <= l || r <= a) return 0;
        if(a <= l && r <= b) return node[k];
        T vl = getsum(a, b, 2*k+1, l, (l+r)/2);
        T vr = getsum(a, b, 2*k+2, (l+r)/2, r);
        return vl + vr;
    }   
};

int main() {
    ll n, d, a; cin >> n >> d >> a;
    vector<pair<ll, ll>> temp(n);
    rep(i, n) cin >> temp[i].first >> temp[i].second;
    sort(temp.begin(), temp.end());
    vector<ll> x(n), h(n);
    rep(i, n) {
        x[i] = temp[i].first;
        h[i] = temp[i].second;
    }

    rep(i, n) {
        if (h[i] % a == 0) h[i] = h[i] / a;
        else h[i] = h[i] / a + 1LL;
    }

    vector<int> to(n);

    rep(i, n) {
        // x[i] + 2*d　を超える最大のx
        int idx = upper_bound(x.begin(), x.end(), x[i] + 2*d) - x.begin();
        --idx;
        to[i] = idx;
    }

    ll ans = 0;

    LazySegmentTree<ll> seg(h);
    rep(i, n) {
        ll num = seg.getsum(i, i+1);
        if (num > 0) {
            ans += num;
            seg.add(i, to[i]+1, -num);
        }
    }

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


    


Measured memory_bytes: 17024
//
//  main.cpp
//  atcoder-grid2
//
//  Created by r on 6/15/19.
//  Copyright © 2019 r. All rights reserved.
//

#include <iostream>
#include <algorithm>
#include <cstring>
#include <iomanip>
#include <fstream>
#include <cmath>
#include <vector>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <map>
#include <stack>
#include <queue>
#include <assert.h>
#include <limits>
#include <cstdio>
using namespace std;

//#define RDEBUG 1
#ifdef RDEBUG
#define D(x) x
#else
#define D(x)
#endif
#define inf 0x7fffffff
#define MOD 1000000007

typedef long long ll;


ll add(ll a, ll b) {
    a += b;
    if(a >= MOD) {
        a -= MOD;
    }
    return a;
}
ll sub(ll a, ll b) {
    a -= b;
    if(a < 0) {
        a += MOD;
    }
    return a;
}

ll mul(ll a, ll b) {
    return (a * b)%MOD;
}

void add_self(ll& a, ll b) {
    a = add(a, b);
}
void sub_self(ll& a, ll b) {
    a = sub(a, b);
}
void mul_self(ll& a, ll b) {
    a = mul(a, b);
}


const ll MAXN = 3010;

pair<ll, ll> rocks[MAXN];
ll factorial[200010], finv[200010];
ll H, W, N;

ll gcd(ll a, ll b, ll & x, ll & y) {
    if (a == 0) {
        x = 0;
        y = 1;
        return b;
    }
    ll x1, y1;
    ll d = gcd(b % a, a, x1, y1);
    x = y1 - (b / a) * x1;
    y = x1;
    return d;
}

ll inverse(ll a) {
    ll x, y;
    gcd(a, MOD, x, y);
    x = (x % MOD + MOD) % MOD;
    return x;
}

ll binomial_coefficient(ll n, ll k) {
    return factorial[n] * finv[k] % MOD * finv[n-k] % MOD;
}

ll rways(ll i, ll j) {
    return binomial_coefficient(i+j, i);
}
 
bool cmp(pair<ll, ll> a, pair<ll, ll> b) {return a.first+a.second<b.first+b.second;}

ll dp[3010];

int main() {
    ios_base :: sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> H >> W >> N;
    for (ll i = 0; i<N; i++) {
        cin >> rocks[i].first >> rocks[i].second;
        rocks[i].first--;
        rocks[i].second--;
    }
    factorial[0] = 1;
    finv[0] = inverse(factorial[0]);
    for (ll i = 1; i < 200010; i++) {
        factorial[i] = factorial[i - 1] * i % MOD;
        finv[i] = inverse(factorial[i]) % MOD;
    }
    rocks[N] = make_pair(H-1, W-1);
    sort(rocks, rocks+N+1, cmp);
    for (int i = 0; i<=N; i++) {
        ll tmp = rways(rocks[i].first, rocks[i].second);
        for (int j = 0; j<i; j++) {
            if (rocks[j].first<=rocks[i].first && rocks[j].second<=rocks[i].second) {
                sub_self(tmp, mul(rways(rocks[i].first-rocks[j].first, rocks[i].second-rocks[j].second), dp[j]));
            }
        }
        dp[i] = tmp;
    }
    cout << dp[N] << endl;
    return 0;
}





Measured memory_bytes: 3456
# include "bits/stdc++.h"
using namespace std;
using LL = long long;
using ULL = unsigned long long;
const double PI = acos(-1);
template<class T>constexpr T INF() { return ::std::numeric_limits<T>::max(); }
template<class T>constexpr T HINF() { return INF<T>() / 2; }
template <typename T_char>T_char TL(T_char cX) { return tolower(cX); };
template <typename T_char>T_char TU(T_char cX) { return toupper(cX); };
const int vy[] = { -1, -1, -1, 0, 1, 1, 1, 0 }, vx[] = { -1, 0, 1, 1, 1, 0, -1, -1 };
const int dx[4] = { 0,1,0,-1 }, dy[4] = { 1,0,-1,0 };
int popcnt(unsigned long long n) { int cnt = 0; for (int i = 0; i < 64; i++)if ((n >> i) & 1)cnt++; return cnt; }
int d_sum(LL n) { int ret = 0; while (n > 0) { ret += n % 10; n /= 10; }return ret; }
int d_cnt(LL n) { int ret = 0; while (n > 0) { ret++; n /= 10; }return ret; }
LL gcd(LL a, LL b) { if (b == 0)return a; return gcd(b, a%b); };
LL lcm(LL a, LL b) { LL g = gcd(a, b); return a / g*b; };
# define ALL(qpqpq)           (qpqpq).begin(),(qpqpq).end()
# define UNIQUE(wpwpw)        sort(ALL((wpwpw)));(wpwpw).erase(unique(ALL((wpwpw))),(wpwpw).end())
# define LOWER(epepe)         transform(ALL((epepe)),(epepe).begin(),TL<char>)
# define UPPER(rprpr)         transform(ALL((rprpr)),(rprpr).begin(),TU<char>)
# define FOR(i,tptpt,ypypy)   for(LL i=(tptpt);i<(ypypy);i++)
# define REP(i,upupu)         FOR(i,0,upupu)

struct INIT{
    INIT(){
        std::ios::sync_with_stdio(false);
        std::cin.tie(0);
        cout << fixed << setprecision(13);
    }
}INIT;


int main(){
    int n;
    cin >> n;
    vector<LL> w(n), s(n), v(n), order(n);
    REP(i, n)cin >> w[i] >> s[i] >> v[i];
    int maxl = (*max_element(ALL(s)) + *max_element(ALL(w))) + 1;
    REP(i, n)order[i] = i;
    sort(ALL(order), [&](int a, int b){return w[a] + s[a] < w[b] + s[b];});
    vector<vector<LL>> dp(n + 1, vector<LL>(maxl, 0));
    REP(i, n){
        int cur = order[i];
        REP(j, maxl)dp[i + 1][j] = dp[i][j];
        for(int j = 0;j <= s[cur];j++){
            if(j + w[cur] < maxl)dp[i + 1][j + w[cur]] = max(dp[i + 1][j + w[cur]], dp[i][j] + v[cur]);
        }
    }
    LL ans = 0;
    REP(i, maxl)ans = max(ans, dp[n][i]);
    cout << ans << endl;
}


Measured memory_bytes: 160640
#-------------------------------------------------------------------
import sys
def p(*_a):
  _s=" ".join(map(str,_a))
  #print(_s)
  sys.stderr.write(_s+"\n")
#-------------------------------------------------------------------
s = input()
q = int(input())

r=0

a=""
z=""

for i in range(q):
	t = input()
	
	if t=='1':
		if r==0:
			r=1
		else:
			r=0
#		p("t,r,s",t,r,s)
		continue
	
	_,f,c = t.split()

	if f=='1':
		if r==0: a = a + c
		if r==1: z = z + c
	if f=='2':
		if r==0: z = z + c
		if r==1: a = a + c


#	p("t,r,_,f,c,x,s","[",t,"]",r,_,f,c,x,s)

ans=""
if (r==0):
	ans = a[::-1] + s + z
else:
	ans = z[::-1] + s[::-1] + a

print(ans)


	
	

Measured memory_bytes: 4408
#include <bits/stdc++.h>
using namespace std;
using lint = long long int;
using pint = pair<int, int>;
using plint = pair<lint, lint>;
struct fast_ios { fast_ios(){ cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(20); }; } fast_ios_;
#define FOR(i, begin, end) for(int i=(begin),i##_end_=(end);i<i##_end_;i++)
#define IFOR(i, begin, end) for(int i=(end)-1,i##_begin_=(begin);i>=i##_begin_;i--)
#define REP(i, n) FOR(i,0,n)
#define IREP(i, n) IFOR(i,0,n)
template<typename T> istream& operator>>(istream &is, vector<T> &vec){ for (auto &v : vec) is >> v; return is; }
template<typename T> ostream& operator<<(ostream &os, vector<T> &vec){ os << "["; for (auto v : vec) os << v << ","; os << "]"; return os; }
template<typename T> ostream& operator<<(ostream &os, set<T> &vec){ os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; }
template<typename T1, typename T2> ostream& operator<<(ostream &os, pair<T1, T2> &pa){ os << "(" << pa.first << "," << pa.second << ")"; return os; }
template<typename TK, typename TV> ostream& operator<<(ostream &os, map<TK, TV> &mp){ os << "{"; for (auto v : mp) os << v.first << "=>" << v.second << ","; os << "}"; return os; }
#define dbg(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ") " << __FILE__ << endl;

int N, K;
vector<int> A, B;

lint solve(int k)
{
    lint res = 0;
    REP(i, N) if (!((~k) & A[i])) res += B[i];
    return res;
}

int main()
{
    cin >> N >> K;
    A.resize(N);
    B.resize(N);
    REP(i, N) cin >> A[i] >> B[i];

    lint ans = solve(K);
    REP(d, 32) if ((K >> d) & 1)
    {
        int k = (K ^ (1 << d)) | ((1 << d) - 1);
        ans = max(solve(k), ans);
    }
    cout << ans << endl;
}


Measured memory_bytes: 1024