akhauriyash/Code-Regression huggingface dataset:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random,resource

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    n = I()
    a = LI()
    q = I()
    bc = [LI() for _ in range(q)]

    t = sum(a)
    u = collections.Counter(a)
    rr = []
    for b,c in bc:
        s = u[b]
        t += (c-b) * s
        u[b] = 0
        u[c] += s
        rr.append(t)


    return JA(rr, '\n')


print(main())




Measured memory_bytes: 52136
#include<stdio.h>
#include<math.h>
int main()
{
	int a,b,c,d,min2,max2;
	while(scanf("%d%d%d%d",&a,&b,&c,&d)!=EOF)
	{
		if(b<c||d<a)
		printf("0\n");
		else
		{
			min2=(a>=c)?a:c;
			max2=(d>=b)?b:d;
			printf("%d\n",max2-min2);
		}
	}
	return 0;
}

Measured memory_bytes: 128
from operator import itemgetter
from collections import deque

n = int(input())
ab = deque(sorted((list(map(int, input().split())) for _ in range(n)), key=itemgetter(1),reverse=True))
cd = sorted((list(map(int, input().split())) for _ in range(n)), key=itemgetter(0))

ans = 0
for i in range(n):
    for j in range(len(cd)):
        if ab[0][0] < cd[j][0] and ab[0][1] < cd[j][1]:
            ans += 1
            ab.popleft()
            cd.pop(j)
            break
    else:
        ab.popleft()

print(ans)


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

const int64_t MOD = 1e9+7;
void add(int64_t& a, int64_t b){
    a = (a+b) % MOD;
}
void mul(int64_t& a, int64_t b){
    a = a*b % MOD;
}

vector<int64_t> fact, seq_inv, fact_inv;

void create_fact_mod(int num){
    fact[0] = fact[1] = 1;
    for(int i=2; i<=num; i++) fact[i] = fact[i-1] * i % MOD;
}

void create_seq_inv_mod(int num){
    seq_inv[0] = seq_inv[1] = 1;
    for(int i=2; i<=num; i++) seq_inv[i] = (MOD - MOD/i) * seq_inv[MOD%i] % MOD;
}

void create_fact_inv_mod(int num){
    fact_inv[0] = fact_inv[1] = 1;
    for(int i=2; i<=num; i++) fact_inv[i] = fact_inv[i-1] * seq_inv[i] % MOD;
}

void create_mod_tables(int num){
    fact.resize(num+1);
    seq_inv.resize(num+1);
    fact_inv.resize(num+1);
    create_fact_mod(num);
    create_seq_inv_mod(num);
    create_fact_inv_mod(num);
}

int64_t comb_mod(int n, int k){
    return fact[n] * fact_inv[n-k] % MOD * fact_inv[k] % MOD;
}

int64_t perm_mod(int n, int k){
    return fact[n] * fact_inv[n-k] % MOD;
}

int64_t power_mod(int64_t num, int64_t power){
    int64_t prod = 1;
    num %= MOD;
    while(power > 0){
        if(power&1) prod = prod * num % MOD;
        num = num * num % MOD;
        power >>= 1;
    }
    return prod;
}

int64_t extgcd(int64_t a, int64_t b, int64_t& x, int64_t& y){
    int64_t d = a;
    if(b != 0){
        d = extgcd(b, a%b, y, x);
        y -= (a/b) * x;
    }else{
        x = 1; y = 0;
    }
    return d;
}

int64_t inv_mod(int64_t a){
    int64_t x, y;
    extgcd(a, MOD, x, y);
    return (MOD + x%MOD) % MOD;
}

int N;
vector<int> edges[200000];
int64_t inv2 = inv_mod(2);

int64_t nothing[200000];
void dfs1(int i, int p){
    nothing[i] = inv2;
    for(int j : edges[i]) if(j != p){
        dfs1(j, i);
        mul(nothing[i], nothing[j]);
    }
}

int64_t ans = 0;
void dfs2(int i, int p, int64_t top){
    if(edges[i].size() > 1){
        vector<int64_t> vals;
        vals.push_back(top);
        int64_t m = top;
        for(int j : edges[i]) if(j != p){
            vals.push_back(nothing[j]);
            mul(m, nothing[j]);
        }
        int64_t res = 1;
        add(res, MOD - m);
        for(int64_t v : vals){
            int64_t sub = m * inv_mod(v) % MOD * (MOD+1-v) % MOD;
            add(res, MOD - sub);
        }
        mul(res, inv2);
        add(ans, res);
    }
    for(int j : edges[i]) if(j != p){
        int64_t top2 = top;
        mul(top2, nothing[i]);
        mul(top2, inv_mod(nothing[j]));
        dfs2(j, i, top2);
    }
}

