akhauriyash/Code-Regression huggingface dataset:
#define _CRT_SECURE_NO_WARNINGS

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <cstring>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <list>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <unordered_set>
#include <unordered_map>
#include <array>
#include <cassert>
#include <bitset>
using namespace std;
using LL = long long;

int main() {
	string s, t;
	while (cin >> s, (s != ".")) {
		cin >> t;
		if (s == t) {
			cout << "IDENTICAL" << endl;
			continue;
		}
		vector<int>P, Q;
		for (int i = 0; i < s.size(); ++i) {
			if (s[i] == '\"')P.push_back(i);
		}
		for (int i = 0; i < t.size(); ++i) {
			if (t[i] == '\"')Q.push_back(i);
		}
		if (P.size() != Q.size()) {
			cout << "DIFFERENT" << endl;
			continue;
		}
		bool ok = false;
		for (int a = 0; a < P.size(); a += 2) {
			int p1 = P[a], p2 = P[a + 1];
			int q1 = Q[a], q2 = Q[a + 1];
			string Sleft = s.substr(0, p1);
			string Sright = s.substr(p2 + 1, s.size() - p2 - 1);
			string Tleft = t.substr(0, q1);
			string Tright = t.substr(q2 + 1, t.size() - q2 - 1);
			if (Sleft == Tleft && Sright == Tright) {
				ok = true;
				break;
			}
		}
		if (ok) {
			cout << "CLOSE" << endl;
		}
		else {
			cout << "DIFFERENT" << endl;
		}
	}
}



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

int main() {
    int x, y, a, b, c;
    cin >> x >> y >> a >> b >> c;

    vector<int64_t> p(a), q(b), r(c);
    for(int i = 0; i < a; i++) cin >> p[i];
    for(int i = 0; i < b; i++) cin >> q[i];
    for(int i = 0; i < c; i++) cin >> r[i];
    sort(p.rbegin(), p.rend());
    sort(q.rbegin(), q.rend());

    vector<int64_t> apples_sorted(x + y + c, 0);
    for(int i = 0; i < x; i++) apples_sorted[i] = p[i];
    for(int i = 0; i < y; i++) apples_sorted[i + x] = q[i];
    for(int i = 0; i < c; i++) apples_sorted[i + x + y] = r[i];
    sort(apples_sorted.rbegin(), apples_sorted.rend());

    int64_t ans = 0;
    for(int i = 0; i < x + y; i++) ans += apples_sorted[i];
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 4736
#include <iostream>
#include <iomanip>
#include <string>
#include <string.h>
#include <math.h>
#include <cmath>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <algorithm>
#include <utility>
#include <deque>
#include <queue>
#include <functional>
//#include <boost/multiprecision/cpp_int.hpp>

#define rep(i, n) for(int i = 0; i < n; ++i)
#define REP(i, m, n) for(int i = m; i < n; ++i)
#define rrep(i,n) for(int i = n; i >= 0; --i)
#define RREP(i, m, n) for(int i = n; i >= m; --i)
#define llrep(i, n) for(ll i = 0; i < n; ++i)
#define llREP(i, m, n) for(ll i = m; i < n; ++i)
#define llrrep(i,n) for(ll i = n; i >= 0; --i)
#define llRREP(i, m, n) for(ll i = n; i >= m; --i)

using ll = long long;
using ull = unsigned long long;
using pii = std::pair<int, int>;
using pll = std::pair<long long, long long>;
using pil = std::pair<int, long long>;
using pli = std::pair<long long, int>;
using plpii = std::pair<long long, std::pair<int, int>>;
using pdd = std::pair<double, double>;

const long long INF = 1000000000000000001;
const long long _MOD = 1000000007;
const long long MOD = 998244353;
const int ALPHABET = 27;
const double pi = 3.14159265358979;

using namespace std;
//namespace mp = boost::multiprecision;

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

	int n, t;
	cin >> n >> t;
	pii* ab = new pii[n];
	rep(i, n) cin >> ab[i].first >> ab[i].second;

	int** dpl = new int* [n];
	int** dpr = new int* [n];
	rep(i, n) {
		dpl[i] = new int[t];
		dpr[i] = new int[t];

		memset(dpl[i], 0, sizeof(int) * t);
		memset(dpr[i], 0, sizeof(int) * t);
	}

	REP(i, ab[0].first, t) {
		dpl[0][i] = ab[0].second;
	}
	REP(i, 1, n) {
		memcpy(dpl[i], dpl[i - 1], sizeof(int) * t);

		REP(j, ab[i].first, t) {
			dpl[i][j] = max(dpl[i - 1][j], dpl[i][j - 1]);
			dpl[i][j] = max(dpl[i][j], dpl[i - 1][j - ab[i].first] + ab[i].second);
		}
	}

	REP(i, ab[n-1].first, t) {
		dpr[n-1][i] = ab[n-1].second;
	}
	RREP(i, 0, n - 2) {
		memcpy(dpr[i], dpr[i + 1], sizeof(int) * t);

		REP(j, ab[i].first, t) {
			dpr[i][j] = max(dpr[i + 1][j], dpr[i][j - 1]);
			dpr[i][j] = max(dpr[i][j], dpr[i + 1][j - ab[i].first] + ab[i].second);
		}
	}

	int ans = 0, sum;
	rep(i, n) {
		if (i == 0) {
			sum = ab[i].second + dpr[i + 1][t - 1];
		}
		else if (i == n - 1) {
			sum = ab[i].second + dpl[i - 1][t - 1];
		}
		else {
			sum = ans;
			rep(j, t) {
				sum = max(sum, ab[i].second + dpl[i - 1][j] + dpr[i + 1][t - 1 - j]);
			}
		}

		ans = max(ans, sum);
	}

	cout << ans << "\n";

	return 0;
}



Measured memory_bytes: 70784
import java.lang.Math

fun main(args: Array<String>)
{
    val n = readLine()!!.toInt()
    val s = readLine()!!.toCharArray()

    var flag = true
    if (n % 2 != 0) println("No")
    else {
        val mid = n / 2
        for (i in 0 until mid) {
            if (s[i] != s[i+mid])   flag = false
        }

        println(if (flag) "Yes" else "No")
    }
}


Measured memory_bytes: 31948
#include<iostream>
#include<vector>
using namespace std;
int main(){
  int n;
  cin>>n;
  int c[n];
  vector<int> num(100000);
  for(int i=0;i<n;i++){
    cin>>c[i];
    num[c[i]+2]++;
    num[c[i]]++;
    num[c[i]+1]++;
    }
  int ans=0;
  for(int i=0;i<100000;i++){
    ans=max(ans,num[i]);
    }
  cout<<ans<<endl;
  return 0;
  }

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define ll long long int
#define MOD 1000000007
#define INF 1e18
#define PI 3.14159265358979

using namespace std;

ll gcd(ll a, ll b);
ll power(ll n, ll k);
ll inv(ll n);
ll genfact(ll n, ll k);
ll fact(ll n);
ll nck(ll n, ll k);

int main(void){
  ll n, m;

  cin >> n >> m;

  vector<ll> divisor(0);
  for (ll i = 1; i <= sqrt(m); i++){
    if (m % i == 0){
      divisor.emplace_back(i);
      divisor.emplace_back(m/i);
    }
  }

  ll ret = 1;
  for (int i = 0; i < divisor.size(); i++){
    if (m/divisor[i] >= n)
      ret = max(ret, divisor[i]);
  }


  cout << ret << endl;

  return 0;
}

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

