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

string sum(string s, string t){
    reverse(s.begin(), s.end());
    reverse(t.begin(), t.end());
    
    string res;
    int carry = 0;
    int md = max(t.size(), s.size());
    for(int i=0; i<=md; i++){
        int sc = i<s.size()? s[i]-'0': 0;
        int tc = i<t.size()? t[i]-'0': 0;
        int d = sc + tc + carry;
        char nd = '0' + (d%10);
        if(i == md && nd == '0')
            continue;
        res += nd;
        carry = d/10;
    }
    reverse(res.begin(), res.end());
    return res;
}

int main(){
    string s, t;
    while(cin >> s >> t){
        cout << sum(s, t).size() << endl;
    }
    return 0;
}



Measured memory_bytes: 3140
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,n) for(int i=0;i<n;i++)
#define why(n,x) int n;while(cin >>n,n!=x)
#define iFOR(i,x,n)for(int i=x;i<n;i++)
#define unless(flg) if ( !(flg) )
#define read cin<<
#define echo cout<<
#define fin <<'\n'
#define __ <<" "<<
#define ___ <<" "
#define bash push_back
#define ALL(x) x.begin(),x.end()
#define SWAP(a,b) ((a != b) && (a += b,b = a - b,a -= b))
#define cinf(n,x) for(int UNCH=0;UNCH<(n);UNCH++) cin >> x[UNCH];
#define fcin(n,x) for(int UNCH=1;UNCH<=(n);UNCH++) cin>> x[UNCH];
#define memmin(x) memset((x),-1,sizeof((x)))
#define memzer(x) memset((x), 0,sizeof((x)))
#define meminf(x) memset((x),0x3f,sizeof((x)))
#define int long long
typedef long long ll;
typedef pair < int , int >  pii;
typedef vector < int > vit;
typedef map < string , int > mstit;
typedef vector < pii > vpi ;
typedef greater < pii > gpi;
typedef priority_queue < pii , vpi , gpi > dijk ;
static const signed int INF = 0x3f3f3f3f;
static const signed long long LINF = 0x3f3f3f3f3f3f3f3fLL;
static const signed int SMOD = 1000000007;
static const signed int NMOD = 1000000009;
static const signed int dx[]={1,0,-1,0,1,1,-1,-1};
static const signed int dy[]={0,-1,0,1,-1,1,-1,1};

bool inside(int x,int y,int w,int h){return (x>=0 && y>=0 && x<w && y<h);}
template<class T>T abs(T &x){return x<0 ? -x : x;}
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
int qp(int a,ll b,int mo){int ans=1;do{if(b&1)ans=1ll*ans*a%mo;a=1ll*a*a%mo;}while(b>>=1);return ans;}
int gcd(int a,int b){return b?gcd(b,a%b):a;}



signed main(){
    string str[3];
    FOR(i,3)
        cin >> str[i];
    cout << str[0][0] << str[1][1] << str[2][2] fin;
  
  return 0;
}



struct xyz{ xyz(){ cin.tie(0), ios::sync_with_stdio(false); cout <<fixed<<setprecision(12);};}xyzzy;



Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  int N,M=0,c=0;
  cin>>N;
  vector<string>S(N);
  for(int i=0;i<N;i++)cin>>S.at(i);
  sort(S.begin(),S.end());
  for(int i=1;i<N;i++){
    M=max(M,c);
    if(S.at(i)==S.at(i-1))c++;
    else c=0;
  }
  M=max(M,c);
  for(int i=0;i<N-M;i++)if(S.at(i)==S.at(i+M)){
    cout<<S.at(i)<<endl;
    i+=M;
  }
}


Measured memory_bytes: 14208
#include<iostream>
#include<queue>
#include<cstring>
#include<vector>
#include<string>
#include<map>
using namespace std;
typedef long long ll;
int main()
{
    string ss;
    cin>>ss;
    map<char,int> m;
    for(int i=0;i<ss.size();i++)
        m[ss[i]]++;
    if((m['N']&&!m['S'])||(m['S']&&!m['N']))
        cout<<"No"<<endl;
    else if((m['W']&&!m['E'])||(m['E']&&!m['W']))
        cout<<"No"<<endl;
    else
        cout<<"Yes"<<endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i, N) for (ll i = 0; i < (N); ++i)
#define ALL(x) (x).begin(), (x).end()
#define MOD 1000000007
#define PB push_back
#define MP make_pair
using namespace std;
typedef long long ll;
ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }

//++時計回り --反時計回り
// int dx[4] = {1, 0, -1, 0};
// int dy[4] = {0, 1, 0, -1};

int main() {
  ll N, M;
  cin >> N >> M;
  vector<vector<ll>> v(1e5+1);
  REP(i, N) {
    ll a, b;
    cin >> a >> b;
    v[a].PB(b);
  }
  ll ans = 0;
  priority_queue<ll> pq;
  for (ll i = 1; i <= M; i++) {
    for (auto e : v[i]) pq.push(e);
    if (pq.size() != 0) {
      ans += pq.top();
      pq.pop();
    }
  }
  cout << ans << '\n';
}


Measured memory_bytes: 5632
N =int(input())

A = [int(input()) for _ in range(N)]



