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

#define ll long long int

using namespace std;

int main() {
    ll h, w, k;
    cin >> h >> w >> k;
    vector<string> C(h);
    for (auto & c : C) cin >> c;

    ll mh = 1L<<h;
    ll mw = 1L<<w;
    ll res = 0;
    for (ll i = 0; i < mh; ++i) {
        for (ll j = 0; j < mw; ++j) {
            ll cur = 0;
            for (ll p = 0; p < h; ++p) {
                if (((1L<<p) & i) != 0) continue;
                for (ll q = 0; q < w; ++q) {
                    if (((1L<<q) & j) != 0) continue;
                    if (C[p][q] == '#') ++cur;
                }
            }
            if (cur == k) ++res;
        }
    }
    cout << res << endl;
}


Measured memory_bytes: 3624
import java.util.*;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int h = sc.nextInt();
		int w = sc.nextInt();
		int n = sc.nextInt();
		int[] colors = new int[n];

		int[][] square = new int[h][w];
		int height = 0;
		int width = 0;
		
		for(int i=0; i<colors.length; i++) {
			colors[i] = sc.nextInt();
			
			for(int j=0; j<colors[i]; j++) {
				if(height%2 ==0) {
					square[height][width] = i+1;
				}else {
					square[height][w - width -1] = i+1;
				}
				width += 1;
				if(width == w) {
					height += 1;
					width = 0;
				}
			}
		}
		
		sc.close();
		
		for(int[] row : square) {
			for(int color : row) {
				System.out.print(color + " ");
			}
			System.out.println();
		}	

	}

}

Measured memory_bytes: 32288
#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define mp make_pair
using namespace std;
using ll=long long;
using P=pair<int,int>;
const ll INF=1LL<<30;
const ll LINF=1LL<<60;
const double eps=1e-5;
const ll MOD=1e9+7;
template<typename T>void chmin(T &a,T b){a=min(a,b);};
template<typename T>void chmax(T &a,T b){a=max(a,b);};
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
int main(){
    int n;cin>>n;
    vector<ll> a(n),b(n);
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    for(int i=0;i<n;i++){
        cin>>b[i];
    }
    vector<ll> v1,v2;
    ll s=0;
    for(int i=0;i<n;i++){
        if(a[i]>b[i]){
            v1.push_back(a[i]-b[i]);
            s+=a[i]-b[i];
        }else if(a[i]<b[i]){
            v2.push_back(b[i]-a[i]);
            s-=b[i]-a[i];
        }
    }
    if(s<0){
        cout<<-1<<endl;
        return 0;
    }
    sort(all(v1));
    reverse(all(v1));
    sort(all(v2));
    s=0;
    int id=0;
    for(int i=0;i<v2.size();i++){
        while(id<v1.size()&&s<v2[i]){
            s+=v1[id];
            id++;
        }
        s-=v2[i];
    }
    cout<<v2.size()+id<<endl;
}   


Measured memory_bytes: 2812
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline void readInt(int &x) {
	x=0;int f=1;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
	while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
	x*=f;
}
inline void readLong(ll &x) {
	x=0;int f=1;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
	while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
	x*=f;
}
/*================Header Template==============*/
ll n;
int main() {
	readLong(n);
	for(ll h=1;h<=3500;h++) {
		for(ll w=1;w<=3500;w++) {
			ll tmp=4*h*w-n*h-n*w;
			ll get=n*h*w;
//			cout<<tmp<<endl;
			if(tmp<=0)
				continue;
			if(get%tmp==0) {
				cout<<h<<" "<<get/tmp<<" "<<w<<endl;
				return 0;
			}
		}
	}
} 




Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] c = new int[n - 1];
		int[] s = new int[n - 1];
		int[] f = new int[n - 1];
		for(int i = 0 ; i < n - 1 ; i++) {
			c[i] = sc.nextInt();
			s[i] = sc.nextInt();
			f[i] = sc.nextInt();
		}
		for(int i = 0 ; i < n - 1 ; i++) {
			int nowT = s[i];
			for(int j = i ; j < n - 1 ; j++) {
				if(i == j) {
					nowT += c[j];
				} else {
					int temp = s[j];
					while(nowT > temp) {
						temp += f[j];
					}
					nowT = temp;
					nowT += c[j];
				}
			}
			System.out.println(nowT);
		}
		System.out.println(0);
	}
}


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

typedef long long ll;
#define all(x) (x).begin(),(x).end()
ll MOD = ll(1e8) + 9;

template<typename T>
T mod(T a, T b){
    return (a + b) % b;
}

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

ll lcm(ll a, ll b){
    return a * b / gcd(a,b);
}

// n を素因数分解
map<ll, ll> factor(ll n){
    map<ll, ll> mp;
    for (ll i = 2; i*i <= n; i++) {
        while (n % i == 0) {
            mp[i]++;
            n /= i;
        }
    }

    if (n > 1) {
        mp[n]++;
    }

    return mp;
}

// 文字列に "hoge" が含まれているか
// string str = "hogepiyo";
// if (str.find("hoge") != string::npos) {
//     cout << "文字列が含まれています" << endl;
// }

// char to string
// char c = 'a';
// string str = {c};



void solve(){
    int A[3][3], mark[3][3];
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            cin >> A[i][j];
            mark[i][j] = 0;
        }
    }
    int N;
    cin >> N;

    for (int i = 0; i < N; i++) {
        int b; cin >> b;
        for (int j = 0; j < 3; j++) {
            for (int k = 0; k < 3; k++) {
                if (A[j][k] == b) mark[j][k] = 1;
            }
        }
    }

    int ans = 0;
    // yoko
    for (int i = 0; i < 3; i++) {
        int cnt = 0;
        for (int j = 0; j < 3; j++) {
            if (mark[i][j]) cnt++;
        }
        if (cnt == 3) {
            cout << "Yes" << endl;
            return;
        }
    }

    for (int i = 0; i < 3; i++) {
        int cnt = 0;
        for (int j = 0; j < 3; j++) {
            if (mark[j][i]) cnt++;
        }
        if (cnt == 3) {
            cout << "Yes" << endl;
            return;
        }
    }

    if (mark[0][0] & mark[1][1] & mark[2][2]) {
        cout << "Yes" << endl;
        return;
    }

    if (mark[0][2] & mark[1][1] & mark[2][0]) {
        cout << "Yes" << endl;
        return;
    }

    cout << "No" << endl;
    return;
}

int main(int argc, char const* argv[])
{
    solve();
    return 0;
}



Measured memory_bytes: 256
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int n,x,a[200002];
bool f[200002];
int main()
{
	scanf("%d%d",&n,&x);
	if(x==1||x==2*n-1)
	{
		printf("No");
		return 0;
	}
	int t=2*n-1;
	a[t/2+1]=x;
	a[t/2]=x-1;
	a[t/2+2]=x+1;
	f[x]=f[x-1]=f[x+1]=1;
	if(t/2-1>0&&x+2<=t)
		a[t/2-1]=x+2,f[x+2]=1;
	if(t/2+3<=t&&x-2>=1)
		a[t/2+3]=x-2,f[x-2]=1;
	int tot=1;
	for(int i=1;i<=t;i++)
	{
		if(a[i])continue;
		while(f[tot])
			tot++;
		a[i]=tot;
		f[tot]=1;
	}
	printf("Yes\n");
	for(int i=1;i<=t;i++)
		printf("%d\n",a[i]);
}

