akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int (i)=(0);(i)<(int)(n);++(i))
using ll = long long;
using P = pair<ll, ll>;
using namespace std;

template<class T> void vin(vector<T>& v, int n) {
    v.resize(n);
    for (int i = 0; i < n; ++i) {
        cin >> v[i];
    }
}

struct SegmentTree {
    int n;
    vector<int> node;
    SegmentTree(vector<int> v) {
        n = 1;
        while (n < v.size()) n *= 2;
        node.resize(2*n-1, INT_MAX);
        for (int i=0; i<v.size(); ++i) node[i+n-1] = v[i];
        for (int i=n-2; i>=0; --i) node[i] = min(node[i * 2 + 1], node[i * 2 + 2]);
    }
    SegmentTree(int N) {
        n = 1;
        while (n < N) n *= 2;
        node.resize(2*n-1, INT_MAX);
    }
    // x?????????????´????val?????´??°
    void update(int x, int val) {
        x += (n - 1);
        node[x] = val;
        while (x > 0) {
            x = (x - 1) / 2;
            node[x] = min(node[2 * x + 1], node[2 * x + 2]);
        }
    }
    // [a, b)?????????????´????????°????????????????
    // k := ?????????????????????????????????????????????
    int query(int a, int b, int k=0, int l=0, int r=-1) {
        if (r < 0) r = n;
        if (r <= a || b <= l) return INT_MAX;
        if (a <= l and r <= b) return node[k];
        int vl = query(a, b, 2*k+1, l, (l+r)/2);
        int vr = query(a, b, 2*k+2, (l+r)/2, r);
        return min(vl, vr);
    }
};

int main() {
    int n, q;
    cin >> n >> q;
    SegmentTree seg(n);
    rep(i, q) {
        int a, b, c;
        cin >> c >> a >> b;
        if (c) cout << seg.query(a, b+1) << endl;
        else seg.update(a, b);
    }
}

Measured memory_bytes: 3800
#include <bits/stdc++.h>
#define mod 1000000007
#define sp ' '
#define intmax 2147483647
#define llmax 9223372036854775807
#define mkp make_pair
#define lP pair<ll, ll>
#define iP pair<int,int>
typedef long long ll;
using namespace std;

struct T {
	int l, r;
	string s;
};

int N, r[3000], b[3000], cr, cb, R;
string S;
vector<T>v;
deque<string>q;

int main() {
	cin >> N >> S;
	for (int i = 0; i < N * 2; ++i) {
		if (S[i] == 'a') {
			r[cr] = i;
			++cr;
		}
		else {
			b[cb] = i;
			++cb;
		}
	}
	v.push_back({ 0,0,"" });
	for (int i = 0; i < N; ++i) {
		if (b[i] < r[i]) {
			if (r[v.back().r] < b[i]) {
				v.push_back({ i,i,"" });
			}
			else {
				v.back().r = i;
			}
		}
	}
	if (r[0] < b[0]) {
		v.erase(v.begin());
	}
	for (int i = 0; i < v.size(); ++i) {
		vector<bool>B(N * 2, false);
		for (int j = v[i].r; j >= v[i].l; --j) {
			B[b[j]] = B[r[j]] = true;
			string s;
			for (int k = b[j]; k <= r[v[i].r]; ++k) {
				if (B[k]) {
					s.push_back(S[k]);
				}
			}
			v[i].s = max(v[i].s, s);
		}
	}
	for (int i = 0; i < v.size(); ++i) {
		while (!q.empty() && q.back() < v[i].s) {
			q.pop_back();
		}
		q.push_back(v[i].s);
		R = r[v[i].r] + 1;
	}
	while (!q.empty()) {
		cout << q.front();
		q.pop_front();
	}
	for (int i = 0; i < N; ++i) {
		if (r[i] < b[i] && r[i] >= R) {
			cout << "ab";
			R = b[i];
		}
	}
	cout << endl;
}

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

int main() {
int H, W;
while(true){
cin >> H >> W;
if(H == 0 && W == 0){
break;
}

for(int i = 0; i < H; i++){
if(i == 0 || i == H-1){
for(int j = 0; j < W; j++){
cout << "#";
}
}
else{
cout << "#";
for(int j = 0; j < W-2; j++){
cout << ".";
}
cout << "#";
}
cout << endl;

}
cout << endl;


}



}



Measured memory_bytes: 3116
#include <stdio.h>

typedef struct{
    int label[6];
}dice;

void roll_south( int* );
void roll_north( int* );
void roll_east( int* );
void roll_west( int* );

int main(){
	char direct[101] = {'\0'};
    int i;
    dice dice1;
    
    for( i = 0; i < 6; i++ ){
        scanf( "%d", &dice1.label[i] );
    }

	scanf( "%s", direct );

	for( i = 0; direct[i] != '\0'; i++ ){
		switch( direct[i] ){
        case '\n':
            break;
        case 'S':
            roll_south( dice1.label );
			break;
        case 'N':
            roll_north( dice1.label );
			break;
        case 'E':
            roll_east( dice1.label );
			break;
        case 'W':
            roll_west( dice1.label );
			break;
		default :
			;
        }
    }
    
    printf( "%d\n", dice1.label[0] );
    
    return 0;
}

void roll_south( int* label )
{
    int work;
    
    work = label[0];
    label[0] = label[4];
    label[4] = label[5];
    label[5] = label[1];
    label[1] = work;
}
void roll_north( int* label )
{
    int work;
    
    work = label[0];
    label[0] = label[1];
    label[1] = label[5];
    label[5] = label[4];
    label[4] = work;
}
void roll_east( int* label )
{
    int work;
    
    work = label[0];
    label[0] = label[3];
    label[3] = label[5];
    label[5] = label[2];
    label[2] = work;
}
void roll_west( int* label )
{
    int work;
    
    work = label[0];
    label[0] = label[2];
    label[2] = label[5];
    label[5] = label[3];
    label[3] = work;
}


Measured memory_bytes: 2088
class InputLine
  def self.to_s
    gets.chomp
  end

  def self.to_i
    InputLine.to_s.to_i
  end
  
  def self.to_f
    InputLine.to_s.to_f
  end

  def self.to_sa
    InputLine.to_s.split(' ')
  end

  def self.to_ia
    InputLine.to_sa.map(&:to_i)
  end
  
  def self.to_fa
    InputLine.to_sa.map(&:to_f)
  end
end

def main(argv)
  (x, y, z) = InputLine.to_ia

  puts [z, x, y].map(&:to_s).join(' ')
end

if self.to_s == 'main' then
  main(ARGV)
end