def solve(target,min_n):
    if A[target] > min_n:
        return (((A[target]-1)//min_n),max(min_n,2))
    else:
        return (0, max(min_n , A[target]+1))

ans =0
min_n=1
for i in range(N):
    res,min_n =solve(i,min_n)
    #print(res)
    ans +=res

print(ans)

Measured memory_bytes: 7152
public class Main {


  private static void solve() {
    int n = ni();
    int m = ni();
    int[] a = na(m);
    int[] num = {0, 2, 5, 5, 4, 5, 6, 3, 7, 6};

    String[] dp = new String[n + 10];
    dp[0] = "";
    for (int i = 0; i < n; i++) {
      if (dp[i] == null) continue;

      for (int j = 0; j < m; j++) {
        String x = a[j] + dp[i];

        if (compare(x, dp[i + num[a[j]]]) > 0) {
          dp[i + num[a[j]]] = x;
        }
      }
    }

    System.out.println(dp[n]);
  }
  
  private static int compare(String s, String t) {
    if (t == null) {
      return 1;
    }
    if (s.length() != t.length()) {
      return s.length() - t.length();
    } else {
      return s.compareTo(t);
    }
  }

  public static void main(String[] args) {
    new Thread(null, new Runnable() {
      @Override
      public void run() {
        long start = System.currentTimeMillis();
        String debug = args.length > 0 ? args[0] : null;
        if (debug != null) {
          try {
            is = java.nio.file.Files.newInputStream(java.nio.file.Paths.get(debug));
          } catch (Exception e) {
            throw new RuntimeException(e);
          }
        }
        reader = new java.io.BufferedReader(new java.io.InputStreamReader(is), 32768);
        solve();
        out.flush();
        tr((System.currentTimeMillis() - start) + "ms");
      }
    }, "", 64000000).start();
  }

  private static java.io.InputStream is = System.in;
  private static java.io.PrintWriter out = new java.io.PrintWriter(System.out);
  private static java.util.StringTokenizer tokenizer = null;
  private static java.io.BufferedReader reader;

  public static String next() {
    while (tokenizer == null || !tokenizer.hasMoreTokens()) {
      try {
        tokenizer = new java.util.StringTokenizer(reader.readLine());
      } catch (Exception e) {
        throw new RuntimeException(e);
      }
    }
    return tokenizer.nextToken();
  }

  private static double nd() {
    return Double.parseDouble(next());
  }

  private static long nl() {
    return Long.parseLong(next());
  }

  private static int[] na(int n) {
    int[] a = new int[n];
    for (int i = 0; i < n; i++)
      a[i] = ni();
    return a;
  }

  private static char[] ns() {
    return next().toCharArray();
  }

  private static long[] nal(int n) {
    long[] a = new long[n];
    for (int i = 0; i < n; i++)
      a[i] = nl();
    return a;
  }

  private static int[][] ntable(int n, int m) {
    int[][] table = new int[n][m];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        table[i][j] = ni();
      }
    }
    return table;
  }

  private static int[][] nlist(int n, int m) {
    int[][] table = new int[m][n];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        table[j][i] = ni();
      }
    }
    return table;
  }

  private static int ni() {
    return Integer.parseInt(next());
  }

  private static void tr(Object... o) {
    if (is != System.in)
      System.out.println(java.util.Arrays.deepToString(o));
  }
}


Measured memory_bytes: 317652
#include<iostream>
#include<cstdio>
#include<stack>
#include<queue>
#include<algorithm>
#include<string>
#include<set>
#include<map>
#include<vector>
#include<math.h>
#include<tuple>
#include<string.h>
#include <numeric> 
#include<unordered_map>
using namespace std; 
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it)
    *this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define pp(...) "\033[94m [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "]\033[0m"
#define pp1(...) "\033[1;47;35m" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "]\033[0m"
#define dg(x) debug() << pp1(x)
#define dg1(x) debug() << "[line : " << __LINE__ <<"]"<< pp(x)
#define dg2(x,y) debug() << "[line : " << __LINE__ <<"]"<< pp(x) pp(y)
#define dg3(x,y,z) debug() << "[line : " << __LINE__ <<"]"<< pp(x) pp(y) pp(z)
#define dg4(w,x,y,z) debug() << "[line : " << __LINE__ <<"]"<< pp(w) pp(x) pp(y) pp(z)
#define int long long
#define all(x) x.begin() , x.end()
#define clr(x , y) memset(x , y , sizeof x);
#define sz(x) (int)x.size()
template<typename T> void db(T x ){ debug() <<">>> " <<  x; }
template<typename T> void db(T x , T y){ debug() <<">>> " <<  x <<" , "<< y; }
template<typename T> void db(T x , T y , T z){ debug() <<">>> "<< x <<" , "<< y <<" , "<< z; }
template<typename T> void db(T x , T y , T z , T a){ debug() <<">>> "<< x <<" , " << y <<" , "<< z <<" , "<< a; }
const int xx = 2e5;
const int Mod = 1e9 + 7;
const int inf = 1e18;
const int Maxn = 20010;

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  vector<int>a(n);
  int gc = 0;
 unordered_map<int,int>Cnt;
  for(int i = 0; i < n; i++) {
    cin >> a[i];
    Cnt[a[i]]++;
    gc = __gcd(a[i] , gc);
  }
  int N = *max_element(all(a));
  dg1(a);
  if(gc > 1) {
    cout << "not coprime" << '\n';
    return 0;
  }
  for(int i = 2; i <= N; i++) {
    int sum = 0;
    for(int j = i; j <= N; j += i) {
      sum += Cnt[j];
    }
    dg2(i , sum);
    if(sum > 1) {
      cout << "setwise coprime" << '\n';
      return 0;
    }
  }
  cout << "pairwise coprime" << '\n';
}

Measured memory_bytes: 50292
#include<iostream>
#include<string>
#include<vector>
#include<queue>
#include<algorithm>
#include<cmath>
typedef long long ll;
#define rep(i,n) for(int i=0;i<(n);i++)
using namespace std;
const ll INF = 1000000007;

int main() {
	int n;
	ll k;
	cin >> n >> k;
	vector<int> a(n);
	rep(i, n) cin >> a[i];
	vector<ll> b(n), c(n);
	for(int i=0;i<n-1;i++) {
		for (int j = i + 1; j < n; j++) {
			if (a[i] > a[j]) b[i]++;
		}
	}
	rep(i, n) {
		rep(j, n) {
			if (a[i] > a[j]) c[i]++;
		}
	}
	ll ans = 0;
	rep(i, n) {
		ans = (ans+(c[i] * ((k * (k - 1) / 2)%INF)) % INF)%INF;
		ans = (ans+((b[i] * k) % INF))%INF;
	}
	cout << ans << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i) 
#define PI acos(-1)

using namespace std;
using ll = long long;
using P = pair<int, int>;

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

    string S;
    cin>>S;

    if (S[0] == S[1] && S[0] == S[2]) cout<<"No"<<endl;
    else cout<<"Yes"<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define int long long
using namespace std;
int a,b;
main()
{
    string s;
    cin>>s;
    for(int i=0;i<s.size();i++){
        if(s[i]=='A')a++;
        else b++;
    }
    if(a&&b)
        cout<<"Yes";
    else
        cout<<"No";
}


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

const int MAXN = 500000;
int seg_tree[26][4 * MAXN];

int n, q;
string s;

void add(int *tree, int v, int tl, int tr, int pos, int val)
{
	if (tl == tr) {
		tree[v] = val;
		return;
	}
	int tm = (tl + tr) / 2;
	if (pos <= tm)
		add(tree, v * 2, tl, tm, pos, val);
	else
		add(tree, v * 2 + 1, tm + 1, tr, pos, val);
	tree[v] = tree[v * 2] + tree[v * 2 + 1];
}

int sum(int *tree, int v, int tl, int tr, int l, int r)
{
	if (l > r)
		return 0;
	if (l == tl && r == tr)
		return tree[v];
	int tm = (tl + tr) / 2;
	return sum(tree, v * 2, tl, tm, l, min(r, tm)) + sum(tree, v * 2 + 1, tm + 1, tr, max(l, tm + 1), r);
}

