akhauriyash/Code-Regression huggingface dataset:
#pragma warning(disable:4996)
#include <bits/stdc++.h>

using namespace std;

#define REP(i,n) for (ll i = 0LL; i<(ll)(n); i++)
#define ALL(a) begin(a), end(a)
#define TPL template
#define TNM typename

using ll = long long;
using ull = unsigned long long;
TPL<TNM T> using vec = vector<T>;
TPL<TNM T> using vec2 = vec<vec<T>>;
TPL<TNM T> using vec3 = vec<vec2<T>>;
TPL<TNM T> using vec4 = vec<vec3<T>>;
TPL<TNM T> using vec5 = vec<vec4<T>>;

TPL<TNM K, TNM V> using umap = unordered_map<K, V>;
TPL<TNM K, TNM V> using uset = unordered_set<K, V>;

TPL<class T> inline void OUT(const T &x) { cout << x << "\n"; }
struct pre_ { pre_() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(6); } } pre__;

TPL<TNM V, TNM H> void resize(vector<V>& v, const H h) { v.resize(h); }
TPL<TNM V, TNM H, TNM ... T> void resize(vector<V>& v, const H& h, const T ... t) { v.resize(h); for (auto& _v : v) resize(_v, t ...); }
TPL<TNM V, TNM T> void fill(V& x, const T& val) { x = val; }
TPL<TNM V, TNM T> void fill(vector<V>& vec, const T& val) { for (auto& v : vec) fill(v, val); }

int main(void) {
	ll N, K;
	cin >> N >> K;
	vec<ll> memo(K, 0);
	for (int i = 1; i <= N; ++i) {
		memo[i%K]++;
	}
	ll ans = 0;
	for (int a = 0; a < K; ++a) {
		ll b = (-a + K * 2'000'00) % K;
		ll c = (-a + K * 2'000'00) % K;
		if ((b + c) % K != 0)continue;
		ans += memo[a] * memo[b] * memo[c];
	}
	OUT(ans);
	return 0;
}

Measured memory_bytes: 1792
import java.util.*;
 
class Main {
    public static void main(String[] args){
        List<String> list = new LinkedList<String>();
 
        String[] mark = {"S", "H", "C", "D"};
 
        for(int i = 0; i < 4; i++){
            for(int j = 0; j < 13; j++){
                list.add(mark[i] + " " + (j + 1));
            }
        }
 
        Scanner sc = new Scanner(System.in);
 
        int n = Integer.parseInt(sc.nextLine());
         
        for(int i = 0; i < n; i++){
            list.remove(sc.nextLine());
        }
 
        for(String str : list){
            System.out.println(str);
        }
         
    }
}

Measured memory_bytes: 17200
using System;
class Program
{
    static void Main(string[] args)
    {
        string[] input = Console.ReadLine().Split(' ');
        int n = int.Parse(input[0]);
        int m = int.Parse(input[1]);
        int x = int.Parse(input[2]);

        int[,] books = new int[n, m + 1];

        for (int i = 0; i < n; i++)
        {
            string[] book = Console.ReadLine().Split(' ');
            books[i, 0] = int.Parse(book[0]);

            for (int j = 1; j < m + 1; j++)
            {
                books[i, j] = int.Parse(book[j]);
            }
        }

        int pattern = (int)Math.Pow(2, n);
        int price = -1;


        for (int i = 0; i < pattern; i++)
        {
            int[] total = new int[m + 1];
            for (int j = 0; j < n; j++)
            {
                if ((i >> j) % 2 == 1)
                {
                    for (int k = 0; k < total.Length; k++)
                    {
                        total[k] = total[k] + books[j, k];
                    }
                }
            }

            int[] point = new int[m];
            Array.Copy(total, 1, point, 0, m);
            Array.Sort(point);
            if (x <= point[0])
            {
                if (price == -1 || total[0] < price)
                {
                    price = total[0];
                }
            }
        }

        Console.WriteLine(price);
    }
}


Measured memory_bytes: 28248
#include<bits/stdc++.h>
#define ll long long
#define pii_ pair<int,int>
#define mp_ make_pair
#define pb push_back
#define fi first
#define se second
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define show1(a) cout<<#a<<" = "<<a<<endl
#define show2(a,b) cout<<#a<<" = "<<a<<"; "<<#b<<" = "<<b<<endl
using namespace std;
const ll INF = 1LL<<60;
const int inf = 1<<30;
const int maxn = 2e5+5;
inline void fastio() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);}

int main()
{
    fastio();
    string s,t;
    cin>>s>>t;
    int n=s.size();
    int m=t.size();
    int flag1 = 1,flag2 = 1;
    for(auto x:s) if(x<'a'||x>'z') flag1=0;
    if(m!=n+1) flag2=0;
    else for(int i=0;i<n;i++) if(s[i]!=t[i]) flag2=0;
    if(flag1 && flag2 && n>=1 && n<=10 && m==n+1) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
    return 0;
}


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

#define each(i, c) for (auto& i : c)
#define unless(cond) if (!(cond))

using namespace std;

typedef long long int lli;
typedef unsigned long long ull;
typedef complex<double> point;

template<typename P, typename Q> ostream& operator << (ostream& os, pair<P, Q> p) { os << "(" << p.first << "," << p.second << ")"; return os; }
template<typename P, typename Q> istream& operator >> (istream& is, pair<P, Q>& p) { is >> p.first >> p.second; return is; }
template<typename T> ostream& operator << (ostream& os, vector<T> v) { os << "("; each (i, v) os << i << ","; os << ")"; return os; }
template<typename T> istream& operator >> (istream& is, vector<T>& v) { each (i, v) is >> i; return is; }

template<typename T> inline T setmax(T& a, T b) { return a = std::max(a, b); }
template<typename T> inline T setmin(T& a, T b) { return a = std::min(a, b); }

int main(int argc, char *argv[])
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  while (true) {
    bool fin = true;
    char g[2][3];
    for (int i = 0; i < 2; ++i) {
      for (int j = 0; j < 3; ++j) {
        fin = fin && (cin >> g[i][j]);
      }
    }
    if (!fin)break;

    bool f = true;
    for (int i = 0; i < 2; ++i) {
      for (int j = 0; j < 3; ++j) {
        f = f && (g[i][j] == g[1 - i][2 - j]);
      }
    }

    cout << (f ? "YES" : "NO") << endl;
  }
  
  return 0;
}


Measured memory_bytes: 256
import heapq

n=int(input())
arr=list(map(int,input().split()))
arr=sorted(arr,reverse=True)
ans=0
q=[]
heapq.heappush(q,-arr[0])
for i in range(1,n):
  tmp=heapq.heappop(q)
  tmp*=-1
  ans+=tmp
  heapq.heappush(q,-arr[i])
  heapq.heappush(q,-arr[i])
print(ans)