Measured memory_bytes: 1788
use std::io::stdin;
use std::str::FromStr;
#[allow(dead_code, unused_mut)]
fn read<T: FromStr>() -> T {
    let mut s = String::new();
    stdin().read_line(&mut s).ok();
    s.trim().parse().ok().expect("1")
}
#[allow(dead_code, unused_mut)]
fn read_vec<T: FromStr>() -> Vec<T> {
    read::<String>()
        .split_whitespace()
        .map(|e| e.parse().ok().expect("2"))
        .collect()
}
#[allow(dead_code, unused_mut)]
fn read_two<T: FromStr>() -> (T, T) {
    let mut s = String::new();
    stdin().read_line(&mut s).unwrap();
    let mut x = s.split_whitespace().map(|x| x.parse().ok().unwrap());
    (x.next().unwrap(), x.next().unwrap())
}
#[allow(dead_code, unused_mut)]
fn read_three<T: FromStr>() -> (T, T, T) {
    let mut s = String::new();
    stdin().read_line(&mut s).unwrap();
    let mut x = s.split_whitespace().map(|x| x.parse().ok().unwrap());
    (x.next().unwrap(), x.next().unwrap(), x.next().unwrap())
}
#[allow(dead_code)]
fn remove_whitespace(s: &str) -> String {
    s.chars().filter(|c| !c.is_whitespace()).collect()
}
#[allow(unused_imports)]
use std::io::{stdout, Write};
fn main() {
    let (n, k) = read_two::<i32>();
    let mut ans = k;
    for i in 0..n-1 {
        ans *= k - 1;
    }
    println!("{}", ans);
}


Measured memory_bytes: 4352
#[allow(unused_imports)]
use std::char::*;
#[allow(unused_imports)]
use std::cmp::*;
#[allow(unused_imports)]
use std::collections::*;
use std::io::*;
use std::str::FromStr;

#[allow(unused_macros)]
macro_rules! debug {($($a:expr),*) => {println!(concat!($(stringify!($a), " = {:?}, "),*), $($a),*);}}
#[allow(unused_macros)]
macro_rules! input {(source=$s:expr,$($r:tt)*) => {let mut iter=$s.split_whitespace(); let mut next=||{iter.next().unwrap()}; input_inner! {next,$($r)*}};($($r:tt)*) => {let stdin=std::io::stdin();let mut bytes=std::io::Read::bytes(std::io::BufReader::new(stdin.lock())); let mut next=move||->String{bytes.by_ref().map(|r|r.unwrap() as char).skip_while(|c|c.is_whitespace()).take_while(|c|!c.is_whitespace()).collect()}; input_inner! {next,$($r)*}};}
#[allow(unused_macros)]
macro_rules! input_inner {($next:expr) => {}; ($next:expr,) => {}; ($next:expr,$var:ident:$t:tt$($r:tt)*) => {let $var=read_value!($next,$t); input_inner! {$next$($r)*}};}
#[allow(unused_macros)]
macro_rules! read_value {($next:expr,($($t:tt),*)) => {($(read_value! ($next,$t)),*)}; ($next:expr, [$t:tt; $len:expr]) => {(0..$len).map(|_|read_value! ($next,$t)).collect::<Vec<_>>()}; ($next:expr,chars) => {read_value! ($next,String).chars().collect::<Vec<char>>()}; ($next:expr,usize1) => {read_value! ($next,usize)-1}; ($next:expr,$t:ty) => {$next().parse::<$t>().expect("Parse error")};}

#[derive(PartialEq, PartialOrd)]
pub struct Total<T>(pub T);
impl<T: PartialEq> Eq for Total<T> {}
impl<T: PartialOrd> Ord for Total<T> {
    fn cmp(&self, other: &Total<T>) -> std::cmp::Ordering {
        self.0.partial_cmp(&other.0).unwrap()
    }
}

#[allow(dead_code)]
const MAX: usize = 100006;
#[allow(dead_code)]
const INF_U32: u32 = 1 << 31;
#[allow(dead_code)]
const INF_I32: i32 = 1 << 30;
#[allow(dead_code)]
const INF_U64: u64 = 1 << 63;
#[allow(dead_code)]
const INF_I64: i64 = 1 << 62;
#[allow(dead_code)]
const MOD: i64 = 1e9 as i64 + 7;

#[allow(dead_code)]
fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

#[allow(dead_code)]
fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}

#[allow(unused_imports)]
use std::f64;

fn main() {
    input!{n:usize, s:[(String,i64);n], x:String};
    let mut ans = 0i64;
    let mut flag = false;
    for i in 0..n {
        if flag { ans += s[i].1; }
        if s[i].0 == x {
            flag = true;
        }
    }
    println!("{}", ans);

}


Measured memory_bytes: 4352
Scanf.scanf "%d %d" @@ fun h w ->
  let sh =
    Array.init (h*w) (fun _ -> Scanf.scanf " %c" (fun c ->
      if c = '#' then 1 else 0))
    |> Array.fold_left (+) 0
  in print_endline @@ if h+w-1 = sh then "Possible" else "Impossible"

Measured memory_bytes: 384
##a = int(stdin.readline().rstrip())
##b, c = [int(x) for x in stdin.readline().rstrip().split()]
##s = stdin.readline().rstrip()
##a = list(set(b))  重複を削除
##a = list(map(int,[int(x) for x in stdin.readline().rstrip().split()])) a[0, 1, 2, ...]
##a = [[0] * 2 for _ in range(n)]  a[0,0]
##v = [s[i: i+2] for i in range(0, len(s), 2)]
##  s="12345678" を v=["12","34","56","78"] にするイメージ
##s = "".join(list)リストを文字列に変換[""]は区切り文字
##a.sort(key=itemgetter(1))リストをソートできるよ(from operator import itemgetterが必要)
##sort_p = sorted(p) 昇順ソート

# -*- coding: utf-8 -*-
from sys import stdin
from operator import itemgetter
from collections import deque, Counter
import math
import pprint
from functools import reduce
import numpy as np
import random
import bisect
import copy
# stdin = open("sample.txt")


MOD = int(1e9+7)
INF = float('inf')
alpha = ["a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z"]

def keta(kazu): # 入力されたintを桁ごとに分解，リストで出力
    kazu_str = str(kazu)
    kazu_list = [int(kazu_str[i]) for i in range(0, len(kazu_str))]
    return kazu_list

def gcd(*numbers): # 最小公倍数
    return reduce(math.gcd, numbers)

def combination(m,n): # mCn
    
    if n > m:
        return 'すまん'
    return math.factorial(m) // (math.factorial(m-n) * math.factorial(n))

def pow_k(x,n):  # (x**n)の計算の高速化
    if n == 0:
        return 1
    K = 1
    while n > 1:
        if n % 2 != 0:
            K *= x
        x *= x
        n //= 2
    return K * x