int main() {
	cin >> n >> s >> q;
	
	for (int i = 0; i < n; ++i)
		add(seg_tree[s[i] - 'a'], 1, 0, n - 1, i, 1);
	
	for (int i = 0; i < q; ++i) {
		int type;
		cin >> type;
		if (type == 1) {
			int pos;
			char c;
			cin >> pos >> c;
			pos--;
			add(seg_tree[s[pos] - 'a'], 1, 0, n - 1, pos, 0);
			s[pos] = c;
			add(seg_tree[s[pos] - 'a'], 1, 0, n - 1, pos, 1);
		} else {
			int l, r, ans = 0;
			cin >> l >> r;
			l--;
			r--;
			for (int j = 0; j < 26; ++j) {
				if (sum(seg_tree[j], 1, 0, n - 1, l, r))
					ans++;
			}
			cout << ans << endl;
		}
		int ans = 0;
		
	}
	
	
	return 0;
}

Measured memory_bytes: 160644
import sys
from sys import stdin

def main():
 
    n = int(stdin.readline().rstrip())
    s = stdin.readline().rstrip()
    MOD=10**9+7
    perm=1
    for i in range(1,n+1):
        perm=perm*i%MOD
    ans=1

    dp=1#L
    l=1
    r=0
    for i in range(1,2*n):
        if s[i]==s[i-1]:
            dp=1-dp
        if dp==1:
            l+=1
        else:
            r+=1
            ans*=l-r+1
            ans%=MOD
    if s[0]=='W' or s[-1]=='W' or l!=r:
        print(0)
        sys.exit()

    print(ans*perm%MOD)

if __name__ == '__main__':
    main()

Measured memory_bytes: 40176
#include <stdio.h>
#include <string.h>
int main(int argc, const char * argv[]) {
    int i,j;
    int pointA=0,pointB=0;
    char strA[101];
    char strB[101];
    int n;
    scanf("%d",&n);
    for(i=0;i<n;i++){
        j=0;
        scanf("%s",strA);
        scanf("%s",strB);
        while(j<=101){
            if(strcmp( strA, strB )==0){
                pointA+=1;
                pointB+=1;
                break;
            }
            if(strB[j]>strA[j]){
                pointB+=3;
                break;
            }if(strA[j]>strB[j]){
                pointA+=3;
                break;
            }
            j++;
        }
    }
    
    printf("%d %d\n",pointA,pointB);
    
    return 0;
}

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

#define mp make_pair
#define pb push_back
#define st first
#define nd second

typedef long long ll;
typedef pair < int , int > pp;
const int mod = 1e9 + 7;
const int N   = 2e5 + 5;

int A[N],cost[N],n,i,t,ans;
string s;
char x;

int main(){
    cin >> n >> s;
    
    for(t=0,i=0;i<n;i++){
        x = s[i];
        cost[i] = t;
        if(x == 'W') t++;
    }
    
    ans = N;
    for(t=0,i=n-1; i>=0 ;i--){
        x = s[i];
        cost[i] += t;
        ans = min(ans , cost[i]);
        if(x == 'E') t++;
    }
    
    cout << ans;
    return 0;
}

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

int next_combination(int comb) {
    int x = comb & -comb, y = comb + x;
    return ((comb & ~y) / x >> 1) | y;
}

