akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#include <math.h>
#define uint unsigned long long
#define ll long long
#define db double
#define ls rt << 1
#define rs rt << 1 | 1
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define X first
#define Y second
#define pcc pair<char, char>
#define vi vector<int>
#define vl vector<ll>
#define rep(i, x, y) for(int i = x; i <= y; i ++)
#define rrep(i, x, y) for(int i = x; i >= y; i --)
#define eps 1e-9

using namespace std;
inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}
struct node
{
    int x, id;
    bool operator <(const node &s)const
    {
        return x < s.x;
    }
}a[100010];
int main()
{
    int n, ans = 0;
    n = read();
    rep(i, 1, n) a[i].x = read(), a[i].id = i;
    sort(a + 1, a + n + 1);
    rep(i, 1, n)
        if (!(i & 1) && a[i].id & 1)
            ans ++;
    cout << ans;
    return 0;
}


Measured memory_bytes: 1024
/*****include*****/
#include <iostream>
#include <fstream>

/*****デバッグ定義*****/
//#define DEBUG
/*****マクロ定義*****/

/*****名前空間*****/
using namespace std;

/*****グローバル変数置き場*****/
int height[10];

/*****その他関数置き場*****/
void Q_sort(int left,int right){
	int threshold = (height[left] + height[right])/2;
	int i;
	int j;
	i = left;
	j = right;
	do{
		while(height[i] < threshold)	i++;
		while(height[j] > threshold)	j--;
		if(i <= j){
			int swap = height[i];
			height[i] = height[j];
			height[j] = swap;
			i++;
			j--;
		}
	}while(i <= j);
	if(j > left)	Q_sort(left,j);
	if(i < right)	Q_sort(i,right);
}
/*****main関数*****/
int main(){
	/*****ファイルオープン*****/
#ifdef DEBUG
	ofstream fout("output.txt");
	ifstream fin("input.txt");
	if(!fout || !fin){
		cout << "Can't open the file.\n";
		return;
	}
#endif
	/*****変数置き場*****/
	for(int i=0;i<10;i++)	cin >> height[i];
	Q_sort(0,9);
	for(int i=0;i<3;i++)	cout << height[9-i] << endl;
	/*****処理部*****/

	/*****処理終了後*****/
#ifdef DEBUG
	fout.close();
	fin.close();
#endif
	return 0;
}

Measured memory_bytes: 1160
H,W,K = map(int,input().split())
dp = [[0]*W for i in range(H+1)]
dp[0][0] = 1
MOD = 10**9+7
for i in range(H):
    for b in range(1<<(W-1)):
        if '11' in bin(b): continue
        for k in range(W):
            if k and b&(1<<(k-1)):
                dp[i+1][k-1] += dp[i][k]
            elif b&(1<<k):
                dp[i+1][k+1] += dp[i][k]
            else:
                dp[i+1][k] += dp[i][k]
print(dp[-1][K-1] % MOD)

Measured memory_bytes: 3064
#include <algorithm>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <functional>
#include <iostream>
#include <map>
#include <memory>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#include <iomanip>
using namespace std;

typedef long long ll;

#define sz size()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define all(c) (c).begin(), (c).end()
#define rep(i,a,b) for(ll i=(a);i<(b);++i)
#define per(i,a,b) for(ll i=(b-1);i>=(a);--i)
#define clr(a, b) memset((a), (b) ,sizeof(a))
#define ctos(c) string(1,c)
#define print(x) cout<<#x<<" = "<<x<<endl;

#define MOD 1000000007

int main() {
  ll n;
  cin>>n;
  ll a = 0;
  ll b = 0;
  vector<ll> v;
  rep(i,0,n){
    ll c;
    cin>>c;
    v.pb(c);
  }
  sort(all(v));
  reverse(all(v));
  rep(i,0,n){
    ll c = v[i];
    b += c;
    if(i%2==0){
      a += c;
    }
  }
  b-=a;
  cout << a-b << endl;
  return 0;
}

Measured memory_bytes: 256
import sys
input = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    a,b=MI()
    if a+b==15:
        print("+")
    elif a*b==15:
        print("*")
    else:
        print("x")

main()


Measured memory_bytes: 61924
N = int(input())
F = []
P = []

for _ in range(N):
    F.append([int(x) for x in input().split()])
for _ in range(N):
    P.append([int(x) for x in input().split()])

maxprofit = None
for i in range(1, 2**10):
    schedule = [int(x) for x in "{:010b}".format(i)]
    profit = 0
    for f,p in zip(F, P):
        c = sum(schedule[x] == f[x] and schedule[x] for x in range(10))
        profit += p[c]
    if maxprofit is None:
        maxprofit = profit
    else:
        maxprofit = max(maxprofit, profit)
        
print(maxprofit)




Measured memory_bytes: 3188
N = int(input())
query = [list(map(int, input().split())) for _ in range(N)]


def isvalid(i, j):
    H = -1
    for p, q, h in query:
        if h != 0:
            H = h + abs(p - i) + abs(q - j)
            break

    for p, q, h in query:
        if H == -1 and h != 0:
            H = h + abs(p - i) + abs(q - j)

        if h != max(H - abs(p - i) - abs(q - j), 0):
            return -1
    return H


for i in range(101):
    for j in range(101):
        H = isvalid(i, j)
        if H >= 1:
            print(i, j, H)
            exit()


Measured memory_bytes: 3064
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>
#include <tuple>
#include <cstdint>
#include <cstdio>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <deque>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <cctype>
#include <functional>
#include <ctime>
#include <cmath>
#include <limits>
#include <numeric>
#include <type_traits>
using namespace std;
using ll = long long;

unsigned euclidean_gcd(unsigned a, unsigned b) {
    if (a < b) return euclidean_gcd(b, a);
    unsigned r;
    while ((r = a % b)) {
        a = b;
        b = r;
    }
    return b;
}

class UnionFind {
public:
    vector <ll> par;
    vector <ll> siz;
    UnionFind(ll sz_) : par(sz_), siz(sz_, 1LL) {
        for (ll i = 0; i < sz_; ++i) par[i] = i;
    }
    void init(ll sz_) {
        par.resize(sz_);
        siz.assign(sz_, 1LL);
        for (ll i = 0; i < sz_; ++i) par[i] = i;
    }
    ll root(ll x) {
        while (par[x] != x) {
            x = par[x] = par[par[x]];
        }
        return x;
    }
    bool merge(ll x, ll y) {
        x = root(x);
        y = root(y);
        if (x == y) return false;
        if (siz[x] < siz[y]) swap(x, y);
        siz[x] += siz[y];
        par[y] = x;
        return true;
    }

