akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <functional>

template <class T>
struct SegmentTree {
    using Merger = std::function<T(T, T)>;

    int length;
    std::vector<T> dat;
    T unit;
    Merger merge;

    SegmentTree() = default;

    SegmentTree(int n, const T& unit, const Merger& merge)
        : length(1), unit(unit), merge(merge) {
        while (length < n) length <<= 1;
        dat.assign(length * 2, unit);
    }

    template <class Container>
    SegmentTree(const Container& elems, const T& unit, const Merger& merge)
        : length(1), unit(unit), merge(merge) {
        int n = elems.size();
        while (length < n) length <<= 1;

        dat.assign(length * 2, unit);

        std::copy(elems.begin(), elems.end(), dat.begin() + length);

        for (int nidx = length - 1; nidx >= 1; --nidx) {
            T vl = dat[nidx * 2 + 0];
            T vr = dat[nidx * 2 + 1];
            dat[nidx] = merge(vl, vr);
        }
    }

    void update(int nidx, const T& elem) {
        nidx += length;
        dat[nidx] = elem;

        while (nidx > 0) {
            nidx >>= 1;
            T vl = dat[nidx * 2 + 0];
            T vr = dat[nidx * 2 + 1];
            dat[nidx] = merge(vl, vr);
        }
    }

    T fold(int ql, int qr) const {
        ql = std::max(ql, 0);
        qr = std::min(qr, length);
        ql += length, qr += length;

        T lacc = unit, racc = unit;
        while (ql < qr) {
            if (ql & 1) {
                lacc = merge(lacc, dat[ql]);
                ++ql;
            }
            if (qr & 1) {
                --qr;
                racc = merge(dat[qr], racc);
            }
            ql >>= 1, qr >>= 1;
        }

        return merge(lacc, racc);
    }

    T get(int idx) const { return dat[idx + length]; }
    T fold_all() const { return dat[1]; }
};

void solve() {
    int n, q;
    std::cin >> n >> q;

    std::vector<int> cs(n);
    for (auto& c : cs) {
        std::cin >> c;
        --c;
    }

    std::vector<std::queue<int>> pos(n);
    for (int i = 0; i < n; ++i) {
        pos[cs[i]].push(i);
    }

    std::vector<std::vector<std::pair<int, int>>> qs(n);
    for (int i = 0; i < q; ++i) {
        int l, r;
        std::cin >> l >> r;
        qs[--l].emplace_back(--r, i);
    }

    SegmentTree<int> seg(n, 0, [](auto a, auto b) { return a + b; });
    for (int i = 0; i < n; ++i) {
        if (!pos[i].empty()) {
            seg.update(pos[i].front(), 1);
            pos[i].pop();
        }
    }

    std::vector<int> ans(q);
    for (int l = 0; l < n; ++l) {
        for (auto [r, i] : qs[l]) {
            ans[i] = seg.fold(l, r + 1);
        }

        int c = cs[l];
        if (!pos[c].empty()) {
            seg.update(pos[c].front(), 1);
            pos[c].pop();
        }
    }

    for (auto a : ans) std::cout << a << "\n";
}

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

    solve();

    return 0;
}


Measured memory_bytes: 370936
import sys
from sys import exit
from collections import deque
from bisect import bisect_left, bisect_right, insort_left, insort_right #func(リスト,値)
from heapq import heapify, heappop, heappush
from math import *

sys.setrecursionlimit(10**6)
INF = 10**20
eps = 1.0e-20
MOD = 10**9+7

def lcm(x,y):
    return x*y//gcd(x,y)
def mint():
    return map(int,input().split())
def lint():
    return list(map(int,input().split()))
def ilint():
    return int(input()), list(map(int,input().split()))
def judge(x, l=['Yes', 'No']):
    print(l[0] if x else l[1])
def lprint(l, sep='\n'):
    for x in l:
        print(x, end=sep)
def ston(c, c0='a'):
    return ord(c)-ord(c0)
def ntos(x, c0='a'):
    return chr(x+ord(c0))
class counter(dict):
    def __init__(self, *args):
        super().__init__(args)
    def add(self,x):
        self.setdefault(x,0)
        self[x] += 1

N = int(input())
work = []
for _ in range(N):
    a,b = mint()
    work.append([a,b])
work.sort(key=lambda x:x[1])
t = 0
ans = True
for a,b in work:
    if t+a>b:
        ans = False
        break
    t += a
judge(ans)

Measured memory_bytes: 113120
#include<cstdio>
#include<utility>
#include<vector>
#include<algorithm>

using namespace std;

typedef pair<int, int> P;

const int inf = 1000000000 + 100;
const long long mod = 1000000007;

struct BIT{
	int N;
	long long dat[100100];
	void init(int N_){
		N = N_;
	}
	void add(int id, long long x){
		while(id <= N){
			dat[id] = (dat[id] + x) % mod;
			id += (id & (-id));
		}
	}
	long long sum(int id){
		long long ans = 0;
		while(id > 0){
			ans = (ans + dat[id]) % mod;
			id -= (id & (-id));
		}
		return ans;
	}
	long long sum(){
		return sum(N);
	}
};

BIT bit;

int N, M;
int X[100100];
int Y[100100];

void input(){
	scanf("%d%d", &N, &M);
	for(int i = 0; i < N; ++i){
		scanf("%d", X + i);
	}
	Y[0] = -1;
	for(int i = 1; i <= M; ++i){
		scanf("%d", Y + i);
	}
	Y[M + 1] = inf;
	M += 2;
}


vector<P> ps;

long long dp[100100];

vector<int> vals;

int getId(int x){
	return lower_bound(vals.begin(), vals.end(), x) - vals.begin() + 2;
}

long long solve(){
	for(int i = 0; i < N; ++i){
		int id = lower_bound(Y, Y + M, X[i]) - Y;
		int n = Y[id];
		int p = Y[id - 1];
		if(p == -1 || n == inf) continue;
		ps.push_back(P(X[i] - p, -(n - X[i])));
		vals.push_back(n - X[i]);
	}
	if(ps.size() == 0) return 1;
	sort(ps.begin(), ps.end());
	ps.erase(unique(ps.begin(), ps.end()), ps.end());
	sort(vals.begin(), vals.end());
	vals.erase(unique(vals.begin(), vals.end()), vals.end());
	bit.init(vals.size() + 1);
	bit.add(1, 1);
	for(int i = 0; i < ps.size(); ++i){
		P p = ps[i];
		int id = getId(-p.second);
		bit.add(id, bit.sum(id - 1));
	}
	long long ans = bit.sum();
	ans %= mod;
	ans += mod;
	ans %= mod;
	return ans;
}

int main(){
	input();
	long long ans = solve();
	printf("%lld\n", ans);
	return 0;
}


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


