akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <numeric>
#include <stdio.h>
#include <stack>
#include <queue>
#include <cstdio>
#include <cmath>
#include <iterator>
#include <map>
#include <cctype>

using namespace std;

#define Int int64_t

void printVec(std::vector<int>& vec) {
	std::cout << "";
	for (auto it = vec.begin(); it != vec.end(); ++it) {
		std::cout << *it << " ";
	}
	std::cout << std::endl;
}
void printVec1(std::vector<string>& vec) {
	std::cout << "";
	for (auto it = vec.begin(); it != vec.end(); ++it) {
		std::cout << *it << " ";
	}
	std::cout << std::endl;
}

template<typename T>
void remove(std::vector<T>& vector, unsigned int index)
{
	vector.erase(vector.begin() + index);
}

int vector_finder(std::vector<string> vec, string number) {
	auto itr = std::find(vec.begin(), vec.end(), number);
	size_t index = std::distance(vec.begin(), itr);
	if (index != vec.size()) { // 発見できたとき
		return 1;
	}
	else { // 発見できなかったとき
		return 0;
	}
}

#include <sstream> 
std::vector<std::string> StringSplit(const std::string& str, char sep)
{
	std::vector<std::string> v;
	std::stringstream ss(str);
	std::string buffer;
	while (std::getline(ss, buffer, sep)) {
		v.push_back(buffer);
	}
	return v;
}



