akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>

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

using namespace std;
using lint=long long;

template<class T>
class Fenwick_tree{
	vector<T> a;
public:
	Fenwick_tree(int n):a(n){}
	void add(int i,T val){
		for(;i<a.size();i|=i+1) a[i]+=val;
	}
	T sum(int l,int r){
		if(l==0){
			T res{};
			for(r--;r>=0;r=(r&(r+1))-1) res+=a[r];
			return res;
		}
		return sum(0,r)-sum(0,l);
	}
};

int n,a[100000];

// number of pairs (l, r) such that median of a[l..r) >= x
lint solve(int x){
	int b[100000];
	rep(i,n) b[i]=(a[i]>=x?1:-1);

	lint res=0;
	int sum=0;
	Fenwick_tree<int> F(2*n+1);
	F.add(n,1);
	rep(i,n){
		sum+=b[i];
		res+=F.sum(0,n+sum+1);
		F.add(n+sum,1);
	}
	return res;
}

int main(){
	scanf("%d",&n);
	rep(i,n) scanf("%d",a+i);

	lint m=n*(n+1LL)/2;

	int lo=0,hi=1e9+1;
	while(hi-lo>1){
		int mi=(lo+hi)/2;
		if((m+1)/2<=solve(mi)) lo=mi;
		else                   hi=mi;
	}
	printf("%d\n",lo);

	return 0;
}


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

#define pb push_back
#define all(c) c.begin(),c.end()
#define allr(c) c.rbegin(),c.rend()
#define MOD 1000000007
#define PI 3.14159265
#define endl '\n'


using namespace std;

void quick ()
{
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(0);/*//*/
}

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

void readFromText()
{
#ifndef ONLINE_JUDGE
    freopen("input.txt","r",stdin);
#endif // ONLINE_JUDGE
}

int main()
{
   quick();
//    readFromText();
    int n ; cin >> n ;
    while (n!=0){
        if (n%10==7){
            cout << "Yes" << endl ;
            return 0 ;
        }
        n/=10;
    }
    cout << "No" << endl ;
    return 0;
}



Measured memory_bytes: 3672
n = int(input())

if n < 105:
    print(0)
    exit()

