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

# define REP(i,n) for (int i=0;i<(n);++i)
# define rep(i,a,b) for(int i=a;i<(b);++i)
# define p(s) std::cout << s ;
# define pl(s)  std::cout << s << endl;
# define printIf(j,s1,s2) cout << (j ? s1 : s2) << endl;
# define YES(j) cout << (j ? "YES" : "NO") << endl;
# define Yes(j) std::cout << (j ? "Yes" : "No") << endl;
# define yes(j) std::cout << (j ? "yes" : "no") << endl;
# define all(v) v.begin(),v.end()
# define showVector(v) REP(i,v.size()){p(v[i]);p(" ")} pl("")
template<class T> inline bool chmin(T &a, T b){ if(a > b) { a = b; return true;} return false;}
template<class T> inline bool chmax(T &a, T b){ if(a < b) { a = b; return true;} return false;}
typedef long long int ll;
typedef pair<ll,ll> pll;
typedef pair<double,double> P_dd;

template<class T>
vector<T> make_vec(size_t a){
    return vector<T>(a);
}

template<class T, class... Ts>
auto make_vec(size_t a, Ts... ts){
  return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}

template<typename T,typename V>
typename enable_if<is_class<T>::value==0>::type
fill_v(T &t,const V &v){t=v;}

template<typename T,typename V>
typename enable_if<is_class<T>::value!=0>::type
fill_v(T &t,const V &v){
  for(auto &e:t) fill_v(e,v);
}


const int MOD = 1000000007;
const int inf=1e9+7;
const ll longinf=1LL<<60 ;

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

void mulM(long long &a, long long b) {
    a = ((a%MOD)*(b%MOD))%MOD ;
}

// a^b mod M
long myPow(long a,long b,int M) {
    long ret = 1;
    long tmp = a;
    while(b>0) {
        if((b&1)==1) ret = (ret * tmp) % M;
        tmp = (tmp * tmp) % M;
        b = b>>1;
    }
    return ret;
}

 // nCk mod M
int nCk(int n,int k,int M) {
    long ret = 1;
    int mi = min(k, n-k);
    for(int i=1;i<=mi;i++) {
        ret = (ret * myPow(i,M-2,M)) % M;
    }
    for(int i=n-mi+1;i<=n;i++) {
        ret = (ret * i) % M;
    }
    return (int)ret;
};

vector<pair<long long, long long> > prime_factorize(long long n) {
    vector<pair<long long, long long> > res;
    for (long long p = 2; p * p <= n; ++p) {
        if (n % p != 0) continue;
        int num = 0;
        while (n % p == 0) { ++num; n /= p; }
        res.push_back(make_pair(p, num));
    }
    if (n != 1) res.push_back(make_pair(n, 1));
    return res;
}

