akhauriyash/Code-Regression huggingface dataset:
n = int(input())
z = []
for i in range(n):
    X, Y = map(int, input().split())
    z.append([X, Y, i])

x = sorted(z, key=lambda x: x[0])
y = sorted(z, key=lambda x: x[1])

new_list = []
for i in range(n-1):
    new_list.append([x[i+1][0]-x[i][0], x[i+1][2], x[i][2]])
    new_list.append([y[i+1][1]-y[i][1], y[i+1][2], y[i][2]])

new_list.sort(key=lambda x: x[0])

# Union-Find  ---------------
parent = [i for i in range(n)]
rank = [0 for i in range(n)]

def find(x):
    if parent[x] == x:
        return x
    else:
        parent[x] = find(parent[x])
        return parent[x]

def judge(a, b):
    a_parent = find(a)
    b_parent = find(b)
    if a_parent == b_parent:
        return True
    else:
        return False

def merge(a, b):
    a_parent = find(a)
    b_parent = find(b)
    if a_parent == b_parent:
        return
    else:
        if rank[a_parent] > rank[b_parent]:
            parent[b_parent] = a_parent
        elif rank[a_parent] < rank[b_parent]:
            parent[a_parent] = b_parent
        else:
            parent[a_parent] = b_parent
            rank[b_parent] += 1
#----------------------------

from collections import deque
q = deque(new_list)

cost = 0
while len(q)>0:
    c = q.popleft()
    if not judge(c[1], c[2]):
        merge(c[1], c[2])
        cost += c[0]

print(cost)

Measured memory_bytes: 57916
#include <iostream>
#include <iomanip>
#include <vector>
#include <valarray>
#include <map>
#include <set>
#include <list>
#include <queue>
#include <stack>
#include <bitset>
#include <utility>
#include <numeric>
#include <algorithm>
#include <functional>
#include <complex>
#include <string>
#include <sstream>

#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <cstring>

// this require C++11
//#include <unordered_set>
//#include <unordered_map>
//#include <random>

using namespace std;

#define all(c) c.begin(),c.end()
#define repeat(i,n) for(int i=0;i<static_cast<int>(n);i++)
#define debug(x) #x << "=" << (x)
#define dump(x) cerr << debug(x) << " (L:" << __LINE__ << ")"<< endl

typedef long long ll;
typedef vector<int> vi;

template<typename T>
ostream& operator<<(ostream& os,vector<T>& vec){
    typename vector<T>::iterator it,endit=vec.end();
    os << "[";
    for(it=vec.begin();it!=endit;it++){
        os << " " << *it << ",";
    }
    os << "]";
    return os;
}

template<typename T>
T input(){
    T t;cin >> t;
    return t;
}

template<typename T>
vector<T> input(const int N){
    vector<T> v(N);
    repeat(i,N) cin >> v[i];
    return v;
}

int solve(int n){
    int m;
    map<char,char> convmap;
    for(int i=0;i<n;i++){
        char temp1,temp2;
        cin >> temp1 >> temp2;
        convmap[temp1]=temp2;
    }
    cin >> m;
    string ans;
    for(int i=0;i<m;i++){
        char temp;
        cin >> temp;
        if(convmap.find(temp)!=convmap.end())
            cout << convmap[temp];
        else
            cout << temp;
    }
    cout <<endl;
    return 0;
}

int main(){
    for(;;){
        int n;
        cin >> n;
        if(n==0)
            break;
        solve(n);
    }
	return 0;
}

Measured memory_bytes: 1188
#include"bits/stdc++.h"
#include<boost/multi_array.hpp>
#include<boost/optional.hpp>
#include<boost/range/irange.hpp>
#include<boost/range/algorithm.hpp>
#include<boost/range/adaptors.hpp>
#include<boost/operators.hpp>
#include<boost/dynamic_bitset.hpp>

namespace adaptor = boost::adaptors;
using index_t = std::size_t;

namespace lib
{
	template<class T>constexpr T pow(T val, std::uint64_t p)
	{
		auto ret = T(1);
		for (auto i : boost::irange(0, 63))
		{
			if (p & (1ULL << i))
			{
				ret *= val;
			}
			val *= val;
		}
		return ret;
	}
	template<std::uint64_t Mod>class modnum :
		private boost::addable<modnum<Mod>>,
		private boost::subtractable<modnum<Mod>>,
		private boost::multipliable<modnum<Mod>>,
		private boost::dividable<modnum<Mod>>
	{
		std::uint64_t val;
		void clamp()
		{
			val %= Mod;
		}
	public:
		modnum() = default;
		modnum(std::int64_t v) :val()
		{
			if (v < 0)
			{
				v += (std::abs(v) / Mod + 1) * Mod;
			}
			val = v;
			clamp();
		}
		modnum(std::uint64_t v) :val(v)
		{
			clamp();
		}
		modnum(std::int32_t v) :modnum(static_cast<std::int64_t>(v))
		{

		}
		modnum(std::uint32_t v) :modnum(static_cast<std::uint64_t>(v))
		{

		}
		friend std::ostream& operator<<(std::ostream& os, modnum const& num)
		{
			return os << num.val;
		}
		auto& operator+=(modnum const& rhs)
		{
			val += rhs.val;
			clamp();
			return *this;
		}
		auto& operator-=(modnum const& rhs)
		{
			val += Mod - rhs.val;
			clamp();
			return *this;
		}
		auto& operator*=(modnum const& rhs)
		{
			val *= rhs.val;
			clamp();
			return *this;
		}
		auto& operator/=(modnum const& rhs)
		{
			val *= pow(rhs, Mod - 2).val;
			clamp();
			return *this;
		}
		auto const& operator*()const
		{
			return val;
		}
	};
}
using mod_t = lib::modnum<1000000007>;

mod_t run(std::size_t N, std::size_t M)
{
	boost::multi_array<mod_t, 2> dp(boost::extents[N + 1][N + 1]);
	dp[0][0] = 1;
	for (auto i : boost::irange<index_t>(1, N + 1))
	{
		dp[i][0] += dp[i - 1][0];
		for (auto j : boost::irange<index_t>(0, N))
		{
			dp[i][j] += dp[i - 1][j + 1];
			dp[i][j + 1] += 2 * dp[i - 1][j];
		}
	}
	return dp[N][M] / lib::pow(mod_t(2), M);
}

void Main()
{
	std::size_t N;
	std::string map;
	std::cin >> N >> map;
	std::cout << run(N, map.size()) << std::endl;
}

int main()
{
	std::cin.tie(nullptr);
	std::ios_base::sync_with_stdio(false);
	std::cout << std::fixed << std::setprecision(15);
	Main();
}

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

