akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

class union_find {
 private:
  vector<int> parent;
  vector<int> rank;
  vector<int> sizes;

 public:
  union_find(int n) : parent(n), rank(n), sizes(n, 1) {
    for (int i = 0; i < n; i++) parent[i] = i;
  }
  void unite(int a, int b) {
    a = find(a);
    b = find(b);
    if (a == b) return;
    if (rank[a] < rank[b]) {
      parent[a] = b;
    } else {
      parent[b] = a;
      if (rank[a] == rank[b]) rank[a]++;
    }
    sizes[find(a)] = sizes[a] + sizes[b];
  }
  int find(int a) { return parent[a] == a ? a : parent[a] = find(parent[a]); }
  int size(int a) { return sizes[find(a)]; }
};

int main() {
  int n, m;
  cin >> n >> m;
  vector<pair<int, int>> a(m);
  for (auto& e : a) {
    cin >> e.first >> e.second;
    e.first--;
    e.second--;
  }
  union_find uf(n);
  vector<ll> r(m);
  r[m - 1] = (ll)n * (n - 1) / 2;
  for (int i = m - 1; i >= 1; i--) {
    r[i - 1] = r[i];
    if (uf.find(a[i].first) != uf.find(a[i].second)) {
      r[i - 1] -= (ll)uf.size(a[i].first) * uf.size(a[i].second);
      uf.unite(a[i].first, a[i].second);
    }
  }
  for (auto e : r) {
    cout << e << endl;
  }
}


Measured memory_bytes: 4096
import sys
from collections import defaultdict, deque

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


def solve():
    H, W = map(int, rl().split())
    S = [rl().rstrip() for _ in range(H)]
    
    roots = []
    searched = [[False] * W for _ in range(H)]
    counter = defaultdict(int)
    for i in range(H):
        for j in range(W):
            if searched[i][j]:
                continue
            roots.append((i, j))
            searched[i][j] = True
            sij = S[i][j]
            counter[(i, j, sij == '.')] += 1
            que = deque([(i, j, sij)])
            while que:
                cy, cx, cc = que.popleft()
                for dy, dx in ((-1, 0), (0, 1), (1, 0), (0, -1)):
                    ny, nx = cy + dy, cx + dx
                    if 0 <= ny < H and 0 <= nx < W:
                        if searched[ny][nx]:
                            continue
                        nc = S[ny][nx]
                        if cc == nc:
                            continue
                        searched[ny][nx] = True
                        counter[(i, j, nc == '.')] += 1
                        que.append((ny, nx, nc))
    
    ans = 0
    for i, j in roots:
        ans += counter[(i, j, 0)] * counter[(i, j, 1)]
    print(ans)


if __name__ == '__main__':
    solve()


Measured memory_bytes: 101980
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush
import itertools
import random
from decimal import *

input = sys.stdin.readline

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
def inputStr(): return input()[:-1]

inf = float('inf')
mod = 1000000007

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-

def main():
	H,W,K = inputMap()
	maps = []
	for i in range(H):
		s = inputStr()
		maps.append(s)

	ans = 0
	for i in range(2**H):
		iBin = bin(i)[2:]
		pl = ""
		for ttt in range(len(iBin), H):
			pl += "0"
		iBin = pl + iBin
		iBin = iBin[::-1]
		for j in range(2**W):
			jBin = bin(j)[2:]
			pl = ""
			for ttt in range(len(jBin), W):
				pl += "0"
			jBin = pl + jBin
			jBin = jBin[::-1]

			kuro = 0
			for iii,mapH in enumerate(maps):
				if iBin[iii] == "1":
					continue
				for jjj,mapW in enumerate(mapH):
					if jBin[jjj] == "1":
						continue
					if mapW == "#":
						kuro += 1
			if kuro == K:
				ans += 1
	print(ans)




#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
if __name__ == "__main__":
	main()


Measured memory_bytes: 79120
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>

#define rep(i,a) for(int i = 0 ; i < a ; i ++)
#define loop(i,a,b) for(int i = a ; i < b ; i ++)
#define vi vector<int>
#define vs vector<string>
#define pii pair<int, int>
#define f first
#define s second
#define pb push_back
using namespace std;

int main(void){
  string a,b;
  cin>>a>>b;
  sort(a.begin(),a.end());
  sort(b.begin(),b.end());
  reverse(b.begin(), b.end());
  cout<<(a<b?"Yes":"No")<<endl;
}

Measured memory_bytes: 256
puts ([[0, 0, 0]] + readlines.drop(1).map{|l| l.split.map(&:to_i)}).each_cons(2).map{|a, b| a.zip(b).map{|x, y| (y - x).abs}}.all?{|t, x, y| g = t - (x + y); g >= 0 && g.even?} ? 'Yes' : 'No'

Measured memory_bytes: 27756
import java.util.Scanner;
public class Main {
	public static void main(String[] args)throws Exception{
		Scanner stdIn=new Scanner(System.in);
		int N=stdIn.nextInt();
		int A[]=new int[N+1];
		long key[]=new long[N+1];
		long ans=0,sum=1,cout=0;
		for(int i=0;i<N+1;i++){
			A[i]=stdIn.nextInt();
		}
		ans=A[N];key[N]=A[N];
		for(int i=N-1;i>=0;i--){
			key[i]=key[i+1]+A[i];
			ans+=key[i];
		}
		for(int i=0;i<N+1;i++){
			if(i!=N&&A[i]+1>sum){
				System.out.println(-1);
				System.exit(0);
			}
			if(i==N&&A[i]>sum){
				System.out.println(-1);
				System.exit(0);
			}
			else
				if(key[i]>sum){
					ans-=key[i]-sum;key[i]=sum;
				}
			sum=(key[i]-A[i])*2;
		}
		System.out.println(ans);
	}
}


Measured memory_bytes: 60796
#include<bits/stdc++.h>
using namespace std;
using Int = long long;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}

//INSERT ABOVE HERE
signed main(){
  Int k,x;
  cin>>k>>x;
  cout<<(k*500>=x?"Yes":"No")<<endl;
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define setbits(x) __builtin_popcount(x)
#define setbitsll(x) __builtin_popcountll(x)
#define endl '\n'
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define se second
#define fi first
#define pai acos(-1)
#define fn(i,x) for(i=0;i<x;i++)
#define fs(i,s,x) for(i=s;i<x;i++)
#define fr(i,x,s) for(i=x;i>=s;i--)
#define fit(itr,s) for(itr=s.begin();itr!=s.end();itr++)
#define W while
#define pp pair<ll,ll>
#define ppi pair<int,int>
#define vl vector<ll>
#define vll vector<pp >
#define vi vector<int>
#define vii vector<ppi>
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))
#define debug(x) cerr<<#x<<" :: "<<x<<endl;
#define debug2(x,y) cerr<<#x<<" :: "<<x<<"\t"<<#y<<" :: "<<y<<endl;
#define debug3(x,y,z) cerr<<#x<<" :: "<<x<<"\t"<<#y<<" :: "<<y<<"\t"<<#z<<" :: "<<z<<endl;
#define debug4(x,y,z,w) cerr<<#x<<" :: "<<x<<"\t"<<#y<<" :: "<<y<<"\t"<<#z<<" :: "<<z<<"\t"<<#w<<" :: "<<w<<endl;
#define boost  ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
const ll MAX=1e16;
const ll MM=1e18;
const ll mod=1e9+7;
int dx[]={-1,0,1,0};
int dy[]={0,1,0,-1};
ll expo(ll x,ll n,ll M=mod)
{
    ll ans=1;
    while(n>0)
    {
        if(n&1){ans=(ans*x)%M;}
                x=(x*x)%M;
                n>>=1;
    }
    return ans;
}