def fact(n): # nの素因数分解の結果を辞書で出力 fuct(24) → {2: 3, 3: 1}
    arr = {}
    temp = n
    for i in range(2,int(n**0.5)+1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr[i] = cnt
    if temp != 1:
        arr[temp] = 1
    if arr == {}:
        arr[n] = 1
    return arr
    
def main():
    N = int(stdin.readline().rstrip())
    A = list(map(int,[int(x) for x in stdin.readline().rstrip().split()]))
    ans = 0
    
    for i in range(1,N):
        if A[i] < A[i-1]:
            ans += abs(A[i-1]-A[i])
            A[i] = A[i-1]
        
    print(ans)
            
main()

Measured memory_bytes: 50736
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <iomanip>
using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<string> VS;
typedef vector< vector<int> > VVI;
typedef vector< vector<ll> > VVL;
typedef pair<int,int> PII;
#define rep(i,n) for(int i=0;i<(n);i++)
#define all(a) (a).begin(),(a).end()
#define pb push_back
#define mp make_pair
#define ub upper_bound
#define lb lower_bound

int main(){
  int H,W;
  cin>>H>>W;
  int N;
  cin>>N;
  VI A(N);
  rep(i,N) cin>>A[i];
  VI P;
  rep(i,N) rep(j,A[i]) P.pb(i+1);
  VVI X(H,VI(W));
  rep(i,H){
    rep(j,W){
      int k=j;
      if(i%2) k=W-1-j;
      X[i][k]=P[i*W+j];
    }
  }
  rep(i,H){
    rep(j,W){
      if(j) cout<<" ";
      cout<<X[i][j];
    }
    cout<<endl;
  }
}

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

int main() {
  int n,a,b,c,d;
  cin >> n;
  a = n/1000;
  b = n/100%10;
  c = n/10%10;
  d = n%10;
  if((a==b&&b==c)||(b==c&&c==d)){
    cout << "Yes" << endl;
  }else{
    cout << "No" << endl;
  }
}

Measured memory_bytes: 3628
#include<bits/stdc++.h>
using namespace std;
int main() {
	int n; cin >> n;
	pair<long long, long long> task[n];
	for (int i = 0; i < n; i++)
	{
		cin >> task[i].second >> task[i].first;
	}
	sort(task, task + n);

	bool res = true;
	long long sum = 0;
	for (int i = 0; i < n; i++)
	{
		sum += task[i].second;
		if(sum > task[i].first) res = false;
	}
	if(res) cout << "Yes" << endl;
	else cout << "No" << endl;
	return 0;
}


Measured memory_bytes: 6744
s = input()

mojiretu = ['dream','dreamer','erase','eraser']

import re
def setudan(s):
  if s[-5:] == 'dream' or s[-5:] == 'erase':
    return s[:-5]
  elif s[-6:] == 'eraser':
    return s[:-6]
  elif s[-7:] == 'dreamer':
    return s[:-7]
  else:
    return 0

while True:
  s = setudan(s)
  if s == 0:
    print('NO')
    break
  if s =='':
    print('YES')
    break

Measured memory_bytes: 3444
#include <iostream>
using ll = long long;
using namespace std;


int main() {
    int n;
    int temp, count = 0;
    cin >> n;
    int L[n];
    for (int i = 0; i < n; ++i) {
        cin >> L[i];
    }
    for (int j = 0; j < n-1; j++) {
        int minj = j;
        for (int k = j; k < n; k++) {
            if (L[k] < L[minj]) minj = k;
        }
        if(j != minj){
            temp = L[j];
            L[j] = L[minj];
            L[minj] = temp;
            count++;
        }
    }
    for (int k = 0; k < n; ++k) {
        if (k) cout << " ";
        cout << L[k];
    }
    cout << "\n";
    cout << count << "\n";
    return 0;
}


Measured memory_bytes: 3092
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<int, int> P;
ll Mod = 1000000007;
int main() {
  ll A,B,C;
  cin >> A >> B >> C;
  ll ans = B + min(A+B+1,C);
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3628
from itertools import combinations_with_replacement

X = list(input())
tmp = X
num = int("".join(tmp))

if num < 100:
    print(0)
    exit()

X.pop()
X.pop()
X = int("".join(X))

food = [100, 101, 102, 103, 104, 105]

for i in combinations_with_replacement(food, X):
    if sum(i) == num:
        print(1)
        exit()

print(0)


Measured memory_bytes: 3060
#include "bits/stdc++.h"
#define lpa(i,a,b) for(int i=a; i<b; ++i)
#define lp(i,n) lpa(i,0,n)
typedef long long ll;
using namespace std;
int main(int argc, char const *argv[])
{
	int n,a;
	cin>>n>>a;
	cout<<n*n-a;
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cstdlib>
#include<queue>
#include<set>
#include<cstdio>

using namespace std;

#define ll long long
#define rep(i, n) for(int i = 0; i < n; i++)
#define P pair<int, int>

typedef vector<int> vec;
typedef vector<vec> mat;

const ll mod = 1000000007;

int main(){
    string s;
    cin >> s;
    string t[] = {"Sunny", "Cloudy", "Rainy", "Sunny"};
    rep(i, 3){
        if(s == t[i]){
            cout << t[i+1] << endl;
            return 0;
        }
    }
}

Measured memory_bytes: 2980
maxnum = 100000

# エラトステネスのふるい
is_prime = [x for x in range(maxnum)]
for prime in is_prime:
    if prime == 0 or prime == 1:
        is_prime[prime] = 0
        continue
    for non_prime in range(prime * 2, maxnum, prime):
        is_prime[non_prime] = 0

is_like = [False] * maxnum
for i in range(maxnum):
    if (is_prime[i] and is_prime[(i + 1) // 2]):
        is_like[i] =  True

like_sum = [0] * maxnum
for i in range(3, maxnum):
    like_sum[i] = like_sum[i - 1]
    if (is_like[i]):
        like_sum[i] += 1

q = int(input())
for i in range(q):
    l, r = map(int, input().split())
    print(like_sum[r] - like_sum[l - 1])


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

#define REP(i, x) REPI(i, 0, x)
#define REPI(i, a, b) for (int i = int(a); i < int(b); ++i)
#define ALL(x) (x).begin(), (x).end()

typedef long long ll;
using namespace std;

ll c2(ll v) {
  if (v == 2ll) {
    return 1ll;
  } else if (v <= 1) {
    return 0ll;
  }
  return v * (v - 1ll) / 2ll;
}

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

  ll N;
  cin >> N;
  unordered_map<ll, ll> count;
  vector<ll> A(N);
  ll a;
  REP(i, N) {
    cin >> a;
    if (count.find(a) == count.end()) {
      count.insert(make_pair(a, 1));
    } else {
      ++count.at(a);
    }
    A.at(i) = a;
  }

  ll total = 0;
  for (auto const it : count) {
    if (it.second >= 2) {
      total += c2(it.second);
    }
  }

  REP(k, N) {
    ll a2 = A.at(k);
    ll ans = total - c2(count.at(a2));
    ans += c2(count.at(a2) - 1);

    cout << ans << endl;
  }

  return 0;
}


Measured memory_bytes: 10952
char*p,*h,s[1025],t[52];
main(i){
	scanf("%*d");
	for(;~scanf("%s",s);){
		memset(t,0,52);
		h=p=t+25;
		*p=*s;
		for(i=1;s[i];i+=3){
			if(s[i+1]=='>')
				++p;
			else
				if(--p<h)
					h=p;
			*p=s[i+2];
		}
		puts(h);
	}
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
 
using namespace std;
typedef long long ll;
typedef vector<int> VI;
ll mm=1000000000;ll MM=mm+7;
#define rep(i, n) for(int i=0;i<n;i++)
#define PI 3.141592653589793
 
   
int main(){
   int n,a,b;
   cin  >> n >> a >> b;
   string s;
   cin >> s;
   int x=0;
   int y=0;
   int m=s.size();
   rep(i,m){
       if(s.at(i)=='a'){
           if(x<(a+b)){
               x++;
               cout << "Yes" << endl;
           }
           else cout << "No" << endl;
       }
       else if(s.at(i)=='b'){
           if(x<(a+b) && y<b){
               x++;
               y++;
               cout << "Yes" << endl;
           }
           else cout <<  "No" << endl;
       }
       else if(s.at(i)=='c')cout << "No" << endl;
   }

} 

Measured memory_bytes: 3744
#include<bits/stdc++.h>
using namespace std;
#define ll  long long
#define endl '\n'
const ll mod = 1000000007;
const double PI = 3.141592653589793238463;
using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
   string s;
   cin>>s;
   int x,y;
   for (int i=0;i<s.length();i++){
    if (s[i]=='A'){
        x=i;
        break;
    }
   }
   for (int i=s.length()-1;i>=0;i--){
    if (s[i]=='Z'){
        y=i;
        break;
    }
   }
   cout<<1+y-x<<endl;
    return 0;
}


Measured memory_bytes: 720
#include <iostream>
#include <cmath>
#include <string>
#include <stack>
#include <algorithm>
#include <vector>
#include <stdio.h>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;

typedef long long llong;

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

	if(c <= b/a) {
		cout << c << endl;
	}else{
		cout << b/a << endl;
	}


	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define deb(x) cout << #x << " = "<< x << "\n";

const int maxn = 200005;
int root[maxn];
void init(int n) {
    for(int i = 1; i <= n; i++)
        root[i] = -1;
}

int find(int n) {
    if(root[n] < 0) return n;
    else return root[n] = find(root[n]);
}

void merge(int a, int b) {
    a = find(a), b = find(b);
    if(a == b) return;
    root[a] += root[b];
	root[b] = a;
}

signed main() {
//	freopen("in.txt", "r",stdin);
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	
	int n; cin >> n;
	int m; cin >> m;
	
	init(n+2);
	
	for(int i = 0, a, b; i < m; i++) {
		cin >> a >> b;
		merge(a, b);
	}
	
	int ans = 0;
	for(int i = 1; i <= n; i++) {
		if(root[i] < 0)
			ans = max(ans, abs(root[i]));
	}
	cout << ans << "\n";
	
}


Measured memory_bytes: 5028
#include <iostream>

int main() {
    int n, x, y;

    std::cin >> n;
    std::cin >> x >> y;

    int z, z_max, z_min, w, w_max, w_min;
    z_max = z_min = x + y;
    w_max = w_min = x - y;

    for (int i = 1; i < n; i++) {
        std::cin >> x >> y;

        z = x + y;
        w = x - y;

        if (z > z_max) {
            z_max = z;
        } else if (z < z_min) {
            z_min = z;
        }
        if (w > w_max) {
            w_max = w;
        } else if (w < w_min) {
            w_min = w;
        }
    }

    z_max -= z_min;
    w_max -= w_min;

    if (z_max > w_max) {
        std::cout << z_max << std::endl;
    } else {
        std::cout << w_max << std::endl;
    }
    
}

Measured memory_bytes: 3608
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace AtCoder
{

    static class Program
    {
        static void Main()
        {
            Console.SetOut(new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false });

            long A;char op;long B;
            Multi(out A, out op, out B);
            var ans = op == '+' ? A + B : A - B;


            Console.WriteLine(ans);


            Console.Out.Flush();
            Console.ReadKey();
        }


        static public string GetStr() { return Console.ReadLine().Trim(); }
        static public char GetChar() { return Console.ReadLine().Trim()[0]; }
        static public int GetInt() { return int.Parse(Console.ReadLine()); }
        static public long GetLong() { return long.Parse(Console.ReadLine()); }
        static public string[] GetStrArray() { return Console.ReadLine().Split(' '); }
        static public int[] GetIntArray() { return Console.ReadLine().Split(' ').Select(int.Parse).ToArray(); }
        static public long[] GetLongArray() { return Console.ReadLine().Split(' ').Select(long.Parse).ToArray(); }
        static public char[] GetCharArray() { return Console.ReadLine().Split(' ').Select(char.Parse).ToArray(); }
        static public Double[] GetDoubleArray() { return Console.ReadLine().Split(' ').Select(double.Parse).ToArray(); }
        static public void WriteObjects<T>(IEnumerable<T> values) { foreach (var o in values) { Console.Write(o + " "); } }
        static string yesno(this bool b) { return b ? "yes" : "no"; }
        static string YesNo(this bool b) { return b ? "Yes" : "No"; }
        static string YESNO(this bool b) { return b ? "YES" : "NO"; }

        static bool eq<T, U>() => typeof(T).Equals(typeof(U));
        static T ct<T, U>(U a) => (T)Convert.ChangeType(a, typeof(T));
        static T cv<T>(string s) => eq<T, int>() ? ct<T, int>(int.Parse(s))
                           : eq<T, long>() ? ct<T, long>(long.Parse(s))
                           : eq<T, double>() ? ct<T, double>(double.Parse(s))
                           : eq<T, char>() ? ct<T, char>(s[0])
                                             : ct<T, string>(s);
        static void Multi<T>(out T a) => a = cv<T>(GetStr());
        static void Multi<T, U>(out T a, out U b)
        {
            var ar = GetStrArray(); a = cv<T>(ar[0]); b = cv<U>(ar[1]);
        }
        static void Multi<T, U, V>(out T a, out U b, out V c)
        {
            var ar = GetStrArray(); a = cv<T>(ar[0]); b = cv<U>(ar[1]); c = cv<V>(ar[2]);
        }
        static void Multi<T, U, V,W>(out T a, out U b, out V c, out W d)
        {
            var ar = GetStrArray(); a = cv<T>(ar[0]); b = cv<U>(ar[1]); c = cv<V>(ar[2]); d = cv<W>(ar[3]);
        }
        static void Multi<T, U, V, W,X>(out T a, out U b, out V c, out W d,out X e)
        {
            var ar = GetStrArray(); a = cv<T>(ar[0]); b = cv<U>(ar[1]); c = cv<V>(ar[2]); d = cv<W>(ar[3]);e = cv<X>(ar[4]);
        }
    }
}

Measured memory_bytes: 13268
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int N=sc.nextInt();
        int W=sc.nextInt();
        long v[]=new long[N];
        int w[]=new int[N];
        for(int i=0;i<N;i++)
        {
            w[i]=sc.nextInt();
            v[i]=sc.nextLong();
        }
        long k[][]=new long[N+1][W+1];
       
        for(int i=0;i<=N;i++)
        {
            for(int j=0;j<=W;j++)
            {
               if(i==0 || j==0)
               {
                   k[i][j]=0;
               }
               else if(j>=w[i-1])
               {
                   k[i][j]= Math.max(v[i-1]+k[i-1][j-w[i-1]],k[i-1][j]);
               }
               else
               {
                   k[i][j]=k[i-1][j];
               }
            }
        }
        System.out.println(k[N][W]);
    }
}


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

#define pout(n)  printf ("%d\n", n)

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

const int d4x[4] = {1, 0, -1, 0};
const int d4y[4] = {0, 1, 0, -1};
const int d8x[8] = { 1,1,0,-1,-1,-1,0,1 };
const int d8y[8] = { 0,1,1,1,0,-1,-1,-1 };
 
typedef long long ll;
using namespace std;
 
int main() {
  string s;
  cin >> s;
  
  reverse(s.begin(), s.end());
  cout << s << endl;
  return 0;
}


Measured memory_bytes: 3144
#include<bits/stdc++.h>
using namespace std;
using Int = long long;
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;}