Measured memory_bytes: 31644
#include <iostream>
#include <cmath>
#include <vector>
#include <string>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); ++i)
using Graph = vector<vector<int>>;
using ll = long long;
using p = pair<int, int>;

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

    int sum = 0;
    rep(i, n.size())
    {
        sum = sum + (int)n[i] - 48;
    }

    if (sum % 9 == 0)
    {
        cout << "Yes" << endl;
    }
    else
    {
        cout << "No" << endl;
    }
}

Measured memory_bytes: 3752
#include <bits/stdc++.h>
#define all(x) begin(x), end(x)
#define dbg(x) cerr << #x << " = " << x << endl
#define _ << ' ' <<
using namespace std;
using ll = long long;
using vi = vector<int>;

int mod = 1000000007;
int add(int a, int b) { return (a += b) < mod? a : a - mod; }
int sub(int a, int b) { return (a -= b) >=  0? a : a + mod; }
int mul(int a, int b) { return 1LL * a * b % mod; }
void adds(int& a, int b) { a = add(a, b); }
void subs(int& a, int b) { a = sub(a, b); }
void muls(int& a, int b) { a = mul(a, b); }
void maxs(int& a, int b) { a = max(a, b); }
void mins(int& a, int b) { a = min(a, b); }
int pwr(int a, ll p) {
    if (p == 0) return 1;
    if (p & 1) return mul(a, pwr(a, p - 1));
    return pwr(mul(a, a), p / 2);
}
int inv(int a) { return pwr(a, mod - 2); }

int n;
string s;
int a[200000];
int dp[10000];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> mod >> s;
    if (mod == 2 || mod == 5)
    {
        ll sol = 0;
        for (int i = 0; i < n; ++i)
            if ((s[i] - '0') % mod == 0)
                sol += i + 1;
        cout << sol;
        return 0;
    }
    reverse(all(s));
    dp[0] = 1;
    ll sol = 0;
    int sum = 0;
    for (int i = 0; i < n; ++i)
    {
        a[i] = mul(pwr(10, i), (s[i] - '0') % mod);
        adds(sum, a[i]);
        sol += dp[sum];
        dp[sum]++;
    }
    cout << sol;
}


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

#define F first
#define S second
using namespace std;
typedef pair<int,int> P;
int main(void)
{
	int w,h,n;
	P pp[100001];
	int i;
	
	cin>>w>>h>>n;
	for(i=0;i<n;i++){
		cin>>pp[i].F>>pp[i].S;
	}
	
	sort(pp,pp+n);
	
	int MIN=pp[n-1].F;
	int MAX=0;
	for(i=n-2;i>=0;i--){
		//cout<<"MAX="<<MAX<<endl;
	 //	cout<<"P#="<<pp[i+1].S<<endl;
		MAX=max(MAX,pp[i+1].S);
		//cout<<"MAX="<<MAX<<endl;
		//cout<<"MIN="<<MIN<<endl;
		//cout<<"P!="<<pp[i].F<<endl;
		MIN=min(MIN,pp[i].F+MAX);
		//cout<<"MIN="<<MIN<<endl;
		
	}
	MAX=max(MAX,pp[0].S);
	MIN=min(MIN,0+MAX);
	cout<<MIN<<endl;
	return 0;
}
		
	


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

using namespace std;

const int MAXN = 200500;

int n;
int a[MAXN];
long long sum[MAXN];

int main() {
  //assert(freopen("input.txt","r",stdin));
  //assert(freopen("output.txt","w",stdout));

  scanf("%d", &n);
  for (int i = 0; i < n; i++) {
    scanf("%d", &a[i]);
  }

  sum[0] = a[0];
  for (int i = 1; i < n; i++) {
    sum[i] = sum[i - 1] + a[i];
  }

  long long ans = -1;

  for (int i = 0; i < n - 1;  i++) {
    long long sumL = sum[i];
    long long sumR = sum[n - 1] - sum[i];

    long long curDiff = abs(sumL - sumR);
    if (ans == -1 || curDiff < ans) {
      ans = curDiff;
    }
  }

  cout << ans << endl;

  return 0;
}

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

using namespace std;
using llong = long long;
using P = pair<llong, llong>;

#define BE(x) x.begin(), x.end()

const llong inf = llong(1e18)+7;
const llong mod = 1e9+7;

llong npn(llong n){
	llong ret = 1;
	for(llong i = 1; i <= n; i++)
		(ret *= i) %= mod;
	return ret;
}

int main(){
	llong N, M;
	cin >> N >> M;
	if(abs(N-M) == 0){
		cout << npn(N)*npn(M)*2%mod << endl;
	}else if(abs(N-M) == 1){
		cout << npn(N)*npn(M)%mod << endl;
	}else{
		cout << 0 << endl;
	}

	return 0;
}

Measured memory_bytes: 256
def binarySearch(alist, item):
    left=0
    right=len(alist)
    found = False
    while left < right and not found:
        mid=int((left+right)/2)
        if alist[mid] == item:
            found=True
        elif item<=alist[mid]:
            right=mid
        else:
            left=mid+1
    return found

n=int(input())
S=list(map(int, input().split()))
q=int(input())
T=list(map(int, input().split()))
counter=0
for t in T:
    if binarySearch(S,t):
        counter+=1
print(counter)




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

using namespace std;
typedef long long ll;

#define REP(i,n) for(int i=0;i<n;++i)
#define SORT(name) sort(name.begin(), name.end())
#define ZERO(p) memset(p, 0, sizeof(p))
#define MINUS(p) memset(p, -1, sizeof(p))
#if 1
#  define DBG(fmt, ...) printf(fmt, __VA_ARGS__)
#else
#  define DBG(fmt, ...)
#endif

#define MOD 1000000007
#define INF 1000000000
#define MAX_N 100010

int N;
ll A[MAX_N];

int main()
{
    cin >> N;
    REP(i, N) { cin >> A[i]; }

    ll prev = A[0];
    ll ans = 0;
    ll diff = 0;
    for(int i=1; i<N; ++i) {
        if(prev < A[i] && diff < 0) {
            ans++;
            diff = 0;
        }
        else if(prev > A[i] && diff > 0) {
            ans++;
            diff = 0;
        }
        else if(diff == 0 && prev != A[i]) {
            diff = (prev < A[i]) ? 1 : -1;
        }
        prev = A[i];
    }
    printf("%lld\n", ans+1);
    return 0;
}


Measured memory_bytes: 1024
# -*- coding: utf-8 -*-

A, B, K = map(int, input().split())

for i in range(K):
    if(i % 2 == 0):
        if A % 2 == 1:
            A += -1
        B += A // 2
        A = A // 2
    else:
        if B % 2 == 1:
            B += -1
        A += B // 2
        B = B // 2

print(str(A) + " " + str(B))

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