//#define int long long
#define reps(i,s,n) for(int (i)=(s);(i)<(n);++(i))
#define rep(i,n) reps(i,0,n)
#define rept(i,n) rep(i,(n)+1)
#define repst(i,s,n) reps(i,s,(n)+1)
#define reprt(i,n,t) for(int (i)=(n);(i)>=(t);--(i))
#define repr(i,n) reprt(i,n,0)
#define each(itr,v) for(auto &(itr):(v))
#define all(c) (c).begin(),(c).end()
#define rall(c) (c).rbegin(),(c).rend()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define tmax(x,y,z) max(x,max(y,z))
#define tmin(x,y,z) min(x,min(y,z))
#define chmin(x,y) if((x)>(y))(x)=(y)
#define chmax(x,y) if((x)<(y))(x)=(y)
#define ln '\n'
#define bln(i,n) (((i)==(n)-1)?'\n':' ')
#define dbg(x) cout<<#x" = "<<(x)<<ln<<flush
#define dbga(x,n) {cout<<#x" : ";for(int (i)=0;i<(n);++i){cout<<((x)[i])<<(i==((n)-1)?'\n':' ')<<flush;}}
#define zero(a) memset(a,0,sizeof(a))
#define unq(a) sort(all(a)),a.erase(unique(all(a)),a.end())

typedef long double ld;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<string> vst;
typedef vector<bool> vb;
typedef vector<ld> vld;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<vector<int> > mat;

const ll inf = (ll)1e9+10;
const ll linf = (ll)1e18+10;
const ll mod = (ll)(1e9+7);
const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};
const int ddx[] = {0, 1, 1, 1, 0, -1, -1, -1};
const int ddy[] = {1, 1, 0, -1, -1, -1, 0, 1};
const double eps = 1e-10;

ll mop(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b) {return a*b/gcd(a,b);}

struct oreno_initializer {
	oreno_initializer() {
		cin.tie(0);
		ios::sync_with_stdio(0);
	}
} oreno_initializer;

// ━━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…
// .｡.:( ^ω^)・ﾟ＋.｡.:( ^ω^)・ﾟ＋.｡.:( ^ω^)・ﾟ＋.｡.:( ^ω^)・ﾟ＋.｡.:( ^ω^)・ﾟ＋
// ・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・

int h, w;
string s[50];

bool ng(int x, int y) {
	bool r = true;
	rep(i,4) {
		int xx = x + dx[i], yy = y + dy[i];
		if (xx<0 || xx>=h || yy<0 || yy>=w) continue;
		if (s[xx][yy]=='#') r = false;
	}
	return r;
}

signed main() {
	cin >> h >> w;
	rep(i,h) cin >> s[i];
	rep(i,h) rep(j,w) if (s[i][j]=='#' && ng(i,j)) return cout << "No" << ln, 0;
	cout << "Yes" << ln;
}

Measured memory_bytes: 256
#include<deque>
#include<queue>
#include<vector>
#include<algorithm>
#include<iostream>
#include<set>
#include<cmath>
#include<tuple>
#include<string>
#include<chrono>
#include<functional>
#include<iterator>
#include<random>
#include<unordered_set>
#include<array>
#include<map>
#include<iomanip>
#include<assert.h>
#include<bitset>
#include<stack>
#include<memory>
using namespace std;
typedef long long ll;
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
//const ll mod = 1000000007;
vector<ll> making_list(ll m) {
	vector<ll> ret;
	for (ll i = 1; i*i <= m; i++) {
		if (m%i == 0) {
			ret.push_back(i);

			
			if (i*i != m) {
				ret.push_back(m / i);
				//cout << "work" << endl;
			}
		}
	}
	/*for (ll i = 0; i*i < ret.size(); i++) {
		cout << ret[i] <<"???"<< endl;
	}*/
	sort(begin(ret), end(ret));

	return ret;

	/*ll& n = m;
	vector< int64_t > ret;
	for (int64_t i = 1; i*i <= n; i++) {
		if (n % i == 0) {
			ret.push_back(i);
			if (i * i != n) ret.push_back(n / i);
		}
	}
	for (ll i = 0; i < ret.size(); i++) {
		cout << ret[i] << "???" << endl;
	}
	sort(begin(ret), end(ret));
	return (ret); */
}

int main() {
	ll answer = 0;
	ll n, m;
	cin >> n >> m;
	vector<ll> ret = making_list(m);
	for (int i = ret.size()-1; i >= 0; i--) {
		if (m >= n * ret[i]) {
		    answer = ret[i];
			cout << answer << endl;
			return 0;
		}

	}
	cout << answer << endl;
	return 0;
}

Measured memory_bytes: 256
n = gets.to_i
t = gets.chomp.split.map(&:to_i)
m = gets.to_i
p = []
x = []
0.upto(m-1) do
    pp, xx = gets.chomp.split.map(&:to_i)
    p << pp
    x << xx
end

sum = t.inject{|s,n| s+n}

0.upto(m-1) do |i|
    pp = p[i] - 1
    xx = x[i]
    dif = t[pp] - xx
    puts sum - dif
end

Measured memory_bytes: 1788
#! /usr/bin/env python
# -*- coding: utf-8 -*-

import os
import sys
import itertools

class Hoge(object):
    
    def __init__(self):
        pass

    def func(self):
        '''
        insert your code
        '''
        while True:
            n, s = map(int, raw_input().split())
            if n == 0 and s == 0:
                break
            ans = 0
            # self.dfs(0, 0, [], n, s)
            # for i in range(10):
            #     for j in range(10):
            #         for k in range(10):
            #             if i >= j or j >= k or i >= k:
            #                 continue

            #             if i + j + k == s:
            #                 print i, j, k
            #                 ans += 1
            for e in itertools.combinations(range(10), n):
                if sum(e) == s:
                    ans += 1
                
            print ans
        return None

    # def dfs(self, num, sumNum, rec, n, s):
    #     print num, sumNum, rec, n, s
    #     if num == n:
    #         if sumNum == s:
    #             self.ans += 1
    #     else:
    #         for i in range(s):
    #             if not i in rec and sumNum + i <= s:
    #                 self.dfs(num + 1, sumNum + i, rec + [i], n, s)

if __name__ == '__main__':
    h = Hoge()
    h.func()
    

Measured memory_bytes: 4356
h, w = map(int, input().split())
a = [''] * h
for i in range(h):
    a[i] = input()
for i in range(w+2):
    print('#', end='')
print()
for i in a:
    print('#' + i + '#')
for i in range(w+2):
    print('#', end='')
print()

Measured memory_bytes: 3064
#include <iostream>
#include<ctype.h>
#include<stdio.h>
using namespace std;