int main() {
	int n; cin >> n;
	int count = 0;
	int x, y;
	for (int i = 0; i < n; i++) {
		cin >> x >> y;
		count += y - x + 1;
	}

	cout << count << endl;

	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <string>

#define FastIO 					\
	ios::sync_with_stdio(0); 	\
	cin.tie(NULL); 				\
	cout.tie(NULL);

using namespace std;

typedef long long ll;

const ll MAXN = 1e6 + 10;
ll N;
ll lf[MAXN], a[MAXN], c[MAXN];

void pf() {
	for (ll i = 0; i < MAXN; i++) {
		lf[i] = i;
	}
	for (ll i = 2; i < MAXN; i++) {
		if (i != lf[i]) {
			continue;
		}
		for (ll j = i * i; j < MAXN; j += i) {
			lf[j] = i;
		}
	}
}

bool ipc() {
	for (ll i = 0; i < MAXN; i++) {
		c[i] = 0;
	}
	for (ll i = 0; i < N; i++) {
		ll x = a[i];
		while (x != 1) {
			ll lfx = lf[x];
			c[lfx]++;
			if (c[lfx] > 1) {
				return 0;
			}
			while (x % lfx == 0) {
				x /= lfx;
			}
		}
	}
	return 1;
}

bool isc() {
	ll t = a[0];
	for (ll i = 1; i < N; i++) {
		t = __gcd(t, a[i]);
	}
	return (t == 1);
}

void solve() {
	pf();
	cin >> N;
	for (ll i = 0; i < N; i++) {
		cin >> a[i];
	}
	if (ipc()) {
		cout << "pairwise coprime\n";
	} else if (isc()) {
		cout << "setwise coprime\n";
	} else {
		cout << "not coprime\n";
	}
}

int main() {
	FastIO;
	int n = 1;
	// cin >> n;
	while (n--) {
		solve();
	}
}


Measured memory_bytes: 27080
import java.util.Arrays;
import java.util.*;

public class Main {
	public static void main(String [] args)
	{
		int i=0,j=0;
		int a[]=new int[10];
		Scanner scan=new Scanner(System.in);
		for(i=0;i<=9;i++)
			 a[i]=scan.nextInt();
		Arrays.sort(a);
		for(i=0;i<3;i++)
			System.out.println(a[9-i]);
	}

}

Measured memory_bytes: 17168
N = int(input())
ans = set()
for length in range(3, len(str(N)) + 1):
    for t in range(3 ** length):
        xs = [[3, 5, 7][t // 3**i % 3] for i in range(length)]
        if 3 in xs and 5 in xs and 7 in xs:
            n = int(''.join(map(str, xs)))
            if 1 <= n <= N:
                ans.add(n)
print(len(ans))

Measured memory_bytes: 6220
#include <bits/stdc++.h>
using ll=long long int;
using namespace std;
typedef pair<int, int>pi;
int main() {
	
		string s; cin >> s;
		int c = 0;
		for (char K : s)if (K == 'S')c++;
		if (c == 3)puts("0");
		else if (c == 1 && s[0] == 'R' && s[1] == 'R')puts("2");
		else if (c == 1 && s[1] == 'R' && s[2] == 'R')puts("2");
		else if (c == 0)puts("3");
		else puts("1");

	return 0;
}

Measured memory_bytes: 3624
#include <iostream>
#include <math.h>
#include <algorithm>
#include <set>
#include <map>
#include <string>
using namespace std;
typedef long long ll;
#define rep(i,s,n)for(ll i=s;i<n;i++)
#define repe(i,s,n)for(ll i=s;i<=n;i++)
#define rep_r(i,s,n)for(ll i=n-1;i>=s;i--)
#define repe_r(i,s,n)for(ll i=s;i<=n;i++)
static const ll MOD = 1e9 + 7;
static const ll MAX_L = (ll)1 << 62;

ll a[100001] = {};
ll b[100001] = {};
ll c[100001] = {};
int main() {
	ll n; cin >> n;

	rep(i, 0, n)cin >> a[i];
	sort(a, a + n);
	rep(i, 0, n)cin >> b[i];
	sort(b, b + n);
	rep(i, 0, n)cin >> c[i];
	sort(c, c + n);

	ll ans = 0;
	rep(i, 0, n) {
		ll B = b[i];
		ll* A = lower_bound(a, a + n, B);
		ll* C = upper_bound(c, c + n, B);
		ans += (A - a)*(c + n - C);
	}

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

Measured memory_bytes: 2560
#include <iostream>
#include <algorithm>
#include <vector>
#define rep(i, n) for(int i =0; i < n ;i++)
using namespace std;

int main(){
    int N, a[102], ans=0;
    cin >>N;
    
    rep(i, N) cin >> a[i];

    for(int i=0; i <  N-1; i++){
        if(a[i] == a[i+1]){
            ans++;
            i++;
        }
        
    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
import math

def read_input():
    a, b, c, d, e, f = map(int, input().split())
    return a, b, c, d, e, f


# 100aと100bの線形結合でf以下でとりうる値を見つける
def search_water_valiation(a, b, f):
    result = []
    for i in range(30):
        for j in range(30):
            water = 100*a*i + 100*b*j
            if water <= f:
                result.append(water)

    result = list(set(result))
    result.sort()

    return result


# c, dの線形結合でmax_sugar以下の最大値を探す
# cx + dy <= max_sugarより
# y <= - c/d x + max_sugar/d
# xの範囲は(0, max_sugar/c)
def search_most_sweet(c, d, max_sugar):
    sugars = []
    for x in range(math.floor(max_sugar/c) + 1):
        y = math.floor((-c * x + max_sugar)/d)
        sugars.append(c*x + d*y)

    sugars = list(set(sugars))
    return max(sugars)

def submit():
    a, b, c, d, e, f = read_input()

    waters = search_water_valiation(a, b, f)
    max_sugars = [min(w * e // 100, f - w) for w in waters]

    result = []
    for water, max_sugar in zip(waters, max_sugars):
        sugar = search_most_sweet(c, d, max_sugar)
        result.append((water, sugar))

    result = [r for r in result if r[0] + r[1] <= f]
    result = [(w+s, s, 100 * s / (w + s)) for (w, s) in result if (w, s) != (0, 0)]

    r = max(result, key=lambda x:x[2])
    print('{} {}'.format(r[0], r[1]))

if __name__ == '__main__':
    submit()

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

#define fi first
#define se second
#define pb push_back
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()

using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
const int maxn = 1e5+15;
ll a[maxn];
int n;
int main(){
    cin >> n;
    for(int i = 1;i <= n; ++i) cin >> a[i];
    ll now = a[n];
    for(int i = n-1; i ; --i) now = a[i]-now;
    cout << now << " "; 
    for(int i = 2;i <= n; ++i){
        now = (a[i-1]-now/2)*2;
        cout << now << " ";
    } 
    return 0;
}

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

#define ll long long
#define fornum(A,B,C) for(A=B;A<C;++A)
#define pii pair<int,int>
#define pll pair<ll,ll>

using namespace std;

/////////////////////////////////////////////////////
char S[101010];
vector<char> ps[10];
deque<char> cq;
ll Q,Sn;
ll i, j, k;
int main(){
    scanf("%s", S);
    Sn = strlen(S);
    fornum(i,0,Sn){
        cq.push_back(S[i]);
    }
    j = 0;
    scanf("%lld", &Q);
    while(Q--){
        ll T;
        scanf("%lld", &T);
        if(T==1){
            j = !j;
        }else{
            ll F;
            char C[3];
            scanf("%lld%s", &F, C);
            F = (F - 1) ^ j;
            if(F==0){
                cq.push_front(C[0]);
            }else{
                cq.push_back(C[0]);
            }
        }
    }
    
    while(cq.size()){
        if(j==0){
            printf("%c", cq.front());
            cq.pop_front();
        }else{
            printf("%c", cq.back());
            cq.pop_back();
        }
    }
    return 0;
}

Measured memory_bytes: 1024
/*
  AtCoder Beginner Contest 090
  B - Palindromic NUmbers
*/

#include<iostream>
using namespace std;

int A, B;

bool check(int x) {
  return ((x / 10000) == (x % 10) && ((x / 1000) % 10) == ((x / 10) % 10));
}

int main() {
  int cnt = 0;
  scanf("%d%d", &A, &B);

  for (int x = A; x <= B; ++x) {
    if (check(x)) cnt += 1;
  }

  printf("%d\n", cnt);
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <stack>
#include <queue>
#include <map>
#include <algorithm>
#include <iomanip>
#include <math.h>
#include <string.h>
#include <cstdio>
#include <tuple>
#include <numeric>
using namespace std; using ll = long long; using ld = long double;  using pll = pair<ll, ll>;
using vl = vector<ll>; using vll = vector<vl>; using vpll = vector<pll>;
using vs = vector<string>; using tll = tuple<ll, ll, ll>; using vtll = vector<tll>;
const ld PI = 3.1415926535897932;
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#define mp make_pair
#define mt make_tuple
void in() {}
void debug_out() { cerr << endl; }
template<typename Head, typename... Tail>
void debug_out(Head h, Tail... t) {
	cerr << " " << h;
	if (sizeof...(t) > 0) cerr << " :";
	debug_out(t...);
}
template <typename T>
ostream& operator<<(ostream& os, vector<T> vec) {
	for (size_t i = 0; i < vec.size(); i++)os << vec[i] << (i + 1 == vec.size() ? "" : " ");
	return os;
}
ll ctoi(char c) {
	switch (c) {
	case '0': return 0; case '1': return 1; case '2': return 2;
	case '3': return 3; case '4': return 4; case '5': return 5;
	case '6': return 6; case '7': return 7; case '8': return 8;
	case '9': return 9;  default: return 0;
	}
}
bool pairCompare(const pll firstElof, pll secondElof)
{
	return firstElof.first > secondElof.first;
}
//**Snippetリスト**//
//rep, vin, all, iteLoop, bitSearch, bitList, nod//
//gcdlcm, isPrime, eratos, primeFactorize, Npow, combination, divisor, modinv, doubling, digitDP//
//dfs, bfs, dijkstra, WarshallFloyd, BellmanFord, UnionFind, Kruskal ,RMQ, LCA//
ll i, j, k, l; ll N, M, K, H, W, L, X, Y, Z, R, Q;
ll MOD = 1000000007, INF = 1LL << 60, ans = 0, z = 0, o = 1;
vl flag, D; vpll path;
//***********//
vl bitList(vl& bitList,ll n, ll k, ll f) {
	bitList.resize(k);
	for (ll i = 0; i < k; i++) {
		bitList[i] = f % n;
		f /= n;
	}
	return bitList;
}
int main() {
	cin >> N;
	string S;
	cin >> S;
	string P = S.substr(0, N);
	string Q = S.substr(N, N);
	reverse(Q.begin(), Q.end());
	map<pair<string,string>, ll>A;
	map<pair<string,string>, ll>B;
	for (i = 0; i < pow(2,N); i++) {
		vl V;
		bitList(V,2, N, i);
		string pre = "";
		string pre2 = "";
			for (j = 0; j < N; j++) {
				if (V[j]) pre += P[j];
				else pre2 += P[j];
		}
		A[mp(pre,pre2)]++;
	}
	for (i = 0; i < pow(2, N); i++) {
		vl V;
		bitList(V,2, N, i);
		string pre = "";
		string pre2 = "";
		for (j = 0; j < N; j++) {
			if (V[j]) pre += Q[j];
			else pre2 += Q[j];
		}
		B[mp(pre,pre2)]++;
	}
	for (auto x : A) {
		ans += x.second * B[x.first];
	}
	cout << ans;
}

Measured memory_bytes: 108288
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // long long64_t, long long*_t
#include <cstdio> // prlong longf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#include <math.h>
#include <iomanip> //setprecision
#include <limits>
using namespace std;
int main(){
    stack<long long>a;
    string n;
    while(cin >> n){
        if(n=="+"){
            long long x,y;
            x=a.top();
            a.pop();
            y=a.top();
            a.pop();
            a.push(x+y);
        }
        else if(n=="-"){
            long long x,y;
            x=a.top();
            a.pop();
            y=a.top();
            a.pop();
            a.push(y-x);
        }
        else if(n=="*"){
            long long x,y;
            x=a.top();
            a.pop();
            y=a.top();
            a.pop();
            a.push(x*y);
        }
        else{
            a.push(stoi(n));
        }
    }
    cout << a.top() << endl;
}



Measured memory_bytes: 3204
_n = STDIN.gets.to_i
numbers = STDIN.gets.split(' ').map(&:to_i)

# 最大値とペアを組んでべき乗になる値は一意
# A1 <= A2 ... <= An
# x = An
# 2のべき乗になるようなyを選ぶ
# x < x + y <= 2x

map = Hash.new { 0 }

numbers.each do |n|
  map[n] += 1
end

count = 0
map.keys.sort.reverse.each do |number|
  tmp = number
  power = 0
  while tmp > 0
    tmp /= 2
    power += 1
  end

  if map[number] <= 0
    next
  end

  base = 2 ** power - number

  if map[base] <= 0
    next
  end

  # p "number: #{number} base: #{base}"
  # p map[2 ** power - number]

  if base == number
    add = map[number] / 2
    map[number] /= 2
    count += add
    next
  end

  add = if map[base] > map[number]
          map[number]
        else
          map[base]
        end
  map[2 ** power - number] -= add
  map[number] -= add
  count += add
end

puts count


Measured memory_bytes: 33672
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
#pragma GCC optimize("unroll-loops")
//#pragma warning(disable : 4996)

#ifdef _MSC_VER
#include <intrin.h>
#define __builtin_popcount __popcnt
#define __builtin_popcountll __popcnt64
#endif

#include <limits.h>
#include <math.h>
#include <time.h>

#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <complex>
#include <cstdio>
#include <cstring>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>

using namespace std;

#define REP(i, n) for (int i = 0; i < (n); ++i)
#define REPR(i, n) for (int i = n - 1; i >= 0; --i)
#define FOR(i, m, n) for (int i = m; i < n; ++i)
#define FORR(i, m, n) for (int i = m - 1; i >= n; --i)
#define SORT(v, n) sort(v, v + n);
#define VSORT(v) sort(v.begin(), v.end());
#define REVERSE(v, n) reverse(v, v + n);
#define VREVERSE(v) reverse(v.begin(), v.end())
#define ll long long
#define print(x) cout << (x) << '\n'
#define pe(x) cout << (x) << " "
#define DEBUG(x) cout << #x << ": " << x << endl
#define lb(v, n) lower_bound(v.begin(), v.end(), (n))
#define ub(v, n) upper_bound(v.begin(), v.end(), (n))
#define int long long
#define double long double
#define all(x) (x).begin(), (x).end()
#define print_space(v) REP(i, v.size()) cout << v[i] << ((i == v.size() - 1) ? "\n" : " ")
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;
}
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef array<int, 3> arr3;
std::random_device rd;
std::mt19937 mt(rd());
constexpr ll MOD = 998244353;
constexpr int MAX = 500050;
const double pi = acos(-1);
constexpr double EPS = 1e-8;
constexpr ll LINF = 1e18 + 1;
constexpr int INF = 1e9 + 1;



void solve() {
	int X, N;
	cin >> X >> N;
	set<int>st;
	REP(i, N) {
		int x; cin >> x;
		st.insert(x);
	}
	REP(i, 101) {
		int a = X + i;
		int b = X - i;
		if (!st.count(b)) {
			print(b); return;
		}
		if (!st.count(a)) {
			print(a); return;
		}

	}
}



signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	//mt.seed((int)(time(0)));
	//REP(_, 10000)test();
	//int q;
	//cin >> q;
	//while (q--)
	solve();
}



Measured memory_bytes: 3652
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n) ;i++)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
#define sz(x) ((int)(x).size())
using ll=long long;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define MOD  1000000007
const ll INF=1e18;
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; }



int main(int argc, char const *argv[]) {
  int n; cin >> n;
  vector<string> s(n);
  rep(i,n) cin >> s[i];
  set<string> st;
  rep(i,n) st.insert(s[i]);
  cout << st.size() << endl;

  return 0;
}


Measured memory_bytes: 25172
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
# define mod 1000000007
# define INF (1 << 29)
# define MAX_N 1000010
/* ACはうれCすぎてうれD */

int main(void){ 
    int a,b;
    cin >> a >> b;
    if(a%2==0 || b%2==0) cout << "No";
    else cout << "Yes";
    return 0;
}

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

ll gcd(ll a, ll b) { return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b) { return a/gcd(a,b)*b;}

int main(){
  ll n;
  cin >> n;
  ll x = 100000000000000000;
  rep(i,5){
    ll t;
    cin >> t;
    x = min(x,t);
  }

  if(n%x==0){
    cout << n/x+4 << endl;
  }else{
    cout << n/x+5 << endl;
  }

  return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
int main()
{
  int i,a,max;
  char v[10];
  a=0;
  max=0;
  scanf("%s", &v);
 
  for(i=0;i<=10;i++){
  if(v[i]=='A'||v[i]=='C'||v[i]=='G'||v[i]=='T'){
    a+=1;
  }
  else{
    a=0;
  }
  if(max<a)
    max=a;
  }
  printf("%d",max);
  return 0;
}

Measured memory_bytes: 128
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int S = sc.nextInt();
        hourMinuteSecond(S);
        
    }
    public static void hourMinuteSecond(int seconds){
        int minutes = seconds / 60;
        seconds = seconds % 60;
        
        int hours = minutes / 60;
        minutes = minutes % 60;
        
        System.out.println(hours + ":" + minutes + ":" + seconds);
    }
}



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

typedef long long ll;
typedef pair<ll, ll> pll;

#define m0(x) memset(x, 0, sizeof(x))
#define all(x) x.begin(), x.end()
#define rep(i, n) for(int i = 0; i < (n); i++)
#define asort(x) sort(all(x));
#define dsort(x, t) sort(x.begin(), x.end(), greater<t>());
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end());
#define MINS(m, s) m.insert(make_pair(s, 1));
#define MFIN(m, s) m.find(s) != m.end()
const int mod = 1000000007;

int factorialMethod(int k) {
    int sum = 1;
    for(int i = 1; i <= k; ++i) {
        sum *= i;
    }
    return sum;
}

int main() {
    int n;
    int x[10], y[10];
    cin >> n;
    for(int i = 0; i < n; i++) {
        cin >> x[i] >> y[i];
    }

    vector<int> v;
    for(int i = 0; i < n; i++) {
        v.push_back(i);
    }

    int factor = factorialMethod(n);
    double ave = 0.0;
    for(int i = 0; i < factor; i++) {
        for(int j = 0; j < n - 1; j++) {
            ave += sqrt(pow(x[v[j]] - x[v[j + 1]], 2) +
                        pow(y[v[j]] - y[v[j + 1]], 2));
        }
        next_permutation(v.begin(), v.end());
    }
    printf("%.10f\n", (double)ave / factor);
    return 0;
}

Measured memory_bytes: 3780
/*
练习题：Marked Ancestor_AOJ 2170
*/ 

#include <bits/stdc++.h>
using namespace std;

const int MAX_N=100007;

//DUS start line

int par[MAX_N];//父亲 
int ran[MAX_N];//树的高度

//初始化n个元素
void init(int n)
{
	for(int i=0; i<n; i++)
	{
		par[i]=i;
		ran[i]=0;
	}
}

//查询树的根
int find(int x)
{
	if(par[x]==x)
		return x;
	else
		return find(par[x]);//此题这里不要给par[x]赋值，即不要做路径优化 
}

//合并x和y所属的集合
void unite(int x, int y)
{
	x=find(x);
	y=find(y);
	if(x==y)
		return ;
	if(ran[x]<ran[y])
		par[x]=y;
	else
	{
		par[y]=x;
		if(ran[x]==ran[y])
			ran[x]++;
	}
}

//判断x和y是否属于同一个集合
bool same(int x, int y)
{
	return find(x)==find(y);
}

//DUS end line 

int N, Q;

int main()
{
	while(scanf("%d%d", &N, &Q)!=EOF)
	{
		if(N==0&&Q==0)
			break;
			
		memset(par, 0, sizeof(par));
		memset(ran, 0, sizeof(ran));
		par[1]=1;
		
		for(int i=2; i<=N; i++)
		{
			scanf("%d", &par[i]);
		}
		
		long long ans=0;
		for(int i=0; i<Q; i++)
		{
			char t;
			getchar();
			t=getchar();
			if(t=='Q')
			{
				int q;
				scanf("%d", &q);
				ans+=find(q);
			}
			else if(t=='M')
			{
				int m;
				scanf("%d", &m);
				par[m]=m;
			}
		}
		printf("%lld\n", ans);
		
		
	}
		
	
	return 0;
}




Measured memory_bytes: 3968
#include <bits/stdc++.h>
#define rep(i,n)for(long long i=0;i<(n);i++)
using namespace std;
using P=pair<long long,long long>;
typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
 

const double pi=acos(-1);
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};


int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);  
  
  ll n;
  string s;
  cin >> n >> s;
  vector<int>r(n+1);
  vector<int>g(n+1);
  vector<int>b(n+1);
  r[0]=0;
  g[0]=0;
  b[0]=0;
  rep(i,n){
    r[i+1]=r[i];
    g[i+1]=g[i];
    b[i+1]=b[i];
    if(s[i]=='R')r[i+1]++;
    if(s[i]=='G')g[i+1]++;
    if(s[i]=='B')b[i+1]++;
  }