int main() {
    long double W,H,x,y;
    cin >> W >> H >> x >> y;

    long double cx = W/2;
    long double cy = H/2;

    int ans;
    if(cx == x && cy == y) ans = 1;
    else ans = 0;

    printf("%.12Lf %d\n",W*H/2,ans);

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <bitset>
#include <math.h>
#include <iomanip>
#include <queue>
#define inp(X) cin >> X
#define out(X) cout << X << endl
#define out16(X) cout << setprecision(16) << X << endl
#define rep(i,n) for(int i=0;i<n;i++ )
#define rep2(i,f,n) for(int i=f;i<n;i++ )
#define MAX(A) *max_element(A.begin(),A.end())
#define MIN(A) *min_element(A.begin(),A.end())
#define SORT(A) sort(A.begin(),A.end())
#define REV(A) reverse(A.begin(),A.end())
typedef long long int ll;
using vi = std::vector<int>;
using vvi = std::vector<std::vector<int>>;
using vd = std::vector<double>;
using vvd = std::vector<std::vector<double>>;
using vll = std::vector<ll>;
using vvll = std::vector<std::vector<ll>>;
using namespace std;
#define MOD 1000000007
#define INF 1000000001
#define LL_INF 1001001001001001001

ll gcd(ll x, ll y){
	if(y==0) return x;
	return gcd(y,x%y);
}

bool bfs(vector<vector<int>> g, vector<int> &dist, int sv){
	queue<int> q;
	q.push(sv);
	dist[sv]=0;
	while(!q.empty()){
		int now = q.front(); q.pop();
		for(auto v : g[now]){
			if(dist[v]!=-1) continue;
			dist[v] = dist[now]+1;
			q.push(v);
		}
	}
}

int main(void) {
	int x,y; cin >> x >> y;
	int ans = 0;
	ans += 100000*max(0,4-x)+100000*max(0,4-y);
	if(x==1&&y==1) ans += 400000;
	out(ans);
}




Measured memory_bytes: 256
def max_distance(maze_map, wi, hi)
	w = maze_map.first.length
	h = maze_map.length
	distance = Array.new(h).map{Array.new(w, nil)}
	distance[hi][wi] = 0
	result = 0
	queue = []
	queue.push([hi, wi])
	while (!queue.empty?)
		temp_queue = []
		while(!queue.empty?)
			hci, wci = queue.shift
			if result < distance[hci][wci]
				result = distance[hci][wci]
			end
			if wci > 0 and distance[hci][wci - 1].nil? and maze_map[hci][wci - 1]
				distance[hci][wci - 1] = distance[hci][wci] + 1
				temp_queue.push([hci, wci - 1])
			end
			if hci > 0 and distance[hci - 1][wci].nil? and maze_map[hci - 1][wci]
				distance[hci - 1][wci] = distance[hci][wci] + 1
				temp_queue.push([hci - 1, wci])
			end
			if wci < w - 1 and distance[hci][wci + 1].nil? and maze_map[hci][wci + 1]
				distance[hci][wci + 1] = distance[hci][wci] + 1
				temp_queue.push([hci, wci + 1])
			end
			if hci < h - 1 and distance[hci + 1][wci].nil? and maze_map[hci + 1][wci]
				distance[hci + 1][wci] = distance[hci][wci] + 1
				temp_queue.push([hci + 1, wci])
			end
		end
		temp_queue.each { |c| queue.push(c) }
	end
	result
end

def max_move_times(w, h, maze_map)
	result = 0
	(0...h).each do |hi|
		(0...w).each do |wi|
			if maze_map[hi][wi]
				distance = max_distance(maze_map, wi, hi)
				result = distance if distance > result
			end
		end
	end
	result
end

h, w = gets.chomp.split(' ').map(&:to_i)
maze_map = Array.new(h, nil)
(0...h).each do |i|
	maze_map[i] = gets.chomp.split('').map { |c| c == "." }
end
puts max_move_times(w, h, maze_map)


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

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


const int INF = INT_MAX;
const int MOD = pow(10,9)+7;
int dy[]={0, 0, 1, -1, 0};
int dx[]={1, -1, 0, 0, 0};

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


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

const int MAX_SIZE = 3005;
ll memo[MAX_SIZE][MAX_SIZE];
vector<ll> a;
int N;


int main() {

    cin >> N;
    
    a.resize(N+5);
    for(auto i = 1; i<=N; i++) cin >> a[i];
    
    for(auto d = 0; d<N; d++){
        for(auto i = 1; i<=N; i++){
            if (i + d >N ) break;
            if ((d+1)%2 == N %2) memo[i][i+d] = max(memo[i+1][i+d]+a[i], memo[i][i+d-1] + a[i+d]);
            if ((d+1)%2 != N %2) memo[i][i+d] = min(memo[i+1][i+d]-a[i], memo[i][i+d-1] - a[i+d]);
        }
    }
    
    cout << memo[1][N] << endl;
    
    return 0;
}




Measured memory_bytes: 70016
#include<stdio.h>
#include<algorithm>
using namespace std;
int a[5010],n,k;
bool dp1[5010][5010];
bool dp2[5010][5010];
int sum[5010];
bool merg(bool*A,bool*B,int from,int to){
	sum[0] = B[0];
	for(int i=1; i<=to; i++)
		sum[i] = sum[i-1] + B[i];
	for(int i=0; i<=to; i++)
		if(A[i] && (sum[to-i] != (from-i-1<0?0:sum[from-i-1])))
			return true;
	return false;
}
int main(){
	int w,x;
	for(scanf("%d%d",&w,&k); w--;){
		scanf("%d",&x);
		if(x < k)a[n++] = x;
	}
	dp1[0][0] = 1;
	for(int i=0; i<n; i++)
	for(int j=0; j<k; j++)
	if(dp1[i][j]){
		dp1[i+1][j] = true;
		if(j+a[i]<k)dp1[i+1][j+a[i]] = true;
	}
	dp2[n][0] = 1;
	for(int i=n; i>0; i--)
	for(int j=0; j<k; j++)
	if(dp2[i][j]){
		dp2[i-1][j] = true;
		if(j+a[i-1]<k)dp2[i-1][j+a[i-1]] = true;
	}
	int res=0;
	for(int i=0; i<n; i++){
		if(!merg(dp1[i],dp2[i+1],k-a[i],k-1))
			res++;
	}
	printf("%d\n",res);
	return 0;
}


Measured memory_bytes: 49152
#include <stdio.h>

int main(){
    int x, y;
    while(1){
        scanf("%d %d", &x, &y);
        if(x==0 && y==0)break;
        if(x<y){
            printf("%d %d\n", x, y);
        }else{
            printf("%d %d\n", y, x);
        }
    }
    return 0;
}


Measured memory_bytes: 2708
#include <bits/stdc++.h>
#define MOD 1000000007LL
using namespace std;
typedef long long ll;
typedef pair<int,int> P;

int main(void){
	int a;
	scanf("%d",&a);
	printf("%.10f\n",(double)a*6.283185307179586232);
	return 0;
}


Measured memory_bytes: 3828
#include <bits/stdc++.h>
using ll = long long;
using namespace std;
#define rep(i,n) for(int i=0, i##_len=(int)(n); i<i##_len; i++)
#define reps(i,n) for(int i=1 , i##_len=(int)(n);i<=i##_len;i++)
#define rrep(i,n) for(int i=((int)(n)-1);i>=0;i--)
#define rreps(i,n) for(int i=((int)(n));i>0;i--)
#define all(x) (x).begin(), (x).end()
#define F first
#define S second
#define mp make_pair
#define pb push_back
#define solve(a) ((a)?"Yes":"No")
typedef vector<long long> V;
typedef vector<V> VV;
typedef pair<long long , long long> P;
typedef vector<P> VP;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1;} return 0;}
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1;} return 0;}
const long long INFLL = 1LL<<62;
const int INF = 1<<30;
const double PI=acos(-1);
#define repi(i,name) for(auto i=name.begin();i!=name.end();i++)
int main(){
	int n,m;
	int ans=0;
	cin >>n;
	map<string,int>sat;
	string bef;
	rep(i,n){
		cin>>bef;
		sat[bef]+=0;
		sat[bef]++;
	}
	cin>>m;
	rep(i, m)
	{
		cin >> bef;
		sat[bef] += 0;
		sat[bef]--;
	}
	repi(i,sat){
		chmax(ans,i->S);
	}
	cout<<ans<<endl;
}

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

int main() {
  int a, b, c, d;
  cin >> a >> b >> c >> d;
  int x = c - a, y = d - b;
  printf("%d %d %d %d\n", c - y, d + x, a - y, b + x);
  return 0;
}


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

using namespace std;
typedef long long ll;
#define int ll

#define REP(i,n) for(ll i=0;i<n;++i)
#define SORT(name) sort(name.begin(), name.end())
#define ZERO(p) memset(p, 0, sizeof(p))
#define MINUS(p) memset(p, -1, sizeof(p))
#if 1
#  define DBG(fmt, ...) printf(fmt, ##__VA_ARGS__)
#else
#  define DBG(fmt, ...)
#endif

const ll LLINF = (1LL<<60);
const int INF = (1LL<<30);
const int MOD = 1000000007;
#define MAX_N 100
#define MAX_M 410

ll N;
ll Ma, Mb;
ll A[MAX_N] = {};
ll B[MAX_N] = {};
ll C[MAX_N] = {};

ll dp[MAX_N][MAX_M][MAX_M] = {};

template <typename T> T gcd(T a, T b) { while (a) { b %= a; swap(a, b); } return b; }

// i を見ていて現在の比が a:b の時の最小を返す
ll dfs(ll i, ll a, ll b) {

    if(dp[i][a][b] != INF) { return dp[i][a][b]; }
    if(i >= N) {
        if(a == 0 || b == 0) {
            dp[i][a][b] = -1;
            return -1;
        }
        ll gcd_val = gcd(a, b);
        ll fix_a = a / gcd_val;
        ll fix_b = b / gcd_val;
        if(fix_a == Ma && fix_b == Mb) {
            dp[i][a][b] = 0;
            return 0;
        }
        dp[i][a][b] = -1;
        return -1;
    }

    // 足してもできるか不明
    // 足す場合
    ll cand1 = dfs(i+1, a + A[i], b + B[i]);
    if(cand1 != -1) { cand1 += C[i]; }
    // 足さない場合
    ll cand2 = dfs(i+1, a, b);

    ll ret = -1;
    if(cand1 == -1 && cand2 == -1) { ret = -1; }
    else if(cand1 == -1) { ret = cand2; }
    else if(cand2 == -1) { ret = cand1; }
    else { ret = min(cand1, cand2); }
    dp[i][a][b] = ret;
    return ret;
}