int main() {

	char ch[2000];
	scanf("%[^\n]", ch);
	for (int i = 0; ch[i] != '\0'; i++) {
		char c = ch[i];
		if ('a' <= c && c <= 'z') {
			printf("%c", toupper(c));
		}
		else if ('A' <= c && c <= 'Z') {
			printf("%c", tolower(c));
		}
		else {
			printf("%c",c);
		}
	}printf("\n");
		return 0;
}


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

int main()
{
        int h, w;
        int l=0;

        while(scanf("%d %d\n", &h, &w)){
                
                if(h==0 && w==0) break;
                
                for( l=0; l<h; l++){
                        if(l%2){
                                for(int i=0; i<w; i++){
                                        cout << (i%2 ? "#" : ".");
                                }
                        }else{
                                for(int i=0; i<w; i++){
                                        cout << (i%2 ? "." : "#");
                                }
                        }
                        cout << endl;
                }
                cout << endl;
        }
}

Measured memory_bytes: 1204
n = gets.to_i
as = gets.split.map(&:to_i)

h = Hash.new(0)
sum = 0

as.each do |a|
  h[a] += 1
  sum += a
end

q = gets.to_i
q.times do
  b, c = gets.split.map(&:to_i)
  sum += h[b] * (c - b)
  h[c] += h[b]
  h.delete(b)

  p sum
end


Measured memory_bytes: 26096
#include<bits/stdc++.h>
using namespace std;
int main(){

string s;

cin>>s;

int m=0;

if(s[2]==s[3]){
m++;
}
if(s[4]==s[5]){
m++;
}

if(m==2){
cout<<"Yes"<<endl;
}else{
cout<<"No"<<endl;

}

return 0;
}


Measured memory_bytes: 3624
#include<iostream>
#include<cstdio>
#include<deque>
#include<algorithm>
#define LL long long
#define reint register int
using namespace std;
const int N=100005;
deque<LL>que;
LL b,s[N],cot[N],ans[N];int n,m,cnt;
void push(LL x){
    while(!que.empty()&&que.back()>=x)que.pop_back();
    que.push_back(x);return;
}
int main(){
    // freopen("l.in","r",stdin);
    // freopen("l.out","w",stdout);
    scanf("%d%d",&n,&m);push(n);
    for(reint i=1;i<=m;i++)
    scanf("%lld",&b),push(b);
    while(!que.empty())
        s[++cnt]=que.front(),que.pop_front();
    cot[cnt]=1;
    for(reint i=cnt-1;~i;i--){
        LL len=s[i+1];
        while(len>s[1]){
            reint pos=upper_bound(s+1,s+i+1,len)-s-1;
            cot[pos]+=len/s[pos]*cot[i+1];
            len%=s[pos];
        }ans[len]+=cot[i+1];
    }
    for(reint i=s[1];i;i--)ans[i]+=ans[i+1];
    for(reint i=1;i<=n;i++)printf("%lld\n",ans[i]);
    return 0;
}

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

typedef struct {
  int to;
  long long dist;
} Edge;

vector<Edge> edge[100005];
vector<int> ans(100005);

void dfs(int start, int from = -1, long long dist = 0) {
  for (Edge e: edge[start]) {
    if (e.to == from) continue;
    ans[e.to] = (dist + e.dist) % 2;
    dfs(e.to, start, (dist + e.dist) % 2);
  }
}

void Main() {
  int n;
  cin >> n;
  for (int i = 0; i < n - 1; i++) {
    int u, v, w;
    cin >> u >> v >> w;
    edge[u - 1].push_back({v - 1, w});
    edge[v - 1].push_back({u - 1, w});
  }

  dfs(0);

  for (int i = 0; i < n; i++) {
    cout << ans[i] << endl;
  }
}

int main() {
  std::cin.tie(nullptr);
  std::ios_base::sync_with_stdio(false);
  std::cout << std::fixed << std::setprecision(15);
  Main();
  return 0;
}


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

using namespace std;

int n, p, c, o;
string curr;

int main(void) {
    cin >> n;

    while(n > 0) {
        p = o = c = 0;
        while(1) {
            cin >> curr;
            if(curr == "HOMERUN") {
                p += c + 1;
                c = 0;
            } else if(curr == "OUT") {
                o += 1;
            } else {
                c += 1;
                if(c == 4) {
                    p += 1;
                    c -= 1;
                }
            }
            if(o == 3) break;
        }
        cout << p << endl;
        n--;
    }
    return 0;
}

Measured memory_bytes: 0
m = int(input())
for _ in range(m):
    train = input()
    trains = set()
    for i in range(1, len(train)):
        mae = train[0:i]
        ato = train[i::]
        r_mae = mae[::-1]
        r_ato = ato[::-1]
        trains.add(mae + ato)
        trains.add(ato + mae)
        trains.add(mae + r_ato)
        trains.add(r_ato + mae)
        trains.add(r_mae + ato)
        trains.add(ato + r_mae)
        trains.add(r_ato + r_mae)
        trains.add(r_mae + r_ato)
    print(len(trains))



Measured memory_bytes: 5632
// Created by Bingoo on 7/8/2020.
#include"bits/stdc++.h"
using namespace std ;
#define ll  long long
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

template <class ...Args>
auto &see(const Args &...args) {return ((cerr << " " << args), ...) << '\n';}
#define bug(...)  cerr << "[ "#__VA_ARGS__" ] = "; see(__VA_ARGS__) << '\n';
//C++17
template<typename... Args>
void read(Args&... args){((cin >> args), ...);}
template<typename... Args>
void write(Args... args){((cout << args << " "), ...);}


vector<int> dp(100005,-1) ;
vector<int> h(100005);
int N , k ;

int solve(int n){
    if(n==N)return 0 ;

    if(dp[n] != -1)return dp[n] ;

    int ans=INT_MAX;

    for(int i = 1 ; i <= k && n+i <= N ; i++)ans= min(abs(h[n]-h[n+i])+solve(n+i),ans);


    return dp[n] = ans;
}

int main(){
    IOS

    cin >> N >> k;

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

    cout << solve(1) <<'\n' ;


}

Measured memory_bytes: 10308
#include <stdio.h>

//#define getchar_unlocked()  getchar()
int in()
{
	int n = 0, c = getchar_unlocked();
	do n = 10*n + (c & 0xf), c = getchar_unlocked(); while (c >= '0');
	return n;
}

int gcd(int a, int b)
{
	int r;
	while (b != 0) r = a % b, a = b, b = r;
	return a;
}

int main()
{
	int a, b;

	a = in(), b = in();
	printf("%d\n", gcd(a, b));
	return 0;
}




Measured memory_bytes: 2048
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)