//INSERT ABOVE HERE
signed main(){
  Int n,m;
  cin>>n>>m;
  vector<Int> as(n);
  for(Int i=0;i<n;i++) cin>>as[i],as[i]--;

  using P = pair<Int, Int>;
  vector<P> vp;

  Int res=0;
  vector<Int> sub(m,0);
  for(Int i=0;i+1<n;i++){
    if(as[i]<as[i+1]){
      vp.emplace_back(as[i],as[i+1]);
    }else{
      res+=m-as[i]-1;
      sub[as[i+1]]+=m-as[i]-1;
      vp.emplace_back(as[i],m);
      vp.emplace_back(-1,as[i+1]);
    }
  }

  vector<Int> cnt(m+1,0);
  vector< vector<Int> > G(m+1);
  for(auto p:vp){
    if(p.first==p.second) continue;
    cnt[p.first+1]++;
    G[p.second].emplace_back(p.first+1);
  }

  Int ans=res,num=cnt[0];
  // cout<<0<<":"<<res<<" "<<num<<endl;
  for(Int i=1;i<m;i++){
    // resolve i - 1
    res-=sub[i-1];
    for(Int l:G[i-1]){
      res-=(i-1)-l;
      num--;
    }
    // at i
    res+=num;
    num+=cnt[i];
    chmax(ans,res);
    // cout<<i<<":"<<res<<" "<<num<<endl;
  }

  Int sum=0;
  for(auto p:vp) sum+=p.second-max(p.first,0LL);
  cout<<sum-ans<<endl;
  return 0;
}


