akhauriyash/Code-Regression huggingface dataset:
#include<stdio.h>
int A[500000],n;

void maxHeapify(int);
void buildMaxHeap(void);
int main(){
  int i;

  scanf("%d",&n);
  for(i=1;i<=n;i++)scanf("%d",&A[i]);
  buildMaxHeap();
  for(i=1;i<=n;i++)printf(" %d",A[i]);
  printf("\n");
  return 0;
}
void maxHeapify(int i){
  int l,r,H,largest;
  l=i*2;
  r=i*2+1;

  if(l<=n&&A[l]>A[i])
    largest=l;
  else
    largest=i;
  if(r<=n&&A[r]>A[largest])
    largest=r;
  if(largest!=i){
    H=A[i];
    A[i]=A[largest];
    A[largest]=H;
    maxHeapify(largest);
  }
}
void buildMaxHeap(){
  int i;
  for(i=n/2;i>0;i--){
    maxHeapify(i);
  }
}



Measured memory_bytes: 3756
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
#define bug(args ...) cerr << __LINE__ << ">> ", err(new istringstream(string(#args)), args), cerr << '\n'
#define all(x) x.begin(), x.end()
#define F first
#define S second
#define M_PI 3.14159265358979323846
#define MOD 1000000007
#define int ll
typedef unsigned long long BITMASK; typedef long long ll; typedef long double ld; typedef pair<int, int> pii; typedef pair<double, double> pdd; typedef pair<long long, long long> pll; typedef cc_hash_table<int, int, hash<int>> intHashTable;
struct custom_hash { static uint64_t splitmix64(uint64_t x) { x += 0x9e3779b97f4a7c15; x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9; x = (x ^ (x >> 27)) * 0x94d049bb133111eb; return x ^ (x >> 31); } size_t operator()(uint64_t x) const { static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count(); return splitmix64(x + FIXED_RANDOM); } };
inline int powMod(int a, int b) { int x = 1; while (b > 0) { if (b&1) x = (x*a) % MOD; a = (a*a) % MOD; b >>= 1; } return x; }
inline int multiply(int x, int y) { return ((x % MOD) * (y % MOD)) % MOD; }
inline int divide(int x, int y) { return ((x % MOD) * powMod(y % MOD, MOD-2)) % MOD; }
inline int ceil(int a, int b) { return (a+b-1)/b; }
int gcd (int a, int b) { while (b) { a %= b; swap(a, b); } return a; }
int lcm (int a, int b) { return a / gcd(a, b) * b; }
int inverseMod(int a, int m) { a = a % m; for (ll x = 1; x < m; x++) if ((a * x) % m == 1) return x; return -1; }
void err(istringstream *iss) {} template<typename T, typename ... Args> void err(istringstream *iss, const T &_val, const Args & ... args) { string _name; *iss >> _name; if (_name.back()==',') _name.pop_back(); cerr << _name << " = " << _val << "; ", err(iss, args ...); }
int str_replace(string& str, const string& from, const string& to, int limit = -1) { if(from.empty()) return 0; size_t start_pos = 0; int cnt = 0; while((start_pos = str.find(from, start_pos)) != std::string::npos) { str.replace(start_pos, from.length(), to); start_pos += to.length(); cnt++; if (cnt == limit) break; } return cnt; }
template<int D, typename T> struct vec : public vector<vec<D - 1, T>> { static_assert(D >= 1, "Vector dimension must be greater than zero!");  template<typename... Args> vec(int n = 0, Args... args) : vector<vec<D - 1, T>>(n, vec<D - 1, T>(args...)) { } }; template<typename T> struct vec<1, T> : public vector<T> { vec(int n = 0, T val = T()) : vector<T>(n, val) { }};

signed main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int n; cin >> n;
    for (int i = 0, x = 100; ; ++i, x += (x/100))
        if (x >= n) { cout << i << '\n'; break; }
    return 0;
}

Measured memory_bytes: 3656
#include<iostream>
#include<algorithm>
#include<vector>
#include<numeric>
#include<string>
#include<cmath>
#include<set>
#include<queue>
#include<deque>
#include<bitset>
#include<iomanip>
#include<cctype>
#include<map>
#include<cstring>
#include<bitset>
#include<cassert>

#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define rep2(i,a,b) for (int (i)=a;(i)<(b);(i)++)
#define all(x) (x).begin(),(x).end()

using namespace std;
using ll = long long int;

const int inf = 1001001000;
const long long int Inf = 1001001001001001000;



void print(vector<vector<int>> a){
	for (int i = 0; i < a.size(); i++)
	{
		for (int j=0;j<a[i].size();j++){
			cout << a[i][j] << " ";
		}
		cout << endl;
	}
}

void print(vector<vector<long long int>> a){
	for (int i=0;i<a.size();i++){
		for (int j=0;j<a[i].size();j++){
			cout << a[i][j] << " ";
		}
		cout << endl;
	}
}

void print(vector<int> a){
    int n = a.size();
    for (int j=0;j<n;j++) {
        if (j != n-1) cout << a[j] << " ";
        else cout << a[j] << endl;
    }
}

void print(vector<long long int> a){
    int n = a.size();
    for (int j=0;j<n;j++) {
        if (j != n-1) cout << a[j] << " ";
        else cout << a[j] << endl;
    }
}

void print(set<int> a){
	for (auto x:a)
		cout << x << " ";
	cout << endl;
}

//深さ優先探索のテンプレ.デフォルトでは参照渡ししたsetに探索済みの頂点が格納される.
//graphは隣接リスト.vは探索開始地点.seenは空のセット
void dfs(vector<vector<int>> &graph, int v,vector<ll> &ans,ll now,set<int> &seen){
	seen.insert(v);
	ans[v] += now;
	for (int i = 0; i < graph[v].size(); i++)
	{
		int nxt = graph[v][i];
		if (seen.count(nxt)) continue;
		dfs(graph, nxt, ans,ans[v],seen);
	}
}

int main(){
	int n, q;
	cin >> n >> q;
	vector<vector<int>> graph(n,vector<int>());
	rep(i,n-1){
		int a, b;
		cin >> a >> b;
		graph[a-1].push_back(b-1);
		graph[b-1].push_back(a-1);
	}
	vector<ll> ans(n, 0);
	rep(i,q){
		int p, x;
		cin >> p >> x;
		ans[p-1] += x;
	}
	set<int> seen;
	dfs(graph, 0, ans, 0, seen);
	print(ans);
 
	return 0;
}


Measured memory_bytes: 38272
#include<iostream>
using namespace std;
int s,m,a,t;
main()
{
  for(int i=5;i--;)
  {
    cin>>a;
    t=(a-1)/10*10+10;
    s+=t;
    if(m<t-a)m=t-a;
  }
  cout<<s-m<<endl;
}

