akhauriyash/Code-Regression huggingface dataset:
use proconio::{fastout, input};
use std::ops::{AddAssign, Sub};

#[derive(Debug)]
pub struct FenwickTree<T> {
    n: usize,
    data: Vec<T>,
}

impl<T> FenwickTree<T>
where
    T: AddAssign + Sub<Output = T> + Clone + Copy + Default,
{
    pub fn new(n: usize) -> Self {
        FenwickTree {
            n,
            data: vec![T::default(); n],
        }
    }

    pub fn add(&mut self, p: usize, x: T) {
        assert!(p < self.n);
        let mut p = p as isize;
        p += 1;
        while p <= self.n as isize {
            self.data[(p - 1) as usize] += x;
            p += p & -p;
        }
    }

    pub fn sum(&self, l: usize, r: usize) -> T {
        assert!(l <= r && r <= self.n);
        self._sum(r) - self._sum(l)
    }

    fn _sum(&self, r: usize) -> T {
        let mut s = T::default();
        let mut r = r as isize;
        while r > 0 {
            s += self.data[(r - 1) as usize];
            r -= r & -r;
        }
        s
    }
}

impl<T> From<Vec<T>> for FenwickTree<T>
where
    T: AddAssign + Sub<Output = T> + Clone + Copy + Default,
{
    fn from(v: Vec<T>) -> FenwickTree<T> {
        let n = v.len();
        let mut tree = FenwickTree::new(n);
        for (i, &e) in v.iter().enumerate() {
            tree.add(i, e);
        }
        tree
    }
}

#[fastout]
fn main() {
    input! {
        n: usize,
        q: usize,
        aa: [usize; n],
        queries: [(usize, usize, usize); q],
    }

    let mut tree = FenwickTree::from(aa);

    for (q, l, r) in queries {
        if q == 0 {
            tree.add(l, r);
        } else if q == 1 {
            let ans = tree.sum(l, r);
            println!("{}", ans);
        }
    }
}


Measured memory_bytes: 34960
k = int(input())
#a,b = map(int,input().split())
#a_L = list(map(int,input().split()))

import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

def gcd_list(numbers):
    return reduce(math.gcd, numbers)

ans = 0
for a in range(1,k+1):
    for b in range(1,k+1):
        for c in range(1,k+1):
            ans += gcd(a,b,c)

print(ans)

Measured memory_bytes: 69812
D, N = list(map(int, input().split()))
if D == 0:
    if N < 100:
        print(N)
    else:
        print(101)
if D == 1 or D == 2:
    if N < 100:
        print(N * 100 ** D)
    else:
        print(101 * 100 ** D)


Measured memory_bytes: 2940
#!/usr/bin/env python3
#AGC3 C

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
a = [I() for _ in range(n)]
b = sorted(a)
lst = []
for i in range(n):
    if a[i] != b[i]:
        r = bl(b,a[i])
        if i % 2 ^ r % 2 == 0:
            continue
        lst.append(a[i])
lst.sort()
m = len(lst)
ans = m//2
print(ans)


Measured memory_bytes: 49756
#include <stdio.h>

int main()
{
    
	int A, B, C;
	int m = scanf("%d %d %d", &A, &B, &C);
	if (m == EOF) {
		printf("scan error!\n");
		return 0;
	}

	//printf("%d\t%d\t%d\n", A, B, C);

	int rest = A - B;
	int rest_C = 0;
	if (rest < C) {
		rest_C = C - rest;
	}

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

	return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <map>
#include <cmath>
#include <algorithm>

using namespace std;

int main()
{
	int  n, x, y;
	cin >> n >> x >> y;
	map<int, int>mp;
	for (int i = 1; i <= n; i++)
	{
		for (int j = i + 1; j <= n; j++)
		{
			int dist = j - i;
			dist = min(dist, (abs(i - x) + 1 + abs(y - j)));
			dist = min(dist, (abs(i - y) + 1 + abs(x - j)));
			mp[dist]++;
		}
	}

	for (int i = 1; i < n; i++)
		cout << mp[i] << endl;

	return 0;
}

Measured memory_bytes: 384
#include<cstdio>
#include<math.h>
#include<algorithm>
#include<vector>
#include<queue>
#include<string>
#include<set>
#include<cstring>

 
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1001001001
#define LLINF 1001001001001001001
#define mp make_pair
#define pb push_back
#define LLIandI pair<long long int , int>
#define ll long long
int main(void){
    int N;
    scanf("%d",&N);
    long long int a[200002],b[200002];//<10^9
    rep(i,N){
        scanf("%lld",&a[i]);
    }
    rep(i,N){
        scanf("%lld",&b[i]);
    }
    long long int amod[200002],bmod[200002];
    long long int ans=0;
    long long int biti=1;
    long long int biti_over=2;
    rep(i,30){
        rep(j,N)amod[j]=a[j]% biti_over;
        rep(j,N)bmod[j]=b[j]% biti_over;
        sort(&amod[0],&amod[N]);
        long long int xorabpair=0;
        rep(j,N){
            long long int xor1a_min=biti-bmod[j];
            long long int xor1a_max=biti_over-bmod[j]-1;
            long long int xor11a_min=biti+biti_over-bmod[j];
            long long int xor11a_max=biti_over+biti_over-bmod[j]-1;
            xorabpair+=abs(upper_bound(&amod[0],&amod[N],xor1a_max)-lower_bound(&amod[0],&amod[N],xor1a_min) );
            xorabpair+=abs(upper_bound(&amod[0],&amod[N],xor11a_max)-lower_bound(&amod[0],&amod[N],xor11a_min) );
        }
        ans+=(xorabpair%2)*biti;
        biti*=2;biti_over*=2;
    }
    printf("%lld\n",ans);
    
}


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

typedef long long ll;
#define fi first
#define se second
#define SORT(a) sort(a.begin(),a.end())
#define REP(i,n) for (int i = 0;i < (n) ; i++) 
#define MP(a,b) make_pair(a,b)
 
using namespace std;

int main(){

    int a,b;
    cin >> a >> b;
    cout << (b-a)*(b-a+1)/2 - b;
    
}


Measured memory_bytes: 256
#include<bits/stdc++.h>    
using namespace std;
#define ll long long 
#define pi pair<ll,ll>
#define pd pair<ld,ld>
#define pb push_back
#define inf 1e18
#define mod 1000000007
#define en '\n'
#define ld long double
#define ff first
#define ss second
#define ull unsigned long long 
#define lb lower_bound
#define ub upper_bound
#define fr(a,b,c) for(ll a = b ; a <= c ; ++a )
#define frn(a,b,c) for(ll a = b ; a >= c ; a -- )
#define fra(a,b) for(auto a: b)
#define ms(a) memset(a,0,sizeof a);
#define alla(a) a,a+n
#define allv(a) a.begin(),a.end()
#define size(a) (ll)a.size()
#define getMat(x,n,m,val) vector<vector<ll>>x(n,vector<ll>(m,val))
const ll MAXN = 1000005;
#define pii 3.14159265358979323846
 
ll pw(ll b, ll r, ll md){
	ll ans = 1;
	while(r){
		if(r&1)ans = (ans*b)%md;
		b = (b*b)%md;
		r>>=1;
	}
	return ans;
}
int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	ll n,m;cin>>n>>m;
	vector<ll>g[n+1];
	fr(i,0,m-1){
		ll a,b;cin>>a>>b;
		g[a].pb(b);
		g[b].pb(a);
	}
	ll ans[n+1];ms(ans);
	queue<ll>q;
	q.push(1);
	ans[1]=1;
	while(!q.empty()){
		ll u = q.front();
		q.pop();
		for(auto v: g[u]){
			if(!ans[v]){
				q.push(v);
				ans[v]=u;
			}
		}
	}
	bool flag = false;
	fr(i,1,n)if(!ans[i])flag=true;
	if(flag)cout<<"No\n";
	else {
		cout<<"Yes\n";
		fr(i,2,n)cout<<ans[i]<<en;
	}
	return 0 ;
}