    bool issame(ll x, ll y) {
        return root(x) == root(y);
    }

    ll size(ll x) {
        return siz[root(x)];
    }
};

long long modpow(long long a, long long n, long long mod) {
    long long res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}

long long modinv(long long a, long long mod) {
    return modpow(a, mod - 2, mod);
}

int main() {
    ll a, b;
    cin >> a >> b;
  ll ans;
  ans =b;
  for(int i = 0;i < a-1;i++){
    ans*=b-1;
}
  cout << ans << endl;
}

Measured memory_bytes: 256
n, x = map(int, input().split())
ans = 0
def search(level, i):
	global ans
	#print(level, i, ans)
	if level == 0:
		return ans + 1
	if i == 1:
		return ans
	elif i == 2 ** (level + 2) - 3:
		return ans + 2 ** (level + 1) - 1
	elif i == 2 ** (level + 1) - 1:
		return ans + 2 ** level
	elif i < 2 ** (level + 1) - 1:
		return search(level-1, i-1)
	else:
		ans += 2 ** level
		return search(level-1, i - (2 ** (level + 1) - 1))
print(search(n, x))

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

#define all(s) s.begin(), s.end()
#define pb push_back
#define ii pair<int, int>
#define x first
#define y second
#define bit(x, y) ((x >> y) & 1)
#define sz(s) ((int) (s).size())

const int MOD = 1000000007;

int x[100005];
long long pref[100005];

int power(int x, int y) {
    int res = 1;
    while (y) {
        if (y % 2) res = 1LL * res * x % MOD;
        y >>= 1;
        x = 1LL * x * x % MOD;
    }
    return res;
}

int fac(int x) {
    if (x == 0) return 1;
    return 1LL * x * fac(x - 1) % MOD;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0); 
    cout.tie(0);
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> x[i];
    }
    for (int i = 1; i <= n; i++) {
        pref[i] = pref[i - 1] + x[i];
    }
    int ans = 0;
    int fa = fac(n - 1);
    for (int i = 1; i <= n - 2; i++) {
        int temp = 1LL * fa * power(1LL * i * (i + 1) % MOD, MOD - 2) % MOD;
        temp = 1LL * temp * ((pref[n - 1] - pref[n - 1 - i] - pref[i]) % MOD) % MOD;
        ans = (ans + temp) % MOD;
    }
    for (int i = 1; i < n; i++) {
        int temp = x[n] - x[i];
        temp = 1LL * temp * fa % MOD * power(n - i, MOD - 2) % MOD;
        ans = (ans + temp) % MOD;
    }
    cout << ans;
    return 0;
}

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

int main()
{
    ll n,k;
    cin>>n;
    cin>>k;
    ll cost[n+1];
    ll dp[n+1];
    for(int i=1;i<=n;i++)
    {
        cin>>cost[i];

    }
    dp[n]=0;
    //dp[n-1]=abs(cost[n]-cost[n-1]);

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

        }
    }
    //
    cout<<dp[1]<<endl;
}

Measured memory_bytes: 5152
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
const int N = 1e5 + 5;
const ll mod = 998244353;
const int DEG = 30;
const double pi = acos(-1.0);
const double eps = 1e-8;
const int inf = 0x3f3f3f3f;
static auto faster_iostream = []() {
    std::ios::sync_with_stdio(false);  // turn off sync
    std::cin.tie(nullptr);             // untie in/out streams
    return 0;
}();
struct node{
	int val, num;
	bool operator < (const node &s)const{
		return val > s.val;
	}
}p[N];
int a[N];
int main(){
	int n, m;
	cin >> n >> m;
	priority_queue<int, vector<int>, greater<int> > q;
	ll ans = 0;
	for(int i = 1; i <= n; i++){
		cin >> a[i];
		q.push(a[i]);
		ans += a[i];
	}
	for(int i = 1; i <= m; i++){
		cin >> p[i].num >> p[i].val;
	}
	sort(p + 1, p + 1 + m);
	for(int i = 1; i <= m; i++){
		while(p[i].num--){
			int now = q.top();
			q.pop();
			if(now < p[i].val){
				ans += (p[i].val - now);
				q.push(p[i].val);
			}
			else {
				cout << ans << endl;
				return 0;
			}
		}
	}
	cout << ans << endl;
	return 0;
}

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

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;

#define fi first
#define se second
#define repl(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++)
#define rep(i,n) repl(i,0,n)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<x<<endl
#define mmax(x,y) (x>y?x:y)
#define mmin(x,y) (x<y?x:y)
#define maxch(x,y) x=mmax(x,y)
#define minch(x,y) x=mmin(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
#define exist(x,y) (find(all(x),y)!=x.end())
#define bcnt __builtin_popcountll

#define INF 1e16
#define mod 1000000007

ll N,K;
ll dp[301][301][301];

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

  cin>>N>>K;
  vector<ll> H(N);
  rep(i,N)cin>>H[i];

  rep(i,N+1)rep(j,N+1)rep(k,K+1)dp[i][j][k]=INF;
  dp[1][1][0]=H[0];
  dp[1][0][1]=0;
  repl(i,1,N)rep(j,i+1)rep(k,K+1){
    if(k<K){
      minch(dp[i+1][j][k+1],dp[i][j][k]);
    }
    if(j==0) minch(dp[i+1][i+1][k],dp[i][j][k]+H[i]);
    else{
      if(H[j-1]<H[i]) minch(dp[i+1][i+1][k],dp[i][j][k]+H[i]-H[j-1]);
      else minch(dp[i+1][i+1][k],dp[i][j][k]);
    }
  }
  ll res=INF;
  rep(j,N+1)rep(k,K+1)minch(res,dp[N][j][k]);
  cout<<res<<endl;

  return 0;
}


Measured memory_bytes: 213376
#include <bits/stdc++.h>
#define ADD(a, b) a = (a + ll(b)) % mod
#define MUL(a, b) a = (a * ll(b)) % mod
#define MAX(a, b) a = max(a, b)
#define MIN(a, b) a = min(a, b)
#define rep(i, a, b) for(int i = int(a); i < int(b); i++)
#define rer(i, a, b) for(int i = int(a) - 1; i >= int(b); i--)
#define all(a) (a).begin(), (a).end()
#define sz(v) (int)(v).size()
#define pb push_back
#define sec second
#define fst first
#define debug(fmt, ...) Debug(__LINE__, ":", fmt, ##__VA_ARGS__)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef pair<int, pi> ppi;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vl> mat;
typedef complex<double> comp;
void Debug() {cerr << '\n'; }
template<class FIRST, class... REST>void Debug(FIRST arg, REST... rest){
	cerr<<arg<<" ";Debug(rest...);}