void solve()
{
   string s,t;
   cin>>s>>t;
   for(int i=0;i<26;i++)
   {
       string temp=s;
       temp+=('a'+i);
       if(temp==t)
       {cout<<"Yes"<<endl;return;}
   }
   cout<<"No"<<endl;
}


int main()
{
  boost;
  int t=1;
  //cin>>t;
  while(t--)
  {
      solve();
  }
}


Measured memory_bytes: 3652
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
char s[15];
LL sum[15][15];
int main(){
    scanf("%s", s);
    int n = strlen(s);
    for(int i=0;i<n;i++){
        for(int j=i;j<n;j++){
            if(j-1 < 0) sum[i][j] = (s[j]-'0');
            else sum[i][j] += sum[i][j-1]*10 + (s[j]-'0');
        }
    }
    LL ans = 0;
    for(int i=0;i<(1<<(n-1));i++){
        int last = 0;
        for(int j=0;j<n;j++){
            if((i>>j)&1){
                ans += sum[last][j];
                last = j+1;
            }
        }
        ans += sum[last][n-1];
    }
    printf("%lld\n", ans);
}

Measured memory_bytes: 256
import java.util.*;

public class Main {

	public static void main(String[] args) {
		Scanner in=new Scanner(System.in);
		int a=in.nextInt(),b=in.nextInt(),n=in.nextInt();
		boolean j=true;

		for(int i=0;i<n;i++){
			int s=in.nextInt(),f=in.nextInt();
			if(s<a && f<=a) {
			}
			else if(s>=b && f>b) {
			}
			else {
				j=false;
			}
		}

		if(j)System.out.println(0);
		else System.out.println(1);
	}
}


Measured memory_bytes: 26540
#include <iostream>
#include <iomanip>
#include <vector>
#include <unordered_map>
#include <algorithm>

struct City {
  size_t PrefId;
  size_t Year;

  City(size_t P, size_t Y) : PrefId(P), Year(Y) {}
};

int main() {
  size_t N, M;

  std::cin >> N >> M;

  std::vector<City> Input;
  Input.reserve(M);
  std::vector<std::vector<size_t>>
    Sort(N+1, std::vector<size_t>());

  for (size_t i=0; i<M; i++) {
    size_t P;
    size_t Y;
    std::cin >> P >> Y;
    Input.push_back(City(P, Y));
    Sort[P].push_back(Y);
  }

  std::vector<std::unordered_map<size_t, size_t>> dicts(N+1);
  for (size_t p=1; p<N+1; p++) {
    std::sort(Sort[p].begin(), Sort[p].end());
    size_t num = 1;
    for (auto y : Sort[p]) {
      dicts[p].insert(std::make_pair(y, num));
      num++;
    }
  }

  for (auto c : Input) {
    auto p = c.PrefId;
    auto y = c.Year;
    std::cout << std::setw(6) << std::setfill('0') << p
              << std::setw(6) << std::setfill('0') << dicts[p][y]
              << std::endl;
  }

  return 0;
}


Measured memory_bytes: 20224
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <stdio.h>


using namespace std;


int main() {
    string str;
    cin >> str;
    vector<int> nums(str.size());
    transform(str.begin(), str.end(), nums.begin(), [](char ch) { return ch - '0';});
    const int* result = nums.data();
    const size_t size = nums.size();
    long long int res;

    for ( size_t i = 0; i < size; ++i ) res += result[i];
    if(res % 9 == 0 || res == 0){
        printf("Yes\n");
    } else {
        printf("No\n");
    }
}

Measured memory_bytes: 4444
using System;

namespace ConsoleApp1
{
    class Program
    {
        static void Main(string[] args)
        {
            int t = int.Parse(Console.ReadLine());
            int a = int.Parse(Console.ReadLine());
            int b = int.Parse(Console.ReadLine());
            t -= a;
            Console.WriteLine(t % b);
        }
    }
}

Measured memory_bytes: 11220
/**
    @Author:Monk78
    @Topic:E_Knapsack02
    @Note-constraint is bigger:
**/

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll>Vl;
typedef pair<ll,ll>PII;
typedef vector<PII>Vll;
typedef vector<pair<ll,pair<ll,ll> > >Vlll;
typedef priority_queue<ll>PQL;
typedef map<ll,ll>MP;
#define S second;
#define F first;
#define rep(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end));i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
#define mp make_pair
#define ms(x,y) memset(x,y,sizeof(x))
#define pb push_back
#define mod 1000000009
#define MAX 100005
#define f(i,a,b) for(int i=(a);i<(b);i++)
#define rf(i,a,b) for(int i=(a);i>=b;i--)
#define sl(n) scanf("%lld",&n)
#define pl(n) printf("%lld",n)
#define vpshVar() int main()
const ll INF=1e18L+5;
void min_self(ll &a,ll b){
    a=min(a,b);
}
vpshVar(){
    ll N,W;
    sl(N);sl(W);
    vector<ll>wt(N),value(N);
    for(ll i=0;i<N;i++){
        sl(wt[i]);sl(value[i]);
    }
    ll sum=0;
    for(ll x:value){
        sum=sum+x;
    }
    vector<ll>dp(sum+1,INF);
    dp[0]=0;
    for(ll item=0;item<N;item++){
        for(ll value_al=sum-value[item];value_al>=0;--value_al){
            min_self(dp[value_al+value[item]],dp[value_al]+wt[item]);
        }
    }
    ll ans=0;
    for(ll i=0;i<=sum;i++){
        if(dp[i]<=W)ans=max(ans,(ll)i);
    }
    pl(ans);

return 0;
}


Measured memory_bytes: 1024
import sys
input = sys.stdin.buffer.readline

