akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
#define f(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) f(i,0,n)
#define fd(i,a,b) for(i=a;i>=b;i--)
#define pb push_back
#define mp make_pair
#define vi vector< int >
#define vl vector< ll >
#define ss second
#define ff first
#define ll long long
#define ull unsigned long long
#define pii pair< int,int >
#define pll pair< ll,ll >
#define sz(a) a.size()
#define inf (1000*1000*1000+5)
#define all(a) a.begin(),a.end()
#define tri pair<int,pii>
#define vii vector<pii>
#define vll vector<pll>
#define viii vector<tri>
#define pi acosl(-1)
#define sqr(x) ((x)*(x))
#define mod (1000*1000*1000+7)
#define pdd pair<double,double>
#define MEMS(x) memset(x,-1,sizeof(x))
#define MEM(x) memset(x,0,sizeof(x))
template <typename T>
string NumberToString(T pNumber)
{
     ostringstream oOStrStream;
     oOStrStream << pNumber;
     return oOStrStream.str();
}
ll StringToNumber(string s)
{
    stringstream geek(s);
    ll x=0;
    geek>>x;
    return x;
}
ll modPow(ll x,ll n,ll m)
{
    if(n==0)
    return 1%m;
    ull u = modPow(x,n/2,m);
    u=u*u%m;
    if(n%2==1)
    u=u*x%m;
    return u;
}
ll gcd(ll a,ll b)
{
    if(b==0)
    return a;
    return gcd(b,a%b);
}
ll seive[1000000];
void seiveForm()
{
    ll i,j;
    seive[0]=seive[1]=1;
    f(i,2,100000)
    {
        if(seive[i]==0)
            for(j=i*i;j<1000000;j+=i)
                seive[j]=1;
    }
}
bool isPerfectSquare(ll num)
{
    double n = sqrt(num);
    return n==(ll)n?true:false;
}
ll countSetbits(ll num)
{
    ull temp=0;
    while(num){
        num=num&(num-1);
        temp++;
    }
    return temp;
}
bool isPowerOfTwo(ll n)
{
   if(n==0)
   return false;
   return (ceil(log2(n)) == floor(log2(n)));
}
ll power(ll x, ll y)
{
    ll res = 1;
    while (y > 0)
    {
        if (y & 1)
            res = res*x;
        y = y>>1;
        x = x*x;
    }
    return res;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll i,temp=0;
    string s,t;
    cin>>s>>t;
    rep(i,s.length())
    {
        if(s[i]!=t[i])
            temp++;
    }
    cout<<temp<<endl;
    return 0;
}


Measured memory_bytes: 3900
use proconio::input;

fn main() {
    input! {
        n: i64,
    }

    let mut res = 0;
    for i in 1..=n {
        for j in 1..=n {
            if i * j >= n {
                break;
            }
            res += 1;
        }
    }

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


Measured memory_bytes: 2116
#include<bits/stdc++.h>
#define int long long
#define for0(i, n) for(int i = 0; i < (n); i++)
#define mp make_pair
using namespace std;
stack<int>st;
string s;
vector<pair<int, int>>ans;
signed main() {
	cin >> s;
	for0(i, s.size()) {
		if (s[i] == '\\') st.push(i);
		else if (s[i] == '/' && st.size()) {
			int p = st.top(); st.pop();
			int t = i - p;
			while (ans.size() && p < ans.back().first) {
				t += ans.back().second;
				ans.pop_back();
			}
			ans.push_back(mp(p, t));
		}
	}
	int sum = 0; for (pair<int, int> p : ans)sum += p.second;
	cout << sum << endl << ans.size();
	for (pair<int, int> p : ans)cout << ' ' << p.second; cout << endl;
}


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

using namespace std;

#define ll long long
ll input(){
	ll x=0,f=0;char ch=getchar();
	while(ch<'0'||ch>'9') f|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
	return f? -x:x;
}

#define pb push_back

const int N=1e5+7,mod=1e9+7;

vector <int> G[N];
ll dp[N][2];

void dfs(int u,int fa){
	dp[u][0]=dp[u][1]=1;
	for(auto v:G[u]){
		if(v==fa) continue;
		dfs(v,u);
		dp[u][0]*=(dp[v][0]+dp[v][1]),dp[u][0]%=mod;
		dp[u][1]*=dp[v][0],dp[u][1]%=mod;
	}
}

int main(){
	int n=input();
	for(int i=1;i<n;i++){
		int u=input(),v=input();
		G[u].pb(v),G[v].pb(u);
	}

	dfs(1,0);

	printf("%lld\n",(dp[1][0]+dp[1][1])%mod);
}

Measured memory_bytes: 14208
def main():
    import sys
    from collections import deque
    input = sys.stdin.readline
    H, W = [int(x) for x in input().strip().split()]
    M = [''] * H
    f = False
    for h in range(H):
        M[h] = list(input().strip())
        if '#' in M[h]:
            f = True
    s = deque([(0, 0)])
    if not f:
        print('Impossible')
        return
    if M[0][0] == '.':
        print('Impossible')
        return
    M[0][0] = '.'
    while s:
        (h, w) = s.popleft()
        if h + 1 < H:
            if M[h+1][w] == '#':
                M[h+1][w] = '.'
                s.append((h+1, w))
                continue
        if w + 1 < W:
            if M[h][w+1] == '#':
                M[h][w+1] = '.'
                s.append((h, w+1))

    for h in range(H):
        if '#' in M[h]:
            print('Impossible')
            return
    else:
        print('Possible')
        return

if __name__ == '__main__':
    main()

Measured memory_bytes: 3316
X, N = map(int, input().split())
p = sorted(list(map(int, input().split())))

if not X in p:
    print(X)
else:
    for i in range(1, 101):
        if not X - i in p:
            print(X - i)
            exit()
        elif not X + i in p:
            print(X + i)
            exit()

Measured memory_bytes: 9184
#include<iostream>
using namespace std;
int main() {
	int m, f, r;
	cin >> m >> f >> r;
	while (m != -1 || f != -1 || r != -1) {
		if (m == -1 || f == -1) cout << "F" << endl;
		else if (m + f >= 80) cout << "A" << endl;
		else if (m + f >= 65) cout << "B" << endl;
		else if (m + f >= 50) cout << "C" << endl;
		else if (m + f >= 30)
			if (r >= 50) cout << "C" << endl;
			else cout << "D" << endl;
		else cout << "F" << endl;

		cin >> m >> f >> r;
	}
	return 0;
}


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

int main() {
  int N;
  int c=0;
  cin >> N;
  for (int i=0; i<N; i++){
    int A;
    int b=0;
    cin >> A;
    while (A%2==0){
     b++;
      A=A/2;
    }
    if (i==0) {
      c=b;
    }
    if (b<c){
     c=b;
    }
    else
      c=c;
    
  }
  cout << c << endl;
    
    
}
   

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

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

  int n;cin>>n;
  vector<int> x(n);
  for(int i=0;i<n;i++)cin>>x[i];
  int ans=pow(10,9);
  for(int i=1;i<=100;i++){
    int t=0;
    for(int j=0;j<n;j++){
      t += pow(x[j]-i, 2);
    }
    ans=min(ans,t);
  }
  cout<<ans<<endl;

  return 0;
}