Measured memory_bytes: 2432
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cstring>
#include <climits>
#include <algorithm>
#include <map>
#include <set>
#include <stack>
#include <vector>
#include <queue>
#include <string>
using namespace std;

#define rep(i,n) for(int i=0; i<n; i++)
#define repa(i,s,e) for(int i=s; i<=e; i++)
#define repd(i,s,e) for(int i=s; i>=e; i--)

typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef pair<int, int> pii;

int W, H, x, y;
string f[20];
char v[20][20];

int ofs[4][2] = { {1, 0}, {-1, 0}, {0, 1}, {0, -1} };

int bfs() {
	int n = 0;
	memset(&v[0][0], 0, sizeof(char) * 20 * 20);

	queue<pii> que;
	que.push(pii(x, y));
	while(!que.empty()) {
		pii p = que.front();
		que.pop();
		if(v[p.second][p.first] == 0) {
			v[p.second][p.first] = 1;
			n++;
		} else {
			continue;
		}

		rep(i,4) {
			int nx = p.first + ofs[i][0];
			int ny = p.second + ofs[i][1];
			if(nx >= 0 && ny >= 0 && nx < W && ny < H && v[ny][nx] == 0 && f[ny][nx] == '.') {
				que.push(pii(nx, ny));
			}
		}
	}
	return n;
}

int main() {
	while(cin>>W>>H, W|H) {
		rep(i,H) {
			cin >> f[i];
			int j = f[i].find_first_of('@');
			if(j != string::npos) {
				x = j;
				y = i;
			}
		}
		cout << bfs() << endl;
	}
}

Measured memory_bytes: 1228
N, M = map(int, input().split())
A = list(map(int, input().split()))

A.sort(reverse=True)
amount = sum(A)
cnt = 0
border = amount * (1/(4*M))
for a in A:
    if a >= border:
        cnt += 1

if cnt >= M:
    print("Yes")
else:
    print("No")


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


int min(int a,int b)
{
	if(a>b)
	return b;
	else return a;
}

int cost(int n ,int h[])
{ int DP[n+1];
	DP[1] = 0; DP[2] = abs(h[2]-h[1]);
	for (int i = 3; i <= n; i++) 
	 DP[i] = min( ( DP[i-1]+ abs(h[i]-h[i-1]) ), ( DP[i-2] + abs(h[i]-h[i-2]) ) );
	 return DP[n];
}





int main() {
	
int n;
cin>>n;
int h[n+1];
for(int i=1;i<n+1;i++)
cin>>h[i];
cout<<cost(n,h);
	// your code goes here
	return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#include <sstream>
#define rep2(i,x,y) for (int i = x; i < (y); ++i)
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
typedef long long int ll;
int INF = 100100101;

int main()
{
  ios::sync_with_stdio(false);  cin.tie(0); cout.tie(0);
  ll x, k, d;
  cin >> x >> k >> d; // x:現在地 k: 繰り返し回数 d:移動距離
  x = abs(x);
  ll straight = min(k, x / d);//straight:繰り返し回数と移動回数のmin
  k -= straight;//繰り返し回数からstraight回数を減らす
  x -= straight * d;//現在地からstraight回数*移動距離を減らす
  if(k % 2 == 0){//kが偶数ならxが答え
    cout << x << endl;
  }
  else{
    cout << d-x << endl;//奇数なら移動距離から現在地を引いたのが答え
  }
  return 0;
}


Measured memory_bytes: 3616
h, w = gets.split.map(&:to_i)
cm = Array.new(h + 2){Array.new(w + 2, 0)}
que = []
a = []
1.upto(h) do |i|
  s = gets.chomp
  1.upto(w) do |j|
    if s[j - 1] == '.'
      cm[i][j] = -1
      a << [i, j]
    end
  end
end
ans = 0
a.each do |b|
  dm = Marshal.load(Marshal.dump(cm))
  que.push(b[0], b[1], 0)
  dm[b[0]][b[1]] = 0
  while que.size > 0
    y = que.shift
    x = que.shift
    r = que.shift
    ans = r + 1 if ans < r + 1
    if dm[y + 1][x] == -1
      dm[y + 1][x] = r + 1
      que << y + 1 << x << r + 1
    end
    if dm[y - 1][x] == -1
      dm[y - 1][x] = r + 1
      que << y - 1 << x << r + 1
    end
    if dm[y][x - 1] == -1
      dm[y][x - 1] = r + 1
      que << y << x - 1 << r + 1
    end
    if dm[y][x + 1] == -1
      dm[y][x + 1] = r + 1
      que << y << x + 1 << r + 1
    end
  end
end
puts ans - 1

Measured memory_bytes: 4092
#include <bits/stdc++.h>
using namespace std;
void debug() {cout<<endl;}
template<typename T,typename... Args>
void debug(T x,Args... args) {cout<<x<<" ";debug(args...);}
#define forn(i,a,b) for(int i=a;i<b;++i)
#define pb push_back
#define F first
#define S second
#define endl "\n"
typedef long long ll;
typedef pair<int, int> pii;

const int MAX = 3005;
string s, t, r;
int dp[MAX][MAX], n, m;

int f(int i, int j){
    if(i == n || j == m)return 0;
    int &ans = dp[i][j];
    if(ans != -1)return ans;
    ans = 0;
    ans = max(ans, f(i, j+1));
    ans = max(ans, f(i+1, j));
    ans = max(ans, f(i+1, j+1)+(s[i]==t[j]));
    return ans;
}

void build(int i, int j){
    if(i == n || j == m)return;
    int &ans = dp[i][j];
    if(f(i, j+1) == ans)build(i, j+1);
    else if(f(i+1, j) == ans)build(i+1, j);
    else if(f(i+1, j+1)+(s[i]==t[j]) == ans){
        r.pb(s[i]);
        build(i+1, j+1);
    }
}


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

  cin >> s >> t;

  n = s.size(), m = t.size();
  memset(dp, -1, sizeof dp);
  f(0, 0);
  build(0, 0);
  cout << r << endl;

}





Measured memory_bytes: 39360
ans = [0 for i in range (4)]
num = int(input())
for i in range (num):
    inp = input()
    if inp == 'AC':
        ans[0] += 1
    elif inp =='WA':
        ans[1] +=1
    elif inp == 'TLE':
        ans[2] += 1
    elif inp == 'RE':
        ans[3] += 1
print ('AC x {}'.format(ans[0]))
print ('WA x {}'.format(ans[1]))
print ('TLE x {}'.format(ans[2]))
print ('RE x {}'.format(ans[3]))