int main() {
    int n; cin >> n;
    vector<long long> cnt(128);
    while (n--) {
        string s; cin >> s;
        cnt[s[0]]++;
    }
    long long ans = 0;
    string march = "MARCH";
    int mask = (1 << 3) - 1;
    for ( ; mask < 1 << 5; mask = next_combination(mask)) {
        long long tmp = 1;
        for (int i = 0; i < 5; i++) if (mask >> i & 1) tmp *= cnt[march[i]];
        ans += tmp;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
#define rep(X,N) for(ll X = 0; X < (N); X++)
#define pback push_back
#define mpair make_pair
#define MODN 1000000007

using namespace std;

int main(){

    int a,b,c;
    cin >> a >> b >> c;

    int remain = a - b;

    cout << max(0, c - remain) << endl;

    return 0;

}

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

int main(){
  int n, i, alice=0, bob=0, dif;
  cin >> n;
  vector<int> card(n);  
  for(i=0; i<n; i++) cin >> card[i];
  sort(card.begin(), card.end());
  reverse(card.begin(), card.end());
  for(i=0; i<n; i++){
    if(i%2 == 0) alice += card[i];
    else bob +=  card[i];
  }
  dif = alice - bob;
  cout << dif << endl;
}

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

using namespace std;
typedef long long ll;
int const N = 5e5 + 10;
int les[N+1], gr[N+1];
int main(){
    string s;
    cin >> s;
    int n = s.size();
    int cnt = 0;
    for (int i=1;i<=n;i++){
        if (s[i-1] == '<') {
            cnt++;
            les[i]=cnt;
        } else {
            les[i]=0;
            cnt=0;
        }
    }

    for (int i=n-1;i>=0;i--){
        if (s[i] == '>'){
            cnt++;
            gr[i]=cnt;
        } else {
            gr[i]=0;
            cnt=0;
        }
    }
    long long res = 0;

    for (int i=0;i<=n;i++){
        res += 1LL*max(les[i],gr[i]);
    }
    cout << res;
    return 0;
}


Measured memory_bytes: 4740
n = int(input())
card = list(map(int, input().split()))
card.sort(reverse=1)
alice = 0
bob = 0
for i in range(1,n+1):
    if i%2==0:
        bob += card[i-1]
    else: alice += card[i-1]
if alice >= bob:
    print(alice - bob)
else: print(bob-alice)

Measured memory_bytes: 3064
# -*- coding: utf-8 -*-
L,R = list(map(int,input().split()))
if R-L >= 2019:
    import sys
    print(0)
    sys.exit()
mod_2019 = lambda x:x%2019
ret = 2020
ij_list = [i for i in range(L,R+1)]
for i in range(len(ij_list)):
    for j in range(i):
        k = mod_2019(ij_list[i]*ij_list[j])
        if k < ret:
            ret = k
print(ret)


Measured memory_bytes: 3060
#include <iostream>
#include <bits/stdc++.h>
#include <string>

using namespace std;

typedef long long int ll;
typedef unsigned long long  ull;
typedef vector<int> vi;
typedef vector<char> vc;
typedef deque <int> di;
typedef deque <char> dc;

#define f(i, a, b) for (int i = a; i < b; i++)
#define f2(i, a, b) for (int i = a; i <=b; i++)
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front;

int main()
{

int n;
int d;
cin >> n >> d;
int x[2*n];
int sum = 0;
f(i, 0, 2*n) {
cin >> x[i];

}
f(i, 0, 2*n) {
if (i%2 == 0) {
        if ((sqrt(pow(x[i], 2) + pow(x[i+1], 2))) <= static_cast<float>(d)) {
         sum++;


        }

}
}
cout << sum;
return 0;
}



Measured memory_bytes: 5192
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<ll> vl;
class ST {
	private:
		int n,h;
		vl st,lz;
		int log2(int v) {
			if(v <= 1) return 1;
			return log2(v/2)+1;
		}
		void ap(int p, int val) {
			st[p] += val;
			if(p < n) {lz[p] += val;}
		}
		void build(int p) {
			while(p > 1) {
				p >>= 1;
				if(p >= n) continue;
				st[p] = max(st[p<<1],st[p<<1|1])+lz[p];
			}
		}
		void psh(int p) {
			for(int s=h;s>0;s--) {
				int i = p>>s;
				if(lz[i] != 0) {
					ap(i<<1,lz[i]);
					ap(i<<1|1,lz[i]);
					lz[i] = 0;
				}
			}
		}
	public:
		ST(int _n) {
			n = _n;
			h = log2(n);
			st.assign(2*n,0);
			lz.assign(n,0);
		}
		void up(int l, int r, ll val) {
			if(l >= r) return;
			l += n;r += n;
			int li = l,ri = r;
			for(;l<r;l>>=1,r>>=1) {
				if(l&1) {ap(l++,val);
				}
				if(r&1) {ap(--r,val);
				}
			}
			build(li);build(ri-1);
		}
		ll qu(int l, int r) {
			l += n;r += n;
			psh(l);psh(r-1);
			ll res = -1LL<<62;
			for(;l<r;l>>=1,r>>=1) {
				if(l&1) {res = max(res,st[l++]);}
				if(r&1) {res = max(res,st[--r]);}
			}
			return res;
		}
};
const int MN = 200200;
ii v[MN];
int main() {
	//ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int n,m;
	cin >> n >> m;
	for(int i=0;i<n;i++) {
		int a,b;
		cin >> a >> b;
		v[i] = {a,b};
	}
	sort(v,v+n);
	ST st(m+10);
	ll ma = max(n-m,0);
	int pt = 0;
	for(int i=1;i<=m;i++) {
		st.up(0,i+1,-1);
	}
	for(int i=0;i<=m;i++) {
		while((pt < n) && (v[pt].first <= i)) {
			st.up(0,v[pt].second+1,1);
			pt++;
		}
		ma = max(ma,st.qu(i,m+5)-i);
	}
	cout << ma << '\n';
}

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

#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define endl "\n"

using namespace std;
using ll = long long;

const ll MOD = 1000000007LL; // = 10^9 + 7
const double PI = 3.14159265358979;

void solve()
{
  int n, a, b, c;
  cin >> n >> a >> b >> c;
  vector<int> l(n);
  for(int i = 0; i < n; ++i)
  {
    cin >> l[i];
  }

  vector<int> target{a, b, c};
  
  do
  {
    do
    {
      // cout << "come\n";
    } while(next_permutation(l.begin(), l.end()));
  } while(next_permutation(target.begin(), target.end()));

  int ans = 1 << 30;
  do
  {
    do
    {
      int ti = 0;
      int cost = 0;
      int now_len = 0;
      for(int li = 0; li < n; ++li)
      {
        if(ti >= 3) continue;
        now_len += l[li];
        int guchoku_cost = abs(now_len - target[ti]);
        int gattai_cost = (li + 1 < n) ? abs(now_len + l[li + 1] - target[ti]) + 10 : 1000000;

        //cout << now_len << " " << l[li] << " ";
        if (guchoku_cost < gattai_cost)
        {
          cost += guchoku_cost;
          now_len = 0;
          ti++;
          //cout << "guchoku : +" << guchoku_cost << " / sum : " << cost << endl;
        }
        else
        {
          cost += 10;
          //cout << "gattai  : +" << 10 << " / sum : " << cost << endl;
        }
      }
      if (ti >= 3)
      {
        ans = min(ans, cost);
      }
    } while(next_permutation(l.begin(), l.end()));
  } while(next_permutation(target.begin(), target.end()));
  cout << ans;
}

int main()
{
  fastio;
  solve();

  return 0;
}

Measured memory_bytes: 3612
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<stack>
#include<queue>
using namespace std;
typedef long long ll;

const int maxn = 100010;
const int M = 1000000007;

int n;
ll a1,a2,a3,a4;

ll ksm(ll i,ll po){
	ll res = 1ll;
	while(po){
		if(po & 1) res = res * i % M;
		po >>= 1;
		i = i * i % M;
	}
	return res % M; 
}

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

int main(){
	a1 = 0 , a2 = 0, a3 = 0, a4 = 0;
	n = read();
	ll a1 = ksm(10,n);
	ll a2 = ksm(9,n);
	ll a3 = ksm(9,n);
	ll a4 = ksm(8,n);
	
	printf("%lld\n",(((a1-a2+M)%M-a3+M)%M+a4)%M);
	
	return 0;
}

Measured memory_bytes: 3752
/**
 *    This code has been written by YueGuang, feel free to ask me question. Blog: http://www.yx.telstudy.xyz
 *    created:
 */
#include <cstdio>
#include <iostream>
#include <set>
#include <map>
#include <algorithm>
#include <cstring>
#include <string>
#include <cmath>
#define REP(i, a, b) for(int i = a; i < b; i++)
#define REP_(i, a, b) for(int i = a; i <= b; i++)
#define sl(n) scanf("%lld", &n);
#define si(n) scanf("%d", &n);
#define RepAll(a) for(auto x: a)
#define cout(ans) cout << ans << endl;
typedef long long ll;

using namespace std;
bool judge(int n){
    string s = to_string(n);
    //cout << s << endl;
    for(int i = 0; i < s.size()/2; i++){  //cout << s[i] << " " << s[s.size() - 1 - i] << endl;
        if (s[i] != s[s.size() - 1 - i]){

            return false;
        }
    }
    return true;
}
int main(){
    int a, b, cnt = 0;
    scanf("%d%d", &a, &b);
    for(int i = a; i <= b; i++){
        if (judge(i)){
            cnt++;
        }
    }
    cout << cnt << endl;
}


Measured memory_bytes: 256
//実装ができないフレンズです

#include <bits/stdc++.h>
#define repd(i,a,b) for (int i=(a);i<(b);i++)
#define rep(i,n) repd(i,0,n)
#define int long long
typedef long long ll;
const int MOD = 1000000007;
const int INF = 1010000000;
const double EPS = 1e-10;
using namespace std;
const pair<int,int> fd[] = {make_pair(1,0),make_pair(-1,0),make_pair(0,1),make_pair(0,-1)}; 

ll f(ll x){
  if(x == -1)return 0;
  ll a = x;
  rep(i,x%4){
    a ^= x-i-1;
  }
  return a;
}

signed main() {
  ll a,b;cin>>a>>b;
  cout << (f(a-1) ^ f(b)) << endl;
}


Measured memory_bytes: 256
N, K = map(int, input().split())
X = sorted(list(map(int, input().split())))
cnt = []

for i in range(N - K + 1):
    left = X[i]
    right = X[i+K-1]
    cnt.append(min(abs(right)+abs(left-right), abs(left) + abs(right - left)))
print(min(cnt))



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

constexpr int64_t INF = 1e18;
constexpr int D = 365;
constexpr int N = 26;
int c[N];
int s[D + 1][N];
int last[D + 1][N];
int64_t score[D + 1];
int t[D + 1];

constexpr int64_t CYCLES_PER_SEC = 2800000000;
constexpr double TIMELIMIT = 2.10;
struct Timer {
	int64_t start;
	Timer() { reset(); }
	void reset() { start = getCycle(); }
	void plus(double a) { start -= (a * CYCLES_PER_SEC); }
	inline double get() { return (double)(getCycle() - start) / CYCLES_PER_SEC; }
	inline int64_t getCycle() {
		uint32_t low, high;
		__asm__ volatile ("rdtsc" : "=a" (low), "=d" (high));
		return ((int64_t)low) | ((int64_t)high << 32);
	}
};
mt19937 mt{random_device{}()};
uniform_int_distribution<int> rnd_contest(0, N - 1);
// uniform_int_distribution<int> rnd_day(1, D);
normal_distribution<> rnd_day(0, 1.5);

void input() {
	int _d; cin >> _d;
	for(int i = 0; i < N; ++i) {
		cin >> c[i];
	}
	for(int i = 1; i <= D; ++i) {
		for(int j = 0; j < N; ++j) {
			cin >> s[i][j];
		}
	}
}

void greedy(int day, int contest = -1) {
	if(contest != -1) {
		for(int j = 0; j < N; ++j) {
			last[day][j] = last[day - 1][j];
		}
		last[day][contest] = day;
		++day;
	}
	for(int i = day; i <= D; ++i) {
		for(int j = 0; j < N; ++j) {
			last[i][j] = last[i - 1][j];
		}
		int64_t loss = 0;
		for(int j = 0; j < N; ++j) {
			loss += c[j] * (i - last[i][j]);
		}
		int64_t maxi = -INF;
		int midx = 0;
		for(int j = 0; j < N; ++j) {
			int64_t los = loss - c[j] * (i - last[i][j]);
			if(s[i][j] - los > maxi) {
				maxi = s[i][j] - los;
				midx = j;
			}
		}
		last[i][midx] = i;
		t[i] = midx;
	}
}

int64_t calc(int day) {
	int64_t ans = score[day - 1];
	for(int i = day; i <= D; ++i) {
		for(int j = 0; j < N; ++j) {
			last[i][j] = last[i - 1][j];
		}
		last[i][t[i]] = i;
		ans += s[i][t[i]];
		for(int j = 0; j < N; ++j) {
			int64_t loss = c[j] * (i - last[i][j]);
			ans -= loss;
		}
		score[i] = ans;
	}
	return ans;
}

void output() {
	for(int i = 1; i <= D; ++i) {
		cout << t[i] + 1 << '\n';
	}
}

int main() {
	Timer timer;
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	input();
	greedy(1);
	calc(1);
	int cnt = 0, update = 0;
	int valid = D;
	int64_t score_now = score[D];
	while(timer.get() < TIMELIMIT) {
		int q = rnd_contest(mt);
		double pro = rnd_day(mt);
		if(pro < 0) continue;
		++cnt;
		int d = max<int>(1, D - pro * D);
		int contest_pre = t[d];
		t[d] = q;
		valid = min(valid, d - 1);
		// greedy(d, q);
		int64_t score_nxt = calc(valid + 1);
		if(score_nxt > score_now) {
			score_now = score_nxt;
			update++;
			valid = D;
		} else {
			t[d] = contest_pre;
			// greedy(d, q);
		}
	}
	// cerr << cnt << " " << update << '\n';
	// cerr << score_now << '\n';
	output();
	return 0;
}


Measured memory_bytes: 4060
#include<bits/stdc++.h>
using namespace std;
int k, n, m, a[100005], sum[100005], ans = (1<<30), b[100005], n1, n2;
int cmp(int x, int y){
	return abs(x) < abs(y);
}
int main(){
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= n ; i++){
		scanf("%d", &k);
		if(k == 0) m --;
		else
		if(k < 0) a[++n1] = k;
		else b[++n2] = k;	
	}
	if(m <= 0) {printf("0");return 0;}
	sort(a + 1, a + 1 + n1, cmp);
	sort(b + 1, b + 1 + n2, cmp);
	for(int i = max(0, m - n2); i <= min(n1, m); i++){
		int j = m - i;
		if(- a[i] * 2 + b[j] < ans) ans = - a[i] * 2 + b[j];
	}
	for(int i = max(0, m - n1); i <= min(n2, m); i++){
		int j = m - i;
		if(b[i] * 2 - a[j] < ans) ans = b[i] * 2 - a[j];
	}
	printf("%d", ans);
	return 0;
}


Measured memory_bytes: 640
from collections import deque;h,w=map(int,input().split());m=[input()for _ in[0]*h];v=[[-1]*w for _ in[0]*h];q=deque([[0,0]]);v[0][0]=0;c=sum(t.count('#')for t in m)
while q:
 y,x=q.popleft()
 for i,j in([1,0],[-1,0],[0,1],[0,-1]):
  t,u=y+i,x+j
  if t+1and t<h and u+1and u<w and m[t][u]=='.'and v[t][u]<0:v[t][u]=v[y][x]+1;q.append([t,u])
print(-1*(v[h-1][w-1]<0)or h*w-c-v[h-1][w-1]-1)

Measured memory_bytes: 3316
from sys import stdin
# import math
import numpy as np
# N = int(stdin.readline().rstrip().split()[0])
# A = [int(x) for x in stdin.readline().rstrip().split()]
# N, X = [int(x) for x in stdin.readline().rstrip().split()]
# S = stdin.readline().rstrip().split()[0]

N = int(stdin.readline().rstrip().split()[0])
S = stdin.readline().rstrip().split()[0]

B =[]
W =[]
b=0
w=0
for i in range(N):
  if S[i]==".":
    w+=1
  W.append(w)
  
  if S[N-1-i]=="#":
    b+=1
  B.append(b)

W=np.array(W)
B=np.array(B[::-1])
ans = N-np.max(W+B)
print(ans)


Measured memory_bytes: 25164
'use strict'

function main (s) {
  let number = Number(s)
  if (number <= 0) {
    console.log(0)
    return
  }
  let quotient = Math.floor(number / 11)
  let remainder = Math.floor(number % 11)
  let few
  if (remainder === 0) {
    few = 0
  } else if (remainder <= 6) {
    few = 1
  } else {
    few = 2
  }
  let count = quotient * 2 + few
  console.log(count)
}

function doMain () {
  let input = ''
  process.stdin.resume()
  process.stdin.setEncoding('utf8')
  process.stdin.on('data', (chunk) => {
    input += chunk
  })
  process.stdin.on('end', () => {
    input = input.trim()
    main(input)
  })
}

doMain()


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

using namespace std;

template<typename S, typename T>
ostream& operator<<(ostream& out, const pair<S, T> p) {
    out << "(" << p.first << "," << p.second << ")";
    return out;
}

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& v) {
    for (auto a: v)
        out << a << " ";
    return out;
}