Measured memory_bytes: 256
#include <iostream>

using namespace std;

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

 	int c = (N + 1) / 2;
 	if (c >= K) {
 		cout << "YES" << endl;
 	} else {
 		cout << "NO" << endl; 		
 	}



	return 0;
}

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

int main(){
    int A, B;
    cin >> A >> B;
    if((A == 1 && B == 2) || (A == 2 && B == 1)) cout << "3" << endl;
    else if((A == 2 && B == 3) || (A == 3 && B == 2)) cout << "1" << endl;
    else if((A == 1 && B == 3) || (A == 3 && B == 1)) cout << "2" << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define SORT(a) sort(a.begin(), a.end())
#define RSORT(a) sort(a.rbegin(), a.rend())
#define REP(i, n) for (long long i = 0; i < n; i++)
#define RREP(i, n) for (long long i = n - 1; 0 <= i; i--)
#define FOR(i, start, end) for (long long i = start; i < end; i++)
#define RFOR(i, start, end) for (long long i = start - 1; 0 <= i; i--)
#define ALL(a) a.begin(), a.end()
#define MOD(a) a %= 1'000'000'007
using ll = long long;
using namespace std;
const int INF32       = 1'050'000'000;
const long long INF64 = 4'000'000'000'000'000'000;
const int MOD7        = 1'000'000'007;
const int MOD9        = 1'000'000'009;
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;
}
void print() { std::cout << '\n'; }
template <class H, class... T> void print(H &&head, T &&... args) {
    std::cout << head;
    sizeof...(args) == 0 ? std::cout << "" : std::cout << ' ';
    print(std::forward<T>(args)...);
}
template <class T> void print(std::vector<T> &v) {
    for (int i = 0; i < v.size(); i++) {
        std::cout << v[i];
        i == v.size() - 1 ? std::cout << '\n' : std::cout << ' ';
    }
}
template <class T> void print(std::vector<std::vector<T>> &v) {
    for (int i = 0; i < v.size(); i++) {
        for (int j = 0; j < v[i].size(); j++) {
            std::cout << v[i][j];
            j == v[i].size() - 1 ? std::cout << '\n' : std::cout << ' ';
        }
    }
}

// 配列を圧縮する。first に値、second に個数
template <class T> vector<pair<T, int>> run_length(vector<T> &v) {
    vector<pair<T, int>> ans;
    ans.emplace_back(v[0], 1);
    T now   = v[0];
    int cnt = 0;
    for (int i = 1; i < v.size(); i++) {
        if (v[i] == now) {
            ans[cnt].second++;
        } else {
            ans.emplace_back(v[i], 1);
            now = v[i];
            cnt++;
        }
    }
    return ans;
}

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

    int N;
    cin >> N;
    vector<int> a(N);
    for (auto &&i : a) {
        cin >> i;
    }

    SORT(a);
    auto les = run_length(a);
    ll ans   = 0;
    vector<int> v;
    vector<int> vv;
    for (auto &&i : les) {
        if (2 <= i.second) {
            v.emplace_back(i.first);
        }
        if (4 <= i.second) {
            vv.emplace_back(i.first);
        }
    }
    RSORT(v);
    RSORT(vv);
    if (2 <= v.size()) {
        ans = (ll)v[0] * v[1];
    }
    if (!vv.empty()) {
        chmax(ans, (ll)vv[0] * vv[0]);
    }
    print(ans);

    return 0;
}

Measured memory_bytes: 1784
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(input())
def inpl(): return list(map(int, input().split()))
def inpl_s(): return list(input().split())

N = inp()
aa = inpl()
ans = 0
for a in aa:
	while a%2 == 0:
		a //= 2
		ans += 1

print(ans)


Measured memory_bytes: 5364
n = int(input())
a = []
for _ in range(n):
    a.append(int(input()))
a.sort()
for i in a:
    if i%10!=0:
        non10 = i
        break
else:
    non10 = None
total = sum(a)
if total%10!=0:
    print(total)
elif non10 is None:
    print(0)
else:
    print(total-non10)

Measured memory_bytes: 3060
#[test]
fn test_solve() {
    assert_eq!(solve("2 5\n1 WA\n1 AC\n2 WA\n2 AC\n2 WA\n"), "2 2\n");
    assert_eq!(solve("100000 3\n7777 AC\n7777 AC\n7777 AC\n"), "1 0\n");
    assert_eq!(solve("6 0\n"), "0 0\n");
}

fn solve(src: &str) -> String {
    let mut sc = Scanner::from_str(src);

    let n: usize = sc.read();
    let m: usize = sc.read();

    let mut ac = 0;
    let mut aced = vec![false; n];
    let mut pe = vec![0; n];

    for _ in 0..m {
        let p: usize = sc.read();
        let s = sc.get();
        if s == "AC" {
            if !aced[p-1] {
                ac += 1;
                aced[p-1] = true;
            }
        } else {
            if !aced[p-1] {
                pe[p-1] += 1;
            }
        }
    }
    for i in 0..n {
        if !aced[i] {
            pe[i] = 0;
        }
    }

    format!("{} {}\n", ac, pe.iter().sum::<usize>())
}

fn main() {
    let mut buf = String::new();
    use std::io;
    use std::io::{Read, Write};
    io::stdin().read_to_string(&mut buf).unwrap();
    io::stdout().write_all(solve(&buf).as_bytes()).unwrap();
}

struct Scanner<'a>(std::str::SplitWhitespace<'a>);
impl<'a> Scanner<'a> {
    fn from_str(src: &str) -> Scanner {
        Scanner(src.split_whitespace())
    }
    fn get(&mut self) -> &str {
        self.0.next().unwrap()
    }
    fn read<T: std::str::FromStr>(&mut self) -> T {
        self.get().parse().ok().unwrap()
    }
    fn chars(&mut self) -> Vec<char> {
        self.get().chars().collect()
    }
}

Measured memory_bytes: 6396
let ($) f g = fun x -> g (f x)
let split_string ?(pattern="") = Str.split @@ Str.regexp pattern
let n = Scanf.sscanf (read_line ()) "%d" @@ fun n -> n
let a = read_line () |> split_string ~pattern:" " |> List.map int_of_string

let all_xor = List.fold_left (lxor) 0 a

let () = 
  a 
  |> List.map (((lxor) all_xor) $ string_of_int)
  |> String.concat " "
  |> print_endline