ll power(ll n, ll k){
  ll res = 1;
  while(k > 0){
    if (k & 1) 
      res = res * n % MOD;
    n = n * n % MOD;
    k >>= 1;
  }
  return res;
}

ll genfact(ll n, ll k){

  ll res = 1;
  while (k >= 0){
    res = (res * (n - k)) % MOD;
    k--;
  }

  return res;
}

ll inv(ll n){
  return power(n, MOD - 2);
}

ll fact(ll n){
  return genfact(n, n - 1);
}

ll nck(ll n, ll k){
  if (k == 0)
    return 1;
  if (n <= 0)
    return 0;

  return ((genfact(n, k) % MOD) * inv(fact(k))) % MOD;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define dbg(x) #x "=" << x << " "
#define fore(i,a,b) for(int i=a,gon=b;i<gon;++i)
#define pb push_back
#define F first
#define S second
typedef double lf;
typedef long long ll;
typedef pair<int, int> pii;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    #ifdef LOCAL
        freopen("in.txt", "r", stdin);
        //freopen("out.txt", "w", stdout);
    #else
        #define endl '\n'
    #endif
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    int x = c-a, y = d-b;
    cout << string(y, 'U');
    cout << string(x, 'R');
    cout << string(y, 'D');
    cout << string(x, 'L');
    cout << 'L';
    cout << string(y+1, 'U');
    cout << string(x+1, 'R');
    cout << 'D';
    cout << 'R';
    cout << string(y+1, 'D');
    cout << string(x+1, 'L');
    cout << 'U' << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
//#pragma once
using namespace std;
#define repd(i,a,b) for (int i=(a);i<(b);i++)
#define rep(i,n) repd(i,0,n)
typedef long long ll;
typedef long double lb;
#define int long long
#define double long double
typedef pair<double,double> P;
const ll INF = 4*1e18;
const int MOD = 1000000007;
const double EPS = 1e-10;
const double PI = 3.141592653589793;
template<class T> inline bool chmin(T& a, T b){if(a>b){a = b;return 1;}return 0;}
template<class T> inline bool chmax(T& a, T b){if(a<b){a = b;return 1;}return 0;}
const pair<int,int> fd[] = {make_pair(1,0),make_pair(-1,0),make_pair(0,1),make_pair(0,-1)}; 

bool o(string s){
  int n = s.length();
  bool ret = true;
  rep(i,n/2){
    ret = ret && (s[i] == s[n-i-1]);
  }
  return ret;
}
int n, a[210000];map<int, int> mp;
signed main(){
  cin>>n;rep(i,n)cin>>a[i];
  rep(i,n){
    mp[a[i]]++;
  }
  int sum = 0;
  for(auto p : mp){
    sum += (p.second * (p.second-1))/2;
  }
  rep(i,n){
    cout << sum - mp[a[i]] + 1 << endl;
  }
}


Measured memory_bytes: 11904
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <utility>
#include <iostream>
#include <functional>
#include <bitset>
#include <algorithm>
#include <vector>
#include <forward_list>
#include <set>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#define rep(i, s, g) for ((i) = (s); (i) < (g); ++(i))
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
const ll MOD = 1e9 + 7;
const ll INF = (1ll << 60);

ll n;
set<string> ans;

void dfs(string s, char m)
{
    if (s.size() == n)
    {
        ans.insert(s);
        return;
    }

    for (char c = 'a'; c <= m; c++)
    {
        s.push_back(c);
        dfs(s, (c == m) ? m + 1 : m);
        s.pop_back();
    }
}

int main(void)
{
    cin >> n;

    string s;

    dfs(s, 'a');

    for (auto x : ans)
    {
        cout << x << endl;
    }
}

Measured memory_bytes: 13824
<?php
  list($n) = explode(" ", trim(fgets(STDIN)));
  $a = array_map('intval', explode(" ", trim(fgets(STDIN))));

  $isBuy = true;
  $kabu = 0;
  $money = 1000;
  for ($i=0; $i<$n-1; $i++) {
    if($isBuy && $a[$i+1] > $a[$i]){
      // buy
      $kabu = intdiv($money, $a[$i]);
      if($kabu == 0){
        continue;
      }
      $money = $money - $kabu * $a[$i];
      $isBuy = false;
    }
    else if(!$isBuy && $a[$i+1] < $a[$i]){
      // sell
      $money = $money + $kabu * $a[$i];
      $isBuy = true;
    }
//    echo $i." ".$money." ".$kabu.PHP_EOL;
  }
  if(!$isBuy){
    $money = $money + $kabu * $a[$n-1];
  }

  echo $money;

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

#define rep(i,n) for(int i = 0; i < (n); i++)
#define REP(i,n) for(int i = 1; i < (n); i++)
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define yesorno(a) printf(a ? "yes\n" : "no\n")
#define YesorNo(a) printf(a ? "Yes\n" : "No\n")
#define YESorNO(a) printf(a ? "YES\n" : "NO\n")

using ll = long long;
using P = pair<int,int>;
using vi = vector<int>;
using vii = vector<vi>;

const int dx[8] = {0,1,0,-1,1,1,-1,-1};
const int dy[8] = {1,0,-1,0,1,-1,-1,1};
const int inf = (1<<30)-1;
const ll infll = (1LL<<62)-1; 

#define int long long

signed main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n;
  cin >> n;
  map<char, int> mp;
  rep(i,n){
    string s;
    cin >> s;
    mp[s[0]]++;
  }
  char march[] = {'M', 'A', 'R', 'C', 'H'};
  ll ans = 0;
  for(int i = 0; i < 3; i++){
    for(int j = i+1; j < 4; j++){
      for(int k = j+1; k < 5; k++){
        ans += mp[march[i]] * mp[march[j]] * mp[march[k]];
      }
    }
  }
  cout << ans << endl;
}

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

int main() {
	int n,x,i,sum = 0,count,min,rem;
	cin>>n>>x;
	int m[n];
	count = n;
	for(i=0;i<n;i++)
	{
		cin>>m[i];
	}
	min = m[0];
	for(i=0;i<n;i++)
	{
		sum = sum+m[i];
		if(min>m[i])
		{
			min = m[i];
		}
	}
	rem = x-sum;
	count = count+(rem/min);
	cout<<count;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <set>
#include <map>
using namespace std;

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

    vector<int> L(n);
    int Lmax = 0;

    for (int i = 0; i < n; i++) {
        cin >> L[i];
    }

    sort(L.begin(), L.end(), greater<int>());

    int sum = 0;
    for (int i = 1; i < n; i++) {
        sum += L[i];
    }
    
    if (sum > L[0]) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl; 
    }
    
    return 0;

}

Measured memory_bytes: 256
#pragma GCC optimize ("Ofast")
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i=(a); i<(int)(b); i++)
#define FORD(i, a, b) for (int i=a; i>(int)(b); i--)
#define PPC(x) __builtin_popcount(x)
#define SZ(x) ((int)(x).size())
#define pb push_back
#define ALL(x) (x).begin(), (x).end()
#define ithBit(m, i) ((m) >> (i) & 1)
#define ft first
#define sd second
#define kw(a) ((a) * (a))
#ifdef DEBUG
#include "debug.h"
#else
#define dbg(...) 0
#endif
using namespace std;
 