from collections import Counter


N, M = map(int, input().split())

graph = [[] for _ in range(N)]
for _ in range(M):
    a, b = [int(x) - 1 for x in input().split()]
    graph[a].append(b); graph[b].append(a)

def dfs(now):
    connected_component[now] = cc
    for next in graph[now]:
        if connected_component[next]:
            continue
        dfs(next)

connected_component = [0] * N
cc = 1
for i in range(N):
    if connected_component[i]:
        continue
    dfs(i)
    cc += 1

ans = max(Counter(connected_component).values())

print(ans)


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

int main() {
  int n;
  cin >> n;
  int c[26], s[n][26];
  vector<int> last(26, -1);
  for (int i = 0; i < 26; ++i)
    cin >> c[i];
  for (int i = 0; i < n; ++i)
    for (int j = 0; j < 26; ++j)
      cin >> s[i][j];
  for (int i = 0; i < n; ++i) {
    int neg(0), test(-1);
    for (int j = 0; j < 26; ++j) {
      if (last[j] >= 0) neg -= c[j] * (j - last[j]);
    }
    int max_score = -1e9;
    for (int j = 0; j < 26; ++j) {
      int ss = s[i][j] + neg + (last[j] >= 0 ? c[j] * (j - last[j]) : 0);
      if (ss > max_score) {
        max_score = ss;
        test = j;
      }
    }
    cout << rand() % 26 + 1 << endl;
    last[test] = i;
  }
  return 0;
}


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

typedef long long s64;
#define rep(i,l,r) for(int i=l;i<=r;++i)
const int N=2e5+5;
int a[N];