def main():
    n, c = map(int, input().split())
    D = [list(map(int, input().split())) for _ in range(c)]
    C_ = [list(map(int, input().split())) for _ in range(n)]
    C = [0]*n
    for i, c_ in enumerate(C_):
        c_ = [x-1 for x in c_]
        C[i] = c_

    #print(C)
    L = [[0]*c for _ in range(3)]
    for k in range(c):
        for i in range(n):
            for j in range(n):
                m = (i+j)%3
                x = C[i][j]
                L[m][k] += D[x][k]
                
    X = [[] for _ in range(3)]
    for j in range(3):
        for i, x in enumerate(L[j]):
            X[j].append((x, i))
    for i, x in enumerate(X):
        x.sort()
        x = x[0:3]
        X[i] = x

    #print(X)
    import itertools
    ans = 10**18
    for p in itertools.product(range(3), repeat=3):
        used_col = set()
        temp = 0
        for j in range(3):
            x, i =X[j][p[j]]
            if i in used_col:
                break
            else:
                temp += x
                used_col.add(i)
        else:
            ans = min(temp, ans)
    print(ans)

if __name__ == '__main__':
    main()


Measured memory_bytes: 47416
#include <stdio.h>
#include <math.h>
/*
int sqrt(int a) {
	int i;
	float res = 1;
	for (i = 0; i < 3; i++) {
		res = (res + a / res) / 2;
	}

	return res;
}
*/


int isPrime(int a) {

	int j;

	if (a == 2) {
		return 1;
	}

	if (a < 2 || a % 2 == 0) {
		return 0;
	}



	for (j = 3; j <= sqrt(a); j++) {
		if (a % j == 0) {
			return 0;
		}
	}

	return 1;
}

int main() {

	int num;
	int p_count = 0;
	int n, i;

	scanf("%d", &num);
	
	for (i = 0; i < num; i++) {
		scanf("%d", &n);

		if (isPrime(n)) {
			p_count++;
		}

	}


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

	return 0;
}

Measured memory_bytes: 596
import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long n = sc.nextInt();
        long k = sc.nextInt();
        int mod = 1000000007;
        long ans = 0;

        for(long i=k; i<=n+1;i++) {
            long min = sum(i-1);
            long max = sum(n) - sum(n-i);
            long sa = max - min;
            sa++;
            ans = (ans + sa) % mod;
        }
        ans = ans % mod;
        System.out.println(ans);
    }
    public static long sum(long n) {
        long ans = n*(n+1)/2;
        //累積和
        return ans;
    }
}


Measured memory_bytes: 35776
#include <bits/stdc++.h>
#define rep(i,n) for (ll i = 0; i < (n); ++i)
#define All(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()   //reverse
#define strall(v) (v).cbegin(),(v).cend() //const_itterator
#define IN(a, b, x) (a<=x&&x<b)
using namespace std;
using ll = long long;
using P = pair<int,int>;
using Graph = vector<vector<ll>>;
template<typename T> using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;
template<typename t, typename u, typename Comp=less<>>
bool chmax(t& xmax, const u& x, Comp comp={}) { if(comp(xmax, x)) { xmax = x; return true; } return false;}
template<typename t, typename u, typename Comp=less<>>
bool chmin(t& xmin, const u& x, Comp comp={}) { if(comp(x, xmin)) { xmin = x; return true;} return false;}
const int INF = 1e9;
const ll infl = ll(1e18)+5;
/*
*ios::sync_with_stdio(false);
*cin.tie(0);
*/

int main(){
  int n;
  cin >> n;
  vector<ll> a(n);
  rep(i,n) cin >> a[i];
  ll ans = 0,num=0;
  ll mi = 1LL<<60;
  rep(i,n){
    if(a[i] < 0) num++;
    chmin(mi,abs(a[i]));
    ans+=abs(a[i]);
  }
  if(num%2==0) cout << ans << endl;
  else cout << ans - 2*mi << endl;
}

Measured memory_bytes: 1024
#include<stdio.h>
#define MAX 100000
typedef long long llong;
int n, k;
llong T[MAX];

int check(llong P){
  int i = 0, j;
  for(j = 0; j < k; j++){
    llong s = 0;
    while(s + T[i] <= P){
      s += T[i];
      i++;
      if(i == n) return n;
    }
  }
  return i;
}

int solve(){
  llong left = 0;
  llong right = 100000 * 10000;
  llong mid;
  int v;
  while(right - left > 1){
    mid = (left + right) / 2;
    v = check(mid);
    if(v >= n) right = mid;
    else left = mid;
  }

  return right;
}

int main(){
  int i;
  scanf("%d%d",&n,&k);
  for(i = 0; i < n; i++) scanf("%d",&T[i]);
  llong ans = solve();
  printf("%d\n",ans);

  return 0;
}

Measured memory_bytes: 1376
#include <iostream>
#include <vector>
#include <iomanip>
#include <cstring>
#include <string.h>
#include <iterator>
#include <math.h>
#include <set>
#include <queue>
#include <stack>
#include <algorithm>
#include <tuple>
#include <limits.h>
#include <string>
#include <bitset>
#include <map>
#include <numeric>
#include<unordered_map>


#define endl cout<<"\n"
#define lli long long int
#define ld long double
#define M_PI (3.14159265358979323846264338327950288)
#define MOD (10e9 + 7)

using namespace std;

//fast-exponentiation-lli
unsigned lli expo_fast(lli a, lli b) {
	a = a;
	lli result = 1;
	while (b) {
		//multiplyint(tos(result), a);
		if (b & 1)result = (result * a);
		b >>= 1;
		a = (a*a);
	}
	return (result);
}


void take_in(vector<lli> *arr) {
	for (int i = 0; i < arr->size(); i++)cin >> (*(arr))[i];
}


lli gcd(lli a, lli b)
{
	if (b == 0)
		return a;
	return gcd(b, a % b);

}

/* Iterative Function to calculate (x^y)%p in O(log y) */
unsigned lli power(lli x, unsigned lli y, lli p)
{
	lli res = 1;      // Initialize result 
	x = x % p;  // Update x if it is more than or equal to p 
	while (y > 0) {
		// If y is odd, multiply x with result 
		if (y & 1)res = (res*x) % p;
		// y must be even now 
		y = y >> 1;
		x = (x*x) % p;
	}
	return res;
}


int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	int n; cin >> n;
	vector<vector<lli>> arr(n + 1, vector<lli>(3));
	vector<vector<lli>> dp(n + 1, vector<lli>(3));
	for (int i = 1; i <= n; i++) {
		cin >> arr[i][0] >> arr[i][1] >> arr[i][2];
	}
	dp[1][0] = arr[1][0];
	dp[1][1] = arr[1][1];
	dp[1][2] = arr[1][2];
	for (int i = 2; i <= n; i++) {
		dp[i][0] = arr[i][0] + max(dp[i - 1][1], dp[i - 1][2]);
		dp[i][1] = arr[i][1] + max(dp[i - 1][0], dp[i - 1][2]);
		dp[i][2] = arr[i][2] + max(dp[i - 1][0], dp[i - 1][1]);
	}
	cout << max(dp[n][0], max(dp[n][1], dp[n][2]));
	//system("PAUSE");
}

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