\
  
  ll ans=0;
  rep(i,n-2){
    for(int k=i+2;k<n;k++){
      if(s[i]=='G' && s[k]=='B') ans+=r[k+1]-r[i];
      if(s[i]=='B' && s[k]=='G') ans+=r[k+1]-r[i];
      if(s[i]=='R' && s[k]=='B') ans+=g[k+1]-g[i];
      if(s[i]=='B' && s[k]=='R') ans+=g[k+1]-g[i];
      if(s[i]=='R' && s[k]=='G') ans+=b[k+1]-b[i];
      if(s[i]=='G' && s[k]=='R') ans+=b[k+1]-b[i];
      if((i+k)%2==0 && s[i]!=s[k] && s[i]!=s[(i+k)/2] && s[k]!=s[(i+k)/2])ans--;
    }
  }
  cout << ans << endl;
  
}





Measured memory_bytes: 3676
/*
ID: usaco.t3
TASK: test
LANG: C++14
*/

#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#define _CRT_SECURE_NO_WARNINGS
/****Author: Barish Namazov****/
#include <bits/stdc++.h>

using namespace std;

/***TEMPLATE***/
#define intt long long

#define pii pair<intt,intt>
#define vi vector<intt>
#define vii vector<pii>

#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()

#define F first
#define S second
#define pb push_back

