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

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

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

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

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

using ll = long long;

using namespace std;

int main() {
  in(string, s, t);
  int n = s.size();
  rep(i, n) if (s.substr(i, n - i) + s.substr(0, i) == t) {
    out("Yes");
    return 0;
  }
  out("No");
}


Measured memory_bytes: 3612
#include <iostream>
#include <vector>
using namespace std;
int main() {
int N, a = 0, b = 1000000000;
cin >> N;
vector<int> A(N);
for (int i = 0; i < N; ++i) cin >> A[i];
for (int i : A) {
        a = max(a, i); 
        b = min(b, i); 
}
cout << a - b << endl;
}

Measured memory_bytes: 888
#include<bits/stdc++.h>
#define rep(i,n) for(int i = 0;i<n;i++)
using namespace std;
typedef pair<int,int> P;
typedef long long ll;
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;}
ll gcd(ll a, ll b) { return b?gcd(b,a%b):a;}
int main() {
    int n;
    cin >> n;
    vector<int>a(n);
    vector<int>cnt(1000005);
    rep(i,n) {
        cin >> a[i];
        cnt[a[i]]++;
    }
    bool pairwise = true;
    for(int i = 2;i<=1000004;i++) {
        int tmp = 0;
        for(int j = i;j<=1000004;j += i) {
            if(cnt[j] > 0) {
                tmp += cnt[j];
            }
        }
        if(tmp >= 2) {
            pairwise = false;
            break;
        }
    }
    if(pairwise) {
        cout << "pairwise coprime" << endl;
        return 0;
    }
    bool setwise = true;
    int val = a[0];
    for(int i = 1;i<n;i++) {
        val = gcd(val,a[i]);
    }
    if(val>1) setwise = false;
    if(setwise) {
        cout << "setwise coprime" << endl;
        return 0;
    }
    cout << "not coprime" << endl;
}

Measured memory_bytes: 11088
/***************************************************************
	File name: F.cpp
	Author: huhao
	Create time: Mon 20 Jan 2020 04:12:26 PM CST
***************************************************************/
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#define fr(i,a,b) for(int i=(a),end_##i=(b);i<=end_##i;i++)
#define fd(i,a,b) for(int i=(a),end_##i=(b);i>=end_##i;i--)
#define i64 long long
i64 read()
{
	i64 r=0,t=1,c=getchar();
	while(c<'0'||c>'9')
	{
		t=c=='-'?-1:1;
		c=getchar();
	}
	while(c>='0'&&c<='9')
	{
		r=r*10+c-48;
		c=getchar();
	}
	return r*t;
}
#define pii std::pair<i64,i64>
const int N=100010;
i64 w[N],f[N],n,D[N];
pii d[N];
int main()
{
	n=read();
	fr(i,1,n) d[i]=pii(read(),i);
	std::sort(d+1,d+n+1);
	fr(i,1,n) w[i]=1;
	fd(i,n,2)
	{
		pii F=*lower_bound(d+1,d+n+1,pii(d[i].first+w[d[i].second]-(n-w[d[i].second]),0));
//		printf("%lld %lld\n",d[i].second,F.second);
		if(F.first!=d[i].first+w[d[i].second]-(n-w[d[i].second])){ printf("-1\n"); return 0; }
		f[d[i].second]=F.second; w[F.second]+=w[d[i].second];
	}
	fd(i,n,2) D[f[d[i].second]]+=D[d[i].second]+w[d[i].second];
	if(D[d[1].second]!=d[1].first){ printf("-1\n"); return 0; }
	fd(i,n,2) printf("%lld %lld\n",d[i].second,f[d[i].second]);
	return 0;
}

Measured memory_bytes: 5248
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
//template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

/* attention
    long longのシフト演算には気をつけよう
    タイポした時のデバッグが死ぬほどきつくなるので変数名は最低3字くらい使った方がいいかも
*/

int main(){
    string s; cin >> s;

    bool flg = true;
    for(char c='a'; c<='z'; c++){
        int cnt = 0;
        for(int i=0; i<s.size(); i++) if(s[i] == c) cnt++;
        if(cnt >= 2) flg = false;
    }

    if(flg) cout << "yes" << endl;
    else cout << "no" << endl;

}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
const ll N = 1e5 + 5, MOD = 1e9+7;

string s;
ll cnt1,cnt2;

int main(){

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

    cin>>s;

    ll n=s.size();
    string s1="",s2="";

    for( ll i=0; i<n; i++ ){
        if(i&1)      s1+='0',s2+='1';
        else         s1+='1',s2+='0';
    }

    for( ll i=0; i<n; i++ ){
        if(s[i]!=s1[i])   cnt1++;
        if(s[i]!=s2[i])   cnt2++;
    }
    cout<<min(cnt1,cnt2)<<endl;
    return 0;
}




Measured memory_bytes: 720
#include <iostream>