Measured memory_bytes: 256
using System;
using System.Collections;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Numerics;
using System.Text;
using System.Threading.Tasks;
using static System.Console;
using static System.Math;
class Z { static void Main() => new K(); }
class K
{
	int F => int.Parse(Str);
	long FL => long.Parse(Str);
	int[] G => Strs.Select(int.Parse).ToArray();
	long[] GL => Strs.Select(long.Parse).ToArray();
	string Str => ReadLine();
	string[] Strs => Str.Split(new char[] { ' ', '\t' }, StringSplitOptions.RemoveEmptyEntries);
	const int MOD = 1000000007;
	public K()
	{
		SetOut(new StreamWriter(OpenStandardOutput()) { AutoFlush = false });
		Solve();
		Out.Flush();
	}
	void Solve()
	{
		var S = Str;
		var cnt = 0;
		var sum = 0L;
		for (var i = 0; i < S.Length; i++)
		{
			if (S[i] == 'W') sum += cnt;
			else cnt++;
		}
		WriteLine(sum);
	}
}


Measured memory_bytes: 13112
#include <bits/stdc++.h>
#include <iostream>
using namespace std;
int main(){
  int N;
  cin >> N;
  string F[N]={};
  string BK[N]={};
  string BN[N]={};
  string SK[N]={};
  string SN[N]={};
  for(int i=0;i<N;i++){
    cin >> F[i];
    BK[i] = F[i].at(0);
    SK[i] = F[i].at(0);
    BN[i] = F[i].at(1);
    SN[i] = F[i].at(1);
  }
  for(int i=0;i<N;i++){
    for(int j=N-1;j>0;j--){
      if(BN[j]<BN[j-1]){
        swap(BN[j],BN[j-1]);
        swap(BK[j],BK[j-1]);
      }
    }
  }
  for(int i=0;i<N;i++){
    if(i<N-1){
    cout << BK[i] << BN[i] << " ";
    }
    else if(i==N-1){
      cout << BK[i] << BN[i] << endl << "Stable" << endl;
    }
  }
  for(int i=0;i<N-1;i++){
    int min=i;
    for(int j=i;j<N;j++){
      if(SN[j]<SN[min]){
        min =j;
      }
    }    
    swap(SN[i],SN[min]);
    swap(SK[i],SK[min]);
  }
  for(int i=0;i<N;i++){
    if(i<N-1){
      cout << SK[i] << SN[i] << " ";
    }
    else if(i==N-1){
      cout << SK[i] << SN[i] << endl;
    }
  }
  for(int i=0;i<N;i++){
    if(BK[i]!=SK[i]){
      cout << "Not stable" << endl;
      break;
    }
    if(i==N-1){
      cout << "Stable" << endl;
    }
  }
}  


Measured memory_bytes: 3140
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
const ll MOD = 1e9+7;
const ll INF = 1e18;
#define rep(i,m,n) for(ll i = (m); i <= (n); i++)
#define rrep(i,m,n) for(ll i = (m); i >= (n); i--)
#define print(x) cout << (x) << endl;
#define printa(x,m,n) for(ll i = (m); i <= n; i++){cout << (x[i]) << " ";} cout<<endl;

ll n;

int main(){
	cin.tie(0); ios::sync_with_stdio(false);
	
	cin >> n;
	ll a[n+1];
	rep(i, 1, n){
		cin >> a[i];
	}
	
	ll cnt[70];
	ll ans = 0;
	memset(cnt, 0, sizeof(cnt));
	rep(i, 1, n){
		for(ll j = 0; j < 60; j++){
			ll flag = (1LL << j);
			flag %= MOD;
			if(a[i] & (1LL << j)){
				ll buf = (i-1-cnt[j]) * flag;
				buf %= MOD;
				ans += buf;
				ans %= MOD;
			}
			else{
				ll buf = cnt[j] * flag;
				buf %= MOD;
				ans += buf;
				ans %= MOD;
			}
			
			if(a[i] & (1LL << j)){
				cnt[j]++;
			}
		}
	}
	print(ans)
	return 0;
}

Measured memory_bytes: 2560
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
const int N=1e5+5;
int main()
{
    int n,m,s;
    scanf("%d%d%d",&n,&m,&s);
    for(int i=1;i<=m;i++) cout<<s<<' ';
    int wzx;
    for(int i=1e9;i>=1;i--){
        if(i!=s){
            wzx=i;
            break;
        }
    }
    for(int i=m+1;i<=n;i++){
        cout<<wzx<<' ';
    }
    cout<<endl;
}


Measured memory_bytes: 1280
#include <cstdio>
#include <bits/stdc++.h>
#include <algorithm>
#include <iostream>
#include <string>
#include <cmath>
#include <functional>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#define rep(i,n) for (int i=0;i<n;i++)
using ll = long long;
using namespace std;

void solve(){

}
int main (){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    vector<int> a(n);
    rep(i,n) cin >> a[i];
    sort(a.begin(),a.end(),greater<int> ());
    vector<int> b(2*n);
    b[0] = a[0];
    for(int i=1;i<n;i++){
        b[2*i-1] = a[i];
        b[2*i] = a[i];
    }
    ll ans=0;
    rep(i,n-1) {
        ans +=b[i];
    }

    cout << ans;

    return 0;
}

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

int main(){
    string S; cin >> S;
    int sum=0;
    rep(i,S.size()){
        sum+=S[i]-'0';
    }
    if(stoi(S)%sum==0) cout <<"Yes";
    else cout << "No";
}

Measured memory_bytes: 256
import java.util.*;
public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int[] bar = new int[n];
    for (int i = 0; i < n; i++) {
      bar[i] = sc.nextInt();
    }
    int count = 0;
    for (int i = 0; i < n - 2; i++) {
      for (int j = i + 1; j < n - 1; j++) {
        for (int k = j + 1; k < n; k++) {
          if (bar[i] + bar[j] > bar[k] && bar[j] + bar[k] > bar[i] && bar[k] + bar[i] > bar[j]) {
            if (bar[i] == bar[j] || bar[j] == bar[k] || bar[k] == bar[i]) {
              continue;
            }
            count++;
          }
        }
      }
    }
    System.out.println(count);
  }
}


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