Measured memory_bytes: 13012
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1010;
int n;
char s[N];
int main(){
	scanf("%s",s+1);
	n=strlen(s+1);
	if(s[n]=='s')
		s[++n]='e';
	s[++n]='s';
	s[n+1]='\0';
	printf("%s",s+1);
	return 0;
}

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

from collections import defaultdict

def solve():
    n = int(input())
    ad = defaultdict(int)
    for i in input().split():
       ad[int(i)] += 1
    
    ans = 0
    for k, v in ad.items():
        if k > v:
            ans += v
        if v > k:
            ans += v - k
    print(ans)

if __name__=="__main__":
    solve()


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

using i64=int64_t;

#define rep(i,x,y) for(i64 i=i64(x),i##_max_for_repmacro=i64(y); i<i##_max_for_repmacro; ++i)
#define debug(x) #x << "=" << (x)
 
#ifdef DEBUG
#define _GLIBCXX_DEBUG
#define print(x) std::cerr << debug(x) << " (L:" << __LINE__ << ")" << std::endl
#else
#define print(x)
#endif
 
const int inf=1.01e9;
const i64 inf64=4.01e18;
const double eps=1e-9;
 
template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec){
    os << "[";
    for (const auto &v : vec) {
        os << v << ",";
    }
    os << "]";
    return os;
}

void solve(){
    i64 N,K;
    cin >> N >> K;

    vector<i64> a(N);
    rep(i,0,N) cin >> a[i];

    vector<i64> s(N);
    s[0]=a[0];
    rep(i,1,N){
        s[i]=s[i-1]+a[i];
    }

    vector<i64> b;
    rep(i,0,N){
        rep(j,i,N){
            i64 tmp=s[j];
            if(i) tmp-=s[i-1];
            b.push_back(tmp);
        }
    }

    sort(rbegin(b),rend(b));

    i64 x=0;
    for(i64 i=42; i>=0; --i){
        i64 cnt=0;
        x|=i64(1)<<i;
        vector<i64> c;
        rep(j,0,b.size()){
            if((x&b[j])==x){
                ++cnt;
                c.push_back(b[j]);
            }
        }
        if(cnt<K) x&=~(i64(1)<<i);
        else b=c;
    }

    cout << x << endl;
}

int main(){
    std::cin.tie(0);
    std::ios::sync_with_stdio(false);
    cout.setf(ios::fixed);
    cout.precision(16);
    solve();
    return 0;
}


Measured memory_bytes: 6384
#include <bits/stdc++.h>
using namespace std;
#define what_is(x) cerr << #x << " is " << x << endl;
#define IOS ios::sync_with_stdio(false); cin.tie(0);
typedef long long ll;
const int N = 100+5;
const int M = 1e5+5;
const int INF = 1e9;
const int MOD = 1e9+7;

int n, W;
int w[N], v[N];
ll mem[N][M];
ll dp(int n, int W){
	if (n == 0) return 0;
	ll &ret(mem[n][W]);
	if (ret != -1) return ret;
	ret = dp(n-1, W);
	if (W-w[n] >=0) ret = max(ret, dp(n-1, W-w[n]) + v[n]);
	return ret;

}
int main()
{
	IOS
	// freopen("input.txt", "r", stdin);
	cin >> n >> W;
	// what_is(n); what_is(W);
	for (int i=1; i<=n; i++){
		cin >> w[i] >> v[i];
	}
	for(int i=0; i<N; i++){
		memset(mem[i], -1, sizeof mem[i]);
	}
	ll ans = dp(n, W);
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 82304
#include <bits/stdc++.h>
using namespace std;
#define ALL(x) (x).begin(),(x).end()
#define COUT(x) cout<<(x)<<"\n"
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define REP(i, n) for(int i=0;i<n;i++)
#define YES(x) cout<<(x?"YES":"NO")<<"\n"
#define Yes(x) cout<<(x?"Yes":"No")<<"\n"
#define dump(x) cout<<#x<<" = "<<(x)<<"\n"
#define endl "\n"
using G = vector<vector<int>>;
using M = map<int,int>;
using P = pair<int,int>;
using PQ = priority_queue<int>;
using PQG = priority_queue<int,vector<int>,greater<int>>;
using V = vector<int>;
using ll = long long;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
const int INF = 1e9;
const int MOD = 1e9+7;
const ll LINF = 1e18;

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

int main() {
  IOS;
  ll a,b,c,d;
  cin >> a >> b >> c >> d; a--;
  ll cd = lcm(c,d);

  ll adivc = a/c;
  ll adivd = a/d;
  ll adivcd = a/cd;

  ll bdivc = b/c;
  ll bdivd = b/d;
  ll bdivcd = b/cd;

  COUT(b-a-((bdivc+bdivd-bdivcd) - (adivc+adivd-adivcd)));
  return 0;
}

Measured memory_bytes: 256
import java.math.BigDecimal;
import java.util.Scanner;


public class Main{
	
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		while(sc.hasNext()) {
			ORLine l1 = new ORLine(sc.next(), sc.next(), sc.next(), sc.next());
			ORLine l2 = new ORLine(sc.next(), sc.next(), sc.next(), sc.next());
			
			if(orthogonal(l1, l2)) System.out.println("YES");
			else System.out.println("NO");
		}
		sc.close();
	}
	
	static boolean orthogonal(ORLine l1, ORLine l2) {
		if(l1.a.multiply(l2.a).compareTo(l1.b.multiply(l2.b).negate()) == 0) return true;
		else return false;
	}
}