Measured memory_bytes: 32892
s = str(input())
for i in range(len(s)):
  if i%2 == 0:
    if s[i] == 'R' or s[i] == 'U' or s[i] == 'D':
      continue
    else:
      print('No')
      exit()
  else:
    if s[i] == 'L' or s[i] == 'U' or s[i] == 'D':
      continue
    else:
      print('No')
      exit()
else:
  print('Yes')
    

Measured memory_bytes: 3060
N, x = map(int, input().split())
a = [int(i) for i in input().split()]
ans = 0
for i in range(N-1):
	if a[i] + a[i+1] > x:
		d = a[i] + a[i+1] - x
		if d <= a[i+1]:
			a[i+1] -= d
			ans += d
		else:
			a[i] -= d - a[i+1]
			a[i+1] = 0
			ans += d
print(ans)

Measured memory_bytes: 14152
package main

import (
    "fmt"
)

func main() {
    var r, D, x2000 int 
    fmt.Scanln(&r, &D, &x2000)

    x := make([]int, 11) 
    x[0] = x2000

    for i := 1; i <= 10; i++ {
        x[i] = r*x[i-1] - D 
        fmt.Println(x[i])
    }   
}

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

#define INF ((int)1e9)

struct Edge {
  int to, cost;
  Edge(int t, int c) : to(t), cost(c) {}
};

typedef pair<int, int> Pii;
typedef pair<int, Pii> Piii; // cost, cnum, node

vector<Edge> G[100];
int memo[100][10];

int dijkstra(int src, int dst, int cnum) {
  
  fill(memo[0], memo[0]+1000, INF);
  
  priority_queue<Piii> pq;
  memo[src][cnum] = 0;
  pq.push(Piii(0, Pii(-cnum, src)));
  while(!pq.empty()) {
    int cost = pq.top().first;
    int cn = -pq.top().second.first;
    int now = pq.top().second.second; pq.pop();
    
    for(int i=0; i<G[now].size(); i++) {
      int next = G[now][i].to;
      int add_c = G[now][i].cost;
      if(memo[next][cn] > cost + add_c) {
	pq.push(Piii(cost+add_c, Pii(-cn, next)));
	memo[next][cn] = cost + add_c;
      }
      if(cn-1<0) continue;
      add_c /= 2;
      if(memo[next][cn-1] > cost + add_c) {
	pq.push(Piii(cost+add_c, Pii(-(cn-1), next)));
	memo[next][cn-1] = cost + add_c;
      }
    }
  }
  
  return *min_element(memo[dst], memo[dst]+10);
}

int main() {
  int C, N, M, S, D;
  while(cin >> C >> N >> M >> S >> D && (N|M)) {
    for(int i=0; i<N; i++) {
      G[i].clear();
    }
    for(int i=0; i<M; i++) {
      int a, b, c; cin >> a >> b >> c; a--, b--;
      G[a].push_back(Edge(b, c));
      G[b].push_back(Edge(a, c));
    }
    
    S --, D --;
    cout << dijkstra(S, D, C) << endl;
  }
  
  return 0;
}

Measured memory_bytes: 1232
S=input()
num=1
ans="No"

while True:
  word=S[0]
  if num%2==1 :
    if  (word=="R") or (word=="U") or (word=="D") :
      if len(S)==1 :
        ans="Yes"
        break
      S=S[1:]
      num+=1
      continue
  else:
    if (word=="L") or (word=="U") or (word=="D") :
      if len(S)==1 :
        ans="Yes"
        break
      S=S[1:]
      num+=1
      continue
  break
      
print(ans)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
/*
真ん中に極端なのおくのかな
68123
38162
小さいのを真ん中におくか、大きいのを真ん中におくかでわかれる？

31826=2,7,6,4=19
28163=6,7,5,3=21
31524

1234
 3142=232 
 2413=232

11224
 14122=331
 24121=2311
*/
int main(){
  ll N,ans=0; cin>>N;
  vector<ll> A(N+1,0),H(200000,0),L(200000,0);
  for(ll i=1; i<=N; i++) cin>>A[i];
  sort(A.begin(), A.end());
  //小さいの中心
  for(ll i=1; i<=N; i++){
    ll n=i/2;
    //小さくて左
    if(n%2==0 && i%2==0) L[100000-n]=A[n];//4
    //小さくて右
    else if(n%2==0 && i%2==1) L[100000+n]=A[n+1];//1,5
    //大きくて左
    else if(n%2==1 && i%2==0) L[100000-n]=A[N+1-n];//2
    //大きくて右
    else if(n%2==1 && i%2==1) L[100000+n]=A[N-n];//3
  }
  //大きいの中心
  for(ll i=1; i<=N; i++){
    ll n=i/2;
    //大左
    if(n%2==0 && i%2==0) H[100000-n]=A[N+1-n];//4
    //大右
    else if(n%2==0 && i%2==1) H[100000+n]=A[N-n];//1,5
    //小左
    else if(n%2==1 && i%2==0) H[100000-n]=A[n];//2
    //小右
    else if(n%2==1 && i%2==1) H[100000+n]=A[n+1];//3
  }
  ll s=100000-N/2-10, g=100000+N/2+10, tmp=0;
  for(ll i=s; i<=g; i++){
    if(L[i]==0 || L[i+1]==0) continue;
    tmp+=abs(L[i+1]-L[i]);
  }
  ans=max(tmp,ans);
  tmp=0;
  for(ll i=s; i<=g; i++){
    if(H[i]==0 || H[i+1]==0) continue;
    tmp+=abs(H[i+1]-H[i]);
  }
  ans=max(tmp,ans);
  cout<<ans<<endl;
}

Measured memory_bytes: 4224
fun main() {
    val k = readLine()?.toInt() ?: return
    if (k % 2 == 0 || k %5 == 0) {
        println("-1")
        return
    }
    val kk = if (k % 7 == 0) k / 7 * 9 else k * 9
    if (kk == 1) {
        println("1")
        return
    }
    var r = 10L
    1.until(kk).forEach {
        r %= kk
        if (r == 1L) {
            println(it.toString())
            return
        }
        r *= 10
    }
}


Measured memory_bytes: 34868
#include<bits/stdc++.h>
#define ll long long int
#define FOR(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++)
#define REP(i,n) FOR(i,0,n)
#define REP1(i,n) FOR(i,1,n)
using namespace std;

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

  if (a < b && b < c)
    cout << "Yes" << endl;
  else
    cout << "No" << endl;

  return 0;
}