Measured memory_bytes: 9236
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin>>n;
int arr[n],pre[n]={0},suf[n]={0},w=0,min=INT_MAX;
for(int i=0;i<n;i++)
{
    cin>>arr[i];
w+=arr[i];
pre[i]=w;

}
w=0;
for(int i=n-1;i>=0;i--)
{
    w+=arr[i];
    suf[i]=w;
}
for(int i=0;i<n-1;i++)
{
    if(min>abs(pre[i]-suf[i+1]))
    min=abs(pre[i]-suf[i+1]);
    if(min==0)
    {
        cout<<0;
        return 0;
    }
}
cout<<min;
}


Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using static System.Console;
using System.Numerics;
class Program
{
    static void Main()
    {
        var N = int.Parse(ReadLine());
        var S = new int[N * 2, N * 2];
        for (int i = 0; i < N; i++)
        {
            var line = ReadLine();
            for (int j = 0; j < N; j++)
            {
                S[i, j] = line[j];
                S[N + i, j] = line[j];
                S[i, N + j] = line[j];
                S[N + i, N + j] = line[j];
            }
        }

        var ans = 0;
        for (int b = 0; b < N; b++)
        {
            if (IsGood(N, S, 0, b)) ans += N;
        }


        WriteLine(ans);
    }

    static bool IsGood(int N, int[,] B, int h, int w)
    {
        for (int i = 0; i < N; i++)
        {
            for (int j = 0; j < N; j++)
            {
                if (B[h + i, w + j] != B[h + j, w + i]) return false;
            }
        }
        return true;
    }
}

Measured memory_bytes: 13168
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int main(){
    string s;
    cin >> s;
    ll cntb = 0;
    ll cnt = 0;
    for(int i = 0; i < s.size(); i++){
        if(s[i] == 'B')
        cntb++;
        else 
        cnt += cntb;
    }
    cout << cnt << endl;
}

Measured memory_bytes: 640
N=int(input())
E=[[] for i in range(N)]
for i in range(N-1):
  a,b=map(int,input().split())
  a,b=a-1,b-1
  E[a].append(b)
  E[b].append(a)

F=[0]*N
S=[0]*N

stack=[]
# 番号、距離、親
stack.append([0,0,-1])
while stack:
  node=stack.pop()
  v=node[0]
  dist=node[1]
  parent=node[2]
  F[v]=dist
  childs=E[v]
  for child in childs:
    if child==parent:
      continue
    stack.append([child,dist+1,v])
  
stack=[]
# 番号、距離、親
stack.append([N-1,0,-1])
while stack:
  node=stack.pop()
  v=node[0]
  dist=node[1]
  parent=node[2]
  S[v]=dist
  childs=E[v]
  for child in childs:
    if child==parent:
      continue
    stack.append([child,dist+1,v])

FenWin=0
SunWin=0
for i in range(N):
  if F[i]<=S[i]:
    FenWin+=1
  else:
    SunWin+=1
print(("Snuke","Fennec")[FenWin>SunWin])

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

using Int = long long;
using ll = long long;

template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;};
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;};

template<typename T> void drop(T x){cout<<x<<endl;exit(0);}


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

  Int n,m;
  cin>>n>>m;
  vector<Int> ls(n),rs(n);
  for(Int i=0;i<n;i++) cin>>ls[i]>>rs[i];

  vector<Int> vs;
  for(Int l:ls){
    vs.emplace_back(l-1);
    vs.emplace_back(l);
    vs.emplace_back(l+1);
  }
  for(Int r:rs){
    vs.emplace_back(r-1);
    vs.emplace_back(r);
    vs.emplace_back(r+1);
  }
  vs.emplace_back(0);
  vs.emplace_back(1);
  vs.emplace_back(m-1);
  vs.emplace_back(m);

  sort(vs.begin(),vs.end());
  vs.erase(unique(vs.begin(),vs.end()),vs.end());

  Int sz=vs.size();
  vector<Int> acc(sz+1,0);
  for(Int i=0;i<n;i++){
    Int p=lower_bound(vs.begin(),vs.end(),ls[i])-vs.begin();
    Int q=lower_bound(vs.begin(),vs.end(),rs[i])-vs.begin();
    acc[p]++;
    acc[q+1]--;
  }
  for(Int i=0;i<sz;i++) acc[i+1]+=acc[i];

  Int num=*max_element(acc.begin(),acc.end());

  //cout<<num<<endl;

  if(num&1){
    Int rgh=0;
    for(Int i=0;i<sz;i++)
      if(acc[i]==num) rgh=i;
    cout<<m*(num-1)+vs[rgh]<<endl;
  }else{
    Int lft=0;
    for(Int i=sz;i>=0;i--)
      if(acc[i]==num) lft=i;
    cout<<m*(num-1)+(m-vs[lft])<<endl;
  }

  return 0;
}



Measured memory_bytes: 24984
process.stdin.resume();
process.stdin.setEncoding('utf8');

var lines = [];
var reader = require('readline').createInterface({
  input: process.stdin,
  output: process.stdout
});
reader.on('line', (line) => {
  lines.push(line);
});
reader.on('close', () => {
  var N = parseInt(lines[0].split(' ')[0]);
  var X = parseInt(lines[0].split(' ')[1]);
  var T = parseInt(lines[0].split(' ')[2]);
  
  var totalT = Math.ceil(N / X) * T;
  console.log(totalT);
});

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

#define fi first
#define se second
#define rep(i, n) for (ll i=0;i<(n); i++)
#define ALL(v) (v).begin(), (v).end()
#define FORR(i, a, b) for(int i=(b)-1; i>=(a); --i)
#define WHITE 0  // 未訪問
#define BLACK 1  // 訪問ずみ

template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }

using namespace std;
typedef long long ll;
typedef pair<ll, ll> pi;

const ll M=1000000007ll;
const ll MOD=1000000007ll;
const ll MAX=100000001ll;
const int N=100000;
//const ll M = 1000000000+7;

ll cnt = 0; 

struct UnionFind {
  vector<int> d;
  UnionFind(int n=0): d(n, -1){}
  int root(int x) {
    if(d[x]<0) return x;
    return d[x] = root(d[x]);
  }
  bool unite(int x, int y){
    x = root(x); y=root(y);
    if(x==y) return false;
    if (d[x]>d[y]) swap(x, y);
    d[x] += d[y];
    d[y] = x;
    return true;
  }
  bool same(int x, int y) {return root(x)==root(y);}
  int size(int x) {return -d[root(x)];}
  int factor_size() {
    int ans=0;
    rep(i,d.size()){
      if (d[i]<0) {ans++;}
    }
    return ans;
  }
  
};
  
int main(){ 
  int n,m,k,s,t;
  cin >> n>>m>>k;

  map<int, int> mp;
  vector<vector<int> > v(n);
  UnionFind g(n);
  UnionFind b(n);

  int a,bb;
  rep(i, m){
    cin>>a>>bb;
    a--;bb--;
    g.unite(a,bb);
    mp[a]++;
    mp[bb]++;
  }
  //  cout<<g.same(1,2)<<endl;
  
  rep(i, k){
    cin>>a>>bb;
    a--;bb--;
    b.unite(a,bb);
    v[a].push_back(bb);
    v[bb].push_back(a);
  }
  rep(i, n){
    ll ans = g.size(i) - mp[i];
    rep(j, v[i].size()){
      if(g.same(i, v[i][j])) ans--;
    }
    
    cout << ans-1<< " ";
  }
  
  
  cout << endl;
  
}