int main()
{
	//freopen("1.in","r",stdin);
	int n;
	cin>>n;
	s64 ans=0;
	a[0]=-1;
	rep(i,1,n)
	{
		scanf("%d",a+i);
		if(a[i]>a[i-1]+1)
		{
			puts("-1");
			exit(0);
		}
		if(a[i]==a[i-1]+1)++ans;
		else ans+=a[i];
	}
	cout<<ans-1;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
const int MAX=200000;


int main(){
    int R[MAX],n;

    cin>>n;
    for(int i=0;i<n;i++) cin>>R[i];

    int maxv=-1e9-1;
    int minv=R[0];

    for(int i=1;i<n;i++){
        maxv=max(maxv,R[i]-minv);
        minv=min(minv,R[i]);
    }

    cout<<maxv<<endl;

    return 0;
}


Measured memory_bytes: 3840
def euler_tour(tree: list, root: int):
    """オイラーツアーを行う"""
    n = len(tree)
    par = {root: -1}
    trail = []
    is_up = []
    stack = [root]
    while stack:
        v = stack.pop()
        if v >= 0:  # 行きがけ順の処理
            trail.append(v)
            is_up.append(0)
            stack.append(~v)
            for nxt_v in tree[v]:
                if nxt_v not in par:
                    par[nxt_v] = v
                    stack.append(nxt_v)
                    

        else:  # 帰りがけ順の処理
            if ~v == root:
                continue
            trail.append(par[~v])
            is_up.append(1)
 
    return trail, is_up


class BIT:
    """区間加算、一点取得クエリをそれぞれO(logN)で答えるデータ構造"""
    def __init__(self, n):
        self.size = n
        self.bit = [0] * (n + 1)

    def build(self, array):
        """arrayを初期値とするBinaryIndexTreeを構築する O(N)"""
        for i in range(1, self.size + 1):
            if i - 1 + (i & -i) >= self.size:
                self.bit[i] = array[i - 1]
            else:
                self.bit[i] = array[i - 1] - array[i + (i & -i) - 1]

    def _add(self, i, val):
        while i > 0:
            self.bit[i] += val
            i -= i & -i

    def get_val(self, i):
        """i番目の値を求める"""
        i = i + 1
        s = 0
        while i <= self.size:
            s += self.bit[i]
            i += i & -i
        return s

    def add(self, l, r, val):
        """区間[l, r)にvalを加える"""
        self._add(r, val)
        self._add(l, -val)


from collections import deque
import sys
input = sys.stdin.readline


n = int(input())
c = list(map(int, input().split()))
info = [list(map(int, input().split())) for i in range(n - 1)]

tree = [[] for i in range(n)]
for a, b in info:
    a -= 1
    b -= 1
    tree[a].append(b)
    tree[b].append(a)

# 葉に対する頂点と辺の追加
plus = n + 1
for i in range(1, n):
   if len(tree[i]) == 1:
        info.append([i + 1, plus])
        plus += 1
# 根に対する頂点と辺の追加
info.append([1, plus])

new_n = len(info) + 1
tree = [[] for i in range(new_n)]
for a, b in info:
    a -= 1
    b -= 1
    tree[a].append(b)
    tree[b].append(a)

root = new_n - 1
et, is_up = euler_tour(tree, root)

bit = BIT(n)
stack = [[] for i in range(n)]
ans = [0] * n

for i in range(len(et)):
    if et[i] >= n:
        continue

    if is_up[i]:
        ind = i
        i = c[et[i]] - 1
        val = bit.get_val(i)
        ans[i] += val * (val + 1) // 2

        bit.add(i, i + 1, -val)
        if len(stack[i]) >= 1 and is_up[ind + 1]:                                                               
            tmp = stack[i].pop()                                                             
            bit.add(i, i + 1, tmp)    
    else:
        i = c[et[i]] - 1
        val = bit.get_val(i)
        stack[i].append(val)
        bit.add(0, n, 1)
        bit.add(i, i + 1, -(val + 1))

for i in range(n):
    val = bit.get_val(i)
    ans[i] += val * (val + 1) // 2

for i in range(n):
    print(n * (n + 1) // 2 - ans[i])

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

int main() {
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    if ((a+d-1)/d<(c+b-1)/b)
    {
        cout << "No";
    }
    else
    {
        cout << "Yes";
    }
    return 0;
}

Measured memory_bytes: 3636
#include <bits/stdc++.h>
using namespace std;
#define Rint register int
typedef long long ll;
ll hd[100010],nxt[400010],eds[400010],val[400010],et=0;
inline ll read(){
	ll x=0,w=1;char c=getchar();
	while(!isdigit(c)){
		if(c=='-')w=-1;
		c=getchar();
	}
	while(isdigit(c)){
		x=(x<<1)+(x<<3)+c-'0';
		c=getchar();
	}
	return x*w;
}
inline void ad(ll u,ll v,ll w){
	eds[++et]=v;
	val[et]=w;
	nxt[et]=hd[u];
	hd[u]=et;
}
ll n,m;
ll dis[100010];
bool vstd[100010];
bool inq[100010];
queue<ll> q;
ll spfa(ll u){
	memset(vstd,0,sizeof(vstd));
	ll minn=0,maxx=0;
	dis[u]=0;
	while(!q.empty())q.pop();
	q.push(u);
	inq[u]=true;
	while(!q.empty()){
		ll now=q.front();
		q.pop();
		inq[now]=false;
		for (Rint i=hd[now];i;i=nxt[i])
			if (dis[eds[i]]>dis[now]+val[i]){
				if(vstd[eds[i]])return -1;
				vstd[eds[i]]=true;
				dis[eds[i]]=dis[now]+val[i];
				maxx=max(maxx,dis[eds[i]]);
				minn=min(minn,dis[eds[i]]);
				if(!inq[eds[i]]){
					inq[eds[i]]=true;
					q.push(eds[i]);
				}
			}
	}
	return maxx-minn;
}
int main(){
	//freopen("line.in","r",stdin);
//	freopen("line.out","w",stdout);
	n=read(),m=read();
	ll t1,t2,t3;
	for (Rint i=1;i<=m;i++){
		t1=read(),t2=read(),t3=read();
		ad(t1,t2,t3);
		ad(t2,t1,-t3);
	}
	memset(dis,0x3f,sizeof(dis));
	ll maxx=0;
	for (Rint i=1;i<=n;i++)
		if (dis[i]==0x3f3f3f3f3f3f3f3f){
			ll tmp=spfa(i);
			if (tmp==-1){
				puts("No");
				return 0;
			}
			maxx=max(maxx,tmp);
		}
	puts("Yes");
	return 0;
} 

Measured memory_bytes: 12160
#include <iostream>
#include <utility>
#include <vector>
#include <string>
#include <cstdio>
#include <algorithm>

using namespace std;

bool cmp(pair<int, pair<int, long long int> > a, pair<int, pair<int , long long int> > b) {
    if(a.second.first!=b.second.first) {
        return a.second.first < b.second.first;
    } else {
        return a.second.second < b.second.second;
    }
}

int main() {
    int N, M;
    cin >> N >> M;
    
    vector<pair<int, pair<int, long long int> > > ipy(M, \
        pair<int, pair<int, long long int> >());
    for(int i=0; i<M; i++) {
        int p;
        long long int y;
        cin >> p >> y;
        ipy[i] = make_pair(i, make_pair(p, y));
    }
    
    sort(ipy.begin(), ipy.end(), cmp);

    // for(int i=0; i<M; i++) {
    //     cout << "After Sorted: " << ipy[i].first << ", " \
    //     << ipy[i].second.first << ", " << ipy[i].second.second << endl;
    // }

    vector<pair<int, int> > ans(M, \
        pair<int, int>());
    int count=1;
    int group=1;
    for(int i=0; i<M; i++) {
        if(group!=ipy[i].second.first) {
            group=ipy[i].second.first;
            count=1;
        }
        // cout << i << ", " << ipy[i].first << ", " << ipy[i].second.first \
        // << ", " << count << endl;
        ans[ipy[i].first] = make_pair(ipy[i].second.first, count);
        count++;
    }
    for(int i=0; i<M; i++) {
        printf("%06d%06d\n", ans[i].first, ans[i].second);
        // char str[13];
    }
    
    return 0;
    
}

Measured memory_bytes: 4608
#include<iostream>
#include<cstdio>
using namespace std;
double a[4][4];
int main()
{
	for(int i=1;i<=3;i++)
	{
		for(int j=1;j<=3;j++)
		{
			scanf("%lf",&a[i][j]);
		}
	}
	if((a[1][2]+a[2][3]+a[3][1]+a[1][3]+a[2][1]+a[3][2])/2==a[1][1]+a[2][2]+a[3][3])
	printf("Yes");
	else
	printf("No");
}

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

def choise(x,y):
    C=[]
    for i in range(x,x+m):
        C.append(A[i][y:y+m])
    return C

ans=0
for x in range(n-m+1):
    for y in range(n-m+1):
        if choise(x,y)==B:
            ans+=1
if ans==0:
    print("No")
else:
    print("Yes")

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

int in(void){
	int i;scanf("%d",&i);
	return i;
}
long long llin(void){
	long long i;scanf("%lld",&i);
	return i;
}
void chin(char s[]){
	scanf("%s",s);
}
void print(int a){
	printf("%d\n",a);
}
void llprint(long long a){
	printf("%lld\n",a);
}
void print2(int a,int b){
	printf("%d %d\n",a,b);
}
long long max(long long a,long long b){
	return a>b?a:b;
}
long long min(long long a,long long b){
	return a<b?a:b;
}

int main(void){
	long long a=llin(),b=llin(),c=llin(),i;
	for(i=1;;i++){
		long long tmp=a*i;
		if(tmp%b==c){
			puts("YES");
			return 0;
		}
		if(tmp%b==0){
			puts("NO");
			return 0;
		}
	}
	return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
#define int long long
//#undef int
#define mk make_pair
#define pb push_back
typedef pair<int, int> pii;
const int mod = 1000000007;
const int INF = 1000000009;
const long long INFL = 1000000000000000018ll;

int m[4];

signed main()
{
    for(int i = 0; i < 4; i++){
        int a;
        cin >> a;
        if(a == 1){
            m[0]++;
        }
        else if(a == 9){
            m[1]++;
        }
        else if(a == 7){
            m[2]++;
        }
        else if(a == 4){
            m[3]++;
        }
    }
    string s = "YES";
    for(int i = 0; i < 4; i++){
        if(m[i] != 1){
            s = "NO";
        }
    }
    cout << s << endl;

    return 0;
}
/*



*/




Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <utility>
#include <map>
#include <algorithm>
#include <queue>
#include <cmath>
#include <string>

using namespace std;

int main() {
  int n;
  cin >> n;
  int ans = 0;
  int smin = INT_MAX;

  for (int i=0; i<n; i++) {
    int s;
    cin >> s;
    ans += s;
    if (s%10!=0) smin = min(smin, s);
  }

  if (ans%10==0) ans -= (smin>100? ans : smin);
  cout << ans << endl;
}

Measured memory_bytes: 256
#define _GLIBCXX_DEBUG//TLEの原因になるので注意！！！！！！！！！！！
#include<cmath>
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
vector<int> arr;
stack<int> st;
queue<int> qu;
queue<pair<int,int> > qu2;
priority_queue<int> pq;
#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define rep2(i,n) for(int i=1; i<=(int)(n); i++)
#define mins(x,y) x=min(x,y)
#define maxs(x,y) x=max(x,y)
typedef set<int> set_t;
typedef set<string> set_g;
typedef complex<double> xy_t;
static const int NIL = -1;
static const int INF = 1000000007;
#define mp make_pair
#define sz(x) int(x.xise())
#define mod 1000000007
#define reps(i,s,n) for(int i = s; i < n; i++)
//#define int long long

//cerrはコメントアウトしなくても通る//ただしTLEを引き起こすことがある

int a[100005];//動物の正体　0羊　１狼

int main(){
    int n;
    cin >> n;
    string s;
    cin>> s;
    rep(p,2){
        rep(q,2){
            a[1]=p;
            a[2]=q;
            //a[0]
            if(a[1]==0){
                if(s[0]=='o'){
                    a[0]=a[2];
                }else{
                    if(a[2]==0){
                        a[0]=1;
                    }else{
                        a[0]=0;
                    }
                }
            }else{
                if(s[0]=='o'){
                    if(a[2]==0){
                        a[0]=1;
                    }else{
                        a[0]=0;
                    }
                }else{
                    a[0]=a[2];
                }
            }
            rep2(i,n-1){
                if(a[i]==0&&a[i+1]==0){
                    if(s[i]=='o'){
                        a[i+2]=0;
                    }else{
                        a[i+2]=1;
                    }
                }else if(a[i]==0&&a[i+1]==1){
                    if(s[i]=='o'){
                        a[i+2]=1;
                    }else{
                        a[i+2]=0;
                    }
                }else if(a[i]==1&&a[i+1]==0){
                    if(s[i]=='o'){
                        a[i+2]=1;
                    }else{
                        a[i+2]=0;
                    }
                }else if(a[i]==1&&a[i+1]==1){
                    if(s[i]=='o'){
                        a[i+2]=0;
                    }else{
                        a[i+2]=1;
                    }
                }
            }
            if(a[1]==a[n+1]&&a[0]==a[n]){
                rep2(i,n){
                    if(a[i]==0){
                        cout<<'S';
                    }else{
                        cout<<'W';
                    }
                }
                //cerr<<a[1]<<a[n+1]<<endl;
                //cerr<<s[1]<<endl;
                cout<<endl;
                return 0;
            }
        }
    }
    cout<<-1<<endl;
    return 0;
}

Measured memory_bytes: 1024
N = int(input())
a = list(map(int, input().strip().split()))
rev = 0
counter = 0
while(rev >= 0):
    for i in range(1, N):
        if(a[i-1] > a[i]):
            a[i-1], a[i] = a[i], a[i-1]
            rev += 1
            counter += 1
    if(rev == 0):
        for j in range(0, N-1):
            print(a[j], end=" ")
        print(a[N-1])
        print(counter)
        break
    rev = 0



Measured memory_bytes: 5604
#include <iostream>
#include <queue>

using namespace std;

int dx[] = {-1, 0, 1, 2, 2, 2, 1, 0, -1, -2, -2, -2};
int dy[] = {-2, -2, -2, -1, 0, 1, 2, 2, 2, 1, 0, -1};

class state {

public:
    int x;
    int y;
    int cnt;
    state(int a, int b, int c) { x = a; y = b; cnt = c; }
};

int main()
{
    int px, py;

    while (cin >> px >> py, px || py) {
        int n;
        vector<int> map[10][10];

        cin >> n;
        for (int i = 0; i < n; i++) {
            int sx, sy;

            cin >> sx >> sy;
            for (int y = -1; y <= 1; y++)
                for (int x = -1; x <= 1; x++) {
                    if (sx + x < 0 || sx + x > 9 || sy + y < 0 || sy + y > 9)
                        continue;
                    map[sy + y][sx + x].push_back(i + 1);
                }
        }
        
        state s(px, py, 1);
        queue<state> q;
        bool flag = false;

        q.push(s);
        
        while (!q.empty()) {
            state now = q.front();
            q.pop();

            if (now.cnt == n + 1) {
                flag = true;
                break;
            }

            for (int i = 0; i < 12; i++) {
                int nx = dx[i] + now.x;
                int ny = dy[i] + now.y;

                if (nx < 0 || nx > 9 || ny < 0 || ny > 9)
                    continue;
                for (int k = 0; k < map[ny][nx].size(); k++) {
                    if (map[ny][nx][k] == now.cnt) {
                        state in(nx, ny, now.cnt + 1);
                        q.push(in);
                    }
                }
            }
        }

        if (flag) 
            cout << "OK\n";
        else
            cout << "NA\n";
    }

    return 0;
}

Measured memory_bytes: 1184
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){
	return o<<"("<<p.fs<<","<<p.sc<<")";
}
template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){
	o<<"{";
	for(const T& v:vc) o<<v<<",";
	o<<"}";
	return o;
}
using ll = long long;
template<class T> using V = vector<T>;
template<class T> using VV = vector<vector<T>>;
constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n-1); }