int main(){
	int n;
	cin>>n;
	int a[n+1];
	
	for(int i=1;i<=n;i++)
		cin>>a[i];
	
	for(int i=1;i<=n;i++){
		if(a[i]%2==0)
			if(a[i]%3!=0 && a[i]%5!=0){
				cout<<"DENIED";
				return 0;
			}		
	}	
	
	cout<<"APPROVED";
	return 0;	
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <map>
#include <queue> 
#include <stack>
#include <set>
#include <list>

using namespace std;
typedef long long ll;
#define rep(i, s, e) for (int(i) = (s); (i) <= (e); ++(i))
#define all(x) x.begin(),x.end()


int main()
{
	int a, b; cin >> a >> b;
	cout << ((b + a - 3) / (a - 1)) << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <set>

using namespace std;
int main(void){
    // Your code here!
  int n;
  int a[110];
  cin>>n;
  for(int i=0; i<n; i++) cin>>a[i];
  set<int> values;
  for (int i = 0; i<n; ++i) {
        values.insert(a[i]); 
    }
  std::cout << values.size() << std::endl;

  
}


Measured memory_bytes: 256
#include <cstdio>
#include <cstdint>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <array>
#include <vector>
#include <unordered_map>
#include <unordered_set>

int main()
{
    int N, M, C;
    std::cin >> N >> M >> C;

    int B[M];
    for (int i = 0; i < M; ++i) {
        std::cin >> B[i];
    }

    int ans = 0;
    int A;
    for (int i = 0; i < N; ++i) {
        int sum = 0;
        for (int j = 0; j < M; ++j) {
            std::cin >> A;
            sum += (A * B[j]);
        }

        sum += C;

        if (sum > 0) {
            ++ans;
        }
    }

    std::cout << ans << std::endl;


    return 0;
}

Measured memory_bytes: 256
import java.io.*;

class Main {
    public static void main(String[] args) {
        try {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));// ??\????????????????????????
            
            String line = br.readLine();
            String[] dataArray = line.split(" ");
            int x = Integer.parseInt(dataArray[0]);
            int y = Integer.parseInt(dataArray[1]);
            if(x<y) System.out.println(Result.LessThan.getValue());
            if(x==y) System.out.println(Result.Equal.getValue());
            if(x>y) System.out.println(Result.GreaterThan.getValue());
        } catch (Exception e) {
            e.printStackTrace();
        }
    }

    // private static void processLine(String line) {
    // System.out.println(line);
    // }
   public enum Result{
    	LessThan("a < b"),
    	Equal("a == b"),
    	GreaterThan("a > b");
	   
		// ?????£??????????????????
	    private String name;
	    
	    // ??????????????????????????????
	    private Result(String name) {
	        this.name = name;
	    }
	    
	    // ????????????
        public String getValue() {
            return this.name;
        }
   };
}

Measured memory_bytes: 24236
#include<iostream>
#include<cmath>
using namespace std;
long long pown(long long x, int N){
    long long ret=1;
    const long long MOD = 1000000007;
    int i;
    for(i=0;i<N;i++){
        ret = ret*x%MOD;
    }
    return ret;
}