Measured memory_bytes: 11392
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define repd(i,a,b) for (int i=(a);i<(b);i++)
#define rep(i,n) repd(i,0,n)
typedef long long ll;
typedef long double lb;
#define int long long
#define double long double
#define endn "\n"
typedef pair<int,int> P;
template<class T> inline bool chmin(T& a, T b){if(a>b){a = b;return 1;}return 0;}
template<class T> inline bool chmax(T& a, T b){if(a<b){a = b;return 1;}return 0;}
const int MOD = 1000000007;
//const int MOD = 998244353;
template<class T> inline int add(T& a, T b, T M = MOD){a=(a+M)%M;b=(b+M)%M;a=(a+b)%M;return a;};
template<class T> inline int mul(T& a, T b, T M = MOD){if(a>=M)a%=M;if(b>=M)b%=M;a*=b;if(a>=M)a%=M;return a;};
const ll INF = 1e16;
const double EPS = 1e-10;
const double PI = 3.141592653589793;
const string abc="abcdefghijklmnopqrstuvwxyz";
const string ABC="ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const pair<int,int> fd[] = {make_pair(1,0),make_pair(-1,0),make_pair(0,1),make_pair(0,-1)}; 

////////////////////////////////////////////////////////////////////
///////////////////////___modpow___////////////////////
ll modpow(ll a,  ll n, const ll &MOD = MOD){
  ll ret = n == 0 ? 1 : modpow(a, n/2, MOD);
  (ret *= ret) %= MOD;
  if(n%2)((ret *= a) %= MOD);
  return ret;
}
///////////////////////___modinv___////////////////////
ll modinv(ll d, const ll &MOD = MOD){
  return modpow(d, MOD-2, MOD);
}
////////////////////////////////////////////////////////////////////
int n, ans;string s;
int a, b, c;
signed main(){
  cin>>n>>s;
  rep(i,n){
    if(s[i] == 'R')a++;
    else if(s[i] == 'G')b++;
    else c++;
  }
  ans = a*b*c;
  rep(i,n){
    repd(j,i+1,n){
      int k = j + (j-i);
      if(k < n && s[i] != s[j] && s[j] != s[k] && s[k] != s[i])ans--;
    }
  }
  cout << ans << endl;
}


Measured memory_bytes: 3588
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int,int> P;
 
const int INF = 1e9;
const int mod = 1e9+7;

int main()
{
    int n;
    cin >> n;
    vector<int> x(n),y;
    for(int i = 0; i < n; i++) cin >> x[i];
    y = x,sort(y.begin(),y.end());    
    for(int i = 0; i < n; i++) cout << (x[i] < y[n/2] ? y[n/2] : y[n/2-1]) << endl;
    return 0;
}

Measured memory_bytes: 3712
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <cstddef>
#include <vector>

enum {BUF_SIZE=(1<<17)};
char buf[BUF_SIZE|1], *pos, *endbuf;

inline int buffer() {
    size_t len=fread(buf, 1, BUF_SIZE, stdin);
    buf[len] = 0;
    endbuf = buf + len;
    pos = buf;
    return len;
}

inline int rebuffer() {
    ptrdiff_t left=endbuf-pos;
    if (buf+left >= pos)
        return *pos;

    memcpy(buf, pos, left);
    size_t len=fread(buf+left, 1, BUF_SIZE-left, stdin);
    endbuf = buf + (left+=len);
    *endbuf = 0;
    pos = buf;
    return len;
}

inline unsigned scan() {
    unsigned u=0;
    if (pos + 10 >= endbuf)
        rebuffer();

    do {
        u = u*10 + *pos-'0';
    } while (*++pos >= '0');

    ++pos;
    return u;
}

int main() {
    buffer();
    size_t N=scan();
    int M=scan();

    std::vector<int> B(N+1), R(N+1);
    R[1] = 1;

    for (int i=0; i<M; ++i) {
        size_t x=scan(), y=scan();

        ++B[y];
        if (R[x])
            R[y] = 1;

        if (!~--B[x])
            R[x] = 0;
    }

    int res=0;
    for (size_t i=1; i<=N; ++i)
        if (R[i])
            ++res;

    printf("%d\n", res);
    return 0;
}


Measured memory_bytes: 1152
#include <iostream>
#include <vector>
#define ll long long int

using namespace std;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll n, res = 0LL, a;
    cin >> n;
    while(n--){
        cin >> a;
        while(a%2== 0){
            res++;
            a /= 2;
        }
    }
    cout << res;
    return 0;
}

















Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define INF 1LL<<62
#define inf 998244353

ll a[100010];
int main() {
	ll n;
	cin>>n;
	ll ma=0;
	for(ll i=0;i<n;i++){
		ll now;
		cin>>now;
		a[now]++;
		ma=max(ma,now);
		if(i==0&&now!=0){
			cout << 0;
			return 0;
		}
	}
	ll ans=a[0];
	if(ans!=1){
		ans=0;
	}
	for(ll i=1;i<ma+1;i++){
		ll cnt=0;
		ll now=1;
		while(a[i]>cnt){
			cnt++;
			now*=a[i-1];
			now%=inf;
		}
		//ll now=pow(a[i-1],a[i]);
		ans*=now;
		ans%=inf;
	}
	cout <<ans%inf;
	// your code goes here
	return 0;
}

Measured memory_bytes: 1024
import collections
import itertools
N = int(input())
P = [input() for i in range(N)]
ans =[]

counter = collections.Counter(P)
mode_v = counter.most_common()[0][-1]
it = list(itertools.takewhile(lambda kv: kv[-1] == mode_v, counter.most_common()))
for i in range(len(it)):
    ans.append(it[i][0])
s_ans = sorted(ans)
for i in range(len(s_ans)):
    print(s_ans[i])

Measured memory_bytes: 51992
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
 
struct query{
  int type;//0=empty, 1=set
  ll value;
  query(int a=0,ll b=0):type(a),value(b) {}
};
 
query s[(1<<18)];
ll t[(1<<18)];
 
void compute(int k,int l,int r){
  query q=s[k];
  s[k].type=0;
  if(q.type==0||r-l==1)return;
  s[k*2+1]=s[k*2+2]=q;  
  t[k*2+1]=t[k*2+2]=q.value;
}
 
void Set(int a,int b,ll x,int k=0,int l=0,int r=(1<<17)){
  if(b<=l || r<=a)return;
  compute(k,l,r);
  if(a<=l && r<=b){
    s[k]=query(1,x);
    t[k]=x;
  }else{
    int m=(l+r)/2;
    Set(a,b,x,k*2+1,l,m);
    Set(a,b,x,k*2+2,m,r);
    t[k]=min(t[k*2+1],t[k*2+2]);
  }
}
 
ll Get(int a,int b,int k=0,int l=0,int r=(1<<17)){
  if(b<=l || r<=a)return (1LL<<60);
  compute(k,l,r);
  if(a<=l && r<=b){
    return t[k];
  }else{
    int m=(l+r)/2;
    ll lv=Get(a,b,k*2+1,l,m);
    ll rv=Get(a,b,k*2+2,m,r);
    return min(lv,rv);
  }
}
 
 
 