using namespace std;
int main(void) {
  string s;
  int64_t k;
  cin >> s >> k;
  for (int i = 0; i < k;++i){
    if (s[i] != '1') {
      cout << s[i] << endl;
      return 0;
    }
  }
  cout << 1 << endl;
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
    string S;
    int j,i,count1=0;
    for(i=0;i<3;i++)
        cin>>S[i];
        for(i=0;i<3;i++)
        {
            for(j=1+i;j<3;j++)
        {
            if(S[i]==S[j])
                count1++;
        }
        }
        if(count1<3)
            cout<<"Yes"<<endl;
        else
            cout<<"No"<<endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cstring>
namespace Qiao_Miao_De_DP
{
	typedef long long ll;
	inline int lowbit(int x){return x&(-x);}
	const int N=21,MOD=1000000007;
	int con[N][N];
	ll f[2][N][1<<N];
	int n,m,S,p;
	void initialize()
	{
		int tmp;
		scanf("%d%d%d",&n,&m,&tmp);
		for(int i=1;i<=m;i++)
			for(int j=1;j<n;j++)
				con[i][j]=-1;
		for(int A,B,C;tmp--;con[A][B]=C)
			scanf("%d%d%d",&A,&B,&C);
		n--,S=1<<n;
	}
	void clear()
	{
		for(int j=1;j<=n+1;j++)
			for(int k=0;k<S;k++)
				f[p][j][k]=0;
	}
	void dp()
	{
		int T;p=0;
		f[0][n+1][0]=1;

		for(int i=0;i<=m;i++)
		{
			p^=1;
			clear();
			for(int k=0;k<S;k++)f[p][1][k]=f[p^1][n+1][k];

			for(int j=1;j<=n;j++)
			{
				for(int k=0;k<S;k++)
				{
//					printf("f[%d][%d][%d] = %lld\n",i,j,k,f[p][j][k]);
					if(!f[p][j][k])continue;

					if(con[i+1][j]<0 || con[i+1][j]==0)
					{
						if(!(k&(1<<(j-1))))
							(f[p][j+1][k]+=f[p][j][k])%=MOD;
					}
					if(con[i+1][j]<0 || con[i+1][j]==1)
					{
						T=k^(k&((1<<(j-1))-1));
						if(!T)T=k^(1<<(j-1));
						else T=k^lowbit(T)^(1<<(j-1));
						(f[p][j+1][T]+=f[p][j][k])%=MOD;
					}
				}
			}
		}
	}
	void solve()
	{
		initialize();
		dp();
		ll ans=0;
		for(int i=0;i<S;i++)
			ans=(ans+f[p][1][i])%MOD;
		printf("%lld\n",ans);
	}
}
int main()
{
//	freopen("in","r",stdin);
//	freopen("out","w",stdout);
	Qiao_Miao_De_DP::solve();
	return 0;
}


Measured memory_bytes: 246016
n = int(input())

res = {}
res["AC"] = 0
res["WA"] = 0
res["TLE"] = 0
res["RE"] = 0

for _ in range(n):
    res[input()] += 1

print("AC x {}".format(res["AC"]))
print("WA x {}".format(res["WA"]))
print("TLE x {}".format(res["TLE"]))
print("RE x {}".format(res["RE"]))


Measured memory_bytes: 69844
n = int(input())
s = input()

r, g, b = 0, 0, 0
rr, gg, bb = [0] * n, [0] * n, [0] * n
rcs, gcs, bcs = [0] * n, [0] * n, [0] * n
for i, c in enumerate(s):
    if c == 'R':
        r = r + 1
        rr[i] = 1
    elif c == 'G':
        g = g + 1
        gg[i] = 1
    else:
        b = b + 1
        bb[i] = 1
    rcs[i], gcs[i], bcs[i] = r, g, b

ans = 0
for j in range(1, n-1):
    l = min(j, n-1-j)
    if s[j] == 'R':
        cs1, cs2, s1, s2 = gcs, bcs, gg, bb
    elif s[j] == 'G':
        cs1, cs2, s1, s2 = rcs, bcs, rr, bb
    else:
        cs1, cs2, s1, s2 = rcs, gcs, rr, gg
    c1 = cs1[j-1], cs1[n-1]-cs1[j]
    c2 = cs2[j-1], cs2[n-1]-cs2[j]
    ans = ans + c1[1] * c2[0] + c1[0] * c2[1]
    for i in range(1, l+1):
        ans = ans - s1[j-i] * s2[j+i] - s1[j+i] * s2[j-i]

print(ans)


Measured memory_bytes: 9356
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.UncheckedIOException;
import java.util.HashMap;
import java.util.StringTokenizer;

public class Main {
	static int N,K,L;
	public static void main(String[] args) {
		SC sc = new SC(System.in);
		N=sc.nextInt();
		K=sc.nextInt();
		L=sc.nextInt();
		UnionFindTree uf=new UnionFindTree(N);
		int[] den=new int[N];
		for(int i=0;i<K; i++) {
			int f=sc.nextInt()-1;
			int t=sc.nextInt()-1;
			uf.unite(f,t);
		}
		for(int i=0; i<N; i++) {
			den[i]=uf.find(i);
		}
		uf=new UnionFindTree(N);
		int[] dou=new int[N];
		for(int i=0;i<L; i++) {
			int f=sc.nextInt()-1;
			int t=sc.nextInt()-1;
			uf.unite(f,t);
		}
		for(int i=0; i<N; i++) {
			dou[i]=uf.find(i);
		}
		HashMap<Long,Integer> num = new HashMap<Long,Integer>();
		long[] id=new long[N];
		for(int i=0; i<N; i++) {
			id[i]=((long)(den[i])*((long) N)+((long)(dou[i])));
			if(num.containsKey(id[i])) {
				num.put(id[i], num.get(id[i])+1);
			}
			else {
				num.put(id[i], 1);
			}
		}
		for(int i=0; i<N; i++) {
			if(i<N-1) {
				p(num.get(id[i])+" ");
			}
			else {
				p(num.get(id[i]));
			}
		}
		pl();
	}
	static class UnionFindTree {
		int[] root;
		int[] rank;

		UnionFindTree(int N){
			root = new int[N];
			rank = new int[N];
			for(int i=0;i<N;i++){
				root[i] = i;
			}
		}

		public int find(int x){
			if(root[x]==x){
				return x;
			}else{
				return find(root[x]);
			}
		}

		public void unite(int x,int y){
			x = find(x);
			y = find(y);
			if(x==y){
				return;
			}else{
				if(rank[x]<rank[y]){
					root[x] = y;
				}else{
					root[y] = x;
					if(rank[x]==rank[y]){
						rank[x]++;
					}
				}
			}
		}

		public boolean same(int x,int y){
			return find(x)==find(y);
		}
	}
	static class SC {
		private BufferedReader reader = null;
		private StringTokenizer tokenizer = null;
		public SC(InputStream in) {
			reader = new BufferedReader(new InputStreamReader(in));
		}
		public String next() {
			if (tokenizer == null || !tokenizer.hasMoreTokens()) {
				try {
					tokenizer = new StringTokenizer(reader.readLine());
				} catch (IOException e) {
					throw new UncheckedIOException(e);
				}
			}
			return tokenizer.nextToken();
		}
		public int nextInt() {
			return Integer.parseInt(next());
		}
		public long nextLong() {
			return Long.parseLong(next());
		}
		public double nextDouble() {
			return Double.parseDouble(next());
		}
		public String nextLine() {
			try {
				return reader.readLine();
			} catch (IOException e) {
				throw new UncheckedIOException(e);
			}
		}
	}
	public static void pl(Object o) {
		System.out.println(o);
	}
	public static void pl() {
		System.out.println();
	}
	public static void p(Object o) {
		System.out.print(o);
	}
}

Measured memory_bytes: 79808
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define MOD 1000000007
int modexp(int x, int y)
{
	int mod = MOD,res = 1;
    x = (x % mod + mod) % mod;
    while(y)
    {
        if(y & 1)res = (res*x) % mod;
        y >>= 1;
        x = ((x%mod)*(x%mod)) % mod;
    }
    return res; 
}
int modInverse(int x)
{
	return modexp(x,MOD-2)%MOD;
}

int choose(int n,int r)
{
  const int mod = MOD;
  int a = 1, b = 1;
  
 for(int i = 0; i < r; i++)
 {
   a = ((a%mod)*((n-i)%mod))%mod;
   b = ((b%mod)*((1+i)%mod))%mod;
 }
  
  int ans = ((a%mod)*((modInverse(b)%mod)%mod))%mod;
  
  return ans%mod;
}
  
int32_t main()
{

  int n,r;
  cin >> n >> r;
  
  if(n >=10)
  {
   cout << r; 
    
  }
  else
  {
    cout << r + 1000 - 100*n;
  }
  
  
}

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

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


    flag = false;
    for (int i=1; i<=1000; i++) {
        if (A<=i*K and i*K<=B) {
            flag = true;
            break;
        }
    }

    if (flag) {
        cout << "OK" << endl;
    } else {
        cout << "NG" << endl;
    }
    return 0;
}