signed main()
{
    cin >> N >> Ma >> Mb;
    REP(i, N) {
        cin >> A[i] >> B[i] >> C[i];
    }
    REP(i, MAX_N) {
        REP(j, MAX_M) {
            REP(k, MAX_M) {
                dp[i][j][k] = INF;
            }
        }
    }
    ll ans = dfs(0, 0, 0);
    printf("%lld\n", ans);
    return 0;
}


Measured memory_bytes: 131584
#include <iostream>
#include <algorithm>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <string.h>
#include <vector>
#include <queue>
#include <cmath>
#include <bitset>
#include <complex>
#include <functional>
#include <numeric>
#include <iomanip>

// output
#define SPBR(w, n) std::cout<<(w + 1 == n ? '\n' : ' ');
#define YES cout << "YES" << endl
#define Yes cout << "Yes" << endl
#define NO cout << "NO" << endl
#define No cout << "No" << endl
// utility
#define ALL(i) (i).begin(), (i).end()
#define FOR(i, a, n) for(int i=(a);i<(n);++i)
#define RFOR(i, a, n) for(int i=(n)-1;i>=(a);--i)
#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 IN(a, x, b) (a<=x && x<b)
#define OUT(a, x, b) (x<a || b<=x)
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; }

// type/const
#define int ll
using ll = long long;
using ull = unsigned long long;
using ld = long double;
const int MOD = 1000000007;
/* const int MOD = 998244353; */
const int INF = 1e18;
const double PI = acos(-1);

using namespace std;
struct INIT { INIT(){
  cin.tie(0); ios::sync_with_stdio(false);
  cout << fixed << setprecision(10);
}}INIT;


signed main() {
  int X; 
  cin >> X;

  REP(i, 6000) REP(j, 6000){
    int a = i*i*i*i*i;
    int b = j*j*j*j*j;
    if(a+b == X){
      cout << i << " " << -j << "\n";
      return 0;
    }
    if(a-b == X){
      cout << i << " " << j << "\n";
      return 0;
    }
  }

  return 0;
}

Measured memory_bytes: 3652
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#include<stack>
#include<vector>
#include<map>
using namespace std;

int read(){
	int x=0,f=1;
	char c=getchar();
	while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
	while(isdigit(c)){x=(x<<3)+(x<<1)+c-48;c=getchar();}
	return x*f;
}

int k,m,n;
char c[1000000];
int main(){
	scanf("%s",c+1);
	n=strlen(c+1);
	for(register int i=1;i<=n;i++)printf("x");
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <set>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
#define rep(i,n) for(int i=0;i<n;++i)
#define INF 1e9+7

int gcd(long int a, long int b) {
	if (a < b)
		swap(a, b);
	long int r = a % b;
	while (r != 0) {
		a = b;
		b = r;
		r = a % b;
	}
	return b;

}
int main() {
	long int n, s;
	cin >> n >> s;
	vector<int>list;
	rep(i, n) {
		long int tmp;
		cin >> tmp;
		list.push_back(abs(tmp - s));
	}
	if (list.size() > 1) {
		long int ans = gcd(list[0], list[1]);
		rep(i, list.size()) {
			ans = gcd(ans, list[i]);
		}
		cout << ans;
	}
	else
		cout << list.front();
}



Measured memory_bytes: 892
import java.util.Scanner;

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

	String s = scan.next();

	int A = Integer.MAX_VALUE;
	int Z = Integer.MIN_VALUE;

	for(int i = 0; i < s.length(); i++){
	    if(s.charAt(i) == 'A' && i < A){
		A = i;
	    }
	    if(s.charAt(i) == 'Z' && i > Z){
		Z = i;
	    }
	}

	System.out.println(Z-A+1);
    }
}


Measured memory_bytes: 26640
#include<bits/stdc++.h>
using namespace std;
int cnt,n,s,flg[10];
void func(int sum,int c,int j){
	int i;
//	cout<<sum<<' '<<c<<endl;
	if(c<n){
		for(i=j;i<10;i++){
			if(sum+i>s)break;
			if(flg[i]==1){	
				if(sum+i==s&&c+1==n){
//					cout<<sum<<' '<<i<<' '<<c<<endl;
					cnt++;
				}
				else if(sum+i<s&&c+1<n){
					flg[i]=0;
					func(sum+i,c+1,i+1);
					flg[i]=1;
				}
			}
		}
	}
}
int main(void){
	int i;
	while(1){
		for(i=0;i<10;i++) flg[i]=1;
		cin>>n>>s;
		if(n==0)break;
		cnt=0;
		func(0,0,0);
		cout<<cnt<<endl;
	}
	return 0;
}

Measured memory_bytes: 3084
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 7;

int ans, dep[N][2], par[N][25], n;
vector<int > p[N][2];

void dfs(int x, int fa, int op){
	dep[x][op] = dep[fa][op] + 1;
	if (op == 1) par[x][0] = fa;
	for (int v : p[x][op]) if (v != fa){
		dfs(v, x, op);
	}
}
void init(){
	for (int i = 1; i < 20; i++){
		for (int j = 1; j <= n; j++){
			par[j][i] = par[par[j][i - 1]][i - 1];
		}
	}
}
int lca(int u, int v){
	if (dep[u][1] < dep[v][1]) swap(u, v);
	for (int i = 0; i < 20; i++) if ((dep[u][1] - dep[v][1]) >> i & 1) u = par[u][i];
	if (u == v) return u;
	for (int i = 19; i >= 0; i--) if (par[u][i] != par[v][i]) u = par[u][i], v = par[v][i];
	return par[u][0]; 
}
int dis(int u, int v){
	int lc = lca(u, v);
	return dep[u][1] + dep[v][1] - 2 * dep[lc][1];
}
void ddfs(int x, int fa){
	if (ans != -1) ans = max(ans, (dep[x][1] - 1) * 2);
	for (int v : p[x][0]){
		if (dis(x, v) >= 3) ans = -1;
	}

	for (int v : p[x][0]) if (v != fa){
		if (dep[v][0] < dep[v][1]){
			ddfs(v, x);			
		}	
	}
}

int main(){
	int S, T, u, v;
	scanf("%d%d%d", &n, &S, &T);
	for (int i = 1; i < n; i++){
		scanf("%d%d", &u, &v);
		p[u][0].push_back(v); p[v][0].push_back(u);
	}
	for (int i = 1; i < n; i++){
		scanf("%d%d", &u, &v);
		p[u][1].push_back(v); p[v][1].push_back(u);
	}
	dfs(S, 0, 0);
	dfs(T, 0, 1);
	init();
	ans = 0;
	ddfs(S, 0);

	printf("%d", ans);
	return 0;
}


Measured memory_bytes: 51708
n = int(input())
a = list(map(int, input().split()))
b = [2 if a[i] % 4 == 0 else 1 if a[i] % 2 == 0 else 0 for i in range(n)]
if b.count(2) + 2 <= b.count(0):
    print("No")
elif b.count(2) >= b.count(0):
    print("Yes")