int main(){
    cin >> N;
    for(int i=0; i<N-1; i++){
        int a, b;
        cin >> a >> b;
        a--; b--;
        edges[a].push_back(b);
        edges[b].push_back(a);
    }
    for(int i=0; i<N; i++) if(edges[i].size() == 1){
        dfs1(i, -1);
        dfs2(i, -1, 1);
        break;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 42368
n = int(input())
xyh = [list(map(int,input().split())) for i in range(n)]
xyh = sorted(xyh, key=lambda x:(x[2]), reverse=True)

ans = -1, -1, -1
for cx in range(101):
    for cy in range(101):
        flg = True
        x, y, h = xyh[0][0], xyh[0][1], xyh[0][2]
        ch = abs(cx-x) + abs(cy-y) + h
        for i in range(1,n):
            x, y, h = xyh[i][0], xyh[i][1], xyh[i][2]
            tmph = max(ch - abs(cx-x) - abs(cy-y), 0)
            if h != tmph:
                flg = False
                break
        if flg:
            ans = cx, cy, ch
print(*ans)

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

    typedef long long int ll;
    #define pb         push_back
    #define mp         make_pair
    #define F          first
    #define S          second
    #define fl(i,a,b)  for(ll i=a;i<b;i++)
    #define pll        pair<ll,ll>
    #define pii        pair<int,int>
    #define all(v)     v.begin(),v.end()
    #define M 1000000007
    #define tr(v, it) for(auto it = v.begin(); it != v.end(); it++)
    using namespace std;

    int main()
    {

    ios_base::sync_with_stdio(false);
	cin.tie(NULL);

       int n,k;
       cin>>n>>k;
        int arr[n];
        for(int i=0; i<n; i++)
            cin>>arr[i];
        vector<int> dp(n+1, INT_MAX);

        dp[1]=0;
        dp[0]=0;
        for(int i=2; i<=n; i++)
        {
            for(int j=1; j<=k; j++)
            {
                 if((i-j)>= 1)
                dp[i]=min(dp[i], dp[i-j]+abs(arr[i-j-1]-arr[i-1]));
            }
        }
        cout<<dp[n];
        return 0;

    }



Measured memory_bytes: 3992
#include <bits/stdc++.h>
#define FOR(i, m, n) for(int i = (m); i < (n); i++)
#define REP(i, n) FOR(i, 0, n)
using namespace std;
const int d[][2] = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};

int main (void) {
  int h, w;
  int shiro = 0;
  cin >> h >> w;
  vector<vector<char>> s(h, vector<char>(w));
  vector<vector<bool>> visited(h, vector<bool>(w, false));
  REP(i, h) REP(j, w) {
    cin >> s[i][j];
    if (s[i][j] == '.') shiro++;
  }
  visited[0][0] = true;
  queue<tuple<int, int, int>> q;
  q.push(make_tuple(0, 0, 1));
  const int unreachable = 1000000;
  int min_dist = unreachable;
  while(!q.empty()) {
    int y, x, dist;
    tie(y, x, dist) = q.front();
    q.pop();
    if (y == h - 1 && x == w - 1) {
      min_dist = min(min_dist, dist);
      continue;
    }
    REP(i, 4) {
      int dy = y + d[i][0], dx = x + d[i][1];
      if (dy >= 0 && dy < h && dx >= 0 && dx < w && s[dy][dx] == '.' && !visited[dy][dx]) {
        visited[dy][dx] = true;
        q.push(make_tuple(dy, dx, dist + 1));
      }
    }
  }
  if (min_dist == unreachable)
    cout << -1 << endl;
  else
    cout << shiro - min_dist << endl;
  return 0;
}


Measured memory_bytes: 256
from collections import Counter

n=int(input())
*v,=map(int,input().split())

v0=list(Counter(v[::2]).items())
v1=list(Counter(v[1::2]).items())

v0.sort(key=lambda x:x[1],reverse=True)
v1.sort(key=lambda x:x[1],reverse=True)

k0,ma0=v0[0]
k1,ma1=v1[0]

if k0==k1 and len(v0)==1 and len(v1)==1:
    print(n//2)
elif k0==k1 and len(v0)==1:
    print((n+1)//2-v1[1][1]+n//2-ma0)
elif k0==k1 and len(v1)==1:
    print(n//2-v0[1][1]+(n+1)//2-ma1)
elif k0==k1:
    print(min((n+1)//2-v1[1][1]+n//2-ma0,n//2-v0[1][1]+(n+1)//2-ma1))
else:
    print((n+1)//2-ma0+n//2-ma1)

Measured memory_bytes: 104976
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)n;i++)
#define rep1(i,n) for(int i=1;i<=(int)n;i++)
#define rep2(i,j,n) for(int j=i;j<n;j++)
#define rep3(i,j,n) for(int j=i;j<=n;j++)
#define rrep(i,n) for(int i=n-1;i>=0;i--)
#define sp(n) cout << fixed << setprecision(n)
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; }
typedef long long ll;
using namespace std;
int main(void){
    int n,C;cin>>n>>C;
    int d[C][C];
    map<int,int> mp1,mp2,mp3;
    rep(i,C)rep(j,C){
        cin>>d[i][j];
    }
    rep(i,n)rep(j,n){
        int c;cin>>c;c--;
        if((i+j)%3==0)mp1[c]++;
        else if((i+j)%3==1)mp2[c]++;
        else mp3[c]++;
    }
    ll res=1e+9;
    rep(i,C)rep(j,C)rep(k,C){
        if(i==j||k==j||k==i)continue;
        ll tmp=0;
        for(auto& p:mp1){
            int x=p.first,y=i;
            tmp+=p.second*(d[x][y]);
        }
        for(auto& p:mp2){
            int x=p.first,y=j;
            tmp+=p.second*(d[x][y]);
        }
        for(auto& p:mp3){
            int x=p.first,y=k;
            tmp+=p.second*(d[x][y]);
        }
        chmin(res,tmp);
    }
    cout<<res<<endl;
}

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

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

Measured memory_bytes: 256
package main

import "fmt"

func main() {
  var a int
  _, err := fmt.Scanf("%d", &a)
  if err != nil {
    panic("error")
  }
  b := a % 1000
  if b == 0 {
    fmt.Println("0")
  } else {
    fmt.Println(1000 - b)
  }
}

Measured memory_bytes: 1832
import Control.Applicative
import Control.Monad
import Data.List
import Data.Array

main = do
  [n, q] <- map (read::String -> Int) . words <$> getLine
  s <- getLine
  let counts = listArray (1, n) . tail . map fst $ scanl (\(count, prv) crt -> if prv == 'A' && crt == 'C' then (count + 1, crt) else (count, crt)) (0, 'N') s
  forM [1..q] (\i -> do
    [l, r] <- map (read::String -> Int) . words <$> getLine
    print $ counts ! r - counts ! l)

Measured memory_bytes: 21140
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+100;
const int INF=0x3f3f3f3f;
typedef long long LL;
typedef pair<int,int> pil;
pil A[maxn];
int n,m;
int main()
{
    cin>>n>>m;
    for(int i=0;i<n;i++)
        cin>>A[i].first>>A[i].second;
    sort(A,A+n);
    priority_queue<int> q;
    int p=0,res=0;
    for(int i=1;i<=m;i++)
    {
        while(p<n&&A[p].first<=i)
            q.push(A[p++].second);
        if(!q.empty())
        {
            res+=q.top();
            //cout<<"fuck "<<q.top()<<endl;
            q.pop();
        }
    }
    cout<<res<<endl;
}


Measured memory_bytes: 1660
#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;
using Graph = vector<vector<int>>;
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;
const int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

int main(){
    fastcin();

    string s;
    cin >> s;
    cout << (s[2]==s[3] && s[4]==s[5] ? "Yes" : "No") << endl;
}

Measured memory_bytes: 256
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		//値の入力
		int N = sc.nextInt();
		int L = sc.nextInt();
		List<String> S = new ArrayList<String>();
		for(int i = 0; i < N; i++) {
			String s = sc.next();
			if(s.length() == L) {
				S.add(s);
			}else {
				i--;
			}
		}
		//辞書順にソート
		S.sort(Comparator.naturalOrder());
		//出力
		for (String s : S) {
			System.out.print(s);
		}

	}

}


Measured memory_bytes: 21972
#include <bits/stdc++.h>
#include <vector>
#include <string>
#include <stdio.h>
#include <cstdlib>
#include <iostream>
#include <cstdlib>
using namespace std;
using ll = long long;
#define pi 3.1415926535897932384626433832795028841971693993

int main()
{
    ll n,m,sum=0;
    cin>>n>>m;
    ll a[m];
    for(ll i=0;i<m;i++)
    {
        cin>>a[i];
        sum+=a[i];
    }
    if(n-sum>=0)
    cout<<n-sum;
    else
        cout<<"-1";
    return 0;
}


Measured memory_bytes: 3704
using System;
using System.Collections.Generic;
using System.Linq;
using static System.Math;

namespace ConsoleApp1
{
    class Program
    {
        static void Main(string[] args)
        {
            A();
        }

        static void A()
        {
            var S = Read();
            for (var i = 0; i < S.Length - 1; i++)
            {
                if (S[i] == S[i + 1])
                {
                    Println("Bad");
                    return;
                }
            }
            Println("Good");
        }

        static IEnumerable<int> Range(int start, int stop)
        {
            if (start < 0 || stop < 0 || start > stop || (start <= 0 && stop <= 0))
                return new List<int>();

            return Enumerable.Range(start, stop - start);
        }

        static bool IsDigit(string str)
        {
            var i = 0;
            return int.TryParse(str, out i);
        }

        static int SumDigits(long num)
        {
            return num.ToString().Select(x => x.ToString()).Sum(int.Parse);
        }

        static int[] ToIntArray(string str)
        {
            return str.Select(x => x.ToString()).Select(int.Parse).ToArray();
        }

        static int Gcd(int a, int b) => b == 0 ? a : Gcd(b, a % b);

        static bool IsPrime(int x)
        {
            if (x <= 1 || (x != 2 && x % 2 == 0)) return false;
            if (x == 2) return true;

            for (int i = 3; i < x; i += 2)
                if (x % i == 0) return false;

            return true;
        }

        static string Read() => Console.ReadLine();
        static int ReadInt() => int.Parse(Read());
        static long ReadLong() => long.Parse(Read());

        static List<string> ReadSplit() => Read().Split().ToList();
        static List<int> ReadSplitInt() => Read().Split().Select(int.Parse).ToList();
        static List<long> ReadSplitLong() => Read().Split().Select(long.Parse).ToList();

        static void Print(object value) => Console.Write(value.ToString());
        static void Println(object value) => Console.WriteLine(value.ToString());

        static string Join<T>(IEnumerable<T> list) => string.Join("", list);
    }

    public static class MyExtensions
    {
        public static string Slice(this string str, int start = 0, int stop = 0)
        {
            if (start > str.Length || stop > str.Length || start < 0 || stop < 0)
                return "";

            if (stop == 0) stop = str.Length;
            return str.Substring(start, stop - start);
        }
    }
}


Measured memory_bytes: 11092
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pli = pair<ll, int>;
using pil = pair<int, ll>;
using uint = unsigned int;
template <typename T>
using Graph = vector<vector<T>>;
const int MOD = 998244353;
const ld PI = acosl(-1);

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

    int N, K;
    cin >> N >> K;
    vector<int> A(N);
    for (int i = 0; i < N; ++i)
        cin >> A[i];

    auto func = [&]() -> void {
        vector<int> B(N + 1, 0);
        for (int i = 0; i < N; ++i) {
            B[max(i - A[i], 0)]++;
            B[min(i + A[i] + 1, N)]--;
        }
        for (int i = 0; i < N; ++i) {
            A[i] = B[i];
            B[i + 1] += B[i];
        }
    };

    K = min(K, 100);
    for (int i = 0; i < K; ++i)
        func();

    for (int i = 0; i < N; ++i) {
        cout << A[i] << " ";
    }
    cout << endl;

    return 0;
}


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

void solve() {
  string s;
  int c = 0;
  while (cin >> s) {
    string t = s;
    reverse(all(t));
    c += s == t;
  }
  cout << c << endl;
}

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

if A + 2 >= B:
  print(K + 1)
else:
  firstHit = A - 1
  remainingK = K - firstHit
  if remainingK % 2 == 0:
    print(A + (B - A) * (remainingK // 2))
  else:
    print(A + (B - A) * (remainingK // 2) + 1)
     


Measured memory_bytes: 2940
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> lpair;
const ll MOD = 1e9 + 7;
const ll INF = 1e18;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
#define rREP(i,m,n) for(ll i = (m); i >= (n); i--)
#define print(x) cout << (x) << endl;
#define printa(x,n) for(ll i = 0; i < n; i++){ cout << (x[i]) << " ";} cout<<endl;
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    ll a,b;
    cin >> a >> b;

    if (a%2 == b%2)
    {
        cout << (a+b) / 2 << endl;
    }
    else
    {
        cout << "IMPOSSIBLE" << endl;
    }
}


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

int main() {
  int N,A,a,imin,j;
  cin >> N >> A;
  for (imin = 0; A % 2 == 0; imin++)
    A /= 2;
  for (int i = 0;i < N-1; i++) {
    cin >> a;
    for (j = 0;a % 2 == 0;j++)
      a /= 2;
    if (j < imin)
      imin = j;
  }
  cout << imin << endl;     
}

Measured memory_bytes: 3632
import sys
sys.setrecursionlimit(10**7)
n = int(input())

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append((i, cnt))

    if temp!=1:
        arr.append((temp, 1))

    if arr==[]:
        arr.append((n, 1))

    return arr

def get_divisors(num):
    f_divs, l_divs = [], []
    for i in range(1, int(num**0.5)+1):
        if not num % i:
            f_divs.append(i)
            if i != num // i:
                l_divs.append(num // i)
    return f_divs + l_divs[::-1]

f = factorization(n)
num, cnt = zip(*f)
ans = len(get_divisors(n-1))-1

def dfs(idx, x):
    nx = x
    if idx >= len(num):
        if x == 1: return
        k = n
        while k % x == 0: k //= x
        if (k-1) % x == 0:
            global ans
            ans += 1
        return

    for i in range(cnt[idx]+1):
        dfs(idx+1, nx)
        nx *= num[idx]

dfs(0, 1)
print(ans)


Measured memory_bytes: 3188
#include <bits/stdc++.h>
#define ll long long
#define INF 1000000005
#define MOD 1000000007
#define EPS 1e-10
#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 srep(i,s,t) for(int i=(int)(s);i<(int)(t);++i)
#define each(a,b) for(auto (a): (b))
#define all(v) (v).begin(),(v).end()
#define len(v) (int)(v).size()
#define zip(v) sort(all(v)),v.erase(unique(all(v)),v.end())
#define cmx(x,y) x=max(x,y)
#define cmn(x,y) x=min(x,y)
#define fi first
#define se second
#define pb push_back
#define show(x) cout<<#x<<" = "<<(x)<<endl
#define spair(p) cout<<#p<<": "<<p.fi<<" "<<p.se<<endl
#define svec(v) cout<<#v<<":";rep(kbrni,v.size())cout<<" "<<v[kbrni];cout<<endl
#define sset(s) cout<<#s<<":";each(kbrni,s)cout<<" "<<kbrni;cout<<endl
#define smap(m) cout<<#m<<":";each(kbrni,m)cout<<" {"<<kbrni.first<<":"<<kbrni.second<<"}";cout<<endl

using namespace std;

typedef pair<int,int> P;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<double> vd;
typedef vector<P> vp;
typedef vector<string> vs;

const int MAX_N = 1000005;

int num[MAX_N];
int cnt[MAX_N];

vector<int> prime;
bool is_prime[MAX_N];

void sieve(int n){
	for(int i=0;i<=n;i++){
		is_prime[i] = true;
	}
	is_prime[0] = is_prime[1] = false;
	for(int i=2;i<=n;i++){
		if(is_prime[i]){
			prime.push_back(i);
			for(int j=2*i;j<=n;j+=i){
				is_prime[j] = false;
			}
		}
	}
}

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int l,r;
    cin >> l >> r;
    sieve(max((int)sqrt(r+100),50));
    rep(i,r-l+1){
        num[i] = l+i;
    }
    for(int i=2;i*i<=r;i++){
        if(is_prime[i]){
            for(int j=((l-1)/i+1)*i;j<=r;j+=i){
                int& val = num[j-l];
                while(val % i == 0){
                    val /= i;
                    cnt[j-l]++;
                }
            }
        }
    }
    // rep(i,r-l+1){
    //     cout << i+l << " " << num[i] << "\n";
    // }
    for(int i=l;i<=r;i++){
        if(num[i-l] != 1){
            cnt[i-l]++;
        }
    }
    // rep(i,r-l+1){
    //     cout << i+l << " " << cnt[i] << "\n";
    // }
    int ans = 0;
    rep(i,r-l+1){
        if(is_prime[cnt[i]]){
            // show(cnt[i]);
            ans++;
        }
    }
    cout << ans << "\n";
    return 0;
}



Measured memory_bytes: 11112
#include<bits/stdc++.h>
using namespace std;
enum type{
	A,
	B,
};
int dp[3][5001][2];
int main(void){
	int n;
	int i,j,k,l;
	
	int a[10001];
	cin>>n;
	for(i=1;i<n;i++)	cin>>a[i];
	for(i=1;i<=2;i++){
		for(j=0;j<=n/2;j++){
			dp[i][j][A]=INT_MAX;
			dp[i][j][B]=INT_MAX;
		}
	}
	dp[1][1][A]=0;dp[1][0][B]=0;
	for(i=1;i<n;i++){
		if(i%2!=0){
			k=1;l=2;
			for(j=0;j<=n/2;j++){
				dp[l][j][A]=INT_MAX;
				dp[l][j][B]=INT_MAX;
			}
		}
		else	  {
			k=2;l=1;
			for(j=0;j<=n/2;j++){
				dp[l][j][A]=INT_MAX;
				dp[l][j][B]=INT_MAX;
			}
		}
		for(j=0;j<=n/2;j++){
			if(dp[k][j][A]!=INT_MAX){
				dp[l][j+1][A]=min(dp[l][j+1][A],dp[k][j][A]);
				if(j+1<=n/2)	dp[l][j][B]=min(dp[l][j][B],dp[k][j][A]+a[i]);
			}
			if(dp[k][j][B]!=INT_MAX){
				dp[l][j][B]=min(dp[l][j][B],dp[k][j][B]);
				if(j+1<=n/2)	dp[l][j+1][A]=min(dp[l][j+1][A],dp[k][j][B]+a[i]);
			}
		}
		/* for(j=0;j<=n/2;j++)	cout<<dp[l][j][A]<<"/"<<dp[l][j][B]<<" ";
		cout<<endl; */
	}
	
		
	cout<<min(dp[l][n/2][A],dp[l][n/2][B])<<endl;
	return 0;
}
	


Measured memory_bytes: 3228
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String s = br.readLine();
		
		if(s.charAt(2) == s.charAt(3) && s.charAt(4) == s.charAt(5)) {
			System.out.println("Yes");
		} else {
			System.out.println("No");
		}
	}

}

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

#include <iostream>
#include <fstream>

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <map>
#include <set>
#include <algorithm>
#include <numeric>
#include <bitset>
using namespace std;
using ll = long long;
constexpr ll INF = 1010000000000000017LL;
#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)
#define all(v) v.begin(), v.end()

ll GCD(ll a, ll b) { if(b==0) return a; else return GCD(b, a%b); }
ll LCM(ll a, ll b) { return a/GCD(a,b)*b; }

class AFiveAntennas {
public:
	void solve(std::istream& in, std::ostream& out) {
	    vector<int> a(5);
	    rep(i,5) in>>a[i];
	    int k;in>>k;
	    int ma =0;
        for (int j = 0; j < 5; ++j) {
            for (int i = j+1; i < 5; ++i) {
                ma = max(ma, a.at(i)-a.at(j));
            }
        }
        if(ma>k) out<<":("<<endl;
        else out<<"Yay!"<<endl;

	}
};


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


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

using namespace std;

typedef long long int ll;
typedef pair<ll, ll> pll;

#define FOR(i, n, m) for(ll (i)=(m);(i)<(n);++(i))
#define REP(i, n) FOR(i,n,0)
#define OF64 std::setprecision(10)

const ll MOD = 1000000007;
const ll INF = (ll) 1e15;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll A, B;
    cin >> A >> B;

    ll n = B - A + 1;

    if (A <= 0 && B >= 0)
        cout << "Zero" << endl;
    else if (A > 0)
        cout << "Positive" << endl;
    else if (n % 2 == 0)
        cout << "Positive" << endl;
    else
        cout << "Negative" << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <cstdlib>
#include <cstdio>
#include <queue>
#include <stack>
#include <list>
#include <utility>
#include <vector>
#include <set>
#include <algorithm>
#include <cmath>
#include <climits>
#include <map>
#include <unordered_map>
#include <string.h>
#include<iomanip>
#include <iterator>
#include <locale>

#define all(a) a.begin(),a.end()
#define VV(T) vector<vector< T > >
#define rep(i,N) for(int i = 0; i <N; i++)
#define repsg(i,s,g) for(int i = s; i <g; i++)
#define name(x) #x
using namespace std;

const int INF = INT_MAX;
const long long INFL = 1LL<<40;
const double PI = atan(1)*4;
const long long MOD = pow(10,9)+7;
int dy[]={0, 0, 1, -1, 0};
int dx[]={1, -1, 0, 0, 0};

typedef long long ll,LL;
typedef vector<int> vint;
typedef vector<vector<int> > vvint;
typedef vector<long long> vll, vLL;
typedef vector<vector<long long> > vvll, vvLL;
typedef pair<int,int> pii;
typedef pair<LL, LL> pLL;


// vector入力
template<typename T>
istream& operator >> (istream& is, vector<T>& vec){
    for(T& x: vec) is >> x;
    return is;
}
// vector出力
template<typename T>
ostream& operator << (ostream& os, vector<T>& vec){
    for(int i=0; i<vec.size(); i++){
        os << vec[i] << ( i+1 == vec.size() ? "" : " " );
    }
    return os;
}




int main() {
    int n;cin>>n;
    /// 75 = 5*5*3
    
    map<int,int> mp;
    

    repsg(j,2,n+1){
        int v(j);
        int i = 2;
        while(v!=1){
            
            while(v%i==0){
                v/=i;
                mp[i]++;
            }
            i++;
            
        }
    }
    
    /// 75, 25*3, 15*5, 5*5*3
    
    ll ans = 0;
    
    for(auto a:mp){
        if(a.second>=74)ans++;
    }
    
    for(auto i = mp.begin(); i!=mp.end();i++){
        
        if((*i).second<24)continue;
        for(auto j = mp.begin();j!=mp.end();j++){
            if(i==j)continue;
            if((*j).second>=2) ans++;
        }
        
    }
    
    for(auto i = mp.begin(); i!=mp.end();i++){
        
        if((*i).second<14)continue;
        for(auto j = mp.begin();j!=mp.end();j++){
            if(i==j)continue;
            if((*j).second>=4) ans++;
        }
        
    }
    for(auto i = mp.begin(); i!=mp.end();i++){
        
        if((*i).second<4)continue;
        auto k(i);
        k++;
        for(auto j = k;j!=mp.end();j++){
            
            if((*j).second<4)continue;
            
            for(auto l = mp.begin(); l!= mp.end(); l++){
                if(l==i || l==j)continue;
                if((*l).second<2)continue;
                ans++;
            }
            
        }
        
    }
    
    cout<<ans<<endl;
    

    return 0;
}







Measured memory_bytes: 256
from collections import Counter
N = int(input())

a = list(map(int, input().split()))
que = []

for i in range(N):
    num = a[i]
    que.append(num+1)
    que.append(num)
    que.append(num-1)


counter = Counter(que)
for word, cnt in counter.most_common(1):
    print(cnt)

Measured memory_bytes: 27352
import numpy as np
N = int(input())
c = input().split()
card = np.array(c, dtype=np.int64)
alice = 0
bob = 0
card = np.sort(card)[::-1]


for i in range(N):
    if i % 2 == 0:
        alice +=  card[i]
    else:
        bob += card[i]

print(alice - bob)

Measured memory_bytes: 12508
#include<bits/stdc++.h>
using namespace std;
int main() {
  int r, g, b; cin >> r >> g >> b;
  int x = 10 * g + b;
  if(x % 4 == 0) {
    cout << "YES" << endl;
  } else {
    cout << "NO" << endl;
  }
}

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

int main(){
    long long n;
    cin >> n;

    vector<long long> a(n);
    for(long long i = 0; i < n; i++) a[i] = i+1;

    vector<long long> sum_a(n+1, 0);
    for(long long i = 0; i < n; i++) sum_a[i+1] = sum_a[i] + a[i];

    long long index = 0;
    long long delta = 0;

    for(long long i = 0; i <= n; i++){
        if(sum_a[i] >= n){
            index = i-1;
            delta = sum_a[i] - n;
            break;
        }
    }

    //printf("delta %lld\n", delta);

    vector<long long> ans;

    for(long long i = 0; i <= index; i++){
        if(delta == i+1) continue;
        ans.push_back(i+1);
    }

    for(auto v : ans) printf("%lld\n", v);

    return 0;
}

Measured memory_bytes: 159744
// Last Change: 03/21/2019 23:03:48.
#include <algorithm>
#include <array>
#include <bitset>
#include <cmath>
#include <cstdlib>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <memory>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

using namespace std;
using ll = long long;

namespace NS {
void LoopUntilZeroInpput() {
  int hogegegege = 0;
  while (cin >> hogegegege && hogegegege != 0) {
  }
}
} // namespace NS

int main() {
  ll A, B, K;
  cin >> A >> B >> K;

  ll big, little;
  big = B - K + 1;
  little = A + K - 1;

  if (little < big) {
    for (ll i = A; i <= little; ++i) {
      cout << i << '\n';
    }
    for (ll i = big; i <= B; ++i) {
      cout << i << '\n';
    }
  } else {
    for (ll i = A; i <= B; ++i) {
      cout << i << '\n';
    }
  }
  cout << flush;

  //NS::LoopUntilZeroInpput();
}


Measured memory_bytes: 256
import sys


def main():
    N, Q = map(int, input().split())
    S = list(input())
    ac_check = [0] * (N)
    tsum = [0] * (N + 1)

    for i in range(N - 1):
        if S[i] == 'A' and S[i + 1] == 'C':
            tsum[i + 2] += 1
            ac_check[i] = 1
            ac_check[i + 1] = 2

    for i in range(N):
        tsum[i + 1] += tsum[i]

    ans = []
    for i in range(Q):
        l, r = map(int, input().split())
        count = tsum[r] - tsum[l - 1]
        if ac_check[l - 1] == 2:
            count -= 1
        ans.append(count)

    print('\n'.join(map(str, ans)))


if __name__ == '__main__':
    main()


Measured memory_bytes: 19476
import math
def trial_division(n):
    #素因数を格納するリスト
    factor = []
    #2から√n以下の数字で割っていく
    tmp = int(math.sqrt(n)) + 1
    for num in range(2,tmp):
        while n % num == 0:
            n //= num
            factor.append(num)
    #リストが空ならそれは素数
    if not factor:
        return [n]
    else:
        factor.append(n)
        return factor

mod = 10**9+7        
N = int(input())
di = {}
ans = 1
for i in range(1,N+1):
    l = trial_division(i)
    for j in l:
        if(j in di):
            di[j]+=1
        else:
            di[j]=1
for i in di:
    if(i==1):
        continue
    ans *= (di[i]+1)
    ans %= mod
print(ans)
    

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

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(v) v.begin(), v.end()

using llint = long long;
using vint = vector<int>;
using vvint = vector<vector <int>>;
using pint = pair<int, int>;
const int INF = 1e9;
const llint llINF = 1e18;

int main () {
    int n = 5;
    int a, b, c, d, e;
    cin >> a >> b >> c >> d >> e;
    vint time = {a, b, c, d, e};
    vint nexttime(n);
    for (int i = 0; i < n; i++) {
        if (time[i] % 10 == 0) nexttime[i] = time[i];
        else nexttime[i] = time[i] - time[i] % 10 + 10;
    }
    int besttime = INF;
    for (int i = 0; i < n; i++) {
        int sumtime = 0;
        for (int j = 0; j < n; j++) {
            if (i == j) {
                sumtime += time[j];
            } else {
                sumtime += nexttime[j];
            }
        }
        besttime = min(besttime, sumtime);
    }
    cout << besttime << endl;
    return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		int a = sc.nextInt();
		int b = sc.nextInt();
		int c = sc.nextInt();
		int d = sc.nextInt();

		System.out.println(Math.min(a, b) + Math.min(c, d));

	}
}

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


int main(){
   
    ll n,k;
    cin >> n >> k ;
    ll a[n],b[n];
    for(int i=0;i<n;i++)
    {
        cin >> a[i] >> b[i];
    }
    ll count = 0;
    for(int i=0;i<n;i++)
    {
        ll p = a[i]*a[i] + b[i]*b[i];    
        double q = sqrt((double)p);
        
        if(q <= k)
        {
            count++;
        }
    }
    cout << count << "\n";
    
    return 0;
}

Measured memory_bytes: 6764
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<limits.h>
using namespace std;

int n;
int d[103][103];
void wf();

int main(){ 
  while(cin >> n)wf();
}




void wf(){
  int i1,m,J2;
  for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
      if(i == j)d[i][j]=0;
      d[i][j]=1000000000;//INT_MAXツつセツづバツグツづゥ
    }
  }

  for(int i=0;i<n;i++){
    cin >> i1 >> m;
    for(int j=0;j<m;j++){
      cin >> J2;
      d[i1-1][J2-1]=1;
    }
  }

  for(int k=0;k<n;k++)for(int i=0;i<n;i++)for(int j=0;j<n;j++)d[i][j] = min(d[i][j],d[i][k]+d[k][j]);
  int oh;

  cin >> oh;
  int st,ed,ttl;
  for(int i=0;i<oh;i++){
    cin >> st >> ed >> ttl;
    if(d[st-1][ed-1]+1 > ttl)cout << "NA" << endl;
    else cout << d[st-1][ed-1]+1 << endl;

  }/*
 for(int i=0;i<n;i++){
     for(int j=0;j<n;j++)cout << d[i][j] << " " ;
     cout << endl;
   }
   */

}

 

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

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> VI;
typedef vector<VI> VVI;
const double PI = 3.14159265358979323846;
const double EPS = 1e-12;
const int INF = numeric_limits<int>::max() / 2;
const int NEG_INF = numeric_limits<int>::min() / 2;

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

  int n,m;
  while(true){
    cin >> n >> m;
    if(n==0) break;
    std::vector<pii> v;
    int sum=0;
    //pair::first-p,second-d
    for(int i=0;i<n;i++){
      int d,p;
      cin >> d >> p;
      pii pa=make_pair(p,d);
      v.push_back(pa);
      sum+=d*p;
    }
    sort(v.begin(),v.end(),greater<pii>());
    for(int i=0;i<n;i++){
      if(m>=v[i].second){
        m -= v[i].second;
        sum -= v[i].first*v[i].second;
      }
      else if(m<v[i].second){
        sum -= v[i].first*m;
        m=0;
      }
      if(m<1) break;
    }
    cout << sum << endl;
  }
}