int main(){
    long long n;
    cin >> n;
    long long a[n];
    for(int i=0;i<n;i++) cin >> a[i];
    long long count1=0,count2=0;
    long long b=0;
    for(int i=0;i<n;i++){
        b+=a[i];
        if(i%2==0&&b<=0){
            count1+=abs(b)+1;
            b=1;
        }
        else if(i%2==1&&b>=0){
            count1+=abs(b)+1;
            b=-1;
        }
    }
    long long c=0;
    for(int i=0;i<n;i++){
        c+=a[i];
        if(i%2==0&&c>=0){
            count2+=abs(c)+1;
            c=-1;
        }
        else if(i%2==1&&c<=0){
            count2+=abs(c)+1;
            c=1;
        }
    }
    cout << min(count1,count2) << endl;
}


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

using namespace std;

typedef long long ll;

const int N = 5001;

bitset<N> pref[N], suf[N];

int fen[N][N];

void add(int v, int pos) {
    for (; pos < N; pos |= pos + 1) {
       ++fen[v][pos];
    }
}

int get(int v, int pos) {
    int s = 0;
    for (; pos >= 0; pos = (pos & (pos + 1)) - 1) {
        s += fen[v][pos];
    }
    return s;
}

int get(int v, int l, int r) {
    return get(v, r) - get(v, l - 1);
}

int main() {
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        a[i] = min(a[i], N);
    }
    pref[0].set(0);
    for (int i = 0; i < n - 1; ++i) {
        pref[i + 1] = (pref[i] << a[i]) | pref[i];
    }
    suf[n - 1].set(0);
    for (int i = n - 1; i > 0; --i) {
        suf[i - 1] = (suf[i] << a[i]) | suf[i];
    }
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < k; ++j) {
            if (suf[i][j]) {
                add(i, j);
            }
        }
    }
    int ans = n;
    for (int i = 0; i < n; ++i) {
        bool f = false;
        for (int j = 0; j < k; ++j) {
            if (pref[i][j] && get(i, k - a[i] - j, k - j - 1)) {
                f = true;
                break;
            }
        }
        if (f) {
            --ans;
        }
    }
    cout << ans;
    return 0;
}

Measured memory_bytes: 104192
#include <iostream>

using namespace std;

int N;



int main() {
  cin >> N;

  int x;
  int sum = 0;
  int max = 0;
  for(int i = 0; i < N; i++) {
    cin >> x;
    sum += x;

    if( max < x )
      max = x;
  }

  if (max * 2 < sum) {
    cout << "Yes";
  } else {
    cout << "No";
  }

	return 0;
}


Measured memory_bytes: 256
import java.util.*;

public class Main {
  public static void main(String[] srgs) {
    Scanner sc = new Scanner(System.in);
    int n = Integer.parseInt(sc.next());
    int[] rating = new int[n];
    int[] number = new int[9];
    for(int i = 0; i < 9; i++) number[i] = 0;
    for(int i = 0; i < n; i++) {
      rating[i] = Integer.parseInt(sc.next());
      number[Math.min(rating[i]/400, 8)]++;
    }
    int min = 0;
    for(int i = 0; i < 8; i++) {
      if(number[i] != 0) min++;
    }
    if(min == 0) {
      min = 1;
      number[8]--;
    }
    System.out.print(min + " ");
    int max = min + number[8];
    System.out.println(max);
  }
}


Measured memory_bytes: 21204
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vl = vector<ll>;
using vvl = vector<vector<ll>>;
#define all(x) x.begin(),x.end()
#define rep(i,j,n) for (long long i = j; i < (long long)(n); i++)
#define _GLIBCXX_DEBUG
#define MOD 1000000007
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
//(a+b-1)/b

signed main(){
	int n; cin>>n;
	if(n<600) cout<<8<<endl;
	else if(n<800) cout<<7<<endl;
	else if(n<1000) cout<<6<<endl;
	else if(n<1200) cout<<5<<endl;
	else if(n<1400) cout<<4<<endl;
	else if(n<1600) cout<<3<<endl;
	else if(n<1800) cout<<2<<endl;
	else cout<<1<<endl;
	
	return 0;
}

Measured memory_bytes: 3628
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define repf(i, a, b) for(ll i = (a); i < (b) ; i++ )
const ll mo = 1000000007;
const ll INF = 1LL << 60; //MAX 9223372036854775807
ll ans = 0;

int main()
{
ll n,m;
cin >> n>>m;
ll s[n] = {};
rep(i, n){
    cin >> s[i];
}
ll t[m] = {};
rep(i, m){
    cin >> t[i];
}
ll dp[m+1][n+1]={};

rep(i,m+1){
    dp[i][0]=1;
}
rep(i,n+1){
    dp[0][i]=1;
}
rep(i,m)rep(j,n){
    dp[i+1][j+1]=dp[i][j+1]+dp[i+1][j]-dp[i][j];
    if(s[j]==t[i]){
        dp[i+1][j+1]+=dp[i][j];
        
    }
    if(dp[i+1][j+1]<0)dp[i+1][j+1]+=mo;
    dp[i+1][j+1]%=mo;
}
cout << dp[m][n] << endl;

/* //2次元配列の中身を見る

for (int i = 0; i < m+1; ++i){
for (int j = 0; j < n+1; ++j) {
    cout << dp[i][j] << " ";
}cout  << endl;}
 */
return 0;
}

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

// セグメント木
// ref:https://ei1333.github.io/luzhiled/snippets/structure/segment-tree.html
template <typename Mnd>
struct segment_tree {
    int sz;
    vector<Mnd> data;
    function<Mnd(Mnd, Mnd)> f;
    Mnd e;
    //サイズだけ指定して初期化
    segment_tree(int _sz, function<Mnd(Mnd, Mnd)> _f, Mnd _e) : f(_f), e(_e) {
        sz = 1;
        while (sz < _sz) sz <<= 1;
        data.assign(sz * 2, e);
    }
    //参照渡しなので代入とかもできる
    Mnd& operator[](const int& k) {
        return data[k + sz];
    }
    //木を構築 O(n)
    void build() {
        for (int i = sz - 1; i > 0; i--) data[i] = f(data[2 * i], data[2 * i + 1]);
    }
    //更新しつつ木を再構築 O(log n)
    void update(int k, Mnd x) {
        data[k += sz] = x;
        while (k >>= 1) data[k] = f(data[2 * k], data[2 * k + 1]);
    }
    //[a,b)でのクエリに答える　O(log n)
    Mnd query(int a, int b) const {
        Mnd l = e, r = e;
        for (a += sz, b += sz; a < b; a >>= 1, b >>= 1) {
            if (a & 1) l = f(l, data[a++]);
            if (b & 1) r = f(r, data[--b]);
        }
        return f(l, r);
    }
};

int n, q;
string s;

int count(bitset<26> b) {
    int res = 0;
    for (int i = 0; i < 26; i++) {
        res += b[i];
    }
    return res;
}

int main() {
    cin >> n >> s >> q;
    segment_tree<bitset<26>> seg(
        n, [](const bitset<26> a, const bitset<26> b) { return a | b; }, 0);
    for (int i = 0; i < n; i++) {
        int c = s[i] - 'a';
        seg[i] = (1 << c);
    }
    seg.build();
    for (int i = 0; i < q; i++) {
        int t;
        cin >> t;
        if (t == 1) {
            int x;
            char c;
            cin >> x >> c;
            x--;
            int keta = c - 'a';
            seg.update(x, 1 << keta);
        } else {
            int l, r;
            cin >> l >> r;
            l--;
            cout << count(seg.query(l, r)) << endl;
        }
    }
}