#define IO ios_base::sync_with_stdio(false);cin.tie();
#define endl '\n'

#define wtfis(x) cerr << "at line " << __LINE__ << ": " << #x << " = " << (x) << endl

const intt max3 = 1003;
const intt max4 = 10004;
const intt maxx = 100005;
const intt max6 = 1000006;
const intt max7 = 10000007;

const intt lg4 = 13;
const intt lg5 = 17;
const intt lg6 = 20;

const intt INF = 2LL * 1000000001;
const intt INFLL = 9LL * 1000000000 * 1000000000;
/***************/

intt powmod (intt a, intt b, intt mod) {
    intt res = 1;
    a %= mod;
    for (; b; b >>= 1) {
        if (b & 1)
            res = (res * a) % mod;
        a = (a * a) % mod;
    }
    return res;
}

intt gcd (intt a, intt b) {
    while (b > 0) {
        intt t = a % b;
        a = b, b = t;
    }
    return a;
}

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

intt is_prime (intt n) {
    if (n <= 1 || n > 3 && (n % 2 == 0 || n % 3 == 0))
        return 0;
    for (intt i = 5, t = 2; i * i <= n; i += t, t = 6 - t)
        if (n % i == 0)
            return 0;
    return 1;
}

/**************************/

const long long MAX = 1000000000000000LL;

struct edge {
  int to;
  int a;
  int b;
  edge() {}
  edge(int to, int a, int b) : to(to), a(a), b(b) {}
};

int n, m, f, s;
long long dis1[maxx], dis2[maxx];
long long res[maxx];
vector <edge> g[maxx];

void bfs1(int node) {
  for (int i = 1; i <= n; i++) {
    dis2[i] = MAX;
  }
  dis2[node] = 0;
  queue <int> Q;
  Q.push(node);
  while (!Q.empty()) {
    int cur = Q.front();
    Q.pop();
    for (edge e : g[cur]) {
      if (dis2[e.to] > dis2[cur] + e.a) {
        dis2[e.to] = dis2[cur] + e.a;
        Q.push(e.to);
      }
    }
  }
}