int main()
{
//	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);

	int n;
	cin >> n;
	int m = 1;
	while(m * (m + 1) < 2 * n) m++;
	int sum = m * (m + 1) / 2;
	sum -= n;
	for (int i = 1; i <= m; i++)
		if (i != sum)
			cout << i << endl;

	return 0;
}

Measured memory_bytes: 256
import numpy as np
Sa = input()
Sb = input()
Sc = input()

def string2int(in_list):
    out_list = np.array(in_list, dtype='S')
    out_list[out_list==b'a'] = 0
    out_list[out_list==b'b'] = 1
    out_list[out_list==b'c'] = 2
    return np.array(out_list, dtype=int)
Sa = string2int(list(Sa))
Sb = string2int(list(Sb))
Sc = string2int(list(Sc))
ALL = [list(Sa), list(Sb), list(Sc)]

current = 0
pre = 0
while True:
    left = len(ALL[current])
    if left == 0:
        break
    current = ALL[current][0]
    ALL[pre] = ALL[pre][1:]
    pre = current

cor = ['A','B','C']
print( cor[current] )

Measured memory_bytes: 20764
#include<stdio.h>
#include<limits.h>

int main(){
  int n,i;
  int a=0;
  long min=LONG_MAX;
  long max=LONG_MIN;
  long sum=0;

  scanf("%d",&n);

  for(i=0;i<n;i++)
    {
      scanf("%d",&a);
      
      if(max < a)
	{
	  max = a;
	}
      if(min > a)
	{
	  min = a;
	}
      sum += a;
    }
  printf("%ld %ld %ld\n",min,max,sum);

  return 0;
}



Measured memory_bytes: 2104
#include <stdio.h>

int main(){
    int a,b,res;
    
    scanf("%d %d",&a,&b);
    
    res=a*b;
    
    if(res%2==0){
        printf("Even\n");
    }
    
    else{
        printf("Odd\n");
    }
    
    return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <sstream>
#include <stack>
#include <iomanip>
#include <string>
#include <algorithm>
#include <functional>
#include <cstdlib>
#include <map>
#include <set>
#include <vector>
#include <utility>
#include <queue>
#include <cmath>

#define BEGIN(x) x.begin()
#define END(x) x.end()
#define ALL(x) BEGIN(x), END(x)
#define PAIR make_pair
#define VEC(type) vector<type >

#define FOR(i, A, B) for(auto i = (A);i != (B); i++)
#define FORD(i, A, B) for(auto i = (A);i != (B); i--)

#define READRANGE(begin, end) FOR(it, begin, end) cin >> *it
#define READVEC(V) READRANGE(BEGIN(V), END(V))

using namespace std;

typedef long long lint;
typedef pair<int, int> Pii;
typedef pair<int, lint> Pil;
typedef pair<lint, lint> Pll;
typedef pair<lint, int> Pli;

// ---- BEGIN LIBRARY CODE ----
// ---- END LIBRARY CODE ----
void io_init()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
};

int main(int argc, char **argv)
{
    io_init();

    // Actual program code starts here.
    string S;
    int n;
    cin >> n >> S;
    int ret = S.size();
    int allWhites = count(ALL(S), '.'), blacks = 0;
    FOR(i, 0, S.size() + 1) {
        ret = min(ret, 2 * blacks + allWhites - i);
        if (i < S.size())
            blacks += S[i] == '#';
    }

    cout << ret << endl;
    return 0;
};


Measured memory_bytes: 720
#include<bits/stdc++.h>
using namespace std;
long long n;
int main()
{
	cin>>n;
	while(n>0)
	{
		if(n%10==9) 
		{
			cout<<"Yes";
			return 0;
		}
		n=n/10;
	}
	cout<<"No";
	return 0;
}


Measured memory_bytes: 256
def main():
    s = input()
    n = len(s)

    print('x' * n)


if __name__ == '__main__':
    main()

# import sys
#
# sys.setrecursionlimit(10 ** 7)
#
# input = sys.stdin.readline
# rstrip()
# int(input())
# map(int, input().split())


Measured memory_bytes: 2940
#include <iostream>
#include <set>
#include <string>
#define rep(i, n) for (int i = 0; (i) < (int)(n); i++)
using namespace std;

int main() {
	set<string> s;
	int N;
	cin >> N;
	rep(i, N) {
		string str;
		cin >> str;
		s.insert(str);
	}
	cout << s.size() << endl;
	return 0;
}

Measured memory_bytes: 19224
import java.io.BufferedReader

class Node(val id: Int) {
    private val links: MutableSet<Node> = mutableSetOf()
    override fun equals(other: Any?): Boolean {
        other.let {
            if (it is Node && this.id == it.id) {
                return true
            }
        }
        return super.equals(other)
    }

    fun addLink(n: Node) {
        this.links.add(n)
    }

    fun getLinks(): Set<Int> {
        return this.links.map(Node::id).toSet()
    }
}

fun main(args: Array<String>) {
    /** comment in when you submit **/
    System.`in`.bufferedReader().use { println(getOutputString(it)) }

    /** delete below after your test **/
    //executeTest()
}

private fun getOutputString(reader: BufferedReader): String {
    val (n, m) = reader.readLine().let {
        val d = it.split(" ")
        Pair(d[0].toInt(), d[1].toInt())
    }
    val nodes = (1..n).map {
        Pair(it, Node(it))
    }.toMap()
    reader.readLines().forEach {
        val d = it.split(" ")
        Pair(d[0].toInt(), d[1].toInt())
        nodes[d[0].toInt()]?.let { base ->
            nodes[d[1].toInt()]?.let { dest ->
                base.addLink(dest)
                dest.addLink(base)
            }
        }
    }
    return culc(1, nodes, nodes.keys.toMutableList()).toString()
}

private fun culc(current: Int, nodes: Map<Int, Node>, cands: MutableList<Int>): Int {
    return nodes[current]?.let {
        if (cands.count() == 1 && cands[0] == current) {
            return 1
        }

        cands.remove(current)

        it.getLinks().filter { l -> l in cands }
                .map { culc(it, nodes, cands.map { it }.toMutableList()) }.sum()
    } ?: 0
}

/** delete below after your test **/
private fun String.mustBe(expected: String): Unit {
    if (this != expected) throw Exception("\"$this\" must be \"$expected\"")

    println("ok")
}

private fun executeTest() {
    getOutputString("3 3\n1 2\n1 3\n2 3".toByteArray(Charsets.UTF_8).inputStream().bufferedReader()).mustBe("2")
    getOutputString("7 7\n1 3\n2 7\n3 4\n4 5\n4 6\n5 6\n6 7".toByteArray(Charsets.UTF_8).inputStream().bufferedReader()).mustBe("1")
}