Measured memory_bytes: 3624
#include <bits/stdc++.h>
#define int long long
#define rep(i,n) for(int i=0;i<n;++i)
#define all(a) a.begin(),a.end()
#define P pair<long long,long long>
#define double long double
using namespace std;
//桁
int kt(int a){
  double b=a;
  b=log10(b);
  int c=b;
  return c+1;
 }
int lcm(int a,int b){
  int d=a,e=b,f;
  if(a<b)
    swap(a,b);
  int c,m=1;
  while(m){
    c=a%b;
    if(c==0){
       f=b;
      m--;
    }
    else{
      a=b;
      b=c;
 }
  }
  return d*e/f;
    }
  int gcm(int a,int b){
      int d=a,e=b,f;
  if(a<b)
    swap(a,b);
  int c,m=1;
  while(m){
    c=a%b;
    if(c==0){
       f=b;
      m--;
    }
    else{
      a=b;
      b=c;
 }
  }
  return f;
  }
signed main(){
  int a,b;
  cin>>a>>b;
  if(b==1)
    cout<<0;
  else{
  int c=0;
  int d=1;
  rep(i,1000){
    d+=a-1;
    c++;
    if(d>=b)
      break;
  }
  cout<<c;
    }
}


Measured memory_bytes: 256
n,k = map(int,input().split())
arr = list(map(int,input().split()))
mod = 10**9 + 7
cnt_list = [[0]*2 for i in range(n)]
for i in range(n):
    for j in range(n):
        if arr[i] > arr[j]:
            if i > j:
                cnt_list[i][0] += 1
            else:
                cnt_list[i][1] += 1
ans = 0
for l,r in cnt_list:
    ans += -l * k + (l+r)*k*(k+1)//2
    ans %= mod
print(ans)

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



using namespace std;

typedef vector<int> VI;
typedef vector<string> VS;


//container util
#define SORT(c) sort((c).begin(),(c).end())

//repetition
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)



int main(void){

	int N, K; cin >> N >> K;

	cout << N - K + 1 << endl;




	return 0;

}


Measured memory_bytes: 256
import java.util.*;

public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int S = sc.nextInt();
		int W = sc.nextInt();
		
        if(S>W){
        	System.out.println("safe");
        	return;
        }
        System.out.println("unsafe");
        	return;
		
	}
}


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

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;

template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()

const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 100001;

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

    int n; cin >> n;
    string s; cin >> s;
    int best = 0;
    F0R(i, s.length() + 1) {
        set<char> data;
        F0R(j, i) {
            data.insert(s.at(j));
        }
        int count = 0;
        FOR(j, i, s.length()) {
            if (data.count(s.at(j)) != 0) {
                data.erase(s.at(j));
                count++;
            }
        }
        best = max(best, count);
    }
    cout << best << endl;
    return 0;
}

// read the question correctly (ll vs int)
// template by bqi343

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

template< typename Monoid >
struct SegmentTree {
  using F = function< Monoid(Monoid, Monoid) >;
 
  int sz;
  vector< Monoid > seg;
 
  const F f;
  const Monoid M1;
 
  SegmentTree(int n, const F f, const Monoid &M1) : f(f), M1(M1) {
    sz = 1;
    while(sz < n) sz <<= 1;
    seg.assign(2 * sz, M1);
  }
 
  void set(int k, const Monoid &x) {
    seg[k + sz] = x;
  }
 
  void build() {
    for(int k = sz - 1; k > 0; k--) {
      seg[k] = f(seg[2 * k + 0], seg[2 * k + 1]);
    }
  }
 
  void update(int k, const Monoid &x) {
    k += sz;
    seg[k] = x;
    while(k >>= 1) {
      seg[k] = f(seg[2 * k + 0], seg[2 * k + 1]);
    }
  }
 
  Monoid query(int a, int b) {
    Monoid L = M1, R = M1;
    for(a += sz, b += sz; a < b; a >>= 1, b >>= 1) {
      if(a & 1) L = f(L, seg[a++]);
      if(b & 1) R = f(seg[--b], R);
    }
    return f(L, R);
  }
 