int main()
{
    int N;
    cin >> N;
    const long long MOD = 1000000007;

    long long ans = 0;
    if(N<=1){
        ans = 0;
    }else if(N==2){
        ans = 2;
    }else{
        ans = (pown(10,N)-pown(9,N)*2+pown(8,N))%MOD;
        ans = (ans+MOD)%MOD;
    }

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



Measured memory_bytes: 3588
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<functional>
#include <random>

using namespace std;

int imin(int a, int b) {
	if (a < b) { return a; }
	else { return b; }
}


int main(void) {
	int N, A, B;
	int P[100];
	int first, second, third;

	scanf("%d", &N);
	scanf("%d %d", &A, &B);
	for (int i = 0; i<N; i++) {
		scanf("%d", &P[i]);
	}
	first = 0;
	second = 0;
	third = 0;

	for (int i = 0; i<N; i++) {
		if (P[i] <= A) {
			first++;
		}
		else if (P[i] <= B) {
			second++;
		}
		else {
			third++;
		}
	}
	printf("%d\n", imin(imin(first, second), third));
}

Measured memory_bytes: 128
#include <iostream>
#include<iomanip>
#include <cmath>
#include <climits>
#include <algorithm>
#include <stdio.h>
#include <vector>
#include <queue>
#include <tuple>
#include <map>
#include <list>
#include <string>
#include <numeric>
#include <utility>
#include <cfloat>
#include <set>

using namespace std;

int sqrtN = 512;
struct SqrtDecomposition{
    int N, K;
    vector <long long> data;
    vector <long long> bucketAdded;
    
    SqrtDecomposition(int n){
        N = n;
        K = (N + sqrtN - 1) / sqrtN;
        data.assign(N, 0);
        bucketAdded.assign(K, 0);
    }

    long long get(int x){
        return data[x] + bucketAdded[x / sqrtN];
    }

    void add(int x, int y, int a){
        if(y - x < sqrtN){
            for(int i = x; i < y; i++){
                data[i] += a;
            }
            return;
        }
        for(int i = x / sqrtN + 1; i < y / sqrtN; i++){
            bucketAdded[i] += a;
        }

        for(int i = x; i < (x / sqrtN + 1) * sqrtN; i++){
            data[i] += a;
        }
        for(int i = y / sqrtN * sqrtN; i < y; i++){
            data[i] += a;
        }
    }
    
};

int main(){
    int n;
    int q;
    cin >> n >> q;
    SqrtDecomposition sq(n);
    for(int i = 0; i < q; i++){
        int com;
        int x;
        int y;
        int a;
        cin >> com;
        if(com == 0){
            cin >> x >> y >> a;
            sq.add(x - 1, y, a);
        } else {
            cin >> x;
            cout << sq.get(x - 1) << endl;
        }
    }
    return 0;
}


Measured memory_bytes: 3552
n = gets.to_i

list = []
order = 0
n.times do
  s, p = gets.chomp.split
  p = p.to_i
  
  order += 1
  
  list << [s, p, order]
end

list.sort! do |a, b|
  (a[0] <=> b[0]).nonzero? || (b[1] <=> a[1])
end

list.each do |s, p, order|
  puts order
end

Measured memory_bytes: 1788
#include<bits/stdc++.h>
#include<algorithm>
using namespace std;
#define _GLIBCXX_DEBUG
#define acc_io cin.tie(0);ios::sync_with_stdio(false)
#define MOD 1e9+7
#define ll long long
#define all(x) x.begin(),x.end()
#define vvl vector<vector<ll>>
#define vl  vector<ll>
#define rep(i,sta,end) for(ll i=sta;i<end;i++)
//name[i]   -> vl  name(i)
//name[i][j]-> vvl name(i,vl(j))
//or-> ||

signed main(){
	acc_io;
	ll n;
	cin>>n;
  	if(n%2!=0)n++;
	cout<<(n/2-1)<<endl;
	return 0;
}


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

int main(){

    int h,w,i,j,i2,j2;

    while(1){

      scanf("%d %d",&h,&w);

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

        for(i=1;i<=h;i++){
          for(j=1;j<=w;j++){
          i2 = i%2;
          j2 = j%2;
           
          if(i2==1 && j2==1) printf("#");
          else if(i2==0 && j2==0) printf("#");
          else printf(".");

          }
          printf("\n");
        }

        printf("\n");

    }

    return 0;

}


Measured memory_bytes: 2104
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int n;
vector< string > s;
vector< int > len;
vector< vector< int > > mem;
long long ans = 0;
void f(int lft, int rit, int lv){
    // printf("%*s%d-%d, %d\n", lv, "", lft, rit, lv);
    if(lft >= rit) return;
    for(int i=lft;i<=rit;i++){
        if(len[i] == lv+1){
            int v = s[i][lv] - 'a';
            for(int j=lft;j<=rit;j++){
                if(j != i && ((mem[j][lv]>>v)&1) == 1){
                    ans++;
                }
            }
        }
    }

    for(int i=lft;i<=rit;i++){
        if(len[i] == lv+1) continue;
        int j = i;
        while(j+1 <= rit && len[j+1] > lv+1 && s[j+1][lv] == s[i][lv]) j++;
        f(i, j, lv+1);
        i = j;
    }
}
int main(void){
    cin >> n;
    for(int i=0;i<n;i++){
        string t;
        cin >> t;
        reverse(t.begin(), t.end());
        s.push_back(t);
    }
    sort(s.begin(), s.end());
    len.assign(n, 0);
    mem.assign(n, vector<int>());
    for(int i=0;i<n;i++){
        len[i] = s[i].length();
        mem[i].assign(len[i]+1, 0);
        for(int j=len[i]-1;j>=0;j--){
            mem[i][j] = mem[i][j+1] | (1<<(s[i][j]-'a'));
        }
    }
    // for(int i=0;i<n;i++) cout << s[i] << endl;
    f(0, n-1, 0);
    cout << ans << endl;
}


Measured memory_bytes: 20116
#!/usr/bin/python

import sys

TOKENS = ["dream", "dreamer", "erase", "eraser"]

def check(s):
    token = s

    while token:
        if token in TOKENS:
            return "YES"

        if len(token) > 5 and token[-5:] in [TOKENS[0], TOKENS[2]]:
            token = token[0:-5]
        elif len(token) > 6 and token[-6:] == TOKENS[3]:
            token = token[0:-6]
        elif len(token) > 7 and token[-7:] == TOKENS[1]:
            token = token[0:-7]
        else:
            return "NO"

def main(argv):
    for line in sys.stdin:
        print check(line.rstrip("\n"))

if __name__ == "__main__":
    main(sys.argv)

Measured memory_bytes: 3024
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=200005;
int flag[N],f[N],c[N],dp[N],x,y,n,m,id[N],rk[N],ne[N],fi[N],zz[N],tot,size[N],a[N],b[N];
vector<int> G[N];
int find(int x){
	if (x==f[x])return x;
	return f[x]=find(f[x]);
}
int cmp(int x,int y){
	return c[x]<c[y];
}
void jb(int x,int y){
	ne[++tot]=fi[x];
	fi[x]=tot;
	zz[tot]=y;
}
void dfs1(int x){
	size[x]=b[x];
	for (int i=0;i<G[x].size();i++)dfs1(G[x][i]),size[x]+=size[G[x][i]];
}
void dfs2(int x){
	if (!G[x].size()){
		dp[x]=b[x]+c[x];
		return;
	}
	dp[x]=1e18;
	for (int i=0;i<G[x].size();i++)dfs2(G[x][i]),dp[x]=min(dp[x],max(c[x],dp[G[x][i]])+size[x]-size[G[x][i]]);
}
signed main(){
	scanf("%lld%lld",&n,&m);
	for (int i=1;i<=n;i++)scanf("%lld%lld",&a[i],&b[i]),c[i]=max(a[i]-b[i],0ll);
	for (int i=1;i<=n;i++)f[i]=i,id[i]=i;
	while (m--){
		scanf("%lld%lld",&x,&y);
		jb(x,y);jb(y,x);
	}
	sort(id+1,id+n+1,cmp);
	for (int i=1;i<=n;i++)rk[id[i]]=i;
	for (int i=1;i<=n;i++)
		for (int j=fi[id[i]];j;j=ne[j]){
			x=find(id[i]),y=find(zz[j]);
			if (id[i]!=y&&rk[x]>rk[y])G[id[i]].push_back(y),f[y]=id[i],flag[y]=1;
		}
	int root=0;
	for (int i=1;i<=n;i++)
		if (!flag[i])root=i;
	dfs1(root);
	dfs2(root);
	printf("%lld\n",dp[root]);
}


Measured memory_bytes: 28544
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <map>
#include <cmath>
#include <numeric>
#include <iomanip>
#include <set>
#include <string.h>

using namespace std;

typedef long long ll;

#define REP(i,n) for(ll (i)=0;(i)<(n);(i)++)
#define REP3(i,st,en) for(ll (i)=(st);(i)<(en);(i)++)

using P = pair<ll, ll>;
const int MOD = 1e9+7;
const ll INF = 1e+14;
const double PI = 3.14159265349;




int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  ll N;
  cin >> N;
  vector<ll> A(N), B(N), C(N-1);
  REP(i,N) { cin >> A[i]; A[i]--; }
  REP(i,N) { cin >> B[i]; }
  REP(i,N-1) { cin >> C[i]; }


  ll ans = accumulate(B.begin(), B.end(), 0);
  REP(i,N-1){
    if (A[i+1]-A[i]==1) {
        ans += C[A[i]];
    }
  }
  cout << ans << "\n";
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int n, x, c, m, i=0;
char s[1005];
int main(){
	scanf("%d", &n);
	scanf("%s", s);
	m=strlen(s);
	if(m>n){
		for(i=0; i<=n-1; i++){
			printf("%c", s[i]);
		}
		printf("...");	
	} 
	else printf("%s", s);
	return 0;
}

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

long long sum = 100L;
long long x;
int t = 0;

int main()
{
	cin >> x;
	long long s;
	while(1)
	{
		s = sum / 100L;
		sum += s;
		t++;
		if(sum >= x) {cout << t; return 0;}
	}
}

Measured memory_bytes: 3636
#include <bits/stdc++.h>
#define int long long
#define INT_MAX INT64_MAX
#define INT_MIN INT64_MIN
#define PI 3.14159265358979323846
#define CLK clock_t clk = clock();//Start of main
#define OCLK cerr << "Time (in ms): " << (double)(clock() - clk) * 1000.0 / CLOCKS_PER_SEC << '\n';//End of main
#define MOD 1000000007
/* DEFINE cout */
#define pln cout << "===============================\n"
#define on cout<<"\n"
#define os cout<<" "
#define o2(a,b) cout<<a<<" "<<b
#define o(a) cout << a
#define bitcount __builtin_popcount
/* DEFINE cout */
#define endl "\n"
#define fastio ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);//fastio
using namespace std;
struct hash_pair { // use pair as key in unordered_map<pair<int,int>,int,hash_pair>;
    template <class T1, class T2>
    size_t operator()(const pair<T1, T2>& p) const
    {
        auto hash1 = hash<T1>{}(p.first);
        auto hash2 = hash<T2>{}(p.second);
        return hash1 ^ hash2;
    }
};
bool prime[10000001];
int P=MOD-2;
int factorial[10000001]={0};
int powerFunction(int x,int y){
    int res = 1;
    int p = MOD;
    x = x % p;
    while (y > 0){
        if (y & 1)
            res = (res*x) % p;
        y = y>>1;
        x = (x*x) % p;
    }
    return res;
}
void sieveFunction(int maxLimit){
    memset(prime, true, sizeof(prime));
    prime[0] = prime[1]=false;
    for(int i=2; maxLimit >= i ; i++){
        if(prime[i]){
            for(int j=2*i ; maxLimit >= j ; j+=i)
                prime[j]=false;
        }
    }
}
void factorialFunction(int maxLimit){
    factorial[0]=1;
    for(int i=1 ; i <= maxLimit ; i++)
        factorial[i]=(factorial[i-1]*i)%MOD;
    return;
}
int gcd(int a, int b){
    if (b == 0)
        return a;
    return gcd(b, a % b);
}
signed main(){
    int n;
    cin >> n;
    int arr[n];
    map<int, int> mp;
    int s = 0;
    for(int i=0; n>i; i++){
        cin >> arr[i];
        s += arr[i];
        mp[arr[i]]++;
    }
    int q;
    cin >> q;
    while(q--){
        int b, c;
        cin >> b >> c;
        int cnt = mp[b];
        mp[b] = 0;
        s -= cnt*b;
        mp[c] += cnt;
        s += c*cnt;
        cout << s << endl;
    }
}






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

int main() {
  int N, M;
  cin >> N >> M;

  vector<pair<int64_t, int>> v;
  for(int i = 0; i < N; i++){
    int A, B;
    cin >> A >> B;

    v.push_back(make_pair(A, B));
  }

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

  int64_t ans = 0;
  int count = 0;
  
  for (auto iter = v.begin(); iter != v.end(); iter++) {
    for(int i = 0; i < iter->second; i++){
      if(count == M){
        break;
      }
      else{
        ans += iter->first;
        count++;
      }
    }
  }

  cout << ans << endl;
}

Measured memory_bytes: 2420
#include<iostream>
#include<string>
using namespace std;
int x[99][99];
int H, W, CX, CY, CD;
int dy[4] = { -1,0,1,0 };
int dx[4] = { 0,1,0,-1 };
char T[9] = ".*#-^>v<";
int main() {
	int U; cin >> U;
	for (int i = 0; i < U; i++) {
		if (i) cout << endl;
		cin >> H >> W;
		for (int i = 0; i < 99; i++) {
			for (int j = 0; j < 99; j++) x[i][j] = 2;
		}
		for (int i = 1; i <= H; i++) {
			for (int j = 1; j <= W; j++) {
				char c; cin >> c;
				for (int k = 0; k < 8; k++) {
					if (T[k] == c) x[i][j] = k;
				}
				if (x[i][j] >= 4) {
					CY = i; CX = j; CD = x[i][j] - 4;
					x[i][j] = 0;
				}
			}
		}
		int P; cin >> P;
		string S; cin >> S;
		for (int i = 0; i < S.size(); i++) {
			if (S[i] == 'U') CD = 0;
			if (S[i] == 'R') CD = 1;
			if (S[i] == 'D') CD = 2;
			if (S[i] == 'L') CD = 3;
			if (S[i] == 'S') {
				int DY = CY, DX = CX;
				while (true) {
					if (x[DY][DX] == 1) { x[DY][DX] = 0; break; }
					if (x[DY][DX] == 2) { break; }
					DY += dy[CD]; DX += dx[CD];
				}
			}
			else {
				if (x[CY + dy[CD]][CX + dx[CD]] == 0) {
					CY += dy[CD]; CX += dx[CD];
				}
			}
		}
		for (int i = 1; i <= H; i++) {
			for (int j = 1; j <= W; j++) {
				if (CY == i && CX == j) { cout << T[CD + 4]; }
				else { cout << T[x[i][j]]; }
			}
			cout << endl;
		}
	}
	return 0;
}

Measured memory_bytes: 1240
/*	MASTER HAS FAILED MORE TIMES
	THAN BEGINNER HAS EVER TRIED
*/

#include <bits/stdc++.h>

using namespace std;

#define endl            '\n'
#define mem(a, n)       memset(a, n, sizeof(a))
#define repeat(i, n)    for(int i=0; i<n; i++)
#define Unique(n)       (n).erase(unique(all(n)), (n).end())
#define isPowerOfTwo(n) (n && !(n & (n - 1)))
#define NumofDigits(n)  ((int)log10(n)+1)
#define all(a)          a.begin(), a.end()

typedef long long ll;
typedef long double ld;

int sieve(int n);
unsigned long long pow(long long base, long long power);
long long gcd(long long a, long long b){ return a%b ? gcd(b, a%b) : b; }
long long lcm(long long a, long long b){ return a*b/gcd(a, b); }

void quicken(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); }
void file(){
    #ifdef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif /*ONLINE_JUDGE*/
}