template<typename T>
ostream& operator<<(ostream& out, const set<T>& S) {
    for (auto a: S)
        cout << a << " ";
    return out;
}

template<typename T>
ostream& operator<<(ostream& out, const multiset<T>& S) {
    for (auto a: S)
        cout << a << " ";
    return out;
}

template<typename S, typename T>
ostream& operator<<(ostream& out, const map<S, T>& M) {
    for (auto m: M)
        cout << "(" << m.first << "->" << m.second << ") ";
    return out;
}

template<typename S, typename T>
pair<S, T> operator+(pair<S, T> a, pair<S, T> b) {
    return make_pair(a.first + b.first, a.second + b.second);
}

template<typename S, typename T>
pair<S, T> operator-(pair<S, T> a, pair<S, T> b) {
    return make_pair(a.first - b.first, a.second - b.second);
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n;
    vector<int> A;
    cin >> n;
    A.resize(n);
    for (int i = 0; i < n; i++)
        cin >> A[i];
    sort(A.begin(), A.end());
    long long ans = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            for (int k = j + 1; k < n; k++) {
                if (A[i] != A[j] && A[j] != A[k] && A[i] + A[j] > A[k])
                    ans++;
            }
        }
    }
    cout << ans << endl;
    return 0;
}


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

int main() {
  string S, T;
  cin >> S >> T;
  int ans = 0;
  for (int i = 0; i < 3; i++){
    if (S.at(i) == T.at(i))
      ans++;
  }
  cout << ans << endl;
}

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