Measured memory_bytes: 39112
#include<bits/stdc++.h>
#define ls(x) (x)<<1
#define rs(x) (x)<<1|1
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define ll rt<<1
#define rr rt<<1|1
#define PI acos(-1)
#define MM int m=(l+r)>>1;
#define fu(i,r,t) for(int i=r;i<=t;i++)
#define fd(i,r,t) for(int i=r;i>=t;i--)
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define int long long
#define endl '\n'
#define lcm(a,b) (a*b)/__gcd(a,b)
#define Case(i,ans) cout<<"Case "<<i<<": "<<ans<<endl;
#define cp(i,ans) printf("%.if",ans);
#define cpp(i,ans) cout<<setprecision(i)<<fixed<<ans<<endl;
#define ppb pop_back
#define ppf pop_front
#define pb push_back
#define pf push_front
#define pq priority_queue
#define lowbit(x) (x)&(-x)
#define all(V) V.begin(),V.end()
#define ms multiset
#define mod(x) ((x+mo_num)%mo_num)
#define vc vector
#define vct vector<int>
#define fa(i,V) for(auto i:V)
#define out(i) cout<<(i)<<endl;
#define fi first
#define se second
#define fun(i) fu(i,1,n)
#define fut(i) fu(i,1,t)
#define fum(i) fu(i,1,m)
#define ld long double
//#define P pair<int,int>
using namespace std;
const int INF=LLONG_MAX;
const int maxn=1e6+5;
const int mo_num=1e9+7;
int n,m,a[maxn],b[maxn],ans;

int32_t main()
{
    IOS
    cin>>n>>m;
    fun(i)
    {
        fu(j,10,m)
        {
            int ff=j/10,f=j%10;
            if(ff>=2 && f>=2 && f*ff==i)ans++;
        }
    }
    cout<<ans;
    return 0;
}

Measured memory_bytes: 256
N = int(input())
S = input()

# 任意のi(0≤i≤n-3)について、S[i]以下3文字が'ABC'であるかを確認すればよい
ans = 0
for i in range(N-2):
  if S[i:i+3] == 'ABC': ans += 1
    
print(ans)

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

ll N, AI, cnt1, cnt2, cnt3;

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

	cin >> N;
	for (ll i = 0; i < N; i++) {
		cin >> AI;
		if (AI % 4 == 0) {
			cnt1++;
		}
		else if (AI % 2 == 0) {
			cnt2++;
		}
		else {
			cnt3++;
		}
	}

	if (cnt2 > 0) {
		cnt3++;
	}

	if (cnt3 > cnt1+1) {
		cout << "No\n";
	}
	else {
		cout << "Yes\n";
	}
	
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<string>
std::string S;
#define LL long long
LL ans;
LL mod = 1e9 + 7;
LL D[4][100010];
LL Q;
LL K[4];

void ad(LL X, LL Y,int i) {
	LL add = (X*Y) % mod;
	add *= K[i];
	add %= mod;
	ans += add;
	ans %= mod;
}
int main() {
	std::cin >> S;
	for (int i = 0; i < S.size();i++) {
		if (S[i] == '?') {
			Q++;
			D[3][i]++;
		}
		else D[S[i] - 'A'][i]++;
		for (int j = 0; j < 4; j++) {
			D[j][i + 1] += D[j][i];
		}
	}
	K[0] = 1;
	for (int i = 0; i < Q - 3; i++) {
		K[0] *= 3;
		K[0] %= mod;
	}
	K[1] = (Q - 2 > 0 ? 3 : 1) * K[0];
	K[1] %= mod;
	K[2] = (Q - 1 > 0 ? 3 : 1) * K[1];
	K[2] %= mod;
	K[3] = (Q > 0 ? 3 : 1) * K[2];
	K[3] %= mod;
	for (int i = 0; i < S.size(); i++) {
		if (S[i] == 'B') {
			ad(D[0][i - 1], D[2][S.size() - 1] - D[2][i], 3);
			ad(D[0][i - 1], D[3][S.size() - 1] - D[3][i], 2);
			ad(D[3][i - 1], D[2][S.size() - 1] - D[2][i], 2);
			ad(D[3][i - 1], D[3][S.size() - 1] - D[3][i], 1);
		}
		if (S[i] == '?') {
			ad(D[0][i - 1], D[2][S.size() - 1] - D[2][i], 2);
			ad(D[0][i - 1], D[3][S.size() - 1] - D[3][i], 1);
			ad(D[3][i - 1], D[2][S.size() - 1] - D[2][i], 1);
			ad(D[3][i - 1], D[3][S.size() - 1] - D[3][i], 0);
		}
	}
	std::cout << ans << std::endl;
	return 0;
}

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

int main() {

  int N, K;
  int x=1 ;
  cin >> N >> K;
  for (int i = 0; i < N; i++) {
    if( 2*x <= x+K){x *= 2;
    }
    else{x += K;
    }
  }
 cout << x << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
//#define eps 1e-8
//#define eq(x,y) (fabs((x)-(y)) < eps)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int>pii;
//const int mod = 1e9+7;
long double PI = acosl(-1);
const ll infl = 3e18+100;
const int inf = 1e8+100;
const int nmax = 2e5+5;
const int MAXLG = log2(nmax)+1;
//mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
//typedef tree< int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ost;



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

    int n;
    cin>>n;
    int cnt = 1, cur = n;
    while(cur % 360) cur += n, cnt++;
    cout<<cnt<<endl;
}


Measured memory_bytes: 3632
#include <iostream>
#include <algorithm>
#include <functional>
#include <string>
#include <vector>
#include <utility>
#include <cmath>
#define REP(i, n) for(int i = 0; i < n; i++)
#define SORT(x) sort(x.begin(), x.end())
#define RSORT(x) sort(x.begin(), x.end(), std::greater<int>())
#define swap(a, b) \
  do { typeof(a) __tmp = (a); (a) = (b); (b) = __tmp; } while (0)
#define vi vector<int>
using namespace std;

const double EPS = 1e-10;
const double PI  = acos(-1.0);

int main() {
  
  int n;
  cin >> n;
  REP(i, n) {
    char x;
    cin >> x;
    if(x == 'Y') {
      cout << "Four" << endl;
      return 0;
    }
  }
  cout << "Three" << endl;
  
}


Measured memory_bytes: 256
A = list(input().split())

S = []

for i in range(len(A)):
    if A[i] == '+':
        a = int(S.pop())
        b = int(S.pop())
        S.append(a + b)
    elif A[i] == '-':
        b = int(S.pop())
        a = int(S.pop())
        S.append(a - b)
    elif A[i] == '*':
        a = int(S.pop())
        b = int(S.pop())
        S.append(a * b)
    else:
        S.append(A[i])

print(int(S.pop()))