Measured memory_bytes: 3072
#include <bits/stdc++.h>
using namespace std;
const double pi = acos(-1);
const double EPS = 1e-7;
const long long mod = 1000000007 ;
#define Hello ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define ll long long
#define ld long double
#define X real()
#define Y imag()
#define cross(a,b) (conj(a)*(b)).imag()
#define dot(a,b) (conj(a)*(b)).real()
#define dist(a,b) ( pow(a.X - b.X, 2) + pow( a.Y - b.Y, 2 ) )
typedef tuple <int, int, int> line;
typedef complex <double> point;
typedef vector <point> polygon;
int n, arr[100000];
ll total, dp[100000];
///dp[idx] = min( abs(arr[i1] - arr[idx]), abs(arr[i2] - arr[idx]) );
ll solve(int idx)
{
    if( idx == n - 1 )
        return 0;
    int i1 = min( idx + 1, n - 1 );
    int i2 = min( idx + 2, n - 1 );
    if( dp[idx] != -1 )
        return dp[ idx ];
    dp[idx] = min(abs(arr[i1] - arr[idx]) + solve(i1), abs(arr[i2] - arr[idx]) + solve(i2));
    return dp[idx];
}
int main()
{
    Hello
    memset(dp, -1, sizeof dp);
    cin >> n;
    for(int i = 0; i < n; i++)
        cin >> arr[i];
    //solve(0);
    cout << solve(0);
    return 0;
}


Measured memory_bytes: 3840
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define all(x) x.begin(),x.end()
#define pll  pair <long long,long long>
#define ss second
#define ff first
#define inf 9223372036854775807
#define maa 1000000007
#define ld long double
#define fast  ios_base::sync_with_stdio(false);cin.tie(NULL);
#define bug(x) cout << #x <<": " << x << '\n';
const ll N=200001 ;
vector<ll>tree[5*N] ;
vector<ll>vv ;
vector<ll>merge(vector<ll>&a,vector<ll>&b)
{
    vector<ll>lol ;
    ll n1=a.size() ;
    ll n2=b.size() ;
    ll i=0,j=0 ;
    while(i<n1&&j<n2)
    {
        if(a[i]<b[j])
        {
            lol.pb(a[i]) ;
            i++ ;
        }
        else
        {
            lol.pb(b[j]) ;
            j++ ;
        }
    }
    while(i<n1)
    {
      lol.pb(a[i]) ;
            i++ ;
    }
    while(j<n2)
    {
        lol.pb(b[j]) ;
        j++ ;
    }
    return lol ;
}
void build_tree( ll cur , ll l , ll r )
{
     if( l==r )
     {
            if(tree[cur].size()==0)
            tree[cur].push_back( vv[ l ] );
            else
                tree[cur][0]=vv[l] ;
            return ;
     }
     ll mid = l+(r-l)/2;
     build_tree(2*cur+1 , l , mid ); // Build left tree
     build_tree(2*cur+2 , mid+1 , r ); // Build right tree
     tree[cur] = merge( tree[2*cur+1] , tree[2*cur+2] ); //Merging the two sorted arrays
}
ll query( ll cur, ll l, ll r, ll x, ll y, ll k)
{
       if( r < x || l > y )
      {
               return 0; //out of range
      }
      if( x<=l && r<=y )
      {
              //Binary search over the current sorted vector to find elements smaller than K

              return upper_bound(tree[cur].begin(),tree[cur].end(),k)-tree[cur].begin();
      }
      ll mid=l+(r-l)/2;
     return query(2*cur+1,l,mid,x,y,k)+query(2*cur+2,mid+1,r,x,y,k);
}
int main()
{
   fast ;
   ll n,k ;
   cin>>n>>k ;
   vector<ll>a(n+1,0) ;
   for(ll i=1;i<=n;i++)
   {
       cin>>a[i] ;
       a[i]-=k ;

   }
   for(ll i=1;i<=n;i++)
   {
       a[i]+=a[i-1] ;
   }
   ll ans=0 ;
   for(ll i=0;i<=n;i++)
   {
       vv.pb(a[i]) ;
   }
   build_tree(0,0,n) ;
   for(ll i=0;i<=n;i++)
   {
      // cout<<i<<" "<<query(0,0,n,0,i-1,a[i])<<endl;
       ans+=query(0,0,n,0,i-1,a[i]);


   }
   cout<<ans  ;
}


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

int main(){
	
	while(1){
		int n,m;
		cin>>n>>m;
		
		if(n==0&&m==0) break;
	
	
	    int vv[100];
	    for(int i=1;i<=m;i++){
			vv[i]=0;
	    }
		
		int d[100],v[100];
		for(int i=0;i<n;i++){
			cin>>d[i]>>v[i];
			
			if(vv[d[i]]<v[i]){
				vv[d[i]]=v[i];
			}	
		}
		
		int ans=0;
		for(int i=1;i<=m;i++) ans+=vv[i];
		
		
		cout<<ans<<endl;
	}
	

	return 0;
}


Measured memory_bytes: 3104
#include <bits/stdc++.h>
#include <math.h>
#define REP(i, n) for(int i = 0; i < (n); i++)
#define ALL(v) (v).begin(), (v).end()
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const int INF = 1001001001;
const int mINF = -1001001001;
// << fixed << setprecision(0) <<
// sort(ALL(),greater<int>());

int main() {
ll n;
cin >> n;
ll ans=(n-1)*n/2;
cout  << ans << endl;
return 0;
}


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

int main(){
  ll x, k, d;
  cin >> x >> k >> d;
  if (x >= 0){
  ll pos_ans = x % d;
  ll neg_ans = abs(pos_ans - d);
  ll pos_ans_move_cnt = x / d;
  ll neg_ans_move_cnt = x / d + 1;
  if (k <= max(pos_ans_move_cnt, neg_ans_move_cnt)) cout << abs(x - k * d) << endl;
  else{
  if ((x / d) % 2 == k % 2) cout << pos_ans << endl;
  else cout << neg_ans << endl;
  }
  }else{
  ll pos_ans = abs(x) % d;
  ll neg_ans = abs(pos_ans - d);
  ll pos_ans_move_cnt = abs(x) / d + 1;
  ll neg_ans_move_cnt = abs(x) / d;
  if (k <= max(pos_ans_move_cnt, neg_ans_move_cnt)) cout << abs(x + k * d) << endl;
  else{
    if ((abs(x) / d) % 2 == k % 2) cout << pos_ans << endl;
    else cout << neg_ans << endl;
  }
  }
  return 0;
}


Measured memory_bytes: 3620
#include<iostream>
#include<string>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<vector>
#include<utility>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<unordered_set>
#include<bitset>
using namespace std;
//#define MODE 1
#ifdef MODE
#define DEB(X) cout<< #X <<": "<<X<<" ";
#define ARDEB(i,X) cout<< #X <<"["<<i<<"]: "<<X[i]<<" ";
#define END cout<<endl;
#else
#define DEB(X) {}
#define ARDEB(i,X) {}
#define END {}
#endif
typedef pair<int,int> P;
struct edge{int to,cost;};
#define REP(i,n) for(int i=0;i<(n);i++)
const int INF=100000000;