Measured memory_bytes: 9092
#include<bits/stdc++.h>
using namespace std;
int main(){
  string s;
  cin>>s;
  int count=0;
  for(int i=0;i<s.size();i++){
    if(s[i]=='o')count++;
  }
  cout<<((count+15-s.size())>=8?"YES":"NO")<<endl;
}

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

#define rep(i,n) for(int i = 0; i < n; i++)
#define Rep(i,n) for(int i = 1; i <= n; i++)
#define sz(x) int(x.size())
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define YesorNo(a) printf(a ? "Yes\n" : "No\n")
#define endl '\n'
#define fi first
#define se second
using ll = long long;
using P = pair<int,int>;
using Pl = pair<ll,ll>;
template<class T> using V = vector<T>;
const int dx[] = {0,1,0,-1,1,1,-1,-1};
const int dy[] = {1,0,-1,0,1,-1,-1,1};
const int inf = (1<<30)-1;
const ll infll = (1LL<<62)-1;
ll ceil(const ll &a, const ll &b){return ((a)+(b)-1)/b;}
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }


struct UnionFind { // UnionFindTree
  vector<int> d;
  UnionFind(int n): d(n,-1) {}
  int find(int x) {
    if(d[x] < 0) return x;
    return d[x] = find(d[x]);
  }
  bool unite(int x, int y) {
    x = find(x);
    y = find(y);
    if(x == y) return false;
    if(-d[x] < -d[y]) swap(x,y);
    d[x] += d[y];
    d[y] = x;
    return true;
  }
  bool same(int x, int y) { return find(x) == find(y); }
  int size(int x) { return -d[find(x)]; }
};


int main(){
    
    int n, m;
    cin >> n >> m;
    V<int> a(n);
    rep(i,n) cin >> a[i];
    UnionFind uf(n);
    rep(i,m) {
        int x, y;
        cin >> x >> y;
        uf.unite(x,y);
    }

    map<int, V<int>> mp;
    rep(i,n) {
        mp[uf.find(i)].push_back(a[i]);
    }
    int cnt = 0;
    ll ans = 0;
    V<int> remain;
    for(auto &p : mp) {
        cnt++;
        sort(all(p.se));
        ans += p.se[0];
        for(int i = 1; i < sz(p.se); i++) {
            remain.push_back(p.se[i]);
        }
    }
    
    if((cnt-1)*2 > n) {
        cout << "Impossible" << endl;
        return 0;
    }

    if(cnt == 1) {
        cout << 0 << endl;
        return 0;
    }

    sort(all(remain));
    rep(i,(cnt-1)*2-cnt) ans += remain[i];
    cout << ans << endl;
}

Measured memory_bytes: 14760
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
using vl = vector<ll>;

/* short */
#define pb push_back
#define mp make_pair
#define Fi first
#define Se second
#define ALL(v) begin(v), end(v)
#define RALL(v) rbegin(v), rend(v)

/* REPmacro */
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define FORR(i, a, b) for(int i = (a); i >= (b); i--)
#define REP(i, n) for(int i = 0; i < (n); i++)
#define FOREACH(x, a) for(auto x : a)

/* exchange */
#define CHMIN(a, b) (a) = min((ll)(a), (ll)(b))
#define CHMAX(a, b) (a) = max((ll)(a), (ll)(b))

/* function */
#define IN(x) cin >> x
#define DEBUG(x) cerr << (x) << " "
#define LN() cerr << "\n"
#define PRINT(x) cout << (x) << endl
#define BR cout << endl

/* const */
const int ARRAY = 100005;
const int INF = 1001001001; // 10^9
const ll LINF = 1001001001001001001; // 10^18
const int MOD = 1e9 + 7;

ll N = 0;
ll Q;
ll K = 0;
ll t;
ll ret = 0;
string s;
vector<char> A;
vector<char> B;
bool rev = false;

void input() {
  IN(s);
  IN(Q);
  REP(i, Q) {
    IN(t);
    if (t == 1) {
      rev = !rev;
    } else {
      ll f;
      char c;
      IN(f);
      IN(c);
      if (f == 1 && !rev) {
        A.pb(c);
      }
      if (f == 2 && !rev) {
        B.pb(c);
      }
      if (f == 1 && rev) {
        B.pb(c);
      }
      if (f == 2 && rev) {
        A.pb(c);
      }
    }
  }
}

void solve() {
  if (!rev) {
    for(ll i = A.size()-1; i >= 0; i--) {
      cout << A[i];
    }
    cout << s;
    for(ll i = 0; i < B.size(); i++) {
      cout << B[i];
    }
  } else {
    for(ll i = B.size()-1; i >= 0; i--) {
      cout << B[i];
    }
    for(ll i = s.length()-1; i >= 0; i--) {
      cout << s[i];
    }
    for(ll i = 0; i < A.size(); i++) {
      cout << A[i];
    }
  }
  cout << endl;
}

int main(void){
  input();
  solve();
}


Measured memory_bytes: 1024
string = input()

n = int(input())

for i in range(n):
    command = input().split()
    c_n = command[0]
    c_i1 = int(command[1])
    c_i2 = int(command[2]) + 1
    if c_n == "print":
        print(string[c_i1:c_i2])
    elif c_n == "reverse":
        string = string[:c_i1] + string[c_i1:c_i2][::-1] + string[c_i2:]
    else:
        string = string[:c_i1] + command[3] + string[c_i2:]

Measured memory_bytes: 7680
#include <bits/stdc++.h>
#define re register
#define SIZE 305
#define INF 0x7f7f7f
using namespace std;
int n;
int a[SIZE];
int cnt[5];
double dp[SIZE*3][SIZE*2][SIZE],ans=0;
inline double dfs(int i,int j,int k)
{ 
	if(dp[i][j][k]!=-1)
		return dp[i][j][k];
	dp[i][j][k]=0;
	double x=i*1.0,y=j*1.0,z=k*1.0;
	double m=x+y+z;
	if(i+j+k<n)
		dp[i][j][k]+=dfs(i+1,j,k)*(x+1)/(m+1);
	if(i-1>=0)
		dp[i][j][k]+=dfs(i-1,j+1,k)*(y+1)/m;
	if(j-1>=0)
		dp[i][j][k]+=dfs(i,j-1,k+1)*(z+1)/m;
	return dp[i][j][k];
}
int main()
{
	scanf("%d",&n);
	for(re int i=1;i<=n;++i)
		scanf("%d",&a[i]),++cnt[a[i]];
	for(re int i=0;i<=cnt[3]+cnt[2]+cnt[1]+1;++i)
		for(re int j=0;j<=cnt[3]+cnt[2]+1;++j)
			for(re int k=0;k<=cnt[3]+1;++k)
				if(i>cnt[3]+cnt[2]+cnt[1] || j>cnt[3]+cnt[2] || k>cnt[3])
					dp[i][j][k]=0;
				else
					dp[i][j][k]=-1;
	dp[cnt[1]][cnt[2]][cnt[3]]=1;
	for(re int i=0;i<=cnt[3]+cnt[2]+cnt[1];++i)
		for(re int j=0;j<=cnt[3]+cnt[2];++j)
			for(re int k=0;k<=cnt[3];++k)
			{
				if(i==0 && j==0 && k==0)
					continue; 
				ans+=(double) (dfs(i,j,k)*n)/(double) (i+j+k);
			}
	printf("%.10lf\n",ans);
	return 0;
} 