template<class T>ostream& operator<<(ostream& out,const vector<T>& v) {
	out<<"[";if(!v.empty()){rep(i,0,sz(v)-1)out<<v[i]<<", ";out<<v.back();}out<<"]";return out;}
template<class S, class T>ostream& operator<<(ostream& out,const pair<S, T>& v){
	out<<"("<<v.first<<", "<<v.second<<")";return out;}
const int MAX_N = 500010;
const int MAX_V = 100010;
const double eps = 1e-6;
const ll mod = 1000000007;
const int inf = (1 << 30) - 1;
const ll linf = 1LL << 60;
const double PI = 3.14159265358979323846;
mt19937 rng; //use it by rng() % mod, shuffle(all(vec), rng)
///////////////////////////////////////////////////////////////////////////////////////////////////

int N;
int dp[MAX_N][2];

int A[MAX_N];

void solve() {
	cin >> N;
	rep(i, 0, N) cin >> A[i];
	rep(i, 1, N + 1) {
		rep(j, 0, 2) {
			dp[i][j] = inf;
		}
	}
	dp[1][0] = 1;
	dp[1][1] = 1;
	rep(i, 1, N) {
		MIN(dp[i + 1][0], dp[i][0] + (A[i - 1] > A[i]));
		MIN(dp[i + 1][1], dp[i][0] + 1);
		MIN(dp[i + 1][0], dp[i][1] + 1);
		MIN(dp[i + 1][1], dp[i][1] + (A[i - 1] < A[i]));
	}
	cout << min(dp[N][0], dp[N][1]) << "\n";
}

uint32_t rd() {
	uint32_t res;
#ifdef __MINGW32__
	asm volatile("rdrand %0" :"=a"(res) ::"cc");
#else
	res = std::random_device()();
#endif
	return res;
}

int main() {
#ifndef LOCAL
	ios::sync_with_stdio(false);
    cin.tie(0);
#endif
    cout << fixed;
	cout.precision(20);
    cerr << fixed;
	cerr.precision(6);
	rng.seed(rd());
#ifdef LOCAL
	//freopen("in.txt", "wt", stdout); //for tester
	if(!freopen("in.txt", "rt", stdin)) return 1;
#endif	
	solve();
    cerr << "Time: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
	return 0;
}



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

int main() {
  int n;
  cin>>n;
  vector<bool> a(n, false);
  ll sum=0;
  rep(i, n) {
    sum+=(i+1);
    a[i]=true;
    if (sum>n) {
      a[sum-n-1]=false;
      break;
    }
    if (sum==n) break;
  }
  rep(i, n) if (a[i]) cout<<(i+1)<<endl;
}

Measured memory_bytes: 1536
n, m, x = map(int, input().split())
c, all = [],[]
for _ in range(n):
  tmp = list(map(int, input().split()))
  c.append(tmp[0])
  all.append(tmp[1:])
ans = float('inf')
for bit in range(1, 1<<n):
  cost = 0
  totalA = [0]*m
  for i, al in enumerate(all):
    if (1<<i) & bit:
      for j, a in enumerate(al):
        totalA[j] += a
      cost += c[i]
  check = True
  for a in totalA:
    if a < x: check = False
  if check: ans = min(ans, cost)
if ans == float('inf'): print(-1)
else: print(ans)

Measured memory_bytes: 9036
# This was written by chizuchizu
import sys
# import collections

# import bisect
# import math
# import numpy as np
import itertools
"""Template"""


class IP:
    """
    入力を取得するクラス
    """

    def __init__(self):
        self.input = sys.stdin.readline

    def I(self):
        """
        1文字の取得に使います
        :return: int
        """
        return int(self.input())

    def S(self):
        """
        1文字の取得(str
        :return: str
        """
        return self.input()

    def IL(self):
        """
        1行を空白で区切りリストにします(int
        :return: リスト
        """
        return list(map(int, self.input().split()))

    def SL(self):
        """
        1行の文字列を空白区切りでリストにします
        :return: リスト
        """
        return list(map(str, self.input().split()))

    def ILS(self, n):
        """
        1列丸々取得します(int
        :param n: 行数
        :return: リスト
        """
        return [int(self.input()) for _ in range(n)]

    def SLS(self, n):
        """
        1列丸々取得します（str
        :param n: 行数
        :return: リスト
        """
        return [self.input() for _ in range(n)]

    def SILS(self, n):
        """
        Some Int LineS
        横に複数、縦にも複数
        :param n: 行数
        :return: list
        """
        return [self.IL() for _ in range(n)]

    def SSLS(self, n):
        """
        Some String LineS
        :param n: 行数
        :return: list
        """
        return [self.SL() for _ in range(n)]


"""ここからメインコード"""


def main():
    # 1文字に省略
    r, e = range, enumerate
    ip = IP()

    """この下から書いてね"""
    # n, m = ip.IL()
    # a = np.array(ip.IL())
    # for _ in range(m):
    #     a[np.argmax(a)] //= 2
    # print(np.sum(a))
    n, k = ip.IL()
    memo = ip.SILS(2*k)[1::2]
    memo = list(itertools.chain.from_iterable(memo))
    memo = list(set(memo))
    memo = [x - 1 for x in memo]
    new = [1 for _ in range(n)]
    for x in memo:
        new[x] = 0
    print(sum(new))
    # memo


main()

Measured memory_bytes: 9460
n = gets.to_i
x, y = n.times.map{ gets.split.map(&:to_i)}.transpose
pat = [*0..n-1].permutation(n).to_a
sum = pat.map do |l|
  (1..n-1).map do |j|
    Math.sqrt((x[l[j-1]] - x[l[j]])**2 + (y[l[j-1]] - y[l[j]])**2)
  end.inject(:+)
end.inject(:+)
puts sum / pat.size

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

#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <unordered_map>
#include <queue>
#include <algorithm>

#include <bits/stdc++.h>
#include <cmath>
#include <limits>

using namespace std;

int main(int argc, char* argv[]){
	int N, K;
	int A[100000+2] = {0};

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

	//A1, ... , ANは 1, 2, ... , Nの並び替え
	//最小は1。最終的な数列は all 1の数列。
	int ind_min = 0;
	for(int i=1; i<=N; i++){
		if(A[i] == 1){
			ind_min = i;
		}
	}

	int ans = (N - 1) / (K - 1);
	if((N - 1) % (K - 1) != 0){
		ans++;
	}
	printf("%d\n", ans);
	return 0;
}