int main(){
	int n,m,x,y,a[110],b[110],max=0,min=INF;
	cin>>n>>m>>x>>y;
	REP(i,n){
		cin>>a[i];
	}
	REP(i,m){
		cin>>b[i];
	}
	for(int i=-1000;i<=1000;i++){
		bool flag=true;
		REP(j,n){
			if(a[j]>=i){
				flag=false;
			}
		}
		REP(j,m){
			if(b[j]<i){
				flag=false;
			}
		}
		if(x<i&&i<=y){
			if(flag==true){
				cout<<"No War"<<endl;
				return 0;
			}
		}
	}
	cout<<"War"<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cmath>
using namespace std;

int main(){
	float a;
	float b;
	int moves;
	cin>>a>>b;
	int arr[int(a)];
	for(int i=0;i<a;i++){
		cin>>arr[i];
	}
	moves=ceil(float((a-b)/(b-1)))+1;
	cout<<moves;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main()
{
	ll n,k;
	cin>>n>>k;
	ll a[n+1];
	for (ll i=1;i<=n;i++)
		cin>>a[i];
	ll dp[n+1];
	dp[0]=0;
	dp[1]=0;
	for (ll i=2;i<=n;i++)
	{
		ll mi=INT_MAX;
		for (ll j=1;j<=k;j++)
		{
			if (i>j)
				mi=min(mi,dp[i-j]+abs(a[i]-a[i-j]));
		}
		dp[i]=mi;
	}
	cout<<dp[n];
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define INF 1LL<<62
#define inf 1000000007
long long modpow(long long a, long long n, long long mod) {
    long long res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}	ll sum2[100010]={};
int main() {
	ll n,k;
	cin>>n>>k;
	ll ans=0;

	for(ll i=1;i<=k;i++){
		ll up=k/i;
//		ll down=up-1;
		ll l=modpow(up, n, 1000000007);
//		ll r=modpow(down,n,1000000007);
		ll sum=(l);
		sum%=inf;
		sum2[i]=sum;
	}
	for(ll i=k;i>=1;i--){
		ll cnt=sum2[i];
		ll j=2;
		while(i*j<=k){
			cnt-=sum2[i*j];
			j++;
			while(cnt<0){
				cnt+=inf;
			}
		}
		sum2[i]=cnt;
		ans+=sum2[i]*i;
		ans%=inf;
	}
	cout <<ans;
	// your code goes here
	return 0;
}

Measured memory_bytes: 4344
/*
 Templatka c++ Kacper Fis																							   																											   //
*/

#include <iostream>
#include <cstdio>
#include <limits>
#include <cstdlib>
#include <utility>
#include <iterator>
#include <bitset>
#include <list>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <algorithm>
#include <cmath>
#include <string>
#include <time.h>
#include <iomanip>
#include <sstream>
#include <bits/stdc++.h>

using namespace std;

const int INF = 1000000001;
const float PI = 3.14;
typedef long long LL;

typedef vector<int> vi;
typedef list<int> li;
typedef queue<int> qi;
typedef pair<int,int> ii;
typedef map<string,int> msi; //np msi['nazwa'] = 'liczba'
typedef vector<ii> vii; //vector par<int>, do tworzenia tablicy dla grafów wagowych #dijkstra #Bellman_Ford
typedef priority_queue< ii, vector<ii>, greater<ii> > pq; //kolejka priorytetowa vectorów par(top()=min) #dijkstra


#define print_list(x) for(it = (x).begin(); it != (x).end(); it++) {cout << *it << " ";}
#define print_vector(x) for(it2 = (x).begin(); it2 != (x).end(); it2++) {cout << *it2 << " ";}
#define search_list(x) for(it = (x).begin(); it != (x).end(); it++)
#define search_vector(x) for(it2 = (x).begin(); it2 != (x).end(); it2++);
#define pb(x) push_back(x)
#define pf(x) push_front(x)
#define mp(x, y) make_pair(x, y)
///////////////////////////////////////////////GLOBAL DEFINITIONS////////////////////////////////////////////////////////



///////////////////////////////////////////////////FUNCTIONS/////////////////////////////////////////////////////////////



/////////////////////////////////////////////////////MAIN////////////////////////////////////////////////////////////////
int main(int argc, char* argv[])
{ios_base::sync_with_stdio(false); cin.tie(NULL);
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	
	string s1;
	string s2;
	cin >> s1 >> s2;
	string word = s1 + s2;
//cout << "word: " << word << endl;
	double one = stod(word);
	//cout << "one: " << one << endl;
	double sqr = sqrt(one);
	int two = (int)sqr;
	
	//cout << "sqr: " << sqr << endl;
	//cout << "two: " << two << endl;
	
	if(sqr == two){
		cout << "Yes" << endl;
	}
	else cout << "No" << endl;





	return 0;
}


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

vector<vector<ll>> G(100005);
vector<ll> used(100005, 0);

void dfs(int c) {
  for (ll n: G[c]) {
    if (used[n]) continue;
    used[n] = 1;
    dfs(n);
  }
}

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

  int N; cin >> N;
  int M; cin >> M;

  for (ll i = 0; i < M; i++) {
    ll a, b; cin >> a >> b; a--; b--;
    ll c; cin >> c;
    G[a].emplace_back(b);
    G[b].emplace_back(a);
  }
  
  ll ans = 0;
  for (int i = 0; i < N; i++) {
    if (!used[i]) {
      ans++;
      dfs(i);
    }
  }
  cout << ans << '\n';
  return 0;
}

Measured memory_bytes: 9600
#include <bits/stdc++.h>
using namespace std;
const long long INF = 1LL << 60;
const int mod = 1e9 + 7;

long long com(long long n, long long x)
{
    long long sum = 0;
    for (long long i = 1; i < x / 3 + 1; i++)
    {
        long long a = x;
        if (i > n - 2)
        {
            break;
        }
        a -= i;
        for (long long j = i + 1; j < a / +1; j++)
        {
            long long b = a;
            if (j > n - 1)
            {
                break;
            }
            b -= j;
            if (b > j && b <= n)
            {
                sum++;
            }
            else if (b <= j)
            {
                break;
            }
        }
    }

    return sum;
}

int main()
{
    long long r, c;
    cin >> r >> c;
    vector<vector<long long> > m(r + 1, vector<long long>(c + 1));
    for (int i = 0; i < r; i++)
    {
        long long sum = 0;
        for (int j = 0; j < c; j++)
        {
            cin >> m.at(i).at(j);
            sum += m.at(i).at(j);
        }
        m.at(i).at(c) = sum;
    }

    for (int i = 0; i < c; i++)
    {
        long long sum = 0;
        for (int j = 0; j < r; j++)
        {
            sum += m.at(j).at(i);
        }
        m.at(r).at(i) = sum;
    }
    m.at(r).at(c) = 0;
    for (int i = 0; i < c; i++)
    {
        m.at(r).at(c) += m.at(r).at(i);
    }

    for (int i = 0; i < r + 1; i++)
    {
        for (int j = 0; j < c + 1; j++)
        {
            if (j == 0)
            {
                cout << m.at(i).at(j);
                continue;
            }
            cout << " " << m.at(i).at(j);
        }
        cout << endl;
    }
    return 0;
}


Measured memory_bytes: 3104
package main
import "fmt"

func main(){
	var x, y int
	fmt.Scan(&x, &y)
	ans := gcd(x, y)
	fmt.Println(ans)
}

func gcd(x, y int)(ret int){
	if x<y{
		gcd(y, x)
	}
	for 0<y{
		x, y = y, x%y
	}
	return x
}


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

typedef long long int lli;

const lli maxn = lli(1e5)+5;

lli vis[maxn], type[2];
vector<lli> graph[maxn];

lli dfs(lli node, lli parity)
{
	vis[node] = parity;
	lli ret = 1;
	for(auto it: graph[node])
	{
		if(vis[it] == -1)
		{
			ret = min(ret, dfs(it, !parity));
		}
		else ret = min(ret, lli(vis[it] == (!parity)));
	}
	return ret;
}

int main(void)
{
	lli n, m, u, v;
	scanf("%lld%lld", &n, &m);
	for(lli i = 0;i < n;i++) vis[i] = -1;
	vector<lli> process;
	while(m--)
	{
		scanf("%lld%lld", &u, &v);
		u--, v--;
		graph[u].push_back(v);
		graph[v].push_back(u);
	}

	lli res = 0, iso = 0;
	for(lli i = 0;i < n;i++)
	{
		if(vis[i] == -1)
		{
			lli x = dfs(i, 0);
			if(graph[i].empty()) iso++;
			else type[x]++;
		}
	}

	//cout << iso << " " << type[0] << " " << type[1] << "\n";
	//combo = (isolated, something)
	res += iso*(n*2ll-iso);
	//combo = (bipartite, bipartite)
	res += type[1]*type[1]*2;
	//combo = (non-bipartite, something non isolated)
	res += type[0]*(type[1]*2+type[0]);
	printf("%lld\n", res);
}

Measured memory_bytes: 12416
import collections
N =  int(input())
a = list(map(int,input().split()))
a = collections.Counter(a)
a = sorted(a.items())
li = [0]*N
tmp = 0
if len(a)==1:
    print(a[0][1])
    exit()

for i in range(len(a)-1):
    tmp += a[i][1]
    if a[i][0]-1==a[i-1][0]:
        tmp += a[i-1][1]
    if a[i][0]+1==a[i+1][0]:
        tmp += a[i+1][1]
    li[i] = tmp
    tmp = 0

if a[-1][0]-1==a[-2][0]:
    li.append(a[-1][1]+a[-2][1])
print(max(li))

Measured memory_bytes: 15312
#!/usr/bin/env python3
import collections as cl
import sys


def II():
    return int(sys.stdin.readline())


def MI():
    return map(int, sys.stdin.readline().split())


def LI():
    return list(map(int, sys.stdin.readline().split()))


def main():

    c = input()

    print(chr(ord(c) + 1))


main()


Measured memory_bytes: 64656
import math

a,b,h,m = map(int,input().split())

time = h*60 + m
ji = math.radians(time*0.5)
hun = math.radians(m*6)

ax = a*math.sin(ji)
ay = a*math.cos(ji)
bx = b*math.sin(hun)
by = b*math.cos(hun)

ans = math.sqrt((ax-bx)**2 + (ay-by)**2)

print(ans)







Measured memory_bytes: 9540
#include<stdio.h>
#include<string.h>

int main(){

	int i, sum, a[1000] = {0};
	char b[1000] = {0}, c[1000] = {0};
	size_t len;

	while(1){

		sum = 0;

		c[0] = '0';

		scanf("%s", b);

		if(strcmp(b, c) == 0){
			break;
		}

		len = strlen(b);

		for(i = 0; i < len; i++){
			sum += b[i] - 48;
		}

		printf("%d\n", sum);
	}

	return 0;
}

Measured memory_bytes: 544
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<utility>
#include<string>
#include<stack>
#include<queue>
#include<set>
#include<math.h>
#include <map>
using namespace std;
typedef long long int ll;
#define repi(i,a,b) for(ll i=a;i<b;i++)
#define rep(i,a) repi(i,0,a)
#define all(u) u.begin(),u.end()
#define pl pair<ll,ll>
#define fi first
#define se second
#define inf 1000000007
#define mp(a,b) make_pair(a,b)

ll N;
ll A[100010];
ll Left[100010];
ll Right[100010];

ll gcd(ll a, ll b){
    while(1) {
        if(a < b) swap(a, b);
        if(!b) break;
        a %= b;
    }
    return a;
}
int main() {
    cin >> N;
    rep(i,N){
        cin >> A[i];
    }
    rep(i,N){
        if (i==0) Left[i] = A[i];
        else Left[i] = gcd(A[i],Left[i-1]);
    }
    for (ll i=N-1;i>=0;i--){
        if (i == N-1) Right[i] = A[i];
        else Right[i] = gcd(A[i],Right[i+1]);
    }
    ll ans = 0;
    rep(i,N){
        if (i==0) ans = max(ans,Right[1]);
        else if(i==N-1) ans = max(ans,Left[N-2]);
        else{
            ans = max(ans,gcd(Left[i-1],Right[i+1]));
        }
    }
    cout << ans << endl;
    
    return 0;
}


Measured memory_bytes: 2560
import java.util.*;
import java.lang.*;

public class Main{
    
    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[][] matrix = new int[n][m];
        int[] bector = new int[m];
        int[] ans = new int[n];
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                matrix[i][j] = sc.nextInt();
            }
        }
        for (int i = 0; i < m; i++) {
            bector[i] = sc.nextInt();
        }
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                ans[i] += bector[j] * matrix[i][j];
            }
            System.out.println(ans[i]);
        }
        
    }
}