else:
    if b.count(1) == 0:
        print("Yes")
    else:
        print("No")

Measured memory_bytes: 63640
#include<iostream>
#include<algorithm>
#include<string>
#include<cstring>
#include<sstream>
#include<iomanip>
#include<limits>
#include<deque>
#include<map>
#include<list>
#include<set>
#include <unordered_set>
#include<vector>
#include<cmath>
#include<cstdio>
#include<memory>
#include<bitset>
#include<stack>
#include<functional>
#include<queue>
#include<regex>
#include<time.h>

using namespace std;


#define YES cout<<"YES"<<endl
#define NO cout<<"NO"<<endl
#define Yes cout<<"Yes"<<endl
#define No cout<<"No"<<endl
#define yes cout<<"yes"<<endl
#define no cout<<"no"<<endl

#define Tof(x) (x) ? Yes : No
#define TOF(x) (x) ? YES : NO
#define tof(x) (x) ? yes : no

using ll = long long;

constexpr ll MOD = 1000000007;
constexpr ll INF = 1050000000;


/*vectorの要素を全部確認するやつだよ。普通に拡張for文したほうがいいよ。

for (vector<int>::iterator itr = ans.begin(); itr != ans.end(); ++itr) {
	cout << *itr << " ";
}

*/


/*for文でx,yを上下左右確認するやつだよ。正直使いづらいよ。

int dy[] = { 0, 1, 0, -1 };
int dx[] = { 1, 0, -1, 0 };


for (int i = 0; i < 4; i++) {
	int ny = y + dy[i];
	int nx = x + dx[i];
}

*/


/*繰り返し二乗法だよ。modもとってくれるよ。n^kをmodで割った余りでやってくれるよ。

ll POW_MOD(ll n, ll k, ll mod) {
	ll r = 1;

	for (; k > 0; k >>= 1) {
		if (k & 1) {
			r = (r * n) % mod;
		}
		n = (n * n) % mod;
	}
	return r;
}

*/


/*実行開始からの経過時間を表すよ。

while (clock() < 1900000) {  }

*/


/*まだ使えないテクニックのメモだよ。

for (int bit = 0; bit < (1<<n); ++bit)//bit全探索用のfor文だよ

*/


/*2重for文書くのめんどくなった時用だよ。

for (int i = 0; i < h; ++i) {
	for (int j = 0; j < w; ++j) {

	}
}

*/

ll GCD(ll a, ll b) {
	ll r = a % b;
	while (r!=0) {
		a = b;
		b = r;
		r = a % b;
	}
	return b;

}

int main(){

	int n; cin >> n;

	ll a, b;

	map<ll, ll> mp;

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


	ll c = 0;

	for (auto x : mp) {
		c += x.second;
		if (c > x.first) { cout << "No" << endl; return 0; }
	}
	cout << "Yes" << endl;

	return 0;
}


Measured memory_bytes: 12800
#include <bits/stdc++.h>
#include <boost/range/adaptors.hpp>
#include <boost/range/irange.hpp>

using namespace std;
using namespace boost;
using namespace boost::adaptors;

int main() {
    int64_t k, n;
    cin >> k >> n;

    vector<int64_t> a(n);
    for (auto&& aa : a) {
        cin >> aa;
    }

    int64_t ans = k - (k + a[0] - a[n - 1]);
    for (auto i : irange(0L, n - 1)) {
        ans = min(ans, k - (a[i + 1] - a[i]));
    }

    cout << ans << endl;
}

Measured memory_bytes: 1792
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <fstream>
#include <sstream>
#include <iomanip>

using namespace std;

long long MOD = 1000000007;

long long gcd(long long N, long long M){
    while (true){
        if (min(N,M)==0){
            return max(N,M);
        }else if (N>M){
            N%=M;
        }else{
            M%=N;
        }
    }
}

long long lcm(long long N, long long M){
    return N*M/gcd(N,M);
}

int main(){
    long long A, B;
    cin >> A >> B;

    cout << lcm(A, B) << endl;

}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> pii;
#define fi first
#define se second
#define mod 1000000007
#define ios ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define endl "\n"
ll dp[200005][3];
ll a[200005];
ll n;
ll func(ll pos,ll k,ll num)
{
	if(pos>n||num==n/2)
		return 0;
	if(dp[pos][k]!=-1)
		return dp[pos][k];
	ll d=LLONG_MIN,j;
	for(j=0;j<=k;j++)
		d=max(d,func(pos+2+j,k-j,num+1)+a[pos]);
	for(j=1;j<=k;j++)
		d=max(d,func(pos+j,k-j,num));
	dp[pos][k]=d;
	return d;
}
int main()
{
	ios;
	memset(dp,-1,sizeof(dp));
	ll i;
	cin>>n;
	for(i=1;i<=n;i++)
		cin>>a[i];
	if(n==1)
	{
		cout<<0<<endl;
		exit(0);
	}
	if(n%2)
		cout<<func(1,2,0)<<endl;
	else
		cout<<func(1,1,0)<<endl;
}


Measured memory_bytes: 17692
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<cmath>
#include<queue>
#include<map>
#include<deque>
#include<bitset>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
typedef long long ll;
typedef pair<ll,ll> P;
template<class T> inline bool chmax(T&a , T b){ if(a<b){ a=b; return true; } else{ return false; } }
template<class T> inline bool chmin(T&a , T b){ if(a>b){ a=b; return true; } else{ return false; } } 

const int INF = 1e9;
const int MOD = 1e9+7;
const ll LINF = 1e18;

int main(){
    string s,t;
    cin >> s;
    cin >> t;
    bool flag = true;
    for(int i=0;i<s.size();i++){
        if(s[i]!=t[i]){
            flag = false;
            break;
        }
    }

    if(flag){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }
}

Measured memory_bytes: 3624
str = gets.chomp
s = str.split[0]
# t = str.split[1]
    
num = gets.chomp
a = num.split[0].to_i
b = num.split[1].to_i
    
u = gets.chomp
    
if s == u then
    print("#{(a-1).to_s} #{b.to_s}")
else
    print("#{a.to_s} #{(b-1).to_s}")
end

Measured memory_bytes: 1788
#include<stdio.h>

int main(void)
{
	int a,n;
	int debt = 100000;
	
	scanf("%d",&n);
	
	for(a = 0 ; a < n ; a++){
		debt *= 1.05;
		if(debt % 1000){
			debt /= 1000;
			debt++;
			debt *= 1000;
		}
	}
	
	printf("%d\n",debt);
	
	return 0;
}

Measured memory_bytes: 592
n, m = map(int, input().split())
p1 = []
p2 = []
for i in range(n):
    a, b = map(int, input().split())
    p1.append((a, b))
for i in range(m):
    c, d = map(int, input().split())
    p2.append((c, d, i + 1))