int main(){
    quicken();

    int arr[3];
    repeat(i, 3) cin >> arr[i];
    sort(arr, arr+3);

    if((arr[0]==arr[1] && arr[0]!=arr[2])
        || (arr[1]==arr[2] && arr[1]!=arr[0]))
        cout << "Yes";
    else cout << "No";

    return 0;
}

unsigned long long pow(long long base, long long power){ /// mod?
    if(power==0) return 1;
    if(power==1) return base;

    unsigned long long ans = pow(base, power/2); /// mod?
    ans *= ans; /// ((ans%mod)*(ans%mod))%mod;

    if(power&1) return ans*base; /// ((ans%mod)*(base%mod))%mod;
    return ans;
}

int sieve(int n){
    int c = 0;
    vector<bool> isPrime(n+1, true);
    isPrime[0] = isPrime[1] = 0;

    for(long long i=2; i*i<=n; i++)
        if(isPrime[i])
            for(long long j=i*2; j<=n; j+=i)
                isPrime[j] = 0;
    repeat(i, n+1)
        if(isPrime[i]) c++;
    return c; /// primeCount [1:n]
}


Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#include <iomanip>
#include <iostream>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <map>
#include <tuple>
#include <climits>
#include <algorithm>
#include <cmath>
using namespace std;

typedef long long LL;
typedef vector<int> VI;
typedef vector<double> VD;
typedef vector<LL> VLL;
typedef vector<string> VS;
typedef vector<bool> VB;
typedef vector<vector<int>> VVI;
typedef vector<vector<long long>> VVLL;
typedef vector<vector<bool>> VVB;
typedef vector<vector<double>> VVD;

#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define all(a) (a).begin(),(a).end()

const int MOD = 1000000007;

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;
}

void debug(VI &arr){
	int n=arr.size();
	rep(i,n){
		cout<<arr.at(i)<<endl;
	}
}

void debug(VVI &board){
	int h = board.size();
	int w = board.at(0).size();
	rep(i,h){
		rep(j,w){
			cout << board.at(i).at(j) << " ";
		}
		cout<<endl;
	}
}

void debug(VVLL &board){
	int h = board.size();
	int w = board.at(0).size();
	rep(i,h){
		rep(j,w){
			cout<<board.at(i).at(j)<<" ";
		}
		cout<<endl;
	}
}

void debug(VS &board){
	int h = board.size();
	rep(i,h){
		cout<<board.at(i)<<endl;
	}
	return;
}

LL gcd(LL a,LL b){
	return b==0?a:gcd(b,a%b);
}

LL lcm(LL a,LL b){
	return a*b/gcd(a,b);
}