ll f[100005];

void saisho(ll h[],ll n){
  int i;
  for(i = 0; i < n; i++){
    if(i == 0){
      f[0] = 0;
    }
    else if(i == 1){
      f[1] = abs(h[1]-h[0]);
    }
    else{
      if(abs(h[i]-h[i-1]) + f[i-1] >= abs(h[i]-h[i-2]) + f[i-2]){
        f[i] = f[i-2] + abs(h[i]-h[i-2]);
      }
      else{
        f[i] = f[i-1] + abs(h[i]-h[i-1]);
      }
    }
  }
}

int main(void){
  ll n; cin >> n;
  ll h[n]; rep(i,n) cin >> h[i];
  saisho(h,n);
  cout << f[n-1] << endl;
  return 0;
}


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

int main() {
	long long A, N, M, cnt = 0;
	cin >> A >> N >> M;

	for (long long i = 1; i <= 100000; i++) {
		long long s = 1;
		for (int j = 1; j <= N; j++) s *= i;
		if (s > M) break;

		string V = to_string(s);
		long long R = 0;
		for (int j = 0; j < V.size(); j++) R += (long long)(V[j] - '0');
		if (R + A == 1LL * i) {
			cnt++;
		}
	}
	cout << cnt << endl;
	return 0;
}


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


const int N = 2e5 + 7;

vector <int> a[N], b[N];

void solve() {
	int n; cin >> n;
	for(int i = 1; i <= n; i++) {
		a[i].clear();
		b[i].clear();
	}
	long long ans = 0;
	for(int i = 1; i <= n; i++) {
		int k, l, r; cin >> k >> l >> r;
		ans += min(l, r); int x = min(l, r); l -= x; r -= x;
		if(l) {
			a[k].push_back(l);
		}
		if(r) {
			b[k + 1].push_back(r);
		}
	}
	priority_queue <int> pq;
	for(int i = 1; i <= n; i++) {
		while(b[i].size()) {
			pq.push(b[i].back()); b[i].pop_back();
		}
		if(pq.size()) {
			ans += pq.top(); pq.pop();
		}
	}
	while(pq.size()) {
		pq.pop();
	}
	for(int i = n; i >= 1; i--) {
		while(a[i].size()) {
			pq.push(a[i].back()); a[i].pop_back();
		}
		if(pq.size()) {
			ans += pq.top(); pq.pop();
		}
	}

	cout << ans << endl;
}

int main() {
	ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int test, tc = 0; cin >> test;
	while(test--) {
		solve();
	}	
}

Measured memory_bytes: 17444
def main():
    m, n = map(int, input().split())
    Sum = 0
    A = list(map(int, input().split()))
    for i in range(n):
        Sum+=A[i]
    if Sum>m:
        print(-1)
    else:
        print(m-Sum)
 
if __name__=='__main__':
    main()

Measured memory_bytes: 9880
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
//#include<cctype>
#include<climits>
#include<iostream>
#include<string>
#include<vector>
#include<map>
//#include<list>
#include<queue>
#include<deque>
#include<algorithm>
//#include<numeric>
#include<utility>
//#include<memory>
#include<functional>
#include<cassert>
#include<set>
#include<stack>
#include<random>

const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, -1, 0, 1};
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<int, int> pii;

int N;
vi now, target;