ans = 0
for i in range(105, n + 1, 2):
    c = 0
    for j in range(3, n // 2):
        if i % j == 0:
            c += 1
    if c == 6:
        ans += 1

print(ans)


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

using namespace std;

#define vit vector<int>::iterator
#define pb push_back
#define ppb pop_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define forn(i, n) for(int i = 0; i < int(n); i++)
#define fr first
#define sc second
#define skip continue
#define PI 3.14159265

typedef unsigned long long ull;
typedef long long ll;
typedef unsigned int ui;
typedef long double ld;
typedef vector<int> vi;
typedef vector<long long> vll;
typedef vector<bool> vb;

const int INF = 1e9 + 5;
const int MAXN = 3e6 + 123;

void faster(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}
bool cmp(const string& a, const string& b) {
	return (a + b) < (b + a);
}

vector<int> Reversed(const vector<int>& s){
   vector<int> d = s;
   reverse(all(d));
   return d;
}
//int a[27];
void solve(){
    string s;
    cin >> s;
    if(((s[0] == '0' && s[1] != '0') || (s[0] == '1' && s[1] <= '2'))  && ((s[2] == '0' && s[3] != '0') || (s[2] == '1' && s[3] <= '2'))){
        cout << "AMBIGUOUS";
        return;
    }
    if(((s[0] == '0' && s[1] != '0') || (s[0] == '1' && s[1] <= '2'))  || ((s[2] == '0' && s[3] != '0') || (s[2] == '1' && s[3] <= '2'))){
       if(((s[0] == '0' && s[1] != '0') || (s[0] == '1' && s[1] <= '2')))
        cout << "MMYY";
       else cout << "YYMM   ";
    }
    else cout << "NA";
}

// ."ww"w"".ww"""...ww"".

int main(){
    //freopen("lepus.in","r",stdin);
    //freopen("lepus.out","w",stdout);
    //faster();
    int n=1;
    //cin>>n;
    while(n--){
    solve();
    //cout << endl;
    }
    //fclose(stdout);
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
using namespace std;
static const int MAX = 200000;


int main(){

    int a[MAX];
    int minv = 0;
    int maxv = 0;
    int n;
    
    cin >> n;
    for (int i = 0;i < n;i++){
        cin >> a[i];
    }
    
    minv = a[0];
    maxv = a[1] - a[0];
    
    for(int i = 1;i < n;i++){
        maxv = max(maxv,a[i] - minv);
        minv = min(minv, a[i]);
    }
    
    cout << maxv << endl;
    return 0;
}

Measured memory_bytes: 1940
#include<iostream>
typedef long long ll;
using namespace std;
int N;
ll ans;
bool is_prime[1001];
ll count[1001];

void era(){
  for(int i = 0; i < 1001; i++)is_prime[i] = true;
  is_prime[0] = is_prime[1] = false;
  for(int i = 2; i < 1001; i++){
    if(is_prime[i]){
      for(int j = 2 * i; j < 1001; j += i)is_prime[j] = false;
    }
  }
  return;
}
  

int main(){
  cin>> N;
  era();
  for(int i = 1; i <= N; i++){
    int s = i;
    for(int j = 2; j <= i; j++){
	if(is_prime[j]){
	  while(s % j == 0){
	    count[j]++;
	    s /= j;
	  }
      }
    }
  }
  ans = (count[2]+1);
  for(int i = 3; i <= N; i++){
    if(is_prime[i] && count[i]){
      ans *= (count[i]+1);
      if(ans > 1000000007)ans %= 1000000007;
    }
}
  cout<<ans<<endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <cstring>
#include <map>
#include <queue>
#include <cmath>
#include <complex> // complex<double> a(1.2 , 2.3);// real(): 1.2, imag()2.3
using namespace std;

#define MOD 1000000007
#define ll long long
#define ld long double
#define FOR(i,a,b) for(ll i=(ll)a;i<(ll)b;i++)
#define rep(i,n) FOR(i,0,n)
#define pb push_back
#define mp make_pair
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define rmsame(a) sort(all(a)),a.erase(unique(all(a)), a.end())
#define rmvector(a,b) rep(i,a.size())rep(j,b.size())if(a[i]==b[j]){a.erase(a.begin()+i);i--;break;}
template<typename X> bool exist(vector<X> vec, X item){return find(all(vec), item)!=vec.end();}

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

  string S,T;
  cin >> S >> T;

  for(ll i = S.size()-T.size(); i>=0;i--){
    string sub1 = S.substr(i,T.size());
    string sub2 = T;
    rep(j,sub1.size()){
      if(sub1[j]=='?')sub2[j]='?';
    }

    if(sub1==sub2){
      rep(j,T.size())
	S[i+j]=T[j];

      rep(j,S.size())
	if(S[j]=='?')S[j]='a';
      cout << S << endl;
      return 0;
    }
    
  }

  cout << "UNRESTORABLE" << endl;
  
  //cout << fixed << setprecision(16) << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#include <string>
#include <stdio.h>
#include <algorithm>
#include <iostream>
#include <vector>
#include <cmath>
#define rep(i,n) for(int i = 0; i < (n); i++)
using namespace std;
int main()
{
    int n;
    cin >> n;
    vector<vector<int>> table(10, vector<int>(10, 0));

    for(int i = 1; i <= n; i++){
        if(i % 10 == 0) continue;
        int end = i % 10;
        int tmp = i;
        while(tmp / 10 != 0) tmp /= 10;
        int front = tmp;
        table[front][end]++;
    }

    int ans = 0;
    for(int i = 1; i <= 9; i++){
        for(int j = 1; j <= i; j++){
            if(i == j) ans += table[i][j] * table[i][j];
            else ans += table[i][j] * table[j][i] * 2; 
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 3620
#include<iostream>

using namespace std;

int main(){
    
    int n;

    cin >> n;

    for(int i = 0; i <= n / 4; i++){
        for(int j = 0; j <= n / 7; j++){
            if((i * 4) + (j * 7) == n){
                cout << "Yes" << endl;
                return 0;
            }
        }
    }

    cout << "No" << endl;

    return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int r = sc.nextInt();
        if (n >= 10) {
            System.out.println(r);
        } else {
            System.out.println(r + (10 - n)* 100);
        }
    }


}

Measured memory_bytes: 23124
#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;
  int x;
  cin >> x;

  vector<int> arr(n);
  for (int &x : arr) {
    cin >> x;
  }
  sort(all(arr));
  cout << accumulate(arr.begin(), arr.begin() + x, 0ll) << 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: 3632
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <fstream>
#include <sstream>
#include <set>
#include <map>
#include <vector>
#include <list>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>
#include <queue>
#include <bitset>     //UWAGA - w czasie kompilacji musi byc znany rozmiar wektora - nie mozna go zmienic
#include <cassert>
#include <iomanip>        //do setprecision
#include <ctime>
#include <complex>
using namespace std;

#define FOR(i,b,e) for(int i=(b);i<(e);++i)
#define FORQ(i,b,e) for(int i=(b);i<=(e);++i)
#define FORD(i,b,e) for(int i=(b)-1;i>=(e);--i)
#define REP(x, n) for(int x = 0; x < (n); ++x)

#define ST first
#define ND second
#define PB push_back
#define MP make_pair
#define LL long long
#define ULL unsigned LL
#define LD long double

const double pi = 3.141592653589793238462643383279502884197169399375105820974944592307816406286208998628034825342;
const int mod=1000000007;

int main(){
	int n,m,c=0;
	cin>>n;
	map<string , int> mp;
	string s;
	FOR(i,0,n){
		cin>>s;
		mp[s]++;
	}
	cin>>m;
	FOR(i,0,m){
		cin>>s;
		mp[s]--;
	}
	for(auto x:mp){
		c=max(x.ND,c);
	}
	cout<<c<<endl;

    return 0;
}


Measured memory_bytes: 256
N = gets.chomp.to_i
ps = gets.chomp.split(' ').map(&:to_i)

prev = false
count = 0
ps.each_with_index do |pi, i|
  if pi == i + 1
    if prev
      prev = false
      count += 1
    else
      prev = true
      count += 1 if i == (ps.length - 1)
    end
  else
    if prev
      count += 1
      prev = false
    end
  end
end

print count

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

int main(){
    int n;
    long long ans = 0;
    cin>>n;
    for(int i=1;i<=n;i++){
        if(i%3!=0 && i%5!=0)
            ans += i;
    }
    cout<<ans;
    return 0;
}


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

int main() {
    string s,t,r;
    cin>>s;
    ll n = s.size(), ans=0;
    for(int i=0; i<n; i++) {
        r += s[i];
        if(t != r) {
            t = r;
            r = "";
            ans++;
        }
    }
    cout<<ans;
}

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

namespace Algorithm
{
    class Program
    {
        static void Main(string[] args)
        {
            var l = Console.ReadLine().Split().Select(int.Parse).ToArray();
            int N = l[0], K = l[1];
            Console.WriteLine(N - K + 1);
        }
    }
}


Measured memory_bytes: 13268
from collections import deque
import bisect
s = str(input())
t = str(input())

sc = [0] * 26
tc = [0] * 26

for i in range(len(s)):
    sc[ord(s[i]) - ord("a")] += 1
for i in range(len(t)):
    tc[ord(t[i]) - ord("a")] += 1

# 不可能な場合
for i in range(26):
    if tc[i] > 0 and sc[i] == 0:
        print(-1)
        exit()


alph = [[] for _ in range(26)]
for i in range(len(s)):
    alph[ord(s[i]) - ord("a")].append(i)

ans = [0] * len(t)
pre_num = -1
for i in range(len(t)):
    num = ord(t[i]) - ord("a")
    if i > 0:
        idx = bisect.bisect_right(alph[num], pre_num)
        if idx >= len(alph[num]):
            num_idx = alph[num][0]
        else:
            num_idx = alph[num][idx]
    else:
        num_idx = alph[num][0]
    ans[i] = num_idx
    pre_num = num_idx

count = 0
pre = -1
for v in ans:
    if pre >= v:
        count += 1
    pre = v

print(count * len(s) + ans[-1] + 1)

Measured memory_bytes: 47984
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    c = [[t for t in S()] for _ in range(2)]
    c[1].reverse()
    if c[0] == c[1]:
        return 'YES'

    return 'NO'



print(main())




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

using namespace std;

int main(){
	int n;
	cin>>n;
	vector<int> arr(n);
  vector<int> dp(n);
	for(int i=0; i<n; i++) cin>>arr[i];
  dp[1] = abs(arr[1] - arr[0]);
	for(int i=2; i<n; i++){
		dp[i] = min(abs(arr[i] - arr[i-1])+dp[i-1], abs(arr[i] - arr[i-2])+dp[i-2]);
	}
	cout<<dp[n-1]<<endl;
	return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
/*{{{*/  //template
#define rep(i,n) for(int i=0;i<n;i++)
constexpr int INF = numeric_limits<int>::max()/2;
constexpr long long LINF = numeric_limits<long long>::max()/3;
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define all(v) (v).begin(),(v).end()
#define sz(x) (int)(x).size()
#define debug(x) cerr<<#x<<":"<<x<<endl
#define debug2(x,y) cerr<<#x<<","<<#y":"<<x<<","<<y<<endl
//struct fin{ fin(){ cin.tie(0); ios::sync_with_stdio(false); } } fin_;
struct Double{ double d; explicit Double(double x) : d(x){} };
ostream& operator<<(ostream& os,const Double x){ os << fixed << setprecision(20) << x.d; return os; }
template<typename T> ostream& operator<<(ostream& os,const vector<T>& vec){ os << "["; for(const auto& v : vec){ os << v << ","; } os << "]"; return os; }
template<typename T,typename U> ostream& operator<<(ostream& os,const pair<T,U>& p){ os << "(" << p.first << ","<< p.second <<")"; return os; }
template<typename T> ostream& operator<<(ostream& os,const set<T>& st){ os<<"{"; for(T v:st) os<<v<<","; os <<"}"; return os; }
template<typename T,typename U> inline void chmax(T &x,U y){ if(y>x) x = y; }
template<typename T,typename U> inline void chmin(T &x,U y){ if(y<x) x = y; }
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
ll gcd(ll a,ll b){ if(b==0) return a; else return gcd(b,a%b); }
//constexpr double eps = 1e-14; 
constexpr double eps = 1e-10; 
constexpr ll mod = 1e9+7;
const int dx[]={1,0,-1,0} ,dy[] = {0,1,0,-1};
/*}}}*/

struct edge{
    long long from,to,cost;
    edge(){}
    edge(long long f,long long t,long long c) : from(f),to(t),cost(c){}
};

bool find_negative_path(int s,int t,const vector<edge>& es,int V,int E){
    constexpr long long inf = 1ll<<60;
    vector<long long> d(V,inf);
    d[s] = 0;
    for(int i=0;i<=2*V;i++){
        for(const edge& e:es){
            if(d[e.from]!=inf && d[e.to] > d[e.from] + e.cost){
                d[e.to] = d[e.from] + e.cost;
                if(i >= V-1 and e.to == t){
                    return true;
                }
            }
        }
    }
    return false;
}


vector<long long> bellman_ford(int s,const vector<edge>& es,int V,int E){
    constexpr long long inf = 1ll<<60;
    vector<long long> d(V,inf);
    d[s] = 0;
 
    int cnt=0;
    while(true){
        if(++cnt == V) break;
        bool update = false;
        for(const edge &e : es){
            if(d[e.from] != inf && d[e.to] > d[e.from] + e.cost){
                d[e.to] = d[e.from] + e.cost;
                update = true;
            }
        }
        if(!update) break;
    }
    return d;
}

int main(){
    int N,M;
    cin >> N >> M;
    vector<edge> es;
    rep(i,M){
        long long a,b,c;
        cin >> a >> b >> c;
        a--;b--;
        es.pb(edge(a,b,-c));
    }


    if(find_negative_path(0,N-1,es,N,M)){
        cout << "inf" << endl;
    }else{
        auto d =  bellman_ford(0,es,N,M);
        cout << -d[N-1] << endl;
    }
    return 0;
}

Measured memory_bytes: 384
#include<iostream>
#include<cmath>
#include<vector>
using namespace std;

int main(){
  int n;
  while(1){
    cin >> n;
    if(!n)break;

    vector<int> d;
    int r = (int)sqrt(n);
    for(int i=2;i<=r;i++){
      if( !(n%i) ){
	d.push_back(i);
	if(i!=n/i)d.push_back(n/i);
      }
    }

    int sum = 0;
    if(n!=1){
      sum += 1;
      for(int i=0;i<(int)d.size();i++){
	sum += d[i];
      }
    }
    if(sum<n)cout << "deficient number" << endl;
    else if(sum>n)cout << "abundant number" << endl;
    else cout << "perfect number" << endl;
  }
}

Measured memory_bytes: 0
n = int(input())
a = list(map(int, input().split()))

odd = [0 for i in range(10**5)]
even = [0 for i in range(10**5)]

for i in range(n):
    if i % 2 == 0:
        odd[a[i]-1] += 1
    else:
        even[a[i]-1] += 1
        
oddmax = 0
evenmax = 0

oddfirst = 0
oddsecond = 0
evenfirst = 0
evensecond = 0

for i in range(10**5):
    if odd[i] >= oddfirst:
        oddsecond = oddfirst
        oddfirst = odd[i]
        oddmax = i
    elif odd[i] >= oddsecond:
        oddsecond = odd[i]
        
    if even[i] >= evenfirst:
        evensecond = evenfirst
        evenfirst = even[i]
        evenmax = i
    elif even[i] >= evensecond:
        evensecond = even[i]

a = 0
if oddmax == evenmax:
    a = min(oddfirst - oddsecond, evenfirst - evensecond)
        
ans = n - oddfirst - evenfirst + a
print(ans)

Measured memory_bytes: 14008
#include <bits/stdc++.h>
#include <unordered_map>
#include <unordered_set>
using namespace std;
#define lp(i, n)         for(int i=0;i<(int)(n);++i)
#define lpi(i, j, n)     for(int i=(j);i<(int)(n);++i)
#define lpd(i, j, n)     for(int i=(j);i>=(int)(n);--i)
#define sci(a)	scanf("%d",&a)
#define scii(a, b)	scanf("%d%d",&a, &b)
typedef long long ll;
const ll  inf = 1000000000000000000LL;
const double EPS = 1e-7;
const ll mod = 1000000007ll;
#define PI acos(-1)

const int maxn = 300500;
map<char,int> cnt;

int main(){
	//freopen("squares.in", "rt", stdin);
//	freopen("uva.txt", "rt", stdin);
   string a; cin >> a;
   for(char c:a) cnt[c]++;
   ll n = a.size();
   ll ret = 0;
   for(auto i: cnt) ret += i.second*ll(i.second-1LL)/2LL;
   cout << (n*(n-1LL)/2LL)-ret+1;
}	

Measured memory_bytes: 640
import java.util.Scanner;

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

        int[][] a = new int[n][3];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < 3; j++) {
                a[i][j] = sc.nextInt();
            }
        }

        int[][] dp = new int[n][3];

        dp[0][0] = a[0][0];
        dp[0][1] = a[0][1];
        dp[0][2] = a[0][2];

        for (int i = 1; i < n; i++) {
            dp[i][0] = a[i][0] + Math.max(dp[i - 1][1], dp[i - 1][2]);
            dp[i][1] = a[i][1] + Math.max(dp[i - 1][0], dp[i - 1][2]);
            dp[i][2] = a[i][2] + Math.max(dp[i - 1][0], dp[i - 1][1]);
        }
        System.out.println(Math.max(dp[n - 1][0], Math.max(dp[n - 1][1], dp[n - 1][2])));
    }
}


Measured memory_bytes: 64412
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int search(int);

int main()
{
  int n,i,j,count=0;
  int *array;

  scanf("%d",&n);
  array = (int *)malloc(sizeof(int) * n);
  if(array == NULL) exit(0);
  for(i = 0;i < n;i++){
    scanf("%d",&array[i]);
  }

  for(i = 0;i < n;i++){
    if(search(array[i]) == 1) count++;
  }
    
  printf("%d\n",count);

  free(array);

  return 0;
}

int search(int x)
{
  int i;

  if(x == 2) return 1;

  if(x < 2 || (x % 2 == 0)) return 0;

  i = 3;
  while(i <= sqrt(x)){
    if(x % i == 0) return 0;
    i = i + 2;
  }

  return 1;
}

Measured memory_bytes: 628
#include <iostream>
#include <fstream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <cassert>
#include <utility>
#include <iomanip>
#include <chrono>
#include <random>
#include <bitset>

using namespace std;

#define sz(x) (int) x.size()
#define unique(x) x.erase(unique(x.begin(), x.end()), x.end())
#define all(a) a.begin(), a.end()
#define sqr(x) ((x) * (x)) 
#define y1 aksjdaskdjksjfksdjf
#define left kdnvldvoiwejifejg
#define right lkdsjflksdjfdjfk
#define prev asdasfsadjkjsdfjs
#define tm aklsjdasjdasjdkdjjf
#define lcm hddalkwjeidjjhasda
#define random_shuffle asdasdd

const int MAXN = 105000;

int n, k;
string s;
int a[MAXN];

bool ok(int x) {
  for (int i = 0; i + x - 1 < n; i++) {
    int need = a[i + x - 1];
    if (i - 1 >= 0) {
      need -= a[i - 1];
    }
    if (s[i] == '0' && i - 1 >= 0 && s[i - 1] == '0') {
      need++;
    }
    if (need <= k) {
      return true;
    }
  }
  return false;
}

int main() { 

  scanf("%d %d\n", &n, &k); 
  getline(cin, s);

  for (int i = 0; i < n; i++) {
    if (s[i] == '0' && (i == 0 || s[i - 1] != '0')) {
      a[i]++;
    }
    if (i > 0) {
      a[i] += a[i - 1];
    }
  }

  int l = 1, r = n;
  while (l < r) {
    int mid = (l + r + 1) / 2;
    if (ok(mid)) {
      l = mid;
    } else {
      r = mid - 1;
    }
  }

  cout << l << endl;

  return 0;
}


Measured memory_bytes: 896
import           Data.Char
import qualified Data.ByteString.Char8 as B

main :: IO ()
main = uncurry solve <$> getParams >>= B.putStrLn

getParams :: IO (Int, B.ByteString)
getParams = (,) <$> readLn <*> B.getLine

solve :: Int -> B.ByteString -> B.ByteString
solve n = B.map (rotate n)

rotate :: Int -> Char -> Char
rotate n = int2chr . rotateInt . chr2int
  where int2chr = chr . (+ basePoint)
        chr2int = subtract basePoint . ord
        rotateInt = (`mod` 26) . (+ n)
        basePoint = ord 'A'


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

using namespace std;
using ll = long long;
using ull = unsigned long long;
constexpr int inf = 1<<30;
constexpr int mo = 1e9+7;
constexpr ll infl = 1ll<<60;

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    
    int n;
    cin>>n;
    int m;
    cin>>m;
    vector<pair<int,int>> v;
    for(int i=0;i<m;++i){
        int l,r;
        cin>>l>>r;
        v.push_back({r,l});
    }
    sort(v.begin(),v.end());
    int cur = 0;
    int ret = 0;
    for(int i=0;i<(int)v.size();++i){
        if(v[i].second >= cur)ret++,cur=v[i].first;
    }
    cout << ret << endl;
    return 0;
}

Measured memory_bytes: 4260
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define MP make_pair
#define PII pair<int, int>
#define PLL pair<ll, ll>
#define PLI pair<ll, int>
#define PIL pair<int, ll>
#define STR string
#define Fst first
#define Snd second
#define SHN 1e9
#define LSHN 1e18
using namespace std;
ll n,m;
int main()
{
	cin >>n>>m;
	cout <<n*m/__gcd(n,m);
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<deque>
#include<cstring>

int main()
{
	int n;
	std::cin >> n;
	
	while( n-- )
	{
		std::string s;
		std::cin >> s;

		std::deque<char> deq;
		deq.push_back( s[0] );
		
		int p = 0;
		
		for( int i = 1; i < s.size(); i += 3 )
		{
			if( s[i] == '<' && !(p--) )
				deq.push_front( s[i+2] ), ++p;
			else if( s[i+1] == '>' && ++p == deq.size() )
				deq.push_back( s[i+2] );
		}

		for( auto it = deq.begin(); it != deq.end(); ++it )
			std::cout << *it;

		std::cout << std::endl;
	}

	return 0;
}

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

using namespace std;

using i64 = int64_t;

const i64 MOD = 1e9+7;

const i64 INF = 1e18+7;


signed main(){
    i64 a, b;
    cin >> a >> b;

    auto f = [&](i64 x){
        if(x % 4 == 0)
            return x;
        if(x % 4 == 1)
            return 1L;
        if(x % 4 == 2)
            return x | 1L;
        return 0L;
    };
    i64 aa = f(a - 1);
    i64 bb = f(b);

    cout << (bb ^ aa) << endl;
}


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

const int INF = 1e9;

int main() {
	int N, W;
	cin >> N >> W;
	vector<int> v(N, 0);
	vector<int> w(N, 0);
	for (int i=0;i<N;i++) {
		cin >> v[i] >> w[i];
	}

	vector<vector<int>> dp(N+1, vector<int>(W+1, -INF));
	dp[0][0] = 0;
	for (int i=0;i<N;i++) {
		for (int j=0;j<W+1;j++) {
			dp[i+1][j] = max(dp[i+1][j], dp[i][j]);
			if (j+w[i]<W+1) dp[i+1][j+w[i]] = max(dp[i+1][j+w[i]], dp[i][j]+v[i]);
		}
	}

	int ans = 0;
	for (int i=0;i<=W;i++) ans = max(ans, dp[N][i]);

	cout << ans << endl;
}


Measured memory_bytes: 6852
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <algorithm>
#include <utility>
#include <deque>
#include <stack>
#include <bitset>
#include <iomanip>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<int,ll> pil;
typedef pair<ll,int> pli;
#define rep(i,n) for (int i=0;i<n;++i)
#define REP(i,n) for (int i=1;i<=n;++i)
#define all(x) x.begin(),x.end()
#define mp make_pair
#define pb push_back
#define pf push_front
#define F first
#define S second
#define read(x) scanf("%d",&x)
int n;
int id[1005][1005],N=0;
vector<int> G[500005];
int dp[500005],Rs[500005];
int x[1005];
queue<int> q;
int main(){
	ios::sync_with_stdio(false);
	cin>>n;
	REP(i,n) REP(j,n-1){
		cin>>x[j];
		if (!id[i][x[j]]) id[i][x[j]]=id[x[j]][i]=++N;
		if (j>1) G[id[i][x[j-1]]].pb(id[i][x[j]]),Rs[id[i][x[j]]]++;
	}
	REP(i,N) if (Rs[i]==0){
		q.push(i);dp[i]=1;
	}
	while(!q.empty()){
		int u=q.front();q.pop();
		for (int i=0;i<G[u].size();++i){
			int v=G[u][i];--Rs[v];
			dp[v]=max(dp[v],dp[u]+1);
			if (Rs[v]==0) q.push(v);
		}
	}
	int ans=0;
	REP(i,N){
		if (!dp[i]){
			cout<<-1<<endl;return 0;
		}
		ans=max(ans,dp[i]);
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 35456
//#pragma GCC optimize("03,unroll-loops")
//#pragma GCC target("avx,avx2,fma")

#include<bits/stdc++.h>
typedef long long ll;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ordered_set tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update>
#define pb           push_back
#define ff           first
#define ss           second
#define gcd(a, b)    __gcd(a, b)
#define lcm(a, b)    ((a)*((b)/gcd(a,b)))
#define all(v)       v.begin(),v.end()
#define lllim        2147483648
#define Pi           2*acos(0.0)
#define sci(n)	     scanf("%d",&n)
#define scii(n,m)    scanf("%d%d",&n,&m)
#define scl(n)       scanf("%lld",&n)
#define scll(n,m)    scanf("%lld%lld",&n,&m)
#define pii          pair<int,int>
#define pll 	     pair<ll,ll>
#define mem(a,b)     memset(a, b, sizeof(a))
#define fill_(a,b)   fill(a,a+n,b);
#define MOD          1e9+7
#define fast_cin     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define filein       freopen("input.txt","r", stdin)
#define D(x)         cerr << __LINE__ << ": " << #x << " = " << (x) << '\n'
#define case		 int t,cas=1;cin>>t;while(t--)
#define rep(i,a,n)   for(int i=a;i<n;i++)
#define rev(i,n,a)   for(int i=n;i>=a;i--)

/*------------------------------Graph Moves----------------------------*/
//const int fx[]= {+1,-1,+0,+0};
//const int fy[]= {+0,+0,+1,-1};
//const int fx[]= {+0,+0,+1,-1,-1,+1,-1,+1};  // Kings Move
//const int fy[]= {-1,+1,+0,+0,+1,+1,-1,-1}; // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*---------------------------------------------------------------------*/

template<class T> void ckmin(T& a, const T& b) {
    a= b < a? b:a;
}
template<class T> void ckmax(T& a, const T& b) {
    a= b > a? b:a;
}

template<class T> void read(T& a) {
    std::cin>>a;
}

template<class T> void read(T& a, T& b) {
    std::cin>>a>>b;
}
template<class T> void read(T& a,T& b, T& c) {
    std::cin>>a>>b>>c;
}

template<class T> void read(T& ara, int sidx,  int eidx) {
    for(int i=sidx; i<eidx; i++)
        std::cin>>ara[i];
}




using namespace std;
using namespace __gnu_pbds;

const int maxn=500;
const int inf = INT_MAX;


void solve()
{
	string s,t;
	cin>>s>>t;
	
	int ans=INT_MAX;
	
	for(int i=0;i<=(int)s.size()-(int)t.size();i++)
	{
		int cnt=0;
		for(int j=0;j<(int)t.size();j++)
		{
			if(s[i+j]==t[j]) cnt++;
		}
		
		ans=min(ans, (int)t.size()-cnt);
	}
	cout<<ans<<endl;
	
	
	
}



int main()
{
	fast_cin;
	//case
	{
		solve();
		
	}
   
    return 0;
}


Measured memory_bytes: 3668
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef pair<ld,ld> pi;
#define inf 1000000000
#define rep(i,a,b) for (int i = a; i <= b; i++)
#define f first
#define s second
#define pb push_back
//#define mp make_pair

int n, k, s;

int main(){

cin >> k >> s;

rep(i, 0, k){
    rep(j, 0, k){

    if(s-(i+j)>=0 && s-(i+j)<=k)n++;

    }
}

cout << n << endl;

return 0;}


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

int next[20][100005];
int xs[100005];

int main(){
  int N,L,Q;
  scanf("%d",&N);
  for(int i=0;i<N;i++){
    scanf("%d",&xs[i]);
  }
  scanf("%d %d",&L,&Q);
  int j=N-1;
  for(int i=N-1;i>=0;i--){
    while(xs[j]-xs[i]>L){
      j--;
    }
    next[0][i]=j;
    for(int k=1;k<20;k++){
      next[k][i]=next[k-1][next[k-1][i]];
    }
  }
  
  for(int i=0;i<Q;i++){
    int A,B;
    scanf("%d %d",&A,&B);
    A--,B--;
    if(A>B) std::swap(A,B);
    int res=1;
    for(int k=20-1;k>=0;k--){
      if(next[k][A]<B){
	A=next[k][A];
	res+=(1<<k);
      }
    }
    printf("%d\n",res);
  }
  return 0;
}


Measured memory_bytes: 8960
#button = i*m + j*(n-2*i) = k
n,m,k = map(int, input().split())
for i in range(n+1):
  if 2*i == n:
    if i*m == k:
      print("Yes")
      break
  else:
    t = k-i*m
    s = n-2*i
    if t%s==0 and 0<=t//s<=m:
      print("Yes")
      break
else:
  print("No")

Measured memory_bytes: 3064
#include "bits/stdc++.h"
#define rep(i,n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	string s;
	cin >> s;
	int n = s.size() / 2;
	n--;
	string t, u;
	while(n > 0){
		bool ok = true;
		rep(i,n){
			if(s[i] != s[i+n]){
				ok = false;
				break;
			}
		}
		if(ok){
			cout << n * 2 << endl;
			return 0;
		}
		n--;
	}
	cout << 2 << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for (int i = 0; i < n; ++i)
template <typename T>
void view(const std::vector<T> &v)
{
    for (const auto &e : v)
    {
        std::cout << e << " ";
    }
    std::cout << std::endl;
}

int main()
{
    int n, k, q;
    cin >> n >> k >> q;
    vector<int> players(n);
    rep(i, q)
    {
        int a;
        cin >> a;
        players[a - 1] += 1;
    }

    rep(i, n)
    {
        string win = k + players[i] > q ? "Yes" : "No";
        cout << win << endl;
    }

    return 0;
}

Measured memory_bytes: 1024
use std::io::Read;

fn main() {
    let mut line = String::new();
    std::io::stdin().read_to_string(&mut line).unwrap();
    let mut it = line.split_whitespace();
    let n: usize = it.next().unwrap().parse().unwrap();
    let k: usize = it.next().unwrap().parse().unwrap();
    let mut count = vec![0; n];
    for _ in 0..k {
        let d: usize =  it.next().unwrap().parse().unwrap();;
        for _ in 0..d {
            let a: usize = it.next().unwrap().parse().unwrap();
            count[a-1] += 1
        }
    }
    let mut ans = 0;
    for i in 0..n {
        if count[i] == 0 {
            ans += 1;
        }
    }
    println!("{}", ans);
}


Measured memory_bytes: 2128
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#include <iomanip> // double
using namespace std;
using vi = vector<int>;
using vii = vector<vi>;
using in6 = int64_t;
using ind = double;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

int main() {
  ios::sync_with_stdio(false);
  while(1) {
      int m,f,r;
      cin >> m >> f >> r;
      if(m == -1 && f == -1 && r == -1) break;
      int sum = m + f;
      if(m * f < 0) cout << "F" << "\n";
      else if(sum >= 80) cout << "A" << "\n";
      else if(sum >= 65) cout << "B" << "\n";
      else if(sum >= 50) cout << "C" << "\n";
      else if(sum >= 30 && r >= 50) cout << "C" << "\n";
      else if(sum >= 30) cout << "D" << "\n";
      else cout << "F" << "\n";
  }
}


Measured memory_bytes: 3212
#include <iostream>

int memo[1000][1000];
int w[1000];

using namespace std;

template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val) {
    std::fill((T *) array, (T *) (array + N), val);
}

int search(const int _n, int l, int r) {
    int m = r - l;
    if (m < 1)return 0;
    if (memo[l][r] >= 0)return memo[l][r];
    int sa = abs(w[l] - w[r]);
    if (m == 1) {
        return (sa < 2) ? 2 : 0;
    } else {
        int s = search(_n, l + 1, r - 1);
        s += (sa < 2 && s == (m - 1)) ? 2 : 0;
        for (int i = l + 1; i < r; i++) s = max(search(_n, l, i) + search(_n, i + 1, r), s);
        return memo[l][r] = s;
    }
}

int main() {
    int n;
    while (true) {
        Fill(memo, -1);
        cin >> n;
        if (n == 0)break;
        for (int i = 0; i < n; i++) cin >> w[i];
        cout << search(n, 0, n - 1) << std::endl;
    }
    return 0;
}


Measured memory_bytes: 7036
import java.util.*;

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

      int a = Integer.parseInt(sc.next());
      int b = Integer.parseInt(sc.next());

      /*
      int[] a = new int[n];
      for(int i=0;i<n;i++){
        a[i] = Integer.parseInt(sc.next());
      }
	  */
      
      int ans;
      
      if(a>12){ans=b;}
      else if(a<6){ans=0;}
      else{ans=b/2;}
      System.out.println(ans);

    }
}


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

int main() {
    int h,w,d;
    cin>>h>>w>>d;
    int x[h*w+1],y[h*w+1];
    for (int i = 0; i < h; ++i) {
        for (int j = 0; j < w; ++j) {
            int num;
            cin>>num;
            x[num]=i;
            y[num]=j;
        }
    }
    int cost[h*w+1];
    for(int i=1;i<d+1;i++){
        cost[i]=0;
        for(int j=i+d;j<h*w+1;j+=d){
            cost[j]=cost[j-d]+abs(x[j]-x[j-d])+abs(y[j]-y[j-d]);
        }
    }
    int q;
    cin>>q;
    for (int k = 0; k < q; ++k) {
        int l,r,m=0;
        cin>>l>>r;
        cout<<cost[r]-cost[l]<<endl;
    }
    return 0;
}

Measured memory_bytes: 2176
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define lvector vector<ll>
#define cvector vector<char>
#define svector vector<string>
#define lque queue<ll>
#define lpque priority_queue<ll>
#define dlpque priority_queue<ll,lvector,greater<ll>>
#define P pair<ll,ll>
#define ALL(a) a.begin(),a.end()
#define RALL(a) a.rbegin(),a.rend()
#define rep(i,n) for(ll i=0; i<n; ++i)
#define print(a) cout << (a) << endl

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  ll n;cin>>n;
  string s;
  map<string,ll> mp;
  rep(i,n) {
    cin>>s;
    mp[s]++;
  }
  printf("AC x %lld\n",mp["AC"]);
  printf("WA x %lld\n",mp["WA"]);
  printf("TLE x %lld\n",mp["TLE"]);
  printf("RE x %lld",mp["RE"]);
  return 0;
}

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