Measured memory_bytes: 222416
#include<stdio.h>

int main(void){
	int a[5],i,j;
	scanf("%d %d %d %d %d",&a[0],&a[1],&a[2],&a[3],&a[4]);

	for(i=0;i<5;i++){
		for(j=0;j<4;j++){
			int t;
			if(a[j]<a[j+1]){
				t=a[j];
				a[j]=a[j+1];
				a[j+1]=t;
			}
		}
	}
	printf("%d %d %d %d %d\n",a[0],a[1],a[2],a[3],a[4]);
	return 0;	
}

Measured memory_bytes: 596
#include <iostream>

using namespace std;

bool check(int num)
{
    int cnt = 0;
    for(int i=1;i*i<num;i++) {
        if(num % i == 0) {
            cnt++;
        }
    }
    return cnt >= 4;
}

int main()
{
    int N;
    cin >> N;
    
    int cnt=0;
    for(int i=1; i<=N; i=i+2) {
        if(check(i)) {
            cnt++;
        }
    }

    cout << cnt << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, srt, end) for (long long i = (srt); i < (long long)(end); i++)
#define VL vector<ll>
#define VS vector<string>
#define VB vector<bool>
#define VP vector<pair<ll,ll>>
#define VVL vector<vector<ll>>
#define VVP vector<vector<pair<ll,ll>>>
#define PL pair<ll,ll>
#define ALL(v) (v).begin(), (v).end()
ll d1[4] = {1, -1, 0, 0};
ll d2[4] = {0, 0, 1, -1};

int main(){
    ll N, K;
    cin >> N >> K;
    VL G(N);
    rep(i, 0, N){
        ll a;
        cin >> a;
        a--;
        G[i] = a;
    }
    ll pos = 0, itr = 0;
    ll tri;
    VB seen(N, false);
    VL ans(N);
    while(true){
        if(seen[pos]){
            tri = pos;
            cerr << itr << endl;
            break;
        }
        seen[pos] = true;
        ans[itr] = pos;
        itr++;
        pos = G[pos];
    }
    pos = 0;
    ll cnt = 0;
    while(true){
        if(pos == tri) break;
        pos = G[pos];
        cnt++;
    }

    if(cnt >= K){
        cout << ans[K]+1 << endl;
        return 0;
    }

    ll r = cnt;

    cnt = 1;
    pos = G[tri];
    while(true){
        if(pos == tri){
            break;
        }
        pos = G[pos];
        cnt++;
    }

    cerr << r << endl;
    cerr << cnt << endl;

    cout << ans[((K - r) % cnt) + r] +1<< endl;
    return 0;
}

Measured memory_bytes: 6428
from itertools import accumulate

N = int(input())
W = [int(_) for _ in input().split()]

W_ = [0] + W
sumW = list(accumulate(W_))

ans = float('inf')

for T in range(N):
    S1 = sumW[T]
    S2 = sumW[N] - sumW[T]
    ans = min(ans, abs(S1 - S2))

print(ans)


Measured memory_bytes: 3060
#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;
typedef tuple<ll,ll,ll> T;
const long long INF = 1LL<<60;
const int MOD = 1000000000+7;
#define rev(s) (string((s).rbegin(), (s).rend()))
template < typename T > inline string toString( const T &a ) { ostringstream oss; oss << a; return oss.str(); };
// cout << fixed << setprecision(10) << ans << endl;
// *min_element(c + l, c + r) *max_element(c + l, c + r)
// int dx[8]={1,1,0,-1,-1,-1,0,1};
// int dy[8]={0,1,1,1,0,-1,-1,-1};
// int dx[4]={1,0,-1,0};
// int dy[4]={0,1,0,-1};
// struct Edge {
//   int to, id;
//   Edge(int to, int id): to(to), id(id) {}
// };

const int MAX = 1000010;
// const int MOD = 1000000007;

long long fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

int main() {
    int X,Y;cin>>X>>Y;
    COMinit();
    if((X+Y)%3!=0) {
        cout<<0<<endl;
        return 0;
    }
    cout<< COM((X+Y)/3,(2*X-Y)/3) <<endl;
}

Measured memory_bytes: 27072
import sys

sys.setrecursionlimit(10 ** 8)
ini = lambda: int(sys.stdin.readline())
inm = lambda: map(int, sys.stdin.readline().split())
inl = lambda: list(inm())
ins = lambda: sys.stdin.readline().rstrip()
debug = lambda *a, **kw: print("\033[33m", *a, "\033[0m", **dict(file=sys.stderr, **kw))

N = ini()
A, B = [], []
for i in range(N):
    a, b = inm()
    A.append(a)
    B.append(b)