void bfs2(int node) {
  for (int i = 1; i <= n; i++) {
    dis1[i] = MAX;
  }
  dis1[node] = 0;
  queue<int> Q;
  Q.push(node);
  while (!Q.empty()) {
    int cur = Q.front();
    Q.pop();
    for (edge e : g[cur]) {
      if (dis1[e.to] > dis1[cur] + e.b) {
        dis1[e.to] = dis1[cur] + e.b;
        Q.push(e.to);
      }
    }
  }
}

int main() {
  // freopen("in.txt","r",stdin);
  // freopen("out.txt","w",stdout);
  IO;
  cin >> n >> m >> f >> s;
  int u, v, a, b;
  for (int i = 1; i <= m; i++) {
    cin >> u >> v >> a >> b;
    g[u].pb(edge(v, a, b));
    g[v].pb(edge(u, a, b));
  }
  bfs1(f);
  bfs2(s);
  long long best = MAX;
  for (int i = n; i > 0; i--) {
    best = min(best, dis1[i] + dis2[i]);
    res[i] = best;
  }
  for (int i = 1; i <= n; i++) {
    cout << MAX - res[i] << endl;
  }
  return 0;
}


Measured memory_bytes: 10752
use proconio::{input, fastout, marker::Chars};

#[fastout]
fn main() {
    input! {
        _n: usize,
        mut c: Chars,
    }

    let mut left_idx = 0;
    let mut right_idx = c.len() - 1;

    let mut res = 0;
    loop {
        while c[left_idx] == 'R' && left_idx < right_idx {
            left_idx += 1;
        }
        while c[right_idx] == 'W' && left_idx < right_idx {
            right_idx -= 1;
        }
        if left_idx >= right_idx {
            break;
        } else {
            res += 1;
            left_idx += 1;
            right_idx -= 1;
        }
    }

    println!("{}", res);
}


Measured memory_bytes: 3024
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define MAX 1000040
  
const int  m = 1000033;
//const int  m2= 1000003;
//7069 - 60
char stack[MAX][15];
int h1(long long);
int h2(long long);
int insert(long long,int);
long long sti(char *);
  
int main(){
  int val,i,j,n,dic=0,dicc=MAX,index2=0,vall;
  char op[15],s[15];
  int exist=-1,index=0;
  
  while(scanf("%d",&n) != EOF){
    dic=0,dicc=MAX;
    for(i=0;i<=MAX;i++)strcpy(&stack[i][0],"not");
    for(i=0;i<n;i++){
      exist=-1;
      scanf("%s %s",op,s);
      if(op[0] == 'i'){
    index=0;
    while(1){
      val = insert(sti(&s[0]),index);
      if(strcmp(&stack[val][0],"not") == 0){
        strcpy(&stack[val][0],&s[0]);
        break;
      }
      else index++;
      if(index == MAX)break;
    }
      }
      else if(op[0] =='f'){
    index2=0;
    while(1){
      vall=insert(sti(s),index2);
      if(strcmp(stack[vall],s) == 0){
        exist=1;
        break;
      }
      else if(strcmp(&stack[vall][0],"not") == 0){
        break;
      }
      index2++;
      if(index2 == MAX)break;
    }
    if(exist == 1)printf("yes\n");
    else printf("no\n");
      }
    }
  }
  return 0;
}
  
  
int h1(long long k){
  return k%m;
}
  
int h2(long long k){
  return 1+k%(m-1);
}
  
int insert(long long k,int i){
  return (h1(k) + i*h2(k))%m;
}
  
long long sti(char *s){
  long long i=0,sum=0;
  while(s[i] != '\0'){
    sum*=10;
    sum+=s[i]-'A'+1;
    i++;
  }
  return sum;
}


Measured memory_bytes: 16440
using System;

namespace ITP1_7_A
{
    class Program
    {
        static void Main(string[] args)
        {
            while(true)
            {
                var input = Console.ReadLine().Split(' ');
                int m = Int32.Parse(input[0]);
                int f = Int32.Parse(input[1]);
                int r = Int32.Parse(input[2]);
                if (m == -1 && f == -1 && r == -1) { return; }
                Console.WriteLine("{0}", howGrade(m, f, r));
            }
        }

        static string howGrade(int m, int f, int r)
        {
            if (m == -1 || f == -1) { return "F"; }
            if (m + f >= 80)
            {
                return "A";
            }
            else if (m + f >= 65)
            {
                return "B";
            }
            else if (m + f >= 50)
            {
                return "C";
            }
            else if (m + f >= 30)
            {
                if (r >= 50) { return "C"; }
                return "D";
            }
            else
            {
                return "F";
            }
        }
    }
}

Measured memory_bytes: 9108
#include <stdio.h>

int selection_sort(int A[], int N) {
    int key, mini, swap = 0;
    for (int i = 0; i < N; ++i) {
        mini = i;
        for (int j = i; j < N; ++j) {
            if (A[j] < A[mini]) {
                mini = j;
            }
        }
        if (i != mini) {
            swap++;
            key = A[i];
            A[i] = A[mini];
            A[mini] = key;
        }
    }
    return swap;
}

int main() {
    int N, swap = 0;
    scanf("%d", &N);
    int A[N];
    for (int i = 0; i < N; ++i) {
        scanf("%d", &A[i]);
    }

    swap = selection_sort(A, N);
    for (int j = 0; j < N; ++j) {
        if (j > 0) printf(" ");
        printf("%d", A[j]);
    }
    printf("\n%d\n", swap);

    return 0;
}


Measured memory_bytes: 2104
ABN = input().split()
A = int(ABN[0])
B = int(ABN[1])
N = int(ABN[2])

answer = 0
temp = 0

if N >= B:
    answer = A*(B-1) // B - A * ((B-1)//B)

else:
    answer = A*N //B - A * (N//B)

print(answer)

Measured memory_bytes: 9192
#include <algorithm>
#include <cstring>
#include <deque>
#include <functional>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <vector>
using namespace std;
using ll = long long;
const ll INF = 1ll << 62;

int main() {
  int N;
  while (cin >> N) {
    vector<pair<ll, ll>> players(N);
    for (int i = 0; i < N; i++) {
      cin >> players[i].first >> players[i].second;
    }
    sort(players.begin(), players.end(), [&](auto &a, auto &b) {
      return min(a.first, b.first - a.second) >
             min(b.first, a.first - b.second);
    });
    vector<ll> dp(N + 1, INF);
    dp[0] = 0;
    for (int i = 0; i < N; i++) {
      int H = players[i].first, P = players[i].second;
      for (int j = N - 1; j >= 0; j--) {
        if (dp[j] <= H) {
          dp[j + 1] = min(dp[j + 1], dp[j] + P);
        }
      }
    }
    int res = N;
    while (dp[res] >= INF) --res;
    cout << res << endl;
  }
  return 0;
}