#ifdef LOCAL
#define show(x) cerr << "LINE" << __LINE__ << " : " << #x << " = " << (x) << endl
#define dump(x) cerr << "LINE" << __LINE__ << " : " << #x << " = {";  \
	for(auto v: x) cerr << v << ","; cerr << "}" << endl;
#else
#define show(x) true
#define dump(x) true
#endif

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);		//DON'T USE scanf/printf/puts !!
	cout << fixed << setprecision(20);
	
	ll a,b,k; cin >> a >> b >> k;
	if(a<k){
		k-=a;a=0;
		if(b<k){
			k-=b;b=0;
		}else{
			b-=k;
		}
	}else{
		a-=k;
	}
	cout << a << " " << b << endl;
}


Measured memory_bytes: 256
import java.io.*;
import java.util.*;

class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = Integer.parseInt(sc.next());
    int[] v = new int[N];
    for (int i = 0; i < N; i++) {
      v[i] = Integer.parseInt(sc.next());
    }
    
    Arrays.sort(v);
    
    double sum = v[0];
    for (int i = 1; i < N; i++) {
      sum = (sum + v[i]) / 2.0;
    }
    
    System.out.println(sum);
  }
}

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

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

using namespace std;

typedef long long llong;

const int MXN = (int)2e5 + 7;
const int MOD = (int)1e9;
const llong INF = 2e18 + 7;

int n, k, s;

int main()
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  #ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
  #endif
  cin >> n >> k >> s;
  for(int i = 1; i <= k; i++){
    cout << s << ' ';
  }
  for(int i = 1; i <= n - k; i++){
    if(s != MOD){
      cout << MOD << ' ';
    }else{
      cout << 1 << ' ';
    }
  }
  return 0;
}


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

int main(){
    int n,ans=0,answer=0;
    cin >> n;
    rep(i,n){
        if(i%2 == 1){ 
        rep(j,i) {if(i%j == 0) ans++;}}
        if(ans==8) answer++;
        ans=0;
    }
    cout << answer << endl;
}

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