const int maxN = 1 << 21;
 
 
void solve()
{
	int a, b, c, d;
	scanf ("%d", &a);
	
	long long res = 0;
	FOR(i, 1, a+1) FOR(j, 1, a+1) FOR(k, 1, a+1)
	{
		res += __gcd(__gcd(i, j), k);
	}
	
	printf("%lld\n", res);
}
 
int main()
{
	int t;
	t=1;//scanf ("%d", &t);
	while (t--)
		solve();
	return 0;
}

Measured memory_bytes: 3816
import java.util.*;class Main{public static void main(String[]z){int i,j,k,c,t,b;Scanner s=new Scanner(System.in);for(b=0;(t=s.nextInt())>0;System.out.println(b),b=0)for(i=1;i<=t;i++)for(j=i+2;j<=t;b+=c==t?1:0,j++)for(c=0,k=i;k<j;k++)c+=k;}}

Measured memory_bytes: 12000
#pragma gcc optimize("Ofast")
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(V) (V).begin(),(V).end()
#define SORT(V) sort(ALL(V)) //小さい方からソート
#define REV(V) reverse(ALL(V)) //リバース
#define RSORT(V) SORT(V);REV(V) //大きい方からソート
#define NPN(V) next_permutation(ALL(V)) //順列
#define pb(n) push_back(n)
#define endl '\n'
#define Endl '\n'
#define DUMP(x)  cout << #x << " = " << (x) << endl
#define YES(n) cout << ((n) ? "YES" : "NO"  ) << endl
#define Yes(n) cout << ((n) ? "Yes" : "No"  ) << endl
#define Yay(n) cout << ((n) ? "Yay!": ":(") << endl
#define RAPID cin.tie(0);ios::sync_with_stdio(false)
#define IN(n) cin >> n
#define IN2(a,b) cin >> a >> b
#define IN3(a,b,c) cin >> a >> b >> c 
#define IN4(a,b,c,d) cin >> a >> b >> c >> d
#define VIN(V) for(int i = 0; i < (V).size(); i++) {cin >> (V).at(i);}
#define OUT(n) cout << n << endl
#define VOUT(V) REP(i, (V).size()) {cout << (V)[i] << endl;}
#define VOUT2(V) REP(i, (V).size()) {cout << (V)[i] << " ";} cout<<endl;

// 型マクロ定義
#define int long long
#define P pair<ll,ll>
#define Vi vector<ll>
#define Vd vector<double>
#define Vs vector<string>
#define Vc vector<char>
#define M map<ll,ll>
#define S set<ll>
#define PQ priority_queue<ll>
#define PQG priority_queue<ll,V,greater<ll>
//

const int MOD = 1000000007;
const int INF = 1061109567;
const double EPS = 1e-10;
const double PI  = acos(-1.0);

int gcd(int a,int b){return b?gcd(b,a%b):a;} //最小公倍数
string toStrUp(string str){char diff = 'A'-'a';REP(i,str.size()) str[i] += diff;return str;}
string gCh(string str, int key){return str.substr(key,1);}

signed main() {
  RAPID;
  // デフォルト変数定義
  int n,m,a,b,c,d,x,y,z;
  string s,t;
  //

  // ここから
  IN2(a,b);
  if(a==1) a=14;
  if(b==1) b=14;
  if(a==b) OUT("Draw");
  else if(a>b) OUT("Alice");
  else OUT("Bob"); 
}

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

int gcd(int x, int y) {
  int a = min(x,y);
  int b = 0;
  for (int i = 0; i < a; i++) {
    if (x%(i+1) == 0 && y%(i+1) == 0) {
      b = i+1;
    }
  }
  return b;
}

int main() {
  int K;
  cin >> K;
  int ans = 0;
  for (int i = 0; i < K; i++) {
    for (int j = 0; j < K; j++) {
      for (int k = 0; k < K; k++) {
        ans += gcd(gcd(i+1,j+1),k+1);
      }
    }
  }
  cout << ans <<endl;
}


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

#define watch(x) cerr << (#x) << ": " << (x) << endl
#define int long long



int32_t main() {

    int k, a, b; cin >> k >> a >> b;

    int ans = 1;
    int remk = k;

    if(ans < a) {
        int taps = min(k, a-ans);
        remk -= taps;
        ans += taps;
    }

    if(b > a+1) {
        int times = remk/2;
        ans += (b-a)*times;

        if(remk%2) {
            ans++;
        }
    } else {
        ans += remk;
    }

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


Measured memory_bytes: 256
#include <stdio.h>
#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>

using ll = long long int;
using P = std::pair<int, int>;
const int INF = (1<<25);
const ll INFLL = (1ll<<60);
const ll MOD = (ll)(1e9+7);

#define l_ength size

void mul_mod(ll& a, ll b){
	a *= b;
	a %= MOD;
}

void add_mod(ll& a, ll b){
	a = (a<MOD)?a:(a-MOD);
	b = (b<MOD)?b:(b-MOD);
	a += b;
	a = (a<MOD)?a:(a-MOD);
}

int h,w;
bool visited[1010][1010];
int dist[1010][1010];
std::string s[1010];

bool check(int i, int j){
	return (0<=i && i<h && 0<=j && j<w && s[i][j]=='.');
}

std::deque<P> deq;

int main(void){
	int i,j,sx,sy,gx,gy,dx[4]={-1,0,0,1},dy[4]={0,-1,1,0},k,x,y;
	P v;
	std::fill(dist[0],dist[1010],INF);
	std::cin >> h >> w;
	std::cin >> sx >> sy;
	--sx; --sy;
	dist[sx][sy] = 0;
	std::cin >> gx >> gy;
	--gx; --gy;
	for(i=0; i<h; ++i){
		std::cin >> s[i];
	}
	deq.push_front(P(sx,sy));
	while(!deq.empty()){
		v = deq.front();
		deq.pop_front();
		sx = v.first; sy = v.second;
		if(visited[sx][sy]){
			continue;
		}
		visited[sx][sy] = true;
		for(k=0; k<4; ++k){
			x = sx+dx[k];
			y = sy+dy[k];
			if(check(x,y) && dist[x][y] > dist[sx][sy]){
				dist[x][y] = dist[sx][sy];
				deq.push_front(P(x,y));
			}
		}
		for(i=-2; i<3; ++i){
			for(j=-2; j<3; ++j){
				x = sx+i; y = sy+j;
				if(check(x,y) && dist[x][y] > dist[sx][sy]+1){
					dist[x][y] = dist[sx][sy] + 1;
					deq.push_back(P(x,y));
				}
			}
		}
	}
	std::cout << ((dist[gx][gy]<INF)?dist[gx][gy]:(-1)) << std::endl;
	return 0;
}


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

using namespace std;

int main() {

    int n, k; cin >> n >> k;

    int cnt[105] = {};

    for (int i = 0; i < k; i++) {

        int d; cin >> d;

        for (int j = 0; j < d; j++) {

            int x; cin >> x;

            cnt[x]++;

        }

    }

    int ans = 0;

    for (int i = 1; i <= n; i++) ans += cnt[i] == 0;

    cout << ans;

}


Measured memory_bytes: 3596
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); ++i)
#define all(x) (x).begin(), (x).end()
int main() {
  ll h;
  cin >> h;
  ll ans = 0;
  while(h) {
    h >>= 1;
    ans++;
  }
  cout << ((1LL << ans) - 1) << endl;
  return 0;
}

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