Measured memory_bytes: 384
//https://atcoder.jp/contests/abc139/tasks/abc139_a
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define ll long long
int main(){
    string yoho,zissai;
    cin >> yoho >> zissai;
    int ans=0;

    rep(i,3){
        if(yoho.at(i) == zissai.at(i)) ans++;
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using static System.Console;
using static System.Math;
using static AtCoderTemplate.MyLibrary;

namespace AtCoderTemplate
{
    class Program
    {
        static void Main (string[] args)
        {
            int X = int.Parse (Console.ReadLine ());

            if (X >= 30) Console.WriteLine ("Yes");
            else Console.WriteLine ("No");
        }
    }

    class MyLibrary
    {
        public static int GCD (int a, int b)
        {
            if (a % b == 0) return b;
            return GCD (b, a % b);
        }
    }
}

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

typedef long long ll;

ll N, M;
vector<ll> H;
unordered_set<ll> R;

int main() {
  cin >> N >> M;
  H.resize(N);
  for (ll i = 0; i < N; ++i) cin >> H[i];
  for (ll i = 0; i < N; ++i) R.insert(i);
  for (ll i = 0; i < M; ++i) {
    ll a, b;
    cin >> a >> b;
    --a, --b;
    if (H[a] <= H[b]) R.erase(a);
    if (H[b] <= H[a]) R.erase(b);
  }
  cout << R.size() << endl;
  return 0;
}


Measured memory_bytes: 8120
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <map>
#include <bitset>
#include <vector>
#include <string>
#include <set>
#include <assert.h>
#include <algorithm>

using namespace std;
#define ll long long

int parent[100001];
int findparent(int i) {
	if (i == parent[i]) return i;
	else return parent[i] = findparent(parent[i]);
}
void connect(int i, int j) {
	int x1 = findparent(i), x2 = findparent(j);
	parent[x1] = x2;
}
int main()
{	
	int N, M;
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		parent[i] = i;
	}

	for (int i = 0; i < M; i++) {
		int t1, t2, t3;
		cin >> t1 >> t2 >> t3;
		connect(t1 - 1, t2 - 1);
	}

	set<int> wholeparent;
	for (int i = 0; i < N; i++) {
		wholeparent.insert(findparent(i));
	}
	cout << wholeparent.size() << endl;

	return 0;
}

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

int main() {
  int N, tmp;
  map<int, int> A, B;
  cin >> N;
  
  for(int i=1; i<=N; i++) {
    cin >> tmp;
    if(i%2==0) {
      A[tmp]++;
    } else {
      B[tmp]++;
    }
  }
  
  int max_A = 0;
  int secmax_A = 0;
  int argmax_A = 0;
  for(auto itr:A) {
    tmp = itr.second;
    if(tmp > max_A) {
      argmax_A = itr.first;
      secmax_A = max_A;
      max_A = tmp;
    } else if(tmp > secmax_A) {
      secmax_A = tmp;
    }
  }
  
  int max_B = 0;
  int secmax_B = 0;
  int argmax_B = 0;
  for(auto itr:B) {
    tmp = itr.second;
    if(tmp > max_B) {
      argmax_B = itr.first;
      secmax_B = max_B;
      max_B = tmp;
    } else if(tmp > secmax_B) {
      secmax_B = tmp;
    }
  }
  
  int ans;
  if(argmax_A != argmax_B) {
    ans = N - max_A - max_B;
  } else {
    ans = N - max(max_A + secmax_B, secmax_A + max_B);
  }
  
  cout << ans << endl;
  
  return 0;
}

Measured memory_bytes: 4992
#include <iostream>
#include <fstream>
#include <typeinfo>
#include <vector>
#include <stack>
#include <cmath>
#include <set>
#include <map>
#include <string>
#include <algorithm>
#include <cstdio>
#include <queue>
#include <iomanip>
#include <cctype>
#include <random>
#define syosu(x) fixed<<setprecision(x)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef pair<double,double> pdd;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<char> vc;
typedef vector<vc> vvc;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<pll> vpll;
typedef pair<int,P> pip;
typedef vector<pip> vip;
const int inf=1<<30;
const ll INF=1ll<<57;
const double pi=acos(-1);
const double eps=1e-8;
const ll mod=1e9+7;
const int dx[4]={0,1,0,-1},dy[4]={1,0,-1,-0};
const int DX[8]={-1,-1,-1,0,1,1,1,0},DY[8]={1,0,-1,-1,-1,0,1,1};

int n,m;
vi x,y,X,Y;

int main(){
	cin>>n>>m;
	x=y=vi(n);
	X=Y=vi(m);
	for(int i=0;i<n;i++) cin>>x[i]>>y[i];
	for(int i=0;i<m;i++) cin>>X[i]>>Y[i];
	for(int i=0;i<n;i++){
		int M=inf,res;
		for(int j=0;j<m;j++){
			int t=abs(x[i]-X[j])+abs(y[i]-Y[j]);
			if(M>t){
				M=t;
				res=j+1;
			}
		}
		cout<<res<<endl;
	}
}

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

#define int long long int

constexpr int INF = std::numeric_limits<int>::max();

signed main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N, M;
    cin >> N >> M;

    vector<int> X(M);
    for (int &x : X) {
        cin >> x;
    }

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

    vector<int> diff;
    for (int i = 1; i < X.size(); i++) {
        diff.push_back(X[i]- X[i-1]);
    }

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

    int ans = 0;
    for (int i = 0; i < M-N; i++) {
        ans += diff[i];
    }

    cout << ans << endl;
}

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

typedef int64_t i64;
typedef uint64_t ui64;

const int inf=1073741823;
const i64 llinf=4611686018427387903LL;

class bitree{
public:
    i64 *node;
    int nd;
    void make(int n){
        nd=n;
        node=new i64[nd]{};
    }
    void update(int k,i64 x){
        if(k>=nd) return;
        node[k]+=x;
        update(k+(~k&-(~k)),x);
    }
    i64 query(int a,int b){
        i64 c1=0,c2=0;
        func(a-1,c1);
        func(b-1,c2);
        return c2-c1;
    }
    void func(int k,i64 &c){
        if(k<0) return;
        c+=node[k];
        func(k-(~k&-(~k)),c);
    }
};

int main(void){
    int n;
    scanf("%i",&n);
    bitree bit;
    bit.make(n);
    int q;
    scanf("%i",&q);
    int c,p,s,t;
    i64 x;
    for(int i=0;i<q;i++){
        scanf("%i",&c);
        if(c==0){
            scanf("%i%lli",&p,&x);
            p--;
            bit.update(p,x);
        }
        if(c==1){
            scanf("%i%i",&s,&t);
            s--;
            t--;
            printf("%lli\n",bit.query(s,t+1));
        }
    }
    return 0;
}