Measured memory_bytes: 640
from math import gcd
from itertools import combinations_with_replacement
def gcds(a):
    tmp = None
    for i in a:
        if tmp == None:
            tmp = i
        else:
            tmp = gcd(i, tmp)
    return tmp


cnt = 0
n = int(input())
for i in combinations_with_replacement(range(1, n + 1), 3):
    tmp = gcds(i)
    # cnt += 6 * tmp
    if len(set(i)) == 3:
        tmp *= 6
        cnt += tmp
    elif len(set(i)) == 2:
        tmp *= 3
        cnt += tmp
    else:
        cnt += tmp
print(cnt)

Measured memory_bytes: 74088
#include <bits/stdc++.h>
#define MOD 1000000007
#define md %998244353
#define INF 2e9
#define EPS 1e-9
#define MAX LLONG_MAX
#define MIN LLONG_MIN
#define F first
#define S second
#define MP make_pair
#define PB push_back
#define EB emplace_back
#define endl "\n"
#define FOR(i,a,b) for (long long i = a; i < b; i++)
#define REV(i,a,b) for (long long i = a; i > b; i--)
#define mset(a, v) memset(a, v, sizeof(a))
#define fd(n) fixed<<setprecision(n)
typedef std::pair<int, int> pii;
typedef std::vector<long long> vi;
typedef std::vector<vi> vvi;
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

ll solve(ll x,ull y,ll p) {
    ll res = 1;
    x = x % p;
    while (y > 0) {
        if (y & 1)
            res = (res*x) % p;
        y = y>>1;
        x = (x*x) % p;
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
   
   ll i,j,n;
    cin>>n;
    ll ans=0;
    if(n>=500)
      {
      		ans = (n/500)*(1000);
      	 n=n%500;
      
  }
  
    	if(n>=5)
      	  ans = (n/5)*5 + ans;
   
   cout<<ans;



}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <chrono>
#define watch(x) cout << (#x) << " is " << (x) << endl
#define eps 1e-9

typedef long long ll;

using namespace std;

const int N = 1e5;
int a[N+5];

int main()

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

    int a, b;
    string s;

    cin >> a >> b >> s;

    for (int i = 0; i < s.size(); i++) {

        if (i == a && s[i] != '-') {

            cout << "No";
            return 0;
        }

        if (i != a && !(s[i] >= '0' && s[i] <= '9')) {

            cout << "No";
            return 0;
        }
    }

    cout << "Yes";

    return 0;
}


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

int main(){
  string str;
  cin >> str;
  string ans="Yes";
  if(str.size()%2==1){
    ans="No";
  }
  for(int i=0;i<str.size();i++){
    if(i%2==0){
      if(str.at(i)!='h'){
        ans="No";
      }
    }
    if(i%2==1){
      if(str.at(i)!='i'){
        ans="No";
      }
    }
  }
  cout<<ans;  
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const int maxn = 3e3 + 10;
int a, b, c, d, e, f;
double ma;
int _a, _b;
bool vis[maxn][maxn];

void dfs(int x, int y) {
    if(x + y > f || vis[x][y] || (y * 1.0) / x > e * 1.0 / 100.0) return;
    vis[x][y] = true;
    double ans = (y * 100.0) / (x + y);
    if(ans >= ma) {
        ma = ans;
        _a = x, _b = y;
    }
    dfs(x + a * 100, y);
    dfs(x + b * 100, y);
    dfs(x, y + c);
    dfs(x, y + d);
}

int main(void) {
    scanf("%d%d%d%d%d%d", &a, &b, &c, &d, &e, &f);
    dfs(0, 0);
    printf("%d %d\n", _a + _b, _b);
}


Measured memory_bytes: 6400
#include <algorithm>
#include <deque>
#include <iostream>
#include <map>
#include <math.h>
#include <queue>
#include <set>
#include <stack>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unordered_map>
#include <vector>

int main() {
  std::string s;
  std::cin >> s;
  std::map<char, int > mp;
  for (int i=0; i<s.length(); i++){
    mp[s[i]]++;
  }
  int pcount_ideal = s.length()/2;
  int gcount_ideal = s.length() - pcount_ideal;
  int ans = pcount_ideal - mp['p'];
  std::cout << ans << std::endl;
  return 0;
}


Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i=0; i<n; i++)
#define rep1(i, n) for(int i=1; i<=n; i++)
#define repr(i, n) for(int i=n-1; i>=0; i--)
#define repr1(i, n) for(int i=n; i>=1; i--)
#define all(v) v.begin(),v.end()
using ll = long long;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
const int INF = 1e9;
const ll LLINF = 1e18;
const ll MOD = 1e9+7;
const double EPS = 1e-10;
const double PI = acos(-1);
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; }

int n, k;
int r, s, p;
string t;

int main() {
    cin >> n >> k >> r >> s >> p >> t;

    vector<bool> win(100010, false);
    int ans = 0;
    rep(i, n) {
        if (i >= k && t[i] == t[i-k] && win[i-k]) continue;
        if (t[i] == 'r') ans += p;
        if (t[i] == 's') ans += r;
        if (t[i] == 'p') ans += s;
        win[i] = true;
    }
    cout << ans << endl;
}


Measured memory_bytes: 3696
#include <stdio.h>

int main(){
    int n, cnt, ans;
    int S[101], T[101];

    ans = 0;
    cnt = 0;

    scanf("%d",&n);
    for (int i=0;i<n;i++) {
        scanf("%d %d",&S[i],&T[i]);
        if(S[i] == T[i]) cnt++;
        else cnt = 0;
        if(cnt > 2) ans++;
    }
    if(ans > 0) printf("Yes");
    else printf("No");
    return 0;
}

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

namespace ABC168
{
    class C
    {
        static void Main(string[] args)
        {
            //var A = Console.ReadLine().Split().Select(long.Parse).ToArray();
            //var abcd = Enumerable.Repeat(0, (int)Q).Select(_ => Console.ReadLine().Split().Select(long.Parse).ToArray()).ToArray();

            var ABHM = Console.ReadLine().Split().Select(double.Parse).ToArray();
            var A = ABHM[0]; var B = ABHM[1]; var H = ABHM[2]; var M = ABHM[3];

            double kakudoA = (360.0 / (12.0 * 60.0)) * (H * 60.0 + M);
            double kakudoB = (360.0 / 60.0) * M;
            double kakudoAB = Math.Abs(kakudoA - kakudoB);
            double kakudo = Math.Min(kakudoAB, 360.0 - kakudoAB);
            Console.WriteLine(Math.Sqrt(Math.Pow(A, 2) + Math.Pow(B, 2) - 2 * A * B * Math.Cos(kakudo * (Math.PI / 180))));
        }
    }
}