using S = long long;
using F = long long;

const S INF = 8e18;
const F ID = 8e18;

S op(S a, S b) { return std::max(a, b); }
S e() { return -INF; }
S mapping(F f, S x) { return (f == ID ? x : f); }
F composition(F f, F g) { return (f == ID ? g : f); }
F id() { return ID; }

const long long SZ = 300000 + 2;
int main() {
    int n, k;
    cin >> n >> k;
    std::vector<S> v(SZ);
    // 1点更新、区間最大値なので遅延ではないセグ木で十分だが、
    // 勉強のため遅延セグ木を用いる。
    atcoder::lazy_segtree<S, op, e, F, mapping, composition, id> seg(v);

    while (n--) {
        long long x;
        cin >> x;
        // 過去に存在した x±k の座標に対する点の数の最大値を求める
        long long me = seg.prod(max(0LL, x - k), min(SZ, x + k + 1));
        // 現在のx座標に対して上記+1をセット（区間更新）
        seg.apply(x, x + 1, me + 1);
    }
    cout << seg.all_prod() << endl;
}


Measured memory_bytes: 18052
#include <iostream>
#include <string>
#include <climits>

using namespace std;

int main() {
	int n, m, a, b;
	int amax{INT_MIN}, bmin{INT_MAX};
	scanf("%d%d", &n, &m);
	for(int i = 0; i < m; i++) {
		scanf("%d%d", &a, &b);
		if(a > amax) {
			amax = a;
		}
		if(b < bmin) {
			bmin = b;
		}
	}
	int result = bmin - amax + 1;
	printf("%d\n", ((result > 0) ? result : 0));
	return 0;
}


Measured memory_bytes: 256
import java.util.*;

public class Main {
    static Scanner sc = new Scanner(System.in);
    static int[][] map =new int[10][10];
    public static void main(String[] args){
        for(int i=0;i<10;i++){
            for(int j=0;j<10;j++){
                map[i][j]=0;
            }
        }
        while(sc.hasNextLine()){
            String[] s=sc.nextLine().split(",");
            int x=Integer.parseInt(s[0]);
            int y=Integer.parseInt(s[1]);
            int size=Integer.parseInt(s[2]);
            if(size==1){
                small(x,y);
            }else if(size==2){
                medium(x,y);
            }else if(size==3){
                large(x,y);
            }
        }
        int ans1=0,ans2=0;
        for(int i=0;i<10;i++){
            for(int j=0;j<10;j++){
                if(map[i][j]==0){
                    ans1++;
                }
                if(map[i][j]>ans2){
                    ans2=map[i][j];
                }
            }
        }
        System.out.println(ans1);
        System.out.println(ans2);
    }
    static void small(int x,int y){
        for(int i=-1;i<=1;i++){
            for(int j=-1;j<=1;j++){
                if((i+j>=-1)
                        &&(i+j<=1)
                        &&(i-j>=-1)
                        &&(i-j<=1)
                        &&(x+i>=0)
                        &&(x+i<10)
                        &&(y+j>=0)
                        &&(y+j<10)){
                    map[x+i][y+j]++;
                }
            }
        }
    }
    static void medium(int x,int y){
        for(int i=-1;i<=1;i++){
            for(int j=-1;j<=1;j++){
                if((x+i>=0)
                        &&(x+i<10)
                        &&(y+j>=0)
                        &&(y+j<10)){
                    map[x+i][y+j]++;
                }
            }
        }
    }
    
    static void large(int x,int y){
        for(int i=-2;i<=2;i++){
            for(int j=-2;j<=2;j++){
                if((i+j>=-2)
                        &&(i+j<=2)
                        &&(i-j>=-2)
                        &&(i-j<=2)
                        &&(x+i>=0)
                        &&(x+i<10)
                        &&(y+j>=0)
                        &&(y+j<10)){
                    map[x+i][y+j]++;
                }
            }
        }
    }
}

Measured memory_bytes: 15348
#include <stdio.h>
int main(void){
	char S[3];
	int i;
	for(i=0;i<3;i++){
		scanf("%c",&S[i]);
	}
	int x=0;
	for(i=0;i<3;i++){
		if(S[i]=='o'){x++;}
	}
	printf("%d",700+100*x);
	
	return 0;}

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

using namespace std;