class ORLine{
	BigDecimal a;
	BigDecimal b;
	
	ORLine(String xa, String ya, String xb, String yb){
		a = new BigDecimal(ya).subtract(new BigDecimal(yb));
		b = new BigDecimal(xb).subtract(new BigDecimal(xa));
	}
}

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

int main()
{
   ll n,d;
   cin>>n>>d;
   ll p,q;
   ll count{};
   while(n--)
   {
      cin>>p>>q;
      double distance = sqrt(p*p + q*q);
      if(distance<=d)
         count++;
   }
   cout<<count;
   return 0;
   
}

Measured memory_bytes: 3668
package main
  
import (
    "fmt"
)

func main() {
    var n, m, c int
    fmt.Scan(&n, &m, &c)
    bs := make([]int, m)
    for i := range bs {
        var b int
        fmt.Scan(&b)
        bs[i] = b
    }

    var cnt int
    for i := 0; i < n; i++ {
        var sum int
        for j := 0; j < m; j++ {
            var a int
            fmt.Scan(&a)
            sum += a * bs[j]
        }
        sum += c
        if sum > 0 {
            cnt++
        }
    }

    fmt.Println(cnt)
}


Measured memory_bytes: 512
#include <iostream>

using namespace std;

int main(){
        int time[5],ans=0;
        for(int i=0; i<5; i++) cin>>time[i];

        int keep=time[0]%10,num=0;
        for(int i=1; i<5; i++) {
                if((time[i]%10<keep)&&(time[i]%10!=0)) num=i;
        }

        for(int i=0; i<5; i++) {
                if((i==num)||(time[i]%10==0))ans+=time[i];
                else ans+=(time[i]/10+1)*10;
        }

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


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

using namespace std;

#define MOD 1000000007

int n, h, d;
long long fac = 1, sum, dp[1000005], ad[1000005], cur;

void add(long long& a, long long b) {
	a += b;
	if (a >= MOD)
		a -= MOD;
}

int main() {
	scanf("%d%d%d", &n, &h, &d);
	for (int i = 1; i <= n; i++) {
		fac = fac * i % MOD;
		add(sum, fac);
	}
	dp[0] = fac;
	for (int i = 0; i < h; i++) {
		add(cur, ad[i]);
		add(dp[i], cur);
		if (i + d >= h)
			add(dp[h], dp[i]);
		ad[i + 1] = (ad[i + 1] + dp[i] * sum) % MOD;
		add(ad[min(i + d + 1, h)], MOD - dp[i] * sum % MOD);
	}
	printf("%lld\n", dp[h]);
}


Measured memory_bytes: 15872
#include <iostream>
 
using namespace std;
 
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};

void dfs(int x,int y);
int w,h;
 
int count;
bool flag;
char maze[21][21];
bool reached[501][501];
 
int main(){
        int w,h;

    while(cin>>w>>h){

            if(w==0&&h==0){
                break;
            }

            for(int i=0;i<h;i++){
                for(int j=0;j<w;j++){
                    cin>>maze[i][j];
                }
            }


// cout<<endl;
//              for(int i=0;i<h;i++){
//                 for(int j=0;j<w;j++){
//                     cout<<maze[i][j];
//                 }
//                 cout<<endl;
//             }

//             cout<<endl;


// cout<<endl;
//             for(int i=0;i<21;i++){
//                 for(int j=0;j<21;j++){
//                     cout<<maze[i][j];
//                 }
//                 cout<<endl;
//             }cout<<endl;

            for(int i=0;i<h;i++){
                for(int j=0;j<w;j++){
                    if(maze[i][j]=='@'){
                        dfs(j,i);
                    }
                }
            }

            // for(int i=0;i<h;i++){
            //     for(int j=0;j<w;j++){
            //         cout<<maze[i][j];
            //     }
            //     cout<<endl;
            // }

            count=0;
            for(int i=0;i<h;i++){
                for(int j=0;j<w;j++){
                    if(maze[i][j]=='!')count++;
                }
            }

            cout<<count<<endl;

            for(int i=0;i<22;i++){
                for(int j=0;j<22;j++){
                    maze[i][j]='%';
                }
            }

            // cout<<endl;


        }
    


 
    return 0;
}
 
 
void dfs(int x,int y){
    maze[y][x]='!';

    for(int i=0;i<4;i++){
        int mx=x+dx[i];
        int my=y+dy[i];
        if(maze[my][mx]=='.'){
            dfs(mx,my);
        }
        if(mx<0||w<=mx||my<0||h<=my){
            continue;
        }//??????????????´?????´???->???????????????



        
    } 
}

Measured memory_bytes: 2996
#include <bits/stdc++.h>
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)

using namespace std;
typedef long long int ll;
typedef unsigned uint;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef pair<int,P> PP;

vector<PP> v;
const double eps = 1e-10;
const ll LINF = 1001002003004005006ll;
const int INF = 1001001001;