Measured memory_bytes: 28636
//Accepted
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main{
	static StringBuilder sb=new StringBuilder();
	public static void main(String[] args) {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		String work[]=new String[3];
		int m;
		int f;
		int r;

		//入力
		try {
			while(true){
				//nとmとrの入力
				work=br.readLine().split("\\s+");
				m=Integer.parseInt(work[0]);
				f=Integer.parseInt(work[1]);
				r=Integer.parseInt(work[2]);
			
				if(m==-1 && f==-1 && r==-1) {break;}
				
				if(m==-1 || f==-1) {	//Fの判定
					sb.append("F");
					sb.append(String.format("%n", ""));
				}else if(m+f >= 80) {	//Aの判定
					sb.append("A");
					sb.append(String.format("%n", ""));
				}else if(m+f >= 65) {
					sb.append("B");
					sb.append(String.format("%n", ""));
				}else if(m+f >= 50) {
					sb.append("C");
					sb.append(String.format("%n", ""));
				}else if((m+f>=30) && (r>=50)) {
					sb.append("C");
					sb.append(String.format("%n", ""));
				}else if(m+f >= 30){
					sb.append("D");
					sb.append(String.format("%n", ""));
				}else {
					sb.append("F");
					sb.append(String.format("%n", ""));
				}
				
			}

		}catch(Exception e) {
			e.printStackTrace();
		}
		
		//出力
		System.out.print(sb);
	}
	
}


Measured memory_bytes: 24664
#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

int main(){
	int a, b, k;
	cin >> a >> b >> k;
	int answer = a - b;
	for(int i = 0; i < (1 << 10); ++i){
		int p = a, q = b, borrow = 0, result = 0;
		if(__builtin_popcount(i) > k){ continue; }
		for(int j = 0, d = 1; p || q; ++j, d *= 10, p /= 10, q /= 10){
			int x = p % 10, y = q % 10;
			if(x - borrow >= y){
				result += (x - borrow - y) * d;
				borrow = 0;
			}else if(i & (1 << j)){
				result += (x - borrow - y + 10) * d;
				borrow = 0;
			}else{
				result += (x - borrow - y + 10) * d;
				borrow = 1;
			}
		}
		if(borrow == 0){ answer = max(answer, result); }
	}
	cout << answer << endl;
	return 0;
}

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

int main(){
  string s,t;
  cin >> s >> t;
  for(char c = 'a';c <= 'z';++c){
    if(s+c == t){
      puts("Yes");
      return 0;
    }
  }
  puts("No");
  return 0;
}


Measured memory_bytes: 3628
#include <bits/stdc++.h>
using namespace std;
//#pragma GCC optimize ("O3")
//#pragma GCC target ("sse4")
#define endl "\n"
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
template<class T, class T2> inline bool chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; }
template<class T, class T2> inline bool chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; }
const ll mod = 998244353;
template<class T> inline void fix(T &x) {if(x >= mod | x <= -mod) {x %= mod;} if(x < 0) {x += mod;}}

const int MAX_N = 3e3 + 10;
ll dp[MAX_N][MAX_N], sum[MAX_N], arr[MAX_N];

signed main() {
    //ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int n, s;
    cin >> n >> s;
    for(int i = 1; i <= n; i ++) {
        cin >> arr[i];
    }
    dp[0][0] = 1;
    for(int i = 1; i <= n; i ++) {
        dp[i][0] ++;
        for(int j = 0; j <= s; j ++) {
            if(j >= arr[i]) {
                dp[i][j] += dp[i - 1][j - arr[i]];
            }
            dp[i][j] += dp[i - 1][j];
            dp[i][j] %= mod;
        }
        for(int j = 0; j < MAX_N; j ++) {
            sum[j] += dp[i][j]; sum[j] %= mod;
        }
    }
    cout << sum[s];
    return 0;
}




Measured memory_bytes: 70784
N, M, Q = map(int, input().split())

a = [[0] * (N + 1) for _ in range(N+1)]
for _ in range(M):
    l, r = map(int, input().split())
    a[l][r] += 1
for i in range(1, N+1):
    for j in range(1, N+1):
        a[i][j] += a[i][j-1]
for i in range(1, N+1):
    for j in range(1, N+1):
        a[i][j] += a[i-1][j]

for _ in range(Q):
    p, q = map(int, input().split())
    print(a[q][q] - a[p-1][q] - a[q][p-1] + a[p-1][p-1])


Measured memory_bytes: 15252
import itertools
n = int(input())
p = list(map(str,input().split()))
q = list(map(str,input().split()))
a = "".join(p)
b = "".join(q)
l = []
m = []
c = 0
d = ""
x = 0
y = 0

for num in itertools.permutations(p):
    d = "".join(num)
    m.append(d)

l = sorted(m)

x = l.index(a)
y = l.index(b)

print(abs(x-y))


Measured memory_bytes: 6424
#include <bits/stdc++.h>
#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 sar(a,n) cout<<#a<<":";rep(pachico,n)cout<<" "<<a[pachico];cout<<endl
#define svec(v) cout<<#v<<":";rep(pachico,v.size())cout<<" "<<v[pachico];cout<<endl
#define svecp(v) cout<<#v<<":";each(pachico,v)cout<<" {"<<pachico.first<<":"<<pachico.second<<"}";cout<<endl
#define sset(s) cout<<#s<<":";each(pachico,s)cout<<" "<<pachico;cout<<endl
#define smap(m) cout<<#m<<":";each(pachico,m)cout<<" {"<<pachico.first<<":"<<pachico.second<<"}";cout<<endl
#define ll __int128
#define int ll

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 = 100005;

int cnt(ll val)
{
    int res = 0;
    while(val){
        res += val % 10;
        val /= 10;
    }
    return res;
}

signed main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    long long K;
    cin >> K;
    vl vec;
    ll val = 1;
    rep(i,3){
        srep(j,2,11){
            vec.pb(val*j-1);
        }
        val *= 10;
    }
    rep(i,14){
        srep(j,1,10){
            srep(k,1,101){
                vec.pb(val*j+val/100*k-1);
            }
        }
        val *= 10;
    }
    sort(all(vec));
    vi num(len(vec));
    rep(i,len(vec)){
        num[i] = cnt(vec[i]);
    }
    rep(i,len(vec)){
        bool ok = true;
        srep(j,i+1,len(vec)){
            if(vec[j]*num[i] < vec[i]*num[j]){
                ok = false;
                break;
            }
        }
        if(ok){
            cout << (long long)vec[i] << "\n";
            K--;
            if(K == 0){
                break;
            }
        }
    }
    return 0;
}