for a, b in p1:
    z = 10 ** 9
    ans = 0
    for c, d, x in p2:
        m = abs(a - c) + abs(b - d)
        if z > m:
            z = m
            ans = x
    print(ans)


Measured memory_bytes: 3064
def resolve():
    n=int(input())
    d=10**9+7
    m=len(bin(n))-2
    a=[(n >> j) & 1 for j in range(m)]
    ansten=1
    anshati=1
    anskyu=1
    for i in range(m):
        ten = 10
        hati = 8
        kyu=9
        if a[i]==1:
            for j in range(i):
                ten=ten*ten
                hati=hati*hati
                kyu=kyu*kyu
                ten=ten%d
                hati=hati%d
                kyu=kyu%d
            ansten*=ten
            anshati*=hati
            anskyu*=kyu
            ansten=ansten%d
            anshati=anshati%d
            anskyu=anskyu%d
    print((ansten-2*anskyu+anshati)%d)
resolve()

Measured memory_bytes: 62008
#include <string>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
#include <iostream>
#include <sstream>
#include <cstring>
#include <numeric>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define F0(i,n) for (int i = 0; i < n; i++)
#define F1(i,n) for (int i = 1; i <= n; i++)
#define CL(a,x) memset(x, a, sizeof(x));
#define SZ(x) ((int)x.size())
const double eps = 1e-10;
const int inf = 1000000009;
int i, j, k, m, n, l;
int ans;

int a[200001], L[200001], R[200001], st[200001], sn;

int main() {
	//freopen("x.in", "r", stdin);
	cin >> n;
	F1(i, n) cin >> a[i];

	sn = 0;
	F1(i, n) {
		while (sn > 0 && a[i] < a[st[sn]]) sn--;
		if (sn > 0) {
			L[i] = st[sn] + 1;
		}
		else {
			L[i] = 1;
		}
		st[++sn] = i;
	}

	sn = 0;
	for (int i = n; i >= 1; i--) {
		while (sn > 0 && a[i] < a[st[sn]]) sn--;
		if (sn > 0) {
			R[i] = st[sn] - 1;
		}
		else {
			R[i] = n;
		}
		st[++sn] = i;
	}

	ll ans = 0;
	F1(i, n) ans += 1LL * (i - L[i] + 1) * (R[i] - i + 1) * a[i];
	cout << ans << endl;

	//F1(i, n) cout << L[i] << " "; cout << endl;
	//F1(i, n) cout << R[i] << " "; cout << endl;

	return 0;
}


Measured memory_bytes: 3328
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <numeric>
#include <bitset>
#include <cmath>

static const int MOD = 1000000007;
using ll = long long;
using u32 = unsigned;
using u64 = unsigned long long;
using namespace std;

template<class T> constexpr T INF = ::numeric_limits<T>::max()/32*15+208;

int main() {
    int n, x, t;
    cin >> n >> x >> t;
    cout << (n+x-1)/x*t << "\n";
    return 0;
}

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

int main() {
	int n, ans = 0;
	cin >> n;
	int pre = -1, temp;
	while (n--) {
		cin >> temp;
		if (pre == temp) {
			ans++;
			temp = -1;
		}
		pre = temp;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
# coding: utf-8
# Your code here!
import sys

stdin = sys.stdin
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip() # ignore trailing spaces

def comb(a,b):
    ans = 1
    for i in range(b):
        ans *= a - i
    for j in range(b):
        ans //= (j + 1)
    return ans

def main():
    s = ns()
    mod = 2019
    tmp1  = 1
    tmp2 = 0
    mod2019 = [1] + [0 for i in range(2018)]
    for i in range(len(s)-1, -1, -1):
        tmp2 = (tmp2 + tmp1*int(s[i]))%mod
        tmp1 = (tmp1*10)%mod
        mod2019[tmp2] += 1
    ans = 0
    for i in range(2019):
        ans += comb(mod2019[i],2)
    print(ans) 
    return

if __name__ == '__main__':
    main()

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

int main() {
	int x, a, b;
	cin >> x >> a >> b;
	if (abs(x - a) < abs(x - b)) cout << "A";
	else cout << "B";
	return 0;
}
/*
31536000のコメント解説欄
ここテンプレで用意してるから、A問題とかだとこの先空欄の危険あり

実際に数直線上の距離を比較すれば良い
*/

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

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

  string s;
  cin >> s;

  string res = "";
  for (char &c : s) {
    if (c != 'B') {
      res += c;
      continue;
    }
    if (res.empty()) continue;
    res = res.substr(0, res.size()-1);
  }
  cout << res << '\n';
  return 0;
}

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

H = input().split()
H2 = [0] * N
for i in range(K):
    a, b = map(int, input().split())
    if int(H[a-1]) > int(H[b-1]):
        H2[b-1] = 1
    elif int(H[a-1]) < int(H[b-1]):
        H2[a-1] = 1
    elif int(H[a-1]) == int(H[b-1]):
        H2[b-1] = 1
        H2[a-1] = 1
count = 0
for i in H2:
    if i == 0:
        count+=1
print(count)

Measured memory_bytes: 17432
#include <bits/stdc++.h>
#define FOR(i, a, n) for(ll i = (ll)a; i < (ll)n; i++)
#define FORR(i, n) for(ll i = (ll)n - 1LL; i >= 0LL; i--)
#define rep(i, n) FOR(i, 0, n)
#define ALL(x) (x).begin(), (x).end()
using namespace std;
using ll = long long;
template <typename T> using V = vector<T>;

constexpr int Mod = 998244353;
constexpr int mod = 1e9 + 7;
constexpr ll inf = 1LL << 60;

template <typename T> constexpr bool chmax(T &a, const T &b) {
    if(a >= b) return false;
    a = b;
    return true;
}
template <typename T> constexpr bool chmin(T &a, const T &b) {
    if(a <= b) return false;
    a = b;
    return true;
}

/*-------------------------------------------*/

const int MAX = 190;
const int LOG = 20;

int H, W;
int sum[MAX][MAX];
int dp1[MAX][MAX][MAX][2];
int dp2[MAX][MAX][MAX][2];

int calc(int h1, int w1, int h2, int w2) {
    return sum[h2][w2] - sum[h1][w2] - sum[h2][w1] + sum[h1][w1];
}

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

    cin >> H >> W;
    rep(i, H) rep(j, W) {
        char c;
        cin >> c;
        sum[i + 1][j + 1] =
            -sum[i][j] + sum[i + 1][j] + sum[i][j + 1] + (c == '#');
    }
    rep(h1, H + 1) FOR(h2, h1, H + 1) {
        int w2 = 0;
        rep(w1, W + 1) {
            chmax<int>(w2, w1);
            while(w2 < W &&
                  (calc(h1, w1, h2, w2 + 1) == 0 ||
                   calc(h1, w1, h2, w2 + 1) == (h2 - h1) * (w2 + 1 - w1)))
                w2++;
            dp1[h1][h2][w1][0] = w2;
        }
    }
    rep(w1, W + 1) FOR(w2, w1, W + 1) {
        int h2 = 0;
        rep(h1, H + 1) {
            chmax<int>(h2, h1);
            while(h2 < H &&
                  (calc(h1, w1, h2 + 1, w2) == 0 ||
                   calc(h1, w1, h2 + 1, w2) == (h2 + 1 - h1) * (w2 - w1)))
                h2++;
            dp2[h1][w1][w2][0] = h2;
        }
    }
    rep(k, LOG - 1) {
        rep(h1, H + 1) FOR(h2, h1, H + 1) {
            int w2 = 0;
            rep(w1, W + 1) {
                int w = dp1[h1][h2][w1][k & 1];
                chmax(dp1[h1][h2][w1][k + 1 & 1], dp1[h1][h2][w][k & 1]);
                chmax<int>(w2, w1);
                while(w2 < W &&
                      dp2[dp2[h1][w1][w2 + 1][k & 1]][w1][w2 + 1][k & 1] >= h2)
                    w2++;
                chmax(dp1[h1][h2][w1][k + 1 & 1], w2);
            }
        }
        rep(w1, W + 1) FOR(w2, w1, W + 1) {
            int h2 = 0;
            rep(h1, H + 1) {
                int h = dp2[h1][w1][w2][k & 1];
                chmax(dp2[h1][w1][w2][k + 1 & 1], dp2[h][w1][w2][k & 1]);
                chmax<int>(h2, h1);
                while(h2 < H &&
                      dp1[h1][h2 + 1][dp1[h1][h2 + 1][w1][k & 1]][k & 1] >= w2)
                    h2++;
                chmax(dp2[h1][w1][w2][k + 1 & 1], h2);
            }
        }
        if(dp1[0][H][0][k & 1] == W || dp2[0][0][W][k & 1] == H) {
            cout << k << endl;
            return 0;
        }
        rep(a, MAX) rep(b, MAX) rep(c, MAX) {
            dp1[a][b][c][k & 1] = 0;
            dp2[a][b][c][k & 1] = 0;
        }
    }

    return 0;
}