Measured memory_bytes: 5600
/*Function Template*/
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
const int MAX = 510000;
const int MOD = 1000000007;
#define rep(i, n) for(ll i = 0; i < (n); i++)
#define ALL(a)  (a).begin(),(a).end()
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
ll fac[MAX], finv[MAX], inv[MAX];


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 COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (ll i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }

}
ll Len(ll n) {
  ll s=0;
  while(n!=0) s++, n/=10;
  return s;
}


ll Sint(ll n) {
  ll m=0,s=0,a=n;
  while(a!=0) s++, a/=10;
  for(ll i=s-1;i>=0;i--) m+=n/((ll)pow(10,i))-(n/((ll)pow(10,i+1)))*10;
  return m;
}


ll Svec(vector<ll> v){
  ll n=0;
  for(ll i=0;i<v.size();i++) n+=v[i];
  return n;
}


ll GCD(ll a,ll b){
  ll r,tmp;
/*自然数 a > b を確認・入替*/
  if(a<b){
    tmp=a,a=b,b=tmp;
  }
/*ユークリッドの互除法*/
  r=a%b;
  while(r!=0){
    a=b,b=r,r=a%b;
  }
  return b;
}


ll LCM(ll a,ll b){
  ll c=a,d=b,r,tmp;
/*自然数 a > b を確認・入替*/
  if(a<b){
    tmp=a,a=b,b=tmp;
  }
/*ユークリッドの互除法*/
  r=a%b;
  while(r!=0){
    a=b,b=r,r=a%b;
  }
  return c/b*d;
}


ll Factorial(ll n){
  ll m=1;
  while(n>=1) m*=n,n--;
  return m;
}

vector<pair<char,ll>> runlength(string s,vector<pair<char,ll>> p){
  ll x=1;
  if(s.size()==1){
    p.push_back(pair<char,ll>(s[0],1));
    return p;
  }
  for(ll i=0;i<s.size()-1;i++){
    if(s[i]==s[i+1]){
      x++;
      if(i==s.size()-2){
        p.push_back(pair<char,ll>(s[i],x));
      }
    }else{
      p.push_back(pair<char,ll>(s[i],x));
      x=1;
      if(i==s.size()-2){
        p.push_back(pair<char,ll>(s[s.size()-1],x));
      }
    }
  }
  return p;
}


ll COM(ll n,ll k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

const int MAX_N=100010;
vector<bool> sieve_of_eratosthenes(){
  vector<bool> isPrime(MAX_N+1,true);
  for(int i=2;i<=MAX_N;i++){
    if(isPrime[i]){
      for(int j=2*i;j<=MAX_N;j+=i){
        isPrime[j]=false;
      }
    }
  }
  return isPrime;
}







/*↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓*/
int main() {
  IOS;
  ll n,m;
  cin>>n>>m;
  vector<bool> issafe(n+1,true);
  rep(i,m){
    ll a;cin>>a;
    issafe[a]=false;
  }
  vector<ll> dp(n+1,0);
  dp[0]=1;
  if(issafe[1]) dp[1]=1;
  for(ll i=2;i<=n;i++){
    if(issafe[i-1]) dp[i]+=dp[i-1];
    if(issafe[i-2]) dp[i]+=dp[i-2];
    dp[i]%=MOD;
  }
  cout<<dp[n]<<endl;
  
  
  
  
  
}

Measured memory_bytes: 1024
/*/ Author:amar1503/*/
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize ("Ofast")
#define fio ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define ull unsigned long long
#define ll long long
#define inf INT_MAX
#define mninf INT_MIN
#define Mod 1000000007
#define endl "\n"
#define cp(x) cout<<(x)<<" "
#define cl(x) cout<<(x)<<endl
#define nl   cout<<endl
//const double PI=3.1415926535897932384626433832;
//looping
#define For(i,a,b) for(int i=a;i<b;i++)
#define test(t)  int (t); cin>>(t); while((t)--)
#define array(a,n) int (n); cin>>(n); int a[n]; for(int i=0;i<(n);i++) cin>>a[i];
#define trace(x) clog<<#x<<": "<<x<<" "<<endl
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))
#define printa(a,n) for(int i = 0 ; i < n ; i++) cout<<a[i]<<' '
#define printv(v)  for(int i=0;i<(v).size();i++) cout<<v[i]<<" "
//containers
#define F first
#define S second
#define pb push_back
#define pf push_front
#define pob pop_back
#define pof pop_front
#define all(v) (v).begin(),(v).end()
#define mp make_pair
#define itr(it, a) for(auto it = (a).begin(); it != (a).end(); it++)
#define present(c,x) ((c).find(x) != (c).end())
#define cpresent(c,x) (find(all(c),x) != (c).end())
#define ers(v)    sort(all(v)); (v).erase(unique(all(v)),(v).end())
typedef vector<int> vi;
typedef vector< vector< int > > vvi;
typedef pair <int, int> pii;
typedef vector < pair <int, int> > vpii;
#define int long long
/*/-----------------------------Code begins----------------------------------/*/
int a[100][100001];
int32_t main(){
int n,w;
cin>>n>>w;
int wt[n],val[n];
For(i,0,n){
cin>>wt[i]>>val[i];}
For(i,0,n){
a[i][0]=0;}
//base case
For(j,0,w+1){
if(j<wt[0])
    a[0][j]=0;
    else a[0][j]=val[0];
}
For(i,1,n){
    For(j,1,w+1){
        if(j<wt[i]){
            a[i][j]=a[i-1][j];
        }
        else {
            a[i][j]=max(a[i-1][j],val[i]+a[i-1][j-wt[i]]);
        }

    }
}
cout<<a[n-1][w];
}


Measured memory_bytes: 78336
#!/usr/bin/env python3
import sys
from itertools import combinations