Measured memory_bytes: 1020
#include<bits/stdc++.h>
#define LL long long
#define maxn 200010
using namespace std;

int main(){
	LL h;
	cin >> h;
	LL now = 1;
	LL ans = 0;
	while(h){
		h = h / 2;
		ans = ans + now;
		now = now * 2;
	}
	cout << ans << endl;
	return 0;
} 

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

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int INF = 1e9;

int main(){
    int n;
    cin >> n;
    map<string, int> mp;
    string s;
    for (int i = 0; i < n; ++i) {
        cin >> s;
        if (s == "AC") mp["AC"]++;
        if (s == "WA") mp["WA"]++;
        if (s == "TLE") mp["TLE"]++;
        if (s == "RE") mp["RE"]++;
    }
    cout << "AC x " << mp["AC"] << endl;
    cout << "WA x " << mp["WA"] << endl;
    cout << "TLE x " << mp["TLE"] << endl;
    cout << "RE x " << mp["RE"] << endl;
}

Measured memory_bytes: 3636
let rec gcd x y =
  let r = x mod y in 
  if r = 0 then y else gcd y r


let rec lcm a = function
  | [] -> a
  | b :: rest -> 
    let n = a / gcd a b * b in lcm n rest


let rec get_input l n =
  if n = 0 then l
  else get_input (read_int () :: l) (n - 1)


let () =
  read_int ()
  |> get_input []
  |> lcm 1
  |> Printf.printf "%d\n"


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

using mint = atcoder::modint998244353;
struct S {
    mint a;
    int sz;
};
struct F {
    mint b;
    mint c;
};
S f_sum(S x, S y) {
    return S{x.a+y.a, x.sz+y.sz};
}
S f_map(F f, S a) {
    return S{f.b*a.a+f.c*a.sz, a.sz};
}
F f_comp(F f2, F f1) {
    return F{f2.b*f1.b, f2.b*f1.c+f2.c};
}
S f_e() {
    return S{0,0};
}
F f_id() {
    return F{1,0};
}


ll solve() {
    ll N, Q, t, l, r, b, c, a;
    cin >> N >> Q;
    vector<S> A(N);
    for ( int i = 0; i < N; i++ ) {
        cin >> a;
        A[i] = S{a,1};
    }
    atcoder::lazy_segtree<S,f_sum,f_e,F,f_map,f_comp,f_id> sg(A);
    vector<ll> ans;
    for ( int q = 0; q < Q; q++ ) {
        cin >> t;
        if ( t == 0 ) {
            cin >> l >> r >> b >> c;
            sg.apply(l,r, F{b,c});
        } else {
            cin >> l >> r;
            S x = sg.prod(l,r);
            ans.push_back(x.a.val());
        }
    }
    for ( ll an : ans ) {
        cout << an << "\n";
    }
    return 0;
}

int main() {
    solve();
    return 0;
}

Measured memory_bytes: 21524
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
from heapq import heappop, heappush
from collections import defaultdict
sys.setrecursionlimit(10**7)
import math
#from itertools import product, accumulate, combinations, product
#import bisect
#import numpy as np
#from copy import deepcopy
#from collections import deque
#from decimal import Decimal
#from numba import jit

INF = 1 << 50
EPS = 1e-8
mod = 10 ** 9 + 7

def mapline(t = int):
    return map(t, sysread().split())
def mapread(t = int):
    return map(t, read().split())


def run():
    N, M = mapline()
    cache = {}
    for i in range(M):
        a, b = mapline()
        cache[a] = cache.get(a, 0) + 1
        cache[b] = cache.get(b, 0) + 1

    for key in cache.keys():
        if cache[key] % 2:
            print('NO')
            return

    print('YES')
    return

if __name__ == "__main__":
    run()


Measured memory_bytes: 14616
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < n; ++i)
#define ALL(v) v.begin(), v.end()
typedef long long ll;
typedef pair<int, int> P;
const int INF = 1000000007;

int main()
{
   int n;
   cin >> n;
   vector<int> a1(n),a2(n);
   rep(i,n)
   {
      cin >> a1[i];
   }
   rep(i,n)
   {
      cin >> a2[i];
   }
   int ans = 0;
   int right = a1[0],left=0;
   rep(i,n)left+=a2[i];
   ans = right + left;
   for(int i = 1;i<n;i++)
   {
      right += a1[i];
      left -= a2[i-1];
      ans = max(ans,right+left);
   }
   cout<<ans<<endl;
   return 0;
}

Measured memory_bytes: 256
import java.util.Arrays;
import java.util.Scanner;
import java.util.stream.Collectors;

public class Main {

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

        int n = sc.nextInt();

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


        int count = 0;
        while (true) {
            boolean exchangeable = false;
            for (int i = n - 1; i > 0; i--) {
                if (a[i] < a[i - 1]) {
                    int temp = a[i];
                    a[i] = a[i - 1];
                    a[i - 1] = temp;
                    exchangeable = true;
                    count++;
                }
            }
            if (!exchangeable) {
                break;
            }
        }
        System.out.println(Arrays.stream(a).mapToObj(String::valueOf).collect(Collectors.joining(" ")));
        System.out.println(count);
    }
}



Measured memory_bytes: 32596
#include <bits/stdc++.h>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

int main() {
  int A, B, C, D;
  cin >> A >> B >> C >> D;
  if (A*B>=C*D) {
    cout << A*B << endl;
  }
  else {
    cout << C*D << endl;
  }
}


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