#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define ll long long
#define pii pair<int,int>
#define all(x) begin(x), end(x)
#define loop(i,n) for(int i=0; i<n; i++)
#define rep(i,a,b,c) for(int i=a; i<b; i+=c)
#define brep(i,a,b,c) for(int i=a; i>b; i-=c)
#define tc(t) int t; cin>>t; while(t--)
#define sz(v) int((v).size())
#define pb push_back

const int maxm = 1000000000 + 7;

double startTime;
double getCurrentTime() {
	return ((double)clock() - startTime) / CLOCKS_PER_SEC;
}


using namespace std;



int main()
{

#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif

  int x;
   cin>>x;

   

   if(x>= 30)
   {
   	cout<<"Yes";
   }

   else
   {
   	cout<<"No";
   }


}

Measured memory_bytes: 3596
import java.io.IOException;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) throws IOException{
	Scanner sc	= new Scanner(System.in);
	
	String[] x = sc.next().split("");
	if(x[0].equals("9")){
		System.out.println("Yes");
	}else if(x[1].equals("9")){
		System.out.println("Yes");
	}else {
		System.out.println("No");
	}
	}
}

Measured memory_bytes: 21844
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <utility>
using namespace std;

#define REP(i, n) for(int i = 0; i < (int)(n); ++i)
#define FOR(i, m, n) for(int i = (int)(m); i < (int)(n); ++i)