  Monoid operator[](const int &k) const {
    return seg[k + sz];
  }
};

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

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

    SegmentTree< int > seg(N, [](int a, int b) { return min(a, b); }, INT_MAX);
    for(int i=0;i<N;i++){
        seg.update(i,p[i]);
    }

    vector<int> nxt(N);
    for(int i=0;i<N;){
        int i0=i++;
        while(i<N and p[i-1]<p[i]) i++;
        for(int j=i0;j<i;j++){
            nxt[j]=i;
        }
    }
    // for(int i=0;i<N;i++) cout<<nxt[i]<<' '; cout<<endl;

    vector<int> dp(N);
    for(int i=0;i+K<=N;i++){
        if(nxt[i]>=i+K){
            dp[i]=K;
            continue;
        }
        int Min=seg.query(nxt[i],i+K);
        dp[i]=lower_bound(p.begin()+i,p.begin()+nxt[i],Min)-(p.begin()+i);
        // cout<<i<<' '<<dp[i]<<endl;
    }

    reverse(p.begin(),p.end());
    for(int i=0;i<N;i++) p[i]*=-1;
    for(int i=0;i<N;){
        int i0=i++;
        while(i<N and p[i-1]<p[i]) i++;
        for(int j=i0;j<i;j++){
            nxt[j]=i;
        }
    }
    SegmentTree< int > seg2(N, [](int a, int b) { return min(a, b); }, INT_MAX);
    for(int i=0;i<N;i++){
        seg2.update(i,p[i]);
    }
    vector<int> dp2(N);
    for(int i=0;i+K<=N;i++){
        if(nxt[i]>=i+K){
            dp2[N-K-i]=K;
            continue;
        }
        int Min=seg2.query(nxt[i],i+K);
        dp2[N-K-i]=lower_bound(p.begin()+i,p.begin()+nxt[i],Min)-(p.begin()+i);
    }
    
    set<pair<int,int>> st;
    for(int i=0;i+K<=N;i++){
        if(dp[i]==K){
            st.insert({0,0});
        }else{
            int l=i+dp[i];
            int r=(i+K)-dp2[i];
            st.insert({l,r});
            // cout<<i<<' '<<l<<' '<<r<<endl;
        }
    }
    // for(int i=0;i+K<=N;i++) cout<<dp[i]<<' '; cout<<endl;
    // for(int i=0;i+K<=N;i++) cout<<dp2[i]<<' '; cout<<endl;
    cout<<st.size()<<endl;
    return 0;
}

Measured memory_bytes: 27264
<?php
fscanf(STDIN, "%d %d %d %d", $a, $b, $c, $d);
$a--;
$e = lcm($c, $d);
$x = intdiv($b, $c) - intdiv($a, $c);
$y = intdiv($b, $d) - intdiv($a, $d);
$z = intdiv($b, $e) - intdiv($a, $e);
echo $b - $a - $x - $y + $z;

function lcm($n, $m){
	return $n * $m / gcd($n, $m);
}
function gcd($n, $m) {
	return $n % $m ? gcd($m, $n % $m) : $m;
}

Measured memory_bytes: 4732
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <set>
#include <queue>
#include <iomanip>
#include <tuple>
#include <unordered_set>
#include <unordered_map>

using namespace std;

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

	priority_queue<double, vector<double>, greater<double>> pq;

	for (int i = 0; i < n; i++) {
		double temp;
		cin >> temp;
		pq.push(temp);
	}

	while (pq.size() > 1) {
		double x = pq.top();
		pq.pop();
		double y = pq.top();
		pq.pop();
		pq.push((x + y) / 2.0);
	}

	cout << pq.top();
}


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

using namespace std;

#define rep(i, n) for(int i = 0; i < (int)n; ++i)
#define FOR(i, a, b) for(int i = a; i < (int)b; ++i)
#define rrep(i, n) for(int i = ((int)n - 1); i >= 0; --i)

typedef long long ll;

const int Inf = 1e9;
const double EPS = 1e-9;
const int MOD = 1e9 + 7;

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    vector<pair<int, int> > a, b;
    rep (i, n) {
        int x, y;
        cin >> x >> y;
        a.push_back(make_pair(x, y));
        b.push_back(make_pair(y, x));
    }
    map<pair<int, int>, int> mpa, mpb;
    sort(a.begin(), a.end(), greater<pair<int, int> >());
    sort(b.begin(), b.end(), greater<pair<int, int> >());
    rep (i, n) {
        FOR (j, i + 1, n) {
            int s, t, u, v;
            s = a[i].first - a[j].first;
            t = a[i].second - a[j].second;
            u = b[i].first - b[j].first;
            v = b[i].second - b[j].second;
            mpa[make_pair(s, t)]++;
            mpb[make_pair(u, v)]++;
        }
        
    }
    int cnt = 0;
    for (auto iter = mpa.begin(); iter != mpa.end(); ++iter) cnt = max(cnt, iter->second);
    for (auto iter = mpb.begin(); iter != mpb.end(); ++iter) cnt = max(cnt, iter->second);
    cout << n - cnt << endl;
    
    return 0;
}



Measured memory_bytes: 384
import java.util.Scanner;

    public class Main {
        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            int a = sc.nextInt();
            int b = sc.nextInt();
            int area = a*b;
            int length = (2*a + 2*b);
    System.out.println(area + " " + length);
        }
    }


Measured memory_bytes: 26064
#include <bits/stdc++.h>
using namespace std;
int n,m,x,y,a[110],b[110];
int main(){
	int i,j;
	scanf("%d%d%d%d",&n,&m,&x,&y);
	int mxa=x,mnb=y;
	for (i=1;i<=n;i++) {scanf("%d",&a[i]);mxa=max(mxa,a[i]);}
	for (i=1;i<=m;i++) {scanf("%d",&b[i]);mnb=min(mnb,b[i]);}
	if (mxa>=mnb) {puts("War");return 0;}
	puts("No War");
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <atcoder/math>

using namespace std;
using namespace atcoder;

using ll = long long;

int main() {
    int T; cin >> T;
    for (int _ = 0; _ < T; _++) {
        ll N, M, A, B; cin >> N >> M >> A >> B;
        cout << floor_sum(N, M, A, B) << "\n";
    }
    return 0;
}

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

#define ALL(v) v.begin(), v.end()
#define V vector
#define P pair
using ll = long long;
using ld = long double;
using Graph = V<V<int>>;
const int MOD =  1000000007;
const ll INF = 1LL << 60;


int main() {
    int n; cin >> n;
    V<int> h(n);
    for(int i = 0; i < n; i++) cin >> h[i];

    V<int> sums;
    sums.push_back(h[0]);
    for(int i = 0; i < n - 1; i++){
        int tmp = h[i + 1] - h[i];
        if(0 < tmp) sums.push_back(tmp);
    }
    cout << accumulate(ALL(sums), 0) << endl;

    return 0;
}


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

const long long int MOD = pow(10, 9) + 7;

int main(void) {

	int N;
	cin >> N;
	long long int a = 1, b = 1, c = 1, ans;
	for (int i = 0; i < N; i++) {
		a *= 10;
		a %= MOD;
		b *= 8;
		b %= MOD;
		c *= 9;
		c %= MOD;
	}
	ans = (a + b - 2 * c) % MOD;
	if (ans < 0) ans += MOD;
	cout << ans << endl;
}

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

struct Card{ char suit, value;};
void bubble(struct Card A[], int N)
{
  rep(i, N)
  {
    for(int j = N - 1; j >= i + 1 ; j--)
    {
      if(A[j].value < A[j-1].value)
      {
        Card t = A[j];
        A[j] = A[j - 1];
        A[j - 1] = t;
      }
    }
  }
}
void selection(struct Card A[], int N)
{
  rep(i, N)
  {
    int minv = i;
    for(int j = i; j < N; j++)
    {
    if(A[j].value < A[minv].value)
    {
      minv = j;
    }
    }
    Card t = A[i]; 
    A[i] = A[minv];
    A[minv] = t;
  }
}
void print(struct Card A[],int N)
{
  for(int i = 0; i < N; i++)
  {
    if(i > 0)
    {
      cout << ' ';
    }
    cout << A[i].suit << A[i].value;
  }
  cout << endl;
}
bool isStable(struct Card C1[],struct Card C2[], int N)
{
  rep(i, N)
  {
    if(C1[i].suit != C2[i].suit)
    {
      return false;
    }
  }
  return true;
}

int main(void)
{
  int N;
  Card C1[100],C2[100];
  cin >> N;
  rep(i, N)
  {
    cin >> C1[i].suit >> C1[i].value;
  }
  rep(i, N) C2[i] = C1[i];
  bubble(C1, N);
  print(C1, N);
  cout << "Stable" << endl;
  selection(C2, N);
  print(C2, N);
  if(isStable(C1, C2, N))
  {
    cout << "Stable" << endl;
  }else{
    cout << "Not stable" << endl;
  }
  return (0);
} 


Measured memory_bytes: 3120
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mod 1000000007
typedef long long ll;

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

    map<string,int> m;
    m["SUN"] = 7;
    m["MON"] = 6;
    m["TUE"] = 5;
    m["WED"] = 4;
    m["THU"] = 3;
    m["FRI"] = 2;
    m["SAT"] = 1;
    string s;
    cin >> s;
    cout << m[s];
}