int main(){
  int n;
  cin >> n;
  int counta=0;
  int sum=0;
  vector<int> a(n);
  for(int i=0;i<n;i++){
    cin >> a[i];
    sum += a[i];
  }
  sort(a.begin(),a.end());
  for(int i=n-1;i>=0;i-=2){
    counta+=a[i];
  }
  cout << 2*counta-sum << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;
typedef string str;
static const long long INF = INT64_MAX;
static const long long MOD = (ll)1e9+7;

#define endl "\n"
#define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL)
#define REP(i, n) for(ll i=0;i<n;i++)
#define SZ(v) (ll)((v).size())
#define WHOLE(v) (v).begin(), (v).end()
#define ASC(v) sort((v).begin(), (v).end())
#define DESC(v) sort((v).rbegin(), (v).rend())
#define INV(v) reverse((v).begin(), (v).end())
#define FOLDL(src, dst, lambda) partial_sum((src).begin(), (src).end(), (dst).begin(), lambda)
#define FOLDR(src, dst, lambda) INV(src);partial_sum((src).begin(), (src).end(), (dst).begin(), lambda);INV(dst)
#define CUMSUML(src, dst) FOLDL(src, dst, [](auto a, auto b) {return a+b;})
#define CUMSUMR(src, dst) FOLDR(src, dst, [](auto a, auto b) {return a+b;})
#define ACCUM(v, d0, lambda) accumulate((v).begin(), (v).end(), d0, lambda)
#define SUM(v, d0) ACCUM(v, d0, [](auto a, auto b) {return a+b;})
#define ERASE(v, i) v.erase(v.begin() + i)
#define UNIQ(v) ASC(v);v.erase(unique(v.begin(), v.end()), v.end())

template <typename T>void debug(T t) {cerr << t << endl;}
template <typename T, typename ...Args>void debug(T t, Args ...args) {cerr << t << " ";debug(args...);}
template <typename T>void out(T t) {cout << t << endl;}
template <typename T, typename ...Args>void out(T t, Args ...args) {cout << t << " ";out(args...);}

void solve() {
    ll N, M;
    cin >> N >> M;
    vll s2i(N), i2g(N);
    REP(i, M) {
        ll a,b;
        cin >> a >> b;
        a--;b--;
        if(a==0) s2i[b]|=1;
        if(b==N-1) i2g[a]|=1;
    }
    REP(i, N) {
        if(s2i[i]&&i2g[i]) {
            out("POSSIBLE");
            return;
        }
    }
    out("IMPOSSIBLE");
}

int main() {
    fast_io;
    solve();
    return 0;
}


Measured memory_bytes: 3328
n = int(input())
a_ls = list(map(int, input().split()))
r = 0
ans = 0
S = a_ls[0]
for l in range(n):
    if l == r and S == 0:
        S = a_ls[l]
    while r + 1 < n and S+a_ls[r+1] == S^a_ls[r+1]:
        S += a_ls[r+1]
        r += 1
    ans += r - l + 1
    if r == l:
        r += 1
    S -= a_ls[l]
print(ans)



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

// #undef DEBUG  // Uncomment this line to forcefully disable debug print.
#if DEBUG
template <typename T>
void debug(T value) {
  std::cerr << value;
}
template <typename T, typename... Ts>
void debug(T value, Ts... args) {
  std::cerr << value << ", ";
  debug(args...);
}
#define dbg(...)                              \
  do {                                        \
    cerr << #__VA_ARGS__ << ": ";             \
    debug(__VA_ARGS__);                       \
    cerr << " (L" << __LINE__ << ")" << endl; \
  } while (0)
#else
#define dbg(...)
#endif

void read_from_cin() {}
template <typename T, typename... Ts>
void read_from_cin(T& value, Ts&... args) {
  std::cin >> value;
  read_from_cin(args...);
}
#define in(type, ...) \
  type __VA_ARGS__;   \
  read_from_cin(__VA_ARGS__);

template <typename T>
void write_to_cout(const T& value) {
  std::cout << value << std::endl;
}
template <typename T, typename... Ts>
void write_to_cout(const T& value, const Ts&... args) {
  std::cout << value << ' ';
  write_to_cout(args...);
}
#define out(...) write_to_cout(__VA_ARGS__);

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

using ll = long long;

template <typename T>
using V = std::vector<T>;
template <typename T>
using VV = V<V<T>>;

using namespace std;

template <typename T>
class BIT {
 public:
  BIT(int n) : v_(n + 1) {}
  T Sum(int i) const {
    T ret = 0;
    while (i) {
      ret += v_[i];
      i -= i & -i;
    }
    return ret;
  }
  T Get(int i) const { return Sum(i) - Sum(i - 1); }
  void Add(int i, T v) {
    while (i < v_.size()) {
      v_[i] += v;
      i += i & -i;
    }
  }

 private:
  std::vector<T> v_;
};

struct Q {
  int l, r, i, v;
};

int main() {
  in(int, n, q);
  V<int> c(n);
  rep(i, n) cin >> c[i];
  V<Q> qs;
  rep(i, q) {
    in(int, l, r);
    qs.push_back({l, r, i, 0});
  }
  sort(all(qs), [](const Q& a, const Q& b) { return a.r < b.r; });
  V<int> seen(n);
  int seen_cnt = 0;
  BIT<int> bit(n);
  auto qit = qs.begin();
  V<int> ans(q);
  rep(i, n) {
    int& s = seen[c[i] - 1];
    if (s == 0) {
      ++seen_cnt;
    } else {
      bit.Add(s, -1);
    }
    s = i + 1;
    bit.Add(i + 1, 1);
    while (qit != qs.end() && qit->r == i + 1) {
      ans[qit->i] = seen_cnt - bit.Sum(qit->l - 1);
      ++qit;
    }
  }
  rep(i, q) out(ans[i]);
}

Measured memory_bytes: 19384
#pragma GCC optimize("Ofast")
#pragma GCC target("avx")
//#undef LOCAL
#include <bits/stdc++.h>

using namespace std;
using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n - 1); }
template <class T> using V = vector<T>;
template <class T> using VV = V<V<T>>;

template<class T, class U> void chmin(T& t, const U& u) { if (t > u) t = u; }
template<class T, class U> void chmax(T& t, const U& u) { if (t < u) t = u; }

#ifdef LOCAL
#define show(x) cerr << __LINE__ << " : " << #x << " = " << (x) << endl
#else
#define show(x) true
#endif

template <class T, class U>
ostream& operator<<(ostream& os, const pair<T, U>& p) {
    return os << "P(" << p.first << ", " << p.second << ")";
}

template <class T> ostream& operator<<(ostream& os, const V<T>& v) {
    os << "[";
    for (auto d : v) os << d << ", ";
    return os << "]";
}

const int MN = 2020;
using B = bitset<MN>;

VV<int> tr;
VV<int> near;
VV<B> ok;

void dfs(int p, int b, int rt, int ci, B& buf) {
    buf.set(p);
    near[rt][p] = ci;
    for (int d: tr[p]) {
        if (d == b) continue;
        dfs(d, p, rt, ci, buf);
    }
}