def solve(N: int, A: "List[int]", B: "List[int]"):
    answer = 10**10
 
    ## 奇数indexにくるものを決め打ち
    for c in combinations(range(N), N//2):
        even, odd= [], []
        
        for i in range(N):
            if i in c:
                odd.append((A[i] if i % 2 == 1 else B[i],i))
            else:
                even.append((A[i] if i % 2 == 0 else B[i],i))
    
        even.sort()
        odd.sort()
        t = []
        ind = []
        
        for i in range(N//2):
            t.append(even[i][0])
            t.append(odd[i][0])
            ind.append(even[i][1])
            ind.append(odd[i][1])
        else:
            if N%2 == 1:
                t.append(even[-1][0])
                ind.append(even[-1][1])
        
        if t != sorted(t):
            continue

        tentousuu = 0
        for i in range(N-1):
            for j in range(i+1,N):
                if ind[i] > ind[j]:
                    tentousuu += 1
        
        if answer > tentousuu:
            answer = tentousuu

    if answer == 10**10:
        print(-1)
    else:
        print(answer)
    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    B = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A, B)

if __name__ == '__main__':
    main()


Measured memory_bytes: 3188
#include <bits/stdc++.h>
#define ios ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr)
using namespace std;
typedef long long ll;
const int MAX = 1e5 + 10;
const int mod = 1e9+7;

int a[MAX];
void solve() {
    ll x,k,d;
    cin>>x>>k>>d;
    x=abs(x);
    ll xiao=x%d;
    ll ci=x/d;
    if(ci<=k){
        ll tem=k-ci;
        if(tem%2==0){
            cout <<xiao;
        }else {
            cout << min(abs(xiao + d), abs(xiao - d));
        }
    }else{
        cout<<x-k*d;
    }

}

int main() {
    int _ = 1;
    //cin >> _;
    while (_--) {
        solve();
    }
    return 0;
}

Measured memory_bytes: 3644
#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<math.h>
#include<time.h>
#include<vector>
#include<bitset>
#include<memory>
#include<utility>
#include<fstream>
#include<stdio.h>
#include<sstream>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
int c[200005];
int w[200005];
int min_num[200005];
int sum[200005];
const int modo=1000000007;
int fact[200005];
int anti_fact[200005];
int c_(int x,int y)
{
    return (long long)fact[x]*anti_fact[y]%modo*anti_fact[x-y]%modo;
}
int power(int x,int y)
{
    if (y==0) return 1;
    int t=power(x,y/2);
    t=(long long)t*t%modo;
    if (y%2==1) t=(long long)t*x%modo;
    return t;
}
int main()
{
    #ifdef absi2011
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    int n,x,y;
    scanf("%d%d%d",&n,&x,&y);
    int i;
    for (i=0;i<n;i++)
    {
        min_num[i]=1099999999;
    }
    fact[0]=1;
    anti_fact[0]=1;
    for (i=1;i<=200000;i++)
    {
        fact[i]=(long long)fact[i-1]*i%modo;
        anti_fact[i]=power(fact[i],modo-2);
    }
    for (i=0;i<n;i++)
    {
        scanf("%d%d",&c[i],&w[i]);
        c[i]--;
        min_num[c[i]]=min(min_num[c[i]],w[i]);
    }
    int min1=0,min2=0;
    for (i=0;i<n;i++)
    {
        if (min_num[min1]>min_num[i])
        {
            min1=i;
        }
    }
    if (min1==0) min2=1;
    for (i=0;i<n;i++)
    {
        if (i==min1) continue;
        if (min_num[min2]>min_num[i])
        {
            min2=i;
        }
    }
    int tot=0;
    for (i=0;i<n;i++)
    {
        if (c[i]==min1)
        {
            if (w[i]+min_num[min2]<=y)
            {
                tot++;
                sum[c[i]]++;
                continue;
            }
            else if (w[i]+min_num[min1]<=x)
            {
                tot++;
                sum[c[i]]++;
                continue;
            }
        }
        else
        {
            if (w[i]+min_num[min1]<=y)
            {
                tot++;
                sum[c[i]]++;
                continue;
            }
            else if ((w[i]+min_num[c[i]]<=x)&&(min_num[c[i]]+min_num[min1]<=y))
            {
                tot++;
                sum[c[i]]++;
                continue;
            }
        }
    }
    int p=1;
    for (i=0;i<n;i++)
    {
        p=(long long)p*c_(tot,sum[i])%modo;
        tot-=sum[i];
    }
    printf("%d\n",p);
    return 0;
}


Measured memory_bytes: 4992
#include <iostream>
#include <string>
#include <cstring>
#include <fstream>
#include <random>
#include <cmath>
#include <iomanip>
#include <climits>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <map>
#include <deque>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <list>
#include <unordered_map>
#include <bitset>
#include <sstream>
#include <new>
#include <typeinfo>
#include <iterator>

typedef long long ll;
typedef unsigned long long ull;
constexpr ll mop = 1000000007;
constexpr ll mop2 = 998244353;

using namespace std;

int main() {
	ll numCity, numTeleport;
	cin >> numCity >> numTeleport;
	vector <ll> ToCityList, TimesCityList;
	ToCityList.resize(numCity + 1);
	TimesCityList.resize(numCity + 1, -1);
	for (ll i = 1; i <= numCity; i++) {
		cin >> ToCityList[i];
	}
	ll nowcity = 1;
	ll times = 0;
	while (TimesCityList[nowcity] == -1) {
		TimesCityList[nowcity] = times;
		times++;
		nowcity = ToCityList[nowcity];
		if (numTeleport == times) {
			cout << nowcity << endl;
			return 0;
		}
	}
	ll modTeleport = times - TimesCityList[nowcity];
	ll ansCity = (numTeleport - TimesCityList[nowcity]) % modTeleport + TimesCityList[nowcity];
	for (ll i = 1; i <= numCity; i++) {
		if (TimesCityList[i] == ansCity) {
			cout << i << endl;
			return 0;
		}
	}
} 

Measured memory_bytes: 6404
#include <iostream>
#include <sstream>
#include <functional>
#include <algorithm>
#include <cstring>
#include <fstream>
#include <cmath>
#include <queue>
#include <vector>
#include <bits/stdc++.h>
using namespace std;
# define my_sizeof(type) ((char *)(&type+1)-(char*)(&type))

string makestring(int x)
{
    stringstream ss;
    ss << x;
    return ss.str();
}

int main()
{

    int n, l, t, c=0, x;
    vector<int> v;
    cin >> n >> l;
    for(int i = 0; i < n; i++){
        cin >> t;
        v.push_back(t);
    }
    for(int i = 0; i < n-1; i++){
        t=v[i]+v[i+1];
        if(c<t){
            c=t;
            x=i;
        }

    }
    if(c<l){
        cout << "Impossible";
    } else {
        cout << "Possible" << endl;
        for(int i = 1; i <= x; i++){
            cout << i << endl;
        }
        for(int i = n-1; i > x; i--){
            cout << i << endl;
        }
    }

    return 0;
}




















Measured memory_bytes: 1400
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author
 */

#include <iostream>
#include <fstream>

#include <bits/stdc++.h>

using namespace std;

class ADodecagon {
public:
    void solve(std::istream &in, std::ostream &out) {
        int a;
        in >> a;
        out << 3 * a * a << endl;
    }
};


int main() {
	ADodecagon solver;
	std::istream& in(std::cin);
	std::ostream& out(std::cout);
	solver.solve(in, out);
	return 0;
}


Measured memory_bytes: 256
N, M, C = map(int, input().split())
B = list(map(int, input().split()))
A = [list(map(int, input().split())) for i in range(N)]
ok = 0
for i in range(N):
    if sum([A[i][j]*B[j] for j in range(M)]) + C > 0:
        ok += 1
print(ok)


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


long int N = 0;      //N個の駅がある
long int cost[501] = { 0 };    //駅iからi+1にかかる時間
long int ft[501] = { 0 };      //始発
long int nex[501] = { 0 };     //時間の間隔
long int ans[501] = { 0 };


int cal(long int i,long int time=0) {
	int point = 0;

	if (i == N) { return time; }

	if (time == 0) {          //その駅から出発するとき
		time += cost[i]+ft[i];
		cal(i + 1, time);
	}
	else {                   //違う駅から来たとき

		if (time <= ft[i]) {       //始発がまだなときもしくはジャストタイミングな時
			time = ft[i] + cost[i];
			cal(i + 1, time);
		}else if (time > ft[i]) {        //始発が出発して次の列車を待つとき
			for (int s = 0; time > ft[i] + nex[i] * s; s++) {   //何番目の列車に乗れるか
				point = s + 1;
			}
			time = ft[i] + nex[i] * point + cost[i];   //待ち時間　+　移動時間
			cal(i + 1, time);
		}
	}
}


int main() {

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

	ans[N] = 0; //最後の駅は無条件で0

	for (int i = 1; i < N; i++) {
		ans[i] = cal(i);
	}

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


	return 0;
}

Measured memory_bytes: 384
#include <iostream>
#include <vector>
#include <algorithm>

int CalcDistance(int destPos, int fromPos)
{
    auto delta = (destPos - fromPos);
    return delta * delta;
}

int main()
{
    int memberCount = 0;
    std::cin >> memberCount;

    std::vector<int> positions;
    positions.resize(memberCount);
    int total = 0;
    for (auto &val : positions)
    {
        std::cin >> val;
        total += val;
    }

    std::sort(positions.begin(), positions.end());

    // 最小値～最大値までの間が一番小さくなるので、最小値を原点として平均に一番近い整数を会場座標とする
    const auto min = *positions.begin();
    total -= (min * memberCount);

    int decaAverage = (total * 10) / memberCount;
    int average = total / memberCount;
    if (decaAverage % 10 > 4)
    {
        ++average;
    }
    const auto dest = min + average;

    int distanceTotal = 0;
    for (const auto pos : positions)
    {
        distanceTotal += CalcDistance(dest, pos);
    }
    
    std::cout << distanceTotal;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n;
  cin >> n;
  int h[n];
  for(int i = 0; i < n; i++) {
    cin >> h[i];
  }

  for(int i = 1; i < n; i++) {
    if(h[i] < h[i - 1]) {
      cout << "No\n";
      return 0;
    } else if(h[i] > h[i - 1]) {
      h[i] = h[i] - 1;;
    }
  }
  cout << "Yes\n";
  return 0;
}

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

using ll = long long;
using Vi = vector<int>;
using Vl = vector<ll>;
using Pii = pair<int, int>;
using Pll = pair<ll, ll>;

constexpr int I_INF = numeric_limits<int>::max();
constexpr ll L_INF = numeric_limits<ll>::max();

//%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

void solve() {
    string S;
    cin >> S;
    ll N = (ll)S.size();

    Vl num(2019);
    ++num[0];
    ll ans = 0;
    ll t = 0;
    ll base = 1;
    for (ll i = N - 1; i >= 0; i--) {
        ll si = S[i] - '0';
        t = (si * base + t) % 2019;
        base = (base * 10) % 2019;
        ans += num[t];
        ++num[t];
    }
    cout << ans << "\n";
}

//%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

int main() {
#ifdef FASTIO
    cin.tie(0), cout.tie(0);
    ios::sync_with_stdio(false);
#endif
#ifdef FILEINPUT
    ifstream ifs("./in_out/input.txt");
    cin.rdbuf(ifs.rdbuf());
#endif
#ifdef FILEOUTPUT
    ofstream ofs("./in_out/output.txt");
    cout.rdbuf(ofs.rdbuf());
#endif
    solve();
    cout << flush;
    return 0;
}

Measured memory_bytes: 3720
import java.util.Scanner;

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

		int x = sc.nextInt();
		int a = sc.nextInt();
		//List<Integer> list=new ArrayList<Integer>();
		if(x<a) {
			System.out.println("0");
		}
		else {
			System.out.println("10");
		}


	}

}