int main(){
  int n,q,type,a,b,x;
  Set(0,(1<<17),2147483647);
  scanf("%d %d",&n,&q);
  while(q--){
    scanf("%d",&type);
    if(type==0){
      scanf("%d %d %d",&a,&b,&x);
assert( x < INT_MAX ) ;
      b++;
      Set(a,b,x);
    }else{
      scanf("%d %d",&a,&b);
      b++;
      printf("%lld\n",Get(a,b));
    }
  }
  return 0;
}

Measured memory_bytes: 8860
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<sstream>
#include<iostream>
#include<string>
#include<queue>
#include<stack>
#include<set>
#include<list>
#include<map>
#include<vector>

using namespace std;


#define rep(i,n) for(int i=0; i<n; i++)
#define ll long long
#define INF 2147483647

// flip pair
template <typename A, typename B>
pair<B, A> flip_pair(pair<A, B> src) {
	return pair<B, A> (src.second, src.first);
}

// flip map
template <typename A, typename B>
multimap<B, A> flip_map(map<A, B> src) {
	multimap<B, A> dst;
	for(auto it = src.begin(); it != src.end(); ++it) {
		auto a = flip_pair(*it);
		dst.insert(a);
	}
	return dst;
}

// get frequency mapping from vector
template <typename Tval>
multimap<int, Tval> freq(vector<Tval> src) {
	map<Tval, int> counter;
	for(auto it = src.begin(); it != src.end(); ++it) {
		auto it2 = counter.find(*it);
		if(it2 != counter.end()) counter[*it]++;
		else counter[*it] = 1;
	}
	auto dst = flip_map(counter);
	return dst;
}

int main(){
	int n, t, a;
	cin >> n >> t >> a;
	double tmp;
	double nearest = INF;
	int ans;
	rep(i, n) {
		cin >> tmp;
		tmp = t - (tmp * 0.006);
		if(abs(tmp - a) < nearest) {
			nearest = abs(tmp - a);
			ans = i+1;
		}
	}
	
	cout << ans << endl;
}



Measured memory_bytes: 256
import sys

input = sys.stdin.buffer.readline
n, k = map(int, input().split())
A = list(map(int, input().split()))

# A.sort()




def hantei(x):
    cnt = 0
    for i in range(n):
        cnt += (A[i] - 1) // x
    return cnt


ok = 10 ** 9
ng = 0

while ok - ng > 1:
    mid = (ok + ng) // 2
    if hantei(mid) <= k:
        ok = mid
    else:
        ng = mid
    # print(ok, ng)
print(ok)


Measured memory_bytes: 92876
#include <iostream>

using namespace std;

int main() {

	int in;
	int i = 1;
	
	while (true) {
		cin >> in;
		if (in == 0) {
			break;
		}
		cout << "Case " << i << ": " << in << endl;
		i++;
	}

	return 0;
}


Measured memory_bytes: 3096
require 'pp'

N = readline.chomp.to_i

dp = Array.new(N)

=begin
dp[2] = {
  aa: 1,
  ac: 1,
  ag: 1,
  at: 1,
  ca: 1,
  cc: 1,
  cg: 1,
  ct: 1,
  ga: 1,
  gc: 1,
  gg: 1,
  gt: 1,
  ta: 1,
  tc: 1,
  tg: 1,
  tt: 1
}
=end

C = %w(a c g t)
PATTERN = /AGC|GAC|ACG|A.GC|AG.C/

keys = 64.times.each.map do |i|
  c0 = C[ i % 4 ]
  c1 = C[ (i/4) % 4 ]
  c2 = C[ (i/16) % 4 ]
  c0+c1+c2
end.sort

#pp keys

dp[3] = {}
keys.each do |k|
  if k == 'agc' or k == 'gac' or k == 'acg'
    dp[3][k] = 0
  else
    dp[3][k] = 1
  end
end

#pp dp[3], dp[3].values.inject(:+)

B = 1_000_000_007

