akhauriyash/Code-Regression huggingface dataset:
using System;
using System.Linq;
using System.Collections;
using System.Collections.Generic;
using System.Text;

class Program
{
    static void Main(string[] args)
    {
        // 入力
        int[][] jag = new int[3][];
        for (int i = 0; i < 3; i++)
        {
            jag[i] = Console.ReadLine().Split().Select(int.Parse).ToArray();
        }

        string ans = "Yes";
        //a1+a2
        if (jag[0][0] - jag[1][0] != jag[0][1] - jag[1][1] || jag[0][0] - jag[1][0] != jag[0][2] - jag[1][2])
        {
            ans = "No";
        }
        //a2+a3
        if (jag[1][0] - jag[2][0] != jag[1][1] - jag[2][1] || jag[1][0] - jag[2][0] != jag[1][2] - jag[2][2])
        {
            ans = "No";
        }
        //a3+a1
        if (jag[0][0] - jag[2][0] != jag[0][1] - jag[2][1] || jag[0][0] - jag[2][0] != jag[0][2] - jag[2][2])
        {
            ans = "No";
        }

        //b1+b2
        if (jag[0][0] - jag[0][1] != jag[1][0] - jag[1][1] || jag[0][0] - jag[0][1] != jag[2][0] - jag[2][1])
        {
            ans = "No";
        }
        //b2+b3
        if (jag[0][1] - jag[0][2] != jag[1][1] - jag[1][2] || jag[0][1] - jag[0][2] != jag[2][1] - jag[2][2])
        {
            ans = "No";
        }
        //b3+b1
        if (jag[0][0] - jag[0][2] != jag[1][0] - jag[1][2] || jag[0][0] - jag[0][2] != jag[2][0] - jag[2][2])
        {
            ans = "No";
        }
        Console.WriteLine(ans);


    }
}


Measured memory_bytes: 13396
S = list(map(int,list(input())))
N = len(S)

sirokuro =[i%2 for i in range(0,N,1)]
kurosiro =[(i+1)%2 for i in range(0,N,1)]

loss1 = 0
for i in range(0,N,1):
    if S[i]!=sirokuro[i]:
        loss1 +=1

loss2 = 0
for i in range(0,N,1):
    if S[i]!=kurosiro[i]:
        loss2+=1

print(min(loss1,loss2))

Measured memory_bytes: 11368
#include <iostream>
#include <algorithm>

using namespace std;

int main(void)
{
    int N, d[101], i, count=0;

    cin >> N;

    for(i=1; i<=N; i++){
        cin >> d[i];
    }

    sort(d+1, d+N+1);

    if(N==1){
        cout << 1 << endl;
    }

    else{
        for(i=1; i<N; i++){
            if(d[i] == d[i+1]){
                count++;
            }
        }

        cout << N-count << endl;
    }

    return 0;
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text.RegularExpressions;
using Library;
using static Library.Input;

namespace AtCoderTemplate
{
    class ProgramD
    {
        static void Main()
        {
            int n = NextInt;
            long k = NextLong;
            var a = IntList;
            var distance = Enumerable.Repeat(long.MaxValue, n + 1).ToArray();
            distance[1] = 0;
            int next = a[0], now = 1;

            while (true)
            {
                if (distance[next] == long.MaxValue)
                {
                    distance[next] = distance[now] + 1;
                    now = next;
                    next = a[next - 1];

                    if (k == distance[now])
                    {
                        System.Console.WriteLine(now);
                        return;
                    }
                }
                else
                {
                    long move = (k - distance[next]) % (distance[now] + 1 - distance[next]) + distance[next];
                    System.Console.WriteLine(
                        Enumerable.Range(1, n).First(i => move == distance[i])
                    );
                    return;
                }
            }

        }
    }
}

namespace Library
{
    class Input
    {
        static IEnumerator<string> enumerator = new string[] { }.AsEnumerable().GetEnumerator();

        public static string Line => Console.ReadLine();

        public static string[] StrArr => Line.Split(' ');

        public static int NextInt => int.Parse(NextWord());

        public static long NextLong => long.Parse(NextWord());

        public static List<int> IntList => StrArr.Select(int.Parse).ToList();

        public static List<long> LongList => StrArr.Select(long.Parse).ToList();

        public static IEnumerable<long[]> TakeLine(int N)
        {
            return Enumerable.Repeat(0, N).Select(_ => Console.ReadLine().Split(' ').Select(long.Parse).ToArray());
        }

        public static string NextWord()
        {
            while (!enumerator.MoveNext())
            {
                enumerator = StrArr.AsEnumerable().GetEnumerator();
            }
            return enumerator.Current;
        }
    }
}


Measured memory_bytes: 44720
import java.util.Scanner;
public class Main{
  public static void main(String[] args){
    Scanner s = new Scanner(System.in);
    int k = s.nextInt();
    int a = s.nextInt();
    int b = s.nextInt();
    boolean ok = false;
    if(a % k == 0){
      ok = true;
    }
    for(int i = a; i <= b; i++){
      if(i % k == 0){
        ok = true;
        break;
      }
    }
    if(ok){
      System.out.println("OK");
    } else{
      System.out.println("NG");
    }
  }
    
}

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


int main() {
  string S,T,U;
  cin >> S >> T;
  int A,B;
  cin >> A>> B >> U;
  if(S==U) {
    cout << A-1 <<" " << B <<endl;
  }
  else {
    cout << A << " " << B-1 << endl;
  }
}

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

using namespace std;

int xdp[216000],ydp[216000];
int n, W, H;
int x, y, w;
int main(){
	cin >> n >> W >> H;
	for(int i = 0;i < n;i++){
		cin >> x >> y >> w;
		xdp[max(x-w,0)]++;xdp[x+w]--;
		ydp[max(y-w,0)]++;ydp[y+w]--;
	}
	int ok = 2;
	for(int i = 0;i < W;i++){
		if(i)xdp[i] += xdp[i-1];
		if(xdp[i] == 0){
			ok--;
			break;
		}
	}
	
	for(int i = 0;i < H;i++){
		if(i)ydp[i] += ydp[i-1];
		if(ydp[i] == 0){
			ok--;
			break;
		}
	}
	if(ok)cout << "Yes" << endl;
	else cout << "No" << endl;
	return 0;
}


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

#define INF (100 * 100 * 100 * 100)

int n;
int m[110][110]; //minimum cost multiply matrixes from i to j

void matrixChainOrder(int *p){
  for(int i = 1;i <= n;i++) m[i][i] = 0;
  
  for(int l = 2;l <= n;l++){
    for(int i = 1;i <= n - l + 1;i++){
      int j = i + l - 1;
      m[i][j] = INF;
      //search the minimun cost multiply matrixes from i to j
      for(int k = i;k <= j - 1;k++){
        int q = m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j];
        m[i][j] = min(m[i][j], q);
      }
    }
  }
}