typedef complex<double> P;

int main(){
	int s[3];
	int a1=0,a2=0;
	while( scanf("%d,%d,%d",s,s+1,s+2) != -1 ){
		//sort(s,s+3);
		if( s[0] * s[0] + s[1] * s[1] == s[2] * s[2] ){
			a1++;
		}
		if( s[0] == s[1] )
			a2++;
	}
	cout << a1 << endl;
	cout << a2 << endl;
			
}

Measured memory_bytes: 3112
#include<set>
#include<queue>
#include<cstdio>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#define lc (x<<1)
#define rc (lc|1)
using namespace std;
inline int read(){
	int x=0; bool f=0; char ch=getchar();
	for(;!isdigit(ch);ch=getchar()) f=(ch=='-');
	for(;isdigit(ch);ch=getchar()) x=(x<<3)+(x<<1)+(ch^48);
	return f?-x:x;
}

int n,mod,ans;
inline int add(int a,int b){return a+b>=mod?a+b-mod:a+b;}

bool v[505][505];
int l[505],r[505],id;
struct node{int x,y,id;}nd[505];
inline bool jud(node a,node b){
	if(a.x==b.x&&a.y==b.y) return a.id>b.id;
	if(a.x==b.x) return a.y<b.y;
	return a.x<b.x;
}

int g[505],f[505][505];
int main(){
	n=read(); mod=read(); memset(l,0x3f,sizeof(l));
	for(int i=0;i<2*n;++i) for(int j=0;j<2*n;++j){
		v[i][j]=(n*n<=i*i+j*j)&&(i*i+j*j<=4*n*n);
		if(v[i][j]) l[i]=min(l[i],j),r[i]=j;
	}
	for(int i=0;i<n;++i) nd[++id].x=l[i]-1,nd[id].y=r[i],nd[id].id=i;
	for(int i=n;i<2*n;++i) nd[++id].x=r[i],nd[id].y=-1,nd[id].id=i;
	sort(nd+1,nd+1+2*n,jud);
	for(int i=1;i<=id;++i) g[i]=g[i-1]+(nd[i].y>=0);
	for(int tot=0;tot<=n;++tot){
		memset(f,0,sizeof(f)); f[0][0]=1;
		for(int i=0;i<id;++i) for(int j=0;j<=tot&&j<=i;++j){
			if(nd[i+1].y==-1) f[i+1][j]=add(f[i+1][j],1ll*f[i][j]*max(0,nd[i+1].x-(i-(g[i]-j))+1)%mod);
			else f[i+1][j]=add(f[i+1][j],1ll*f[i][j]*max(0,nd[i+1].y-(2*n-1-nd[i+1].id)-tot+j+1)%mod),
				f[i+1][j+1]=add(f[i+1][j+1],1ll*f[i][j]*max(0,nd[i+1].x-(i-(g[i]-j))+1)%mod);
		}
		ans=(ans+(tot&1?mod-1ll:1ll)*f[id][tot])%mod;
	}
	printf("%d\n",ans);
	return 0;
}

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

int main() {
    int x, n;
    vector<int> d(102);
    P ans(99999, -1);
    cin >> x >> n;
    for (int i = 0; i < n; i++)
    {
        int p;
        cin >> p;
        d[p] = 1;
    }

    for (int i = 0; i <= 101; i++)
    {
        if (d[i] == 1) continue;
        int dif = abs(x - i);
        ans = min(ans, P(dif, i));
    }
    cout << ans.second << endl;
    return 0;
}

Measured memory_bytes: 3572
//21
//write force 33min
//sample 3min bug3 bug1
//write std 15min
//check 4min
//sample 4min bug1
#include<cstdio>
#include<algorithm>
using namespace std;

const int maxn = 100002;
const int lbt = 1e9 + 7;

struct node {
	int l, r;
	node *ls, *rs;
	int d;
};

node* create(int l, int r);
node* build(int l, int r);
void change(node *p, int x, int d);
int query(node *p, int l, int r);

int N, m;
int x[maxn], y[maxn];
int n;
int l[maxn], r[maxn];
int uni[maxn];
int ord[maxn];
int tr[maxn];
int d[maxn];

bool cmp(int i, int j) {
	if (l[i] != l[j]) return l[i] < l[j];
	return r[i] < r[j];
}

int main() {
	scanf("%d%d", &N, &m);
	for (int i = 1; i <= N; i++) {
		scanf("%d", &x[i]);
	}
	for (int i = 1; i <= m; i++) {
		scanf("%d", &y[i]);
	}
	for (int i = 1; i <= N; i++) {
		int pos = upper_bound(y + 1, y + 1 + m, x[i]) - y - 1;
		if (pos == 0 || pos == m) continue;
		n++;
		l[n] = y[pos] - x[i];
		pos++;
		r[n] = y[pos] - x[i];
	}
	for (int i = 1; i <= n; i++) {
		uni[i] = r[i];
	}
	sort(uni + 1, uni + 1 + n);
	m = unique(uni + 1, uni + 1 + n) - uni - 1;
	for (int i = 1; i <= n; i++) {
		r[i] = lower_bound(uni + 1, uni + 1 + m, r[i]) - uni - 1;
	}
	for (int i = 1; i <= n; i++) {
		ord[i] = i;
	}
	sort(ord + 1, ord + 1 + n, cmp);
	node *rt = build(0, m);
	change(rt, m, 1);
	for (int _ = 1; _ <= n; _++) {
		int k = 0;
		int __ = _;
		for (; __ <= n && l[ord[__]] == l[ord[_]]; __++) {
			tr[++k] = r[ord[__]];
		}
		_ = __ - 1;
		k = unique(tr + 1, tr + 1 + k) - tr - 1;
		tr[0] = -1;
		tr[k + 1] = m;
		for (int p = 1; p <= k; p++) {
			d[p] = query(rt, tr[p] + 1, m);
		}
		for (int p = 1; p <= k; p++) {
			change(rt, tr[p], d[p]);
		}
	}
	int ans = query(rt, 0, m);
	printf("%d", ans);
	return 0;
}

node* create(int l, int r) {
	static node pool[2 * maxn];
	static node *p = pool;
	p->l = l;
	p->r = r;
	p->ls = p->rs = NULL;
	p->d = 0;
	return p++;
}

node* build(int l, int r) {
	node *p = create(l, r);
	if (l == r) return p;
	int mid = (l + r) / 2;
	p->ls = build(l, mid);
	p->rs = build(mid + 1, r);
	return p;
}

void change(node *p, int x, int d) {
	if (p->l == p->r) {
		p->d = (p->d + d) % lbt;
		return;
	}
	if (p->ls->r >= x) change(p->ls, x, d);
	else change(p->rs, x, d);
	p->d = (p->ls->d + p->rs->d) % lbt;
}