Measured memory_bytes: 23124
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define pi 3.141592653589793238
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define MOD 1000000007

void solve()
{
	ll n;
	cin>>n;
	if(n%10==9 || (n/10)==9)
		cout<<"Yes";
	else
		cout<<"No";
	return;
}
int main()
{
	fast;
	int q;
	q=1;
	// cin>>q;
	while(q--)
	{
		solve();
	}
	return 0;
}

Measured memory_bytes: 3548
#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>

using namespace std;

int main() {
	static int k, s, c;
	cin >> k >> s;
	for (int i = 0; i <= k; ++i) {
		for (int j = 0; j <= k; ++j) {
			int n = s - (i + j);
			if (n >= 0 && n <= k)++c;
		}
	}
	cout << c << endl;
	// system("pause");
	return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <bits/stdc++.h>
#include <algorithm>
#include <iostream>
#include <string>
#include <cmath>
#include <functional>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#define rep(i,n) for (int i=0;i<n;i++)
using ll = long long;
using namespace std;


void solve(){

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

    int a,b;
    cin >> a >> b;

    cout << max(max(a+b,a-b),a*b);

    return 0;
}

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

using namespace std;

int main() {

	int n;
	cin >> n ;

	vector<int> a(n, 0);
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}

	cout << *max_element(a.begin(), a.end()) - *min_element(a.begin(), a.end()) << endl;

}

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

typedef vector<int> vi;

int N;
string S;
vi cntW;

void make_data(void) {
	cntW.resize(N + 2, 0);
	for (int i = 1; i <= N; ++i) {
		cntW[i] += cntW[i - 1];
		if (S[i - 1] == 'W')
			++cntW[i];
	}
	cntW[N + 1] = cntW[N];
}

int solve(void) {
	int min_cnt = N;
	for (int i = 1; i <= N; ++i) {
		int l = cntW[i - 1];
		int r = (N - i) - (cntW[N + 1] - cntW[i]);
		int cnt = l + r;
		min_cnt = min(cnt, min_cnt);
	}
	return min_cnt;
}

int main(void) {
	cin >> N >> S;

	make_data();
	int ans = solve();

	cout << ans << '\n';
	return 0;
}


Measured memory_bytes: 1796
#include<bits/stdc++.h>
using lint=long long;
lint mod=998'244'353;
void add_assign(lint&x,lint y){x+=y;if(mod<=x)x-=mod;}
int main(){
    lint n,S;std::cin>>n>>S;
    std::vector<lint>dp(S+1);
    lint ans=0;
    for(lint i=0;i<n;i++){
        lint x;std::cin>>x;
        for(lint j=S;j-x>=0;j--){
            add_assign(dp.at(j),dp.at(j-x));
        }
        if(x<=S)add_assign(dp.at(x),i+1);
        add_assign(ans,dp.at(S));
    }
    std::cout<<ans<<'\n';
}