int main(){
  
  int p[110];

  //input
  cin >> n;
  
  for(int i = 0;i < n;i++){
    int r, c;

    //p[0] is the number of first matrix's row
    //p[i] is the number of matrixs' column
    cin >> r >> c;
    if(i) p[i + 1] = c;
    else{
      p[0] = r;
      p[1] = c;
    }
  }
  
  matrixChainOrder(p);

  //output
  cout << m[1][n] << endl;
  
  return 0;
}




Measured memory_bytes: 3136
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define int long long
#define endl '\n'
#define pb push_back
#define fi first
#define se second
#define all(c) (c).begin(),(c).end()
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef vector<int> vi;

template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define TRACE
#ifndef ONLINE_JUDGE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
	cerr << name << " : " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
	const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...)
#endif

const ll inf = 2e18;
const int mod = 1e9 + 7;
const int N = 1e5 + 10;

signed main() {
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	int n, m;
	cin >> n >> m;
	int a[n], sum = 0;
	for(int i = 0; i < n; i++) {
		cin >> a[i];
		sum += a[i];
	}
	int cnt = 0;
	for(int i = 0; i < n; i++) {
		if(a[i] >= ((sum + 4 * m - 1) / (4 * m))) {
			cnt++;
		}
	}
	if(cnt >= m) {
		cout << "Yes";
	}
	else {
		cout << "No";
	}

	return 0;
}

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

using namespace std;

struct edge {long to, cost;};

struct UnionFind
{
	//number of parents(par[i] = i => root)
	vector<int> par;
	//rank of tree
	vector<int> rank;

	UnionFind(int n) : par(n), rank(n, 1)
	{
		//initialize
		for (int i = 0; i < n; i++) par[i] = i;
	}

	//find root (keiroasshuku at the same time)
	int root(int x)
	{
		if (par[x] == x)
			return x;
		else
			return par[x] = root(par[x]);
	}

	//unite
	void unite(int x, int y)
	{
		x = root(x);
		y = root(y);
		if (x == y)
			return;
		if (rank[x] > rank[y])
			swap(x, y);
		par[x] = y;
		rank[y] += rank[x];
	}

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

struct Edge
{
	long from, to, cost;

	// コストの大小で順序定義
	bool operator<(const Edge &o) const
	{
		return cost < o.cost;
	}
};

struct Kruskal
{
	int V; // number of nodes
	vector<Edge> edges;

	Kruskal(int v)
	{
		V = v;
	}

	// グラフが非連結のときは最小全域森のコストの和となる
	long calc()
	{
		//init
		UnionFind uf(V);
		sort(edges.begin(), edges.end());
		long min_cost = 0L;

		for (Edge e : edges)
		{
			if (!uf.same(e.from, e.to))
			{
				min_cost += e.cost;
				uf.unite(e.from, e.to);
			}
		}
		return min_cost;
	}
};

void solve()
{
	long N, D;
	cin >> N >> D;
	priority_queue<pair<long, long>, vector<pair<long, long>>, greater<pair<long, long>>> q;
	vector<edge> graph[2*N];
	for (int i = 0; i < N; i++)
	{
		long A; cin >> A;
		if (i != N-1)
		{
			graph[i+N].push_back({i+N+1, D});
			graph[i+N+1].push_back({i+N, D});
		}
		graph[i].push_back({i+N, A});
		graph[i+N].push_back({i, A});
		q.push({0, i});
	}

	Kruskal kruskal(N);

	vector<long> dist(2*N, 1e18), par(2*N, -1);
	for (int i = 0; i < N; i++)
	{
		par[i] = i;
		dist[i] = 0;
	}
	bitset<400040> vst;

	while(!q.empty())
	{
		auto p = q.top(); q.pop();
		long v = p.second, d = p.first;
		vst[v] = 1;
		for (auto e : graph[v])
		{
			long nv = e.to;
			if (vst[nv])
			{
				kruskal.edges.push_back({par[v], par[nv], dist[v] + dist[nv] + e.cost});
				//cout << par[v] << ' ' << par[nv] << ' ' << dist[v] << ' ' << dist[nv] << ' ' << e.cost << endl;
			}
			else
			{
				if (dist[nv] > d + e.cost)
				{
					par[nv] = par[v];
					dist[nv] = d + e.cost;
					q.push({d + e.cost, nv});
				}
			}
		}
	}

	cout << kruskal.calc() << endl;
}

int main(void)
{
	solve();
	//cout << "yui(*-v・)yui" << endl;
	return 0;
}


Measured memory_bytes: 70500
import java.util.Scanner;

public class Main {

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] heights = new int[N];
        for(int i=0;i<N;i++){
            heights[i] = sc.nextInt();
        }
        System.out.println(frog1(heights));
    }

    static int frog1(int[] heights){

        int[] dp= new int[heights.length];
        dp[0]= 0;
        dp[1]= Math.abs(heights[1]-heights[0]);

        for(int i=2;i<heights.length;i++){
            dp[i] = Math.min(
                    dp[i-1] +Math.abs(heights[i]-heights[i-1]),
                    dp[i-2] +Math.abs(heights[i]-heights[i-2])
            );
        }
        return dp[heights.length-1];
    }
}

Measured memory_bytes: 50268
use std::io::*;

fn main() {
    let mut s: String = String::new();
    std::io::stdin().read_to_string(&mut s).ok();
    let mut itr = s.trim().split_whitespace();
    let n: usize = itr.next().unwrap().parse().unwrap();
    let k: usize = itr.next().unwrap().parse().unwrap();
    let s: usize = itr.next().unwrap().parse().unwrap();

    let mut ans: Vec<usize> = Vec::new();
    let max = 1_000_000_000;
    for _ in 0..k {
        ans.push(s);
    }
    for _ in 0..n - k {
        if s == max {
            ans.push(max - 1);
        } else {
            ans.push(max);
        }
    }
    let mut out = Vec::new();
    for i in 0..n {
        write!(out, "{}", ans[i]).ok();
        if i == n - 1 {
            writeln!(out, "").ok();
        } else {
            writeln!(out, " ").ok();
        }
    }
    stdout().write_all(&out).unwrap();
}