bool dfs(int d, int maxDepth) {
    if (d == maxDepth) {
        if (now == target) return true;
        else return false;
    }
    int exist = 0;
    for (int i = 0; i < N; i++) {
        int tmp = (10+target[i]-now[i])%10;
        exist |= 1<<tmp;
    }
    int cnt = __builtin_popcount(exist);
    if (cnt/3*3+(cnt%3)+d > maxDepth+1) return false;
    for (int i = 0; i < N; i++) if (now[i] != target[i]) {
        int diff = (10+target[i]-now[i])%10;
        for (int j = i; j < N; j++) {
            for (int k = i; k <= j; k++) {
                now[k] = (now[k]+diff)%10;
            }
            if (dfs(d+1, maxDepth)) return true;
            for (int k = i; k <= j; k++) {
                now[k] = (now[k]+10-diff)%10;
            }
        }
        break;
    }
    for (int i = N-1; i >= 0; i--) if (now[i] != target[i]) {
        int diff = (10+target[i]-now[i])%10;
        for (int j = 0; j <= i; j++) {
            for (int k = j; k <= i; k++) {
                now[k] = (now[k]+diff)%10;
            }
            if (dfs(d+1, maxDepth)) return true;
            for (int k = j; k <= i; k++) {
                now[k] = (now[k]+10-diff)%10;
            }
        }
        break;
    }
    return false;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    while (cin >> N) {
        if (N==0) break;
        now.clear(); target.clear();
        now.resize(N); target.resize(N);
        string s, t;
        cin >> s >> t;
        for (int i = 0; i < N; i++) {
            now[i] = (s[i]-'0');
            target[i] = (t[i]-'0');
        }
        int ans = N;
        for (int i = 0; i < ans; i++) {
            if (dfs(0, i)) {
                ans = i;
                break;
            }
        }
        cout << ans << endl;
    }
    return 0;
}

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

using namespace std;

#define INF 1000000007
#define LINF (1LL << 60)
#define PI 3.14159265358979

typedef long long i64;
typedef pair<i64,i64> P;

inline i64 mod(i64 a, i64 m) { return (a % m + m) % m; }

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }



int h, w;
string a[111];
int cnt[26];
void solve(){
	cin >> h >> w;
	for(int i = 0; i < h; i++){
		cin >> a[i];
		for(int j = 0; j < w; j++){
			cnt[a[i][j]-'a']++;
		}
	}
	
	int b = (h%2)*(w%2), c = (h%2)*w/2 + (w%2)*h/2;
	for(int i = 0; i < 26; i++){
		if(cnt[i] == 0) continue;
		if(cnt[i]%2 == 1){
			b--;
			cnt[i]--;
		}
		if(cnt[i]%4 == 2){
			c--;
			continue;
		}
	}
	if(b < 0 || c < 0) cout << "No" << endl;
	else cout << "Yes" << endl;
}

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


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

int n,a[105],b[105],ans;