int main() {
	int a,b;
	string s;
	cin >> a >> b;
	int ans = a - b*2;
	if(ans<0) cout << "0" << endl;
	else cout << ans << endl;
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <math.h>
#include <iomanip>
#include <bitset>
#include <string>
#include <cstring>
#include <stdlib.h>
#include <utility>
#include <set>
#include <map>
using namespace std;
typedef long long int ll;
typedef long double ld;
typedef pair<ll,ll> pairs;

#define MOD 998244353


ll gcd(ll a,ll b){
    if (a%b==0)return(b);
    else return(gcd(b,a%b));
}

bool primeNumber(ll n){
    if(n < 2) return false;
    else{
        for(ll i = 2; i * i <= n; i++){
            if(n % i == 0) return false;
        }
        return true;
    }
}


int main(){
    ll k; cin>>k;
    ll a[32] = {1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};
    cout<<a[k-1]<<endl;
    return 0;
}



Measured memory_bytes: 256
n,x = map(int,raw_input().split())
arr = map(int,raw_input().split())
su = arr[0]
ans = 0
for i in range(1,n):
    su += arr[i]
    if su > x:
        diff = min(arr[i],su-x)
        arr[i] -= diff
        su = arr[i-1]+arr[i]
        if su > x:
            diff1 = min(arr[i-1],su-x)
            arr[i-1] -= diff1
            su = arr[i-1]+arr[i]
            ans += diff1
        ans += diff
    su = arr[i]
print ans

Measured memory_bytes: 41836
package main

import "fmt"

func main() {
	var w string
	fmt.Scan(&w)

	dic := map[rune]int{}
	ans := "Yes"

	for _, v := range w {
		if _, ok := dic[v]; !ok {
			dic[v] = 0
		}
		dic[v]++
	}

	for _, v := range dic {
		if v%2 != 0 {
			ans = "No"
			break
		}
	}
	fmt.Println(ans)
}


Measured memory_bytes: 512
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <algorithm>
#include <cmath>

using namespace std;

int main()
{
    int i, j;
    long long n, k;

    cin >> n >> k;

    long long a = n / k;
    long long b = n - (k * a);

    if (b > k / 2) {
        cout << k - b << endl;
    } else {
        cout << b << endl;
    }

    return 0;
}


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

#define rep(i, n) for (int i = 0; i < int(n); i++)
#define rrep(i, n) for (int i = int(n) - 1; i >= 0; i--)
#define reps(i, n) for (int i = 1; i <= int(n); i++)
#define rreps(i, n) for (int i = int(n); i >= 1; i--)
#define repc(i, n) for (int i = 0; i <= int(n); i++)
#define rrepc(i, n) for (int i = int(n); i >= 0; i--)
#define repi(i, a, b) for (int i = int(a); i < int(b); i++)
#define repic(i, a, b) for (int i = int(a); i <= int(b); i++)
#define all(a) (a).begin(), (a).end()
#define bit32(x) (1 << (x))
#define bit64(x) (1ll << (x))
#define sz(v) ((int) v.size())

using namespace std;

using i64 = long long;
using f80 = long double;
using vi32 = vector<int>;
using vi64 = vector<i64>;
using vf80 = vector<f80>;
using vstr = vector<string>;

void yes() { cout << "Yes" << endl; exit(0); }
void no() { cout << "No" << endl; exit(0); }
template <typename T> class pqasc : public priority_queue<T, vector<T>, greater<T>> {};
template <typename T> class pqdesc : public priority_queue<T, vector<T>, less<T>> {};
template <typename T> void amax(T &x, T y) { x = max(x, y); }
template <typename T> void amin(T &x, T y) { x = min(x, y); }
template <typename T> T exp(T x, i64 n, T e = 1) { T r = e; while (n > 0) { if (n & 1) r *= x; x *= x; n >>= 1; } return r; }
template <typename T> istream& operator>>(istream &is, vector<T> &v) { for (auto &x : v) is >> x; return is; }
template <typename T> ostream& operator<<(ostream &os, vector<T> &v) { rep(i, v.size()) { if (i) os << ' '; os << v[i]; } return os; }
void solve(); int main() { ios::sync_with_stdio(0); cin.tie(0); cout << fixed << setprecision(16); solve(); return 0; }

const i64 INF = 1000000000000000000;
const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, 1, 0, -1};

void solve() {
  int n;
  cin >> n;
  vi64 a(n);
  cin >> a;
  rep(i, n) {
    if (a[i] == 0) {
      cout << 0 << endl;
      return;
    }
  }
  {
    int c = 0;
    rep(i, n) {
      if (a[i] > (i64) 1e9) c += 1;
    }
    if (c >= 2) {
      cout << -1 << endl;
      return;
    }
  }
  i64 ans = 1;
  rep(i, n) {
    ans *= a[i];
    if (ans > (i64) 1e18) {
      cout << -1 << endl;
      return;
    }
  }
  cout << ans << endl;
}


Measured memory_bytes: 3996
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define INF (1LL<<50)
#define MOD 1000000007

int main(){
    int N;
    cin >> N;
    map<int,int> mp_odd,mp_even;
    vector<int> A(N);
    bool f = true;
    int bf;
    rep(i,N){
        cin >> A[i];
        if(i==0) bf = A[i];
        else if(bf!=A[i]) f=false;
        if(i%2!=0){
            mp_odd[A[i]]++;
        }else{
            mp_even[A[i]]++;
        }
    }
    // すべての数が一緒の場合
    if(f){
        cout << N/2 << endl;
        return 0;
    }

    int odd_memo=0,odd_memo2=0;
    int even_memo=0,even_memo2=0;
    int odd_1st = -1;
    int odd_2nd = -1;
    int even_1st = -1;
    int even_2nd = -1;
    rep(i,N){
        if(i%2!=0){
            if(odd_1st<mp_odd[A[i]]){
                odd_1st = mp_odd[A[i]];
                odd_memo = A[i];
            }
        }else{
            if(even_1st<mp_even[A[i]]){
                even_1st = mp_even[A[i]];
                even_memo = A[i];
            }
        }
    }
    if(odd_memo!=even_memo){
        cout << N - odd_1st - even_1st << endl;
        return 0;
    }
    // 最頻値が同じときは2番目の数を候補にする
    mp_odd[odd_memo]=-1;
    mp_even[even_memo]=-1;
    rep(i,N){
        if(i%2!=0){
            if(odd_2nd<mp_odd[A[i]]){
                odd_2nd = mp_odd[A[i]];
                odd_memo2 = A[i];
            }
        }else{
            if(even_2nd<mp_even[A[i]]){
                even_2nd = mp_even[A[i]];
                even_memo2 = A[i];
            }
        }
    }
    // 2番目の最頻値が多いほうを2番目にそろえる
    if(odd_2nd>even_2nd){
        cout << N - even_1st - odd_2nd << endl;
    }else if(odd_2nd<even_2nd){
        cout << N - even_2nd - odd_1st << endl;
    }else{
        // 2番目も同じ場合はどっちでもいい
        cout << N - even_1st - odd_2nd << endl;
    }
    return 0;
}

Measured memory_bytes: 5376
s = input()
q = int(input())
for i in range(q):
    line = input()
    if 'print' in line:
        op, a, b = line.split()
        a = int(a)
        b = int(b)
        print(s[a:b+1])
    elif 'reverse' in line:
        op, a, b = line.split()
        a = int(a)
        b = int(b)
        reversed_substring = ''.join(list(reversed(s[a:b+1])))
        s = s[:a] + reversed_substring + s[b+1:]
    elif 'replace' in line:
        op, a, b, p = line.split()
        a = int(a)
        b = int(b)
        s = s[:a] + p + s[b+1:]



Measured memory_bytes: 5616
package main

import (
	"bufio"
	"fmt"
	"os"
	"sort"
	"strconv"
)

var sc = bufio.NewScanner(os.Stdin)

func scanInt() int {
	sc.Scan()
	i, err := strconv.Atoi(sc.Text())
	if err != nil {
		panic(err)
	}
	return i
}

func main() {
	sc.Split(bufio.ScanWords)

	N, M := scanInt(), scanInt()
	X := make([]int, M)
	for i := 0; i < M; i++ {
		X[i] = scanInt()
	}
	sort.Ints(X)

	Y := make([]int, M-1)
	for i := 0; i < M-1; i++ {
		Y[i] = X[i+1] - X[i]
	}
	sort.Ints(Y)

	ans := 0
	for i := 0; i < M-N; i++ {
		ans += Y[i]
	}

	fmt.Println(ans)
}