Measured memory_bytes: 9596
#include <bits/stdc++.h>
#define LL long long
#define it map <vector <LL>,vector <O> >::iterator
#define ito i->second
using namespace std;
const LL mo=1000000007;
struct O{LL l,r;};
vector <O> g; vector <LL> f;
map <vector <LL>,vector <O> > M;
int n;
LL K,a[205],b[205],c[205],mi,s,P,X,L,R,ans;
bool cmp(O a,O b){
	return a.l==b.l?a.r<b.r:a.l<b.l;
}
int qiu(LL l,LL r){
	int i,x=0; LL y=0;
	for (i=60;~i;--i)
		if (l>>i!=r>>i) return x+1-(y==l);
		else if (l>>i&1) ++x,y|=1ll<<i;
	return x;
}
int main(){	
	scanf("%d%lld",&n,&K);
	for (int i=1;i<=n;++i) scanf("%lld",&a[i]);
	sort(a+1,a+n+1); c[0]=-1;
	for (int k=0;k<=60;++k){
		s=1ll<<k; mi=(1e18)+5;
		for (int i=1;i<=n;++i){
			b[i]=a[i]/s; mi=min(mi,b[i]);
			c[i]=a[i]-b[i]*s;
		}
		sort(c+1,c+n+1);
		for (int i=1;i<=n;++i)
		if (c[i-1]<c[i]){
			P=qiu(c[i-1]+1,c[i]);
			X=K-k-P; f.clear();
			for (int j=1;j<=n;++j)
			if (c[i]<=a[j]-b[j]*s) X=min(X,b[j]),f.push_back(b[j]);
			else X=min(X,b[j]-1),f.push_back(b[j]-1);
			if (X<0) continue;
			sort(f.begin(),f.end()); R=f[0]; L=f[0]-X;
			for (int i=0;i<f.size();++i) f[i]-=R;
			M[f].push_back((O){L,R});
		}
	}
	for (it i=M.begin();i!=M.end();++i){
		g=i->second;
		sort(g.begin(),g.end(),cmp); L=0; R=-1;
		for (int j=0;j<g.size();++j){
			if (R<g[j].l) ans+=(R-L+1)%mo,L=g[j].l;
			R=max(R,g[j].r);
		}
		ans+=R-L+1;
	}
	printf("%lld\n",ans%mo);
	return 0;
}

Measured memory_bytes: 16512
n, m, l = map(int, input().split())
A = [list(map(int, input().split())) for i in range(n)]
B = [list(map(int, input().split())) for i in range(m)]

for i in range(n):
    for j in range(l):
        c = 0
        print("{}{}".format(' ' if j else '', sum(A[i][k] * B[k][j] for k in range(m))), end='')
    print()