Measured memory_bytes: 256
#include <algorithm>
#include <cstdio>

using namespace std;

int main() {
  for (int x = 1;; x++) {
    int N, M[10][10];
    scanf("%d", &N);
    if (!N) return 0;
    for (int s = 0, c = 0; s <= (N-1)*2; s++)
      for (int i = min(s, N-1); i >= 0 && s-i < N; i--)
        (s % 2 ? M[i][s-i] : M[s-i][i]) = ++c;
    printf("Case %d:\n", x);
    for (int y = 0; y < N; y++) {
      for (int x = 0; x < N; x++)
        printf("%3d", M[x][y]);
      puts("");
    }
  }
}

Measured memory_bytes: 0
import java.util.*;

class Main{
	public static void main(String args[]){
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    int K = sc.nextInt();
    int [] judge = new int[N];
    int Q = sc.nextInt();
    for(int i=0;i< Q ;i++){
      int in=sc.nextInt();
      judge[in-1]++;
    }
    for(int i=0;i< N ;i++){
      if(K-Q+judge[i]<=0)System.out.println("No");
      else System.out.println("Yes");
          }

}
}


Measured memory_bytes: 65112
#include<cstdio>
#include<cstdlib>
#define NIL NULL

struct node {
  struct node * right;
  struct node * left;
  struct node * parent;
  int key;
};
typedef struct node * Node;

Node root;

Node treeMinimum(Node x) {};
Node treeMaximum(Node x) {};
Node treeSearch(Node u, int k) {};
Node treeSuccessor(Node x) {};

void treeDelete(Node z) {
  Node y; // node to be deleted
  Node x; // child of y
}

void insert(int k) {
  Node y = NIL;
  Node x = root;
  Node z;

  z = (Node)malloc(sizeof(node));
  z->key = k;
  z->left = NIL;
  z->right = NIL;

  while (x != NIL) {
    y = x;
    if (z->key < x->key) x = x->left;
    else x = x->right;
  }

  z->parent = y;

  if (y == NIL) root = z;
  else if (z->key < y->key) y->left = z;
  else y->right = z;
}

void inorder(Node u) {
  if (u == NIL) return;
  inorder(u->left);
  printf(" %d", u->key);
  inorder(u->right);
}

void preorder(Node u) {
  if (u == NIL) return;
  printf(" %d", u->key);
  preorder(u->left);
  preorder(u->right);
}

int main() {
  int n, i, x;
  char com[20];
  scanf("%d", &n);

  for (i = 0; i < n; i++) {
    scanf("%s", &com);
    if (com[0] == 'i') {
      scanf("%d", &x);
      insert(x);
    } else if (com[0] == 'p') {
      inorder(root);
      printf("\n");
      preorder(root);
      printf("\n");
    }
  }

  return 0;
}



Measured memory_bytes: 26172
#include<iostream>
using namespace std;
int main(){
    int H,W;
    cin >> H >> W;
    
    string S[100];
    for(int i = 0; i < H; i++){
        cin >> S[i];
    }
    
    for(int i = 0; i < W + 2; i++){
        cout << "#";
    }cout << endl;
    
    for(int i = 0; i < H; i++){
        cout << "#" << S[i] << "#" << endl;
    }
    
    for(int i = 0; i < W + 2; i++){
        cout << "#";
    }cout << endl;
    
}

Measured memory_bytes: 3584
#include<bits/stdc++.h>
#define ford(i,a,b) for(int i=(a);i>=b;i--)
#define rep1(i,a,b) for(int i=(a);(i)<=(b);(i)++)
#define rep(i,a,b) for(int i=(a);(i)<(b);(i)++)
#define ll long long
#define N 200005
#define pql priority_queue<ll>
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define rev(a,n) reverse(a,a+n)
using namespace std;
int n,a[N],t[N];
int main() {
	cin>>n;
	rep(i,0,n) {
    	cin>>a[i];
    	t[i]=a[i];
	}
	sort(t,t+n);
	rep(i,0,n) {
    	if(a[i]<t[n/2])cout<<t[n/2]<<"\n";
    	else cout<<t[n/2-1]<<"\n";
	}
	return 0;
}


Measured memory_bytes: 5092
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
const ll mod=1000000007;
ll powmod(ll a,ll b){ll res=1;a%=mod;assert(b>=0);for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}

const double PI=acos(-1.0);
int main(){
	double r;
	scanf("%lf",&r);
	printf("%.5lf",2.0*r*PI);
    return 0;
}


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