Measured memory_bytes: 3272
#include <iostream>
#include <cmath>
#include <algorithm>
#include <map>
#include <cstring>
#include <vector>
#define FOR(i, a, b)  for(int i=a; i<b; ++i)
#define rFOR(i, a, b) for(int i=a-1; i>=b; --i)
#define REP(i, n) for(int i=0; i<n; ++i)
#define rREP(i, n) for(int i=n-1; i>=0; --i)
#define all(a)  a.begin(), a.end()
#define MAXNUM 1000000
using namespace std;

bool num[MAXNUM];
void erast(int n){
  FOR(i, 2, floor(sqrt(n))+1){
    if(num[i]){
      FOR(j, 2, n){
        if(i*j>=MAXNUM) break;
        num[i*j] = false;
      }
    }
  }
}

int main(){
  int n;
  REP(i, MAXNUM)  num[i] = true;
  num[0]=false;
  num[1]=false;
  while(cin >> n){
    int ans=0;
    erast(n);
    REP(i, n+1){
      if(num[i]){
        ans++;
      }
    }
    cout << ans << endl;
  }
  return 0;
}



Measured memory_bytes: 4056
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, N) for (int i = 0; i < (int)N; ++i)
#define all(a) (a).begin(), (a).end()
template <typename T>
class LiChaoTree {
  class Line {
   public:
    T gradients;
    T intercepts;
    Line(T a, T b) : gradients(a), intercepts(b) {}
    T y(T x) { return gradients * x + intercepts; }
  };

