akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define For(i, a, b) for(int (i)=(int)(a); (i)<(int)(b); ++(i))
#define rFor(i, a, b) for(int (i)=(int)(a)-1; (i)>=(int)(b); --(i))
#define rep(i, n) For((i), 0, (n))
#define rrep(i, n) rFor((i), (n), 0)
#define fi first
#define se second
using namespace std;
typedef long long lint;
typedef unsigned long long ulint;
typedef pair<int, int> pii;
typedef pair<int, lint> pil;
typedef pair<lint, int> pli;
typedef pair<lint, lint> pll;
template<class T> bool chmax(T &a, const T &b){if(a<b){a=b; return true;} return false;}
template<class T> bool chmin(T &a, const T &b){if(a>b){a=b; return true;} return false;}
template<class T> T div_floor(T a, T b){
    if(b < 0) a *= -1, b *= -1;
    return a>=0 ? a/b : (a+1)/b-1;
}
template<class T> T div_ceil(T a, T b){
    if(b < 0) a *= -1, b *= -1;
    return a>0 ? (a-1)/b+1 : a/b;
}

constexpr lint mod = 1e9+7;
constexpr lint INF = mod * mod;
constexpr int MAX = 100010;

int main(){
    int a[3][3];
    rep(i, 3)rep(j, 3) scanf("%d", &a[i][j]);
    int n;
    scanf("%d", &n);
    rep(i, n){
        int b;
        scanf("%d", &b);
        rep(j, 3)rep(k, 3)if(a[j][k] == b) a[j][k] = -1;
    }
    if(a[0][0]+a[1][1]+a[2][2] == -3){
        puts("Yes");
        return 0;
    }
    else if(a[0][2]+a[1][1]+a[2][0] == -3){
        puts("Yes");
        return 0;
    }
    else{
        rep(i, 3){
            if(a[i][0]+a[i][1]+a[i][2] == -3){
                puts("Yes");
                return 0;
            }
            if(a[0][i]+a[1][i]+a[2][i] == -3){
                puts("Yes");
                return 0;
            }
        }
    }
    puts("No");
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <tuple>
#include <numeric>

using namespace std;

typedef long long ll;

int main(void){
    ll a,b;
    cin >> a >> b;
    ll ans = 0;
    for(ll i = a;i <= b; i++){
        string tmp,f,l;
        l = "";
        f = to_string(i);
        tmp = to_string(i);
        for(ll j = tmp.size() - 1;j >= 0;j--){
            l = l + tmp[j];
        }
        if(f == l){
            ans++;
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
#include<cstdio>
#include<set>
#include<cstdlib>
#include<chrono>

using namespace std;

int d, c[100], s[400][100];
int sat;
int m, t[400];
set<int> app[100];

int last(int d, int i) {
  return *(--app[i].upper_bound(d));
}

int next(int d, int i) {
  return *app[i].upper_bound(d);
}

int random(int x, int y) {
  return rand() % (y - x + 1) + x;
}

int main() {
  scanf("%d", &d);
  for (int i = 1; i <= 26; i++) {
    scanf("%d", &c[i]);
    app[i].insert(0);
    app[i].insert(d+1);
  }
  for (int i = 1; i <= d; i++) {
    for (int j = 1; j <= 26; j++) {
      scanf("%d", &s[i][j]);
    }
  }
  for (int i = 1; i <= d; i++) {
    int best = -2e9, best_j = 0;
    for (int j = 1; j <= 26; j++) {
       int tmp = 0;
       tmp += s[j][t[j]];
       for (int k = 1; k <= 26; k++) {
         if (j == k) {
           continue;
         }
         tmp -= c[k] * (i - last(i, k));
       }
       if (tmp > best) {
         best = tmp;
         best_j = j;
       }
    }
    t[i] = best_j;
    sat += s[i][t[i]];
    app[t[i]].insert(i);
    for (int j = 1; j <= 26; j++) {
      sat -= c[j] * (i - last(i, j));
    }
  }
  auto start = chrono::steady_clock::now();
  auto end = chrono::steady_clock::now();
  while (chrono::duration_cast<chrono::nanoseconds>(end - start).count() < 1.9e9) {
    int d = random(1, ::d);
    int q = random(1, 26);
    while (q == t[d]) {
      q = random(1, 26);
    }
    app[t[d]].erase(d);
    int tmp = 0;
    tmp -= s[d][t[d]];
    tmp -= c[t[d]] * (next(d, t[d]) - d) * (d - last(d, t[d]));

    tmp += s[d][q];
    tmp += c[q] * (next(d, q) - d) * (d - last(d, q));
    if (tmp > 0) {
      app[q].insert(d);
      t[d] = q;
    } else {
      app[t[d]].insert(d);
    }
    end = chrono::steady_clock::now();
  }
  for (int i = 1; i <= d; i++) {
    printf("%d\n", t[i]);
  }
}


Measured memory_bytes: 3472
#include<bits/stdc++.h> 
#define LL long long
#define clr(x,i) memset(x,i,sizeof(x))
using namespace std;
const int N=300005;
int n,sum[2][N];
char s[N];
int main()
{
	scanf("%d%s",&n,s+1);
	for(int i=1;i<=n;i++){
		sum[0][i]=sum[0][i-1];
		sum[1][i]=sum[1][i-1];
		if(s[i]=='W') sum[0][i]++;
		else sum[1][i]++;
	}
	int ans=n+1;
	for(int i=1;i<=n;i++){
		ans=min(ans,sum[0][i-1]+sum[1][n]-sum[1][i]);
//		cout<<i<<' '<<sum[0][i-1]<<' '<<sum[1][n]-sum[1][i]<<endl;
	}
	printf("%d\n",ans);
	return 0;
}



Measured memory_bytes: 2944
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <utility>
#include <string>
#include <set>

using namespace std;


// Union-Find
class UnionFind {
private:
	// parents[i] >= 0 なら i の親
	// parents[i] < 0 で、根。abs(parents[i])がその木に属する頂点数
	vector<int> parents;
	int n_root;

public:
	UnionFind();
	UnionFind(int n) {
		parents.assign(n, -1);
		n_root = n;
	}
	~UnionFind() {
		parents.clear();
	};

	int find(int x) {
		if (parents[x] < 0) {
			return x;
		} else {
			return parents[x] = find(parents[x]);
		}
	}

	void unite(int x, int y) {
		x = find(x);
		y = find(y);

		if (x == y) {
			return;
		}

		if (size(x) < size(y)) {
			swap(x, y);
		}

		parents[x] += parents[y];
		parents[y] = x;
		n_root--;
		return ;
	}

	bool same(int x, int y) {
		return find(x) == find(y);
	}

	// xが属する集団のサイズ
	int size(int x) {
		return -parents[find(x)];
	}

	// いくつの集団があるか
	int get_n_root() {
		return n_root;
	}
};

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

	int x, y, z;
	UnionFind uf(n);

	set<int> known;
	for (int i = 0; i < m; i++) {
		cin >> x >> y >> z;
		x--;
		y--;

		uf.unite(x, y);

		if (x == y) {
			known.insert(x);
		}
	}

	set<int> known_root;
	for (auto a: known) {
		known_root.insert(uf.find(a));
	}

	int ans = uf.get_n_root() - known_root.size();
	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
const int maxn = 1e5 + 10;
LL n;
int main()
{
    scanf("%lld", &n);
    LL ans = 1000 * (n / 500);
    n %= 500;
    ans += 5 * (n / 5);
    printf("%lld", ans);
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  int a,b,c;
  cin >> a >> b >> c;
  int m=a;
  m=max(m,b);m=max(m,c);
  if(m==a) cout << a*10+b+c <<endl;
  else if(m==b) cout << b*10+a+c <<endl;
  else cout << c*10+a+b<<endl;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <boost/range/irange.hpp>
#include <boost/range/algorithm.hpp>
using namespace std;
using namespace boost::range;
using boost::irange;

using ll = int64_t;
constexpr char LN = '\n';
template<class T> bool chmax(T& a, const T& b) {if(a<b){a=b;return true;}else{return false;}}
template<class T> bool chmin(T& a, const T& b) {if(b<a){a=b;return true;}else{return false;}}

#ifdef LOCAL
template<class H> void dump_(const char* s, H h) {cout<<s<<"="<<h<<LN; }
template<class H, class... T> void dump_(const char* s, H h, T... t) {for(;*s!=',';++s){cout<<*s;}cout<<"="<<h<<",";dump_(++s,t...);}
#define dump(...) dump_(#__VA_ARGS__, __VA_ARGS__)
#else
#define dump(...)
#endif

struct init_ {init_(){ 
    cin.tie(nullptr); ios::sync_with_stdio(false);
    cout << fixed << setprecision(20);
}} init_;

template<class C> C scan(size_t n) {C c(n);for(auto& v:c){cin>>v;}return c;}
template<class C> C scan(size_t n, size_t m) {C vss(n);for(auto& vs:vss){vs.resize(m);for(auto& v:vs){cin>>v;}}return vss;}

template<class R> struct Joined { const R& r; const char* s; };
template<class R> Joined<R> joined(const R& r, const char* s = " ") {return{r,s};}
template<class R> ostream& operator<<(ostream& out, Joined<R> j) {bool f=true;for(const auto& v:j.r){if(f){f=false;}else{out<<j.s;}out<<v;}return out;}

template<class T> using matrix = vector<vector<T>>;
template<class T> matrix<T> make_matrix(size_t n, size_t m, const T& init = T()) {matrix<T> vss(n);for(auto& vs:vss){vs.resize(m,init);}return vss;}
template<class T> ostream& operator<<(ostream& out, Joined<matrix<T>> j) {bool a=true;for(const auto& vs:j.r){if(a){a=false;}else{out<<LN;}bool f=true;for(const auto& v:vs){if(f){f=false;}else{out<<j.s;}out << v;}}return out;}

ll comb(int n, int k) {
    if (n < k) {
        return 0;
    }
    if (n / 2 < k) {
        k = n - k;
    }
    ll ns = 1;
    ll ks = 1;
    while (k>0) {
        ns *= n--;
        ks *= k--;
    }
    return ns / ks;
}

int main() {
    int N;
    cin >> N;
    auto A = scan<vector<int>>(N);
    vector<ll> count(N+1);
    for (int a : A) {
        count[a]++;
    }
    ll sum = 0;
    for (ll c : count) {
        if (c != 0) {
            sum += c * (c - 1) / 2;
        }
    }
    for (int a : A) {
        cout << (sum - count[a] + 1) << LN;
    }
}


Measured memory_bytes: 4992
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
using namespace  std;
#define REP(i, n) for(long long (i)=0; (i)<(n); ++i)
#define ALL(a) (a).begin(),(a).end()

int EditDistanse(const string &s, const string &t){
    int N = s.size(), M = t.size();
    vector<vector<int>> dp(N+1, vector<int>(M+1, 0));
    dp[0][0] = 0;
    for(int i=1; i<=M; i++) dp[0][i] = dp[0][i-1] + 1;
    for(int i=1; i<=N; i++) dp[i][0] = dp[i-1][0] + 1;
    for(int i=0; i<N; i++){
        for(int j=0; j<M; j++){
            if(s[i]==t[j]){
                dp[i+1][j+1] = min({dp[i][j], dp[i+1][j]+1, dp[i][j+1]+1});
            }
            else{
                dp[i+1][j+1] = min({dp[i][j]+1, dp[i+1][j]+1, dp[i][j+1]+1});
            }
        }
    }
    return dp[N][M];
}
signed main(){
    string s, t;
    cin>>s>>t;
    cout << EditDistanse(s, t) << endl;
    return 0;
}


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

#define rep(i, n) for(long long i=0;i<(long long)(n);i++)
#define rep2(i, s, n) for(long long i=(s);i<(long long)(n);i++)
#define all(v) v.begin(), v.end()

using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;
using P = pair<ll, ll>;

const ll INF = (1LL<<60);

int main(){

    ll n; cin >> n;
    vll h(n);
    rep(i, n) cin >> h[i];

    for(ll i=n-2;i>=0;i--){
        if(h[i]>h[i+1]) h[i]--;
    }

    rep(i, n-1){
        if(h[i]>h[i+1]){
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;
    return 0;
}

Measured memory_bytes: 1024
# row = [int(x) for x in input().rstrip().split(" ")]
# n = int(input().rstrip())
# s = input().rstrip()

def resolve():
    import sys
    input = sys.stdin.readline

    n, a, b = [int(x) for x in input().rstrip().split(" ")]
    ans = 0
    for i in range(1, n+1):
        x = sum([int(c) for c in str(i)])
        if x >= a and x <= b:
            ans += i

    print(ans)


if __name__ == "__main__":
    resolve()


Measured memory_bytes: 73808
# -*- coding utf-8 -*-
N = int(input())
AN = list(map(int, input().split()))
BN = list(map(int, input().split()))

ans = 0

for i in range(N):
    c1 = AN[i] if BN[i] >= AN[i] else BN[i]
    BN[i] -= c1
    AN[i] -= c1

    c2 = AN[i + 1] if BN[i] >= AN[i + 1] else BN[i]
    BN[i] -= c2
    AN[i + 1] -= c2

    ans += c1 + c2

print(ans)


Measured memory_bytes: 18624
#include <iostream>
#include <string>//
#include <vector>//
#include <map>
#include <cstdlib>
#include <numeric>
#include <algorithm>//ソート等に使用
#include <iomanip>
#define _USE_MATH_DEFINES
#include <cmath>
#include <math.h>
#include <stdio.h>
#include <tuple>
#include <bitset>
#include <thread>///////////////////
#include <queue>//幅優先等のキュー
#include <stack>

#define rep(i,m,n) for(int i=(m);i<(n);i++)
#define mer(i,m,n) for(int i=(m);i>(n);--i)

#define MOD 1000000007
//#define MOD 998244353
#define MAX 

using namespace std;

using ll = long long int;
using ld = long double;
using std::swap;

vector<int> v;
vector<int> w;
vector<long long int> vll;
vector<long long int> wll;
//vector<vector<int>> vec(50, vector<int>(4, 0));
vector<vector<int>> vv;
vector<vector<int>> ww;



int main() {
	int N, K;
	int ans = 0;
	cin >> N >> K;
	v.resize(N);
	rep(i, 0, N) {
		cin >> v[i];
	}
	sort(v.begin(), v.end());
	rep(i, 0, K) {
		ans += v[i];
	}
	cout << ans << '\n';
	return 0;
}

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

using namespace std;
string S;

int main(void) {

	cin >> S;

	string y = S.substr(0, 4);
	string m = S.substr(5, 2);
	string d = S.substr(8, 2);

	string ans;

	if (y < "2019") {
		ans = "Heisei";
	}
	else if ((y == "2019") &&( m < "04")) { ans = "Heisei"; }
	else if ((y == "2019" )&& (m == "04") && (d <= "30")) { ans = "Heisei"; }
	else { ans = "TBD"; }

	cout << ans << endl;

	//system("pause");
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <cmath>
#include <cstdlib>
#include <queue>
#include <stack>
#include <iomanip>
#include <fstream>
#include <unordered_map>
#include <unordered_set>
#include <assert.h>
using namespace std;


#define REP(i, n) for(ll i = 0;i < n;i++)
#define REPR(i, n) for(ll i = n;i >= 0;i--)
#define FOR(i, m, n) for(ll i = m;i < n;i++)
#define FORR(i, m, n) for(ll i = m;i >= n;i--)
#define REPO(i, n) for(ll i = 1;i <= n;i++)
#define ll long long
#define INF (ll)1 << 60
#define MINF (-1 * INF)
#define ALL(n) n.begin(),n.end()
#define MOD 1000000007
#define P pair<ll, ll>


// test :::::::::::::::::::::::::::::
// aaaaaaaaaaaaaaaaaaaaa
/*
　　　　　　　　　　　　　　　　＿__.. -―‐- ..
　　　　　　　　　　　　　　　,. ､.. ::´: : :´: : : ,. ヘ: : :＼
　　　　　　　　　　　　　 ／: : :｀: : : : : : : : : : : : :＼: : ＼
　　　　　　　　　　　　 /: :／: : : : : : : :ヽ: : : : : : : : ヽ: : :ヽ
　　　　 　 　 　 　 　 /: /: : : : :/: : |: : : l: ＿＿: : : : ﾊ : : ﾊ
.　　　　　　 　 　 　 / /|: / : : :! : : |:!: : |´ﾚ!ル'ヽ人!: }: : : :l
*/
int main() {
	double n;
	cin >> n;
	double pi = 3.14;
	cout << n * 2 * pi << endl;
}

Measured memory_bytes: 3740
#include <iostream>
#include <string>
#include <algorithm>
#include <set>
#include <cmath>
#include <vector>

typedef long long ll;

using namespace std;

int main()
{
    ll n;

    cin >> n;

    vector<ll> d(n);

    for(ll i=0; i<n; ++i) 
        cin >> d[i];

    sort(d.begin(), d.end());

    ll i(0), j(n-1);
    while (1)
    {
        if (i >= j)
            break;

        i++, j--;
    }

    cout << d[i] - d[j] << endl;

    return 0;
}


Measured memory_bytes: 1024
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstring>
#include <string>
#include <cctype>
#include <sstream>
#include <cmath>
#include <climits>
#include <set>
#include <iostream>
#include <map>
#include <functional>

using namespace std;

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

typedef vector<int> vi;
typedef pair<int, int> pii;

int main()
{
	char str[16];
	while(scanf("%16s", str) != EOF){
		int a[10];
		rep(i, 10) a[i] = str[i] - '0';

		rep(i, 9){
			rep(j, 9-i){
				a[j] = (a[j] + a[j+1]) % 10;
			}
		}

		printf("%d\n", a[0]);
	}

	return 0;
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
#define rep(i, a, n) for(int i = a; i < n; i++)
#define repb(i, a, b) for(int i = a; i >= b; i--)
#define all(a) a.begin(), a.end()
#define o(a) cout << a << endl
#define int long long
#define fi first
#define se second
using namespace std;
typedef pair<int, int> P;

int dp[10010];

signed main(){
    int n;
    cin >> n;
    int d[110] = {};
    rep(i, 0, n) cin >> d[i];
    rep(i, 0, 10010) dp[i] = -1; 
    dp[0] = 0;
    rep(i, 0, n){
        repb(j, 10000, 0){
            if(j - d[i] >= 0 && dp[j - d[i]] != -1){
                dp[j] = 1;
            }
        }
    }
    int ans = 0;
    rep(i, 0, 10010) if(dp[i] == 1 && i % 10 != 0) ans = i;
    cout << ans << endl;
}

Measured memory_bytes: 384
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<cmath>
#include<cstdio>
#include<queue>
#include<deque>
#include<map>
#include<stack>
#include<set>
#include<utility>
using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
typedef pair<int,ll> p;
typedef pair<pii,int> P;
int dy[]={1,0,-1,0};
int dx[]={0,1,0,-1};
const int MAXN=100000;
const int MAXE=100000;
const int MAXV=10000;
const ll INF=2e18;
const ll MOD=1e9+7;
int gcd(int a,int b){
    if(b==0) return a;
    return gcd(b,a%b);
}
ll f(ll a,ll b){
    if(b==0) return -a;
    return 2*(a/b)*b+f(b,a%b);
}
int main(){
    ll n,x;cin>>n>>x;
    cout<<n+f(n-x,x)<<endl;
    return 0;
}

Measured memory_bytes: 3612
#include <stdio.h>
#include <math.h>
int main()
{
    int n;
    int ans = 0;
    int sn;
    scanf("%d", &n);
    sn = (int)sqrt((double)(n - 1));

    for (int i = 1; i <= sn; i++)
    {
        ans += 2 * ((n - 1) / i);
    }
    ans -= sn * (sn - 1);
    ans -= sn;
    printf("%d", ans);
    return 0;
}


Measured memory_bytes: 2180
#include <bits/stdc++.h>
#define DUMP(x)  cout << #x << " = " << (x) << endl;
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define IFOR(i, m, n) for(int i = n - 1; i >= m; i-- )
#define REP(i, n) FOR(i,0,n)
#define IREP(i, n) IFOR(i,0,n)
#define FOREACH(x,a) for(auto& (x) : (a) )
#define ALL(v) (v).begin(), (v).end()
using namespace std;
typedef long long ll;
const ll INF = 1e18;
/* テンプレートここまで */

int main() {
  ll a,b,c,x; cin >> a >> b >> c >> x;
  ll ans = 0;
  REP(i, a+1) REP(j, b+1) REP(k, c+1){
    if(500*i+100*j+50*k == x) ans++;
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
d,g = map(int,input().split())
num = [list(map(int,input().split())) for i in range(d)]
lis = []
for i in range(1<<d):
    ind = [l for l in range(d)]
    cntT = 0
    cntA = 0
    for j in range(d):
        if (i>>j) & 1 == 1:
            cntT += num[j][0]
            cntA += num[j][0]*(j+1)* 100 + num[j][1]
            ind[j] = -1
    if cntA < g:
        m = 100*(max(ind)+1)
        s = min((g-cntA + m -1)//m,num[max(ind)][0])
        cntA += s*m
        cntT += s
    if cntA >= g:
        lis.append(cntT)

print(min(lis))


Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define rep(i, n) for (ll i = 0; i < n; ++i)
typedef long long ll;
using namespace std;
const int MOD = 1e9 + 7;

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

    ll sum = 0;
    rep(i, n) sum += a[i];

    ll ans = 0;
    rep(i, n) {
        sum -= a[i];
        ans += sum % MOD * a[i] % MOD;
        ans %= MOD;
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 4848
h,w,d=map(int,input().split())
l=[[0,0]]+[[]for _ in range(h*w)]
for i in range(h):
    for j,a in enumerate(map(int,input().split())):
        l[a]=[i,j]
for i in range(h*w+1):
    if i<d:
        l[i].append(0)
    else:
        a,b=l[i]
        x,y,v=l[i-d]
        l[i].append(abs(x-a)+abs(y-b)+v)
for _ in range(int(input())):
    a,b=map(int,input().split())
    print(l[b][2]-l[a][2])

Measured memory_bytes: 71164
import java.util.Scanner;

class Main{
	int tiket[]={0,6000,4000,3000,2000};
	int t,n,uriage;
	
	public void solve(){
		Scanner sc=new Scanner(System.in);
		for(int i=1;i<=4;i++){
			t=sc.nextInt();
			n=sc.nextInt();
			uriage=tiket[t]*n;
			System.out.println(uriage);
			}
			}
			public static void main(String[]args){
				Main obj=new Main();
				obj.solve();
			}
}

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

#define trav(a, A) for (auto & a : A)
#define f first
#define s second

typedef long long ll;

ll MOD = 1e+9+7;
const ll INFLL = 0x3f3f3f3f3f3f3f3f;
const int INF = 0x3f3f3f3f;
const ll MAXN = 1e+5+7;

int main ()
{
	ios_base::sync_with_stdio (0);
	cin.tie (0);
	ll i, j, n, h, w, m;
	cin >> h >> w >> m;
	vector <ll> H (h), W (w);
	set <pair <ll, ll>> bomb;
	for (i = 0; i < m; ++i)
	{
		ll hi, wi;
		cin >> hi >> wi;
		--hi, --wi;
		++H[hi], ++W[wi];
		bomb.insert ({hi, wi});
	}
	pair <ll, ll> ans = {0, 0};
	for (i = 0; i < h; ++i)
		if (H[ans.f] < H[i]) ans.f = i;
	for (i = 0; i < w; ++i)
		if (W[ans.s] < W[i]) ans.s = i;
	if (bomb.find (ans) == bomb.end ())
	{
		cout << H[ans.f] + W[ans.s] << '\n';
		return 0;
	}
	vector <ll> Word (w), Hord (h);
	iota (Word.begin (), Word.end (), 0);
	iota (Hord.begin (), Hord.end (), 0);
	sort (Word.begin (), Word.end (), [&] (auto a, auto b)
		{ return W[a] < W[b]; });
	sort (Hord.begin (), Hord.end (), [&] (auto a, auto b)
		{ return H[a] < H[b]; });
	for (i = h - 1; i >= 0; --i)
	{
		if (i < h - 1 && H[Hord[i + 1]] > H[Hord[i]]) break;
		for (j = w - 1; j >= 0; --j)
		{
			if (j < w - 1 && W[Word[j + 1]] > W[Word[j]]) break;
			if (bomb.find ({Hord[i], Word[j]}) == bomb.end ())
			{
				cout << H[Hord[i]] + W[Word[j]] << '\n';
				return 0;
			}
		}
	}
	cout << H[ans.f] + W[ans.s] - 1 << '\n';

	return 0;
}



Measured memory_bytes: 31420
#include <iostream>
#include <string>
#include <sstream>
#include <iomanip> 
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <functional>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <complex>

using namespace std;

//#pragma GCC optimize("Ofast")
//#pragma GCC optimization("unroll-loops, no-stack-protector")
//#pragma GCC target("avx,avx2,fma")



// range query using segment tree
#define ISMAXRANGE	1		// 1 = max range, 0 = min range
#define VERYBIG		(1LL << 60)


class segment_tree {
	vector<long long> t;
	long size;
public:
	segment_tree(long n) {
		if (ISMAXRANGE) t.assign(4 * n + 1, 0);
		else t.assign(4 * n + 1, VERYBIG);
		size = n;
	}

	void initialize_array(vector<long long>& v) {
		initialize_with_array(1, 0, size - 1, v);
	}

	void initialize_with_array(long startpos, long l, long r, vector<long long>& v) {
		if (l == r) {
			t[startpos] = v[l];
		}
		else {
			long m = (l + r) / 2;
			initialize_with_array(2 * startpos, l, m, v);
			initialize_with_array(2 * startpos + 1, m + 1, r, v);

			if (ISMAXRANGE == 1) t[startpos] = max(t[startpos * 2], t[startpos * 2 + 1]);
			else  t[startpos] = min(t[startpos * 2], t[startpos * 2 + 1]);
		}
	}

	void update(long index, long long val) { // insert val into location index
		update_full(1, 0, size - 1, index, val);
	}

	void update_full(long startpos, long l, long r, long index, long long val) {
		if (l == r) {
			t[startpos] = val;
		}
		else {
			long m = (l + r) / 2;
			if (index <= m) update_full(2 * startpos, l, m, index, val);
			else update_full(2 * startpos + 1, m + 1, r, index, val);

			if (ISMAXRANGE) t[startpos] = max(t[startpos * 2], t[startpos * 2 + 1]);
			else t[startpos] = min(t[startpos * 2], t[startpos * 2 + 1]);
		}
	}

	long long query(long l, long r) {  // get range min/max between l and r
		if (l > r) {
			if (ISMAXRANGE) return 0;
			else return VERYBIG;
		}
		return query_full(1, 0, size - 1, l, r);
	}

	long long query_full(long startpos, long left, long right, long l, long r) {	 // left/right = current range, l/r = intended query range
		if ((left >= l) && (right <= r)) return t[startpos];
		long m = (left + right) / 2;
		long long ans;
		if (ISMAXRANGE) ans = -(1LL << 60);
		else ans = VERYBIG;
		if (m >= l) {
			if (ISMAXRANGE) ans = max(ans, query_full(startpos * 2, left, m, l, r));
			else ans = min(ans, query_full(startpos * 2, left, m, l, r));
		}
		if (m + 1 <= r) {
			if (ISMAXRANGE) ans = max(ans, query_full(startpos * 2 + 1, m + 1, right, l, r));
			else ans = min(ans, query_full(startpos * 2 + 1, m + 1, right, l, r));
		}
		return ans;
	}
};



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

	long long n, i, j, k, ans, x, MAXX = 300010, l, r;
	cin >> n >> k;
	vector<long long> a(n);
	for (i = 0; i < n; i++) cin >> a[i];

	segment_tree st(MAXX);
	ans = 0;

	for (i = 0; i < n; i++) {
		l = max(0LL, a[i] - k);
		r = min(MAXX - 1, a[i] + k);

		x = st.query(l, r) + 1;
		ans = max(ans, x);
		st.update(a[i], x);
	}

	cout << ans << "\n";



	return 0;
}




Measured memory_bytes: 15008
#include <bits/stdc++.h>
using namespace std;
int main()
{
  int a, b, x;
  cin >> a >> b >> x;

  string s = "NO";
  for (int i = 0; i < x; i++) {
    if (a + b >= x && a <= x) {
      s = "YES";
    }
  }

  cout << s << endl;

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define pb          emplace_back
#define ll          long long
#define fi          first
#define se          second
#define mp          make_pair
 
using namespace std;
 
const int N = int(2e3) + 7;
const int mod = int(1e9) + 7;
typedef pair<int, int> pii;
 
int n, a, b, c, d, f[N][N], fac[N], rev[N];
 
void add(int& x, int y) {if((x += y) >= mod) x -= mod;}
int mul(int x, int y) {return 1ll * x * y % mod;}
 
int Pow(int x, int y) {
   int res = 1;
   for(; y > 0; y >>= 1) {
       if(y & 1) res = mul(res, x);
       x = mul(x, x);
   }
   return res;
}
 
int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    #define Task        "test"
    if(fopen(Task".inp", "r")) {
        freopen(Task".inp", "r", stdin);
        freopen(Task".out", "w", stdout);
    }
    cin >> n >> a >> b >> c >> d;
    fac[0] = 1;
    for(int i = 1; i <= n; ++i) fac[i] = mul(fac[i - 1], i);
    rev[n] = Pow(fac[n], mod - 2);
    for(int i = n - 1; i >= 0; --i) rev[i] = mul(rev[i + 1], i + 1);
    for(int i = 0; i <= b; ++i) f[0][i] = 1;
    for(int i = 1; i <= n; ++i) {
       for(int j = a; j <= b; ++j) {
          for(int k = c; i - k * j >= 0 && k <= d; ++k)
             add(f[i][j], mul(f[i - k * j][j - 1], mul(Pow(rev[j], k), rev[k])));
          add(f[i][j], f[i][j - 1]);
          //cout << f[i][j] << ' ';
       }
       //cout << '\n';
    }
    cout << mul(f[n][b], fac[n]);
}

Measured memory_bytes: 8448
n,m=map(int,input().split())
H=list(map(int,input().split()))


visited=[1]*n
for _ in range(m):
    a,b=map(int,input().split())
    a-=1
    b-=1
    if H[a]>H[b]:
        visited[b]=0
    elif H[b]>H[a]:
        visited[a]=0
    else:
        visited[a]=visited[b]=0   

print(sum(visited)) 

Measured memory_bytes: 20112
#include<bits/stdc++.h>
#pragma GCC target ("avx2")
#pragma GCC optimization ("03")
#pragma GCC optimization ("unroll-loops")
using namespace std;

const int maxn = 1;
const int maxe = 20;
int n,m,a[maxn],c=0,k,pa[maxn];
double f=0;
int st[maxn][maxe];

void build(int n){
    for(int j=1;(1<<j)<=n;j++){
        for(int i=1;i+(1<<j)-1<=n;i++){
            st[i][j] = min(st[i][j-1], st[i+(1<<(j-1))][j-1]);
        }
    }
}

int query(int a, int b){
    int k = 31- __builtin_clz(b-a+1);
    return min(st[a][k], st[b-(1<<k)+1][k]);
}

int find(int i)
{
    if(pa[i]==i)return i;
    return pa[i]=find(pa[i]);
}

int bs(int l,int r,int x)
{
    while(l!=r)
    {
        int mi=(l+r)/2;
        if(a[mi]>x)r=mi;
        else l=mi+1;
    }
}

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

    cin>>n>>m;
    for(int i=1;i<=n;i++){
    cin>>k;
    if(k>=m)c++;
    }
    cout<<c;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long
using namespace std;
template<typename T>inline void read(T &x){
	int p=1;x=0;char c=getchar();
	while(!isdigit(c)){
		if(c=='-')p=-1;
		c=getchar();
	}
	while(isdigit(c)){
		x=(x<<3)+(x<<1)+(c^'0');
		c=getchar();
	}
	x*=p;
}
int n,d,x;
int a[101];
int p[101];
int main(){
	read(n),read(d),read(x);
	for(register  int i=1;i<=n;++i){
		read(a[i]);
		for(register int j=0;a[i]*j<=d;++j){
			p[a[i]*j+1]++;
			if(a[i]*j>=d)break;
		}
	}
	for(register int i=d;i>=1;--i)
		x+=p[i];
	cout<<x<<endl;
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <functional>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <numeric>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cctype>
#include <sstream>

#define rep(i, a) REP(i, 0, a)
#define REP(i, a, b) for(int i = a; i < b; ++i)
#define rrep(i, a) RREP(i, a, 0)
#define RREP(i, a, b) for(int i = a; i >= b; --i)
#define repll(i, a) REPLL(i, 0, a)
#define REPLL(i, a, b) for(ll i = a; i < b; ++i)
#define rrepll(i, a) RREPLL(i, a, 0)
#define RREPLL(i, a, b) for(ll i = a; i >= b; --i)

typedef long long ll;
typedef unsigned long long ull;
typedef std::pair<int, int> P;
typedef std::pair<int, P> PP;
const double PI = 3.14159265358979323846;
const double esp = 1e-9;
const int infi = (int)1e+9 + 10;
const ll infll = (ll)1e+17 + 10;

int n, t, e;

int main() {
	std::cin >> n >> t >> e;
	rep(i, n) {
		int x;
		std::cin >> x;
		int k = t / x;
		if (t - k * x <= e || (k + 1) * x - t <= e) {
			std::cout << i + 1 << std::endl;
			goto end;
		}
	}
	std::cout << -1 << std::endl;
end:;
	return 0;
}

Measured memory_bytes: 1164
#include <iostream>
#include <cmath>
#define MAX 1000000
using namespace std;

void eratos(int,bool*);

main(){
  bool prime[MAX+1];
  eratos(MAX, prime);

  while(1){
    int a, d, n;
    cin >> a >> d >> n;
    if(a==0 && d==0 && n==0) break;
    int count=0;
    for(int i=a;i<=MAX;i+=d){
      if(prime[i]){
	count++;
      }
      if(n==count){
	cout << i << endl;
	break;
      }
    }
  }
  return 0;
}

void eratos(int n, bool prime[]){
  for(int i=0;i<=n;i++) prime[i]=false;
  for(int i=3;i<=n;i+=2) prime[i]=true;
  prime[2]=true;
  int limit=(int)sqrt((double)n)+1;
  for(int i=3;i<=limit;i+=2){
    if(!prime[i]) continue;
    for(int j=i+i;j<=n;j+=i) prime[j]=false;
  }
}

Measured memory_bytes: 0
/*
    Author:zeke
    
    pass System Test!
    GET AC!!
*/
#include <iostream>
#include <queue>
#include <vector>
#include <iostream>
#include <vector>
#include <string>
#include <cassert>
#include <algorithm>
#include <functional>
#include <cmath>
#include <queue>
#include <set>
#include <stack>
#include <deque>
#include <map>
#include <iomanip>
#include <utility>
#include <stack>
#include <bitset>
using ll = long long;
using ld = long double;
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(), (x).end()
#define rep3(var, min, max) for (ll(var) = (min); (var) < (max); ++(var))
#define repi3(var, min, max) for (ll(var) = (max)-1; (var) + 1 > (min); --(var))
#define Mp(a, b) make_pair((a), (b))
#define F first
#define S second
#define Icin(s) \
    ll(s);      \
    cin >> (s);
#define Scin(s) \
    ll(s);      \
    cin >> (s);
template <class T>
bool chmax(T &a, const T &b)
{
    if (a < b)
    {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
bool chmin(T &a, const T &b)
{
    if (b < a)
    {
        a = b;
        return 1;
    }
    return 0;
}
typedef pair<ll, ll> P;
typedef vector<ll> V;
typedef vector<V> VV;
typedef vector<P> VP;
ll mod = 1e9 + 7;
ll MOD = 1e9 + 7;
ll INF = 1e18;

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    string s;
    cin >> s;
    ll k;
    cin >> k;
    set<string> temp;
    rep(i,s.size()){
        for (int j = 1; i + j <= s.size()&&j<=k;j++){
            temp.insert(s.substr(i,j));
        }
    }
    vector<string> res;
    for(auto itr=temp.begin();itr!=temp.end();itr++){
        res.push_back(*itr);
    }
    cout << res[k-1] << endl;
}


Measured memory_bytes: 1920
import math
def prime(x):
  p = {}
  cnt = 2
  Flag = True
  while Flag:
    last = math.ceil(x ** 0.5) 
    if cnt > last:
      break
    for i in range(cnt, last + 1):
      if x % i == 0:
        x //= i
        p[i] = 1
        cnt = i + 2
        while x % i == 0:
          x //= i
          p[i] += 1
        cnt = i + 1
        break
      if i == last:
        Flag = False
  if x != 1:
    p[x] = 1
  return p

N, K = list(map(int, input().split()))
A = list(map(int, input().split()))

x = sum(A)

tL = prime(x)
L = [1]
for k, v in tL.items():
  t = len(L)
  n = k
  for i in range(v):
    for j in range(t):
      L.append(L[j] * n)
    n *= k

L.sort(reverse = True)

for i in L:
  M = [j % i for j in A]
  M.sort()
  f = True
  c = 0
  for k in M:
    if f:
      if c + k <= K:
        c += k
      else:
        f = False
        c = (i - k)
    else:
      if c + (i - k) <= K:
        c += (i - k)
      else:
        break
  else:
    print(i)
    break


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

int n, a[300];

int main(){
  cin >> n;
  rep(i, n) cin >> a[i];
  int res = 100000000;
  for(int y = -100; y <= 100; y++){
    int sum = 0;
    rep(i, n){
      int cost = abs(a[i] - y);
      cost = pow(cost, 2);
      sum += cost;
    }
    res = min(sum, res);
  }
  cout << res << endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vvvll = vector<vvll>;
using vs = vector<string>;
using pll = pair<ll, ll>;
using vp = vector<pll>;
#define rep(i, n) for (ll i = 0; i < (n); i++)
#define repr(i, a, b) for (ll i = (a); i < (b); i++)
#define ALL(a) (a).begin(), (a).end()
#define SZ(x) ((ll)(x).size())
#define PRINT(V) for (auto v:(V)) {cerr << v << " ";} cerr << endl
#define dump(x) cerr << #x << " : " << (x) << endl
#define dump2(x, y) cerr << "(" << #x << ", " << #y << ") = (" << x << ", " << y << ")" << endl
const ll MOD = 1000000007;
const ll INF = 100000000000000000LL;
inline ll GCD(ll a, ll b){return b ? GCD(b, a % b) : a;}
inline ll LCM(ll a, ll b){return a / GCD(a, b) * b;}
inline ll powint(ll x, ll y){ll r=1;while(y){if(y&1)r*=x;x*=x;y>>=1;}return r;}
inline ll powmod(ll x, ll y, ll m = MOD){ll r=1;while(y){if(y&1)r*=x;x*=x;r%=m;x%=m;y>>=1;}return r;}
/* END OF TEMPLATE */

int main(){
    cin.tie(0); ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    ll n;
    cin >> n;
    vll a(n);
    rep(i, n){
        cin >> a[i];
    }
    ll hs = accumulate(ALL(a), 0LL)/2;
    vll pso(n, 0), psob(n, 0), pse(n, 0), pseb(n, 0);
    ll c = 0;
    for(ll i = 0; i < n; i += 2){
        c += a[i];
        pso[i] = c;
    }
    c = 0;
    for(ll i = 1; i < n; i += 2){
        c += a[i];
        pse[i] = c;
    }
    c = 0;
    for(ll i = n-1; i >= 0; i -= 2){
        c += a[i];
        psob[i] = c;
    }
    c = 0;
    for(ll i = n-2; i >= 0; i -= 2){
        c += a[i];
        pseb[i] = c;
    }
    rep(i, n){
        if(i == 0) cout << 2*(hs-pseb[1]);
        else if(i == 1) cout << 2*(hs-psob[2]);
        else if(i == n-1) cout << 2*(hs-pso[i-2]);
        //else if(i == n-2) cout << 2*(hs-pse[i-2]);
        else if(i%2) cout << 2*(hs-pse[i-2]-psob[i+1]);
        else cout << 2*(hs-pso[i-2]-pseb[i+1]);
        if(i < n-1) cout << " ";
    }
    cout << endl;
    return 0;
}

Measured memory_bytes: 5248
const t={input:require('fs').readFileSync('/dev/stdin','utf8').split(/[\s]/),n:(arg:number=0):any=>{if(arg){const a=[];for(let i=0;i<arg;i++){a.push(t.n())}return a}else{const a=t.input[0];t.input.shift();return Number(a)}},s:(arg:number=0):any=>{if(arg){const a=[];for(let i=0;i<arg;i++){a.push(t.s())}return a}else{const a=t.input[0];t.input.shift();return String(a)}},c:(arg:number=0):any=>{if(arg){const a=[];for(let i=0;i<arg;i++){a.push(t.c())}return a}else{let a=t.input[0].split('');const b=a[0];a.shift();if(a.length>0){t.input[0]=a.join('')}else{t.input.shift()}return String(b)}},o:(...arg)=>{console.log(...arg)},abs:(a)=>{return Math.abs(a)},min:(...a)=>{return Math.min(...a)},max:(...a)=>{return Math.max(...a)},floor:(a)=>{return Math.floor(a)},asc:(ar:number[])=>{return ar.sort((a,b)=>{return a-b})},desc:(ar:number[])=>{return ar.sort((a,b)=>{return b-a})},sw:(a,arr:any[],op:'=='|'>='|'>'|'<='|'<'='==')=>{for(let i=0;i<arr.length;i+=2){if(eval(a+op+arr[i]))return arr[i+1];}return arr[arr.length-1]}};
const main=()=>{
  let s=t.s().split('');
  let ans='Yes'
  for(let i=0;i<s.length; i++){
    if(i%2==0&&s[i]=='L'){
      ans='No'
      break;
    }else if(i%2!=0&&s[i]=='R'){
      ans='No'
      break;
    }
  }
  t.o(ans)
}
main()

Measured memory_bytes: 7372
#include<bits/stdc++.h>
#define _ ios_base::sync_with_stdio(0);
#define endl "\n"
#define MAXN 100123
#define ll long long
#define INF INT_MAX
#define FORE(i,m,n) for(int i=0;i<n;i++)
#define FOR(i,n) FORE(i,0,n)
#define ii pair<int,int>
#define vi vector<int>
#define vii vector<ii>
#define ps(v) push_back(v)
#define ms(v,x) memset(v,x,sizeof(v)) 
using namespace std;

int n,t;

int main(){_
    cin >> n;
    cout << fixed << setprecision(20);
    cout << 2*M_PI*n << endl;
    return 0;
}

Measured memory_bytes: 3804
n = int(input())
A =list(map(int, input().split()))
mod = 10**9+7

d = {}
for i in range(n+1):
    if A[i] not in d:
        d[A[i]] = i
    else:
        l = d[A[i]]
        r = i
        break
#print(l, r)

def cmb1(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
N = 10**6
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

for k in range(1, n+2):
    ans = cmb1(n+1, k, mod) - cmb1(l+n-r, k-1, mod)
    print(ans%mod)


Measured memory_bytes: 142552
chomp (my ($n, $p) = split / /, <STDIN>);
my %h;

if ($p==1) {
  print "1\n";
} elsif ($n==1) {
  print "$p\n";
} else {
  factorization($p);
  my $ans = 1;
  for my $k (keys %h) {
    my $v = $h{$k};
    while ($v >= $n) {
      $ans *= $k;
      $v -= $n;
    }
  }
  print "$ans\n";
}
sub factorization {
  my $arg = shift;
  while ($arg % 2 == 0) {
    $h{2}++;
    $arg /= 2;
  }
  for my $i (3..sqrt($arg)) {
    if ($arg % $i == 0) {
      $h{$i}++;
      return ($i, factorization($arg / $i));
    }
  }
  $h{$arg}++ if $arg > 0;
}

Measured memory_bytes: 512
#include<iostream>
#include<vector>
#include<string>
#include<deque>
#include<unordered_map>
#include<unordered_set>
#include<queue>
#include<algorithm>
#include<cmath>
#include<numeric>
using namespace std;
typedef long long LL;

const int MOD = 1e9+7;


class BIT{
public:
    vector<int> table;
    BIT(int n){
        table = vector<int>(n+1,0);        
    }
    int query(int x){
        int ans = 0;
        while(x){
            ans += table[x];
            x-=lowbit(x);
        }
        return ans;
    }
    void update(int x,int val){
        if(x==0) return;
        int n = table.size()-1;
        while(x<=n){
            table[x]+=val;
            x+=lowbit(x);
        }
    }
    int lowbit(int x){
        return x &(-x);
    }
};
void solve(){
    int n,d,a;
    cin>>n>>d>>a;
    vector<vector<int>> table(n,vector<int>(2,0));
    for(int i=0;i<n;i++) cin>>table[i][0]>>table[i][1];
    sort(table.begin(),table.end(),
        [](vector<int>&a,vector<int> &b){
        return a[0]<b[0];
    });
    LL ans = 0;
    BIT tree(n);
    for(int i=0;i<n;i++){
        auto tsum = tree.query(n);
        tsum-=tree.query(i);
        if(1ll * tsum * a >=table[i][1]) continue;
        int l = i;
        int r = n;
        LL threshold = table[i][0]+2ll * d;
        while(l<r){
            int m = (l+r)/2;
            if(table[m][0]>threshold) r = m;
            else l=m+1;
        }
        l--;
        tsum = table[i][1]-tsum*a;
        int cnt = (tsum-1)/a+1;
        ans+=cnt;
        tree.update(i,-cnt);
        tree.update(l+1,cnt);
    }
    cout<<ans<<endl;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T = 1;
    // cin>>T;
    while(T--){
        solve();
    }
    return 0;
}



Measured memory_bytes: 12032
#include<bits/stdc++.h>
#define range(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,b) for(int i = 0; i < (b); i++)
#define all(a) (a).begin(), (a).end()
#define show(x)  cerr << #x << " = " << (x) << endl;
//const int INF = 1e8;
using namespace std;

class KnuthMorrisPratt{
	public:
		vector<int> fail;
		string t; // 探す文字列
		KnuthMorrisPratt(string& t) {
			this->t = t;
			int m = t.size();
			fail = vector<int>(m + 1);
			int j = fail[0] = -1;
			for (int i = 1; i <= m; ++i) {
				while (j >= 0 && t[j] != t[i - 1]) j = fail[j];
				fail[i] = ++j;
			}
		}
		vector<int> match(string& s){
			int n = s.size(), m = t.size();
			vector<int> res;
			for (int i = 0, k = 0; i < n; ++i) {
				while (k >= 0 && t[k] != s[i]) k = fail[k];
				if (++k >= m) {
					res.emplace_back(i - m + 1); // match at s[i-m+1 .. i]
					k = fail[k];
				}
			}
			return res;
		}
};

int main(){
	string s, t;
	cin >> s >> t;
	KnuthMorrisPratt kmp(t);
	for(auto i : kmp.match(s)){
		cout << i << endl;
	}
}



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

using namespace std;

using ll = long long;

const long long MOD = 1e9 + 7;
const int INF = 1e9 + 7;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    cin >> N;
    vector<int> rate(9, 0);
    for (int i = 0; i < N; ++i) {
        int a;
        cin >> a;
        int r = min(a / 400, 8);
        rate[r]++;
    }
    int mi = 0, ma = 0;
    for (int i = 0; i < 8; ++i) if (rate[i] > 0) mi++;
    ma = mi + rate[8];
    if (mi == 0) mi = 1;
    cout << mi << " " << ma << endl;
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
void call(int n){
  int i = 1;
 CHECK_NUM:
  int x = i;
  if ( x % 3 == 0 ){
    cout << " " << i;
    goto END_CHECK_NUM;
  }
 INCLUDE3:
  if ( x % 10 == 3 ){
    cout << " " << i;
    goto END_CHECK_NUM;
  }
  x /= 10;
  if ( x ) goto INCLUDE3;
 END_CHECK_NUM:
  if ( ++i <= n ) goto CHECK_NUM;

  cout << endl;
}
int main(){
	int x;
	while(cin>>x){
		call(x);
	}
	return 0;
} 


Measured memory_bytes: 3100
#include <bits/stdc++.h>
#define pi 3.14159
using namespace std;

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

Measured memory_bytes: 3576
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rrep(i, n) for (int i = (n - 1); i >= 0; i--)
#define ALL(v) v.begin(), v.end()
using namespace std;
using P = pair<int, int>;
typedef long long ll;
bool ok = true;

void dfs(int h, int w, vector<string> &tmp) {
  for (int j = 1; j < 8; j++){
    if (h + j < 8 && w + j < 8 && tmp[h + j][w + j] == 'Q'){
      ok = false;
      return;
    }
    if (h + j < 8 && w - j >= 0 && tmp[h + j][w - j] == 'Q'){
      ok = false;
      return;
    }
    if (h - j >= 0 && w + j < 8 && tmp[h - j][w + j] == 'Q'){
      ok = false;
      return;
    }
    if (h - j >= 0 && w - j >= 0 && tmp[h - j][w - j] == 'Q'){
      ok = false;
      return;
    }
  }
  return;
}

int main() {
  int k;
  cin >> k;
  vector<int> used_row(8, -1);
  vector<int> a(8);
  vector<string> grid(8, "........");
  rep(i, k) {
    int x, y;
    cin >> x >> y;
    grid[x][y] = 'Q';
    used_row[x] = y;
  }
  rep(i, 8) a[i] = i;
  sort(ALL(a));
  do{
    ok = true;
    vector<string> tmp = grid;
    vector<int> Q;
    rep(i, 8) {
      if(used_row[i] != -1 && used_row[i] != a[i]){
        ok = false;
        break;
      }
      tmp[i][a[i]] = 'Q';
      Q.emplace_back(a[i]);
    }
    rep(i, 8) {
      if(!ok)break;
      dfs(i, Q[i], tmp);
    }
    if(ok){
      rep(i, 8) {
        cout << tmp[i] << endl;
      }
      return 0;
    }
  } while (next_permutation(a.begin(),a .end()));
  
}


Measured memory_bytes: 3244
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#define il inline
#define re register
#define fo(i,j,k) for(register int i=j;i<=k;i++)
#define do(i,j,k) for(register int i=j;i>=k;i--) 
#define inf 0x7fffffff
typedef long long ll;
using namespace std;
il ll read()
{
	ll x=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
	while(c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
	return f*x;	
}
/*int h[200010],v[200010],dis[200010];
struct edge
{
	int v,w,next;
}e[200010*2];
il void add(int u,int v,int w)
{
	e[++cnt].v=v;
	e[cnt].w=w;
	e[cnt].next=h[u];
	h[u]=cnt;
}*/
ll n,k,ans;
ll dp[100010];
const ll mod=1e9+7;
ll cal(ll a,ll b)
{
    ll ret=1;
    while(b)
    {
        if(b&1) ret=(ret*a)%mod;
        a=(a*a)%mod;
        b>>=1LL;
    }
    return ret;
}
int main()
{
    n=read(),k=read();
    for(re ll i=k;i>=1;i--)
    {
        ll num=k/i;
        dp[i]=cal(num,n);
        for(ll j=2*i;j<=k;j+=i)
        {
            dp[i]=(dp[i]-dp[j]+mod)%mod;
        }
        ans=(ans+dp[i]*i)%mod;
    }
    printf("%lld\n",ans);
}

Measured memory_bytes: 4548
#include <bits/stdc++.h>
using namespace std;
/* typedef */
typedef long long ll;
typedef pair<int, int> pii;
/* constant */
const int INF = 1 << 30;
const ll LINF = 1LL << 50;
const int NIL = -1;
const int MAX = 200001;
const int mod = 1000000007;
const double pi = 3.141592653589;
/* global variables */
vector<vector<int> > divs(MAX, vector<int>());
/* function */
void divisor() {
    for (ll i = 1; i < MAX; i++) {
        for (ll j = 1; j * j <= i; j++) {
            if (i % j == 0) {
                divs[i].push_back(j);
                if (j * j != i) divs[i].push_back(i / j);
            }
        }
    }
}
/* main */
int main(){
    int N;
    cin >> N;
    vector<int> a(N + 1), cnt(N + 1);
    for (int i = 1; i <= N; i++) cin >> a[i];
    divisor();
    vector<int> ret;
    for (int i = N; i >= 1; i--) {
        if (cnt[i] % 2 == a[i]) continue;
        ret.push_back(i);
        for (int d : divs[i]) { cnt[d]++; }
    }
    cout << ret.size() << '\n';
    if (ret.size() != 0) {
        sort(ret.begin(), ret.end());
        for (int i = 0; i < ret.size(); i++) {
            cout << ret[i] << ((i != (ret.size() - 1)) ? ' ' : '\n');
        }
    }
}


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

#define Rep(i, n) for (int i = 1; i <= n; i ++)
#define Rep0(i, n) for (int i = 0; i <= n; i ++)

using namespace std;

int a[100010];

int main()
{
	int n, m;
	scanf("%d%d", &n, &m);
	int t1 = 0, t2 = 0;
	Rep(i, m){
		scanf("%d", &a[i]);
		if (a[i] & 1){
			if (!t1) t1 = i;
			else if (!t2) t2 = i;
			else {printf("Impossible\n"); return 0;}
		}
	}
	if (t1) swap(a[1], a[t1]); 
	if (t2) swap(a[m], a[t2]);
	Rep(i, m) printf("%d ", a[i]);
	printf("\n");
	if (m == 1) {
		if (a[1] == 1) printf("1\n1\n");
		else {
			printf("2\n");
			printf("1 %d\n", a[1] - 1);
		}
		return 0;
	}
	a[1] --, a[m] ++;
	if (a[1]) printf("%d\n", m);
	else printf("%d\n", m - 1);
	Rep(i, m) if (a[i]) printf("%d ", a[i]);
	
	
	return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <vector>

using namespace std;

const long long int MOD=1e9+7;

int main() {
    int N, M;
    cin >> N >> M;
    
    vector<long long int> memo(N+1, 0);
    memo[0]=1;
    for(int m=0; m<M; m++) {
        int a;
        cin >> a;
        memo[a]=-1;
    }
    for(int n=0; n<N+1; n++) {
        if(memo[n]==-1) continue;
        for(int i=n+1; (i<n+3 && i<N+1); i++) {
            if(memo[i]==-1) continue;
            memo[i] += memo[n];
            memo[i] %= MOD;
        }
    }
    cout << memo[N] << endl;


    return 0;
    
}

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

int main() {
  ll A, B, C;
  cin >> A >> B >> C;
  if (A%2 == 0 || B%2 == 0 || C%2 == 0) {
    cout << 0 << endl;
  }
  else {
    cout << min({A*B, B*C, A*C}) << endl;
  }
}


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



int main() {

	
	long N;
	long A;
	long B;
	long res;

	cin >> N;
	cin >> A;
	cin >> B;

	res = (N / (A + B))*A;

	if ((N % (A + B) > A)) res += A;
	else res += N % (A + B);


	cout << res << endl;

	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <numeric>
#include <vector>
#include <math.h>
#include <map>
#include <algorithm>
#include <stdio.h>
#include <set>
#define mod 1000000007
using namespace std; 

int main(){
	int n,m;
	cin >> n >> m;
	cout << n*(n-1)/2+m*(m-1)/2 << "\n";
}


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

using namespace std;
typedef long long ll;
const ll INF = 1e17;
struct edge{ll from,to,cost;};

vector<edge> v;

int main(){
    ll n,m,p;
    cin >> n >> m >>p;
    v.resize(m);
    ll i,j,k;
    for(i=0;i<m;i++){
        ll from,to,cost;
        cin >> from >> to >> cost;
        cost-=p;
        edge e;
        e.from = from,e.to=to,e.cost=-cost;
        v[i]=e;
    }

    ll d[n+1];
    ll ret = 0;
    for(i=0;i<=n+1;i++)d[i]=INF;
    d[1]=0;
    for(i=0;i<=2*n+1;i++){
        for(j=0;j<m;j++){
            edge e = v[j];
            if(d[e.to]>d[e.from]+e.cost){
                d[e.to] = d[e.from] + e.cost;
            }
        }
        if(i == n) {
            ret = d[n];
        }
    }
    if(d[n] != ret) {
        cout << -1 << endl;
        return 0;
    }
    cout << max(0LL,-ret) << endl;
    return 0;
}

Measured memory_bytes: 384