Measured memory_bytes: 40660
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAXN=1e6+10;

int main() {
    LL x;
    cin>>x;
    LL ans=0;
    ans+=x/500*1000;
    ans+=(x%500)/5*5;
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
// Begin Header {{{
#define all(x) (x).begin(), (x).end()
#define lli long long int
#define rep(i,n) for(lli i=0; i<n; i++)
#define loop(i, j, n) for(lli i=j; i<n; i++)
#define Max(a, b) ((a) > (b) ? (a) : (b))
#define Min(a, b) ((a) < (b) ? (a) : (b))
constexpr int INF  = 0x3f3f3f3f;
const long long mod=1e9+7;
//Function
lli combi(lli n, lli r)
{
	if(r==0 || r==n) return 1;
	else return combi(n-1,r) + combi(n-1,r-1);
}
lli sigma1(lli n){return n*(n+1)/2;}
lli sigma2(lli s, lli n){return sigma1(n) - sigma1(s -1);}
using namespace std;
// }}} End Header

int main()
{
	ios::sync_with_stdio(false); cin.tie(nullptr);
	lli a, b;
	cin >> a >> b;
	lli g = __gcd(a, b);
	lli l = (a*b)/g;
	cout << l << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define REP(i,n) for(int i = 0; i < (int)(n); ++i)
#define DEBUG(x) cerr << #x << " = " << x << endl
signed main() {
  ios::sync_with_stdio(false);
  int N, M; cin >> N >> M;
  vector<int> x1(N), y1(N), x2(M), y2(M);
  REP(i,N) cin >> x1[i] >> y1[i];
  REP(i,M) cin >> x2[i] >> y2[i];
  REP(i,N) {
    vector<int> d(M);
    REP(j,M) {
      d[j] = abs(x1[i] - x2[j]) + abs(y1[i] - y2[j]);
    }
    int argmin = 0;
    REP(j,M) {
      if(d[argmin] > d[j]) argmin = j;
    }
    cout << argmin + 1 << endl;
  }
}


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

// 区間加算にも対応した BIT
template <class Abel> struct BIT {
    vector<Abel> dat[2];
    Abel UNITY_SUM = 0;                     // to be set
    
    /* [1, n] */
    BIT(int n) { init(n); }
    void init(int n) { for (int iter = 0; iter < 2; ++iter) dat[iter].assign(n + 1, UNITY_SUM); }
    
    /* a, b are 1-indexed, [a, b) */
    inline void sub_add(int p, int a, Abel x) {
        for (int i = a; i < (int)dat[p].size(); i += i & -i)
            dat[p][i] = dat[p][i] + x;
    }
    inline void add(int a, int b, Abel x) {
        sub_add(0, a, x * -(a - 1)); sub_add(1, a, x); sub_add(0, b, x * (b - 1)); sub_add(1, b, x * (-1));
    }
    
    /* a is 1-indexed, [a, b) */
    inline Abel sub_sum(int p, int a) {
        Abel res = UNITY_SUM;
        for (int i = a; i > 0; i -= i & -i) res = res + dat[p][i];
        return res;
    }
    inline Abel sum(int a, int b) {
        return sub_sum(0, b - 1) + sub_sum(1, b - 1) * (b - 1) - sub_sum(0, a - 1) - sub_sum(1, a - 1) * (a - 1);
    }
    
    /* debug */
    void print() {
        for (int i = 1; i < (int)dat[0].size(); ++i) cout << sum(i, i + 1) << ",";
        cout << endl;
    }
};

using pll = pair<long long, long long>;
int N;
long long D, A;
vector<long long> X, H;

long long solve() {
    // モンスターを X が小さい順に
    vector<int> ids(N);
    for (int i = 0; i < N; ++i) ids[i] = i;
    sort(ids.begin(), ids.end(), [&](int i, int j) {
            return X[i] < X[j]; });
    vector<long long> nX(N), nH(N);
    for (int i = 0; i < N; ++i) nX[i] = X[ids[i]], nH[i] = H[ids[i]];
    X = nX, H = nH;

    // BIT で処理していく
    BIT<long long> bit(N+10);
    for (int i = 0; i < N; ++i) bit.add(i+1, i+2, H[i]); // 初期化
    long long res = 0;
    for (int i = 0; i < N; ++i) {
        long long cur = bit.sum(i+1, i+2);
        if (cur <= 0) continue;

        // モンスター i を倒すのに必要な回数
        long long need = (cur + A - 1) / A;

        // X[i] を左端とした爆発が届く範囲を求める
        long long right = X[i] + D * 2;
        int id = upper_bound(X.begin(), X.end(), right) - X.begin();

        // 爆発させる
        bit.add(i+1, id+1, -need * A);
        res += need;
    }
    return res;
}

int main() {
    cin >> N >> D >> A;
    X.resize(N); H.resize(N);
    for (int i = 0; i < N; ++i) cin >> X[i] >> H[i];
    cout << solve() << endl;
}

Measured memory_bytes: 10368
#include <stdio.h>
#include <stdlib.h>

struct node {
	int car;
	int cdr;
	int height;
	int depth;
	int degree;
	int parent;
	int sibling;
};

int
depth(struct node *a, int p)
{
	if (a[p].depth != -1)
		return a[p].depth;

	a[p].depth = a[p].parent == -1 ? 0 : depth(a, a[p].parent) + 1;

	return a[p].depth;
}

int
height(struct node *a, int p, int d)
{
	int c0 = a[p].car < 0 ? 0 : height(a, a[p].car, d + 1);
	int c1 = a[p].cdr < 0 ? 0 : height(a, a[p].cdr, d + 1);

	a[p].depth = d;
	a[p].height = c0 < c1 ? c1 : c0;

	return a[p].height + 1;
}

int
main(void)
{
	int i, j, n;
	struct node *a;

	scanf("%d", &n);

	a = (struct node *)malloc(sizeof(struct node) * n);
	if (a == NULL)
		return 1;

	for (i = 0; i < n; i++) {
		a[i].parent = -1;
		a[i].sibling = -1;
		a[i].height = 0;
		a[i].depth = -1;
	}

	for (i = 0; i < n; i++) {
		int id, car, cdr;
		scanf("%d%d%d", &id, &car, &cdr);
		a[id].car = car;
		a[id].cdr = cdr;
		car >= 0 && (a[car].parent = id);
		cdr >= 0 && (a[cdr].parent = id);
		if (car >= 0 && cdr >= 0)
			a[cdr].sibling = car, a[car].sibling = cdr;
		a[id].degree = (car >= 0) + (cdr >= 0);
	}

	for (i = 0; i < n; i++)
		if (a[i].parent == -1) {
			height(a, i, 0);
			break;
		}

	for (i = 0; i < n; i++) {
		printf("node %d", i);
		printf(": parent = %d", a[i].parent);
		printf(", sibling = %d", a[i].sibling);
		printf(", degree = %d", a[i].degree);
		printf(", depth = %d", a[i].depth);
		printf(", height = %d", a[i].height);
		printf(", %s\n",
		       a[i].parent == -1 ? "root" :
		       a[i].degree > 0 ? "internal node" : "leaf");
	}

	return 0;
}



Measured memory_bytes: 2100
MOD = 10 ** 9 + 7

def pow(x,n)
  if n == 0
    1
  elsif n % 2 == 0
    pow(x*x%MOD, n/2) % MOD
  else
    x * pow(x, n-1) % MOD
  end
end

n = gets.to_i
dp = Array.new(n+1){Array.new(3,0)}
dp[0][0] = 1
if n == 1
  puts 0
else
  n.times do |i|
    dp[i+1][0] = (dp[i][0] * 8) % MOD
    dp[i+1][1] = (dp[i][0] * 2 + dp[i][1] * 9) % MOD
    dp[i+1][2] = (dp[i][1] * 1 + dp[i][2] * 10) % MOD
  end
  puts dp[n][2]
end


Measured memory_bytes: 66552
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <string>
#include <map>
#include <set>
#include <stack>
#include <tuple>
#include <deque>
#include <numeric>
#include <bitset>
#include <iomanip>
#include <cassert>
#include <chrono>
#include <random>
#include <limits>
#include <iterator>
#include <functional>
#include <sstream>
#include <complex>
using namespace std;

typedef long long ll;
typedef uint64_t ull;
typedef pair<int, int> P;
constexpr double PI = 3.1415926535897932;   // acos(-1)
constexpr double EPS = 1e-9;
constexpr int INF = 1001001001;
constexpr int mod = 1000000007;
// constexpr int mod = 998244353;

#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)

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

    ll x;
    cin >> x;
    ll st = 100;
    ll ans = 0;
    while(st < x){
        st = st + st / 100;
        ++ans;
    }
    cout << ans << endl;
}

Measured memory_bytes: 3612
// clang-format off
#include <bits/stdc++.h>
#define int long long
#define main signed main()
#define loop(i, a, n) for (int i = (a); i < (n); i++)
#define rep(i, n) loop(i, 0, n)
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define prec(n) fixed << setprecision(n)
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
using namespace std;
using pii = pair<int, int>;
using vi = vector<int>;
using vd = vector<double>;
using vc = vector<char>;
using vb = vector<bool>;
using vs = vector<string>;
using vpii = vector<pii>;
using vvi = vector<vi>;
using vvb = vector<vb>;
using vvpii = vector<vpii>;
template<typename A> using fn = function<A>;
constexpr int INF = sizeof(int) == sizeof(long long) ? 1000000000000000000LL : 1000000000;
constexpr int MOD = 1000000007;
constexpr double PI = acos(-1);
template<typename A, typename B> bool cmin(A &a, const B &b) { return a > b ? (a = b, true) : false; }
template<typename A, typename B> bool cmax(A &a, const B &b) { return a < b ? (a = b, true) : false; }
constexpr bool odd(const int &n) { return n & 1; }
constexpr bool even(const int &n) { return !odd(n); }
// clang-format on

main {
  int n;
  cin >> n;
  set<int> v;
  rep(i, n) {
    int a;
    cin >> a;
    v.insert(a);
  }
  cout << v.size() - even(v.size()) << endl;
}


Measured memory_bytes: 4992
import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    while (true) {
      int x = sc.nextInt();
      int y = sc.nextInt();
      if (x == 0 && y == 0) {
        return;
      }
      if (x <= y) {
        System.out.println(x + " " + y);
      } else {
        System.out.println(y + " " + x);
      }
    }
  }
}