long long solution(vector<pair<long long, long long>>& M, long long D, long long A){
    int N = M.size();
    // 左から見ていくために、座標の昇順でソート
    sort(M.begin(), M.end());

    long long ans = 0, carry = 0;
    queue<pair<long long, long long>> q;
    REP(i, N){
        long long X = M[i].first;
        long long H = M[i].second;
        // これまでの操作の範囲に含まれないものの効果を取り除く
        while(!q.empty() and q.front().first < X){
            carry -= A*q.front().second;
            q.pop();
        }
        H -= carry;
        if(H > 0){
            long long num = (H+A-1)/A;
            ans += num;
            carry += A*num;
            q.emplace(X+2*D, num);
        }
    }
    return ans;
}


/* Binary Indexed Tree (Fenwick Tree)
 * 数列 {v_n} に対して、
 * ・ v[i] += w
 * ・ sum(l,r) = v[l+1]+...+v[r]
 * の操作を O(logN) でしたいって時に使える
 * cf. http://hos.ac/slides/20140319_bit.pdf
 * 1-index と 0-index を使い分けること！ (0-index のsimpleじゃない方の実装怪しい)
 */
template <typename T=long long>
class BIT  
{
    private:
        int sz;  // 1, 2, ..., sz の index を管理
        vector<T> bit;  // BIT を保存する vector; 区間の右端で番号付け