def solve():
    sa = sorted(A)
    sb = sorted(B)
    if N % 2 == 1:
        return sb[N // 2] - sa[N // 2] + 1
    else:
        return (sb[N // 2] + sb[N // 2 - 1]) - (sa[N // 2] + sa[N // 2 - 1]) + 1


print(solve())


Measured memory_bytes: 28564
S = list(map(str, input()))

F = int(S[0]+S[1])
L = int(S[2]+S[3])

if (L == 0 and F == 0) or (F > 12 and L > 12) or (F == 0 and L > 12) or (L == 0 and F > 12):
  print('NA')

elif F <= 12 and (L > 12 or L == 0):
  print('MMYY')
  
elif L <= 12 and (F > 12 or F == 0):
  print('YYMM')
  
 
else:
  print('AMBIGUOUS')

Measured memory_bytes: 3064
#include <iostream>
#include <algorithm>
#include <string>
#include <functional>
#include <math.h>
#include <map>
#include <vector>
using namespace std;

int main() {
	long long n;
	cin >> n;
	string s;
	char s2[100000];
	for (long long i = 0; i < n; i++) {
		cin >> s;
		s2[i] = s[0];
	}
	long long M = 0, A = 0, R = 0, C = 0, H = 0;
	for (long long i = 0; i < n; i++) {
		if (s2[i] == 'M') {
			M++;
		}
		if (s2[i] == 'A') {
			A++;
		}
		if (s2[i] == 'R') {
			R++;
		}
		if (s2[i] == 'C') {
			C++;
		}
		if (s2[i] == 'H') {
			H++;
		}
	}
	cout << M*A*R + M*A*C + M*A*H + M*R*C + M*R*H + M*C*H + A*R*C + A*R*H + A*C*H + R*C*H << endl;

	return 0;
}

Measured memory_bytes: 384
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int INF = 1e9;
const ll LINF = 1e18;
template<class S,class T> ostream &operator << (ostream& out,const pair<S,T>& o){
    out << "(" << o.first << "," << o.second << ")"; return out;
}
/*
<url:>
問題文============================================================

=================================================================

解説=============================================================

================================================================
*/

ll V;
vector<vector<ll>> G;
vector<ll> match;
vector<int> used;

void add_edge(ll u, ll v) {
    G[u].push_back(v);
    G[v].push_back(u);
}

bool dfs(ll v) {
    used[v] = 1;
    for (int i = 0; i < G[v].size(); i++) {
        ll u = G[v][i], w = match[u];
        if (w < 0 || ((used[w] == 0) && dfs(w))) {
            match[v] = u;
            match[u] = v;
            return true;
        }
    }
    return false;
}

ll bipartite_matching() {
    ll res = 0;
    for (int i = 0; i < (int)match.size();i++)match[i] = -1;
    for (int v = 0;v < V;v++) {
        if (match[v] < 0) {
            for (int i = 0; i < (int)used.size();i++)used[i] = 0;
            if (dfs(v))res++;
        }
    }
    return res;
}

ll solve(){
    ll res = 0;
    ll N; cin >> N;
    vector<ll> a(N),b(N),c(N),d(N);
    for(int i = 0; i < N;i++) cin >> a[i] >> b[i];
    for(int i = 0; i < N;i++) cin >> c[i] >> d[i];
    
    match.resize(2*N); used.resize(2*N); G.resize(2*N);
    V = 2*N;
    for(int i = 0; i < N;i++){
        for(int j = 0; j < N;j++){
            if(a[i] < c[j] && b[i] < d[j]){
                add_edge(i,N+j);
            }
        }
    }
    res = bipartite_matching();
    return res;
}
int main(void) {
	cin.tie(0); ios::sync_with_stdio(false);
    cout << solve() << endl;
	return 0;
}


Measured memory_bytes: 384
#include <iostream>

 int main()
{
    int a,b;
    std::cin >> a >> b;
    if (a > b) {
        std::cout << "a > b" << std::endl;
    } else if (a == b) {
        std::cout << "a == b" << std::endl;
    } else {
        std::cout << "a < b" << std::endl;
    }
    return 0;
   }


Measured memory_bytes: 3076
#include <bits/stdc++.h>
#define rep(i, n) for (ll i = 0; i < (n); i++)
#define all(x) (x).begin(), (x).end()
using ll = long long;
using namespace std;
template <typename T> using vec = std::vector<T>;

int main() {
    ll N;
    cin >> N;
    
    vec<ll> A(N);
    rep(i, N) cin >> A[i];
    sort(all(A),greater<ll>());
    
    ll ans = 0;
    for(int i=1;i<N;++i){
        ans+=A[i/2];
    }
    cout << ans << endl;
}


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

int main() {
    int a, b;
    cin >> a >> b;
    if(a < 9 && b < 9) cout << "Yay!" << endl;
    else cout << ":(" << endl;
    return 0;
}

Measured memory_bytes: 384
# include <iostream>
# include <algorithm>
# include <vector>
# include <string>
# include <set>
# include <map>
# include <cmath>
# include <iomanip>
# include <functional>
# include <utility>
# include <stack>
# include <queue>
# include <list>
# include <unordered_map>
constexpr int MOD = 1000000000 + 7;
constexpr int INF = 2000000000;
using namespace std;
using LL = long long;

int main() {
	int n;
	cin >> n;
	vector<int> A;
	int a;
	for (int i = 0; i < n; i++) {
		cin >> a;
		A.emplace_back(a);
	}
	sort(A.begin(), A.end(), greater<int>());
	LL ans = 1;
	int count = 0;
	for (int i = 0; i < n - 1; i++) {
		if (A[i] == A[i + 1]) {
			if (count < 2) {
				ans *= A[i];
			}
			i++;
			count++;
		}
	}
	cout << (count >= 2 ? ans : 0) << endl;
}

Measured memory_bytes: 892
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int INF = 1e9;
const ll LINF = 1e18;
template<class S,class T> ostream& operator << (ostream& out,const pair<S,T>& o){ out << "(" << o.first << "," << o.second << ")"; return out; }
template<class T> ostream& operator << (ostream& out,const vector<T> V){ for(int i = 0; i < V.size(); i++){ out << V[i]; if(i!=V.size()-1) out << " ";} return out; }
template<class T> ostream& operator << (ostream& out,const vector<vector<T> > Mat){ for(int i = 0; i < Mat.size(); i++) { if(i != 0) out << endl; out << Mat[i];} return out; }
template<class S,class T> ostream& operator << (ostream& out,const map<S,T> mp){ out << "{ "; for(auto it = mp.begin(); it != mp.end(); it++){ out << it->first << ":" << it->second; if(mp.size()-1 != distance(mp.begin(),it)) out << ", "; } out << " }"; return out; }

/*
 <url:>
 問題文============================================================
 =================================================================
 解説=============================================================
 ================================================================
 */

ll solve(){
    ll res = 0;
    ll N,M; cin >> N >> M;
    vector<ll> toys(N); for(auto&in:toys) cin >> in;
    vector<vector<ll>> cusum(N+1,vector<ll>(M));
    for(int i = 0; i < N;i++){
        toys[i]--;
        for(int j = 0; j < M;j++){
            cusum[i+1][j] = cusum[i][j] + (toys[i]==j);
        }
    }
    vector<ll> bitdp(1<<M,LINF);
    bitdp[0] = 0;
    for(int i = 0; i < (1<<M);i++){
        if(bitdp[i] == LINF) continue;
        ll T = 0;
        for(int j = 0; j < M;j++){
            if((i>>j)&1) T += cusum[N][j];
        }
        for(int j = 0; j < M;j++){
            if((i>>j)&1) continue;
            bitdp[i|1<<j] = min(bitdp[i|1<<j],
                                bitdp[i]+cusum[N][j]-(cusum[T+cusum[N][j]][j]-cusum[T][j]));
        }
    }
    res = bitdp[(1<<M)-1];
    return res;
}
int main(void) {
    cin.tie(0); ios_base::sync_with_stdio(false);
    cout << solve() << endl;
    return 0;
}



Measured memory_bytes: 31148
import java.util.*;

public class Main {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int a = scan.nextInt();
		int b = scan.nextInt();
		int ans = a * b;
		if(ans%2 == 0){
			System.out.println("Even");
		}else{
			System.out.println("Odd");
		}
		
	}

}


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

int main(){
  int a[5], k;
  for(int i=0; i<5; i++) cin >> a[i];
  cin >> k;
  for(int i=0; i<5;i++){
    for(int j=0; j<5;j++){
      if(a[i]-a[j]>k){
        cout << ":(" << endl;
        return 0;
      }
    }
  }
  cout << "Yay!" << endl;
  return 0;
}


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

using namespace std;

int main()
{
    int A, B, C, D;
    cin >> A >> B >> C >> D;

    int atackA, atackB;
    atackA = C / B;
    if (C % B)
        atackA++;
    atackB = A / D;
    if (A % D)
        atackB++;
    string ans = "No";
    if (atackA <= atackB)
        ans = "Yes";
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3628
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <vector>
#define rep(i,n) for (int i=0; i<(n); ++i)
using namespace std;
using ll = long long;
using P = pair<int, int>;

const int INF = 1001001001;

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

    vector<int> s;
    rep(i, N) s.push_back(0);

    rep(i, K) {
        int d;
        cin >> d;

        rep(j, d) {
            int sNum;
            cin >> sNum;

            s[sNum-1] += 1;
        }
    }

    int res = 0;
    rep(i, N) {
        if (s[i] == 0) ++res;
    }
    
    cout << res << endl;

    return 0;
}

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

int main() {
  
   long int n,W;
   cin>>n>>W;
   
   long int w[n],v[n];

   for(long int i=0;i<n;i++) cin>>w[i]>>v[i];

   long int dp[n][W+1];

   memset(dp,0,sizeof(dp));

   for(long int j=w[0];j<=W;j++) dp[0][j] = v[0];
   
   for(long int i=1;i<n;i++) {
        
   	    for(long int j=0;j<=W;j++) {
   	    	if(j < w[i]) dp[i][j] = dp[i-1][j];
   	    	else dp[i][j] = max(dp[i-1][j], v[i] + dp[i-1][j-w[i]]);
   	    }
   }
   
   cout<<dp[n-1][W]<<endl;
return 0;	
}

Measured memory_bytes: 81620
#include<bits/stdc++.h>
using namespace std;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}

template<typename F>
struct FixPoint : F{
  FixPoint(F&& f):F(forward<F>(f)){}
  template<typename... Args>
  decltype(auto) operator()(Args&&... args) const{
    return F::operator()(*this,forward<Args>(args)...);
  }
};
template<typename F>
inline decltype(auto) MFP(F&& f){
  return FixPoint<F>{forward<F>(f)};
}

//INSERT ABOVE HERE
signed main(){
  using ll = long long;

  ll d;
  cin>>d;

  const ll MAX = 19;

  vector<ll> po(MAX,1);
  for(int i=0;i+1<MAX;i++)
    po[i+1]=po[i]*10;

  vector<ll> c1(12,0),c2(12,0);
  for(int i=1;i<10;i++)
    for(int j=1;j<=i;j++)
      c1[abs(i-j)]++;

  for(int i=0;i<10;i++)
    for(int j=0;j<=i;j++)
      c2[abs(i-j)]++;

  ll ans=0;
  for(int l=2;l<=MAX;l++){
    // [s, t]
    ans+=
      MFP([&](auto dfs,ll s,ll t,ll w)->ll{
            if(s>=t){
              if(w!=0) return 0;
              return s==t?10:1;
            }
            ll dif=po[t]-po[s];
            ll x=w/dif;
            if(x>=10) return 0;

            ll res=0;
            res+=(s==0?c1:c2)[x+0]*dfs(s+1,t-1,abs(w-(x+0)*dif));
            res+=(s==0?c1:c2)[x+1]*dfs(s+1,t-1,abs(w-(x+1)*dif));
            return res;
          })(0,l-1,d);
  }
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 256
using System;
class c
{
  static void Main()
  {
    int N=int.Parse(Console.ReadLine());
    int K=int.Parse(Console.ReadLine());
    int ans=1;
    for(int i=0;i<N;i++)
    {
      ans=Math.Min(ans*2,ans+K);
    }
    Console.WriteLine(ans);
  }
}

Measured memory_bytes: 13140
#include "bits/stdc++.h"

using namespace std;

using ll = long long;
using ld = long double;
using P = pair<ll, ll>;
constexpr ld EPS = 1e-12;
constexpr int INF = numeric_limits<int>::max() / 2;
constexpr int MOD = 1e9 + 7;

vector<vector<int>> sum(6000, vector<int>(6000, 0));

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

    int n, m;
    cin >> n >> m;
    vector<P> v(n);
    set<ll> xst, yst;
    for (int i = 0; i < n; i++)
    {
        ll x, y;
        cin >> x >> y;
        x += 1e10;
        y += 1e10;
        v[i] = P(x, y);
        xst.insert(x);
        yst.insert(y);
    }
    map<int, int> xmp, ymp;
    int idx = 1;
    xmp[0] = 0;
    for (auto x : xst)
    {
        xmp[x] = idx;
        idx++;
    }
    idx = 1;
    ymp[0] = 0;
    for (auto y : yst)
    {
        ymp[y] = idx;
        idx++;
    }
    int xsz = xst.size(), ysz = yst.size();
    for (int i = 0; i < n; i++)
    {
        ll x = v[i].first, y = v[i].second;
        x = xmp[x];
        y = ymp[y];
        sum[x][y]++;
    }
    for (int i = 1; i <= xsz; i++)
    {
        for (int j = 1; j <= ysz; j++)
        {
            sum[i][j] += sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];
        }
    }
    for (int i = 0; i < m; i++)
    {
        ll sx, sy, gx, gy;
        cin >> sx >> sy >> gx >> gy;
        sx += 1e10;
        sy += 1e10;
        gx += 1e10;
        gy += 1e10;
        auto x1 = xst.lower_bound(sx);
        auto y1 = yst.lower_bound(sy);
        auto x2 = xst.upper_bound(gx);
        auto y2 = yst.upper_bound(gy);
        if (x1 == xst.end() || y1 == yst.end())
        {
            cout << 0 << endl;
            continue;
        }
        x2--;
        y2--;
        sx = xmp[*x1];
        sy = ymp[*y1];
        gx = xmp[*x2];
        gy = ymp[*y2];
        //cout<<sx<<" "<<sy<<" "<<gx<<" "<<gy<<endl;
        cout << sum[gx][gy] - sum[sx - 1][gy] - sum[gx][sy - 1] + sum[sx - 1][sy - 1] << endl;
    }
}