(3..(N-1)).each do |i|
  dp[i+1] = {}
  keys.each do |k|
    if k == 'agc' or k == 'gac' or k == 'acg'
      dp[i+1][k] = 0
    elsif k =~ /.gc/
      c0 = k[0]
      dp[i+1][k] = keys.select {|k2| k2 =~ /[cgt]#{c0}g/ }.map {|k2| dp[i][k2] }.inject(:+) % B
    elsif k =~ /g.c/
      c1 = k[1]
      dp[i+1][k] = keys.select {|k2| k2 =~ /[cgt]g#{c1}/ }.map {|k2| dp[i][k2] }.inject(:+) % B
    else
      c2 = k[0]+k[1]
      dp[i+1][k] = keys.select {|k2| k2 =~ /.#{c2}/}.map {|k2| dp[i][k2] }.inject(:+) % B
    end
  end
end

puts dp[N].values.inject(:+) % B


Measured memory_bytes: 6012
import math
n = int(input())
nn = (int(math.sqrt(n)) + 2) * 2
s = [i * (i + 1) // 2 for i in range(nn)]

for i in range(nn):
    if n <= s[i]:
        mx = i
        break

for i in range(mx, 0, -1):
    f = True

    if (s[mx] - i) == n:
        f = False

    if f:
        print(i)
    else:
        pass

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

using namespace std;
using ll = long long;

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

    int n, q, ptmp, t = 0;
    cin >> n >> q;
    string s;
    queue<pair<string, int>> p;
    for(int i = 0; i < n; ++i) {
        cin >> s >> ptmp;
        p.emplace(pair<string, int>(s, ptmp));
    }
    while(!p.empty()) {
        if(p.front().second <= q) {
            t += p.front().second;
            cout << p.front().first << " " << t << "\n";
        } else {
            t += q;
            p.front().second -= q;
            p.emplace(p.front());
        }
        p.pop();
    }

    return 0;
}


Measured memory_bytes: 6308
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int T = sc.nextInt();
		Integer[][] item = new Integer[N][2];
		for (int i = 0; i < N; i++) {
			item[i][0] = sc.nextInt();
			item[i][1] = sc.nextInt();
		}
		Arrays.sort(item, new ArrayComparator(new int[]{0, 1}, true));
		int[] dp = new int[10000];
		for (int i = 0; i < dp.length; i++) {
			dp[i] = 0;
		}
		for (int i = 0; i < N; i++) {
			int wi = item[i][0];
			int vi = item[i][1];
			for (int j = T - 1; j >= 0; j--) {
				dp[j + wi] = Math.max(dp[j + wi], dp[j] + vi);
			}
		}
		int ans = 0;
		for (int i = 0; i < dp.length; i++) {
			ans = Math.max(ans, dp[i]);
		}
		System.out.println(ans);
	}

	@SuppressWarnings("rawtypes")
	public static class ArrayComparator implements Comparator<Comparable[]> {
		private final int[] columnToSort;
		private final boolean ascending;

		public ArrayComparator(int[] columnToSort, boolean ascending) {
			this.columnToSort = columnToSort;
			this.ascending = ascending;
		}

		@SuppressWarnings("unchecked")
		public int compare(Comparable[] c1, Comparable[] c2) {
			int cmp = c1[columnToSort[0]].compareTo(c2[columnToSort[0]]);
			for (int i = 1; i < columnToSort.length; i++) {
				if (cmp == 0) {
					cmp = c1[columnToSort[i]].compareTo(c2[columnToSort[i]]);
				} else {
					break;
				}
			}
			return ascending ? cmp : -cmp;
		}
	}
}

Measured memory_bytes: 43548
def calcmax c,k
    pr = 1
    max = 0
    (c.length-k+1).times do |i|
        k.times do |j|
            pr *= c[i+j]
        end
        if  pr > max
            max = pr
        end
        pr = 1
    end
    return max
end
def swap c,i,j
    t = c[i]
    c[i] = c[j]
    c[j] = t
    return c
end

loop do
    n, k = gets.split.map(&:to_i)
    if n==0 && k==0
        break
    end
    c = Array.new(n)
    n.times do |i|
        c[i] = gets.to_i
    end
    d = calcmax c, k
    max = d
    b = false
    (n-1).times do |i|
        for j in i+1..n-1
            c = swap c,i,j
            m = calcmax c,k
            if m >= max
                b = true
                max = m
            end
            c = swap c,i,j
        end
    end
    puts b ? max-d : "NO GAME"
end

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

// @author: pashka

int main() {
    ios::sync_with_stdio(false);
    
    int n;
    cin >> n;
    string s;
    cin >> s;
    
    for (int i = 0; i < s.size(); i++) {
        int x = s[i] - 'A';
        x = (x + n) % 26;
        s[i] = 'A' + x;
    }
    
    cout << s;

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
struct po{int lx,ly,rx,ry;};
int w,h;
string mp[2][51];
bool visited[51][51][51][51];
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};

bool bfs(int lx,int ly,int rx,int ry){
  queue <po> Q;
  Q.push((po){lx,ly,rx,ry});
  while(!Q.empty()){
    po t=Q.front();Q.pop();
    if(mp[0][t.ly][t.lx]=='%'&&mp[1][t.ry][t.rx]=='%')return true;
    if(visited[t.lx][t.ly][t.rx][t.ry]||mp[0][t.ly][t.lx]=='%'||mp[1][t.ry][t.rx]=='%')continue;
    visited[t.lx][t.ly][t.rx][t.ry]=1;
    for(int i=0;i<4;i++){
      int flg=0;
      int nlx=t.lx+dx[i],nly=t.ly+dy[i];
      int nrx=t.rx-dx[i],nry=t.ry+dy[i];
      if(nlx<0||nly<0||nlx>=w||nly>=h||mp[0][nly][nlx]=='#')nlx=t.lx,nly=t.ly,flg++;
      if(nrx<0||nry<0||nrx>=w||nry>=h||mp[1][nry][nrx]=='#')nrx=t.rx,nry=t.ry,flg++;
      if(flg==2||visited[nlx][nly][nrx][nry])continue;
      Q.push((po){nlx,nly,nrx,nry});
    }
  }
  return false;
}

int main(){
  while(1){
    cin >>w>>h;
    if(!w&&!h)break;
    for(int i=0;i<h;i++)cin>>mp[0][i]>>mp[1][i];
    int lx,ly,rx,ry;
    for(int i=0;i<h;i++)
      for(int j=0;j<w;j++){
	if(mp[0][i][j]=='L')lx=j,ly=i;
	if(mp[1][i][j]=='R')rx=j,ry=i;
      }

    memset(visited,0,sizeof(visited));
    if(bfs(lx,ly,rx,ry))cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
  }
  return 0;
}

Measured memory_bytes: 9592
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
#define SPEED ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
signed main()
{
    SPEED;
    int n,a,b;
    cin>>n>>a>>b;
    if(n%(a+b)<=a)
    cout<<(n/(a+b))*a+n%(a+b);
    else
    cout<<(n/(a+b))*a+a;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define what_is(x) cerr << #x <<" is " << x << endl;
typedef long long ll;
const int MOD = 998244353;
const double PI = 3.141592653589793;
const ll INF =  1e18 + 7;
const int nax = 200005;


ll power(ll a, ll b) {
	ll ans = 1;
	while (b) {
		if (b & 1) {
			ans = (ans * a);
		}
		a = (a * a);
		b = b >> 1;
	}
	return ans;
}


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int tc = 1;
	// cin >> tc;
	while (tc--) {
		int n;
		cin >> n;
		vector<ll> a(n+10);
		
		for(int i=1;i<=n;i++){
			cin >> a[i];
		}
		
		ll ans = 0;
		map<ll,int> cnt;
		for(ll j=1;j<=n;j++){
			ans += cnt[j-a[j]];
			cnt[j+a[j]]++;
		}
		cout<<ans;
	}
	return 0;
}




















Measured memory_bytes: 27376
import sys
input==sys.stdin.readline
n,c,k=map(int,input().split())
t=[int(input()) for _ in range(n)]
t.sort()
inf=float("inf")
ans=0
tl=inf
m=0
for i in range(n):
    if tl<t[i]:
        ans+=1
        m=1
        tl=t[i]+k
    elif m==c:
        ans+=1
        m=1
        tl=t[i]+k
    else:
        m+=1
        if m==1:
            tl=t[i]+k
if m:
    ans+=1
print(ans)


Measured memory_bytes: 50264
#define _USE_MATH_DEFINES
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<string>
#include<iostream>
#include<iostream>
#include<cctype>
#include<cstdio>
#include<vector>
#include<stack>
#include<queue>
#include <algorithm>
#include<math.h>
#include<set>
#include<map>
#include <sstream>
#include<iomanip>
#include <ctype.h>
using namespace std;

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


int main() {
	
	int y;
	cin >> y;
	if (y < 1200)cout << "ABC" << endl;
	else if (y < 2800)cout << "ARC" << endl;
	else cout << "AGC" << endl;

	return 0;
}

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

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

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

#define INF 1e16
#define mod 1000000007

vector<vector<ll>> g;
vector<ll> a;
vector<ll> dp;
vector<ll> res;

void dfs(ll v,ll pre){
  ll idx=(lower_bound(all(dp),a[v])-dp.begin());
  ll tmp=dp[idx];
  dp[idx]=a[v];
  res[v]=(lower_bound(all(dp),INF)-dp.begin())-1;
  for(ll nv : g[v]){
    if(nv==pre)continue;
    dfs(nv,v);
  }
  dp[idx]=tmp;
}

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

  ll N;
  cin>>N;
  g.resize(N);
  a.resize(N);
  res.resize(N);
  rep(i,N)cin>>a[i];
  rep(i,N-1){
    ll aa,b;
    cin>>aa>>b;
    aa--;b--;
    g[aa].push_back(b);
    g[b].push_back(aa);
  }
  dp.resize(N+1,INF);
  dp[0]=0;
  dfs(0,-1);
  rep(i,N){
    cout<<res[i]<<"\n";
  }

  return 0;
}