Measured memory_bytes: 4152
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<vector>
#include<queue>
#include<cmath>
#define ll long long
#define F(i,a,b) for(int i=(a);i<=(b);i++)
using namespace std;
template<class T>inline void read(T &x) {
    x=0; int ch=getchar(),f=0;
    while(ch<'0'||ch>'9'){if (ch=='-') f=1;ch=getchar();}
    while (ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    if(f)x=-x;
}
const int inf=0x3f3f3f3f;
const int maxn=300050;
ll n,c[maxn],s[maxn],ans[maxn];
bool calc(ll x,ll y)
{
	if(s[x]>=x*y) return true;
	return false;
}
int main()
{
	read(n);
	F(i,1,n)
	{
		int x;read(x);
		c[x]++;
		s[c[x]]++;
	}
	for(int i=1;i<=n;i++) s[i]+=s[i-1];
	int t=n;
	for(int i=1;i<=n;i++)
	{
		while(t&&(!calc(t,i))) t--;
		ans[i]=t;
	}
	for(int i=1;i<=n;i++) cout<<ans[i]<<endl;
	return 0;
}



Measured memory_bytes: 7936
n,m=map(int,input().split())
A=[int(i) for i in input().split()]
if 2 in A and 3 in A:
  A.remove(2)
if 3 in A and 5 in A:
  A.remove(3)
if 2 in A and 5 in A:
  A.remove(2)
if 6 in A and 9 in A:
  A.remove(6)
m=len(A)
D={}
D[1]=2
D[2]=5
D[3]=5
D[4]=4
D[5]=5
D[6]=6
D[7]=3
D[8]=7
D[9]=6
DP=[-float("inf")]*(n+1)
DP[0]=0
for i in range(n):
  for j in range(m):
    if D[A[j]]<=i+1 and DP[i+1-D[A[j]]]!=float("inf") and DP[i+1-D[A[j]]]+1>=DP[i+1]:
      DP[i+1]=DP[i+1-D[A[j]]]+1
A.sort(reverse=True)
k=DP[n]
ans=""
cur=n
for _ in range(k):
  for j in range(m):
    if cur>=D[A[j]] and DP[cur-D[A[j]]]==DP[cur]-1:
      ans+=str(A[j])
      cur-=D[A[j]]
      break
print(ans)

Measured memory_bytes: 43628
#include<iostream>
#include<string>
#include<vector>
#include<queue>
#include<cmath>
#include<iomanip>
#include<algorithm>
#define lint long long int
#define FOR(x, to) for(int x=0; x<(to); x++) // for簡略表記
#define DUMP(ar) for(int i=0; i<ar.size(); i++) cout << "[" << i << "]:" << ar[i] << endl // 配列一覧表示
#define COUT(x) cout << x << endl // 単要素出力
#define ALL(ar) ar.begin(), ar.end() // コンテナの全要素
using namespace std;
// cout << fixed << setprecision(4) で小数点以下4桁の桁そろえ
// goto ANSWER; で最後へ飛ぶ
 
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
     
    int n, q;
    cin >> n;
    vector<int> s(n);
    FOR(i, n) cin >> s[i];
    cin >> q;
    vector<int> t(q);
    FOR(i, q) cin >> t[i];
 
    int cnt = 0;
    for(int i=0; i<q; i++){
        for(int k=0; k<n; k++){
            if(s[k] == t[i]){
                cnt++;
                break;
            }
        }
    }
     
ANSWER:
    COUT(cnt);
    return 0;
}


Measured memory_bytes: 3176
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <cmath>
#include <vector>
#define rep(i, n) for(int i = 0; i < n; i++)
using namespace std;
typedef long long ll;

int main() {
    int n, a, b;
    cin >> n >> a >> b;
    if(a > b) {
        cout << 0 << endl;
        return 0;
    }
    else if(a == b) {
        cout << 1 << endl;
        return 0;
    }
    else {
        if(n == 1) {
            cout << 0 << endl;
            return 0;
        }
        else {
            ll ans = (ll)(n-2)*(b-a) + 1;
            cout << ans << endl;
            return 0;
        }
    }
}

Measured memory_bytes: 256
import collections

N=int(input())
c=collections.Counter(list(map(int,input().split())))

l4=sorted([Ai for Ai in c if c[Ai]>=4])
l2=sorted([Ai for Ai in c if c[Ai]>=2])

S=R=0

if len(l4)>=1:
    S=l4[-1]**2
if len(l2)>=2:
    R=l2[-1]*l2[-2]

print(max(S,R))

Measured memory_bytes: 68760
#include <bits/stdc++.h>
#include <math.h>
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rrep(i, n) for(int i = 0; i <= (n); i++)
using namespace std;
typedef long long ll;
const int MOD = 1000000007;
const ll INF = 1LL<<60;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
using Graph = vector<vector<int>>;

typedef pair<int, int> P;