int main(){
	int a, b ,c, k;
	
	cin >> a >> b >> c >> k;
	
	
	if(a > b && a > c){
		a = a*pow(2,k);
		cout << a+b+c << endl;
		
	}
	else if(b >= a && b >= c){
		b = b*pow(2,k);
		cout << a+b+c << endl;
		
	}
	else{
		c = c*pow(2,k);
		cout << a+b+c << endl;
		
	}
	
	
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define N 200006
using namespace std;
long long a[N],b[N],ans;int n;
inline int read()
{
    int x=0,c=getchar();while(c<48)c=getchar();
    while(c>47)x=x*10+c-48,c=getchar();return x;
}
int main()
{
	n=read();
	for(int i=1;i<=n;i++)a[i]=read(),b[i]=read();
	for(int i=n;i>=1;i--){
		a[i]+=ans;
		ans+=1LL*(a[i]/b[i]+(((a[i]/b[i]+1)*b[i]-a[i])%b[i]>0?1:0))*b[i]-a[i];
	}
	cout<<ans;
}

Measured memory_bytes: 1792
matrix = []
for i in range(3):
    matrix.append(list(map(int, input().split())))

mat_dif = [0, 0, 0]
for i in range(3):
    mat_dif[i] = ([matrix[i][0]-matrix[i][1]], [matrix[i][1]-matrix[i][2]])

if mat_dif[0] == mat_dif[1] == mat_dif[2]:
    print("Yes")
else:
    print("No")
    

Measured memory_bytes: 3060
n = gets.to_i
heights = gets.chomp.split(' ').map(&:to_i)
max = 0
counter = 0
i = 1
while i < n
  if heights[i-1] >= heights[i]
    counter += 1
    if max < counter
      max = counter
    end
  else
    counter = 0
  end
  i += 1
end
if max < counter
  max = counter
end
puts max

Measured memory_bytes: 21856
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <map>
#include <cmath>
#include <queue>
#include <numeric>
#include <climits>
#include <iterator>
#include <iomanip>
#include <stack>
#include <set>
#include <cstdio>
#include <bitset>
#include <functional>
#include <tuple>
#include <list>
#include <deque>
#include <sstream>
using namespace std;
const constexpr int INF = 1e9;
#define FOR(i, a, n) for (ll i = (ll)a; i<(ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)

typedef long long ll;
typedef vector<int> VI;
const constexpr ll MOD = 1e9+7;
struct Less{
   bool operator()(const pair<string, int>&a, const pair<string, int>&b){
        if(a.first==b.first){
            return a.second < b.second;
        }
       return a.first < b.first;
    }
};

ll extGCD(ll a, ll b, ll& x, ll& y){
    if(b==0){
        x=1;
        y=0;
        return a;
    }
    ll d = extGCD(b, a%b, y, x);
    y -= a/b*x;
    return d;
}
ll GCD(ll a, ll b){
    if(a<b) swap(a, b);
    if(b==0) return a;
    return GCD(b, a%b);
}
int par[100010], rr[100010];
void init(){
    for(int i=0; i<100010; ++i){
        par[i]=i;
        rr[i]=0;
    }
}
int root(int x){
    return par[x] == x ? x:par[x] = root(par[x]);
}
bool same(int x, int y){
    return root(x)==root(y);
}
void unite(int x, int y){
    x = root(x);
    y = root(y);
    if(x==y) return ;
    
    if(rr[x]<rr[y]){
        par[x] = y;
    }else{
        par[y] = x;
        if(rr[x]==rr[y]) rr[x]++;
    }
}

ll pow_mod(ll x, ll n){
    ll res = 1;
    while(n>0){
        if(n&1){
            res = res*x%MOD;
        }
        x = x*x%MOD;
        n>>=1;
    }
    return res;
}
int main() {
    int N; cin >> N;
    int s[N+1]={0};
    int sum=0;
    for(int i=1; i<=N; ++i){
        cin >> s[i];
        sum+=s[i];
    }
    sort(s, s+N);
    for(int i=0; i<=N; ++i){
        if((sum-s[i])%10!=0){
            cout << sum-s[i] << endl;
            return 0;
        }
    }
    cout << 0 << endl;   
    
    
    return 0;
}

Measured memory_bytes: 256
n = int(input())
a = list(map(int, input().split()))
ans = 1
for i in range(n):
    if a[i] == 0:
        ans = 0
    if ans != -1:
        ans = ans * a[i]
    if ans > 1000000000000000000:
        ans = -1
print(ans)

Measured memory_bytes: 21568
#include <iostream>
#include <vector>
#include <stack>
#include <queue>

using namespace std;

static const int N = 100;
static const int WHITE = 0;
static const int GREY = 1;
static const int BLACK = 2;

int n, m[N][N];
bool visited[N];
int d[N], dist;


void bfs(int i){
	queue<int> q; q.push(i);
	visited[i] = true;

	while (!q.empty()) {
		int u = q.front(); q.pop();
		for (int v = 0; v < n; ++v) {
			if (!visited[v] && m[u][v]){
				d[v] = d[u] + 1;
				visited[v] = true;
				q.push(v);
			}
		}
	}
}


void search(){
	for (int i = 0; i < n; ++i) {
		d[i] = -1;
		visited[i] = false;
	}
	d[0] = 0;
	bfs(0);

	for (int i = 0; i < n; ++i)	cout << i + 1 << " " << d[i] << endl;
}


int main()
{
	cin >> n;

	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) m[i][j] = 0;
	}

	for (int i = 0; i < n; ++i) {
		int u, d; cin >> u >> d;
		for (int j = 0; j < d; ++j) {
			int v; cin >> v;
			m[u - 1][v - 1] = 1;
		}
	}

	search();

	return 0;
}

Measured memory_bytes: 3116
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(long long i=0; i<(int)n; i++)
#define rep2(i,a,n) for(long long i=(a); i<(int)(n); i++)
#define all(vec) vec.begin(),vec.end()
using ll = long long;
using vi = vector<int>;
using vs = vector<string>;
using vvi = vector<vi>;
using vll = vector<ll>;
using pii = pair<int, int>;
using psi = pair<string, int>;
const int dx[4] = {1, 0,-1, 0};
const int dy[4] = {0, 1, 0,-1};
const ll mod = 1e9+7;
int gcd(int a, int b){if(a%b == 0){return(b);}else{return(gcd(b, a%b));}}
int lcm(int a, int b){return a * b / gcd(a, b);}

int N, M, K, H, W, L, R, X;
string S, T;

int main(){
  cin >> N;
  vi A(N+1);
  rep2(i,1,N+1) cin >> A[i];
  vi B(N+1,0);
  ll ans = 0;
  vi ansB;
  for(int i=N; i>0; i--){
    int crt = 0;
    for(int j=i; j<=N; j += i){
      if(B[j]) crt++;
    }
    if(crt%2 == A[i]) continue;
    else {
      B[i] = 1;
      ans++;
      ansB.push_back(i);
    }
  }
  cout << ans << endl;
  rep(i,ans){
    cout << ansB[i];
    if(i!=ans-1) cout << " ";
  }
  cout << endl;
  return 0;
}

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

template <typename T>
T gcd(T a, T b) {
  if (a % b == 0) {
    return b;
  } else {
    return gcd(b, a % b);
  }
}

template <typename T>
set<T> factorize(T num) {
  set<T> result;
  T d = 2;
  while (d * d <= num) {
    if (num % d == 0) {
      num /= d;
      result.insert(d);
    } else {
      d++;
    }
  }
  if (num != 1) result.insert(num);
  return result;
}

int main() {
  ll a, b;
  cin >> a >> b;

  ll cd = gcd(a, b);

  auto s = factorize(cd);

  ll ans = s.size() + 1;
  cout << ans << endl;
}


Measured memory_bytes: 3660
#include <cstdio>
#include <string>

using namespace std;

#define COUNT 5

int main(void){
  int a,b,c,d,e;
  int duration[COUNT];
  int i;
  for(i=0; i<COUNT; i++) scanf("%d", &duration[i]);

  int idxMinMod = 0;
  int minMod = duration[0]%10;
  for(i=1; i<COUNT; i++){
    int mod = duration[i]%10;
    if (mod>0 && mod < minMod)
    {
      idxMinMod = i;
      minMod = mod;
    }
  }
  
  int totalDuration = 0;
  for(i=0; i<COUNT; i++){
    if (i==idxMinMod){
      totalDuration += duration[i];
    }
    else{
      totalDuration += (duration[i]/10)*10;
      if(duration[i]%10!=0){
        totalDuration += 10;
      }
    }
  }
  printf("%d\n",totalDuration);
  fflush(stdout);

  return 0;
}



Measured memory_bytes: 128
#include <iostream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <climits>
#include <cfloat>
using namespace std;

int main()
{
    for(;;){
        int n, k, m;
        cin >> n >> k >> m;
        if(n == 0)
            return 0;

        vector<int> next(n);
        for(int i=0; i<n; ++i)
            next[i] = (i+1) % n;

        int curr = m - 1;
        int prev = (m - 2 + n) % n;
        for(int i=0; i<n-1; ++i){
            next[prev] = next[curr];
            for(int j=0; j<k; ++j){
                prev = curr;
                curr = next[curr];
            }
        }

        cout << (curr+1) << endl;
    }
}

Measured memory_bytes: 940
#include <iostream>
#include <string>
#include <vector>
#include <numeric>
#include <algorithm>
#include <cmath>
#include <map>
#include <cstdio>
#define fol(i,n) for(int i=0;i<n;i++)
#define db(a) cout << a<< endl;
using namespace std;


int main(){
    int a,b;
    cin >>a>>b;
    cout << (a-1)*(b-1)<<endl;
    return 0;
}


Measured memory_bytes: 256
import kotlin.math.PI

fun main() {
    println(solve())
}