Measured memory_bytes: 107520
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
using namespace std;
int main(){
	int k,s;
	cin>>k;
	if(k%2==1)s=k/2*(k/2+1);
	else s=k/2*(k/2); 
	cout<<s;
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <utility>
#include <cmath>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <tuple>
#include <numeric>
#include <functional>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef pair<ll, ll> P;
#define rep(i, n) for(ll i = 0; i < n; i++)
#define exrep(i, a, b) for(ll i = a; i <= b; i++)
#define out(x) cout << x << endl
#define exout(x) printf("%.10f\n", x)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define pb push_back
#define re0 return 0
const ll mod = 1000000007;
const ll INF = 1e16;
const ll MAX_N = 100010;

ll gcd(ll x, ll y) {
    if(y == 0) {
        return x;
    }
    return gcd(y, x%y);
}

ll lcm(ll x, ll y) {
    return x/gcd(x, y)*y;
}

int main() {
    ll n, m;
    cin >> n >> m;
    string s, t;
    cin >> s >> t;

    ll g = gcd(n, m);
    ll a = n/g;
    ll b = m/g;
    rep(i, g) {
        if(s[i*a] != t[i*b]) {
            out(-1);
            re0;
        }
    }
    
    out(lcm(n, m));
    re0;
}

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

int main() {
  int32_t X = 0, Y = 0;
  std::cin >> X >> Y;

  if(Y%2!=0){
    std::cout << "No" << std::endl;
    return 0;
  }

  int32_t t = 2*X-Y/2, k= Y/2-X;

  std::cout << ((t>=0 && k>=0)? "Yes":"No") << std::endl;

  return 0;
}

Measured memory_bytes: 3636
#include <algorithm>
#include <array>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <vector>
using namespace std;
#define int long long

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

    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    vector<int> m(1000000 + 10);
    for (auto &&i : a) {
        m[i]++;
    }

    sort(a.begin(), a.end());

    int ans = 0;
    for (int i = 0; i < n; i++) {
        m[a[i]]--;
        bool flug = true;

        if (m[a[i]] > 0)
            flug = false;
        else
            for (int j = 1; j * j <= a[i]; j++) {
                if (a[i] % j == 0 && (m[j] > 0 || m[a[i] / j] > 0))
                    flug = false;
            }

        if (flug) ans++;

        m[a[i]]++;
    }

    cout << ans << endl;
}


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

#define MAX_V 205
#define INF 1e9

// 辺を表す構造体 (行き先, 容量, 逆辺)
struct edge {
    int to, cap, rev;
};

vector<edge> G[MAX_V]; // グラフの隣接リスト表現
bool used[MAX_V];           // DFSですでに調べたかのフラグ

// fromからtoへ向かう容量capの辺をグラフに追加する
void add_edge(int from, int to, int cap) {
    G[from].push_back((edge){to, cap, G[to].size()});
    G[to].push_back((edge){from, 0, G[from].size() - 1});
}

// 増加パスをDFSで探す
int dfs(int v, int t, int f) {
    if (v == t)
        return f;
    used[v] = true;
    for (int i = 0; i < G[v].size(); i++) {
        edge &e = G[v][i];
        if (!used[e.to] && e.cap > 0) {
            int d = dfs(e.to, t, min(f, e.cap));
            if (d > 0) {
                e.cap -= d;
                G[e.to][e.rev].cap += d;
                return d;
            }
        }
    }
    return 0;
}

// sからtへの最大流を求める
int max_flow(int s, int t) {
    int flow = 0;
    for (;;) {
        memset(used, 0, sizeof(used));
        int f = dfs(s, t, INF);
        if (f == 0)
            return flow;
        flow += f;
    }
}

int main(){
    int n;
    cin >> n;
    vector<pair<int, int>> red, blue;
    for(int i=1;i<=n;++i){
        int a, b;
        cin >> a >> b;
        red.push_back(make_pair(a, b));
        add_edge(0, i, 1);
    }
    for(int i=1;i<=n;++i){
        int c, d;
        cin >> c >> d;
        blue.push_back(make_pair(c, d));
        add_edge(n+i, 2*n+1, 1);
    }

    for(int i=1;i<=n;++i){
        for(int j=1;j<=n;++j){
            if(red[i-1].first < blue[j-1].first && red[i-1].second < blue[j-1].second){
                add_edge(i, n+j, 1);
            }
        }
    }

    cout << max_flow(0, 2*n+1) << endl;

    return 0;
}


Measured memory_bytes: 384
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
using namespace std;
int main()
{
    int n,a[200005],i,b[200005];
    while(scanf("%d",&n)==1)
    {
        int x1,x2;
        for(i=0;i<n;i++)
        {
            scanf("%d",&a[i]);
            b[i]=a[i];
        }
        sort(b,b+n);
        x1=b[(n-1)/2],x2=b[n/2];
        for(i=0;i<n;i++)
        {
            if(a[i]<=x1)
                printf("%d\n",x2);
            else
                printf("%d\n",x1);
        }
    }
    return 0;
}