int main(){
    int N; cin >> N;
    string S; cin >> S;
    string ans = "";
    int left_count = 0;
    for (int i = 0; i < N ; i++){
        if (S[i] == '('){
            left_count++;
        }
        else{
            if (left_count > 0){
                left_count--;
            }
        }
    }
    int right_count = 0;
    for (int i = N-1; i >= 0; i--){
        if (S[i] == ')'){
            right_count++;
        }
        else{
            if (right_count > 0){
                right_count--;
            }
        }
    }
    if (right_count > 0){
        rep(i,right_count){
            ans += '(';
        }
    }
    ans += S;
    if (left_count > 0){
        rep(i, left_count){
            ans += ')';
        }
    }

    cout << ans << endl;
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;

//21:20
    class Program
    {
        static void Main(string[] args)
        {
            string line1 = Console.ReadLine();

            int N = int.Parse(line1);

            // List<int> Nums = new List<int>(line1.Split(' ').Select((arg) => int.Parse(arg)));

            Console.Write(N*N*N);

        }
    }

Measured memory_bytes: 13140
#include <iostream>
#include <cstdio>
#include <climits>
#include <cmath>
#include <algorithm>
#include <utility>
#include <vector>
#include <string>

using namespace std;

template <typename T>
class BinarySearchTree
{
private:
  struct Node
  {
    T key;
    Node *right, *left, *parent;
  };
  void inorder(Node *u)
  {
    if(u == NIL) return;
    inorder(u->left);
    cout << " " << u->key;
    inorder(u->right);
  }
  void preorder(Node *u)
  {
    if(u == NIL) return;
    cout << " " << u->key;
    preorder(u->left);
    preorder(u->right);
  }

public:
  Node *root, *NIL;
  BinarySearchTree()
  {
    root = new Node;
    NIL = new Node;
    NIL->parent = NIL;
    NIL->left = NIL;
    NIL->right = NIL;
    root = NIL;
  }
  ~BinarySearchTree(){}
  void insert(int k)
  {
    Node *x = root;
    Node *y = NIL;
    Node *z;
    z = new Node;
    z->key = k;
    z->left = NIL;
    z->right = NIL;
    while(x != NIL)
    {
      y = x;
      if(z->key < x->key)
        x = x->left;
      else
        x = x->right;
    }
    z->parent = y;
    if(y == NIL)
      root = z;
    else
    {
      if(z->key < y->key)
        y->left = z;
      else
        y->right = z;
    }
  }
  bool find(int k)
  {
    Node* u = root;
    while (u != NIL && k != u->key)
    {
      if(k < u->key) u = u->left;
      else u = u->right;
    }
    return u != NIL;
  }
  void dispPre(){preorder(root);cout << endl;}
  void dispIn(){inorder(root);cout << endl;}
  void print(){dispIn();dispPre();}
};

int main()
{
  int n, x;
  string com;
  cin >> n;
  BinarySearchTree<int> T;
  for(int i = 0; i < n; i++)
  {
    cin >> com;
    if(com == "find")
    {
      cin >> x;
      cout << (T.find(x)?"yes":"no") << endl;
    }
    else if(com == "insert")
    {
      cin >> x;
      T.insert(x);
    }
    else if(com == "print")
    {
      T.print();
    }
  }
  return 0;
}

Measured memory_bytes: 19960
#include<iostream>
#include<cmath>
#include<vector>

using namespace std;
int main() {
	int D, N,ans,i,j,k,l,m,flag,sum;
	sum = 0;
	cin >> N;
	vector<long long int>a(N);
	for (i = 0; i < N; i++) {
		cin >> a[i];
		while (a[i] % 2 == 0) {
			a[i] /= 2;
			sum += 1;
		}
	}
	cout << sum << endl;


	return 0;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
typedef vector<ll> vl;
typedef vector<string> vs;
typedef vector<char> vc;
typedef queue<ll> ql;
typedef deque<ll> dql;
typedef priority_queue<ll/*, vl, greater<ll>*/> pql; //降順(/*昇順*/)
typedef set<ll> sl;
typedef pair<ll, ll> pl;
typedef vector<vl> vvl;
typedef vector<pl> vpl;
#define rep(i, n) for(ll i = 0; i < ll(n); i++)
#define rep2(i, n) for(ll i = 1; i <= ll(n); i++)
//#define rep(i, k, n) for(ll i = k-1; i < ll(n); i++)
//#define rep2(i, k, n) for(ll i = k; i <= ll(n); i++)
#define all(v) (v).begin(), (v).end()
bool chmin(ll &a, ll b) {if(b < a) {a = b; return 1;} return 0;}
bool chmax(ll &a, ll b) {if(b > a) {a = b; return 1;} return 0;}
const ll INF = 1LL << 60;
const ll MOD = 1e9 + 7;
//const ll MOD = 998244353;
const ll MAX = 1e9;
const char newl = '\n';

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

  ll n;
  cin >> n;
  
  ll num, ans=0;
  vl cnt(1e5+1);
  rep(_, n) {
    cin >> num;
    if(num>1e5) ans++;
    else cnt[num]++;
  }
  rep2(i, 1e5) {
    if(cnt[i]>=i) ans += cnt[i]-i;
    else ans += cnt[i];
  }
  cout << ans << newl;
  return 0;
}

Measured memory_bytes: 3996
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<string>
#include<map>
#include<cmath>
#include<queue>	

using namespace std;

namespace MyLib {
#define ALL(a) a.begin(),a.end()
#define REP(i,n) for(int i=0;i<n;i++)
#define RREP(i,n) for(int i=n-1;i>=0;i--)
#define debug(x) if(1)cout<<#x<<":"<<x<<endl;
#define DEBUG(x) if(1)cout<<#x<<":"<<x<<endl;
#define ll long long
}
using namespace MyLib;

int ten[10];
int main() {
	int q;
	int r;
	int count;
	ten[0] = 1;
	REP(i, 8)
		ten[i + 1] = ten[i] * 10;
	cin >> q;
	REP(i, q) {
		cin >> r;
		if (r == 1000000) {
			cout << 1 << endl;
			break;
		}
		for (count = 0;; count++) {
			if (r < 10)
				break;
			int ma = 0;
			REP(j, 6) {
				int k = r / ten[j];
				int s = r - (r / ten[j])*ten[j];
				ma = max(ma, k*s);

			}
			r = ma;

		}
		cout << count << endl;



	}



	return 0;
}

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

using namespace std;

int main()
{

   int i,b,c,sum;
   cin>>b;
   sum=0;
   for(i=1;i<=b;i++)
   {
       sum=sum+i;
       c=sum;

   }
cout<<c<<endl;


    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i,b) for(int i=1;i<=b;i++)
#define drep(i,b) for(int i=b;i>=1;i--)
#define Rep(i,a,b) for(int i=a;i<=b;i++)
#define int long long
#define endl '\n'
using namespace std;
const int N=2e5+5;
const int mod=1e9+7;
int n,m,k,t,x,y,z;
//pr
//
#define mid (l+r)/2
#define ls i<<1
#define rs i<<1|1
//vec
//alg


void solve(int sum=0) {
    int a,b;
    cin>>n;
    cin>>a>>b;
    if(a%n==0) {
        cout<<"OK"<<endl;
        return ;
    }
    n=n*(a/n+1);
    if(n<=b) cout<<"OK"<<endl;
    else cout<<"NG"<<endl;
}

#undef int
int main() {
    ios::sync_with_stdio(false);
    //int T;cin>>T;
    //while(cin>>n>>m)
        solve();
}


Measured memory_bytes: 3652
import math
import sys
import itertools
MAX_INT = int(10e12)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

s = S()
K = I()
N = len(s)

start = s[0]
left = 0
right = 0
f = 0
for i in range(N):
  if f == 0:
    if s[i] == start:
      left = i
    else:
      f = 1
if f == 0:
  ans = N*K//2
  print(ans)
else:
  if s[0] == s[-1]:
    f = 0
    for i in range(N-1,-1,-1):
      if f == 0:
        if s[i] == start:
          right = i
        else:
          f = 1
    left = left +1

    #print(left)
    #print(right)
    #print(((left + (N-right))//2)*(K-1))
    ans = ((left + (N-right))//2)*(K-1) + left//2  + (N-right)//2
  else:
    ans = 0
    left = 0
    right = N
  tmp = 0
  t = ""
  for i in range(left,right):
    if t == s[i]:
      tmp += 1
    else:
      t = s[i]
      tmp = 1
    if tmp%2 == 0:
      ans += K
  print(ans)

Measured memory_bytes: 38520
n = int(input())
b = list(map(int,input().split()))
c = []
for i in range(n):
  j = n-i-1
  while j >= 0 :
    if b[j] == j+1:
      del b[j]
      c.append(j+1)
      j = -1
    else:
      j -= 1
if len(c) != n:
  print(-1)
  exit()  
c.reverse()
for ci in c:
  print(ci)
      
    
      
      
      
    



Measured memory_bytes: 3060
#include <string>
#include <iostream>
#include <vector>
#include <algorithm> 
using namespace std;
int main()
{
	int flag=0;
	string s,t;
    cin>>s;
    cin>>t;
    for(int i=0;i<s.length();i++)
    {
    	if(s[i]!=t[i])
        {
        	flag=1;
            break;
        }
        
    }
    
   	if(flag==0)
    {
    	if(s.length()+1==t.length())
        	cout<<"Yes";
        else
        	cout<<"No";
    }
    else 
     	cout<<"No";
        
        
     return 0;
     
     
}
    

Measured memory_bytes: 3624
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<sstream>
#include<cmath>
#include<numeric>
#include<map>
#include<stack>
#include<queue>
#include<list>
#include<set>
#include<cstring>
using namespace std;
long long int mod = 1e9 + 7;
int main() {
  int n; cin >> n;
  string s; cin >> s;
  vector<long long int> a(26, 0);
  for(int i=0; i<s.size(); i++){
    a[s[i]-'a']++;
  }

  long long int cnt = 1;
  for(int i=0; i<26; i++) {
    cnt *= (a[i]+1);
    cnt %= mod;
  }
  cnt += mod-1;
  cnt %= mod;

  cout << cnt << endl;


  return 0;
}



//EOF


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

vector<bool> furui_bool(int n) {
  vector<bool> fu(n + 1, 1);
  fu.at(0) = 0; fu.at(1) = 0;
  for (int i=2; i <= n/2 + 1; i++) {
    if (fu.at(i) == 1) {
      int j = 2 * i;
      while (j <= n) {
        fu.at(j) = 0;
        j += i;
      }
    }
  }
  return fu;
}

int main() {
  int x;
  cin >> x;
  vector<bool> out = furui_bool(100003);
  for(int i=x;i<100004;i++){
    if(out.at(i)){
      cout << i << endl;
      break;
    }
  }
}


Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <numeric>
#include <functional>
#include <cmath>
#include <queue>
#include <stack>
#include <bitset>
#include <map>
#include <string>
#include <utility>

#define repd(i,a,b) for(ll i=(a);i<(b);i++)
#define rep(i,n) repd(i,0,n)
typedef long long ll;

using namespace std;

int inputValue(){
	int a;
	cin >> a;
	return a;
}

void inputArray(int *p,int a){
	rep(i,a){
		cin >> p[i];
	}
}

void inputVector(vector<int> *p,int a){
	rep(i,a){
		int input;
		cin >> input;
		p -> push_back(input);
	}
}

template <typename T>
void output(T a,int precision){
	if(precision > 0){
		cout << setprecision(precision) << a << "\n";
	}else{
		cout << a << "\n";
	}
}

string shape(string str){
	int index1=0,index2=str.size()-1;
	rep(i,str.size()-1){
		if(str[i]=='#'){
			index1=i;
			break;
		}
	}

	for(int i=str.size()-1;i>=0;i--){
		if(str[i]=='.'){
			index2=i;
			break;
		}
	}

	return str.substr(index1,index2-index1+1);
}

int main(){
	//source
	int n;
	string s;
	cin >> n;
	cin >> s;
	int num_white=0,num_black=0;

	rep(i,n){
		if(s[i]=='.'){
			num_white++;
		}
	}
	int ans=num_white+num_black;

	rep(i,n){
		if(s[i]=='.'){
			num_white--;
		}else{
			num_black++;
		}
		ans=min(ans,num_white+num_black);
	}

	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 640
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=1e5+5;
char s[N];
int main()
{
    int n;
    scanf("%s",s+1);
    n=strlen(s+1);
    int cnt=0;
    int ans=0;
    for(int i=1;i<=n;i++){
        if(s[i]=='g')
            if(cnt)
                ans++,cnt--;
            else
                cnt++;
        else
            if(cnt)
                cnt--;
            else
                ans--,cnt++;
    }
    printf("%d\n",ans);
}


Measured memory_bytes: 888
#include<iostream>
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#include <iomanip>//setprecision
#include<math.h>
#include <functional>
#include<climits>
using namespace std;
#define rep(i, n)        for(int i=0; i<(int)(n); ++i)
#define ll  long long 
  vector<ll>to[1000005];
int main(){
  double a,b,c,d;cin>>a>>b>>c>>d;
  cout<<a*b/2<<" ";
  if(a/2==c&&b/2==d)cout<<1;
  else cout<<0;
}


Measured memory_bytes: 23680
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <climits>
#include <ctime>
#include <queue>
#include <stack>
#include <algorithm>
#include <list>
#include <vector>
#include <set>
#include <map>
#include <iostream>
#include <deque>
#include <complex>
#include <string>
#include <iomanip>
#include <sstream>
#include <bitset>
#include <valarray>
#include <iterator>
using namespace std;
typedef long long int ll;
typedef unsigned int uint;
typedef unsigned char uchar;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef vector<int> vi;

#define REP(i,x) for(int i=0;i<(int)(x);i++)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();i++)
#define RREP(i,x) for(int i=((int)(x)-1);i>=0;i--)
#define RFOR(i,c) for(__typeof((c).rbegin())i=(c).rbegin();i!=(c).rend();i++)
#define ALL(container) container.begin(), container.end()
#define RALL(container) container.rbegin(), container.rend()
#define SZ(container) ((int)container.size())
#define mp(a,b) make_pair(a, b)
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );

template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }
template<class T> ostream& operator<<(ostream &os, const vector<T> &t) {
os<<"["; FOR(it,t) {if(it!=t.begin()) os<<","; os<<*it;} os<<"]"; return os;
}
template<class T> ostream& operator<<(ostream &os, const set<T> &t) {
os<<"{"; FOR(it,t) {if(it!=t.begin()) os<<","; os<<*it;} os<<"}"; return os;
}
template<class S, class T> ostream& operator<<(ostream &os, const pair<S,T> &t) { return os<<"("<<t.first<<","<<t.second<<")";}

const int INF = 1<<28;
const double EPS = 1e-8;
const int MOD = 1000000007;

int n, q;
const int BLOCK = 255;
main(){
	ios::sync_with_stdio(false);
	while(cin >> n >> q, n){
		vector< vector<pii> > g(n);
		REP(i, n-1){
			int p; cin >> p; p--;
			g[p].emplace_back(i+1, 1);
		}
		vector<pii> res(n);
		REP(i, n) res[i] = pii(INF, 0);
		ll sum = 0;
		REP(i, q){
			char c;
			int v;
			cin >> c >> v; v--;
			if(c == 'Q'){
				sum += res[v].second+1;
			}else{
				queue<pair<pii, int>> que;
				que.emplace(pii(0, v), v);
				while(!que.empty()){
					pii c = que.front().first;
					const int v = que.front().second;
					que.pop();
					if(res[v] < c) continue;
					res[v] = c;
					c.first ++;
					FOR(e, g[v]){
						if(chmin(res[e->first], c))
							que.emplace(c, e->first);
					}
				}
			}
		}
		cout << sum << endl;
	}
	return 0;
}

Measured memory_bytes: 7416
#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin >> n;
    map<int, int> odds;
    map<int, int> evens;
    for(int i = 0; i < n; i++) {
        int v;
        cin >> v;
        if(i % 2 == 0) {
            evens[v]++;
        } else {
            odds[v]++;
        }
    }

    vector<pair<int, int>> odds_freq(0);
    vector<pair<int, int>> evens_freq(0);
    for(pair<int, int> kv : odds) {
        odds_freq.push_back({kv.second, kv.first});
    }
    for(pair<int, int> kv : evens) {
        evens_freq.push_back({kv.second, kv.first});
    }
    sort(odds_freq.begin(), odds_freq.end(), greater<pair<int, int>>());
    sort(evens_freq.begin(), evens_freq.end(), greater<pair<int, int>>());

    int ans = 0;
    if(odds_freq.at(0).second == evens_freq.at(0).second) {
        int ans1 = 0;
        for(int i = 1; i < odds_freq.size(); i++) {
            ans1 += odds_freq.at(i).first;
        }
        for(int i = 0; i < evens_freq.size(); i++) {
            if(i == 1) {
                continue;
            }
            ans1 += evens_freq.at(i).first;
        }
        int ans2 = 0;
        for(int i = 0; i < odds_freq.size(); i++) {
            if(i == 1) {
                continue;
            }
            ans2 += odds_freq.at(i).first;
        }
        for(int i = 1; i < evens_freq.size(); i++) {
            ans2 += evens_freq.at(i).first;
        }
        ans = min(ans1, ans2);
    } else {
        for(int i = 1; i < odds_freq.size(); i++) {
            ans += odds_freq.at(i).first;
        }
        for(int i = 1; i < evens_freq.size(); i++) {
            ans += evens_freq.at(i).first;
        }
    }

    cout << ans << endl;

    return 0;
}

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

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