val solve: () -> Any = {
    val (N, M) = readIntList()
    val A = readIntList()
    (N-A.sum()).let {if (it >= 0) it else -1}
}

fun readString() = readLine()!!
fun readInt() = readLine()!!.toInt()
fun readLong() = readLine()!!.toLong()
fun readStringList() = readLine()!!.split(" ")
fun readIntList() = readLine()!!.split(" ").map(String::toInt)

Measured memory_bytes: 39324
#include<bits/stdc++.h>
#define int long long int
#define pb push_back
#define  fill(st,et,val,arr) for(int i=st;i<=et;i++)arr[i]=val;
#define all(v) v.begin(),v.end()
template <class T>
inline void read(T &x) {
    x = 0;
    char ch = getchar(), w = 0;
    while (!isdigit(ch)) w = ch == '-', ch = getchar();
    while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
    x = w ? -x : x;
    return;
}
 
const int M=1e9 + 7;
const int MAX=1e5+7;
using namespace std;
bool comp(int a,int b)
{	
	return a>b;
}
void printQ(vector<int> q)
{   
    cout<<"v->  ";
	for(int i=0;i<q.size();i++)
	{
		cout<<q[i]<<" ";
	}
	cout<<endl;
}
int solve(int h,int* a,int*  c,int n,vector<vector<int>>& dp)
{
	if(h<=0)
	{
		return 0;
	}
	if(n==0)
	{
		return INT_MAX;
	}
	if(dp[h][n]!=-1)
	{
		return dp[h][n];
	}
	//int ans=c[0]+solve(h-a[0],a+1,c+1);
	int ans=solve(h,a+1,c+1,n-1,dp);
	ans=min(ans,c[0]+solve(h-a[0],a,c,n,dp));
	ans=min(ans,c[0]+solve(h-a[0],a+1,c+1,n-1,dp));
	dp[h][n]=ans;
	return ans;
}
int32_t main() 
{
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int a,b,c;
    cin>>a>>b>>c;
    set<int> st;
    st.insert(a);
    st.insert(b);
    st.insert(c);
    if(st.size()==2)
    {
    	cout<<"Yes"<<endl;
	}else{
		cout<<"No"<<endl;
	}
	return 0;
}













Measured memory_bytes: 256
#include<stdio.h>
int main()
{
    int a,b,c,d=0,i,j;
    scanf("%d",&a);
    int x[a];
    for(i=0;i<a;i++){
        scanf("%d",&x[i]);
    }
    scanf("%d",&b);
    for(i=0;i<b;i++){
        scanf("%d",&c);
        for(j=0;j<a;j++){
            if(c==x[j]){
                d++;
                break;
            }
        }
    }
    printf("%d\n",d);
    return 0;
}

Measured memory_bytes: 640
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <climits>
#include <cmath>
#include <map>
#include <queue>
#include <iomanip>
#include <set>
using namespace std;

#define rep(i,n) for(int (i)=0;(i)<(n);(i)++ )
#define repf(i,m,n) for(int (i)=m;(i)<n;(i)++)
#define all(v) (v).begin(), (v).end()
#define ll long long
#define vec(name,num) vector<ll> name((num),0);
#define op(i) cout<<(i)<<endl;
#define opf(i) cout<<fixed<<setprecision(10)<<(i)<<endl;
#define ip(i) cin>>(i);
#define opN cout<<"No"<<endl;
#define opY cout<<"Yes"<<endl;
#define opP cout<<"Possible"<<endl;
#define opI cout<<"Impossible"<<endl;
#define mat(name,fnum,snum); vector<vector<ll>> name((fnum),vector<ll>((snum),0));
#define matC(name,fnum,snum); vector<vector<char>> name((fnum),vector<char>((snum),0));
#define debugP int debug_point; cin>>debug_point;
#define FI first
#define SE second
const ll MOD= 1e9 + 7;

const string YES = "Yes";
const string NO = "No";

void solve(long long N, long long A){
  cout<<(N%500<=A?"Yes":NO)<<endl;
}

// Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
int main(){
    long long N;
    scanf("%lld",&N);
    long long A;
    scanf("%lld",&A);
    solve(N, A);
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int MOD = 998244353;

int main() {
	int n, k; cin >> n >> k;
	vector<int> L(k), R(k);
	vector<long long> cnt(n + 1);
	for (int i = 0; i < k; ++i) {
		cin >> L[i] >> R[i];
		++cnt[L[i]];
		--cnt[min(n, R[i] + 1)];
	}
	for (int i = 1; i < n; ++i) {
		(cnt[i] += cnt[i - 1]) %= MOD;
		for (int j = 0; j < k; ++j) {
			(cnt[min(n, i + L[j])] += cnt[i]) %= MOD;
			(cnt[min(n, i + R[j] + 1)] -= cnt[i]) %= MOD;
		}
	}
	cout << (cnt[n - 1] + MOD) % MOD << endl;

	return 0;
}


Measured memory_bytes: 4772
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<string> vstr;
typedef pair<ll, ll> pll;
typedef vector<pll> vp;
typedef map<ll, ll> mll;
typedef map<string, ll> mstrll;
typedef queue<ll> qll;
typedef queue<pll> qp;
#define pb push_back
#define mp make_pair
#define fir first
#define sec second
#define maxs(x, y) (x = max(x, y))
#define mins(x, y) (x = min(x, y))
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define _overload3(_1, _2, _3, name, ...) name
#define _rep(i, n) repi(i, 0, n)
#define repi(i, a, b) for(ll i = ll(a); i < ll(b); i++)
#define rep(...) _overload3(__VA_ARGS__, repi, _rep,)(__VA_ARGS__)
#define _rev(i, n) revi(i, n, 0)
#define revi(i, a, b) for(ll i = ll(a - 1); i >= ll(b); i--)
#define rev(...) _overload3(__VA_ARGS__, revi, _rev,)(__VA_ARGS__)
#define each(i, n) for(auto&& i: n)
#define out(x) cout << (x)
#define indent() cout << '\n'
#define print(x) cout << (x) << '\n'
#define debug(x) cerr << #x << ": " << (x) << '\n'
ll gcd(ll a, ll b){return b != 0 ? gcd(b, a % b) : a;}
ll lcm(ll a, ll b){return a / gcd(a, b) * b;}
ll factorial(ll a){return a < 2 ? 1 : factorial(a - 1) * a;}
ll summation(ll a){return a < 1 ? 0 : (a * a + a) / 2;}
const ll INF = 1e16, MOD = 1e9 + 7;
const string ALPHABETS = "abcdefghijklmnopqrstuvwxyz";
ll dx[] = {-1, 0, 1, 0}, dy[] = {0, -1, 0, 1};
//ll dx[] = {-1, 0, 1, -1, 1, -1, 0, 1}, dy[] = {-1, -1, -1, 0, 0, 1, 1, 1};
ll N, M, X, Y, Z, W, H;
string S, T;

signed main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    while(cin >> N){
        ll res = 0, cnt = 0, a_need = 0, b_need = 0, mx = -INF, mn = INF, a[N] = {}, b[N] = {}, dif[N] = {};
        bool flag = true;
        vll v;
        pll p;
        qll q;
        rep(i, N){
            cin >> a[i];
        }
        rep(i, N){
            cin >> b[i];
        }
        rep(i, N){
            if(a[i] < b[i]){
                cnt += (b[i] - a[i] + 1) / 2;
                a_need += b[i] - a[i];
            }else{
                b_need += a[i] - b[i];
            }
        }
        a_need -= 2 * cnt, b_need -= cnt;
        print(a_need >= b_need ? "Yes" : "No");
    }
}


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