    public:
        BIT(int N): sz(N), bit(N+1, 0) {};

        // v[idx] に w を足す
        void add(int idx, T w){
            // x&(-x) で x の最も下の立っているbit (=各BITが管理する長さ) が取り出せる
            // 自分の番号に自分の長さを足していくと自分が含まれている領域を全て尽くせる
            // for(int x = idx; x <= sz; x += x&(-x)) bit[x] += w;  // 1-index
            for(int x = idx+1; x <= sz; x += x&(-x)) bit[x] += w;  // 0-index simple
            // for(int x = idx; x < sz; x |= x+1) bit[x] += w;  // 0-index 
        }

        // v[1]+...+v[idx] を返す
        T sum(int idx){
            T ret = 0;
            // 区間和は、自分の番号から自分の区間の長さを引くと求まる
            // for(int x = idx; x > 0; x -= x&(-x)) ret += bit[x];  // 1-index
            for(int x = idx+1; x > 0; x -= x&(-x)) ret += bit[x];  // 0-index simple
            //for(int x = idx-1; x >= 0; x = (x&(x+1))-1) ret += bit[x];  // 0-index
            return ret;
        }
        
        // v[left+1]+...+v[right] を返す
        T sum(T left, T right){ return sum(right)-sum(left); }
};

long long solutionWithBIT(vector<pair<long long, long long>>& M, long long D, long long A){
    int N = M.size();
    sort(M.begin(), M.end());
    long long ans = 0;
    BIT<long long> bit(N+1);
    REP(i, N){
        long long X = M[i].first;
        long long H = M[i].second;

        H -= A*bit.sum(i);
        if(H <= 0) continue;
        long long num = (H+A-1)/A;
        ans += num;
        bit.add(i, num);
        int j = distance(M.begin(), lower_bound(M.begin(), M.end(), make_pair(X+2*D+1, (long long) -1)));
        bit.add(j, -num);
    }
    return ans;
}