int query(node *p, int l, int r) {
	if (p->l == l && p->r == r) return p->d;
	if (p->ls->r >= r) return query(p->ls, l, r);
	else if (p->rs->l <= l) return query(p->rs, l, r);
	else return (query(p->ls, l, p->ls->r) + query(p->rs, p->rs->l, r)) % lbt;
}

Measured memory_bytes: 9216
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
using namespace std;
typedef long long ll;
const int mod=1e9+7;
const int MAXN=2e5+5;
int maze[1450][1450];
int dp[1450][1450];
int main()
{
    int h,w;
    cin>>h>>w;
    for(int i=1;i<=h;i++)
    {
        for(int j=1;j<=w;j++)
        {
            cin>>maze[i][j];
        }
    }
    int ans=0;
    for(int i=1;i<=h;i++)
    {
        for(int j=1;j<=w;j++)
        {
            dp[i][j]=(maze[i][j]+1)%2;
            ans=ans|dp[i][j];
        }
    }
    for(int i=2;i<=h;i++)
    {
        for(int j=2;j<=w;j++)
        {
            if(maze[i][j]==1)
            {
                dp[i][j]=0;
            }
            else
            {
                dp[i][j]=min(dp[i-1][j-1],min(dp[i-1][j],dp[i][j-1]))+1;
                ans=max(ans,dp[i][j]);
            }
        }
    }
    cout<<ans*ans<<endl;
}


Measured memory_bytes: 18884
object Main extends App {
  val sc = new java.util.Scanner(System.in)
  val a, b = sc.next()
  println(a match {
    case "H" if b == "H" => "H"
    case "H" => "D"
    case "D" if b == "D" => "H"
    case _ => "D"
  })
}


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

// Order statistics tree (if supported by judge!):
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;

// template<class TK, class TM> using order_tree = tree<TK, TM, less<TK>, rb_tree_tag, tree_order_statistics_node_update>;
// iterator	find_by_order(int r) (zero based)
// int		order_of_key(TK v)
// template<class TV> using order_set = order_tree<TV, null_type>;

#define x first
#define y second
#define rs resize
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define rep(i,a,b) for(auto i=(a);i!=(b); ++i)
#define REP(i,n) rep(i,0,n)
#define all(v) (v).begin(), (v).end()

typedef long long ll;
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<ii> vii;

template<class T> int sz(const vector<T> &v) { return (int) v.size(); }

template<class T> ostream& operator<<(ostream &os, vector<T> v) {
	os << "\n[";
	for(T &x : v) os << x << ',';
	return os << "]\n";
}

// lambda-expression: [] (args) -> retType { body }

map<ii, int> lookup;

int n;
vi E[100];

ll find_path(int fr, int to) {
	vl mask(n, 0);

	vector<bool> vis(n, false);
	queue<int> q;
	q.push(fr);
	vis[fr] = true;
	while (!q.empty()) {
		int cur = q.front();
		q.pop();
		for (int nxt : E[cur]) {
			if (vis[nxt]) continue;
			vis[nxt] = true;
			mask[nxt] = mask[cur] | ( 1LL << lookup[{cur,nxt}] );
			q.push(nxt);
		}
	}
	assert(mask[to] != 0);
	return mask[to];
}

ll M[1<<20] = {};
int sgn[1<<20] = {};

void run() {
	cin >> n;
	REP(i, n-1) {
		int a, b;
		cin >> a >> b;
		a--; b--;
		E[a].pb(b);
		E[b].pb(a);

		lookup[{a,b}] = lookup[{b,a}] = i;
	}

	int m;
	cin >> m;
	vi u(m), v(m);
	vl path(m);
	REP(i, m) {
		cin >> u[i] >> v[i];
		u[i]--; v[i]--;

		path[i] = find_path(u[i], v[i]);
	}

	M[0] = 0LL;
	int pm = 1<<m;

	int N = n;
	ll ans = 1LL << (N-1);

	sgn[0] = 1;

	for (int i=1; i < pm; i++) {
		int j = 31 - __builtin_clz(i & -i);
		assert((i & -i) == (1<<j));

		M[i] = M[i & ~(1<<j)] | path[j];
		sgn[i] = -sgn[i & ~(1<<j)];

		int sz = __builtin_popcountll(M[i]);
		// int nrMs = __builtin_popcount(i);

		// assert((nrMs % 2 == 0) == (sgn[i] == 1));

		/* if (nrMs&1)
			ans -= 1LL<<(N-1-sz);
		else
			ans += 1LL<<(N-1-sz); */
		ans += (1LL << (N-1-sz)) * sgn[i];
	}

	cout << ans << endl;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cerr << boolalpha;
	(cout << fixed).precision(10);

	run();

	return 0;
}


Measured memory_bytes: 12544
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdlib>
#include <string>
using namespace std;
using ll = long long;

#define reps(i,s,n) for(int (i) = (s) ; (i) < (n); ++(i))
#define rep(i,n) reps(i,0,n)

string s1,s2,s3;
string s4;

int main(){
    cin >> s1 >> s2 >> s3;
    
    s4 = (s1[0]);
    s4 += (s2[0]);
    s4 += (s3[0]);
    std::transform(s4.cbegin(),s4.cend(),s4.begin(),::toupper);
    cout << s4 << endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i=0;i<(n);++i)
#define fi first
#define se second
#define INF 1000000009
#define lINF 1000000000000000009
typedef long long ll;

int main(){
  int n;
  string s;
  cin>>n>>s;
  if(n%2==1){
    cout<<"No"<<endl;
    return(0);
  }
  string a=s.substr(0,n/2);
  string b=s.substr(n/2);
  cout<<(a==b?"Yes":"No")<<endl;
  return(0);
}


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

int main() {
  int N;
  cin >> N;
  map<string, int> S;
  int m = 0;
  for (int i = 0; i < N; i++) {
    string s;
    cin >> s;
    if (!S[s])
      S[s] = 1;
    else
      S[s]++;
    m = max(m, S[s]);
  }

  for (auto p : S) {
    if (p.second == m) cout << p.first << endl;
  }
  return 0;
}

Measured memory_bytes: 25216
#define _CRT_NONSTDC_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <array>
#include <algorithm>
#include <list>
#include <iomanip>
#include <queue>
#include <functional>
#include <cassert>
#include <cmath>
#include <set>
#include <map>
#include <numeric>

#define NL << endl
#define REP(i,n) for(int (i) = 0; i < (n); ++(i))
#define Yes cout << "Yes" NL
#define No cout << "No" NL

using namespace std;
using ll = long long;
using ull = unsigned long long;
constexpr int INTMAX = numeric_limits<int>::max();
constexpr int INTMIN = numeric_limits<int>::min();
constexpr ll LLMAX = numeric_limits<long long>::max();
constexpr ll LLMIN = numeric_limits<long long>::min();
constexpr int MOD = 1000000007;