Measured memory_bytes: 6572
{-# LANGUAGE ScopedTypeVariables #-}
{-# LANGUAGE BangPatterns #-}

import Control.Applicative
import Control.Monad
import Control.Arrow
import Data.List
import Data.Maybe
import Data.Char
import qualified Data.ByteString.Char8 as B
import Text.Printf

readInt = ( readLn :: IO Int )
readInts = map ( read :: String -> Int ) . words <$> getLine

getList = map ( fst . fromJust . B.readInt ) . B.words <$> B.getLine

which a b f = if f then a else b
mp [ a, b ] = ( a, b )

main = do
	o <- getLine
	e <- getLine
	putStrLn $ solve o e

solve [] _ = []
solve [c1] [] = c1 : []
solve (c1:s1) (c2:s2) = c1 : c2 : solve s1 s2


Measured memory_bytes: 508
#include<iostream>
using namespace std;
int t[] = {500,100,50,10,5,1};
int main(void){
    while(true){
        int n,count = 0;
        cin >> n;
        if(n == 0)break;
        n = 1000 - n;
        for(int i=0; i<6; i++){
            count+=n/t[i];
            n%=t[i];
        }
        cout<<count<<endl;
    }
}


Measured memory_bytes: 2984
N = int(input())
xyh = [list(map(int, input().split())) for i in range(N)]
ansx = 0
ansy = 0
ansh = 0
for x in range(101):
  for y in range(101):
    hset = set()
    for i in range(N):
      xyhi = xyh[i]
      if xyhi[2] == 0:
        continue
      hset.add(abs(xyhi[0]-x) + abs(xyhi[1]-y) + xyhi[2])

    if len(hset) == 1 and list(hset)[0] != 0:
      flag = True
      for i in range(N):
        xyhi = xyh[i]
        if xyhi[2] != 0:
          continue
        elif xyhi[2] == 0 and max(list(hset)[0] - abs(xyhi[0]-x) - abs(xyhi[1]-y), 0) == 0:
          continue
        flag = False
        break
      if flag:
        ansx = x
        ansy = y
        ansh = list(hset)[0]

print(ansx, ansy, ansh)



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

int main(void)
{
    ll x,k,d;
    cin >> x >> k >> d;
    x = abs(x);
    ll n = min(k,x/d);
    k -= n;
    x -= n*d;
    if(k%2) cout << abs(x-d) << endl;
    else cout << x << endl;
    return 0;
}

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

bool solve(int n,int d){
    vector<vector<int>> c(n);
    
    for(int i=0;i<n;i++){
        int m;
        cin>>m;
        for(int j=0;j<m;j++){
            int buf;
            cin>>buf;
            c[i].push_back(buf);
        }
    }
    if(n==1) return true;

    while(true){
        vector<int> sum(n);
        for(int i=0;i<n;i++) sum[i]=accumulate(c[i].begin(),c[i].end(),0);
        int midx=max_element(sum.begin(),sum.end())-sum.begin();
        int smidx=midx ? 0 : 1;
        for(int i=0;i<n;i++){
            if(i!=midx && sum[smidx]<sum[i]) smidx=i;
        }
        bool isok=false;
        for(int i=0;i<n && !isok;i++){
            if(i==midx) continue;
            if(c[i].size()>0 && sum[midx]-(sum[i]-c[i].back())<=d){
                c[i].pop_back();
                isok=true;
            }
        }
        if(isok) continue;
        if(c[midx].size()==0 || sum[smidx]-(sum[midx]-c[midx].back())>d){
            break;
        }
        c[midx].pop_back();
    }
    return all_of(c.begin(),c.end(),[](const vector<int>& vec){return vec.empty();});
}
int main(){
    int n,d;
    while(cin>>n>>d,n){
        cout<<(solve(n,d) ? "Yes" : "No")<<endl;
    }
    return 0;
}


Measured memory_bytes: 3172
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import array
from bisect import *
from collections import *
import fractions
import heapq
from itertools import *
import math
import random
import re
import string
import sys

A, B, C = map(int, input().split())
s = set([A, B, C])
if len(s) == 2:
    print('Yes')
else:
    print('No')



Measured memory_bytes: 6992
#include <stdio.h>

int main(void)
{
        int W, H, N;
        int x, y, a;
        int area[100][100] = {{ 0 }};
        int i, j, k, count = 0;

        scanf("%d %d %d", &W, &H, &N);
        for (i = 0; i < N; i++) {
                scanf("%d %d %d", &x, &y, &a);
                switch(a) {
                case 1:
                        for (j = 0; j < x; j++) {
                                for (k = 0; k < H; k++) {
                                        area[j][k] = 1;
                                }
                        }
                        break;
                case 2:
                        for (j = x; j < W; j++) {
                                for (k = 0; k < H; k++) {
                                        area[j][k] = 1;
                                }
                        }
                        break;
                case 3:
                        for (j = 0; j < W; j++) {
                                for (k = 0; k < y; k++) {
                                        area[j][k] = 1;
                                }
                        }
                        break;
                case 4:
                        for (j = 0; j < W; j++) {
                                for (k = y; k < H; k++) {
                                        area[j][k] = 1;
                                }
                        }
                        break;
                }
        }

        for (i = 0; i < W; i++) {
                for (j = 0; j < H; j++) {
                        if (area[i][j] == 1) {
                                count++;
                        }
                }
        }

        printf("%d\n", ((W * H) - count));

        return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
using Int = long long;

int main() {

	Int A, B, C, D, E, F;

	std::cin >> A >> B >> C >> D >> E >> F;

	long double ans_density = 0;
	Int ans_sum = 0;
	Int ans_sugar = 0;
	Int number_a = F / 100 / A;
	Int number_b = F / 100 / B;
	Int number_c = F / C;
	Int number_d = F / D;

	for (Int a = 0; a <= number_a; a++) {
		for(Int b=0;b<=number_b;b++){
			if (100 * A * a + 100 * B * b > 0) {
				for (Int c = 0; c <= number_c; c++) {
					for (Int d = 0; d <= number_d; d++) {
						long double sugar = C * c + D * d;
						long double sum = 100 * A * a + 100 * B * b + C * c + D * d;
						long double density = sugar*100 / sum;
						if (density >= ans_density && sum <= F) {
							if (density <= (long double)((long double)(E*100)/(long double)(100+E))) {
								ans_density = density;
								ans_sum = sum;
								ans_sugar = sugar;
							}
						}
					}
				}
			}
		}
	}

	std::cout << ans_sum <<" "<< ans_sugar << std::endl;

}

Measured memory_bytes: 256
import java.io.IOException;
import java.util.Scanner;

class Main {
	static final int INF = 1000000001;

	static int changecount;
   public static void main(String args[]) throws IOException{

      Scanner sc = new Scanner(System.in);
	  // BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	   int n = Integer.parseInt( sc.next()  );
	  // String[] string =  br.readLine().split(" ");
	   int[] A = new int[n];

	   for(int i = 0;i < n; i++){
        // A[i] = Integer.parseInt( string[i] ) ;
		   A[i] = Integer.parseInt(sc.next());
	   }

	    mergeSort(A, 0, n);

	   for(int i = 0;i < n; i++){
		   System.out.print(A[i]);
		   if(i < n-1 ){
			   System.out.print(" ");
		   }
	   }
	   System.out.println();
	   System.out.println(changecount);
	   sc.close();
   }



   public static void merge( int[] A, int left, int mid ,int right){

	   int n1 = mid - left;
	   int n2 = right - mid;
       int[] L = new int[n1+1];
       int[] R = new int[n2+1];

       //System.out.println("  n1="+ n1+" n2="+n2);
	   for(int i = 0; i < n1;i++ ){
		   L[i] = A[left + i];
		   //System.out.println(" n1="+n1+" n2="+n2);
		   //System.out.println("  L[i]="+ L[i]);
	   }

	   for(int i = 0; i < n2;i++ ){
		   R[i] = A[mid + i];
		   //System.out.println("  R[i]="+ R[i]);
	   }

	   L[n1] =  INF;
	   R[n2] =  INF;

	   int i = 0;
	   int j = 0;

	   for(int k = left; k < right; k++ ){

		   if(L[i] <= R[j]){
			   A[k] = L[i];
			      i = i + 1;
			      changecount++;
		   }else{
			   A[k] = R[j];
			      j = j + 1;
			      changecount++;
		   }

	   }
	   //System.out.println(changecount);


   }


   public static void mergeSort(int[] A, int left, int right){
	   //System.out.println(" left="+left+" right="+right);

	   if(left+1 < right){
		    int mid = (left + right)/2;
		    mergeSort(A, left, mid);
		    mergeSort(A, mid, right);
		   merge(A, left, mid, right);
		    //System.out.println(changecount);
	   }



   }
}

Measured memory_bytes: 142660
#include<bits/stdc++.h>
#include<cstdlib>
using namespace std;
int main(){
  int N; cin>>N;
  int K=N%10;
  if(K==3)
    cout<<"bon"<<endl;
  else if(K==2||K==4||K==5||K==7||K==9)
    cout<<"hon"<<endl;
  else cout<<"pon"<<endl;
}


Measured memory_bytes: 3592
def gcd2(a, b):
    if b == 0:
        return a
    
    return gcd2(b, a % b)

def gcd3(a, b, c):
    return gcd2(gcd2(a, b), c)

if __name__ == "__main__":
    k = int(input())
    
    ans = 0

    for a in range(1, k + 1):
        for b in range(1, a + 1):
            for c in range(1, b + 1):
                if a == b and b == c and c == a:
                    ans += gcd3(a, b, c)
                elif a == b or b == c or c == a:
                    ans += gcd3(a, b, c) * 3
                else:
                    ans += gcd3(a, b, c) * 6
    
    print(ans)

Measured memory_bytes: 9224
import java.util.*;
public class Main {
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);

    String x = sc.next();
    String y = sc.next();
    int num_x = 0;
    int num_y = 0;
   
    if(x.equals("A")) num_x=10;
    else if(x.equals("B")) num_x=11;
    else if(x.equals("C")) num_x=12;
    else if(x.equals("D")) num_x=13;
    else if(x.equals("E")) num_x=14;
    else if(x.equals("F")) num_x=15;

    if(y.equals("A")) num_y=10;
    else if(y.equals("B")) num_y=11;
    else if(y.equals("C")) num_y=12;
    else if(y.equals("D")) num_y=13;
    else if(y.equals("E")) num_y=14;
    else if(y.equals("F")) num_y=15;

    if(num_x == num_y) System.out.println("=");
    else if(num_x > num_y) System.out.println(">");
    else System.out.println("<");
    
  }
}

Measured memory_bytes: 35620
#define _USE_MATH_DEFINES
#include <cstdio>
#include <iostream>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <complex>
#include <string>
#include <vector>
#include <array>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <limits>
#include <climits>
#include <cfloat>
#include <functional>
#include <iterator>
using namespace std;

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

    if(a * b % 2 == 0)
        cout << "Even" << endl;
    else
        cout << "Odd" << endl;

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
const int INF = 1e9;
const int MOD = 1e9+7;
const long long LINF = 1e18;
#define dump(x)  cout << 'x' << ' = ' << (x) << ` `;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) for(int i=0;i<(n);++i)
#define REPR(i,n) for(int i=n;i>=0;i--)
#define FOREACH(x,a) for(auto& (x) : (a) )
typedef long long ll;
using namespace std;
typedef pair<ll, ll> P;
template<typename T> 
void print(vector<T> &x) {
    int n = x.size();
    REP(i,n) {
        if (i != n-1) cout << x[i] << " ";
        else cout << x[i] << endl;
    }
}
int main(int argc, char const *argv[]) {
    int n, m;
    cin >> n >> m;
    vector<int> gate(n+10);
    REP(i,m) {
        ll l,r;
        cin >> l >> r;
        --l;
        gate[l]++; gate[r]--;
    }
    REP(i,n+10) gate[i+1] += gate[i];
    int ans = 0;
    REP(i,n) {
        if (gate[i] == m) ans++;
    }
    // print(gate);
    cout << ans << endl;
    return 0;
}

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

int main(){
    int H, W, K;
    cin >> H >> W >> K;
    char c[H][W];

    for(int i = 0; i < H; i++){
        for(int j = 0; j < W; j++){
            cin >> c[i][j];
        }
    }

    // char temp[H][W];

    int column[W];
    int row[H];
    int num = 0;
    int cnt = 0;
    int tem = num;
    int ans = 0;

    
    for(num = 0; num < (1<<(H+W)); num++){
        cnt = 0;
        tem = num;
        for(int i = 0; i < H; i++){
            row[i] = tem % 2;
            tem /= 2;
        }
        for(int j = 0; j < W; j++){
            column[j] = tem % 2;
            tem /= 2;
        }

        for(int i = 0; i < H; i++){
            for(int j = 0; j < W; j++){
                if( (row[i] == 0) && (column[j] == 0) && (c[i][j] == '#') ){
                    cnt++;
                }
            }
        }

        if (cnt == K){
            ans++;
        }
    }

    cout << ans << endl;
    

    return 0;
}

Measured memory_bytes: 3628
import java.util.Scanner;


public class Main
{
	public static void main(String[] args)
	{
		Scanner scanner = new Scanner(System.in);
		
		for(; scanner.hasNext();)
		{
			float w = scanner.nextFloat();
			String rank;
			
			if(w <= 48)
				rank = "light fly";
			else if(48<w && w<=51)
				rank = "fly";
			else if(51<w && w<=54)
				rank = "bantam";
			else if(54<w && w<=57)
				rank = "feather";
			else if(57<w && w<=60)
				rank = "light";
			else if(60<w && w<=64)
				rank = "light welter";
			else if(64<w && w<=69)
				rank = "welter";
			else if(69<w && w<=75)
				rank = "light middle";
			else if(75<w && w<=81)
				rank = "middle";
			else if(81<w && w<=91)
				rank = "light heavy";
			else 
				rank = "heavy";
			
			System.out.println(rank);
		}
	}
}

Measured memory_bytes: 27856
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
  long long a,b,c,ans=0;
  cin >> a >> b >> c;
  ans=c+b;
  if(a+b<c){
    ans-=c-a-b-1;
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
import std.stdio;
import std.string;
import std.conv;
import std.typecons;
import std.algorithm;
import std.functional;
import std.bigint;
import std.numeric;
import std.array;
import std.math;
import std.range;
import std.container;

void main() {
    int[] input = readln.split.to!(int[]);
    int N = input[0];
    int R = input[1];
    int L = input[2];
    Node[] nodes = new Node[N];
    foreach(int i; 0..N) {
        nodes[i] = new Node(i);
    }
    Node node = nodes[0];
    int preT = 0;
    foreach(int i; 0..R) {
        input = readln.split.to!(int[]);
        int d = input[0]-1;
        int t = input[1];
        int x = input[2];

        node.time += t-preT;
        nodes[d].score += x;
        if (x > 0) {
            if ((nodes[d].score > node.score) || (nodes[d].score == node.score && nodes[d].id < node.id)) {
                node = nodes[d];
            }
        } else if (d == node.id) {
            foreach(int j; 0..N) {
                if (nodes[j].score > node.score || (nodes[j].score == node.score && nodes[j].id < node.id)) {
                    node = nodes[j];
                }
            }
        }
        preT = t;
    }
    node.time += L-preT;
    multiSort!("a.time>b.time", "a.id<b.id")(nodes);
    writeln(nodes.front.id+1);
}
class Node{
    int id, time, score;
    this(int id) {
        this.id = id;
        time = 0;
        score = 0;
    }
}

Measured memory_bytes: 11416
#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())
using namespace std;
using ll = long long;

int main() {
    int n, m;
    cin >> n >> m;
    vector<pair<ll, int>> v;
    rep(i, n) {
        ll a;
        int b;
        cin >> a >> b;
        v.emplace_back(pair(a, b));
    }
    sort(all(v));
    ll prc = 0, sum = 0;
    rep(i, n) {
        sum += v[i].second;
        if (sum < m) {
            prc += v[i].first * v[i].second;
        } else {
            ll diff = sum - m;
            prc += v[i].first * (v[i].second - diff);
            break;
        }
    }
    cout << prc << "\n";
}

Measured memory_bytes: 5376
#!/usr/bin/env run-cargo-script

use io::*;
use std::*;

fn solve(S: String) {
    let w = S.as_str();
    match w {
        "Sunny" => println!("Cloudy"),
        "Rainy" => println!("Sunny"),
        "Cloudy" => println!("Rainy"),
        _ => unreachable!(),
    }
}

// Generated by 1.1.5 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
fn main() {
    let con = read_string();
    let mut scanner = Scanner::new(&con);
    let mut S: String;
    S = scanner.next();
    // In order to avoid potential stack overflow, spawn a new thread.
    let stack_size = 104_857_600; // 100 MB
    let thd = std::thread::Builder::new().stack_size(stack_size);
    thd.spawn(move || solve(S)).unwrap().join().unwrap();
}

pub mod io {
    use std;
    use std::str::FromStr;

    pub struct Scanner<'a> {
        iter: std::str::SplitWhitespace<'a>,
    }

    impl<'a> Scanner<'a> {
        pub fn new(s: &'a str) -> Scanner<'a> {
            Scanner {
                iter: s.split_whitespace(),
            }
        }

        pub fn next<T: FromStr>(&mut self) -> T {
            let s = self.iter.next().unwrap();
            if let Ok(v) = s.parse::<T>() {
                v
            } else {
                panic!("Parse error")
            }
        }

        pub fn next_vec_len<T: FromStr>(&mut self) -> Vec<T> {
            let n: usize = self.next();
            self.next_vec(n)
        }

        pub fn next_vec<T: FromStr>(&mut self, n: usize) -> Vec<T> {
            (0..n).map(|_| self.next()).collect()
        }
    }

    pub fn read_string() -> String {
        use std::io::Read;

        let mut s = String::new();
        std::io::stdin().read_to_string(&mut s).unwrap();
        s
    }

    pub fn read_line() -> String {
        let mut s = String::new();
        std::io::stdin().read_line(&mut s).unwrap();
        s.trim_right().to_owned()
    }
}


Measured memory_bytes: 8572
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>	
#include<map>
#include<set>
#include<utility>
#include<cmath>
#include<cstring>
#include<queue>
#include<stack>
#include<cstdio>
#include<sstream>
#include<iomanip>
#define loop(i,a,b) for(int i=a;i<b;i++) 
#define rep(i,a) loop(i,0,a)
#define pb push_back
#define mp make_pair
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)
using namespace std;
//kaewasuretyuui
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vp;
typedef vector<vp> vvp;
typedef vector<string> vs;
typedef vector<double> vd;
typedef pair<int,pii> pip;
typedef vector<pip>vip;
const double PI=acos(-1);
const double EPS=1e-8;
const int inf=1e8;
int main(){
	int n,m;
	cin>>n>>m;
	int x,y;
	rep(i,n)rep(j,m){
		string s;
		cin>>s;
		if(s=="snuke"){
			x=i,y=j;
		}
	}
	cout<<(char)(y+'A')<<x+1<<endl;
}








Measured memory_bytes: 256
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<bitset>
#include<map>

#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)

using namespace std;

typedef long long LL;
typedef double db;

int get(){
	char ch;
	while(ch=getchar(),(ch<'0'||ch>'9')&&ch!='-');
	if (ch=='-'){
		int s=0;
		while(ch=getchar(),ch>='0'&&ch<='9')s=s*10+ch-'0';
		return -s;
	}
	int s=ch-'0';
	while(ch=getchar(),ch>='0'&&ch<='9')s=s*10+ch-'0';
	return s;
}

const int N = 2e+5+5;
const int mo = 1e+9+7;

int n;
struct man{
	int x,v;
}a[N];
int sta[N],top;
int lef[N],rig[N];
multiset<int>w[N];
LL f[N],tree[N];

bool cmp(man x,man y){return x.v<y.v;}

LL add(LL x,LL y){return x+y>=mo?x+y-mo:x+y;}

void add(int x,LL v){x++;for(;x<=n+1;x+=x&-x)tree[x]=add(tree[x],v);}

LL getv(int x){x++;LL ans=0;for(;x;x-=x&-x)ans=add(ans,tree[x]);return ans;}

int main(){
	n=get();
	fo(i,1,n){a[i].x=get();a[i].v=get();}
	sort(a+1,a+1+n,cmp);
	fo(i,1,n)lef[i]=rig[i]=i;
	top=0;
	fo(i,1,n){
		if (!top||a[i].x>a[sta[top]].x)sta[++top]=i;
		int l=1,r=top;
		while(l<=r){
			int mid=(l+r)/2;
			if (a[sta[mid]].x<a[i].x)l=mid+1;
			else r=mid-1,lef[i]=sta[mid];
		}
	}
	top=0;
	fd(i,n,1){
		if (!top||a[i].x<a[sta[top]].x)sta[++top]=i;
		int l=1,r=top;
		while(l<=r){
			int mid=(l+r)/2;
			if (a[sta[mid]].x>a[i].x)l=mid+1;
			else r=mid-1,rig[i]=sta[mid];
		}
	}
	f[0]=1;
	add(0,1);
	fo(i,1,n)w[rig[i]].insert(lef[i]);
	fo(i,1,n){
		for(set<int>::iterator h=w[i].begin();h!=w[i].end();h++){
			LL tmp=(getv(i)+mo-getv((*h)-2))%mo;
			f[i]=add(f[i],tmp);
			add(i,tmp);
		}
	}
	printf("%lld\n",f[n]);
	return 0;
}

Measured memory_bytes: 26112
fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>().split_whitespace()
        .map(|e| e.parse().ok().unwrap()).collect()
}
struct SegTree<T, F>
where
    F: Fn(T, T) -> T,
    T: std::clone::Clone + std::marker::Copy,
{
    n: usize,
    dat: Vec<T>,
    init: T,
    functor: F,
}