V<B> g;
int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(20);
    
    int n, m;
    cin >> n >> m;
    tr = VV<int>(n);
    ok = VV<B>(n);
    g = V<B>(n);
    for (int i = 0; i < n - 1; i ++) {
        int a, b;
        cin >> a >> b; a--; b--;
        tr[a].push_back(b);
        tr[b].push_back(a);
    }


    near = VV<int>(n, V<int>(n, -1));     
    for (int s = 0; s < n; s++) {
        int deg = int(tr[s].size());
        V<B> buf(deg);
        ok[s] = V<B>(deg);
        for (int i = 0; i < deg; i++) {
            dfs(tr[s][i], s, s, i, buf[i]);
        }
        B sm = B();
        for (int i = 0; i < deg; i++) {
            ok[s][i] |= sm;
            sm |= buf[i];
        }
        sm.reset();
        for (int i = deg - 1; i >= 0; i--) {
            ok[s][i] |= sm;
            sm |= buf[i];
        }
    }    

    using P = pair<int, int>;
    queue<P> que;
    auto add_edge = [&](int a, int b) {
        if (a == b || g[a][b]) return;
        g[a].set(b);
        g[b].set(a);
        que.push({a, b});
        que.push({b, a});
    };
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b; a--; b--;
        add_edge(a, b);
    }
    while (!que.empty()) {
        int a, b;
        tie(a, b) = que.front(); que.pop();
/*        show(a);
        show(b);
        show(g[a]);
        show(g[b]);
        show(near[a][b]);
        show(ok[a][near[a][b]]);*/
        auto ne = ok[a][near[a][b]] | ok[b][near[b][a]];
        auto mp = (g[a] & ne) & ~g[b];
        while (mp.any()) {
            int c = mp._Find_first();
            add_edge(b, c);
            mp.reset(c);
        }
    }

    int ans = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (g[i][j]) ans++;
        }
    }
    cout << ans << endl;
    return 0;
}



Measured memory_bytes: 50436
// ~maqsat~
/*    
**	  “Anyone who has never made a mistake has never tried anything new.”
**    © Albert Einstein
*/

// #pragma GCC target ("avx2")
// #pragma GCC optimization ("Ofast")
// #pragma GCC optimization ("unroll-loops")

// #pragma comment(linker, "/stack:200000000")
// #pragma GCC optimize("Ofast")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

#define F first
#define S second
#define in insert
#define pb push_back
#define eb emplace_back
#define sz(x) int(x.size())
#define all(x) x.begin(), x.end()
#define count1 __builtin_popcountl
#define debug(x) cerr << (#x) << " = " << (x) << "\n"
#define ACCELERATE ios_base::sync_with_stdio(false),cin.tie(nullptr)
#define fre(f) if(fopen(f".in", "r")) freopen(f".in", "r", stdin),freopen(f".out", "w", stdout)

using namespace std;
using namespace __gnu_pbds;

using ll = long long;
using ull = unsigned long long;
// using big = __int128_t; // -10^38...10^38
using db = double;
using ld = long double;
typedef pair<int,int> ii;
typedef pair<ll,ll> pll;

template <class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template <class T> inline void cmin(T &a, T b) { a = min(a, b); }
template <class T> inline void cmax(T &a, T b) { a = max(a, b); }

const int oo = 0x3f3f3f3f;
const ll N = 1e5 + 345;
const ll MOD = 1e9 + 7;
const ll INF = 1e10 + 9;
const db EPS = 1e-9;
const db PI = acos(-1); // 3.14159265358979323846
const int dx[] = {1, -1, 0, 0, 1, 1, -1, -1};
const int dy[] = {0, 0, 1, -1, 1, -1, -1, 1};

int main() {
    fre("");
    ACCELERATE;

	int n;
	cin >> n;

	int a[N];
	unordered_map<int, int> cnt;
	for(int i = 0; i < n; i++) cin >> a[i], cnt[a[i]]++;

	int ans = 0;
	for(auto i: cnt) {
		if(i.F == i.S) continue;
		else if(i.F > i.S) ans += i.S;
		else ans += (i.S - i.F);
	}

	cout << ans;
    return 0;
}
/*
 
*/


Measured memory_bytes: 4644
<?php
list($n) = ints();
$p = [1, 1];
for ($i = 0; $i < $n; ++$i) {
    $a = ints();
    if ($a[0] >= $p[0] && $a[1] >= $p[1]) {
        $p = $a;
        continue;
    }
    //$m = max((int) ceil($p[0] / $a[0]), (int) ceil($p[1] / $a[1]));
    $m[0] = $p[0] % $a[0] ? intdiv($p[0], $a[0]) + 1 : intdiv($p[0], $a[0]);
    $m[1] = $p[1] % $a[1] ? intdiv($p[1], $a[1]) + 1 : intdiv($p[1], $a[1]);
    $p = [$a[0] * max($m), $a[1] * max($m)];
}
echo array_sum($p);
function ints()
{
    return array_map('intval', explode(' ', trim(fgets(STDIN))));
}


Measured memory_bytes: 4604
#include <iostream>
#include <vector>
#include <cstdio>
#include <algorithm>
#include <utility>
#include <string>
#include <cmath>
#include <set>
#include <functional>
#include <map>
#include <queue>
#include <cstring>
#include <stack>
#include <iomanip>
#include <climits>
#include <numeric>
using namespace std;
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define show(x) cout << #x << " = " << x << endl;
typedef long long ll;
typedef pair<int,int> pii;
int prime[]={
    2,79,191,311,439,577,709,857,
    3,83,193,313,443,587,719,859,
    5,89,197,317,449,593,727,863,
    7,97,199,331,457,599,733,877,
    11,101,211,337,461,601,739,881,
    13,103,223,347,463,607,743,883,
    17,107,227,349,467,613,751,887,
    19,109,229,353,479,617,757,907,
    23,113,233,359,487,619,761,911,
    29,127,239,367,491,631,769,919,
    31,131,241,373,499,641,773,929,
    37,137,251,379,503,643,787,937,
    41,139,257,383,509,647,797,941,
    43,149,263,389,521,653,809,947,
    47,151,269,397,523,659,811,953,
    53,157,271,401,541,661,821,967,
    59,163,277,409,547,673,823,971,
    61,167,281,419,557,677,827,977,
    67,173,283,421,563,683,829,983,
    71,179,293,431,569,691,839,991,
    73,181,307,433,571,701,853,997
};
int main(){
    int n;
    cin >> n;
    ll ans = 1;
    map<int,int>k;
    for(int i = 1; i<=n; i++)for(auto x:prime){
        int q = i;
        while(q%x==0){
            //show(i);
            //cout << x << endl;
            q/=x;
            k[x]++;
        }
    }
    for(auto x:k){
        ans*=x.second+1;
        ans= ans%1000000007;
    }
    cout << ans << endl;
    
}

Measured memory_bytes: 256