Measured memory_bytes: 3712
N,K=list(map(int,input().split()))
a=list(map(int,input().split()))
a.sort(key=lambda x:abs(x),reverse=True)

mod=10**9+7

p=[]
m=[]
zero=False
cntm=0
cntp=0

for aa in a:
    if aa>=0:
        p.append(aa)
        if cntp+cntm<K:
            cntp+=1
    elif aa<0:
        m.append(-aa)
        if cntp+cntm<K:
            cntm+=1
    
    if aa==0:
        zero=True

ans=1

if cntm%2==1:
    if cntm+1<=len(m) and cntm+1<=K and cntp+1<=len(p) and cntp+1<=K:
        if p[cntp]*p[cntp-1]>m[cntm]*m[cntm-1]:
            cntp+=1
            cntm-=1
        else:
            cntm+=1
            cntp-=1
    elif cntm+1<=len(m) and cntm+1<=K:
        cntm+=1
        cntp-=1
    elif cntp+1<=len(p) and cntp+1<=K:
        cntp+=1
        cntm-=1
    else:
        if zero:
            print(0)
            exit(0)
        
        for i in range(K):
            ans*=a[N-i-1]
            ans=(ans+mod*mod)%mod
        
        print(ans)
        exit(0)

for i in range(cntm):
    ans*=m[i]
    ans%=mod
for i in range(cntp):
    ans*=p[i]
    ans%=mod

print(ans)

Measured memory_bytes: 114568
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define VV vector
#define pb push_back
#define bitc  __builtin_popcountl
#define m_p make_pair
#define inf 200000000000000
#define MAXN 1000001
#define eps 0.0000000001
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);
string char_to_str(char c){string tem(1,c);return tem;}
// string to integer stoi()
// string to long long stoll()
// string.substr(position,length);
// integer to string to_string();

//////////////

#define S second
#define F first
#define int long long  

//////////

signed main()
{
    fastio;
    int n;
    cin>>n;
    int ans[n][3];
    for(int i=0;i<n;++i)
    {
        cin>>ans[i][0]>>ans[i][1]>>ans[i][2];
        if(i==0)
            continue;
        ans[i][0]+=max(ans[i-1][1],ans[i-1][2]);
        ans[i][1]+=max(ans[i-1][2],ans[i-1][0]);
        ans[i][2]+=max(ans[i-1][0],ans[i-1][1]);
    }
    cout<<max(ans[n-1][0],max(ans[n-1][1],ans[n-1][2]));
}

Measured memory_bytes: 2560
// Problem: F - Range Set Query
// Contest: AtCoder - AtCoder Beginner Contest 174
// URL: https://atcoder.jp/contests/abc174/tasks/abc174_f
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define pb push_back
#define mp make_pair
#define y1 y114514
#define y2 y1919810
//#define int long long
#define lsh(i) (1 << (i))
#define lshll(i) (1LL << (i))
#define repn(i, n) for (int i = 1; i <= (int)n; i++)
#define rep(i, n) for (int i = 0; i < (int)n; i++)
#define range(i, s, t) for (int i = s; i <= (int)t; i++)
#define RESET(x) memset((x), 0, sizeof(x))
const int INF = 0x3f3f3f3f;
const long double EPS = 1e-6;
const int N = 500050;
int cnt[N], ans, a[N];
void move(int pos, int sign) {
  if (sign) {
    if (++cnt[a[pos]] == 1) ++ans;
  } else {
    if (--cnt[a[pos]] == 0) --ans;
  }
}
int n, Q;
struct Query {
  int l, r, id;
} q[N];
int answer[N];
void solve() {
  scanf("%d%d", &n, &Q);
  rep(i, n) cin >> a[i];
  int BL = 1000;
  rep(i, Q) {
    int l, r;
    scanf("%d%d", &l, &r);
    --l;
    q[i] = {l, r, i};
  }
  sort(q, q + Q, [BL](const Query& a, const Query& b) {
    int al = a.l / BL, bl = b.l / BL;
    return (al != bl) ? al < bl : a.r < b.r;
  });
  int l = 0, r = 0;
  rep(i, Q) {
    while (l > q[i].l) move(--l, true);
    while (r < q[i].r) move(r++, true);
    while (l < q[i].l) move(l++, false);
    while (r > q[i].r) move(--r, false);
    answer[q[i].id] = ans;
  }
  rep(i, Q) printf("%d\n", answer[i]);
}
signed main() {
  int T = 1;
  // cin >> T;
  while (T--) solve();
  return 0;
}


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

using namespace std;

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

    int64_t ans = 0;
    vector<int64_t> v0(2019), v1(2019);
    for(int i=0; i<S.size(); i++) {
        for(int j=0; j<2019; j++) {
            v1[(10*j + S[i] - '0')%2019] += v0[j];
        }
        v1[S[i] - '0']++;
        ans += v1[0];
        swap(v0, v1);
        fill(v1.begin(), v1.end(), 0);
    }

    cout << ans << endl;
    // vector<int[2019]> v(S.size()+1);
    // for(int i=0; i<S.size(); i++) {
    //     for(int j=0; j<2019; j++) {
    //         v[i+1][(j*10 + S[i] - '0')%2019] += v[i][j];
    //     }
    //     v[i+1][S[i] - '0']++;
    // }

    // int64_t ans = 0;
    // for(int i=0; i<=S.size(); i++) {
    //     ans += v[i][0];
    // }

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


Measured memory_bytes: 3696
#include<bits/stdc++.h>
#define MAX 10010
int main(){
    int H;
    int W;
   
while(true){
    scanf("%d %d",&H,&W);
    if(H==0 && W == 0)break;
    else{
    for(int i=0;i<H;i++){
        ;
        for(int i=0;i<W;i++){
            putchar('#');
        }
    printf("\n");
    }
printf("\n");
}
}
return 0;

}


Measured memory_bytes: 3144
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<set>
#include<map>
#include<queue>
#include<cmath>
#define REP(i,a) for (int i = 0;i < (a);++i)
#define FOR(i,a,b) for (int i = (a);i < (b); ++i)
#define FORR(i,a,b) for (int i = (a);i >= (b); --i)
#define ALL(obj) (obj).begin(),(obj).end()
#define SORT(list) sort(ALL((list)));
#define MOD 1000000007
using namespace std;
using ll = long long;
int main(){
    int r;
    cin >> r;
    if(r<1200){
        cout << "ABC" << endl;
    }else if(r < 2800){
        cout << "ARC" << endl;
    }else{
        cout << "AGC" << endl;
    }
    return 0;
}