impl<T, F> SegTree<T, F>
where
    F: Fn(T, T) -> T,
    T: std::clone::Clone + std::marker::Copy,
{
    fn new(n: usize, init: T, f: F) -> SegTree<T, F> {
        let mut m = 1;
        // For simplicity, we use 2 ** n sized SegTree.
        while m < n {
            m *= 2;
        }
        SegTree {
            n: m,
            dat: vec![init; 2 * m - 1],
            init: init,
            functor: f,
        }
    }

    // dat[k] = a;
    fn update(&mut self, k: usize, a: T) {
        let mut k = k;
        k += self.n - 1;
        self.dat[k] = a;
        while k > 0 {
            k = (k - 1) / 2;
            self.dat[k] = (self.functor)(self.dat[k * 2 + 1], self.dat[k * 2 + 2]);
        }
    }

    fn query(&self, a: usize, b: usize) -> T {
        self.query_inner(a, b, 0, 0, self.n)
    }

    fn query_inner(&self, a: usize, b: usize, k: usize, l: usize, r: usize) -> T {
        if r <= a || b <= l {
            return self.init;
        }
        if a <= l && r <= b {
            return self.dat[k];
        }

        let vl = self.query_inner(a, b, k * 2 + 1, l, (l + r) / 2);
        let vr = self.query_inner(a, b, k * 2 + 2, (l + r) / 2, r);
        (self.functor)(vl, vr)
    }
}