int main(){
    ll N,Q; 
    cin >> N;
    vector<ll> A(N);
    for(ll i=0;i<N;i++)cin >> A[i];
    cin >> Q;
    vector<ll> B(Q),C(Q);
    for(ll i=0;i<Q;i++)cin >> B[i] >> C[i];

    vector<ll> D(100005);
    for(ll i=0;i<=100004;i++)D[i] = 0;
    for(ll i=0;i<N;i++)D[A[i]] += 1;
    ll sum = 0;
    for(ll i = 0;i<N;i++)sum += A[i];
    for(ll q=0;q<Q;q++){
        sum -= B[q]*D[B[q]];
        sum += C[q]*D[B[q]];
        D[C[q]] += D[B[q]];
        D[B[q]] = 0;
        cout << sum << endl;
    }
}

Measured memory_bytes: 6440
#003
N,x=input().split(" ")
s = input().split(" ")
list = []
for i in range(int(N)):
    list.append(int(s[i]))
count = 0

if(list[0]>int(x)):
    count+=list[0]-int(x)
    list[0]-=list[0]-int(x)

for i in range(1,int(N)):
    temp = list[i]+list[i-1]
    if(temp>int(x)):
        count+=temp-int(x)
        list[i]-=temp-int(x)        
print(count) 

Measured memory_bytes: 14152
L, R = map(int, input().split())

if R // 2019 != L // 2019:
    print(0)
else:
    L = L % 2019
    R = R % 2019
    min_m = 1000000000000
    for i in range(L, R+1):
        for j in range(i+1, R+1):
            m = (i * j) % 2019 
            if m < min_m:
                min_m = m
    print(min_m)

Measured memory_bytes: 3060
import heapq
import collections
n = int(input())
v = list(map(int, input().split()))

cnts = [collections.Counter(v[::2]), collections.Counter(v[1::2])]

hs = [[], []]
for i in range(2):
    for k, c in cnts[i].items():
        heapq.heappush(hs[i], (-c, k))
h0 = heapq.heappop(hs[0])
h1 = heapq.heappop(hs[1])
if h0[1] == h1[1]:
    if not hs[0] and not hs[1]:
        print(n//2)
    elif not hs[0]:
        print(n+h1[0])
    elif not hs[1]:
        print(n+h0[0])
    else:
        n0 = heapq.heappop(hs[0])
        n1 = heapq.heappop(hs[1])
        print(n + min(h0[0]+n1[0], n0[0]+h1[0]))
else:
    print(n+(h0[0]+h1[0]))


Measured memory_bytes: 20792
from collections import deque

n=int(input())
X=[[] for _ in range(n)]
for i in range(n-1):
    a,b,c=map(int,input().split())
    X[a-1].append([b-1,c])
    X[b-1].append([a-1,c])
    
distance=[-1]*n

q,k=map(int,input().split())

Que=deque([[k-1,0]])

while Que:
    b,c=Que.popleft()
    distance[b]=c
    for pb,pc in X[b]:
        if distance[pb]==-1:
            Que.append([pb,c+pc])

for i in range(q):
    x,y=map(int,input().split())
    print(distance[x-1]+distance[y-1])

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

/**
* @brief インタフェース
*/
class IAizuPR
{
public:
    virtual std::string& executeEx() = 0;
};

/**
* @brief 文字列を操作する
*/
class AizuPR final : public IAizuPR
{
public:
    /**
    * @brief コンストラクタ
    */
    AizuPR(std::string& ss) :
        str(ss) ,
        bufCnt(0) {}

    /**
    * @brief デストラクタ
    */
    ~AizuPR() {}

public:
    /**
    * @fn std::string& executeEx()
    * @brief 文字列からHoshinoを検索し、Hoshinaへ変換する
    * @return std::string& 変換後の文字列
    */
    std::string& executeEx();

private:
    /**
    * @fn bool isFind(int& index)
    * @brief Hoshinoが含まれるか検索する
    * @param[out] index 開始位置
    * @return bool 含まれる場合はtrueを、そうでなければfalseを返す
    */
    bool isFind(int& index);

    /**
    * @fn void replace(int index)
    * @brief HoshinoをHoshinaに置き換える
    * @param[in] index 開始位置
    */
    void replace(int index);

private:
    //! "Hoshino"
    static const std::string Hoshino;

    //! "Hoshina"
    static const std::string Hoshina;

private:
    //! ターゲット文字列
    std::string str;

    //! バッファカウント
    int bufCnt;
};

const std::string AizuPR::Hoshino("Hoshino");
const std::string AizuPR::Hoshina("Hoshina");

std::string& AizuPR::executeEx()
{
    int tIdx = 0;
    std::string tStr(str);

    while (isFind(tIdx)) {
        replace(tIdx);
    }

    return str;
}

/**
* @brief コントロール
*/
class Control
{
public:
    /**
    * @fn void executeEx()
    * @brief データセット回文字列を読み込み、HoshinoをHoshinaへ変換し、表示する
    */
    void executeEx();

};

bool AizuPR::isFind(int& index)
{
    
    if (std::string::npos == (index = str.find(Hoshino, bufCnt))) {
        index = 0;
        return false;
    }

    bufCnt = index + Hoshina.length();

    return true;
}

void AizuPR::replace(int index)
{
    str.replace(index, Hoshino.length(), Hoshina);
}

void Control::executeEx()
{
    std::string in("");
    std::string out("");

    int size = 0;

    std::cin >> size;
    std::cin.ignore();

    for (int i = 0; i < size; i++) {
        std::getline(std::cin, in);

        IAizuPR* pAizuPR = new AizuPR(in);

        out = pAizuPR->executeEx();

        std::cout << out << std::endl;

        in.clear();

        out.clear();
        delete pAizuPR;
    }
}

/**
* @fn int main()
* @brief エントリポイント
*/
int main()
{
    Control().executeEx();
}



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

inline long long read(){
    long long s = 0, w = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9'){
        if (ch == '-') w = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9'){
        s = s * 10 + ch - '0';
        ch = getchar();
    }
    return s * w;
}

int main(){
    long long a = read(), b = read();
    if (a > b){
        puts("safe");
    }
    else{
        puts("unsafe");
    }
    return 0;
}
//g++ A.cpp -o A.exe -lm -Wall