Measured memory_bytes: 144912
/***
*	5-1 ?????????
****/

#include <iostream>
#include <vector>
using namespace std;

//--------------------------------------------
vector<int> input()
{
	int n;
	cin >> n ;
	vector<int> str;
	str.resize(n);
	
	for(int i=0; i< n; i++){
		cin >> str[i];
	}
	return str;
}
//--------------------------------------------
void judge(bool result)
{
	if (result){
		cout << "yes" << endl;
	} else {
		cout << "no" << endl;
	}
}
//--------------------------------------------

//--------------------------------------------
bool solve(int i, int m, vector<int> &A)
{
	if(m==0){
		return true;
	}
	if(i >= (A.size())){
		return false;
	}
//	bool res ;
//	//i????????????????????¨??????????????????
//	bool res1 = solve((i+1), m, A);
//	//i?????????????????¨??????A[i]?????????
//	bool res2 = solve((i+1), m- A[i], A);
//	if(res1 || res2){
//		res = true;
//	}
//	else{
//		res = false;
//	}
	bool res = solve((i+1), m, A)||solve((i+1), m-A[i], A); 

	return res;
}
//--------------------------------------------
int main()
{
	//??°????????\???
	vector<int> strA = input();
	
	//?????????q?????\???
	int q;
	cin >> q;
	
	//q????????°??????????????????
	for	(int i=0; i< q; i++){
		int integM;
		cin >> integM;
		
		//i ????????\??????????´?????????£??? m ??????????????´??? true ???????????¢??°
		bool result = solve(0, integM, strA);
		
		//?????????q????????????
		judge(result);
	}
	
	return 0;
}