Measured memory_bytes: 256
#include <stdio.h>
#include <math.h>
int main(){
	
	int H, W, N;
	int max, min;
    scanf("%d%d%d", &H, &W, &N);

	if(H>W){
		printf("%.0f", ceil(N*1.0/H));
	} else {
		printf("%.0f", ceil(N*1.0/W));
	}
	return 0;	
}

Measured memory_bytes: 2176
n = int(input())
h = list(map(int, input().split()))

# print(n, h)

count = 0
for i in range(n):
    able_to_see = True
    for j in range(i):
        if h[j] > h[i]:
            able_to_see = False
    if able_to_see:
        count += 1

print(count)


Measured memory_bytes: 2940
import std.stdio;
import std.conv;
import std.string;
import std.typecons;
import std.algorithm;
import std.array;
import std.range;
import std.math;
import std.regex : regex;
import std.container;

void main()
{
	while (1) {
		auto x = readln.chomp.to!int;
		auto h = readln.chomp.to!int;
		if (x + h == 0) break;
		writefln("%.8f", 2*x*sqrt((x/2.0)^^2+h^^2)+x^^2);
	}
}

Measured memory_bytes: 1116
#include <bits/stdc++.h>
#define l_ength size
const int inf = (1<<30);
const int mod = 1000000007;
using ll = long long;
using namespace std;