int main(){
	//cout<<fixed;
	//cout<<setprecision(9)<<...
	LL x;
	cin>>x;
	for(LL i=-118;i<=119;i++){
		for(LL j=-119;j<=118;j++){
			if(i*i*i*i*i-j*j*j*j*j==x){
				cout<<i<<" "<<j<<endl;
				return 0;
			}
		}
	}
	return 0;
}


Measured memory_bytes: 3636
import java.util.*;

class Main{
    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        Map<Integer, Integer> map = new HashMap<>();
        int n = sc.nextInt();
        for(int i = 0; i < n; i++){
            int a = sc.nextInt();
            if(map.containsKey(a)){
                map.put(a,map.get(a)+1);
            }else {
                map.put(a,1);
            }
        }
        int count = 0;
        for(int a: map.keySet()){
            //System.out.println(a + " : " + map.get(a));
            if(a <= map.get(a)){
                count += map.get(a) - a;
            }else {
                count += map.get(a);
            }
        }
        System.out.println(count);
    }
}

Measured memory_bytes: 62072
#include <bits/stdc++.h>
// iostream is too mainstream
#include <cstdio>
// bitch please
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <list>
#include <cmath>
#include <iomanip>
#include <time.h>
#define dibs reserve
#define OVER9000 1234567890123456789LL
#define ALL_THE(CAKE,LIE) for(auto LIE =CAKE.begin(); LIE != CAKE.end(); LIE++)
#define tisic 47
#define soclose 1e-8
#define chocolate win
// so much chocolate
#define patkan 9
#define ff first
#define ss second
#define abs(x) ((x < 0)?-(x):x)
#define uint unsigned int
#define dbl long double
#define pi 3.14159265358979323846
using namespace std;
// mylittledoge

typedef long long cat;

#ifdef DONLINE_JUDGE
	// palindromic tree is better than splay tree!
	#define lld I64d
#endif

int main() {
	cin.sync_with_stdio(0);
	cin.tie(0);
	cout << fixed << setprecision(10);
	string S;
	cin >> S;
	if(S.length() >= 4 && S.substr(0,4) == "YAKI") cout << "Yes\n";
	else cout << "No\n";
	return 0;}

// look at my code
// my code is amazing


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

int main(){
  int a = 0 , m = 0, N;
  cin >> N;
  vector<int> H(N);
  for (int i = 0; i < N; i++){
    cin >> H.at(i);
  }
  if (N > 1) {
    for (int j = 0; j < N-1; j++){
      if (H.at(j) >= H.at(j+1) ) {
        a++;
      }
      else if (H.at(j) < H.at(j+1) ) {
        m = max(m,a);
        a = 0;
      }
    }
    m = max(m,a);
  }
  cout << m << endl;
}

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

#define int ll

#define pb push_back
#define eb emplace_back
#define all(v) (v).begin(), (v).end() 
#define sz(v) (int)((v).size())
#define fs first
#define sd second

typedef long long ll;

typedef pair < int, int > pi;
typedef pair < pi, int > ppi;

typedef vector < int > vi;
typedef vector < vector < int > > vvi;
typedef vector < pi > vpi;
typedef vector < vpi > vvpi;
typedef vector < ppi > vppi;

void fast() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}

vector<string> vec_splitter(string s) {
	s += ',';
	vector<string> res;
	while(!s.empty()) {
		res.push_back(s.substr(0, s.find(',')));
		s = s.substr(s.find(',') + 1);
	}
	return res;
}

void debug_out(
vector<string> __attribute__ ((unused)) args,
__attribute__ ((unused)) int idx, 
__attribute__ ((unused)) int LINE_NUM) { cerr << endl; } 
template <typename Head, typename... Tail>
void debug_out(vector<string> args, int idx, int LINE_NUM, Head H, Tail... T) {
	if(idx > 0) cerr << ", "; else cerr << "Line(" << LINE_NUM << ") ";
	stringstream ss; ss << H;
	cerr << args[idx] << " = " << ss.str();
	debug_out(args, idx + 1, LINE_NUM, T...);
}

#ifdef LOCAL
#define debug(...) debug_out(vec_splitter(#__VA_ARGS__), 0, __LINE__, __VA_ARGS__)
#else
#define debug(...) 42
#endif

double get_time() {
	return 1.0 * clock() / CLOCKS_PER_SEC;
}

const int MAX = 13;
int n, m, x;
int c[MAX];
int a[MAX][MAX];

int32_t main() {
	cin >> n >> m >> x;
	for(int i = 0; i < n; i++) {
		cin >> c[i];
		for(int j = 0; j < m; j++)
			cin >> a[i][j];
	}
	int res = 1E9 + 5;
	int allmask = (1 << n) - 1;
	for(int i = 0; i <= allmask; i++) {
		vi v;
		for(int bit = 0; bit < n; bit++) {
			if(i & (1 << bit))
				v.pb(bit);
		}
		int cost = 0;
		bool ok = 1;
		vi skill(m);
		for(int book : v) {
			cost += c[book];
			for(int j = 0; j < m; j++)
				skill[j] += a[book][j];
		}
		for(int i = 0; i < m; i++)
			ok &= (skill[i] >= x);
		if(ok)
			res = min(res, cost);
	}
	if(res > int(1E9))
		res = -1;
	cout << res << '\n';
}


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

int s[5];
char op[5];

void solve(int index, int cur_sum) {
    if (index == 3) {
        if (cur_sum == 7) {
            for(int i = 0; i < 4; ++i) {
                if (i > 0) cout << op[i];
                cout << s[i];
            }
            cout << "=7";
            exit(0);
        }
        return;
    }
    // +
    op[index + 1] = '+';
    solve(index + 1, cur_sum+s[index + 1]);        

    //-
    op[index + 1] = '-';
    solve(index + 1, cur_sum-s[index + 1]);   
}

int main () {
    for(int i = 0; i < 4; ++i) {
        char ch; cin >> ch;
        s[i] = ch - '0';
    }
    solve(0, s[0]);
}


Measured memory_bytes: 3604
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
int main() {
  int n;
  scanf("%d", &n);
  vector<int> a(n);
  rep(i,n)
  {
    scanf("%d", &a[i]);
    a[i] -= i + 1;
  }
  sort(a.begin(), a.end());
  int b = a[n / 2];
  long long ans = 0;
  rep(i,n)
    ans += abs(b - a[i]);
  printf("%lld", ans);
  return 0;
}


Measured memory_bytes: 1024
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		final String s = sc.next();

		final String sList[] = s.split("");

		if (!sList[0].equals("A")) {
			java.lang.System.out.println("WA");
			return;
		}

		int count = 2;
		final int maxcount = s.length() - 2;
		List<String> list = new ArrayList<String>();
		while (count <= maxcount) {
			list.add(sList[count]);
			count++;
		}
		int cCount = 0;
		for (final String item : list) {
			if (item.equals("C")) {
				cCount++;
			}
		}
		if (cCount > 1 || cCount == 0) {
			java.lang.System.out.println("WA");
			return;
		}

		int upperCount = 0;
		for (final String item2 : sList) {
			if (Character.isUpperCase(item2.charAt(0))) {
				upperCount++;
			}

		}

		if (upperCount > 2) {
			java.lang.System.out.println("WA");
			return;
		}

		java.lang.System.out.println("AC");

	}

}