Measured memory_bytes: 30296
#include<bits/stdc++.h>
using namespace std;
#define T top()
#define E end()
#define PS push
#define Q queue
#define PP pop()
#define L0 (LL)0
#define V vector
#define ST stack
#define FI first
#define MAX 4e18
#define MIN -MAX
#define DQ deque
#define RE rend()
#define SZ size()
#define C clear()
#define B begin()
#define F front()
#define SE second
#define DL double
#define G getline
#define IN insert
#define endl "\n"
#define EM empty()
#define EE emplace
#define RB rbegin()
#define MD 1000000007
#define PSB push_back
#define PI acos(-1.00)
#define PPB pop_back()
#define PSF push_front
#define ub upper_bound
#define lb lower_bound
#define PPF pop_front()
#define EB emplace_back
#define LL long long int
#define PQ priority_queue
#define N cout<<"NO"<<endl
#define Y cout<<"YES"<<endl
#define FAST ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define file freopen("input.txt","r",stdin);freopen("output.txt","w",stdout)
#define UOSMOY v.C;w.C;ww.C;uu.C;uo.C;vo.C;vu.C;ab.C;bc.C;cc.C;uuu.C;a.C;b.C;c.C
V<LL>v;
V<LL>w,ab,bc;
set<LL>uo;
map<LL,LL>ww,cc,u;
V<pair<LL,LL> >uu;
map<LL,V<LL> >uuu;
map<pair<LL,LL>,LL> vo;
map<pair<LL,LL>,LL> vu;
LL ar[100];
LL dxx[]= {-1,0,1,0};
LL dyy[]= {0,1,0,-1};
LL dx[]= {2,1,-1,-2,-2,-1,1,2};
LL dy[]= {1,2,2,1,-1,-2,-2,-1};
struct point {
    int left, right, block, id;
};

bool cmp(const point &lhs, const point &rhs) {
    if (lhs.block < rhs.block)
        return true;
    else if (lhs.block > rhs.block)
        return false;
    else
        return lhs.right < rhs.right;
}
int main()
{
//  BRR;
//  file;
    FAST;
    char ch;
    string a,b,c;
    DL x,y,d,e,f,g,h;
//    cin>>tt;
    int n, q;
    scanf("%d %d", &n,&q);
    vector<int> A(n);
    for (int i = 0; i < n; i++)
        scanf("%d", &A[i]);

    int block_size = sqrt(n);
    vector<point> query(q);
    for (int i = 0; i < q; i++) {
        scanf("%d %d", &query[i].left, &query[i].right);
        query[i].left--, query[i].right--;
        query[i].block = query[i].left / block_size;
        query[i].id = i;
    }

    sort(query.begin(), query.end(), cmp);

    vector<int> solution(q);
    vector<int> hash(1000100);

    int left = 0, right = 0, answer = 1;
    hash[A[0]] = 1;

    for (const point &task : query) {
        while (left < task.left) {
            hash[A[left]]--;
            answer -= (hash[A[left]] == 0);
            left++;
        }
        while (left > task.left) {
            left--;
            hash[A[left]]++;
            answer += (hash[A[left]] == 1);
        }
        while (right < task.right) {
            right++;
            hash[A[right]]++;
            answer += (hash[A[right]] == 1);
        }
        while (right > task.right) {
            hash[A[right]]--;
            answer -= (hash[A[right]] == 0);
            right--;
        }
        solution[task.id] = answer;
    }

    for (int answer : solution)
        printf("%d\n", answer);

return 0;
//IN
//AL
}


Measured memory_bytes: 19320
#include <iostream>
using namespace std;
int main(void){
    int a,b,c,d;
    int e,f,g,h;
    cin >> a >> b >> c >> d;
    cin >> e >> f >> g >> h;
    int x = a+b+c+d;
    int y = e+f+g+h;
    if(x>y){
        cout << x << endl;
    }
    else{
        cout << y <<endl;
    }
}



Measured memory_bytes: 3096
#include <bits/stdc++.h>
#define For(i, a, b) for(int (i)=(int)(a); (i)<(int)(b); ++(i))
#define rFor(i, a, b) for(int (i)=(int)(a)-1; (i)>=(int)(b); --(i))
#define rep(i, n) For((i), 0, (n))
#define rrep(i, n) rFor((i), (n), 0)
#define fi first
#define se second
using namespace std;
typedef long long lint;
typedef unsigned long long ulint;
typedef pair<int, int> pii;
typedef pair<lint, lint> pll;
template<class T> bool chmax(T &a, const T &b){if(a<b){a=b; return true;} return false;}
template<class T> bool chmin(T &a, const T &b){if(a>b){a=b; return true;} return false;}
template<class T> T div_floor(T a, T b){
    if(b < 0) a *= -1, b *= -1;
    return a>=0 ? a/b : (a+1)/b-1;
}
template<class T> T div_ceil(T a, T b){
    if(b < 0) a *= -1, b *= -1;
    return a>0 ? (a-1)/b+1 : a/b;
}

constexpr lint mod = 1e9+7;
constexpr lint INF = mod * mod;
constexpr int MAX = 200010;

int main(){
    int n;
    string s;
    cin >> n >> s;
    int p[1<<(n+1)];
    rep(i, 1<<n){
        scanf("%d", &p[i]);
        p[i+(1<<n)] = p[i];
    }

    int dp[1<<(n+1)][n+1];
    rep(i, 1<<n) dp[i][0] = dp[i+(1<<n)][0] = p[i];
    For(j, 1, n+1)rep(i, 1<<n){
        int a = dp[i][j-1], b = dp[i+(1<<j-1)][j-1];
        if(a < b) swap(a, b);
        dp[i][j] = dp[i+(1<<n)][j] = (s[a-b-1] == '1' ? a : b);
    }
    rep(i, 1<<n) printf("%d\n", dp[i][n]);
}


Measured memory_bytes: 44396
from bisect import bisect_right as br
def main():
  while True:
    n, m = map(int, input().split())
    if n == 0:break
    ofuton = list(map(int, input().split()))
    dlst = sorted(map(int, input().split()))
    
    INF = 10 ** 20
    end = 2 ** n - 1
    dic = {}
    def min_score(stat, power, index):
      if stat in dic:return dic[stat]
      if stat == end:return 0
      
      mask = 1
      ret = INF
      for i in range(n):
        if mask & stat:
          mask <<= 1
          continue
        new_power = power + ofuton[i]
        new_stat = stat | mask
        new_index = br(dlst, new_power) - 1
        add = (m - new_index - 1) * ofuton[i]
        for j in range(index + 1, new_index + 1):
          if new_power - dlst[j] < dlst[j] - power:
            add += (dlst[j] - power) - (new_power - dlst[j])
        ret = min(ret, -add + min_score(new_stat, new_power, new_index))
        mask <<= 1
      dic[stat] = ret
      return ret
    
    print(sum(dlst) + min_score(0, 0, -1))

main()


Measured memory_bytes: 10124
r1, c1, r2, c2 = map(int, input().split())
MOD = 10**9+7