int gcd(int a, int b) { return b ? gcd(b, a%b) : a; }
ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }

using namespace std;


signed main() {
	int ans = 0;
	double min = INTMAX;
	int n;
	cin >> n;
	double t, a;
	cin >> t >> a;

	for (int i = 0; i < n; i++) {
		int x;
		cin >> x;
		double tt = t - x * 0.006;
		if (min > abs(a - tt)) {
			min = abs(a - tt);
			ans = i;
		}
	}

	cout << ans + 1 NL;

	return 0;

}



Measured memory_bytes: 256
// ※※※ 解答不能 ※※※
// 正解者のソースを学習する(一部改変).
// hbi1998氏
// https://atcoder.jp/contests/agc038/submissions/7642316
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int N = 440;
const int mod = 998244353;

int dp[2][N][N];
int g[N], r[N], a[N], b[N], p[N];

int main(){
    for(int i = 0; i < N; i++){
        r[i] = i < 2 ? i : (LL)r[mod % i] * (mod - mod / i) % mod;
        g[i] = i == 0 ? 1 : (LL)g[i - 1] * r[i] % mod;
    }
    int n;
    scanf("%d", &n);
    for(int i = 0; i < n; i++) scanf("%d %d", &a[i], &b[i]);
    int S = accumulate(a, a + n, 0);
    for(int i = 0; i < n; i++) p[i] = (LL)r[S] * a[i] % mod;
    int now = 0;
    dp[0][0][0] = mod - 1;
    int asum = 0, bsum = 0;
    auto add = [&](int &a, int b){ ((a += b) >= mod) && (a -= mod); };
    for(int i = 0; i < n; i++){
        now ^= 1;
        memcpy(dp[now], dp[!now], sizeof dp[now]);
        for(int j = 0; j <= asum; j++){
            for(int k = 0; k <= bsum; k++){
                if(dp[!now][j][k]){
                    for(int l = 0, cur = mod - 1; l < b[i]; l++){
                        add(dp[now][j + a[i]][k + l], (LL)dp[!now][j][k] * g[l] % mod * cur % mod);
                        cur = (LL)cur * p[i] % mod;
                    }
                }
            }
        }
        asum += a[i];
        bsum += b[i] - 1;
    }
    int ans = 0;
    for(int i = 1; i <= S; i++){
        int cur = (LL)S * r[i] % mod;
        int ret = 1;
        for(int j = 0; j <= bsum; j++){
            ret = (LL)ret * cur % mod;
            add(ans, (LL)ret * dp[now][i][j] % mod);
            ret = (LL)ret * (j + 1) % mod;
        }
    }
    printf("%d\n", ans);
    return 0;
}

Measured memory_bytes: 1792
hn=input().split(" ")
H=int(hn[0])
N=int(hn[1])
A=input().split(" ")
A=[int(s) for s in A]
#print(A)
total=0
for i in range(N):
  total+=A[i]
if H<=total:
  print("Yes")
else:
  print("No")

Measured memory_bytes: 14016
//AtCoder ABC097 B - Exponential
#include <bits/stdc++.h>
using namespace std;
using ll=int64_t;

ll pw(ll a,ll b){
    ll ret=1;
    for(ll i=0;i<b;++i){
        ret*=a;
    }
    return ret;
}

int main() {
#if LOCAL&0
    std::ifstream in("input.txt");
    std::cin.rdbuf(in.rdbuf());
#endif
    ll X; cin>>X;
    ll ans=1;
    for(ll i=2;i<=sqrt(X);++i){
        ll tmp=X;
        ll cnt=0;
        while(tmp>=i){
            ++cnt;
            tmp/=i;
        }
        ans=max(pw(i,cnt),ans);
    }
    cout<<ans<<endl;    
    return 0;
}

Measured memory_bytes: 256
parseInt(x) = parse(Int, x)
parseBigInt(x) = parse(BigInt, x)
parseFloat(x) = parse(Float64, x)
parseBigFloat(x) = parse(BigFloat, x)
parseMap(x::Array{SubString{String},1}) = map(parseInt, x)

function main()
    a,b,c,k=parseMap(split(readline()))
    if k<=a
        println(k)
    elseif k<=a+b
        println(a)
    else
        println(a-(k-a-b))
    end
end
main()

Measured memory_bytes: 162896
use proconio::input;

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

    let mut ans = None;
    for i in 1..=n {
        if 108 * i / 100 == n {
            ans = Some(i);
            break;
        }
    }

    if let Some(x) = ans {
        println!("{}", x);
    } else {
        println!(":(");
    }
}


Measured memory_bytes: 2100
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<iomanip>
#include<set>
#include<queue>

using namespace std;
long long gcd(long long a, long long b) { return b ? gcd(b, a%b) : a; }
int main()
{
	long long a,b;
	cin >> a >> b;
	cout << a*b/gcd(a,b) << endl;




}


Measured memory_bytes: 256
import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int max = 0;
        int nGood = 0;
        while (N > 0) {
            int h = sc.nextInt();
            if (h >= max) {
                nGood += 1;
                max = h;
            }
            N -= 1;
        }

        System.out.println(nGood);
    }

}


Measured memory_bytes: 25172
/*
                                Bismillahi-r-Rahmani-r-Rahim
                                        RhIeyAaD
                                    IIT-7th Batch,JU
*/
#include<bits/stdc++.h>
using namespace std;

#define ll              long long int
#define MAX             2134567891
#define fr(i,n)         for(i=0;i<n;i++)
#define rep(i,n)        for(i=1;i<=n;i++)
#define rev(i,a,n)      for(i=n;i>=a;i--)
#define FOR(i,a,n)      for(i=a;i<=n;i++)
#define ALL(n)          n.begin(),n.end()
#define mem(x,n)        memset(x,n,sizeof(x))
#define TC(t)           printf("Case %lld: ",t)
#define ans(t,c)        printf("Case %lld: %lld\n",t,c)
#define SETP(n)         cout<<setprecision(n)<<fixed
#define READ            freopen("F:\\Project\\Test_Case.txt","r",stdin)
#define WRITE           freopen("F:\\Project\\Output_Test.txt","w",stdout)
#define IO              ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);
#define PAIR            pair<ll,ll>
#define MP              make_pair
#define pb(a)           push_back(a)
#define ff              first
#define ss              second
#define NL              print("\n");
#define debug(a)        cout<<a<<" ";
#define hlw             printf("hlw\n");
#define NN              111
#define MOD             1000000007///10^9
#define N               1000007 ///10^6->6 zero after 1 **

ll x[N],y[N],z[N],n;
string s,S;
vector<ll>v,old;
//map <ll,ll> mp;