int main() {
    int N;
    ll ans = 1e12;
    cin >> N;
    for (int a=1; a<N; ++a) {
        int b = N-a;
        string as = to_string(a), bs = to_string(b);
        ll at = 0; rep(i, as.size()) at += (as[i]-'0');
        ll bt = 0; rep(i, bs.size()) bt += (bs[i]-'0');
        ans = min(ans, at+bt);
    }
    cout << ans << endl;
}


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

int main(){
 
    string a;
    cin >> a;
    for (int i = 0; i < 3; i++)
    {
        if(a[i] == '1'){
            a[i] = '9';
        }else{
            a[i] = '1';
        }
    }
    
    cout << a << endl;

    
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

int32_t main()
{
	//freopen("input.txt", "r", stdin);
	IOS;
	
	int d; cin >> d;
	int t; cin >> t;
	int s; cin >> s;

	if(s*t >= d) {
		cout << "Yes\n";
	}
	else {
		cout << "No\n";
	}
	return 0;
}

Measured memory_bytes: 3632
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <queue>
#include <cstring>
#include <vector>
#include <map>
#include <algorithm>
#include <cctype>
#include <cmath>
#include <bitset>
#include <set>
#include <stack>
using namespace std;

#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define RREP(i,n) for(int i=n-1;i>=0;i--)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);i++)
#define all(i,n) (i),(i+n)

int dx4[4]={1,0,-1,0};
int dy4[4]={0,-1,0,1};
int dx8[8]={1,0,-1,1,-1,1,0,-1};
int dy8[8]={1,1,1,0,0,-1,-1,-1};
int dx9[9]={0,1,0,-1,1,-1,1,0,-1};
int dy9[9]={0,1,1,1,0,0,-1,-1,-1};

typedef pair<int, int> P;
typedef pair<string, int> SP;
typedef long long ll;
typedef pair<ll, ll> PLL;

const int INF = 1e9;
const ll LLINF = 1e18;
const int MAX_V = 1e6+1;
const ll mod = 1000000007;
// << fixed << setprecision
// --------------------------------------
ll n, k;
ll dp[64][2];
int bit_count(ll t) {
  int c = 0;
  while(t) {
    t /= 2;
    c++;
  }
  return c;
}
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);

  cin >> n >> k;

  int ma = bit_count(k);
  vector<ll> a(n);
  REP(i, n) {
    cin >> a[i];
    ma = max(bit_count(a[i]), ma);
  }

  vector<ll> bs(ma, 0);
  REP(i, n) {
    int c = 1;
    ll t = a[i];
    while(t) {
      if(t % 2) bs[ma - c]++;
      c++;
      t /= 2;
    }
  }

  bool under = false;
  REP(i, ma) {
    if(1LL << (ma - (i + 1)) > k) {
      dp[i + 1][0] = dp[i][0] + bs[i] * (1LL << (ma - (i + 1)));
    } else {
      if(under) {
        dp[i + 1][1] = dp[i][1] + max(bs[i], n - bs[i]) * (1LL << (ma - (i + 1)));
      }
      if(1LL << (ma - (i + 1)) & k) {
        dp[i + 1][0] = max(dp[i + 1][0], dp[i][0] + (n - bs[i]) * (1LL << (ma - (i + 1))));
        dp[i + 1][1] = max(dp[i + 1][1], dp[i][0] + bs[i] * (1LL << (ma - (i + 1))));
        under = true;
      } else {
        dp[i + 1][0] = max(dp[i + 1][0], dp[i][0] + bs[i] * (1LL << (ma - (i + 1))));
      }
    }
  }

  cout << max(dp[ma][0], dp[ma][1]) << endl;
}


Measured memory_bytes: 3988
#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>;

const ll MOD = 1e9 + 7;

vector<ll> mf(100009, -1);

ll modfact(ll n) {
  if (mf[n] != -1) return mf[n];
  if (n == 0) return mf[0] = 1;
  else return mf[n] = n * modfact(n-1) % MOD;
}

int main() {
  ll n, m;
  cin >> n >> m;
  ll ans;
  if (n == m) ans = 2 * modfact(n) * modfact(m) % MOD;
  else if (abs(n - m) == 1) ans = modfact(n) * modfact(m) % MOD;
  else ans = 0;
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 5532