def init_mod_c(lim=10**7, mod=10**9+7):
    fact = [1, 1] + [0] * (lim-1)
    fact_inv = [1, 1] + [0] * (lim-1)
    inv = [0, 1] + [0] * (lim-1)
    
    for i in range(2, lim+1):
        fact[i] = fact[i - 1] * i % mod
        inv[i] = mod - inv[mod % i] * (mod//i) % mod
        fact_inv[i] = fact_inv[i - 1] * inv[i] % mod

    def mod_c(n, m):
        if n < m or n < 0 or m < 0: return 0
        return fact[n] * (fact_inv[m] * fact_inv[n-m] % mod) % mod

    return mod_c

comb = init_mod_c()
pc = lambda r, c: comb(r+c, min(r, c))

ans = 0
for i in range(r1, r2+1):
    ans += pc(i+1, c2)
    if c1 > 0: ans -= pc(i+1, c1-1)
    ans %= MOD

print(ans)

Measured memory_bytes: 376376
n, k = map(int, input().split())
d = 0

people_dic = []
have_dic = []
temp_min = []
min_people = []
min_num = 0


for all in range(1, n+1):
    people_dic.append(all)

for cnt in range(k):
    d = int(input())
    have_dic.append(list(map(int, input().split())))

for comparison in range(k):
    temp_min.append((list(set(people_dic) - set(have_dic[comparison]))))

min_people = temp_min[0]
for duplication in range(k):
    min_people = list(set(min_people) & set(temp_min[duplication]))

min_num = len(min_people)

print(min_num)

Measured memory_bytes: 9244
N = int(input())


A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

sat = 0
prev = 0

for i, a in enumerate(A):
    sat += B[a - 1]

    if i > 0:
        if (a - 1 - prev) == 1:
            sat += C[prev]

    prev = a - 1

print(sat)

Measured memory_bytes: 3064
#include<bits/stdc++.h>
#define bye return 0
#define Yes cout << "Yes" << "\n"
#define No  cout << "No" << "\n"
#define YES cout << "YES" << "\n"
#define NO cout << "NO" << "\n"
using namespace std;
int main(){
	ios::sync_with_stdio(false);
    cin.tie(NULL);
    string s;
    string a;
    string b;
    string c;
    int i = 0, j =0, k = 0;
    cin >> a;
    cin >> b;
    cin >> c;
    
    
    alice:
    if(i==a.size()){
    	cout << "A" << "\n";
    	bye;
    }else{
    	if(a[i]=='a'){
    		i++;
    		goto alice;
    	}else if(a[i] == 'b'){
    		i++;
    		goto bob;
    	}else if(a[i] == 'c'){
    		i++;
    		goto charlie;
    	}

    }

    bob:
    if(j==b.size()){
    	cout << "B" << "\n";
    	bye;
    }else{
    	if(b[j]=='a'){
    		j++;
    		goto alice;
    	}else if(b[j]=='b'){
    		j++;
    		goto bob;
    	}else if(b[j]== 'c'){
    		j++;
    		goto charlie;
    	}
    }

    charlie:
    if(k==c.size()){
    	cout << "C" << "\n";
    	bye;
    }else{
    	if(c[k]=='a'){
    		k++;
    		goto alice;
    	}else if(c[k]=='b'){
    		k++;
    		goto bob;
    	}else if(c[k]=='c'){
    		k++;
    		goto charlie;
    	}
    }
    
    

   bye;

}

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

#define N 50

using namespace std;

vector < vector < bool > > graph(N+1, vector < bool >(N+1, false));
bool visited[N+1];
int n;

void dfs(int p) {
    for (int i=1; i<=n; i++) {
        if (graph[p][i] && !visited[i]) {
            visited[i] = true;
            dfs(i);
        }
    }
    return;
}

int main() {
    int m, res = 0;

    scanf("%d %d", &n, &m);

    for (int i=0; i<m; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
        graph[a][b] = true;
        graph[b][a] = true;
    }

    for (int i=1; i<=n; i++) {
        for (int j=1; j<=n; j++) {
            if (graph[i][j] && i < j) {
                for (int k=0; k<=n; k++) {
                    visited[k] = false;
                }
                visited[1] = true;

                graph[i][j] = false;
                graph[j][i] = false;
                dfs(1);
                graph[i][j] = true;
                graph[j][i] = true;

                bool flag = true;
                for (int k=1; k<=n; k++) {
                    if (!visited[k]) {
                        flag = false;
                        break;
                    }
                }
                if (!flag) {
                    //cout << i << " " << j << endl;
                    res++;
                }
            }
        }
    }

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

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <string>
#include <string.h> 
#include <stack>
#include <bitset>
#include <map>
#include <cmath>
#include <climits>
#include <queue>

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

using namespace std;

int main() {
	int n, k, d, o;
	scanf("%d %d", &n, &k);
	vector<int> A(n, 0);
	rep(i, k) {
		scanf("%d", &d);
		rep(j, d) {
			scanf("%d", &o);
			A[o - 1]++;
		}
	}
	o = 0;
	rep(i, n) if (A[i] == 0) o++;
	printf("%d\n", o);
}

Measured memory_bytes: 3796
#include <bits/stdc++.h>
#define ss second
#define ff first
#define all(x) x.begin(), x.end()
 
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
 
const int oo = 1e9 + 7;
const ll mod = 1e9 + 7, maxn = (1 * 1e5) + 10;
const long double PI = acos(-1);

ll solve (vector<ll> vs, ll sum, int n){
    ll ans = 0;
    for  (int i=0; i<n; i++){
        sum = (sum - vs[i] + mod) % mod;
        ans = (ans + vs[i]*sum) % mod;
    }
    return ans;
}

int main (){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n;
    ll sum = 0;
    cin >> n;
    vector<ll> vs(n);

    for (auto &it: vs) cin >> it, sum = (sum + it) % mod;

    cout << solve(vs, sum, n) << endl;
    return 0;
}

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

const ll MX = 1e18;

int main() {
	int n;
	cin >> n;
	ll ans = 1;
	vector<ll> a(n);
	rep(i, n) {
		cin >> a[i];
		if (a[i] == 0) {
			cout << 0 << endl;
			return 0;
		}
	}
	rep(i, n) {

		if (MX / ans < a[i]) {
			cout << -1 << endl;
			return 0;
		}
		ans *= a[i];
	}
	cout << ans << endl;
}

Measured memory_bytes: 4036
N,C=map(int,input().split())
L=[list(map(int,input().split())) for _ in range(N)]
L.sort()
stc=[[] for _ in range(C)]
for i in range(N):
  s,t,c=L[i]
  if stc[c-1] and s-stc[c-1][-1][1]<=1:
    stc[c-1][-1]=[stc[c-1][-1][0],t]
  else:
    stc[c-1].append([s-1,t])

STC=[j for i in stc for j in i]
STC.sort()

RCM=[[0,0] for _ in range(C)]
for S,T in STC:
  for i in range(C):
    if RCM[i][1]<=S:
      RCM[i][1]=T
      break

for i in range(C):
  if RCM[i]==[0,0]:
    print(i)
    exit()
print(C)

Measured memory_bytes: 39432
#include<bits/stdc++.h>
using namespace std;
#define fs first
#define sc second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define ALL(A) A.begin(),A.end()
#define RALL(A) A.rbegin(),A.rend()
typedef long long LL;
typedef pair<LL,LL> P;
const LL mod=998244353;
const LL LINF=1LL<<62;




int main(){
    int n,t;cin >> n >> t;
    int ans=114155;
    for(int i=0;i<n;i++){
        int c,x;
        cin >> c >> x;
        if(x<=t) ans=min(ans,c);
    }
    if(ans==114155) puts("TLE");
    else cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256