Measured memory_bytes: 3600
#include <iostream>
#include <algorithm>
#include <string>
#include <cmath>
#include <ctype.h>
#include <map>
#include <vector>
#include <stdlib.h>
#include <cctype>
#define REP(i,n) for(int i=0;i<(int)n;++i)
#define REP1(j,n) for(int j=0;j<(int)n;++j)
#define REPD(i,n) for(int i=n;i>=0;--i)
#define REPD1(j,n) for(int j=n;j=>0;--j)
#define REPS(i,n) for(int i=1;i<=(int)n;++i)
#define REPS1(j,n) for(int j=1;j<=(int)n;++j)
#define rep(i,a,n) for(int i=a;i<=(int)n;++i)
#define SZ(x) ((int)(x).size())	//size() unsigned -> int
#define DescSort(a) sort(a.begin(),a.end(),std::greater<int>())

using namespace std;
typedef long long ll;

int main(void) {
	int a, b;
	vector<int> n,x,ans(100,0);
	for (int c = 0;; ++c) {
		cin >> a >> b;
		if (a == 0 && b == 0) break;
		n.push_back(a);
		x.push_back(b);
	}
	for(int c=0;c<n.size();c++){
		REPS(i, n[c]) {
			rep(j, i + 1, n[c]) {
				for (int z = j + 1; z <= n[c]; ++z) {
					if (x[c] == i + j + z) ans[c]++;
				}
			}
		}
	}
	for (int i = 0; i<n.size();++i) {
		cout << ans[i] << endl;
	}
	return 0;
}




Measured memory_bytes: 3160
#include <bits/stdc++.h>
#define maxn 1000233
using namespace std;
int a[maxn];
int v[maxn << 1];
int main() {
	int n, g, M = 0;
	scanf("%d", &n);
	for(int i = 1; i <= n; ++i) scanf("%d", a + i), ++v[a[i]], M = max(M, a[i]);
	g = __gcd(a[1], a[2]);
	for(int i = 1; i <= n; ++i) g = __gcd(g, a[i]);
	bool valid = true;
	for(int i = 2; i <= M; ++i) {
		int c = 0;
		for(int j = i; j < maxn && c < 2; j += i) if(v[j]) c += v[j];
		if(c > 1) valid = false;
	}
	if(valid) {
		puts("pairwise coprime");
	} else if(g == 1) {
		puts("setwise coprime");
	} else {
		puts("not coprime");
	}
	return 0;
}

Measured memory_bytes: 11420
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000
#define mod 1000000007
#define fi first
#define sc second
#define rep(i,x) for(int i=0;i<x;i++)
#define repn(i,x) for(int i=1;i<=x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())

/*
  let's try computer shogi
*/

int main(){
  string s;
  cin >> s;
  ll out = 0;
  ll cnt = 0;
  for(ll i=0;i<s.length();++i){
    if(s[i]=='W'){
      out+=i-cnt;
      cnt+=1;
    }
  }
  cout<<out<<endl;
}

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

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

Measured memory_bytes: 3660
#include <bits/stdc++.h>
using ll = long long;
using namespace std;
ll GCD(ll a, ll b){ return a ? GCD(b % a, a) : b; }
int main(){
    ll n;
    cin>>n;
    vector<ll> prime(n+1,0),divisor(n+1,0);
    for(int i=1; i<=n; i++){
        for(int j=i; j<=n; j+=i){
            prime[j] += 1;
        }
    }
    ll ans = 0;
    for(int i=1; i<=n; i++){
        ans += prime[i]*i;
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 159436
using System;
using System.Linq;
namespace algo
{
    class Program
    {
        static void Main(string[] args)
        {
            int N = int.Parse(Console.ReadLine());
            int[] A = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();

            int[] result = new int[N];

            for(int i=0; i<A.Length; ++i){
                int tmp = A[i];
                ++result[tmp - 1];
            }

            for(int i = 0; i<result.Length; ++i){
                Console.WriteLine(result[i]);
            }
            
        }
    }
}


Measured memory_bytes: 43696
//omajinai c++
#include <iostream>
#include<cmath>

#include<vector>
#include <algorithm>
#include <limits>
#include <numeric>
#include <type_traits>
#include <map>
#include <string>
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
constexpr auto mod = 1000000007;
using namespace std;
int main() {
	int n,k;
	cin >> n>>k;
	int a = 0;
	while (n != 0) {
		a++;
		n /= k;
	}
	cout << a;

}

Measured memory_bytes: 256
AC=0
WA=0
TLE=0
RE=0
N=int(input())
for i in range(N):
  y=input()
  if y=="AC":
    AC+=1
  if y=="WA":
    WA+=1
  if y=="TLE":
    TLE+=1
  if y=="RE":
    RE+=1
print("AC x "+str(AC))
print("WA x "+str(WA))
print("TLE x "+str(TLE))
print("RE x "+str(RE))

Measured memory_bytes: 9140
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate
import sys
import bisect
import string
import math
import time
from fractions import gcd
#import random


def I(): return int(input())


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


def LI(): return [int(i) for i in input().split()]


def LI_(): return [int(i)-1 for i in input().split()]


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


def input(): return sys.stdin.readline().rstrip()


def show(*inp, end='\n'):
    if show_flg:
        print(*inp, end=end)


YN = ['No', 'Yes']
MOD = 10**9+7
inf = float('inf')
IINF = 10**10
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']


show_flg = True
show_flg = False


def main():
    N = I()
    a = LI()
    ans = 0
    temp = []

    for i in range(N):
        if len(temp) == 0 and a[i] == 1:
            temp.append(1)
        elif len(temp) != 0 and a[i] == temp[-1] + 1:
            temp.append(a[i])
        else:
            ans += 1

    # print(temp)
    if len(temp) == 0:
        print(-1)
    else:
        print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 106880
# coding: utf-8
# Your code here!

n,m=map(int,input().split(" "))
s = input()
t = input()

def gcd(x, y):
    if y == 0:
        return x
    else:
        return gcd(y, x % y)

k = gcd(n,m)
k_n = int(n/k) #3
k_m = int(m/k) #2

s_a = s[0::k_n]
t_a = t[0::k_m]

if s_a == t_a:
    print(int(n*m/k))
else:
    print(-1)

Measured memory_bytes: 3316
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)
#define rep2(i, a, n) for(ll i = a; i < (ll)(n); i++)
#define memi cout << endl
#define kono(n) cout << fixed << setprecision(n)
#define all(c) (c).begin(), (c).end()
#define pb push_back
#define hina cout << ' '
#define in(n) cin >> n
#define in2(n, m) cin >> n >> m
#define in3(n, m, l) cin >> n >> m >> l
#define out(n) cout << n
const ll mei = (ll)1e9 + 7;

int main(){
  ll x, y;
  in2(x, y);
  out(x + y / 2);
  memi;
}

Measured memory_bytes: 256