using namespace std;
#define ll long long
ll dp[100005] , n , k , tmp , h[100005];

ll solve(int ind)
{
    if (ind==n-1) return 0;
    if (ind >= n) return 1e18;
    if (dp[ind]!=-1) return dp[ind];
    ll ans=1e18;
    for (int i=ind+1; i<=ind+k && i<n; i++)
    {
        dp[ind]= ans = min(ans , abs(h[ind]-h[i])+solve(i));
    }

    return dp[ind]=ans;
}

int main()
{
    cin >> n >> k;
    memset(dp, -1 , sizeof(dp));
    for (int i=0; i<n; i++)
        cin >> h[i];
    cout << solve(0) << "\n";

    return 0;
}


Measured memory_bytes: 6528
#include <algorithm>
#include <iostream>

using namespace std;

int main()
{
	while (1) {
		int x, y;
		cin >> x >> y;
		if (x == 0 && y == 0) {
			break;
		}
		if (x < y) {
			cout << x << " " << y << endl;
		}
		else {
			cout << y << " " << x << endl;
		}
	}
	return 0;
}



Measured memory_bytes: 2984
//include
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <climits>
#include <queue>

using namespace std;

//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;

//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())

//repetition
//------------------------------------------
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI  = acos(-1.0);
const LL MOD =  1e9+7;

class UnionFind{
private:
  vector<int> par, rank;
public:
  UnionFind(int n){
	par.assign(n, 0);
	rank.assign(n, 0);
	for(int i=0;i<n;++i)
	  par[i] = i;
  }

  //find root of x
  int find(int x){
	if(par[x] == x)
	  return x;
	return (par[x] = find(par[x]));
  }

  void unite(int x, int y){
	x = find(x);
	y = find(y);
	if(x == y) return;

	if(rank[x] < rank[y])
	  par[x] = y;
	else{
	  par[y] = x;
	  if(rank[x] == rank[y])
		++rank[x];
	}
  }

  bool same(int x, int y){
	return find(x) == find(y);
  }
};

LL powM(LL a, LL b){
  if(b == 0) return 1;
  return powM(a*a%MOD,b/2) * (b&1? a: 1);
}

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

  int N, M;
  while(cin>>N>>M,N){
	UnionFind uf(N);
	vector<PII> special(M);
	REP(i,M) cin >> special[i].first >> special[i].second;
	REP(i,M) uf.unite(special[i].first-1, special[i].second-1);

	VI vis(N, 0);
	REP(i,N) vis[uf.find(i)]++;
	LL ans = 1, cnt = 0;
	REP(i,N){
	  if(uf.find(i) == i)
		ans = ans * 2 % MOD, ++cnt;
	}
	if(cnt < N) ++ans;
	cout << ans << endl;
  }
  
  return 0;
}

Measured memory_bytes: 2904
import java.util.*;

public class Main{
  public static void main(String[] args){
    Scanner scan = new Scanner(System.in);
    String s = scan.next();
    while (s.length() > 0){
      int c = s.length();
      if (c >= 7){
        String check2 = s.substring(0,7);
        if (check2.equals("dreamer")){
          if (s.length() == 7){
            System.out.println("YES");
            return;
          }
          else{
            int g = s.length();
            s = s.substring(7,g);
            if (s.length() >= 3){
              String cc = s.substring(0,3);
              if (cc.equals("ase")){
                s = "er" + s;
              }
            }
          }
          continue;
        }
      }

      if (c >= 6){
        String check1 = s.substring(0,6);
        if (check1.equals("eraser")){
          if (s.length() == 6){
            System.out.println("YES");
            return;
          }
          else{
            int g = s.length();
            s = s.substring(6,g);
          }
          continue;
        }
      }

      if (c >= 5){
        String check3 = s.substring(0,5);
        if ((check3.equals("erase")) || (check3.equals("dream"))){
          if (s.length() == 5){
            System.out.println("YES");
            return;
          }
          else{
            int g = s.length();
            s = s.substring(5,g);
          }
          continue;
        }
      }

      System.out.println("NO");
      return;
    }


  }

}


Measured memory_bytes: 58476
#include <bits/stdc++.h>
#define REP(i, n) for (ll i = 0; i < n; ++i)
#define FOR(i, b, n) for (ll i = b; i < n; ++i)

using namespace std;
using ll = long long;
using P = pair<int, int>;

void solve(int A, int B, int C, long X, long Y) {
  long ans(0);
  if (X > Y)
    ans = Y * 2 * C + (X - Y) * A;
  else
    ans = X * 2 * C + (Y - X) * B;
  ans = min(ans, A * X + B * Y);
  ans = min(ans, max(X, Y) * 2 * C);
  cout << ans << endl;
}

int main(){
  // int 3E4  long 2E9  ll 9E18
  cin.tie(0);
  ios::sync_with_stdio(false);

  int A, B, C;
  long X, Y;
  cin >> A >> B >> C >> X >> Y;

  solve(A, B, C, X, Y);

  return 0;
}


Measured memory_bytes: 3648
#include <bits/stdc++.h>
using namespace std;
int main(){
  int N;
  cin >> N;
  if ( 1 <= N && N <= 9){
    cout << N << endl;
  }
  else if ( 9 < N && N <= 99){
    cout << 9 << endl;
  }
  else if (99 < N && N <= 999){
    cout << 9 + N - 99 << endl;
  }
  else if ( 999 < N && N <= 9999){
    cout << 909 << endl;
  }
  else if ( 9999 < N && N <= 99999){
    cout << 909 + N - 9999 << endl;
  }
  else if ( N == 100000){
    cout << 90909 << endl;
  }
}


Measured memory_bytes: 256
// Problem : C - Product and GCD
// Contest : AtCoder - CADDi 2018
// URL : https://atcoder.jp/contests/caddi2018/tasks/caddi2018_a
// Memory Limit : 1024 MB
// Time Limit : 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;
 
typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;
 
typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;
 
#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,b,a) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)
#define trav(a,x) for (auto& a : x)
 
#define bug(x) cout<<#x<<"="<<x<<endl; 
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define ins insert
 
template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
const ld pii=3.14159265359; 
const int MOD = 1000000007;
const char nl = '\n';
const int MX = 200001; //check the limits, dummy
 