int main()
{
    //IO;
    //while(1)
    //READ;WRITE;
{
    ll a=0,b=0,c=0,d,e,f,g,i,j,k,l,m,p,q,r,u,w,t,tc,in,mod,loc,diff,val,sz,lo,hi,mid,mn=MAX,mx=0,sum=0,ans=0;
    cin>>k;
    rep(i,9)v.pb(i);
    while(1)
    {
        //cout<<v.size()<<endl;
        if(k<=v.size())
        {
            cout<<v[k-1]<<endl;
            return 0;
        }
        k-=v.size();
        old.clear();
        swap(v,old);
        fr(j,old.size())
        {
            a=old[j];
            for(i=-1;i<=1;i++)
            {
                m=a%10+i;
                if(m>=0 && m<=9)
                {
                    v.pb(a*10+m);
                }
            }
        }
    }
}
    return 0;
}

/*

*/
/// Check for constraint 0 or 1?
/// long long or double? sqrt or division will work fine??


Measured memory_bytes: 1884
m,d = gets.split.map(&:to_i)
if d < 22
  puts 0
  exit
end
count = 0
(1..m).each do |month|
  (22..d).each do |i|
    d10,d1 = i.to_s.split("").map(&:to_i)
    next if d10 < 2 || d1 < 2
    count += 1 if d10 * d1 == month
  end
end
puts count


Measured memory_bytes: 14316
# -*- coding: utf-8 -*-
"""
Created on Sun Jul  8 10:56:33 2018

@author: maezawa
"""
n = int(input())
adj = [[] for _ in range(n)]
d = [0 for _ in range(n)]
f = [0 for _ in range(n)]

for j in range(n):
    ain = list(map(int, input().split()))
    u = ain[0]
    k = ain[1]
    for i in range(k):
        adj[u-1].append(ain[i+2]-1)
    adj[u-1].sort()
    #print(*adj[u-1])

t = 1

for j in range(n):
    if d[j] == 0:
        stack = [j]

    while stack:
        #print(stack)
        current = stack[-1]
        if d[current] == 0:
            d[current] = t
            t += 1
        flag = 0
        for k in adj[current]:
            if d[k] == 0:
                stack.append(k)
                flag = 1
                break
        if flag == 0:
            f[current] = t
            t += 1
            stack.pop()

    #print('current = {}, t = {}'.format(current, t))
    #print('stack', *stack)

for i in range(n):
    print('{} {} {}'.format(i+1, d[i], f[i]))



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

#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds; 

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int getRand(int l, int r)
{
    uniform_int_distribution<int> uid(l, r);
    return uid(rng);
}
  
#define int long long 
#define pb push_back
#define S second
#define F first
#define f(i,n) for(int i=0;i<n;i++)
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define vi vector<int>
#define pii pair<int,int>
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> 
#define precise(x) fixed << setprecision(x) 

const int MOD = 1e9+7;

int mod_pow(int a,int b,int M = MOD)
{
    int res = 1;
    
    while(b)
    {
        if(b&1) res=(res*a)%M;
        a=(a*a)%M;
        b>>=1;
    }
    
    return res;
}


void solve()
{
   int n;
    cin >> n;
    
   cout << ((1000 - (n%1000))%1000); 
    
    
}

signed main()
{
    fast;
    
    int t = 1;
    
//    cin >> t;
    
    while(t--)
        
    solve();
}

Measured memory_bytes: 3612
def q1():
    K = int(input())
    A, B = (int(i) for i in input().split())

    ans = 'NG'
    for i in range(A, B+1):
        if i % K == 0:
            ans = 'OK'
            break

    print(ans)


if __name__ == '__main__':
    q1()


Measured memory_bytes: 9168
#include<stdio.h>
int main(void)
{
    char s[101];
    int i=0,a=0;
    scanf("%s",s);
    while(s[i]!='\0'){
        if((i%2==0)&&(s[i]!='L'))
            a++;
        else if((i%2==1)&&(s[i]!='R'))
            a++;
        i++;
    }
    if(i==a)
        printf("Yes\n");
    else
        printf("No\n");
    return 0;
}

Measured memory_bytes: 128
use proconio::*;
use proconio::marker::*;
use std::cmp::*;

pub trait MoOperator {
    type Value;
    type Query;
    type Answer;
    fn init(&mut self);
    fn insert(&mut self, v: &Self::Value);
    fn delete(&mut self, v: &Self::Value);
    fn answer(&mut self, q: Self::Query) -> Self::Answer;
    fn solve(
        &mut self,
        array: &[Self::Value],
        mut query: Vec<(usize, usize, Self::Query)>,
        answer: &mut [Self::Answer],
    ) {
        let state = self;
        let size = array.len();
        assert!(query.len() <= answer.len());
        assert!(query.iter().all(|p| p.0 < p.1 && p.1 <= size));
        if query.is_empty() {
            return;
        }
        let batch = (size as f64 / (query.len() as f64).sqrt()).ceil() as usize;
        let mut q = vec![];
        std::mem::swap(&mut q, &mut query);
        let mut query = (0..(size / batch + 1)).map(|_| vec![]).collect::<Vec<_>>();
        for (i, (l, r, op)) in q.into_iter().enumerate() {
            query[l / batch].push((r, l, i, op));
        }
        state.init();
        let mut x = 0;
        let mut y = 0;
        for (i, mut query) in query.into_iter().enumerate() {
            query.sort_unstable_by_key(|p| p.0);
            if i & 1 == 1 {
                query.reverse();
            }
            for (r, l, k, op) in query.into_iter() {
                for v in array[min(x, l)..x].iter().rev() {
                    state.insert(v);
                }
                for v in array[min(y, r)..r].iter() {
                    state.insert(v);
                }
                for v in array[min(x, l)..l].iter() {
                    state.delete(v);
                }
                for v in array[min(y, r)..y].iter().rev() {
                    state.delete(v);
                }
                x = l;
                y = r;
                answer[k] = state.answer(op);
            }
        }
    }
}

struct State {
    cnt: Vec<u32>,
    ans: usize,
}

impl MoOperator for State {
    type Value = usize;
    type Query = ();
    type Answer = usize;
    fn init(&mut self) {
        for c in self.cnt.iter_mut() {
            *c = 0;
        }
        self.ans = 0;
    }
    fn insert(&mut self, x: &Self::Value) {
        let c = &mut self.cnt[*x];
        if *c == 0 {
            self.ans += 1;
        }
        *c += 1;
    }
    fn delete(&mut self, x: &Self::Value) {
        let c = &mut self.cnt[*x];
        if *c == 1 {
            self.ans -= 1;
        }
        *c -= 1;
    }
    fn answer(&mut self, _q: Self::Query) -> usize {
        self.ans
    }
}

#[fastout]
fn run() {
    input! {
        n: usize,
        q: usize,
        c: [Usize1; n],
        ask: [(Usize1, usize); q],
    }
    let ask: Vec<_> = ask.into_iter().map(|(l, r)| (l, r, ())).collect();
    let mut ans = vec![0; q];
    State {
        cnt: vec![0; n],
        ans: 0,
    }.solve(&c, ask, &mut ans);
    for a in ans {
        println!("{}", a);
    }
}