bool isPalli(string s){
	string t(s.rbegin(),s.rend());
	return s == t;
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	string s;
	cin>>s;
	int n =s.length();
	if( isPalli(s) && isPalli( s.substr( 0 , (n-1) / 2 ) ) && isPalli( s.substr((n+3)/2-1, (n-1)/2)) ){
		cout<<"Yes\n";
	}else{
		cout<<"No\n";
	}
}

Measured memory_bytes: 256
import collections
N,K = map(int,input().split())
A = list(map(int,input().split()))
ans = 0
tmp = len(list(set(A)))
li = collections.Counter(A)
value,counts = zip(*li.most_common())
for i in range(K,tmp,1):
    ans += counts[i]
print(ans)

Measured memory_bytes: 59576
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n,m;
  cin>>n>>m;
  for(int i=0;i<n;i++){
    if(i)cout<<" ";
    if(i<=(n)/2)cout<<0;
    else cout<<m;
  }
  cout<<endl;
  return 0;
}

Measured memory_bytes: 3116
import java.util.Scanner;
import java.lang.Math;

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

        while(true){
        int n = stdIn.nextInt();
        if(n==0) break;
        int a[] = new int[n];
        double sum = 0;
        double sum1 = 0;
        double t = 0;

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

        for (int j = 0; j < n; j++) {
            sum1 += (double) (a[j] - sum / n) * (a[j] - sum / n);
        }

        t = Math.sqrt((double) sum1 / n);

        System.out.println(t);
    }
    }
}


Measured memory_bytes: 31516
#include <algorithm>
#include <bitset>
#include <tuple>
#include <cstdint>
#include <cstdio>
#include <cctype>
#include <assert.h>
#include <stdlib.h>
#include <stdio.h>
#include <cassert>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <ctime>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <limits>
#include <map>
#include <memory>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
#include <math.h>

// ===============================================================

using namespace std;
using ll = long long;
using vl = vector<long long>;
using vll = vector<vector<long long>>;
using vs = vector<string>;
using vc = vector<char>;
using vcc = vector<vector<char>>;
using vm = vector<short>;
using vmm = vector<vector<short>>;
using pii = pair<int, int>;
using psi = pair<string, int>;
using ld = long double;
using ull = unsigned long long;
using ld = long double;

// ========================================================================



ll gcd(ll a, ll b)
{
	if (a % b == 0)
	{
		return(b);
	}
	else
	{
		return(gcd(b, a % b));
	}
}
//最大公約数
ll lcm(ll a, ll b)
{
	return a * b / gcd(a, b);
}
//最小公倍数
ll box(double a)
{
	ll b = a;
	return b;
}
//切り捨て
ll fff(double a)
{
	ll b = a + 0.5;
	return b;
}
//四捨五入
ll sum(ll n) {
	return (1 + n) * n / 2;
}
//1から整数nまでの合計を出す
ll mch(ll n) {
	if (n == 1) return 1;
	else return n * mch(n - 1);
}
//1から整数nまでの階乗を出す(INFで割っていない)
bool prime(ll a)//素数判定、primeならtrue,違うならfalse
{
	if (a < 2) return false;
	else if (a == 2) return true;
	else if (a % 2 == 0) return false;
	double m = sqrt(a);
	for (int i = 3; i <= m; i += 2)
	{
		if (a % i == 0)
		{
			return false;
		}
	}

	// 素数である
	return true;
}
//素数判定
ll modpow(ll a, ll n, ll mod) {
	ll hi = 1;
	while (n > 0) {
		if (n & 1) hi = hi * a % mod;
		a = a * a % mod;
		n >>= 1;
	}
	return hi;
}
//いろいろやります（ただの前座）
ll mg(ll a, ll mod) {
	return modpow(a, mod - 2, mod);
}
//割り算の10^9+7等対策で逆元を出します 
template<class T> inline bool chmin(T& a, T b) {
	if (a > b) {
		a = b;
		return true;
	}
	return false;
}
template<class T> inline bool chmax(T& a, T b) {
	if (a < b) {
		a = b;
		return true;
	}
	return false;
}
ll cnt = 0;
//#define int long long;


// ========================================================================


/*signed*/int main() {
	ll n; cin >> n;
	vl a(n);
	vl b(n);
	for (int i = 0; i < n; i++) cin >> a[i];
	for (int i = 0; i < n; i++) cin >> b[i];
	ll ans = 0;
	if (n != 1) {
		for (int i = 0; i < n; i++) {
			if (i == 0) {
				for (int j = 0; j < n; j++) {
					if (i > j) ans += a[j];
					else ans += b[j];
				}
				ans += a[i];
			}
			else {
				for (int j = 0; j < n; j++) {
					if (i > j) cnt += a[j];
					else cnt += b[j];
				}
				cnt += a[i];
				ans = max(cnt, ans);
				cnt = 0;
			}
		}
		cout << ans << endl;
	}
	else {
		cout << a[0] + b[0] << endl;
	}
	
	return 0;
}

Measured memory_bytes: 3732
/*{{{*/
#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstring>
#include <unordered_map>
#include <unordered_set>
#include <cassert>
using namespace std;
typedef pair<int, int> PP;
typedef long long LL;
#define pb push_back
#define fr first
#define sc second
#define bitcnt __builtin_popcount
#define all(x) x.begin(), x.end()
inline int ri() {int x; scanf("%d", &x); return x;}
#define rep2(i, n, ...) for (int i = 0; i < (n); i ++) 
#define rep3(i, a, b, ...) for (int i = (a); i < (b); i ++)
#define GET_MACRO(_1, _2, _3, NAME, ...) NAME
#define rep(...) GET_MACRO(__VA_ARGS__, rep3, rep2)(__VA_ARGS__)
#define drep2(i, n, ...) for (int i = (n) - 1; i >= 0; i --)
#define drep3(i, a, b) for (int i = (a) - 1; i >= (b); i --)
#define drep(...) GET_MACRO(__VA_ARGS__, drep3, drep2)(__VA_ARGS__)
template<typename T>inline bool smax(T&a, T b){if(a<b){a=b;return true;}return false;} 
template<typename T>inline bool smin(T&a, T b){if(a>b){a=b;return true;}return false;} 
/*}}}*/