int main() 
{
	ios_base::sync_with_stdio(0); cin.tie(0);    
	ll n,N;
	cin>>n>>N;
	ll cp=N;
	map<ll,int> m;
	while(N%2==0)
		N/=2,m[2]++;
	for(ll x=3;x<=sqrt(cp);x+=2)
	{
		while(N%x==0)
			N/=x,m[x]++;
	}
	if(N!=1)
		m[N]++;
	ll ans=1;
	for(auto i:m)
	{
		if(i.s>=n)
			for(ll y=1;n*y<=i.s;y++)
				ans*=i.f;
	}
	cout<<ans<<nl;
	return 0;
}
 
// read the question correctly (ll vs int)
// template by bqi343

Measured memory_bytes: 3648
from sys import stdin
import fractions
N = int(stdin.readline().rstrip())
data = [int(x) for x in stdin.readline().rstrip().split()]

#ans = sum(data) - N
def lcm(a,b):
    return a * b // fractions.gcd(a,b)

lcm_num = lcm(data[0],data[1])
for i in data[2:]:
    lcm_num = lcm(lcm_num,i)

ans = 0
for j in data:
    ans += (lcm_num-1) % j
print(int(ans))

Measured memory_bytes: 5340
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<functional>
using namespace std;
int main(void)
{
	int i,j,cnt=0,len;
	char w[11],txt[1001];
	char o[27]={'A','B','C','D','E','F','G','H','I','J','K','L','N','M','O','P','Q','R','S','T','U','V','W','X','Y','Z'};
	char c[27]={'a','b','c','d','e','f','g','h','i','j','k','l','n','m','o','p','q','r','s','t','u','v','w','x','y','z'};
	scanf("%s",w);
	while(1){
		scanf("%s ",txt);
		if(strcmp("END_OF_TEXT",txt)==0) break;
		len=strlen(txt);
		for(i=0;i<len;i++){
			for(j=0;j<27;j++){
				if(txt[i]==o[j]){
					txt[i]=c[j];
				}
			}
		}
		if(strcmp(w,txt)==0) cnt++;
	}
	printf("%d\n",cnt);
	return 0;
}
		

Measured memory_bytes: 976
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
const string ln = "\n";
constexpr int INF = 1001001001;
constexpr int MOD = 1000000007;

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

  string s, t;
  cin >> s >> t;

  ll n = s.size();

  string ans = "No";
  if (s == t.substr(0, n)) {
    ans = "Yes";
  }

  cout << ans << ln;

  return 0;
}

Measured memory_bytes: 3652
#include<bits/stdc++.h>
// using namespace std;
typedef long long ll;
const int mod=998244353;
const int N=5e5+5;//,M=2e5+5;
int n,m;
int c[N];
struct Q{
    int l,r,id;
    bool operator<(Q& x){
        return l<x.l;
    }
}q[N];
int ans[N];
int s[N];
void add(int pos,int x){
    while(pos<=n){
        s[pos]+=x;
        pos+=pos&-pos;
    }
}
int que(int pos){
    int ans=0;
    while(pos){
        ans+=s[pos];
        pos-=pos&-pos;
    }
    return ans;
}

int p[N],nxt[N];//颜色桶

int main()
{
    // ios::sync_with_stdio(false);std::cin.tie(0);cout.tie(0);
    // freopen("a.in","r",stdin);
    // while(~scanf("%d",&n)){
    if(true){
    // int T;scanf("%d",&T);for(int tttt=1;tttt<=T;tttt++){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%d",c+i);
    }
    for(int i=n;i;i--){
        nxt[i]=p[c[i]];
        p[c[i]]=i;
    }
    for(int i=1;i<=n;i++){
        if(p[i]) add(p[i],1);
    }
    for(int i=1;i<=m;i++){
        scanf("%d%d",&q[i].l,&q[i].r);
        q[i].id=i;
    }
    std::sort(q+1,q+1+m);
    int pos=1;
    for(int i=1;i<=m;i++){
        while(pos<q[i].l){
            add(pos,-1);
            if(nxt[pos])add(nxt[pos],1);
            pos++;
        }
        ans[q[i].id]=que(q[i].r)-que(q[i].l-1);
    }
    for(int i=1;i<=m;i++) printf("%d\n",ans[i]);
    }return 0;
}


Measured memory_bytes: 19360
#include <algorithm>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <vector>

using namespace std;

typedef long long ll;
// constexpr ll MOD = 998244353;
constexpr ll MOD = 1000000007;

// struct UnionFind {
//     vector<int> par;
    
//     UnionFind(int N): par(N) {
//         for (int i=0;i<N;i++) par[i] = i;
//     }

//     int root(int x) {
//         if (par[x] == x) return x;
//         else return par[x] = root(par[x]);
//     }

//     void unite(int x, int y) {
//         int rx = root(x);
//         int ry = root(y);
//         if (rx == ry) return;
//         par[rx] = ry;
//     }

//     bool same(int x, int y) {
//         int rx = root(x);
//         int ry = root(y);
//         return rx == ry;
//     }
// };

int main(void) {
    string S;
    ll K;
    cin >> S >> K;
    for (int i=0;i<S.size();i++) {
        if (S[i] == '1') {
            if (K>1) K--;
            else {
                cout << 1 << endl;
                break;
            }
        } else {
            cout << S[i] << endl;
            break;
        }
    }    

    return 0;
}


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

// 総数を1000000007（素数）で割った余り
const long long mod = 1e9 + 7;

using ll = long long;
using pii  = pair<int, int>;
using pll = pair<ll, ll>;
#define ull unsigned long long
#define ld long double
#define vi vector<int>
#define vll vector<ll>
#define vc vector<char>
#define vs vector<string>
#define vpii vector<pii>
#define vpll vector<pll>

#define rep(i, n) for (int i = 0, i##_len = (n); i < i##_len; i++)
#define rep1(i, n) for (int i = 1, i##_len = (n); i <= i##_len; i++)
#define repr(i, n) for (int i = ((int)(n)-1); i >= 0; i--)
#define rep1r(i, n) for (int i = ((int)(n)); i >= 1; i--)

#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

#define SORT(v, n) sort(v, v + n);
#define VSORT(v) sort(v.begin(), v.end());
#define RSORT(x) sort(rall(x));
#define pb push_back
#define mp make_pair

#define INF (1e9)
#define PI (acos(-1))
#define EPS (1e-7)

ull gcd(ull a, ull b) { return b ? gcd(b, a % b) : a; }
ull lcm(ull a, ull b) { return a / gcd(a, b) * b; }