Measured memory_bytes: 1188
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <memory.h>

#define pb push_back

using namespace std;

int n, k, m = 0;
string s;

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

    for(int i = 0; i < s.length(); i++)
    {
        if((i % 2 == 0 && s[i] == 'A') || (i % 2 == 1 && s[i] == 'B'))
            m += 2;
        else
            m++;
    }

    if(k >= m)
    {
        k = k - m;
        if(s.length() % 2 == 1)
        {
            if(k % 2 == 0)
                cout << "A";
            else
                cout << "B";
            for(int i = 1; i < s.length(); i++)
                if(i % 2 == 1)
                    cout << "B";
                else
                    cout << "A";
        }else
        {
            for(int i = 0; i < s.length(); i++)
                if(i % 2 == 0)
                    cout << "B";
                else
                    cout << "A";
        }
    }else
    {
        bool u = 1;
        deque <int> dq;
        for(int i = 0 ; i < s.size() ; i ++)
            dq.pb(int(s[i] - 'A'));
        while(k --)
        {
            if(u && dq.front() == 0 || !u && dq.front() == 1)
                dq.front() ^= 1;
            else
            {
                dq.pop_front();
                u ^= 1;
                if(u)
                    dq.pb(0);
                else
                    dq.pb(1);
            }
        }
        while(!dq.empty())
        {
            if(u)
                cout << ((dq.front()) ? 'B' : 'A');
            else
                cout << ((dq.front() ^ 1) ? 'B' : 'A');
            dq.pop_front();
        }
    }

    return 0;
}


Measured memory_bytes: 1540
n, m = map(int, input().split())
a = list(map(int, input().split()))
l = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
dp = [-1] * (n+1)
dp[0] =  0

for i in range(n+1):
    for j in a:
        if i + l[j] < n+1:
            dp[i + l[j]] = max(dp[i + l[j]], dp[i]*10 + j)
print(dp[-1])

Measured memory_bytes: 20480
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<string>
#define rep(i,n) for(int i=0;i<n;i++)

using namespace std;

int main(){

long long s;
cin >>s;
int x[10];
long long t=10'0000'0000;
rep(i,10){
x[i]=s/t;
if(s>=t){
    s-=t*x[i];
}
t/=10;
}
int sum;
int Ans=753;
int dif;
for(int i=2;i<10;i++){
sum=x[i-2]*100+x[i-1]*10+x[i]*1;
dif=abs(753-sum);
Ans=min(Ans,dif);
}
cout <<Ans<<endl;
 return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include "math.h"
using namespace std;

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

    int a_order=0;

    if(b/100){
        a_order =1000;
    }else if(b/10){
        a_order =100;
    }else{
        a_order=10;
    }

    int concat_number;
    concat_number = a*a_order + b;

    if(sqrt(concat_number)-int(sqrt(concat_number))==0) {
        cout << "Yes";
    }else{
        cout << "No";
    }

    return 0;
}

Measured memory_bytes: 256
#include <algorithm>  
#include <iostream>  
#include <sstream>  
#include <string>  
#include <cstring>
#include <vector>  
#include <queue>  
#include <set>  
#include <map>  
#include <cstdio>  
#include <cstdlib>  
#include <cctype>  
#include <cmath>  
#include <list>  
#include <cassert>
#include <ctime>
#include <climits>
using namespace std;  

#define PB push_back  
#define MP make_pair  
#define SZ(v) ((int)(v).size())  
#define FOR(i,a,b) for(int i=(a);i<(b);++i)  
#define REP(i,n) FOR(i,0,n)  
#define FORE(i,a,b) for(int i=(a);i<=(b);++i)  
#define REPE(i,n) FORE(i,0,n)  
#define FORSZ(i,a,v) FOR(i,a,SZ(v))  
#define REPSZ(i,v) REP(i,SZ(v))  
typedef long long ll;
typedef unsigned long long ull;
ll gcd(ll a,ll b) { return b==0?a:gcd(b,a%b); }

const int MAXN=10000;
const int MAXLEN=20;

bool calcbefore(char *s,int slen,char *t,int tlen) {
	int len=min(slen,tlen);
	REP(i,len) {
		if(s[i]=='?') { assert(t[i]!='?'); if(t[i]=='a') continue; else return true; }
		if(t[i]=='?') { assert(s[i]!='?'); if(s[i]=='z') continue; else return true; }
		if(s[i]!=t[i]) return s[i]<t[i];
	}
	return slen<=tlen;
}


int n;
char s[MAXN][MAXLEN+1];
char t[MAXN];
int slen[MAXN];
int tlen;


void run() {
	scanf("%d",&n);
	REP(i,n) scanf("%s",s[i]); scanf("%s",t);
	REP(i,n) slen[i]=strlen(s[i]); tlen=strlen(t);
	REP(i,tlen) assert(t[i]!='?');
	int nbefore=0,nafter=0,neither=0;
	REP(i,n) {
		bool canbefore=calcbefore(s[i],slen[i],t,tlen);
		bool canafter=calcbefore(t,tlen,s[i],slen[i]);
		assert(canbefore||canafter);
		if(canbefore&&canafter) ++neither; else if(canbefore) ++nbefore; else ++nafter;
	}
	REPE(i,neither) { if(i!=0) printf(" "); printf("%d",1+nbefore+i); } puts("");
}

int main() {
	run();
	return 0;
}


Measured memory_bytes: 512
#include <stdio.h>

int A[1000000], n;

/* 二分探索 */
int binarySearch(int key) {
  int left = 0;
  int right = n;
  int mid;
  while(left < right) {
    mid = (left + right) / 2;
    if(key == A[mid]) return 1; /* keyを発見 */
    if(key > A[mid]) left = mid + 1; /* 後半を探索 */
    else if(key < A[mid]) right = mid; /* 前半を探索 */
  }
  return 0;
}

int main(void) {
  int i, q, k, sum = 0;
  scanf("%d",&n);
  for(i=0; i<n; i++) {
    scanf("%d",&A[i]);
  }
  scanf("%d",&q);
  for(i=0;i<q;i++) {
    scanf("%d",&k);
    if(binarySearch(k))
      sum++;
  }
  printf("%d\n",sum);
  return 0;
}


Measured memory_bytes: 2196