Measured memory_bytes: 11372
n = int(input())
A = list(map(int,input().split()))
ok = True
if n%2==1:
    a=sorted(A)
    for i in range(len(a)):
        if i%2==0:
            if a[i]!=i:
                ok = False
        else:
            if a[i]!=i+1:
                ok = False
else:
    a=sorted(A)
    for i in range(len(a)):
        if i%2==1:
            if a[i]!=i:
                ok = False
        else:
            if a[i]!=i+1:
                ok = False
if ok:
    print(2**(n//2)%1000000007)
else:
    print(0)

Measured memory_bytes: 14008
#include<bits/stdc++.h>
using namespace std;
#define N 100010
int main()
{
	int n,m,h[N],maxv[N];
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		cin>>h[i];
		maxv[i]=0;
	}
	for(int i=0;i<m;i++)
	{
		int a,b;
		cin>>a>>b;
		maxv[a]=max(maxv[a],h[b]);
		maxv[b]=max(maxv[b],h[a]);
	}
	int ans=0;
	for(int i=1;i<=n;i++)
	{
		ans+=h[i]>maxv[i];
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 4412
string = [str(i) for i in input()]
for _ in range(int(input())):
	n = input().split()
	order = n.pop(0)
	if order == 'replace':
		string = string[:int(n[0])] + \
		[i for i in n[2]] + string[int(n[1])+1:]
	elif order == 'reverse':
		string = string[:int(n[0])] + \
		string[int(n[0]):int(n[1])+1][::-1] + \
		string[int(n[1])+1:]
	else :
		out = string[ int(n[0]) : int(n[1])+1 ]
		print(''.join(out))

Measured memory_bytes: 7752
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
int main() {
	// your code goes here
	long int t=1;
// 	cin>>t;
	while(t--)
	{
	    long long int a,b,c,d;
	    cin>>a>>b>>c>>d;
	    long long int ans1 = a*c,ans2= b*d,ans3 = a*d,ans4 = b*c;
	    ans1=max({ans1,ans2,ans3,ans4});
	    cout<<ans1<<endl;
	}
	return 0;
}


Measured memory_bytes: 3632
S = input()

les = len(S)

R = [0] * les
for i in range(les):
    if S[i] == '<':
        R[i] = R[i-1] + 1
    else:
        R[i] = 0

R = [0] + R

L = [0] * (les+1)
for i in range(les-1,-1,-1):
    if S[i] == '>':
        L[i] = L[i+1] + 1
    else:
        L[i] = 0

print(sum([max(R[x],L[x]) for x in range(les+1)]))

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

struct card {
  char mark;
  int rank;
};

void quicksort(struct card *A, int p, int r);
int partition(struct card *A, int p, int r);

int main(int argc, char *argv[])
{
  int n, i, j, stable, order, max = 0;
  struct card *A;
  struct card *original;
  char m[4];

  scanf("%d", &n);
  A = (struct card *)malloc(sizeof(struct card) * n);
  for (i = 0; i < n; i++) {
    scanf("%s", &(A[i].mark));
    scanf("%d", &(A[i].rank));
    max = (int)fmax(max, A[i].rank);
  }
  original = (struct card *)malloc(sizeof(struct card) * n);
  memcpy(original, A, sizeof(struct card) * n);

  quicksort(A, 0, n - 1);

  stable = 1;
  for (i = 1; i <= max; i++) {
    order = 0;
    for (j = 0; j < n; j++) {
      if (original[j].rank == i) m[order++] = original[j].mark;
    }
    order = 0;
    for (j = 0; j < n; j++) {
      if (A[j].rank == i) {
        if (A[j].mark != m[order]) {
          stable = 0;
          break;
        }
        order++;
      }
    }
    if (stable == 0) break;
  }

  if (stable == 1) printf("Stable\n");
  else printf("Not stable\n");
  for (i = 0; i < n; i++) printf("%c %d\n", A[i].mark, A[i].rank);

  return 0;
}

void quicksort(struct card *A, int p, int r)
{
  int q;

  if (p < r) {
    q = partition(A, p, r);
    quicksort(A, p, q-1);
    quicksort(A, q+1, r);
  }
}

int partition(struct card *A, int p, int r)
{
  int x = A[r].rank, i = p - 1, j;
  struct card tmp;

  for (j = p; j < r; j++) {
    if (A[j].rank <= x) {
      i++;
      memcpy(&tmp, &A[j], sizeof(struct card));
      memcpy(&A[j], &A[i], sizeof(struct card));
      memcpy(&A[i], &tmp, sizeof(struct card));
    }
  }
  memcpy(&tmp, &A[r], sizeof(struct card));
  memcpy(&A[r], &A[i+1], sizeof(struct card));
  memcpy(&A[i+1], &tmp, sizeof(struct card));

  return i+1;
}

Measured memory_bytes: 2196
import java.util.Scanner;

public class Main {

    public static int count;
    public static int m;
    public static int[] G = new int[100];

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

		int n = stdIn.nextInt();
        int [] a = new int[n];

        for(int i = 0; i < n; i++){
        	a[i] = stdIn.nextInt();
        }
        stdIn.close();

        shellSort(a,n);

        //m出力
        System.out.println(m);
        //g出力
        for (int i = m - 1; i >= 0; i--) {
            if (i != 0)
                System.out.print(G[i] + " ");
            else
                System.out.println(G[i]);
        }
        //count出力
        System.out.println(count);

        out_put(a);
	}

	private static void out_put(int array[]){

        	for(int i = 0; i < array.length; i++){
        		System.out.printf("%s", array[i]);
                System.out.printf("%n");
        	}
    }
	private static void insertionSort(int A[], int n, int g) {
        for (int i = g; i < n; i++) {
        	int v = A[i];
        	int j = i - g;
        	while (j >= 0 && A[j] > v){
                A[j+g] = A[j];
        		j = j - g;
        		count++;
        	}
        	A[j+g] = v;
        }
	}
	private static void shellSort(int A[], int n) {
		//初期化
	    count = 0;
	    m = 0;

	    for (int i = 1; ;i = 3 * i + 1) {
	        if (i > n) break;
	        G[m] = i;
	        m++;
	    }
		for (int i = m-1; i >=0; i--){
            insertionSort(A, n, G[i]);
		}
	}
}



Measured memory_bytes: 566824
#include<bits/stdc++.h>
#define ui unsigned int
#define ll long long
#define db double
#define ld long double
#define ull unsigned long long
const ll inf=1e18;
template<typename T> inline void read(T &x)
{
	T data=0,w=1;
	char ch=0;
	while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
	if(ch=='-')w=-1,ch=getchar();
	while(ch>='0'&&ch<='9')data=((T)data<<3)+((T)data<<1)+(ch^'0'),ch=getchar();
	x=data*w;
}
template<typename T> inline void write(T x,char ch='\0')
{
	if(x<0)putchar('-'),x=-x;
	if(x>9)write(x/10);
	putchar(x%10+'0');
	if(ch!='\0')putchar(ch);
}
template<typename T> inline void chkmin(T &x,T y){x=(y<x?y:x);}
template<typename T> inline void chkmax(T &x,T y){x=(y>x?y:x);}
template<typename T> inline T min(T x,T y){return x<y?x:y;}
template<typename T> inline T max(T x,T y){return x>y?x:y;}
inline ll qexp(ll a,ll b)
{
	ll res=1;
	while(b)
	{
		if(b&1)res=res*a;
		a=a*a;
		b>>=1;
	}
	return res;
}
int main()
{
	ll n,f[100010];
	read(n);
	for(register int i=1;i<=n;++i)f[i]=inf;
	for(register ll i=1;i<=n;++i)
	{
		chkmin(f[i],f[i-1]+1);
		for(register ll j=1;;++j)
		{
			ll now=qexp(6,j);
			if(now>i)break;
			else chkmin(f[i],f[i-now]+1);
		}
		for(register ll j=1;;++j)
		{
			ll now=qexp(9,j);
			if(now>i)break;
			else chkmin(f[i],f[i-now]+1);
		}
	}
	write(f[n],'\n');
	return 0;
}

Measured memory_bytes: 1024
/* AOJ 0089
 *
 * http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0089
 *
 */

#include <stdio.h>

#define BUFSIZE 500
#define DEBUG 0

#define true 1
#define false 0

int data[201][100];
int sum[202][101];


int is_num(char c){
    return ('0' <= c) && (c <= '9');
}


int parseInt(char** p){
    int i, r;
    char *s;
    int sign;
    int len;
    s = *p;

    r = 0;

    if(*s == '-'){
        sign = -1;
        s++;
    }else{
        sign = +1;
    }
    while(is_num(*s)){
        r *= 10;
        r+= (*s - '0');
        s++;
    }
    *p=s;
    return sign*r;
}

int parseComma(char** p){
    if(**p == ','){
        (*p)++;
        return true;
    }
    return false;
}


int parse(char* buf, int* found){
    int n;
    char*p;

    p = buf;
    n = 0;
    found[n] = parseInt(&p);
    n++;

    while(*p){
        if(!parseComma(&p)){
            break; /* cr lf etc.*/
        }
        found[n] = parseInt(&p);
        n++;
    }
    return n;
}


void load(int row, int *found, int count){
    int i;
    for(i=0;i<count;i++){
        data[row+1][i+1] = found[i];
    }
}

int max(int a, int b){
    if(a > b)
        return a;
    return b;
}

int solve(int size){
    int i, j;
    int row, diff;

    for(row=1;row<=size;row++){
        for(i=1;i<row+1;i++){
            if(DEBUG)
                printf(" v=%d@(%d, %d) ",data[row][i], row, i);
            sum[row][i] = max(sum[row-1][i-1], sum[row-1][i]) + data[row][i];
            if(DEBUG)
                printf(" s=%d@(%d, %d) ",sum[row][i], row, i);
        }
        if(DEBUG)
            printf("\n");
    }
    for(diff=1;diff<=size-1;diff++){
        /* row = diff + size */
        for(i=1;i< size - diff + 1;i++){
            if(DEBUG)
                printf(" v=%d@(%d, %d) ",data[diff+size][i], diff+size, i);
            row = diff+size;
            sum[row][i] = max(sum[row-1][i], sum[row-1][i+1]) + data[row][i];
            if(DEBUG)
                printf(" s=%d@(%d, %d) ",sum[diff+size][i], diff+size, i);
        }
        if(DEBUG)
            printf("\n");
    }
    return sum[size*2-1][1];
}


int main(){
    char buf[BUFSIZE+3];
    int found[100];
    int row;
    int size;
    int count;

    row = 0;
    size = 1;
    while(fgets(buf, BUFSIZE, stdin)){ 
        count = parse(buf, found);
        if(DEBUG)
            printf("size = %d\n", size);
        if(count >= row){
            load(row, found, count);
            row++;
            size = row;
        }else{
            load(row, found, count);
            row++;
        }
    }
    printf("%d\n", solve(size));
    return 0;
}

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

#define int64 long long

int main()
{
	int64 aa, bb, cc, kk;
	scanf("%lld %lld %lld %lld", &aa, &bb, &cc, &kk);
	if(kk <= aa)
	{
		printf("%lld\n", kk);
		return 0;
	}
	else if(kk <= aa + bb)
	{
		printf("%lld\n", aa);
		return 0;
	}
	else
	{
		printf("%lld\n", (aa - (kk - aa - bb)));
		return 0;
	}
	return 0;
}

Measured memory_bytes: 1732
using System.Linq;
using System;
using static System.Console;

class Program
{
  static void Main() => new Program().solve();

  void solve()
  {
    var param = ReadLine().Split(' ').Select(int.Parse).ToArray();
    var k = param[3];

    var seqA = ReadLine().Split(' ').Select(long.Parse).OrderByDescending(i => i).ToArray();
    var seqB = ReadLine().Split(' ').Select(long.Parse).OrderByDescending(i => i).ToArray();
    var seqC = ReadLine().Split(' ').Select(long.Parse).OrderByDescending(i => i).ToArray();

    var seqAB = seqA.SelectMany((a,i) =>
        seqB.TakeWhile((b,j) => i * j <= k).Select(b => a + b)
      ).OrderByDescending(ab => ab)
      .Take(k).ToArray();
    var seqABC = seqAB.SelectMany((ab, i) =>
        seqC.TakeWhile((c, j) => i * j <= k).Select(c => ab + c)
      ).OrderByDescending(abc => abc)
      .Take(k).ToArray();
    WriteLine(String.Join("\n", seqABC));
  }
}

Measured memory_bytes: 17760
n = int(input())
t = []
x = []
y = []
for _ in range(n):
    ti, xi, yi = map(int,input().split())
    t.append(ti)
    x.append(xi)
    y.append(yi)
for i in range(n):
    if ((x[i]+y[i])%2==0 and t[i]%2==1 or (x[i]+y[i])%2==1 and t[i]%2==0 or x[i]+y[i]>t[i]):
        print("No")
        exit()
print("Yes")


Measured memory_bytes: 11712
#include <bits/stdc++.h>
#include <iostream>
#include <string>
#include <map>
#include <math.h>
#include <vector>
using namespace std;
map<int, int> ct;
map<int, int> ct2;
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
typedef vector<pair<int, int> > vpii;
typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
typedef vector<ll> vll;
#define INF 0x3f3f3f3f
#define MOD 998244353LL
#define EPS 0.00001
#define f first
#define s second
#define pb push_back
#define mp make_pair

#define FOR(i, a, b) for (int i=(a); i<=(signed)(b); i++)
#define AFOR(i, a) for (int i=0; i<(signed)(a); i++)
#define RFOR(i, a, b) for (int i=(a); i >= b; i--)

#define MN 100005
int n, m, l;
int a, b, c;
string s[MN];
string str;
string ans;
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };

/*
int N;
cin >> N;
vi vect(N);
FOR(i,N) cin >> vec.at(i);*/
//sort(vec.begin(),vec.end());
//vvi data(N,vi(4));


/*	int bfs(int x, int y,vvi &A,vvi flag) {
		queue<pii> que;
		que.push(pii(x, y));
		while (que.size()) {
			pii p = que.front(); que.pop();
			AFOR(i, 4) {
				int nx = p.first + dx[i]; int ny = p.second + dy[i];
				if (0 <= nx && nx < N && 0 <= ny && ny < N) {
					if (A.at(p.first).at(p.second) + flag.at(p.first).at(p.second) < A.at(nx).at(ny)) {
						A.at(nx).at(ny) = A.at(p.first).at(p.second) + flag.at(p.first).at(p.second);
						que.push(pii(nx, ny));
					}
				}
			}
		}
		return 0;
	}
	*/
	/*int gcd(int p, int q){
		while(q != 0){
		int r = p % q;
		p = q;
		q = r;
		}
	return p;
	}*/

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int N;
	cin >> str;

	if (str.at(2) == str.at(3)&& str.at(4) == str.at(5)) {
			cout << "Yes" << endl;
	}
	
	else cout << "No" << endl;

	return 0;
}