Measured memory_bytes: 36176
N, K = map(int, input().split())

A = list(map(int, input().split()))

p = 0
q = 0
ans = 0
for i in range(N):
    for j in range(i, N):
        if A[i] > A[j]:
            p += 1

for i in range(N):
    for j in range(N):
        if A[i] > A[j]:
            q += 1

ans = (p * K) % 1000000007 + (q * K * (K-1) // 2) % 1000000007

print(ans % 1000000007)


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

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

    }}

Measured memory_bytes: 3080
import java.util.Scanner;

class Main{
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int N=sc.nextInt();
		int[][] sw=new int[N][2];
		long cnt=0;
		for(int i=0; i<N; i++) {
			sw[i][0]=sc.nextInt();
			sw[i][1]=sc.nextInt();
		}
		for(int i=N-1; i>=0; i--) {
			if((cnt+sw[i][0])%sw[i][1]==0) {
				//
			}
			else {
				cnt+=sw[i][1]-(cnt+sw[i][0])%sw[i][1];
			}
		}
		System.out.println(cnt);
		sc.close();
	}
}

Measured memory_bytes: 94540
/*NOT_FREE == 2*N+2   FREE == 2*N+3*/

#include<stdio.h>
#define N 8
#define Not 2*N+2
#define FREE 2*N+3