int main()
{
	scanf("%d",&n);
	for(int i=1;i<n;++i) scanf("%d",b+i);
	b[n]=b[n-1],b[0]=b[1];
	for(int i=1;i<=n;++i) a[i]=min(b[i],b[i-1]);
	for(int i=1;i<=n;++i) ans+=a[i];
	printf("%d",ans);
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<ll, ll>;

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

    int N;
    cin >> N;
    vector<ll> L(N);
    for (int i = 0; i < N; ++i) {
        ll A;
        cin >> A;
        if (i) {
            L.at(i) = L.at(i - 1) + A;
        } else {
            L.at(i) = A;
        }
    }
    ll ans = LLONG_MAX;
    for (int i = 0; i < N; ++i) {
        ll cost = abs((L.at(N - 1) - L.at(i)) - L.at(i));
        ans = min(ans, cost);
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = s; i < (int)(n); i++)
#define Clear(a) a = decltype(a)()
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define vec vector
typedef long long ll;
typedef pair<int,int> p;
//const ll big=998244353;
const ll big=1000000007;
const int dx[4]={1,0,-1,0};
const int dy[4]={0,1,0,-1};
ll max(ll x,ll y){
if(x>y)return x;
else return y;
}
ll min(ll x,ll y){
if(x<y)return x;
else return y;
}
ll expm(ll x,ll y){
    if(y==0)return 1;//0^0=1
    if(x==1||x==0)return x;
    if(y%2==1)return (expm(x,y-1)*x)%big;
    ll t=expm(x,y/2);
    return (t*t)%big;
}
ll exp(ll x,ll y){
    if(y==0)return 1;//0^0=1
    if(x==1||y==0)return x;
    if(y%2==1)return exp(x,y-1)*x;
    ll t=exp(x,y/2);
    return t*t;
}
ll inv(ll x){
    return expm(x,big-2);
}


int main(){
    ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    cout << fixed << setprecision(10);
    /*--------------------------------*/

    int n;cin >> n;
    if(n>=30)cout << "Yes" << endl;
    else cout << "No" << endl;
}

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

struct UnionFind{
    vector<int> par;

    UnionFind(int n): par(n){
        for(int i=0; i<n; i++){
            par[i] = i;
        }
    }

    int root(int i){
        if(par[i] == i) return i;
        else return par[i] = root(par[i]);
    }

    void unite(int x, int y){
        int rx = root(x);
        int ry = root(y);
        if(rx != ry){
            par[rx] = ry;
        }
    }

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


signed main(){
    // cout << fixed << setprecision(10) << flush;

    int V, E;
    cin >> V >> E;
    vector<tuple<int, int, int>> wt;
    for(int i=0; i<E; i++){
        int s, t, w;
        cin >> s >> t >> w;
        wt.push_back(make_tuple(w, s, t));
    }
    sort(wt.begin(), wt.end());
    
    int sum_span = 0;
    UnionFind uf(V);
    for(int i=0; i<E; i++){
        int w = get<0>(wt[i]);
        int s = get<1>(wt[i]);
        int t = get<2>(wt[i]);
        if(uf.root(s) != uf.root(t)){
            sum_span += w;
            uf.unite(s, t);
        }
    }

    cout << sum_span << endl;
    return 0;
}


Measured memory_bytes: 5892
import sys
import bisect
import itertools
sys.setrecursionlimit(10**7)

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n = ni()
a = na()
b = a.copy()
for i in range(n):
    a[i] += i+1
    b[i] -= i+1
ans = 0
b.sort()
for i in range(n):
    ans += bisect.bisect_right(b, -a[i]) - bisect.bisect_left(b, -a[i])
print(ans)

Measured memory_bytes: 32116
#include<stdio.h>
#include<string.h>
int main(void)
{
    char s[101];
    int a=0,b=0,c=0,i,j=1;
    scanf("%s",s);
    for(i=1;i<strlen(s)-1;i++){
        a++;
        if(a==10){
            a=0; b++;
        }
        if(b==10){
            b=0; c++;
        }
    }
    if(c>0){
        s[j]=c+'0';
        j++;
    }
    if((b>0)||(c>0)){
        s[j]=b+'0';
        j++;
    }
    if((a>0)||(b>0)){
        s[j]=a+'0';
        j++;
    }
    s[j]=s[strlen(s)-1];
    s[j+1]='\0';
    printf("%s\n",s);
    return 0;
}

Measured memory_bytes: 1656
import sys
from collections import deque
input = sys.stdin.readline
n, q = map(int, input().split())
edges = [[] for _ in range(n)]
for _ in range(n-1):
    a, b = list(map(lambda x: int(x)-1, input().split()))
    edges[a].append(b)
    edges[b].append(a)

values = [0]*n
for _ in range(q):
    p, x = map(int, input().split())
    values[p-1] += x

queue = deque([0])
visited = [0]*n
while queue:
    v = queue.pop()
    if visited[v]:
        continue
    visited[v] = 1
    for v2 in edges[v]:
        if visited[v2]:
            continue
        values[v2] += values[v]
        queue.append(v2)
print(*values)

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

const int Maxn = 100005;
int n, ct, pnt, a[Maxn];
int main()
{
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
		scanf("%d", &a[i]);
	sort(a + 1, a + 1 + n, greater <int> ());
	pnt = n; 
	for (int i = 1; i <= n; i++)
		if (a[i] < i)
		{
			pnt = i - 1;
			break;
		}
	for (int i = pnt + 1; i <= n; i++)
		if (a[i] == pnt) ct++;
	puts((((a[pnt] - pnt) & 1) || (ct & 1)) ? "First" : "Second");
	return 0;
}

Measured memory_bytes: 4088
#line 2 "/Users/kaage/Desktop/ProgrammingWorkspace/library/other/template.hpp"
#define _CRT_SECURE_NO_WARNINGS
#pragma target("avx2")
#pragma optimize("O3")
#pragma optimize("unroll-loops")
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <ctime>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <memory>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <string.h>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
#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()
typedef unsigned int uint;
typedef long long lint;
typedef unsigned long long ulint;
typedef std::pair<int, int> P;
typedef std::pair<lint, lint> LP;
constexpr int INF = INT_MAX/2;
constexpr lint LINF = LLONG_MAX/2;
constexpr double eps = DBL_EPSILON;
constexpr double PI=3.141592653589793238462643383279;
template<class T>
class prique :public std::priority_queue<T, std::vector<T>, std::greater<T>> {};
template <class T, class U>
inline bool chmax(T& lhs, const U& rhs) {
	if (lhs < rhs) {
		lhs = rhs;
		return 1;
	}
	return 0;
}
template <class T, class U>
inline bool chmin(T& lhs, const U& rhs) {
	if (lhs > rhs) {
		lhs = rhs;
		return 1;
	}
	return 0;
}
inline lint gcd(lint a, lint b) {
	while (b) {
		lint c = a;
		a = b; b = c % b;
	}
	return a;
}
inline lint lcm(lint a, lint b) {
	return a / gcd(a, b) * b;
}
bool isprime(lint n) {
	if (n == 1)return false;
	for (int i = 2; i * i <= n; i++) {
		if (n % i == 0)return false;
	}
	return true;
}
template<typename T>
T mypow(T a, lint b) {
	T res(1);
	while(b){
		if(b&1)res*=a;
		a*=a;
		b>>=1;
	}
	return res;
}
lint modpow(lint a, lint b, lint m) {
	lint res(1);
	while(b){
		if(b&1){
			res*=a;res%=m;
		}
		a*=a;a%=m;
		b>>=1;
	}
	return res;
}
template<typename T>
void printArray(std::vector<T>& vec) {
	rep(i, vec.size()){
		std::cout << vec[i];
		std::cout<<(i==(int)vec.size()-1?"\n":" ");
	}
}
template<typename T>
void printArray(T l, T r) {
	T rprev = std::prev(r);
	for (T i = l; i != rprev; i++) {
		std::cout << *i << " ";
	}
	std::cout << *rprev << std::endl;
}
LP extGcd(lint a,lint b) {
	if(b==0)return {1,0};
	LP s=extGcd(b,a%b);
	std::swap(s.first,s.second);
	s.second-=a/b*s.first;
	return s;
}
LP ChineseRem(const lint& b1,const lint& m1,const lint& b2,const lint& m2) {
	lint p=extGcd(m1,m2).first;
	lint tmp=(b2-b1)*p%m2;
	lint r=(b1+m1*tmp+m1*m2)%(m1*m2);
	return std::make_pair(r,m1*m2);
}
template<typename F>
inline constexpr decltype(auto) lambda_fix(F&& f){
	return [f=std::forward<F>(f)](auto&&... args){
		return f(f,std::forward<decltype(args)>(args)...);
	};
}
#line 2 "main.cpp"
int main(){
	int x;
	std::cin>>x;
	std::cout<<1-x<<std::endl;
	return 0;
}

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

using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;

int gcd(int arr[]) {
	int res = arr[0];
	for (int i = 1; i < 3; i++) res = __gcd(res, arr[i]);
	return res;
}

int main() {
	int k; cin >> k;
	int res = 0;
	for (int i = 1; i <= k; i++) {
		for (int j = 1; j <= k; j++) {
			for (int h = 1; h <= k; h++) {
				int arr[3] = {i, j, h};
				res += gcd(arr);
			}
		}
	}
	cout << res;
	return 0;
}

Measured memory_bytes: 3644
L, R = map(int, input().split())
explore_list = []
def explore(L, R):
    for i in range(L, min(L+2020, R + 1)):
        explore_list.append(i % 2019)

explore(L, R)
answer_list = []
for i in range(len(explore_list)):
    for j in range(i + 1, len(explore_list)):
        answer_list.append(explore_list[i] * explore_list[j] % 2019)

print(min(answer_list))



Measured memory_bytes: 107532
import java.util.Scanner;

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

        int N = sc.nextInt();

        int[] A = new int[N];
        for (int i = 0; i < N; i++) {
            A[i] = sc.nextInt();
        }

        int dummy;
        int count = 0;
        boolean unsorted = true;

        while(unsorted){
            unsorted = false;
            for (int i = N-1; i > 0; i--) {
                if(A[i] < A[i-1]){
                    dummy = A[i-1];
                    A[i-1] = A[i];
                    A[i] = dummy;

                    count++;
                    unsorted = true;
                }
            }
        }

        for (int i = 0; i < N; i++) {
            System.out.print(A[i]);
            if(i != N-1){
                System.out.print(" ");
            }
        }
        System.out.println("");
        System.out.println(count);

        sc.close();
    }
}


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

int main(){
    int A1, A2, A3;
    cin >> A1 >> A2 >> A3;
    if( A1+A2+A3<22 ){
        cout << "win" << endl;
    }else{
        cout << "bust" << endl;
    }

    return 0;
}

Measured memory_bytes: 256