Measured memory_bytes: 3620
#include<bits/stdc++.h>
using namespace std;
long long a[100001],b[100001],vis[100001],ans;
vector<int> adj[100001],sum[100001];
map<long long,int> mp;
void dfs2(int x){
	if (vis[x]) return;vis[x]=1;
	if (a[x]<1){
		puts("0");exit(0);
	}
	for (int i=0;i<adj[x].size();i++){
		if (vis[adj[x][i]]){
			if (a[adj[x][i]]!=sum[x][i]-a[x]){
				puts("0");
				exit(0);
			}
		}
		a[adj[x][i]]=sum[x][i]-a[x];
		dfs2(adj[x][i]);
	}
}
void check(int x,int ax,int bx,int ax2,int bx2){
	if (ax==ax2){
		if (bx==bx2) return;
		puts("0");exit(0);
	}
	if (bx==bx2){
		if (ax==ax2) return;
		puts("0");exit(0);
	}
	if ((bx-bx2)%(ax-ax2)!=0){
		puts("0");exit(0);
	}
	int xx=-(bx-bx2)/(ax-ax2);
	if (xx<1){
		puts("0");exit(0);
	}
	memset(a,0,sizeof(a));
	a[1]=xx;
	memset(vis,0,sizeof(vis));
	dfs2(1);
	puts("1");
	exit(0);
}
void dfs(int x){
	if (vis[x]) return;vis[x]=1;
	for (int i=0;i<adj[x].size();i++){
		if (vis[adj[x][i]]){
			check(adj[x][i],-a[x],sum[x][i]-b[x],a[adj[x][i]],b[adj[x][i]]);
		}
		a[adj[x][i]]=-a[x];
		b[adj[x][i]]=sum[x][i]-b[x];
		dfs(adj[x][i]);
	}
}
void adrg(long long l,long long r){
	if (l>r) return;
	l=max(l,1ll);
	r=min(r,(long long)(1e9));
	mp[l]++;mp[r+1]--;
}
int main(){
	int i,j;
	int n,m;
	scanf("%d%d",&n,&m);
	for (i=0;i<m;i++){
		int x,y,z;
		scanf("%d%d%d",&x,&y,&z);
		adj[x].push_back(y);adj[y].push_back(x);
		sum[x].push_back(z);sum[y].push_back(z);
	}
	a[1]=1;b[1]=0;
	mp[1];mp[(long long)(1e9+1)];
	dfs(1);
	for (i=1;i<=n;i++){
		long long lim=1-b[i];
		if (a[i]==1) adrg(1,lim-1); else adrg((-lim)+1,1e9);
	}
	int s=0,lst=mp.begin()->first;
	for (map<long long,int>::iterator i=mp.begin();i!=mp.end();i++){
		if (!s) ans+=i->first-lst;
		s+=i->second;
		lst=i->first;
	}
	printf("%lld",ans);
	return 0;
}

Measured memory_bytes: 21632
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define int long long int
#define mod 1000000007
#define string_mod 2549536629329_base_255
#define pb push_back
#define F first
#define S second
#define ff first
#define endl "\n"
#define ss second
#define all(v) v.begin(), v.end()
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
int power(int x, unsigned int y, int p)
{
    int res = 1;
    x = x % p;
    while (y > 0)
    {
        if (y & 1)
            res = (res * x) % p;
        y = y >> 1;
        x = (x * x) % p;
    }
    return res % p;
}
 
int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int tc;
    tc = 1;
    //  cin >> tc;
    while (tc--)
    {
        int h, m, hh, mm,k;
        cin >> h >> m >> hh >> mm>>k;
        hh -= h;
        if(hh<0){
            hh += 24;
        }
        hh *= 60;
        mm -= m;
        hh += mm;
        cout << hh - k << endl;
    }

    return 0;
}

Measured memory_bytes: 3648
#include<stdio.h>
int main()
{
    int n;
    scanf("%d",&n);
    int t=1000;
    int res = t - n;
    if(res>0)
    {
        printf("%d\n",res);
    }
    else
    {
        for(;res<0;)
        {
            t = t + 1000;
            res = t-n;
        }
        printf("%d\n",res);
    }
}


Measured memory_bytes: 1704
from collections import defaultdict

s = input()
t = input()

def fprint(x):
    d = defaultdict(list)
    for i, c in enumerate(x):
        d[c].append(i)
    return sorted(d.values())

sf = fprint(s)
tf = fprint(t)
if sf == tf:
    print('Yes')
else:
    print('No')

Measured memory_bytes: 55996
#include <stdio.h>
#include <iostream>
#include <vector>
#include <string>
#include <tuple>
#include <algorithm>
#include <map>
#include <cmath>
using namespace std;
long long int MOD = 1000000000 + 7;
using ll = long long;

int main() {
	ll n, k, s;
	cin >> n >> k >> s;
	ll dummy = 1000000000;
	if (s == dummy) {
		dummy--;
	}
	vector<ll> a(n, dummy);


	for (ll i = 0; i < k; ++i) {
		a[i] = s;
	}

	for (ll i = 0; i < n; ++i) {
		cout << a[i];
		if (i == n - 1) {
			cout << endl;
		}
		else {
			cout << " ";
		}
	}
}


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

#define fi first
#define se second
#define repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define rep(i,n) repl(i,0,n)
#define each(itr,v) for(auto itr:v)
#define pb(s) push_back(s)
#define mp(a,b) make_pair(a,b)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<x<<endl
#define maxch(x,y) x=max(x,y)
#define minch(x,y) x=min(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
#define exist(x,y) (find(all(x),y)!=x.end())
#define bcnt(x) bitset<32>(x).count()

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;
typedef pair<P, int> PPI;
typedef pair<ll, ll> PL;
typedef pair<P, ll> PPL;

#define INF INT_MAX/3

#define MAX_N 1000
#define BROKEN 1000000001

int n;
int a[1111];

int main(){
	cin.sync_with_stdio(false);
	while(1){
		cin>>n;
		if(n==0)break;
		rep(i,n){
			string s;
			cin>>s;
			if(s[0]=='x')a[i]=BROKEN;
			else a[i]=stoi(s);
		}
		bool ok=true;
		rep(i,n){
			if(i>0&&a[i-1]!=BROKEN&&a[i]!=BROKEN&&((i%2==0&&a[i-1]<a[i])||(i%2==1&&a[i-1]>a[i])))ok=false;
			if(i<n-1&&a[i]!=BROKEN&&a[i+1]!=BROKEN&&((i%2==0&&a[i]>a[i+1])||(i%2==1&&a[i]<a[i+1])))ok=false;
			if(i>0&&a[i-1]==BROKEN&&a[i]==BROKEN)ok=false;
		}
		if(!ok){
			cout<<"none"<<endl;
			continue;
		}
		int lb=-BROKEN,ub=BROKEN;
		rep(i,n){
			if(i>0&&a[i]==BROKEN&&a[i-1]!=BROKEN){
				if(i%2==0)minch(ub,a[i-1]-1);
				else maxch(lb,a[i-1]+1);
			}
			if(i<n-1&&a[i]==BROKEN&&a[i+1]!=BROKEN){
				if(i%2==0)minch(ub,a[i+1]-1);
				else maxch(lb,a[i+1]+1);
			}
		}
		if(lb==-BROKEN||ub==BROKEN||(lb<ub))cout<<"ambiguous"<<endl;
		else if(lb==ub)cout<<lb<<endl;
		else cout<<"none"<<endl;
	}
	return 0;
}

Measured memory_bytes: 3224
#include <iostream>
#include <vector>
#include <unordered_map>
#include <deque>
#include <list>
#include <set>
#include <random>
#include <deque>

using namespace std;
using ll = long long;
const int BIG = 100000007;


int main() {
    ll l,r,d;
    cin >> l >> r >> d;
    cout << (r / d - (l - 1) / d) << endl;
}




Measured memory_bytes: 3188