Measured memory_bytes: 1024
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		double sum = 0;
		for(int i = 1 ; i <= N; i ++) {
			if(i % 3 != 0 && i % 5 != 0) {
				sum += i;
			}
		}
		System.out.println(String.format("%.0f", sum));
	}
}

Measured memory_bytes: 35948
/*
 * ID: ITP1_6_B
 * Problem: Finding missing cards
 */

#include <stdio.h>

int main(void)
{
    int n;
    int card[128][14] = {};
    char suites[] = "SHCD";

    scanf("%d%*c", &n);
    for (int i = 0; i < n; i++) {
        char suite;
        int number;
        scanf("%c %d\n", &suite, &number);
        card[(int)suite][number]++;
    }

    for (int i = 0; i < 4; i++)
        for (int j = 1; j <= 13; j++)
            if (!card[(int)suites[i]][j])
                printf("%c %d\n", suites[i], j);

    return 0;
}



Measured memory_bytes: 2100
#include <bits/stdc++.h>
using namespace std;
#define IOS                  \
    ios::sync_with_stdio(0); \
    cin.tie(0);              \
    cout.tie(0);
#define int long long
const unsigned int M = 1000000007;
using namespace std;
int freq[1000007];
int32_t main()
{
    IOS int t = 1;
    //cin >> t;
    while (t--)
    {
        int n;
        cin >> n;
        int sum = 0;
        int a[n];
        for (int i = 0; i < n; i++)
        {
            cin >> a[i];
            freq[a[i]]++;
            sum += a[i];
        }
        int q;
        cin >> q;
        while (q--)
        {
            int b, c;
            cin >> b >> c;
            sum -= b * freq[b];
            sum += c * freq[b];
            freq[c] += freq[b];
            freq[b] = 0;
            cout << sum << endl;
        }
    }

    return 0;
}

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