int main(){
    int n, d;
    cin >> n >> d;
    vector<vi> x(n, vi(d));
    rep(i, n) rep(j, d) cin >> x[i][j];
    int ans = 0;
    rep(i, n-1) for (int j=i+1; j<n; ++j) {
        int dist = 0;
        rep(k, d) {
            dist += (x[i][k] - x[j][k]) * (x[i][k] - x[j][k]);
        }
        for (int k=1; k*k<=16000; ++k) {
            if (dist == k * k) ++ans;
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
from itertools import product
N, M = map(int, input().split())
S = [list(map(int, input().split())) for _ in range(M)]
P = list(map(int, input().split()))
result = 0
for switches in product((0, 1), repeat=N):
    for s, p in zip(S, P):
        num = sum([switches[s_ - 1] for s_ in s[1:]])
        if num % 2 != p:
            break
    else:
        result += 1
print(result)


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

#define rep(...) repN((__VA_ARGS__,rep3,rep2,loop,~))(__VA_ARGS__)
#define loop(n) rep2(_loop_,n)
#define rep2(i,n) rep3(i,0,n)
#define rep3(i,begin,end) for(int i = (int)(begin), i##_end = (int)(end); i < i##_end; ++i)
#define repN(a) repX a
#define repX(a0,a1,a2,x,...) x

void solve(int A, int B, string S){
	bool ans = true;
	if(S.size() != A + B + 1) ans = false;
	rep(i, A + B + 1){
		if((i == A) ^ (S[i] == '-')) ans = false;
	}
	printf(ans ? "Yes\n" : "No\n");
}

int main(void){
	int A;
	int B;
	scanf("%d", &A);
	scanf("%d", &B);
	string S;
	cin >> S;
	solve(A, B, S);
	return 0;
}

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

#include <iostream>
//#include <algorithm>
// #include <iomanip>
#define ll long long
#define map unordered_map
#define set unordered_set

using namespace std;

const ll MOD = 1000000007;
const ll INF = (1LL << 62);

int main() {
  // std::cout << std::fixed << std::setprecision(10);
  ll a, b, c, d, e;
  scanf("%lld %lld %lld %lld %lld", &a, &b, &c, &d, &e);

  ll k;
  scanf("%lld", &k);

  cout << ((e - a) <= k ? "Yay!" : ":(") << endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
using namespace std;
int main()
{
	string s;
	int n,k;
	cin>>n>>k;
    cin>>s;
    for(int i=0;i<s.length();i++)
	 {
	 	if(i==k-1)
	 	 s[i]+=32;
	 cout<<s[i];	 
	 }
	
	
	return 0;
 } 

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

int main() {
  string s, t; cin >> s >> t;
  
  bool found = false;
  string ans = s;
  
  for (int i = s.size() - t.size(); i >= 0; i--) {
    if (s[i] == t[0] || s[i] == '?') {
      bool unfit = false; 
      string cand = s; 
      cand[i] = t[0];
      for (int j = 1; j < t.size(); j++) {
        if (cand[i + j] == '?') {
          cand[i + j] = t[j];
        } else {  
          if (cand[i + j] != t[j]) {
            unfit = true;
            break;
          }
        }
      }
      if (unfit) continue;
      found = true;
      for (int i = 0; i < cand.size(); i++) if (cand[i] == '?') cand[i] = 'a';
      if (ans != s) ans = min(ans, cand);
      else ans = cand;
    }
  }
  
  if (found) cout << ans << endl;
  else cout << "UNRESTORABLE" << endl;
}

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

int main(){
    int n;
    cin >> n;
    vector<int> x(n),y(n),h(n);
    int ex,ey,eh;
    for(int i= 0;i < n;i++){
        cin >> x.at(i) >> y.at(i) >> h.at(i);
        if(h.at(i) > 0){
            ex= x.at(i);
            ey= y.at(i);
            eh= h.at(i);
        }
    }
    
    bool is_answer = true;
    
    for(int cx = 0; cx <= 100; cx++){
        for(int cy = 0; cy <= 100; cy++){
            int ch = eh + abs(ex - cx) + abs(ey - cy);
            ch = max(ch,0);
            is_answer = true;
            
            
            for(int i =0; i < n; i++){
                int v = ch - abs(x.at(i) - cx) - abs(y.at(i) - cy);
                v = max(v,0);
                if(v != h.at(i))is_answer = false;
            }
            
            
            if(is_answer){
                if(ch == -1)ch = 1;
                cout << cx << " " << cy << " " << ch;
            }
            
        }
        
        
    }
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
char s[110];
int n,position,maxn;
int main()
{
    scanf("%d%s",&n,s+1);
    for(int i=1;i<=n;i++)
    {
        if(s[i]=='I') position++;
        else position--;
        maxn=max(maxn,position);
    }
    printf("%d\n",maxn);
    return 0;
}

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

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

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

    string s;
    cin >> s;
    string ans;
    for (char c: s) {
        if (ans.size() && ans.back() < c) {
            ans.pop_back();
        } else {
            ans.push_back(c);
        }
    }
    cout << int(ans.size()) << "\n";

    return 0;
}

Measured memory_bytes: 916
#include<cstdio>
#include<queue>
#include<tuple>

using namespace std;

char m[1200][1200];
int main(void) {
    int M=0;
    int h,w;
    priority_queue<tuple<int,int,int>> q;

    scanf("%d%d",&h,&w);
    for(int i=0; i<h; i++)
        scanf("%s", m[i]);

    for(int i=0; i<h; i++)
        for(int j=0; j<w; j++)
            if(m[i][j] == '#')
                m[i][j] = '.', q.push(make_tuple(-0, i, j));

    int dx[] = {-1, 0, 1, 0};
    int dy[] = {0, -1, 0, 1};
    while(!q.empty()) {
        auto t = q.top(); q.pop();
        auto d = -get<0>(t);
        auto i = get<1>(t);
        auto j = get<2>(t);
        if(!(0 <= i && i < h)) continue;
        if(!(0 <= j && j < w)) continue;
        if(m[i][j] != '.') continue;
        m[i][j] = '!';

        for(int k=0; k<4; k++) {
            int y = i+dy[k];
            int x = j+dx[k];

            if(m[y][x] == '.')
                q.push(make_tuple(-(d+1), y, x));
        }
        M = d;
    }

    printf("%d\n", M);
}


Measured memory_bytes: 26600