int main()
{
    int N, D, A;
    cin >> N >> D >> A;
    vector<pair<long long, long long>> M(N);
    REP(i, N) cin >> M[i].first >> M[i].second;

    cout << solutionWithBIT(M, D, A) << endl;

    return 0;
}

Measured memory_bytes: 4992
n = int(input())
a = list(map(int, input().split()))
"""
４の倍数がn//2個以上
or
全部が２の倍数
"""

n2 = 0
n4 = 0

for _a in a:
    if _a%4 == 0:
        n4 += 1
    elif _a%2 == 0:
        n2 += 1

if n4 + n2//2 >= n//2:
    print("Yes")
else:
    print("No")

Measured memory_bytes: 15020
# -*- coding: utf-8 -*-
"""
Created on Sun Jan 19 20:52:57 2020

@author: over-
"""

N=int(input())
A=input().split()
A=[int(a) for a in A]

D=dict()

for a in A:
    if a not in D:
        D[a]=1
    else:
        D[a]+=1

ans=0
for d in D:
    ans+=D[d]*(D[d]-1)/2

for a in A:
    d=D[a]
    if d!=1: 
        add=(d-1)*(d-2)/2-d*(d-1)/2
    else:
        add=0
    print(int(ans+add))




Measured memory_bytes: 24748
#include <algorithm>
#include <cstdio>