int main(){
	int n; cin >> n;
	vector<ll> s(n);
	--n;
	ll ans = 0;
	for( auto &k : s ) cin >> k;
	for( int x = 1; x <= n; ++x ){
		ll cur = 0;
		int l = 0, r = n;
		if( n%x != 0 ){
			while( l+x < n ){
				cur += ( s[l] + s[r] );
				ans = max(ans, cur);
				l += x; r -= x;
			}

		} else {
			while( l < r ){
				cur += ( s[l] + s[r] );
				ans = max(ans, cur);
				l += x; r -= x;
			}
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 1152
#include <iostream>
#include <cmath>

using namespace std;

int main()
{

    long long int N,D;
    cin>>N>>D;
    long long int count=0;
    for(long long int i=1;i<=N;i++){
        long long int x,y;
        cin>>x>>y;
        double d=(x*x)+(y*y);
        if(sqrt(d)<=D)
            count++;
    }

    cout<<count<<endl;

    return 0;
}


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

int main(){
  int H,W;
  cin >> H >> W;
  vector<string> C(H);
  for(int i=0;i<H;i++){
    cin >> C[i];
  }
  vector<string> D(2*H);
  for(int i=0;i<2*H;i++){
    D[i]=C[i/2];
    cout << D[i] << endl;;
  }
}

Measured memory_bytes: 3640
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize ("-ffloat-store") // to restrict undesirable precision
#pragma GCC optimize ("-fno-defer-pop")// to pop argument of function as soon as it returns
#define all(a) a.begin(),a.end()
#define ll long long int
#define ld long double
ll power(ll a,ll b,ll m){ if(b==0) return 1; if(b==1) return a%m; ll t=power(a,b/2,m)%m; t=(t*t)%m; if(b&1) t=((t%m)*(a%m))%m; return t;}
ll modInverse(ll a, ll m) { return power(a, m-2, m); }
#define ps push_back
#define fs first
#define sc second
#define takeline cin.ignore();
#define iactive cout.flush();
#define N 200005
#define endl "\n"
#define mod 1000000007
#define PI 3.141592653589793
//((1.0l)*BIG MULTIPLY MAGIC?)
// string to integer stoi()
// string to long long stoll()
// string.substr(position,length);
// integer to string to_string();
//-----------------------------------------------
int main(){

	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	
	ll i,j,k,l,n;
	cin>>n;
	ll ar[n+1],s=0; map<ll,ll> mp;
	for(i=1;i<=n;i++){
		cin>>ar[i];
		s+=ar[i];
		mp[ar[i]]++;
	}
	ll q;
	cin>>q;
	while(q--){
		cin>>k>>l;
		s-=k*mp[k];
		mp[l]+=mp[k];
		s+=l*mp[k];
		mp[k]=0;
		cout<<s<<endl;
	}
	return 0;	
}

Measured memory_bytes: 10264
n,m = map(int,input().split())

max_val = 10**5+1
# dictの初期化
ac_L = []
wa_L = []
for val in range(1,max_val):
    wa_L.append(0)
    ac_L.append(0)

ac_ans,wa_ans = 0,0


for i in range(m):
    p,s = map(str,input().split())
    p = int(p)
    # acの処理
    if ac_L[p] ==0 and s == "AC":
        ac_L[p] = 1
        wa_ans += wa_L[p]
    # waの処理
    wa_L[p] += 1


#print(ac_dic,wa_dic)
print(sum(ac_L),wa_ans)

Measured memory_bytes: 52976
#include<iostream>
using namespace std;
int main()
{
    int k,a,b;
    cin>>k>>a>>b;

    if(a%k==0||b%k==0)
        cout<<"OK"<<endl;
    else if( ((a/k)+1)*k <= b)
        cout<<"OK"<<endl;
    else
        cout<<"NG"<<endl;

}


Measured memory_bytes: 3624
import sys
input = lambda: sys.stdin.readline().rstrip()

from collections import Counter

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

c = Counter(A)

sum_comb = 0

for key in c:
    sum_comb += c[key] * (c[key] - 1) // 2

for num in A:
    tmp = c[num] * (c[num] - 1) // 2
    tmp2 = (c[num]-1) * (c[num] - 2) // 2
    print(sum_comb - tmp + tmp2)

Measured memory_bytes: 82900
fun main(args:Array<String>?): Unit {
    val (m, n) = readLine()!!.trim().split(' ').map(String::toInt)
    val k = readLine()!!.trim().toInt()
    val state = Array(m){readLine()!!.trim()}
    val jungle = state.map{line -> line.map{if (it == 'J') 1 else 0}.toIntArray()}
    val ocean = state.map{line -> line.map{if (it == 'O') 1 else 0}.toIntArray()}
    val ice = state.map{line -> line.map{if (it == 'I') 1 else 0}.toIntArray()}
    for (i in 0 until m){
        for (j in 0 until n){
            if (i > 0) {
                jungle[i][j] += jungle[i - 1][j]
                ocean[i][j] += ocean[i - 1][j]
                ice[i][j] += ice[i - 1][j]
            }
            if (j > 0){
                jungle[i][j] += jungle[i][j - 1]
                ocean[i][j] += ocean[i][j - 1]
                ice[i][j] += ice[i][j - 1]
            }
            if (i > 0 && j > 0){
                jungle[i][j] -= jungle[i - 1][j - 1]
                ocean[i][j] -= ocean[i - 1][j - 1]
                ice[i][j] -= ice[i - 1][j - 1]
            }
        }
    }
    fun count(a: Int, b: Int, c: Int, d: Int, dp: List<IntArray>): Int {
        var result = dp[c][d]
        if (a > 0) result -= dp[a - 1][d]
        if (b > 0) result -= dp[c][b - 1]
        if (a > 0 && b > 0) result += dp[a - 1][b - 1]
        return result
    }
    repeat(k){
        val (a, b, c, d) = readLine()!!.trim().split(' ').map{it.toInt() - 1}
        println("${count(a, b, c, d, jungle)} ${count(a, b, c, d, ocean)} ${count(a, b, c, d, ice)}")
    }
}


Measured memory_bytes: 124400
#include"bits/stdc++.h"
using namespace std;
using ll=long long;
template<typename T=ll>inline T in(istream&is=cin){T ret;is>>ret;return ret;}
template<typename T>inline auto vec2(typename vector<T>::size_type h,typename vector<T>::size_type w,T v=T()){return vector<vector<T>>(h,vector<T>(w,v));}

int main()
{
    cout<<string(in<string>().length(),'x')<<endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
using namespace std;
int main(){
    int t;
    cin >> t;
    int p1=0,p2=0;
    for (int i=0;i<t;i++){
        string s1,s2;
        cin >> s1 >> s2;
        if (s1>s2)
            p1+=3;
        else if (s1<s2)
            p2+=3;
        else {
            p1+=1;
            p2+=1;
        }
    }
    cout << p1 << ' ' << p2 << endl;
    return 0;
}


Measured memory_bytes: 3192
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key

typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<int> vi;
typedef long double ld;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    ll mod=1e9+7;
    ll n,m;
    cin>>n>>m;
    if(n<m)
        swap(n,m);
    ll ans=1;
    if(n-m>1){
        cout<<0;
    }
    else if(n-m==1){
        for(ll i=1;i<=n;i++){
            ans=ans*i;
            ans=ans%mod;
        }
        for(ll i=1;i<=m;i++){
            ans=ans*i;
            ans=ans%mod;
        }
        cout<<ans;
    }
    else if(n-m==0){
        ans=2;
        for(ll i=1;i<=n;i++){
            ans=ans*i;
            ans=ans%mod;
        }
        for(ll i=1;i<=m;i++){
            ans=ans*i;
            ans=ans%mod;
        }
        cout<<ans;
    }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
#define DUMP(x) cout << #x << " = " << (x) << endl;
#define FOR(i, m, n) for (ll i = m; i < n; i++)
#define IFOR(i, m, n) for (ll i = n - 1; i >= m; i--)
#define REP(i, n) FOR(i, 0, n)
#define IREP(i, n) IFOR(i, 0, n)
#define FOREACH(x, a) for (auto&(x) : (a))
#define ALL(v) (v).begin(), (v).end()
#define SZ(x) ll(x.size())

int main() {
  ll n;
  cin >> n;
  vector<ll> cnt(n + 1, 0);

  FOR(i, 1, n) {
    for (ll j = i; j < n; j += i) {
      cnt[j]++;
    }
  }
  ll ans = 0;
  FOR(i, 1, n) { ans += cnt[i]; }
  cout << ans << endl;
}

Measured memory_bytes: 11084
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;
int main(){
  int n,v=1<<16;
  cin>>n;
  int h[n],w[n],dp[v],used[v];
  for(int i=0;i<n;i++) cin>>h[i]>>w[i];
  string s[4],c="RGB";;
  for(int i=0;i<4;i++) cin>>s[i];
  memset(dp,-1,sizeof(dp));
  memset(used,0,sizeof(used));
  queue<P> q;
  q.push(P(0,0));
  while(!q.empty()){
    int bit=q.front().first,d=q.front().second;
    q.pop();
    if(~dp[bit]) continue;
    dp[bit]=d;
    for(int i=0;i<n;i++)
      for(int j=-h[i]+1;j<4;j++)
	for(int k=-w[i]+1;k<4;k++)
	  for(int l=0;l<3;l++){
	    int z=bit;
	    for(int a=max(0,-j);a<min(h[i],4-j);a++){
	      for(int b=max(0,-k);b<min(w[i],4-k);b++){
		int y=j+a,x=k+b;
		if(s[y][x]==c[l]) z|=1<<(y*4+x);
		else z&=v-1-(1<<(y*4+x));
	      }
	    }
	    if(dp[z]<0&&!used[z]) q.push(P(z,d+1)),used[z]=1;
	  }
  }
  cout<<dp[v-1]<<endl;
  return 0;
}

Measured memory_bytes: 3848
#include <bits/stdc++.h>
#define REP(i,s,e) for(int i=(s); i<(e);i++)
#define rep(i,n) REP(i,0,n)
#define rep1(i,n) REP(i,1,n)
#define repe(i,n) for(auto &&i:n)
#define all(v) (v).begin(),(v).end()
#define decimal fixed<<setprecision(20)
#define fastcin() cin.tie(0);ios::sync_with_stdio(false)
using namespace std;
using LL = long long;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const int INF = 1e9;
const LL LLINF = 1e16;

/*
!) 0-indexed
!) [a, b)に対する演算
!) m0, merge, updateNodeを書く
*/
template<typename Monoid>
struct Segtree{
    int n;
    vector<Monoid> dat;
    Monoid m0; // データの初期化値
    Segtree(int sz, Monoid m0) : m0(m0){
        n = 1;
        while(n < sz) n *= 2;
        dat.assign(2*n-1, m0);
    }

    Monoid merge(Monoid a, Monoid b){ return a + b; }
    void updateNode(int k, Monoid x){ dat[k] += x; }

    void update(int k, Monoid x){
        k += n-1;
        updateNode(k, x);
        while(k > 0) {
            k = (k-1)/2;
            dat[k] = merge(dat[k*2+1], dat[k*2+2]);
        }
    }
    Monoid query(int a, int b){
        Monoid L = m0, R = m0;
        int A = a+n-1;
        int B = b+n-1;
        while(A < B) {
            if((A&1) == 0) L = merge(L, dat[A++]);
            if((B&1) == 0) R = merge(dat[--B], R);
            A >>= 1;
            B >>= 1;
        }
        return merge(L, R);
    }
    Monoid operator[](const int &k) const { return dat[k+n-1]; }
};

int main(){
    int n, Q;
    cin >> n >> Q;
    Segtree<LL> a(n, 0);
    rep(i, Q){
        int q, x, y;
        cin >> q >> x >> y;
        if(q == 0){
            x--;
            a.update(x, y);
        }else{
            x--; y--;
            cout << a.query(x, y+1) << endl;
        }
    }

}


Measured memory_bytes: 4952