vector<LL> v;
map<LL, LL> p;
LL res[200000];
void f(LL x, LL d) {
  auto t = lower_bound(v.begin(), v.end(), x);
  if (x == 0) {
    return;
  }
  if (t == v.begin()) {
    res[x] += d;
  }
  else {
    t --;
    p[*t] += x / (*t) * d;
    f(x % (*t), d);
  }
}
int main() {
  #ifdef _TEST_
  freopen("input.txt", "r", stdin);
  //freopen("out.txt", "w", stdout);
  #endif
  int n, m;
  cin >> n >> m;
  v.push_back(n);
  rep(i, m) {
    LL x; cin >> x;
    while (!v.empty() && v.back() >= x) v.pop_back();
    v.push_back(x);
  }
  
  //for (int x : v) cout << x << endl;
  //cout << "--\n";
  p[v.back()] = 1;
  drep(i, v.size()) {
    f(v[i], p[v[i]]);
  }

  drep(i, n) 
    res[i] += res[i + 1];
  rep(i, 1, n + 1) 
    cout << res[i] << '\n';
  return 0;
}


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

typedef long long ll;

int main()
{
    

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    ll n;
    cin>>n;
    double x = 2*(3.1415926535897932)*n;
    cout<<x<<endl;
    
    return 0;
}

Measured memory_bytes: 3800
#include<stdio.h>

int main(void){
    int N,M;
    scanf("%d %d",&N,&M);
    int A[N][M];
    int K=0;
    //初期化
    for(int i=0;i<N;i++){
        for(int j=0;j<M;j++){
            A[i][j]=0;
        }
    }

    for(int i=0;i<N;i++){
        scanf("%d",&K);
        int temp=0;
        for(int j=0;j<K;j++){
            scanf("%d",&temp);
            A[i][temp-1] = 1;
        }
    }
    int count =0;

    for(int i=0;i<M;i++){
        int sum=0;
        for(int j=0;j<N;j++){
            sum += A[j][i];
        }
        if(sum == N){
            count ++;
        }
    }
    printf("%d",count);
    return 0;
}

Measured memory_bytes: 128
n = int(input())
s = input()
t = input()

idx = 0
a = []
b = []

for i in range(n):
    if(s[n-i-1] == t[i]):
        idx = i+1
    else:
        break

for i in range(1, n+1):
    for j in range(1, i):
        a += s[n-i+j]
        b += t[j-1]
    if(a == b): idx = i-1
    a = []
    b = []

if(s == t):
    print(n)
else:
    print(n*2-idx)


Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
typedef vector<int> VI;
typedef vector<VI> VVI;
const ll MOD = 1000000007;
const ll INF = 2147483647;
const ll LLINF = 9223372036854775807;
#define REP(i, n) for(int i = 0; i < n; i++)
#define ALL(v) v.begin(), v.end()

char m3[3][4] = {
	"aab",
	"c.b",
	"cdd"
};

char m4[4][5] = {
	"aabc",
	"ddbc",
	"bcaa",
	"bcdd"
};

char m5[5][6] = {
	"aabbc",
	"d.eec",
	"dj..f",
	"gj..f",
	"ghhii"
};

char m6[6][7] = {
	"aab..f",
	"c.b..f",
	"cddee.",
	".ffaab",
	"e..c.b",
	"e..cdd",
};

char m7[7][8] = {
	"aa.bb.c",
	".ii..jc",
	"h..mmj.",
	"h.n...d",
	".ln...d",
	"gl..kk.",
	"g.ff.ee"
};

int main() {
	int n; cin >> n;
	vector<vector<char>> ans(n, vector<char>(n,'.'));
	if (n <= 2) {
		cout << -1;
		return 0;
	}
	if (n == 3) {
		REP(i, 3)REP(j, 3){
			ans[i][j] = m3[i][j];
		}
	}
	if (n >= 4) {
		REP(i, (n / 4) - 1) {
			REP(j, 4)REP(k, 4)
				ans[j + (i * 4)][k + (i * 4)] = m4[j][k];
		}
		if (n % 4 == 0) {
			REP(i, 4)REP(j, 4)
				ans[i + n - (n % 4) - 4][j + n - (n % 4) - 4] = m4[i][j];
		}
		if (n % 4 == 1) {
			REP(i, 5)REP(j, 5)
				ans[i + n - (n % 4) - 4][j + n - (n % 4) - 4] = m5[i][j];
		}
		if (n % 4 == 2) {
			REP(i, 6)REP(j, 6)
				ans[i + n - (n % 4) - 4][j + n - (n % 4) - 4] = m6[i][j];
		}
		if (n % 4 == 3) {
			REP(i, 7)REP(j, 7)
				ans[i + n - (n % 4) - 4][j + n - (n % 4) - 4] = m7[i][j];
		}
	}
	REP(i, n) {
		REP(j, n)
			cout << ans[i][j];
		cout << endl;
	}
}

Measured memory_bytes: 2176
# 写経AC

N = int(input())
A = tuple(map(int, input().split()))

# P,Q,R,S に対応
score = [A[0], A[1], A[2], sum(A[3:])]

ans = float("inf")
left, right = 1, 3


""" 尺取り法 """
# 真ん中
for mid in range(2, N-1):
    # 左側
    while left < mid and abs(score[0] - score[1]) > abs((score[0] + A[left]) - (score[1] - A[left])):
        score[0] += A[left]
        score[1] -= A[left]
        left += 1
    # 右側
    while right < N and abs(score[2] - score[3]) > abs((score[2] + A[right]) - (score[3] - A[right])):
        score[2] += A[right]
        score[3] -= A[right]
        right += 1

    ans = min(ans, max(score) - min(score))

    score[1] += A[mid]
    score[2] -= A[mid]

print(ans)

Measured memory_bytes: 25196
#include <iostream>
#include <map>

using namespace std;

int main() {
  int n;
  cin >> n;
  map<int, int> freq;
  for (int i = 0; i < n; i ++) {
    int num;
    cin >> num;
    if (freq.count(num) == 0) {
      freq[num] = 0;
    }
    freq[num]++;
  }
  cout << freq.size() << endl;
}


Measured memory_bytes: 256
K, A, B = map(int, input().split())

if A>= B:
    print(K + 1)
elif A <= B <= A+2:
    print(K + 1)
else:
    to_A = A - 1
    last_K = K - to_A
    if last_K <= 0:
        print(K)
    else:
        if last_K % 2 == 0:
            print(A + (B-A) * last_K // 2)
        else:
            print(A + (B - A) * (last_K // 2) + 1)


Measured memory_bytes: 3060
#include <iostream>
#include <iomanip>
#include <utility>
#include <cmath>
#include <random>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <string>
#include <algorithm>
using namespace std;

#define rep(i,n) for(int i = 0; i<n; ++i)
const int INF = 100100100;
const int MOD = (int)1e9 + 7;
typedef long long ll;

int main(){
    int n; cin >> n;
    cout << ((n%2 == 0)? n:2*n) << endl;
}


Measured memory_bytes: 256