using namespace std;

#define ll long long
#define X first
#define Y second
#define all(x) x.begin(), x.end()

const int MX = (int)1e5 + 10;
const int mod = (int)1e9 + 7;

void add_self(int &x, int y){x += y; if(x >= mod) x -= mod;}
void sub_self(int &x, int y){x -= y; if(x < 0) x += mod;}
void mul(int &x, int y){x = x * 1LL * y % mod;}


int main(){

    cin.tie(0); cout.tie(0);
    ios_base::sync_with_stdio(0);

    int n;
    cin >> n;

    int res = n / 2 - (n % 2 == 0);

    cout << res << endl;
    
    return 0;
}

Measured memory_bytes: 256
//https://atcoder.jp/contests/dp/tasks/dp_c
#include <bits/stdc++.h>
//#define long int64_t
#define cerr if(0)cerr
#define watch(x) cerr << (#x) << " is " << (x) << endl
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define max3(a,b,c) (a>=b and a>=c ? a : b>=c and b>=a ? b : c)
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)
#define MOD 1e8 + 7
#define INF 2e9
#define DESPACITO 1e18
#define PI acos(-1);
#define E 998244353
#define pb push_back
#define mp make_pair
#define ll long long

using namespace std;
const int N = 1e5 + 5;
ll a[N], b[N], c[N], cache[N][3];