Measured memory_bytes: 3996
#include  <functional>
#include  <algorithm>
#include  <exception>
#include  <stdexcept>
#include  <streambuf>
#include  <iterator>
#include  <string.h>
#include  <stdlib.h>
#include  <typeinfo>
#include  <valarray>
#include  <iostream>
#include  <sstream>
#include  <istream>
#include  <stdio.h>
#include  <climits>
#include  <clocale>
#include  <complex>
#include  <csetjmp>
#include  <csignal>
#include  <cstdarg>
#include  <cstddef>
#include  <ctype.h>
#include  <cassert>
#include  <cstdlib>
#include  <utility>
#include  <cstring>
#include  <numeric>
#include  <ostream>
#include  <cwctype>
#include  <fstream>
#include  <iomanip>
#include  <math.h>
#include  <bitset>
#include  <cctype>
#include  <string>
#include  <vector>
#include  <limits>
#include  <locale>
#include  <memory>
#include  <cerrno>
#include  <time.h>
#include  <iosfwd>
#include  <cfloat>
#include  <cstdio>
#include  <cwchar>
#include  <cmath>
#include  <ctime>
#include  <deque>
#include  <queue>
#include  <stack>
#include  <list>
#include  <ios>
#include  <map>
#include  <set>
#include  <new>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define ll long long
#define pii pair<int,int>
using namespace std;
const int maxn=100005;
int m[maxn];
int n;
int a[maxn];
bool cmp(int c,int d)
{
    return c>d;
}
int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
        m[a[i]]++;
        m[a[i]+1]++;
        m[a[i]-1]++;
    }
    sort(m,m+maxn,cmp);
    cout<<m[0]<<endl;
    return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for (int i = (a); i <= (b); i++)
#define FORD(i,a,b) for (int i = (a); i >= (b); i--)
#define REP(i,a) FOR(i,0,(int)(a)-1)
#define reset(a,b) memset(a,b,sizeof(a))
#define all(x) x.begin(), x.end()
#define uni(x) x.erase(unique(all(x)), x.end());
#define BUG(x) cout << #x << " = " << x << endl
#define BUGP(x) cout << #x << " = " << x._1 << ", " << x._2 << endl
#define PR(x,a,b) {cout << #x << " = "; FOR (_,a,b) cout << x[_] << ' '; cout << endl;}
#define CON(x) {cout << #x << " = "; for(auto i:x) cout << i << ' '; cout << endl;}
#define mod 1000000007
#define pi acos(-1)
#define eps 1e-6
#define pb push_back
#define sqr(x) (x) * (x)
#define _1 first
#define _2 second

int high, low, ori;
string pre, sys, big;

int main() {
	ios::sync_with_stdio(false);
	big = "999999999";
	string notsobig = "999999";
	while (1) {
		high = 10;
		if (pre.size()) low = 0;
		else low = 1;
		ori = low;
		while (low < high) {
			int mid = (low + high) / 2;
			if (pre.size() > 7) cout << "? " << pre << mid << notsobig << endl;
			else cout << "? " << pre << mid << big << endl;
			cout.flush();
			cin >> sys;
			if (sys == "N") low = mid + 1;
			else high = mid;
		}
		int cur = high;
		bool term = false;
		if (cur != ori) {
			cout << "? " << pre << ori << 0 << endl;
			cout.flush();
			cin >> sys;
			if (sys == "N") term = true;
		} else {
			cout << "? " << pre << 9 << endl;
			cout.flush();
			cin >> sys;
			if (sys == "Y") term = true;
		}
		pre += (char)('0' + cur);
		if (term) {
			cout << "! " << pre << endl;
			return 0;
		}
	}
}

Measured memory_bytes: 596
N = int(input())
A = list(map(int, input().split()))
A.sort()