Measured memory_bytes: 21844
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#include <numeric>
typedef long long Int;
#define rep(i,a,b) for(Int i=a;i<b;++i)
#define rrep(i,a,b) for(Int i=a;i>=b;--i)
using namespace std;

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

    int A, B, C; cin >> A >> B >> C;
    if ((A==5 and B==5 and C==7) or (A==5 and B==7 and C==5) or (A==7 and B==5 and C==5)) cout << "YES" << endl;
    else cout << "NO" << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define N 100001
#define ll long long
ll suma, sumb, sumc;
ll maxa[N], maxb[N];
int numa, numb, numc;
struct faner {
    int a, b;
} s[N];
bool cmp(faner a, faner b) { return a.a - a.b > b.a - b.b; }
priority_queue<ll, vector<ll>, greater<ll> > quea, queb;
int main() {
    scanf("%d%d%d", &numa, &numb, &numc);
    int n = numa + numb + numc;
    for (int i = 1, a, b, c; i <= n; i++) {
        scanf("%d%d%d", &a, &b, &c);
        s[i] = {a -= c, b -= c}, sumc += c;
    }
    sort(s + 1, s + n + 1, cmp);
    for (int i = 1; i <= n - numb; i++) {
        if (i <= numa) {
            suma += s[i].a;
            quea.push(s[i].a);
        } else if (quea.top() < s[i].a) {
            suma += s[i].a - quea.top();
            quea.pop();
            quea.push(s[i].a);
        }
        maxa[i] = suma;
    }
    for (int i = n; i > numa; i--) {
        if (n - i < numb) {
            sumb += s[i].b;
            queb.push(s[i].b);
        } else if (queb.top() < s[i].b) {
            sumb += s[i].b - queb.top();
            queb.pop();
            queb.push(s[i].b);
        }
        maxb[i] = sumb;
    }
    ll ans = maxa[numa] + maxb[numa + 1];
    for (int i = numa + 1; i <= n - numb; i++)
        ans = max(ans, maxa[i] + maxb[i + 1]);
    printf("%lld\n", ans + sumc);
    return 0;
}

Measured memory_bytes: 2972
/**
 *      purpose : 
 *      author  : 𝒌𝒚𝒐𝒎𝒖𝒌𝒚𝒐𝒎𝒖𝒑𝒖𝒓𝒊𝒏
 *      created : 
**/

#include <iostream>
#include <deque>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <complex>
#include <numeric>
#include <bitset>
#include <cassert>
#include <cctype>
#include <functional>
#include <iomanip>
#include <random>
#include <utility>

using namespace std;

using int64 = long long;
#define debug(_) cerr << #_ << ": " << (_) << '\n'
template<typename T> inline void chmin(T &a, T b) { if (a > b) a = b; return; }
template<typename T> inline void chmax(T &a, T b) { if (a < b) a = b; return; }
template<typename T> ostream& operator<<(ostream& os, const vector<T>& vec) { os << '{'; for (size_t i = 0; i < vec.size(); ++i) { os << vec[i]; if (i != vec.size() - 1) os << ','; } os << '}'; return os; }
template<typename T, typename U> ostream& operator<<(ostream& os, const pair<T, U>& p) { return os << '{' << p.first << " " << p.second << '}'; }

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  int n; cin >> n;
  string s; cin >> s;
  if (s.size() & 1) {
    cout << "No" << endl;
    return 0;
  }

  string t = s.substr(0, s.size() / 2);
  //debug(t);
  t += t;
  //debug(t);
  if (s == t) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }

  return 0;
}