ll dp (int idx, int opt) {
    if (idx == 0)
        return 0;
    ll &ans = cache[idx][opt];
    if (ans != -1) 
        return ans;
    else {
        switch(opt) {
            case 0:
                ans = max(dp(idx-1, 1), dp(idx-1, 2)) + a[idx];
                break;
            case 1:
                ans = max(dp(idx-1, 0), dp(idx-1, 2)) + b[idx];
                break;
            case 2:
                ans = max(dp(idx-1, 0), dp(idx-1, 1)) + c[idx];
                break;
        }
        //cerr << "cache[" << idx << "][" << opt << "] is " << cache[idx][opt] << endl;
        return ans;
    }
}

int main() {
    int i, n;
    memset(cache, -1, sizeof(cache));
    cin >> n;
    for(i = 1; i <= n; i++) 
        cin >> a[i] >> b[i] >> c[i];
    cout << max(dp(n, 0), max(dp(n, 1), dp(n, 2)));
    return 0;
}

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

int main() {
  int n;
  double sum=0;
  cin >> n;
  vector<int> vec(n);
  for(int i=0;i<n;i++){
    int v;
    cin >> v;
    vec.at(i) = v;
  }
  sort(vec.begin(),vec.end());
  sum = vec.at(0);
  for(int i=1;i<n;i++){
    sum = (sum+vec.at(i))/2.0;
  }
  cout << sum << endl;
}

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

#define ll long long
#define tc                int T;cin>>T;while(T--)
const int INF =1e9+5;
int main()
{
    ios_base::sync_with_stdio(false);cin.tie(NULL);
	int n, c, b ; cin >> n;
  	vector<int> a(n,0);
	for (int& e : a)cin >> e;
	vector<int> dp(n, INF);
	dp[0] = 0;
	for (int i = 0; i < n; ++i) {
		for (int e : {i + 1, i + 2}) {
			if (e < n)
					dp[e] = min(dp[e],dp[i] + abs(a[e] - a[i]));
		}
	}
	cout << dp[n - 1] << '\n';
	return 0;
}


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

using namespace std;

int main()
{
int a;
int y[100];
cin>>a;
for(int i=0;i<a;i++)
cin>>y[i];
sort(y,y+a);
cout<<y[a-1]-y[0];
cout<<endl;
return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
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; }
const ll INF = 1LL << 60;

int N, M, X;
vector<int> C;
vector<vector<int>> A;

bool ok(vector<int> &ALG) {
    for (int i = 0; i < M; i++) {
        if (ALG[i] < X) return false;
    }

    return true;
}

int dfs(vector<int> &B) {
    if (B.size() == N) {
        vector<int> ALG(M);
        int cost = 0;
        for (int i = 0; i < N; i++) {
            if (B[i]) {
                cost += C[i];
                for (int j = 0; j < M; j++) {
                    ALG[j] += A[i][j];
                }
            }
        }

        if (ok(ALG)) {
            return cost;
        }

        return 1000000000;
    }

    int ans = 1000000000;
    for (int i = 0; i < 2; i++) {
        B.push_back(i);
        chmin(ans, dfs(B));
        B.pop_back();
    }

    return ans;
}

int main() {
    cin >> N >> M >> X;
    C.resize(N);
    A.resize(N, vector<int>(M));
    for (int i = 0; i < N; i++) {
        cin >> C[i];
        for (int j = 0; j < M; j++) {
            cin >> A[i][j];
        }
    }
    vector<int> B;

    int ans = dfs(B);

    if (ans == 1000000000) {
        cout << -1 << endl;
    } else {
        cout << ans << endl;
    }
    return 0;
}

Measured memory_bytes: 3552
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
//#define MOD 998244353
#define INF 1145141919810893364
//#define INF 810114514
#define PI 3.141592653589
typedef long long ll;
typedef pair<ll,ll> PP;
#define int ll
#define setdouble setprecision
#define REP(i,n) for(int i=0;i<(n);++i)
#define OREP(i,n) for(int i=1;i<=(n);++i)
#define RREP(i,n) for(int i=(n)-1;i>=0;--i)
#define GOODBYE do { cout << "0" << endl; return 0; } while (false)
#define MM <<" "<<
#define Endl endl
#define debug false
#define debug2 false


signed main(void){
    int N,M;
    cin >> N >> M;
    vector<pair<int,pair<int,int>>> Ans;
    
    
    if(N%2==1){
        int l=1,r=N-1;
        while(l<r){
            int k = min(r-l,N+l-r);
            Ans.push_back({k,{l,r}});
            l=(l+1)%N;
            r=(r+N-1)%N;
        }
    }else{
        
        int l=1,r=N/2;
        while(r-l>=1){
            int k = min(r-l,N+l-r);
            Ans.push_back({k,{l,r}});
            l=(l+1)%N;
            r=(r+N-1)%N;
        }
        l=(N+2)/2;r=N-1;
        while(r-l>=1){
            int k = min(r-l,N+l-r);
            Ans.push_back({k,{l,r}});
            l=(l+1)%N;
            r=(r+N-1)%N;
        }
    }
    
    //cout << Ans.size() << endl;
    sort(Ans.begin(),Ans.end());
    
    REP(i,M){
        
        cout << Ans[i].second.first+1 << " " << Ans[i].second.second+1 << endl;
    }
    
    return 0;
}




Measured memory_bytes: 6320
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
#define len(n) (int)n.length()
#define pb push_back
#define ll long long
#define make_pair mkp
#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define ALL(v) (v).begin(), (v).end()
#ifdef DBGPRT
#define dbg(n) cerr << "//" << #n << ":" << n <<endl
#else
#define dbg(n) ;
#endif
typedef pair<ll, ll> LLARR;
#define INF 999999999
const double PI = 3.1415926535897932384626433832795;

int main()
{
	ios::sync_with_stdio(false);
	ll x;
	cin >> x;
	cout << ((x/11) * 2 + ( x%11 != 0 ? (x%11 <= 6 ? 1 : 2 ) : 0 )) << endl;
	
	return 0;
}

Measured memory_bytes: 384