/*??°?????????????????°*/
int row[N],cal[N],Q[N][N];
int dpos[2*N-1],dneg[2*N-1];/*??°????????????????????????????????????*/
/*????????????????????£?¨?*/
void printboard(void);
int putQueen(int);

int main(){
int k,i,j,r,c;
  scanf("%d",&k);

  for(i=0;i<=k-1;i++){
  scanf("%d%d", &r, &c);
     Q[r][c] = Not;
  }

  putQueen(0);

  return 0;
}


int putQueen(int i){
  int j;

  if(i==N){
    printboard();
    return 0;
  }

  for(j=0;j<=N-1;j++){
    if(cal[j]==Not || dpos[i+j]==Not || dneg[i-j+N-1]==Not){
      continue;
    }  
    row[i]=j;
    cal[j]=dpos[i+j] = dneg[i-j+N-1] = Not;
    putQueen(i+1);
    cal[j] = dpos[i+j] = dneg[i-j+N-1] = FREE;
  }
}




void printboard(){
  int i, j;
  
  for(i = 0; i < N; i++){
    for(j = 0; j < N; j++){
      if(Q[i][j] == Not && row[i] != j)
	 return;
       }
      }
  
  for(i = 0; i < N; i++){
    for(j = 0; j < N; j++){
      if(row[i] == j)
	 printf("Q");
       else
	 printf(".");
       }
       printf("\n");
      }
  }

Measured memory_bytes: 572
<?php
$n = trim(fgets(STDIN));
$b = explode(" ", trim(fgets(STDIN)));

$count = 0;
$count += $b[0];
for($i=1; $i<count($b); $i++){
    $count += min($b[$i-1],$b[$i]);
}
$count += $b[count($b)-1];

echo $count;

?>

Measured memory_bytes: 4728
#include <iostream>
#include <iomanip>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <math.h>
#include <sstream>
#include <numeric>
#include <string>
#include <cassert>
#include <bitset>

using namespace std;
typedef long long ll;

int main() {
  int N;
  string S;
  int Q;
  cin >> N >> S >> Q;
  map<char, set<int> > sets;
  for (int i = 0; i < N; ++i) {
    char ch = S[i];
    sets[ch].insert(i);
  }
  
  for (int iter = 0; iter < Q; ++iter) {
    int cmd;
    cin >> cmd;
    if (cmd == 1) {
      int i;
      char ch;
      cin >> i >> ch;
      --i;
      char old_ch = S[i];
      sets[old_ch].erase(i);
      S[i] = ch;
      sets[ch].insert(i);
    } else {
      int l, r;
      cin >> l >> r;
      --l; --r;
      int ans = 0;
      for (char ch = 'a'; ch <= 'z'; ++ch) {
      	const set<int> &s = sets[ch];
	auto it = s.lower_bound(l);
      	if (it != s.end() and *it <= r) ++ans;
      }
      cout << ans << endl;
    }      
  }
  return 0;
}


Measured memory_bytes: 24324