flag = True
if N % 2 == 0:
  for i in range(N):
    if A[i] != 1 + 2*(i//2):
      flag = False
      break
  if flag:
    ans = 2 ** (N//2)
  else:
    ans = 0
else:
  for i in range(N):
    if A[i] != 2*((i+1)//2):
      flag = False
      break
  if flag:
    ans = 2 ** (N//2)
  else:
    ans = 0
ans = ans % (10**9+7)
print(ans)

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

#define rep(i, x, n) for (int i = x; i < n; i++)
typedef long long ll;

const int INF = 1e9 + 7;

using namespace std;

class UnionFind {
public:
	vector<int> tree;
	vector<int> s;

	UnionFind(int n) : tree(n), s(n) {
		rep (i, 0, n) {
			tree[i] = i;
			s[i] = 1;
		}
	}

	int root(int x) {
		if (tree[x] == x) {
			return x;
		} else {
			int r = root(tree[x]);
			tree[x] = r;
			s[x] = s[r];
			return r;
		}
	}

	void unite(int x, int y) {
		int rx = root(x);
		int ry = root(y);

		if (rx == ry) {
			return ;
		} else {
			tree[ry] = rx;
			s[rx] += s[ry];
			s[ry] = s[rx];
		}
	}

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

	int size(int x) {
		return s[root(x)];
	}
};

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

	int n, m;
	cin >> n >> m;

	vector<int> a(m);
	vector<int> b(m);
	rep (i, 0, m)
		cin >> a[i] >> b[i];

	UnionFind un(n);
	vector<ll> res(m);
	res[m - 1] = (ll)n * ((ll)n - 1) / 2LL;

	for (int i = m - 1; i >= 0; i--) {
		a[i]--;
		b[i]--;
		int min_v = min(a[i], b[i]);
		int max_v = max(a[i], b[i]);

		if (!un.same(min_v, max_v)) {
			ll tmp = (ll)un.size(min_v) * (ll)un.size(max_v);

			if (i > 0)
				res[i - 1] = max(res[i] - tmp, 0LL);
		} else {
			if (i > 0)
				res[i - 1] = res[i];
		}

		un.unite(min_v, max_v);
	}


	rep (i, 0, m)
		cout << res[i] << endl;
	return 0;
}


Measured memory_bytes: 3712
# coding: utf-8
X, Y, A, B, C = map(int, input().split())
P = list(map(int, input().split()))
Q = list(map(int, input().split()))
R = list(map(int, input().split()))
P.sort(reverse=True)
Q.sort(reverse=True)
R.sort(reverse=False)
ans = 0
L = P[:X] + Q[:Y] + R
L.sort(reverse=True)
print(sum(L[:X+Y]))

Measured memory_bytes: 23328
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define rep(i,N) for(int i=0;i<(int)N;i++)
#pragma GCC optimize("O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
static inline char GET(void)
{
  static char buf[1<<17],*s1=buf,*s2=buf;
  return s1==s2&&(s2=(s1=buf)+fread(buf,1,1<<17,stdin),s1==s2)?EOF:*s1++;
}
static inline void PUT(char c)
{
  static char buf[1<<15],*ptr=buf;
  if(ptr==buf+strlen(buf)||c==0){fwrite(buf,1,ptr-buf,stdout),ptr=buf;}*ptr++=c;
}
static inline int IN(void)
{
  int x=0,f=0,c=GET();while(c<48||c>57){f^=c==45,c=GET();}
  while(c>47&&c<58){x=x*10+c-48,c=GET();}return f?-x:x;
}
static inline void OUT(int a)
{
  if(a<0)PUT('-'),a=-a;
  int d[40],i=0;do{d[i++]=a%10;}while(a/=10);
  while(i--){PUT(d[i]+48);}PUT('\n');
}
static inline int Max(int x,int y){return x>y?x:y;}
int main(void)
{
  int H=IN(),W=IN(),M=IN(),row[H],col[W],bombY[M],bombX[M],
      idh=0,idw=0,hmax=0,wmax=0,obj=0;
  memset(row,0,sizeof(row));memset(col,0,sizeof(col));
  rep(i,M)
  {
    bombY[i]=IN()-1,bombX[i]=IN()-1;
    row[bombY[i]]++;col[bombX[i]]++;
    hmax=Max(hmax,row[bombY[i]]);wmax=Max(wmax,col[bombX[i]]);
  }
  rep(i,H){if(hmax==row[i]){idh++;}}rep(j,W){if(wmax==col[j]){idw++;}}
  rep(i,M){obj+=(row[bombY[i]]==hmax&&col[bombX[i]]==wmax);}
  return OUT(hmax+wmax-(1l*obj==1l*idh*idw)),0;
}

Measured memory_bytes: 6352
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<map>
#include<functional>
#include<queue>
using namespace std;
int main() {
	int n;
	cin >> n;
	int sum = 0;
	while (n != 1) {
		switch (n % 3)
		{
		case 1:
			n = (n - 1) / 3 + 1;
			break;
		case 2:
			n = (n - 2) / 3 + 1;
			break;
		case 0:
			n = n / 3;
			break;
		}
		sum++;
	}
	cout << sum << endl;
}

Measured memory_bytes: 3096
// Problem : A - Lucky 7
// Contest : AtCoder Beginner Contest 162
// URL : https://atcoder.jp/contests/abc162/tasks/abc162_a
// Memory Limit : 1024 MB
// Time Limit : 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cp-editor)

#include<bits/stdc++.h>
#define int long long
#define mod 1000000007
#define trace(x) cerr<<#x<<": "<<x<<" "<<endl
#define tarce(x) cerr<<#x<<": "<<x<<" "<<endl
#define trace2(x, y) cerr<<#x<<": "<<x<<" | "<<#y<<": "<<y<<endl
#define trace3(x, y, z) cerr<<#x<<":" <<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl
#define trace4(a, b, c, d) cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl
#define sa(a,n) for(int i =0 ; i<n ; i++) cin>>a[i]
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))
#define pb push_back
#define inf 2e18
#define scan() int n; cin>>n ; int a[n]; for(int i = 0 ; i<n ; i++) cin>>a[i]
#define print(a,n) for(int i = 0 ; i < n ; i++) cout<<a[i]<<' '
#define mem(a,v) memset(a,v,sizeof(a))
#define pii pair<int,int>
#define mkp make_pair
using namespace std;
#define N 200005


int32_t main(){
        ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);
        
        string s;
        cin >> s;
        int w=0;
        for(int i=0; i<s.size(); i++){
        	if(s[i]=='7'){
        		w=1;
        		break;
        	}
        }
        if(w)cout << "Yes" << '\n';
        else cout << "No";
        
        
        
        
        
        

}

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

int main () {
  int A, B;
  cin >> A >> B;
  int C = A * B % 2;
  if (C == 1) {
    cout << "Odd" <<endl;
  }
  else {
    cout << "Even" << endl;
  }
  
  
}

Measured memory_bytes: 3544
#include <bits/stdc++.h>
using namespace std;
#define REP(i,N) for(i=0;i<N;i++)
typedef long long ll;
typedef pair<int, int> P;
typedef struct{
  int first;
  int second;
  int third;
}T;

//昇順
bool comp_Se(T& l, T& r){
  return l.second < r.second;
}

int main(void){
  int A,B,C;
  cin >> A >> B >> C;
  cout << A+B+C + 9*max(A,max(B,C)) << endl;
  return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<tuple>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<deque>
#include<cmath>
#include<stack>
#include<string.h>
#include <iomanip>
#define rep(i,n) for(int i = 0;i<n;i++)
#define _GLIBCXX_DEBUG
using ll = long long; 
using namespace std;
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; }


int main() {
    int n,m;
    cin >> n>> m;
    vector<int>broken(n+1);
    rep(i,m) {
        int a;
        cin >> a;
        broken[a] = 1;
    }
    vector<int>dp(n+2);
    const int mod = 1000000007;
    dp[n] = 1;
    for(int i = n-1;i>=0;i--) {
        if(broken[i]) {
            dp[i] = 0;
            continue;
        }
        dp[i] = (dp[i+1]+dp[i+2]) %mod;
    }

    cout << dp[0] << endl;
    return 0;
}

Measured memory_bytes: 1024
n=input()
ps=input()

ps=ps.split()
ps=[int(k) for k in ps]

output=0

for m in range(int(n)-2): 
    if ps[m]<ps[m+1] and ps[m+1]<ps[m+2]:
        output=output+1
    elif ps[m]>ps[m+1] and ps[m+1]>ps[m+2]:
        output=output+1
    else:
        output=output+0

print(output)

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

int main(){
    int x;
    cin >> x;
    for(int64_t a=-200;a<=200;++a){
        for(int64_t b=-200;b<=200;++b){
            if(a*a*a*a*a-b*b*b*b*b == x){
                cout << a << " " << b << endl;
                return 0;
            }
        }
    }

    return 0;
}

Measured memory_bytes: 3636
#include<stdio.h>

int main(void) {
	int N, A[100], i, j, minj, s, sw;
        sw = 0;

	scanf("%d", &N);

	for (i = 0;i < N;i++) scanf("%d", &A[i]);

	for (i = 0;i < N - 1;i++) {
		minj = i;
                for(j = i;j < N;j++){
                  if(A[j] < A[minj]) minj = j;
                }
        s = A[i];
        A[i] = A[minj];
        A[minj] = s;
        if(i != minj) sw++;
        }

	for (i = 0;i < N;i++) {
	  if (i != 0) printf(" ");
	  printf("%d", A[i]);
	}

	printf("\n");

	printf("%d\n", sw);

	return 0;
}

Measured memory_bytes: 1852