int main() {
    int M, N;
    scanf(" %d%d", &N, &M);
    int a = 1, b = N;
    for (int i = 0; i < M; ++i) {
        int L, R;
        scanf(" %d%d", &L, &R);
        a = std::max(L, a);
        b = std::min(R, b);
    }
    printf("%d\n", std::max(b - a + 1, 0));
    return 0;
}


Measured memory_bytes: 128
//Radhe Radhe
#include<bits/stdc++.h>
#define ll long long
#define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define mod 1000000007
using namespace std;

int main()
{
    fast_io
    ll i,t,n,j,k,sum=0,cpn;
    string s;
    cin>>n;


    if(n%2==0)
        cout<<n<<endl;
    else
        cout<<n*2<<endl;

    return 0;
}





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

template <int MOD_>
struct modnum {
	static constexpr int MOD = MOD_;
	static_assert(MOD_ > 0, "MOD must be positive");
 
private:
	using ll = long long;
 
	int v;
 
	static int minv(int a, int m) {
		a %= m;
		assert(a);
		return a == 1 ? 1 : int(m - ll(minv(m, a)) * ll(m) / a);
	}
 
public:
 
	modnum() : v(0) {}
	modnum(ll v_) : v(int(v_ % MOD)) { if (v < 0) v += MOD; }
	explicit operator int() const { return v; }
	friend std::ostream& operator << (std::ostream& out, const modnum& n) { return out << int(n); }
	friend std::istream& operator >> (std::istream& in, modnum& n) { ll v_; in >> v_; n = modnum(v_); return in; }
 