  vector<T> xs;
  vector<Line> nodes;
  int N;

  int V() { return 2 * N - 1; }

  // [l, r)
  void insert(int i, int l, int r, Line& line) {
    T xl = xs[l], xr = xs[r - 1];
    if (nodes[i].y(xl) <= line.y(xl) && nodes[i].y(xr) <= line.y(xr)) return;
    if (nodes[i].y(xl) > line.y(xl) && nodes[i].y(xr) > line.y(xr)) {
      nodes[i] = line;
      return;
    }

    int m = (l + r) / 2;
    T xm = xs[m];
    if (line.y(xm) < nodes[i].y(xm)) swap(line, nodes[i]);

    if (line.y(xl) < nodes[i].y(xl)) {
      insert(2 * i + 1, l, m, line);
    } else {
      insert(2 * i + 2, m, r, line);
    }
  }

 public:
  LiChaoTree(const vector<T>& x) : xs(x) {
    N = 1;
    while (N < xs.size()) N <<= 1;

    while (xs.size() < N) xs.push_back(xs.back() + 1);
    nodes.resize(V(), Line(0, 1e32));
  }

  void insert(T gradients, T intercepts) {
    Line line = Line(gradients, intercepts);
    insert(0, 0, N, line);
  }

  T y(int i) {
    T x = xs[i];
    i += N - 1;
    T res = nodes[i].y(x);
    while (i > 0) {
      i = (i - 1) / 2;
      res = min(res, nodes[i].y(x));
    }
    return res;
  }
};