fn main() {
    let n: usize = read();
    let h = read_vec::<usize>();
    let a = read_vec::<u64>();
    let mut seg = SegTree::new(n + 1, 0, std::cmp::max);
    let mut dp = vec![0; n + 1];

    for i in 0..n {
        dp[h[i]] = seg.query(0, h[i]) + a[i];
        seg.update(h[i], dp[h[i]]);
    }
    println!("{:?}", dp.iter().max().unwrap());
}


Measured memory_bytes: 15900
import java.io.IOException;
import java.io.InputStream;
import java.util.Arrays;
import java.util.NoSuchElementException;

public class Main {
	public static void main(String[] args) {
		FastScanner sc = new FastScanner();
		int N = sc.nextInt();
		String ans = "No";
		for (int i = 1; i <= 9; i++) {
			if (N % i == 0 && N / i <= 9) {
				ans = "Yes";
				break;
			}
		}
		System.out.println(ans);
	}
	
	public static long gcd(long a, long b) {
		long remainder = a % b;
		if (remainder == 0) {
			return b;
		} else {
			return gcd(b, remainder);
		}
	}
}

class FastScanner {
    private final InputStream in = System.in;
    private final byte[] buffer = new byte[1024];
    private int ptr = 0;
    private int buflen = 0;
    private boolean hasNextByte() {
        if (ptr < buflen) {
            return true;
        } else {
            ptr = 0;
            try {
                buflen = in.read(buffer);
            } catch (IOException e) {
                e.printStackTrace();
            }
            if (buflen <= 0) {
                return false;
            }
        }
        return true;
    }