fn main() {
    run();
}


Measured memory_bytes: 41696
// setprecision example

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(false);
#define FO cout.tie(NULL);
#define FI cin.tie(NULL);
#define IN cin>>
#define OUT cout<<
#define loop(i,a,n) for(int i=a; i<n; i++)
#define rloop(i,a,n) for(int i=a; i>=n; i--)
#define endl "\n";
#define pb push_back
#define mp make_pair
#define set_bits(a) __builtin_popcountll(a)
#define ll long long int
#define ld long double
#define vll vector<long long int>
#define pll pair<long long int, long long int>
#define mod 1000000007
#define M 998244353
ll gcd(ll a, ll b)
{
    return (b?gcd(b,a%b):a);
}
ll P(ll B, ll power, ll modulo)
{
    ll ans=1LL;
    while(power>0LL)
    {
        if(power%2LL==1LL)
        {
            ans=(ans*B)%modulo;
        }
        B=(B*B)%modulo;
        power/=2LL;
    }
    return ans;
}
bool isPrime(ll n)
{
    if(n<=1LL)
    {
        return false;
    }
    if(n<=3LL)
    {
        return true;
    }
    if(n%2==0LL || n%3==0LL)
    {
        return false;
    }
    for(ll i=5LL; (i*i)<=n; i+=6LL)
    {
        if(n%i==0LL || n%(i+2LL)==0LL)
        {
            return false;
        }
    }
    return true;
}
using namespace std;
bool sortbysec(const pair<pair<int,int>,int> &a, const pair<pair<int,int>,int> &b)
{
    return (a.first.second<b.first.second);
}
bool sortbysecll(const pll &a, const pll &b)
{
    return (a.second<b.second);
}
ll modinv(ll x, ll y, ll modulo)
{
    return ((x%modulo)*(P(y,modulo-2LL,modulo)%modulo))%modulo;
}
void het()
{
    FAST
    FO
    FI
//    #ifndef ONLINE_JUDGE
//        freopen("input.txt","r",stdin);
//        freopen("output.txt","w",stdout);
//    #endif
}
int main()
{
    het();
       int t;
    cin>>t;
    double f =6.28318530717958623200;

    cout << std::setprecision(26) << f*t << '\n';
    return 0;
}



Measured memory_bytes: 3796
main = do
    n <- readLn :: IO Int
    s <- getLine
    putStrLn $ solve s n

solve :: String -> Int -> String
solve s n = map sub s
    where
        sub x = do
            if (fromEnum x) + n > fromEnum 'Z'
                then toEnum ((fromEnum x) + n - (fromEnum 'Z') + (fromEnum 'A') - 1)
                else toEnum ((fromEnum x) + n)


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

class Program
{
    static string InputPattern = "InputX";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("4 5 3");
            WillReturn.Add("8");
            WillReturn.Add("7");
            WillReturn.Add("4");
            WillReturn.Add("2");
            //2
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("2 10 4");
            WillReturn.Add("20");
            WillReturn.Add("20");
            //4
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("5 2 1");
            WillReturn.Add("900000000");
            WillReturn.Add("900000000");
            WillReturn.Add("1000000000");
            WillReturn.Add("1000000000");
            WillReturn.Add("1000000000");
            //800000000
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static long mA;
    static long mB;
    static long[] mHArr;

    static void Main()
    {
        checked {

            List<string> InputList = GetInputList();
            long[] wkArr = InputList[0].Split(' ').Select(X => long.Parse(X)).ToArray();

            mA = wkArr[1];
            mB = wkArr[2];

            mHArr = InputList.Skip(1).Select(X => long.Parse(X)).ToArray();
            //降順にソートしておく
            Array.Sort(mHArr, (A, B) => B.CompareTo(A));

            Console.WriteLine(ExecNibunHou());
        }
    }

    //2分法で何回の爆発が必要かを調べる
    static long ExecNibunHou()
    {
        checked {
            long L = 0;
            long R = mHArr.Sum(X => X / mA + 1);

            while (L + 1 < R) {
                long Mid = (L + R) / 2;

                bool IsOK = DeriveIsOK(Mid);
                if (IsOK) R = Mid;
                else L = Mid;
            }
            return R;
        }
    }

    //K回の爆発でOKかを返す
    static bool DeriveIsOK(long pK)
    {
        checked {

            //爆発回数
            long BakuhatuCnt = 0;

            //余波の合計
            long YohaSum = pK * mB;

            foreach (long EachH in mHArr) {
                long RestH = EachH - YohaSum;
                if (RestH <= 0) continue;

                long wkDiff = mA - mB;
                long CurrBakuhatuCnt = RestH / wkDiff;
                if (EachH % wkDiff > 0) CurrBakuhatuCnt++;

                BakuhatuCnt += CurrBakuhatuCnt;
                if (BakuhatuCnt > pK) return false;
            }
            return true;
        }
    }
}


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


int main() {
  int N;
  cin >> N;
  string Iro;
  cin >> Iro;
  int Ans = 0;
  int Red = 0;
  
  for(int i=0; i<N; i++){
    if(Iro.at(i)=='R'){
      Red++;
    }
  }
  
  if(Red != 0){
    Red--;
      for(int i=0; i<=Red; i++){
      if(Iro.at(i)=='W'){
        Ans++;
      }
    }
  }
    cout << Ans;
  
}

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


count = 0
R = set(range(N))
A = set()
for i in R:
    B = set()
    A.add(i)
    B = A.union(B)
    for j in R - A:
        B.add(j)
        if K[i] != K[j]:
            for k in R - B:
                if (K[i] != K[k]) and (K[j] != K[k]) and ((K[i]+K[j]) > K[k]) and ((K[j]+K[k]) > K[i]) and ((K[k]+K[i]) > K[j]):
                    count += 1

print(count)

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

int main() {
  string s;
  int count=0;
  cin>>s;
  
  for (int i;i<s.size()/2;i++) {
    if (s[i]==s[s.size()-1-i]) {
      continue;
    }
    else {
      count+=1;
    }
  }
  cout<<count<<endl;
}
      
      
      

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>

#define rep(i, n) for (int i = 0; i < (n); ++i)

using std::cin;
using std::cout;
using std::endl;
using std::string;
using std::vector;

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

  D = 2 * D + 1;
  cout << (N + (D - 1)) / D << endl;

  return 0;
}


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

using namespace std;

int main() {
	int n, s[200] = {}, result = 0,lamp=1,in,ax;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> s[i];
	}
	ax= s[1];
	in= s[1];
	for (int i = 2; i <= n; i++) {
		ax = max(ax, s[i]);
		in = min(in, s[i]);
	}
	cout << ax-in;
}

Measured memory_bytes: 256