int N;
ll C;
vector<ll> h;
int main() {
  cin >> N >> C;
  h.resize(N);
  rep(i, N) cin >> h[i];

  vector<ll> dp(N, 0);
  LiChaoTree<ll> t(h);
  for (int i = 1; i < N; ++i) {
    int j = i - 1;
    t.insert(-2LL * h[j], dp[j] + h[j] * h[j]);
    dp[i] = t.y(i) + h[i] * h[i] + C;
  }

  cout << dp[N - 1] << endl;
  return 0;
}


Measured memory_bytes: 14592
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,a) for(int i=0;i<(a);i++)
const ll MOD=1000000007;

int main(){
  int N,M; cin>>N>>M;
  vector<int> X(M); rep(i,M) cin>>X[i];
  if(N>=M){
    cout<<0<<endl;
    return 0;
  }
  sort(X.begin(),X.end());
  vector<int> V; rep(i,M-1) V.push_back(X[i+1]-X[i]);
  sort(V.begin(),V.end());
  int ans=0;
  // M-1-(N-1)
  rep(i,M-N) ans+=V[i];
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 1276
//minamoto
#include<bits/stdc++.h>
#define R register
#define fp(i,a,b) for(R int i=(a),I=(b)+1;i<I;++i)
#define fd(i,a,b) for(R int i=(a),I=(b)-1;i>I;--i)
#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)
template<class T>inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;}
template<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,1:0;}
using namespace std;
typedef long long ll;
const int N=1e5+5;
struct node{
	int l,r;ll d;
	inline node(R int li,R int ri,R ll di):l(li),r(ri),d(di){}
	inline bool operator <(const node &b)const{return d==b.d?r>b.r:d>b.d;}
};set<node>s;
int a[N],fa[N],l[N],r[N],ans[N],n,L,top;ll sum[N];
inline int find(R int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
int main(){
//	freopen("testdata.in","r",stdin);
	scanf("%d%d",&n,&L);
	fp(i,1,n)scanf("%d",&a[i]),fa[i]=l[i]=r[i]=i,sum[i]=a[i];
	fp(i,1,n-1)s.insert(node(i,i+1,a[i]+a[i+1]));
	while(!s.empty()&&s.begin()->d>=L){
		R int ql=s.begin()->l,qr=s.begin()->r;s.erase(s.begin());
		ans[++top]=r[find(ql)],find(qr);
		if(ql>1)find(ql-1),s.erase(node(l[fa[ql-1]],r[fa[ql]],sum[fa[ql-1]]+sum[fa[ql]]));
		if(qr<n)find(qr+1),s.erase(node(l[fa[qr]],r[fa[qr+1]],sum[fa[qr]]+sum[fa[qr+1]]));
		r[fa[ql]]=r[fa[qr]],sum[fa[ql]]+=sum[fa[qr]],fa[fa[qr]]=fa[ql];
		if(ql>1)s.insert(node(l[fa[ql-1]],r[fa[ql]],sum[fa[ql-1]]+sum[fa[ql]]));
		if(qr<n)s.insert(node(l[fa[ql]],r[fa[qr+1]],sum[fa[ql]]+sum[fa[qr+1]]));
	}
	if(top<n-1)return puts("Impossible"),0;
	puts("Possible");
	fd(i,top,1)printf("%d\n",ans[i]);
	return 0;
}

Measured memory_bytes: 9856
#include<bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define fi first
#define se second
#define pb push_back
using namespace std;
typedef long long ll;
const ll INF = 1e18;
const ll MOD = 1e9+7;

ll fastpowMOD(ll a, ll p,ll MOD);
ll fastpowMOD(ll a, ll p,ll MOD){ if(p==0) return 1; a %= MOD; ll z = fastpowMOD(a,p/2,MOD); z = (z*z)%MOD; if(p%2) z = (z*a)%MOD; return z; }

int main(){
  ll n;
  cin>>n;
  string str;
  cin>>str;
  ll cnt = 0;
  for(ll i=0;i<n-2;){
    if(str[i]=='A' && str[i+1]=='B' && str[i+2]=='C'){
      i += 3;
      cnt++;
    }
    else{
      i++;
    }
  }
  cout<<cnt<<"\n";
}

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

using ll = long long;
constexpr ll inf = 1e18;

int main() {
    int n, k; cin >> n >> k;
    vector<ll> h(n);
    for(int i = 0; i < n; ++i) {
        cin >> h[i];
    }
    auto hs = h;
    hs.push_back(0);
    sort(hs.begin(), hs.end());
    hs.erase(unique(hs.begin(), hs.end()), hs.end());
    for(int i = 0; i < n; ++i) {
        h[i] = lower_bound(hs.begin(), hs.end(), h[i]) - hs.begin();
    }

    const int m = hs.size();
    vector<vector<ll>> dp(m, vector<ll>(k + 1, inf));
    dp[0][0] = 0;
    for(int i = 0; i < n; ++i) {
        vector<vector<ll>> ndp(m, vector<ll>(k + 1, inf));
        for(int prev_h = 0; prev_h < m; ++prev_h) {
            for(int used = 0; used <= k; ++used) {
                { // the same
                    ndp[h[i]][used] = min(ndp[h[i]][used], dp[prev_h][used] + max(0LL, hs[h[i]] - hs[prev_h]));
                }
                if(used != k) { // change
                    ndp[prev_h][used + 1] = min(ndp[prev_h][used + 1], dp[prev_h][used]);
                }
            }
        }
        dp = move(ndp);
    }

    ll ans = inf;
    for(int i = 0; i < m; ++i) {
        ans = min(ans, dp[i][k]);
    }

    cout << ans << endl;
}


Measured memory_bytes: 1744
#include<bits/stdc++.h> 
using namespace std;
using ll=long long;
typedef pair<ll,ll> P;
#define fi first
#define se second
#define all(v) (v).begin(),v.end()
set<string> c;
const ll mod=1000000007;
const ll mod2=998244353;
const ll inf=100000000000000000;
ll gcd(ll a,ll b) {return b ? gcd(b,a%b):a;}
ll lcm(ll c,ll d){return c/gcd(c,d)*d;}
vector<int> dy={-1,0,1,0},dx={0,-1,0,1};
int main(){
 ll n,s;
 cin>>n>>s;
 if(s==n){cout<<n+1<<endl;return 0;}
 ll border=sqrt(n);
 for(int i=2;i<=sqrt(n)+100000;i++){
     ll res=0,rec=n;
     while(rec!=0){
          res+=rec%i;
          rec/=i;
     }
     if(res==s){cout<<i<<endl;return 0;}
 }
 vector<ll> tmp;
 for(ll i=2;i<=sqrt(n-s)+10000;i++){
     if((n-s)%(i-1)!=0)continue;
    tmp.push_back(i);
    tmp.push_back((n-s)/(i-1)+1);//(b-1)となるようなpを使いそこからbの候補を取得する（もう片方の約数）
     
 }
 sort(all(tmp));
 for(int i=0;i<tmp.size();i++){
     ll res=0,tm=tmp[i],rec=n;
    // cout<<tm<<endl;
     while(rec!=0){
          res+=rec%tm;
          rec/=tm;
     }
     if(res==s){cout<<tm<<endl;return 0;}
 }
 cout<<-1<<endl;
}




Measured memory_bytes: 256
#include<stdio.h>

#define N 100000

int search(int key);

int A[N];
int n;



int main(){
  
  int i, n2;
  int key, count = 0;

  
  scanf("%d", &n);
  
  for ( i = 0; i < n; i++ ) {
    
    scanf("%d", &A[i]);
    
  }

  scanf("%d", &n2);
  
  for ( i = 0; i < n2; i++ ){
    
    scanf("%d", &key);
    
    if ( search( key ) ) {
      
      count++;
      
    }
    
  }
  printf("%d\n", count);

  return 0;
}


int search(int key){
  
  int left = 0;
  int right = n;
  int mid;
  
  while( left < right ){
    
    mid = (left + right ) /2;
    if ( key == A[mid] ) return 1;
    if ( key > A[mid] ) left = mid + 1;
    else if ( key < A[mid] ) right = mid;
    
  }
  
  return 0;
}

Measured memory_bytes: 988
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
count_a = 0
count_b = 0
for i in range(n):
    count_a += max(0, (b[i] - a[i]) // 2)
    count_b += max(0, a[i] - b[i])
if sum(b) >= sum(a):
    if count_a >= count_b:
        print("Yes")
        exit()
print("No")


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

const int inf = 1000003;

int N;

int A[18], B[18];
int dp[36][(1<<18)];

int solve(int pos, int mask, int prev)
{
    if(pos == N)
        return 0;
    
    if(dp[prev][mask] != -1)
        return dp[prev][mask];

    int ans = inf, x = __builtin_popcount(mask);

    for(int i=0; i<N; i++)
    {
        if(mask & (1<<i))
        {
            x--;
            continue;
        }

        if(abs(i - pos) % 2)
        {
            if(B[i] >= prev)
                ans = min(ans, solve(pos+1, (mask | (1 << i)), B[i]) + abs(i + x - pos));
        }
        else
        {
            if(A[i] >= prev)
                ans = min(ans, solve(pos+1, (mask | (1 << i)), A[i]) + abs(i + x - pos));
        }
    }

    return dp[prev][mask] = ans;
}

int compress()
{
    map<int, int> M;

    for(int i=0; i<N; i++)
        M[ A[i] ], M[ B[i] ];
    
    int k = 0;

    for(auto &it : M)
        it.second = k++;
    
    for(int i=0; i<N; i++)
        A[i] = M[ A[i] ], B[i] = M[ B[i] ];
    
    return k;
}

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

    cin >> N;

    for(int i=0; i<N; i++)
        cin >> A[i];
    for(int i=0; i<N; i++)
        cin >> B[i];
    
    int maxx = compress();
    memset(dp, -1, sizeof(dp));

    int ans = solve(0, 0, 0);
    
    if(ans == inf)
        ans = -1;

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


Measured memory_bytes: 37248
#include <algorithm>
#include <bitset>
#include <climits>
#include <cmath>
#include <cstdio>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
#define REP(var, a, b) for (int var = (a); var < (b); var++)
#define rep(var, n) for (int var = 0; var < (n); ++var)
#define ALL(c) (c).begin(), (c).end()
#define rALL(c) (c).rbegin(), (c).rend()
ll MOD = 1000000007;
const ll INF = 1LL << 60;

int main() {
  //
  ll n,m,l;
  cin >> n >> m >> l;
  vvl dist(n, vl(n, INF)), dist2(n, vl(n, INF));
  rep(i, n) {
    dist[i][i] = 0;
    dist2[i][i] = 0;
  }
  rep(i,m) {
    ll a,b,c;
    cin >> a >> b >> c;
    a--, b--;
    if (c > l) {
      continue;
    }
    dist[a][b] = min(dist[a][b], c);
    dist[b][a] = min(dist[b][a], c);
  }
  rep(k, n) {
    rep(i,n) {
      rep(j, n) {
        dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
      }   
    }
  }
  rep(i, n) {
    rep(j, n) {
      if (dist[i][j] <= l) {
        dist2[i][j] = 0;
      }
    }
  }
  rep(k, n) {
    rep(i,n) {
      rep(j, n) {
        dist2[i][j] = min(dist2[i][j], dist2[i][k] + dist2[k][j] + 1);
      }   
    }
  }
  // rep(i,n) {
  //   rep(j,n) {
  //     cerr << dist[i][j] << " ";
  //   }
  //   cerr << endl;
  // }
  ll q;
  cin >> q;
  rep(i, q) {
    ll s, t;
    cin >> s >> t;
    s--, t--;
    if (dist2[s][t] == INF) {
      cout << -1 << endl;
    } else {
      cout << dist2[s][t] << endl;
      // if (dist[s][t] % l == 0) {
      //   cout << dist[s][t] / l - 1 << endl;
      // } else {
      //   cout << dist[s][t] / l << endl;
      // }
    }
  }
  return 0;
}


Measured memory_bytes: 1920