    private int readByte() {
        if (hasNextByte())
            return buffer[ptr++];
        else
            return -1;
    }

    private static boolean isPrintableChar(int c) {
        return 33 <= c && c <= 126;
    }

    public boolean hasNext() {
        while (hasNextByte() && !isPrintableChar(buffer[ptr]))
            ptr++;
        return hasNextByte();
    }

    public String next() {
        if (!hasNext())
            throw new NoSuchElementException();
        StringBuilder sb = new StringBuilder();
        int b = readByte();
        while (isPrintableChar(b)) {
            sb.appendCodePoint(b);
            b = readByte();
        }
        return sb.toString();
    }

    public long nextLong() {
        if (!hasNext())
            throw new NoSuchElementException();
        long n = 0;
        boolean minus = false;
        int b = readByte();
        if (b == '-') {
            minus = true;
            b = readByte();
        }
        if (b < '0' || '9' < b) {
            throw new NumberFormatException();
        }
        while (true) {
            if ('0' <= b && b <= '9') {
                n *= 10;
                n += b - '0';
            } else if (b == -1 || !isPrintableChar(b)) {
                return minus ? -n : n;
            } else {
                throw new NumberFormatException();
            }
            b = readByte();
        }
    }

    public int nextInt() {
        long nl = nextLong();
        if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE)
            throw new NumberFormatException();
        return (int) nl;
    }

    public double nextDouble() {
        return Double.parseDouble(next());
    }
}


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

 
int main() {
  ll L,R;
  cin >> L >> R;
  vector<ll> data;
  if(R-L>=(ll)2019){
    cout << "0" << endl;
  }else{
  	for(ll i=L; i<=R; i++){
    	data.push_back(i);
        //cout << data[i-L] << endl;
    }
    int n = data.size();
    int min = 30000;
    for(ll i=0;i<n;i++){
      for(ll j=0; j<n;j++){
        if(i!=j){
          if( (data[i]*data[j])%2019 < min){
            min = (data[i]*data[j])%2019;
          }
        }  
      }
    }
    cout << min << endl;
  }
}

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


int main(){
 int N;
 int value;
 vector<float> values;


 cin >> N;
 for(int i =0; i<N; i++){
    cin >> value;
    values.push_back(value);
 }
    // Sort this vector
    sort(values.begin(), values.end());

    int i = 2;
    float sum ;
    sum = (values[0] + values[1])/2;
    while(i< N ){
        sum = (values[i] + sum)/2;
        i++; 
    }

    cout << sum;


    return 0;




}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i,n,N) for(long long i=(n);i<(int)N;i++)
#define p(s) cout<<(s)<<endl
#define ck(n,a,b) (a)<=(n)&&(n)<(b)
typedef long long ll;
using namespace std;
const int inf=1e9;

int main(){
	ll N, W;
	ll w[101], tv;
	vector<ll> vt[4];
	cin>>N>>W;
	REP(i,0,N){
		cin>>w[i]>>tv;
		vt[w[i]-w[0]].push_back(tv);
	}
	REP(i,0,4)	sort(vt[i].begin(), vt[i].end(), greater<long long>());
	ll ans = 0;
	REP(i,0,vt[0].size()+1){
		REP(j,0,vt[1].size()+1){
			REP(k,0,vt[2].size()+1){
				REP(l,0,vt[3].size()+1){
					ll sum = 0;
					REP(ii,0,i) sum += vt[0][ii];
					REP(ii,0,j) sum += vt[1][ii];
					REP(ii,0,k) sum += vt[2][ii];
					REP(ii,0,l) sum += vt[3][ii];
					if(i*w[0] + j*(w[0]+1) + k*(w[0]+2) + l*(w[0]+3) <= W) ans = max(ans, sum);
				}
			}
		}
	}

	p(ans);

	return 0;
}


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