Measured memory_bytes: 256
class DualSegmentTree():

    def __init__(self, n, op, e):
        """
        :param n: 配列の要素数
        :param op: 作用素（モノイド＝結合則＋単位元存在）
        :param e:  単位元
        """
        self.n = n
        self.op = op
        self.e = e
        self.depth = (self.n - 1).bit_length()
        self.size = 1 << self.depth
        self.lazy = [self.e] * ((self.size << 1) + 1)

    def built(self, array):
        """
        arrayを初期値とするセグメント木を構築
        """
        n, size, lazy = self.n, self.size, self.lazy
        for i in range(n):
            lazy[size + i] = array[i]

    def update(self, l, r, x):
        """
        半開区間 [l, r) の各々の要素 a に op(x, a)を作用させる （ 0-indexed ）　（ O(logN) ）
        """
        op, lazy = self.op, self.lazy
        l += self.size
        r += self.size
        self.propagate(l//(l&-l))
        self.propagate((r//(r&-r))-1)
        while l < r:
            if r&1:
                r -= 1              # 半開区間なので先に引いてる
                lazy[r] = op(x, lazy[r])
            if l&1:
                lazy[l] = op(x, lazy[l])
                l += 1
            l >>= 1
            r >>= 1

    def propagate(self, i):
        """
        根から葉に伝搬させる。可換モノイドの場合は更新時の伝搬をサボれる。　（ O(logN) ）
        """
        e, op, lazy = self.e, self.op, self.lazy
        for k in range(i.bit_length()-1, 0,-1):
            x = i>>k
            if lazy[x] == e:
                continue
            lazy[(x<<1)|1] = op(lazy[x], lazy[(x<<1)|1])
            lazy[x<<1] = op(lazy[x], lazy[x<<1])
            lazy[x] = e

    def get(self, i):
        """
        i 番目の値を取得（ 0-indexed ） ( O(logN) )
        """
        i += self.size
        self.propagate(i)
        return self.lazy[i]

    def __getitem__(self, i):
        return self.get(i)

    def __iter__(self):
        n, size, e, op, lazy = self.n, self.size, self.e, self.op, self.lazy
        for x in range(1, size):
            if lazy[x] == e:
                continue
            lazy[(x<<1)|1] = op(lazy[x], lazy[(x<<1)|1])
            lazy[x<<1] = op(lazy[x], lazy[x<<1])
            lazy[x] = e
        for a in lazy[size:size+n]:
            yield a

    def __str__(self):
        n, size, e, op, lazy = self.n, self.size, self.e, self.op, self.lazy
        for x in range(1, size):
            if lazy[x] == e:
                continue
            lazy[(x << 1) | 1] = op(lazy[x], lazy[(x << 1) | 1])
            lazy[x << 1] = op(lazy[x], lazy[x << 1])
            lazy[x] = e
        return str(lazy[size:size + n])

##################################################################################################################
import sys
from bisect import *
input = sys.stdin.readline

N, Q = map(int, input().split())

e = -1
op = lambda x, y: x if x != e else y
st = DualSegmentTree(Q, op, e)

Qu = [list(map(int, input().split())) for _ in range(N)]
Qu.sort(key=lambda x:x[2], reverse=True)

D = [int(input()) for _ in range(Q)]

for q in Qu:
    S, T, X = q
    L = bisect_left(D,S-X)
    R = bisect_left(D,T-X)
    st.update(L, R, X)
print(*st, sep="\n")


Measured memory_bytes: 146280
n = gets.to_i
a, b = Array.new(n) { gets.split.map(&:to_i) }.transpose

a.sort!
b.sort!
med_a = n.even? ? (a[n / 2] + a[n / 2 - 1]) / 2.0 : a[n / 2]
med_b = n.even? ? (b[n / 2] + b[n / 2 - 1]) / 2.0 : b[n / 2]

puts n.even? ? ((med_b - med_a) * 2 + 1).to_i : med_b - med_a + 1

Measured memory_bytes: 33132
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define rep2(i, s, n) for (ll i = (s); i < (ll)(n); i++)
#define all(v) v.begin(), v.end()
#define sz(v) v.size()
#define INF 100000000000000 //10^14 100兆
// aよりもbが大きいならばaをbで更新する
// (更新されたならばtrueを返す)
template <typename T>
bool chmax(T &a, const T& b) {
  if (a < b) {
    a = b;  // aをbで更新
    return true;
  }
  return false;
}
// aよりもbが小さいならばaをbで更新する
// (更新されたならばtrueを返す)
template <typename T>
bool chmin(T &a, const T& b) {
  if (a > b) {
    a = b;  // aをbで更新
    return true;
  }
  return false;
}

unsigned euclidean_gcd(unsigned a, unsigned b) {
  if(a < b) return euclidean_gcd(b, a);
  unsigned r;
  while ((r=a%b)) {
    a = b;
    b = r;
  }
  return b;
}

int main(){
  ll N;
  string S;
  cin >> N >> S;
  vector<ll> R(N+1, 0), G(N+1, 0), B(N+1, 0);
  rep(i, N){
    if(S.at(i) == 'R'){
      R.at(i+1) = R.at(i)+1;
      G.at(i+1) = G.at(i);
      B.at(i+1) = B.at(i);
    }
    if(S.at(i) == 'G'){
      R.at(i+1) = R.at(i);
      G.at(i+1) = G.at(i)+1;
      B.at(i+1) = B.at(i);
    }
    if(S.at(i) == 'B'){
      R.at(i+1) = R.at(i);
      G.at(i+1) = G.at(i);
      B.at(i+1) = B.at(i)+1;
    }
  }
  ll ans = 0;
  rep2(i, 1, N-1){
    if(S.at(i) == 'R'){
      ll eq = 0;
      rep2(j, 1, min(i, N-i-1)+1){
        if(S.at(i-j) == 'G' && S.at(i+j) == 'B'){
          eq++;
        }
        if(S.at(i-j) == 'B' && S.at(i+j) == 'G'){
          eq++;
        }
      }
      ans += G.at(i) * (B.at(N) - B.at(i+1)) + B.at(i) * (G.at(N) - G.at(i+1)) - eq;
    }
    if(S.at(i) == 'G'){
      ll eq = 0;
      rep2(j, 1, min(i, N-i-1)+1){
        if(S.at(i-j) == 'B' && S.at(i+j) == 'R'){
          eq++;
        }
        if(S.at(i-j) == 'R' && S.at(i+j) == 'B'){
          eq++;
        }
      }
      ans += B.at(i) * (R.at(N) - R.at(i+1)) + R.at(i) * (B.at(N) - B.at(i+1)) - eq;
    }
    if(S.at(i) == 'B'){
      ll eq = 0;
      rep2(j, 1, min(i, N-i-1)+1){
        if(S.at(i-j) == 'R' && S.at(i+j) == 'G'){
          eq++;
        }
        if(S.at(i-j) == 'G' && S.at(i+j) == 'R'){
          eq++;
        }
      }
      ans += R.at(i) * (G.at(N) - G.at(i+1)) + G.at(i) * (R.at(N) - R.at(i+1)) - eq;
    }
  }
  cout << ans << endl;
}

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

const int N = 5e5+10;
char a[N];

int32_t main(){
    cin>>a;
    //cout<<a<<endl;
    int len = strlen(a);
    int sum1 = 0, sum2 = 0;
    int ans = 0;
    bool f=0;
    if(a[len-1]=='>') a[len]='<';
    if(a[len-1]=='<') a[len]='>';
    for(int i = 0; i <= len; i++){
        if(a[i]=='<'){
            if(sum2){
                if(sum2 > sum1){
                    ans += (1+sum2)*sum2/2;
                    sum2=0;
                    sum1=0;
                }else{
                    ans += (1+sum2-1)*(sum2-1)/2;
                    ans += sum1;
                    sum2=0;
                    sum1=0;
                }
                f=0;
            }
            sum1++;
        }else{
            if(!f){
                ans += (1+sum1-1)*(sum1-1)/2;
                f=1;
            }
            sum2++;
        }
    }
    if(a[len]=='<')cout<<ans;
    else cout<<ans+sum1;
    return 0;
}

Measured memory_bytes: 768
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5 + 5;
vector<int> g[N];
int vis[2][N];
int n, m, sz[2];
void dfs(int u,int parity) {
    sz[parity]++;
    vis[parity][u] = 1;
    for(int i = 0 ; i < g[u].size() ; ++i)  {
        int v = g[u][i];
        for(int j = 0 ; j < g[v].size() ; ++j)  {
            int z = g[v][j];
            if(vis[parity][z])
                continue;
            dfs(z,parity);
        }
    }
}
signed main()  {
    ios_base::sync_with_stdio(false);   cin.tie(0);
    cin >> n >> m;
    for(int i = 1 ; i <= m ; ++i)  {
        int x, y;   cin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    sz[0] = 0;  dfs(1,0);
    sz[1] = 0;  dfs(g[1][0],1);
    int ans =  sz[0] * (n - sz[0]);
        ans += sz[1] * (n - sz[1]);
        ans += (n - 1) * (sz[0] + sz[1] - n);
    cout << (ans / 2) - m << endl;
}

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

#define rep(i, a, b) for (int i = a; i < (int)(b); ++i)
#define rrep(i, a, b) for (int i = b - 1; i >= (int)(a); --i)

using namespace std;

using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;

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

    int n;
    cin >> n;

    vvi g(n, vi(n, INT_MAX));

    rep(i, 0, n) {
        int u, k;
        cin >> u >> k;

        rep(j, 0, k) {
            int v, c;
            cin >> v >> c;
            g[u][v] = c;
        }
    }

    vector<bool> seen(n, false);
    vi ds(n, INT_MAX);

    ds[0] = 0;

    while (true) {
        int minv = INT_MAX;
        int u = -1;

        rep(i, 0, n) {
            if (!seen[i] && ds[i] < minv) {
                minv = ds[i];
                u = i;
            }
        }
        if (u == -1) { break; }
        seen[u] = true;

        rep(v, 0, n) {
            if (!seen[v] && g[u][v] != INT_MAX && ds[v] > minv + g[u][v]) {
                ds[v] = minv + g[u][v];
            }
        }
    }

    rep(i, 0, n) {
        cout << i << " " << ds[i] << endl;
    }

    return 0;
}


Measured memory_bytes: 3156