	friend bool operator == (const modnum& a, const modnum& b) { return a.v == b.v; }
	friend bool operator != (const modnum& a, const modnum& b) { return a.v != b.v; }
 
	modnum inv() const {
		modnum res;
		res.v = minv(v, MOD);
		return res;
	}
	modnum neg() const {
		modnum res;
		res.v = v ? MOD-v : 0;
		return res;
	}
 
	modnum operator- () const {
		return neg();
	}
	modnum operator+ () const {
		return modnum(*this);
	}
 
	modnum& operator ++ () {
		v ++;
		if (v == MOD) v = 0;
		return *this;
	}
	modnum& operator -- () {
		if (v == 0) v = MOD;
		v --;
		return *this;
	}
	modnum& operator += (const modnum& o) {
		v += o.v;
		if (v >= MOD) v -= MOD;
		return *this;
	}
	modnum& operator -= (const modnum& o) {
		v -= o.v;
		if (v < 0) v += MOD;
		return *this;
	}
	modnum& operator *= (const modnum& o) {
		v = int(ll(v) * ll(o.v) % MOD);
		return *this;
	}
	modnum& operator /= (const modnum& o) {
		return *this *= o.inv();
	}
 
	friend modnum operator ++ (modnum& a, int) { modnum r = a; ++a; return r; }
	friend modnum operator -- (modnum& a, int) { modnum r = a; --a; return r; }
	friend modnum operator + (const modnum& a, const modnum& b) { return modnum(a) += b; }
	friend modnum operator - (const modnum& a, const modnum& b) { return modnum(a) -= b; }
	friend modnum operator * (const modnum& a, const modnum& b) { return modnum(a) *= b; }
	friend modnum operator / (const modnum& a, const modnum& b) { return modnum(a) /= b; }
};
using num = modnum<int(1e9) + 7>;

const int MAXN = 3010;
int N;
int Q;
int A[MAXN];

num prob[MAXN][MAXN];

int main() {
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> N >> Q;
	for (int i = 0; i < N; i++) {
		cin >> A[i];
	}

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			prob[i][j] = (A[i] < A[j]);
		}
	}
	for (int q = 0; q < Q; q++) {
		int x, y; cin >> x >> y; x--, y--;
		for (int i = 0; i < N; i++) {
			if (i == x || i == y) continue;
			prob[x][i] = prob[y][i] = (prob[x][i] + prob[y][i]) / 2;
			prob[i][x] = prob[i][y] = (prob[i][x] + prob[i][y]) / 2;
		}
		prob[x][y] = prob[y][x] = (prob[x][y] + prob[y][x]) / 2;
	}
	
	num ev = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < i; j++) {
			ev += prob[i][j];
		}
	}
	for (int q = 0; q < Q; q++) {
		ev *= 2;
	}
	cout << ev << '\n';

	return 0;
}


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

using ll = long long;
using ull = unsigned long long;

#define MOD 1000000007

int main(void) {
    ll N, M;
    ll ans = LONG_LONG_MIN;
    vector<tuple<ll, ll, ll>> S;
    cin >> N >> M;
    S.resize(N);
    for(ll i = 0;i < N;i++) cin >> get<0>(S[i]) >> get<1>(S[i]) >> get<2>(S[i]);
    for(ll i = 0;i < 8;i++) {
        ll a = 0;
        vector<ll> s;
        for(ll j = 0;j < N;j++) {
            ll t = 0;
            t += ((i & 1) ? 1 : -1) * get<0>(S[j]);
            t += ((i & 2) ? 1 : -1) * get<1>(S[j]);
            t += ((i & 4) ? 1 : -1) * get<2>(S[j]);
            s.push_back(t);
        }
        sort(s.begin(), s.end(), greater<>());
        for(ll j = 0;j < M;j++) a += s[j];
        ans = max(ans, a);
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(void){
    int h,r;
    cin >> h >> r;
    int d = h+r;
    if(d==0)cout << 0;
    else if(d<0)cout << -1;
    else if(d>0)cout << 1;
    cout << endl;
    return 0;
}


Measured memory_bytes: 3088
a,b,c = map(int,input().split())
cou = 0
while True:
  if a % 2 or b % 2 or c % 2:
    print(cou)
    exit()
  if a == b == c:
    print("-1")
    exit()
  co_a = b//2 + c//2
  co_b = a//2 + c//2
  co_c = a//2 + b//2
  a = co_a
  b = co_b
  c = co_c
  cou += 1


Measured memory_bytes: 3060
#include<stdio.h>

int main(void)
{
	int a,b,c,i,x=0;
	scanf("%d %d %d",&a,&b,&c);
	for(i=a;i<=b;i++)
	{
		if(c%i==0) x++;
	}
	printf("%d\n",x);

	return 0;
}


Measured memory_bytes: 596
#include <bits/stdc++.h>
#define fi first
#define se second
#define rep(i,s,n) for (int i = (s); i < (n); ++i)
#define rrep(i,n,g) for (int i = (n)-1; i >= (g); --i)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define len(x) (int)(x).size()
#define dup(x,y) (((x)+(y)-1)/(y))
#define append push_back
#define Field(T) vector<vector<T>>
using namespace std;
using ll = long long;
using P = pair<int,int>;

int f(int n) {
  if (n%2 == 0) return n/2;
  return 3*n+1;
}

int main() {
  int s;
  cin >> s;
  vector<bool> a(1000100,false);
  a[s] = true;
  int m = 1;
  while(true) {
    s = f(s);
    m++;
    if (a[s]) break;
    a[s] = true;
  }
  cout << m << endl;
  return 0;
}


Measured memory_bytes: 3712