#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; i >= n; i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define VSORTR(v) sort(v.rbegin(), v.rend());
#define ALL(v) (v).begin(),(v).end()

using namespace std;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
using P = pair<ll, ll>;

const string YES = "Yes";
const string NO = "No";
const ll mod = 1e9+7;


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

    ll n,m; cin >> n >> m;
    ll a = n % m;
    ll b = (-1)*(a-m);
    cout << min(a,b) << endl;
    return 0;
    
}



Measured memory_bytes: 256
import sys
def MI(): return map(int,sys.stdin.readline().rstrip().split())


class UnionFind:
    def __init__(self,n):
        self.par = [i for i in range(n+1)]  # 親のノード番号
        self.rank = [0]*(n+1)
        self.X = [0]+[1]*n  # 各連結成分の大きさ(根の頂点では正確)

    def find(self,x):  # xの根のノード番号
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def same_check(self,x,y):  # x,yが同じグループか否か
        return self.find(x) == self.find(y)
    
    def unite(self,x,y):  # x,yの属するグループの併合
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            x,y = y,x
        if self.rank[x] == self.rank[y]:
            self.rank[x] += 1
        self.par[y] = x
        self.X[x] = self.X[x]+self.X[y]


N,M = MI()
UF = UnionFind(N)
AB = [tuple(MI()) for _ in range(M)]
AB.reverse()

# 逆再生で考える

ans = N*(N-1)//2
ANS = []
for i in range(M):
    ANS.append(ans)
    a,b = AB[i]
    if UF.same_check(a,b):
        continue
    else:
        ans -= UF.X[UF.find(a)]*UF.X[UF.find(b)]
        UF.unite(a,b)

ANS.reverse()
print(*ANS,sep='\n')


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

int main() {
	int N, M;
	cin >> N >> M;
	vector<int> vx(N + 1);
	vector<int> vy(M + 1);
	cin >> vx[0] >> vy[0];

	for (int i = 0; i < N; i++) {
		cin >> vx[i + 1];
	}
	for (int i = 0; i < M; i++) {
		cin >> vy[i + 1];
	}

	sort(vx.begin(), vx.end());
	sort(vy.begin(), vy.end());

	if (vx[N] < vy[0]) {
		cout << "No War" << endl;
	}
	else {
		cout << "War" << endl;
	}

	return 0;
}

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

// GNU C Compiler
//template<class T> inline string toString(T x) { ostringstream sout; sout << x; return sout.str(); }

// type
using ll = int_fast64_t;
using ull = uint_fast64_t;
using LL = long long;
using ULL = unsigned long long;
using PII = pair<int, int>;
//using pair<T1, T2> = p12;

//container
#define PB emplace_back
#define MP make_pair 
#define SZ(a) int((a).size())
#define ALL(v) v.begin(),v.end()

//repetition
#define REP(n) for(int i=0; i<(n); i++)
#define REPj(n) for(int j=0; j<(n); j++)
#define REPinit(i,a,n) for(int i=(a); i<(n); i++)
#define REPinitj(j,a,n) for(int j=(a); j<(n); j++)

//algorithm
//#define SORT(c) sort((c).begin(),(c).end())

//constant

//clear memory
#define CLR(a) memset((a), 0 ,sizeof(a))

//Optimizer
// #pragma GCC optimize("Ofast")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

/* 
	add utility Algorithm
*/



int main(int argc, char const *argv[])
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int A, B;
    cin >> A >> B;
    cout << ((A - 1) * (B - 1)) << endl;
    
    return 0;
}


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

int main(){
    string s;
    cin>>s;
    
    int t=s.size()-1;
    bool judge=true;

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

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

#define REP(i, start, count) for(int i=(start); i<(int)(count); ++i)
#define rep(i, count) REP(i, 0, count)
#define ALLOF(c) (c).begin(), (c).end()

typedef long long ll;
typedef unsigned long long ull;

int main(void) {
    int N;
    vector<string> s;

    cin >> N;
    s.resize(N);
    int aend = 0;
    int bbegin = 0;
    int ab = 0;
    int count = 0;
    rep(i, N) {
        cin >> s[i];
        
        if (s[i][0] == 'B' && s[i].back() == 'A') ab++;
        else if (s[i][0] == 'B') bbegin++;
        else if (s[i].back() == 'A') aend++;
        
        int k = 0;
        while (true) {
            int pos = s[i].find("AB", k);
            if (pos != string::npos) {
                count++;
                k = pos + 2;
                if (k >= s[i].size()) break;
                continue;
            }
            break;
        }
    }

    count += max(ab - 1, 0);
    if (ab > 0 && aend >= 1) {
        count++;
        aend--;
    }
    if (ab > 0 && bbegin >= 1) {
        count++;
        bbegin--;
    }
    int abmin = min(aend, bbegin);
    count += abmin;
    
    cout << count << endl;


    return 0;
}

Measured memory_bytes: 768
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>


int main(void){
    long i,n;
    scanf("%ld",&n);
    long h[n];
    for(i=0;i<n;i++){
        scanf("%ld",&h[i]);
    }
    for(i=0;i<n-1;i++){
        if(i==0) h[i]-=1;
        if(h[i]>h[i+1]){
            printf("No\n");
            return 0;
        }
        if(h[i]<h[i+1]){
            h[i+1]-=1;
        }
    }
    printf("Yes\n");
    return 0;
}


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


int main(){
    int d;
    string s="Christmas";
    cin >> d;
    int x=25-d;
    rep(i,x){
        s+=" Eve";
    }
    cout << s << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define REP(i,n) for(int i=0; i<(n); i++)	//for文
#define REP2(i,x,n) for(int i=x; i<(n); i++)	//for文
int gcd(int a,int b){return b?gcd(b,a%b):a;}    //最大公約数
int lcm(int a, int b) {return a * b / gcd(a, b);}   //最小公倍数

int main()
{
    string str;
    cin>>str;
    int count=0;
    REP(i,str.length()){
        if(str[i]=='1')
            count++;
    }
    cout<<count<<endl;
    return 0;
}

Measured memory_bytes: 256