akhauriyash/Code-Regression huggingface dataset:
import java.io.IOException;
import java.util.InputMismatchException;

public class Main {
	double area(double[][] p) {
		int n = p.length;
		double res = 0;

		for (int i = 0; i < n; i++) {
			double[] p1 = p[i];
			double[] p2 = p[(i + 1) % n];
			res += (p2[0] - p1[0]) * (p2[1] + p1[1]);
		}
		res /= 2;

		return res;
	}

	void run() {
		MyScanner sc = new MyScanner();

		int tc = 0;
		while (true) {
			int n = sc.nextInt();
			if (n == 0) {
				break;
			}
			double[][] p = new double[n][];
			for (int i = 0; i < n; i++) {
				p[i] = new double[]{sc.nextInt(), sc.nextInt()};
			}

			double sum = area(p);
			System.out.printf("%d %.1f\n", ++tc, sum);
		}
	}

	public static void main(String[] args) {
		new Main().run();
	}

	public void mapDebug(int[][] a) {
		System.out.println("--------map display---------");
		for (int i = 0; i < a.length; i++) {
			for (int j = 0; j < a[i].length; j++) {
				System.out.printf("%3d ", a[i][j]);
			}
			System.out.println();
		}
		System.out.println("----------------------------" + '\n');
	}

	class MyScanner {
		int read() {
			try {
				return System.in.read();
			} catch (IOException e) {
				throw new InputMismatchException();
			}
		}

		boolean isSpaceChar(int c) {
			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
		}

		boolean isEndline(int c) {
			return c == '\n' || c == '\r' || c == -1;
		}

		int nextInt() {
			return Integer.parseInt(next());
		}

		int[] nextIntArray(int n) {
			int[] array = new int[n];
			for (int i = 0; i < n; i++)
				array[i] = nextInt();
			return array;
		}

		long nextLong() {
			return Long.parseLong(next());
		}

		long[] nextLongArray(int n) {
			long[] array = new long[n];
			for (int i = 0; i < n; i++)
				array[i] = nextLong();
			return array;
		}

		double nextDouble() {
			return Double.parseDouble(next());
		}

		double[] nextDoubleArray(int n) {
			double[] array = new double[n];
			for (int i = 0; i < n; i++)
				array[i] = nextDouble();
			return array;
		}

		String next() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			StringBuilder res = new StringBuilder();
			do {
				res.appendCodePoint(c);
				c = read();
			} while (!isSpaceChar(c));
			return res.toString();
		}

		String[] nextStringArray(int n) {
			String[] array = new String[n];
			for (int i = 0; i < n; i++)
				array[i] = next();

			return array;
		}

		String nextLine() {
			int c = read();
			while (isEndline(c))
				c = read();
			StringBuilder res = new StringBuilder();
			do {
				res.appendCodePoint(c);
				c = read();
			} while (!isEndline(c));
			return res.toString();
		}
	}

}

Measured memory_bytes: 17276
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <functional>
#include <bitset>

using namespace std;
using lint = long long int;
using ll = long long int;
using graph = vector<vector<int>>;
using wgraph = vector<vector<pair<int, lint>>>;
const lint INF = 1001001001001001LL;
const lint MOD = 1000000007LL;
const double PI = 3.1415926535897932;
int di[] = {-1, 0, 1, 0, -1, 1, 1, -1};
int dj[] = {0, 1, 0, -1, 1, 1, -1, -1};

void yes(){ cout << "yes" << endl; }
void Yes(){ cout << "Yes" << endl; }
void YES(){ cout << "YES" << endl; }
void no(){ cout << "no" << endl; }
void No(){ cout << "No" << endl; }
void NO(){ cout << "NO" << endl; }
void possible(){ cout << "possible" << endl; }
void Possible(){ cout << "Possible" << endl; }
void POSSIBLE(){ cout << "POSSIBLE" << endl; }
void impossible(){ cout << "impossible" << endl; }
void Impossible(){ cout << "Impossible" << endl; }
void IMPOSSIBLE(){ cout << "IMPOSSIBLE" << endl; }

#define rep(i,n) for(int i = 0; i < (n); i++)
#define rrep(i,n) for(int i = 1; i <= (n); i++)
#define drep(i,n) for(int i = (n)-1; i >= 0; i--)
#define srep(i,s,t) for(int i = s; i < t; i++)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()



int main(){
  
  lint n, m; cin >> n >> m;
  vector<lint> s(n);
  rep(i, n) cin >> s[i];
  vector<lint> t(m);
  rep(i, m) cin >> t[i];
  vector<vector<lint>> dp(n + 1, vector<lint> (m + 1, 0));
  dp[0][0] = 1;
  for(int j = 1; j <= m; j++) dp[0][j] += 1;
  for(int i = 1; i <= n; i++) dp[i][0] += 1;
  for(int i = 1; i <= n; i++){
    for(int j = 1; j <= m; j++){
      if(s[i - 1] == t[j - 1]) dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
      else dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1];
      dp[i][j] = (dp[i][j] + MOD) % MOD;
    }
    
  }

  cout << dp[n][m] << endl;

  return 0;
}


Measured memory_bytes: 31616
MOD = 10 ** 9 + 7
s = int(input())
memo = [0]*(s+1)
memo[0] = 1
for i in range(s+1):
    for j in range(3,2001):
        try:
            memo[i+j] += memo[i] % MOD
        except:
            pass
print(memo[s]%MOD)

Measured memory_bytes: 9200
// ABC148C.cpp : このファイルには 'main' 関数が含まれています。プログラム実行の開始と終了がそこで行われます。
//

//#include "pch.h"
#include <iostream>
#include<algorithm>
using namespace std;
int main()
{
	long long A, B;
	cin >> A >> B;
	long long C, D;
	if (A >= B)
	{
		C = A;
		D = B;
	}
	else {
		C = B;
		D = A;
	}
	long long LC, LD,TMP;
	LC = C;
	LD = D;
	while ((LC%LD)!=0)
	{
		TMP = LC % LD;
		LC = LD;
		LD = TMP;
	}
	cout << C/LD*D << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define uint unsigned
#define pii pair<int,int>
#define pll pair<ll,ll>
#define IT iterator
#define PB push_back
#define fi first
#define se second
#define For(i,j,k) for (int i=(int)(j);i<=(int)(k);i++)
#define Rep(i,j,k) for (int i=(int)(j);i>=(int)(k);i--)
#define CLR(a,v) memset(a,v,sizeof(a));
#define CPY(a,b) memcpy(a,b,sizeof(a));
#define debug puts("wzpakking")
#define y1 ysghysgsygsh
using namespace std;
int gcd(int x,int y){
	return y?gcd(y,x%y):x;
}
ll F(int H,int W,int K){
	ll ans=0;
	int LIM=2*K+2*W;
	int LIM2=2*K+W+1200;
	For(k,1,W-1){
		For(d,0,H-2){
			int p1=1,p2=p1+d;
			if (p2<1) p1+=1-p2,p2=1;
			ll key=1ll*p1*(W-k)+1ll*p2*k;
			if (key>=2*K+3*W) break;
			key-=gcd(abs(d),W);
			ll b=(key>2*K?-1:max(0ll,(2*K-key)/W));
			ans+=min(H-1ll-max(p1,p2),b)+1; key+=(++b)*W;
			for (;key<=LIM&&b+p1<H&&b+p2<H;key+=W,++b){
				ll cv=key-gcd(k,b+p1)-gcd(W-k,b+p2);
				if (cv<=2*K-2) ++ans;
			}
		}
		Rep(d,-1,-H+2){
			int p1=1,p2=p1+d;
			if (p2<1) p1+=1-p2,p2=1;
			ll key=1ll*p1*(W-k)+1ll*p2*k;
			if (key>=2*K+3*W) break;
			key-=gcd(abs(d),W);
			ll b=(key>2*K?-1:max(0ll,(2*K-key)/W));
			ans+=min(H-1ll-max(p1,p2),b)+1; key+=(++b)*W;
			for (;key<=LIM&&b+p1<H&&b+p2<H;key+=W,++b){
				ll cv=key-gcd(k,b+p1)-gcd(W-k,b+p2);
				if (cv<=2*K-2) ++ans;
			}
		}
	}
	return ans*2;
}
int main(){
	int W,H,K;
	scanf("%d%d%d",&W,&H,&K);
	cout<<F(W,H,K)+F(H,W,K)<<endl;
	return 0;
}
/*
5000 5000 100000
*/

Measured memory_bytes: 3768
//Author: Fuadul Hasan(fuadul202@gmail.com)
//BSMRSTU,Gopalganj
#include<bits/stdc++.h>
using namespace std;int tc = 1;
#define happy ios::sync_with_stdio(false);
#define coding  cin.tie(0);
#define mp make_pair
#define ll long long
#define Pi atan(1)*4
#define pb  push_back
#define vpr vector<pr> 
#define pr pair<int, int> 
#define vi std::vector<int>
#define vll std::vector<ll>
#define YES printf("YES\n");
#define NO printf("NO\n");
#define Yes printf("Yes\n");
#define No printf("No\n");
#define all(n) n.begin(),n.end()
#define point(x) setprecision(x)
#define Test printf("Case %d: ",tc++);
#define Unique(c) (c).resize(unique(all(c))-(c).begin())
#define vout(v) for (auto z: v) cout << z << " "; cout << endl;

const int M = 1e9 + 7;
const ll  Inf = (ll)2e18 + 5;
const int N   = 2e5 + 5;

int solve() 
{
	//happy coding
	
	int n;
	cin>>n;
	for(int i = 128;i>=-128 ;i --){
		for(int j= -128;j<=128;j++){
			ll a = pow((ll)i,5);
			ll b = pow((ll)j,5);
			if(a-b==(ll)n){
				//cout<<a<<" "<<b<<endl;
				cout<<i<<" "<<j<<endl;
				return 0;
			}
		}
	}


	
	return 0;
}
int main(){
	int test = 1;
	//scanf("%d", &test);
	while (test--)solve();return 0;
}

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

notes = []
for _ in range(N):
    note = []
    for _ in range(int(input())):
        x, y = map(int, input().split())
        note.append((x-1, y))
    notes.append(note)

ans = 0
for state in range(1 << N):
    flag = True
    for i in range(N):
        if state >> i & 1:
            for x, y in notes[i]:
                flag &= (y == 1 and state >> x & 1) or (y == 0 and (state >> x & 1) == 0)

    if flag:
        ans = max(ans, sum(state >> i & 1 for i in range(N)))
print(ans)


Measured memory_bytes: 3064
#include <iostream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <climits>
#include <cfloat>
using namespace std;

int main()
{
    for(;;){
        int n;
        cin >> n;
        if(n == 0)
            return 0;

        vector<int> num(7, 0);
        for(int i=0; i<n; ++i){
            int a;
            cin >> a;
            a = min(a, 60);
            ++ num[a/10];
        }

        for(int i=0; i<7; ++i)
            cout << num[i] << endl;
    }
}

Measured memory_bytes: 908
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define P pair<ll,ll>
#define FOR(I,A,B) for(ll I = ll(A); I < ll(B); ++I)
#define FORR(I,A,B) for(ll I = ll((B)-1); I >= ll(A); --I)
#define TO(x,t,f) ((x)?(t):(f))
#define SORT(x) (sort(x.begin(),x.end())) // 0 2 2 3 4 5 8 9
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin()) //xi>=v  x is sorted
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin()) //xi>v  x is sorted
#define NUM(x,v) (POSU(x,v)-POSL(x,v))  //x is sorted
#define REV(x) (reverse(x.begin(),x.end())) //reverse
ll gcd(ll a,ll b){if(a<b)swap(a,b);if(a%b==0)return b;return gcd(b,a%b);}
ll lcm(ll a,ll b){ll c=gcd(a,b);return ((a/c)*(b/c)*c);}//saisyo kobaisu
#define NEXTP(x) next_permutation(x.begin(),x.end())
const ll INF=1e18+7;
const ll MOD=1e9+7;
#define out(a) cout<<fixed<<setprecision((a))

ll calc(ll a,ll b,ll p){//a^(b) mod p   
	if(b==0)return 1;
	ll y = calc(a,b/2,p);y=(y*y)%p;
	if(b & 1) y = (y * a) % p;
	return y;
}


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

	ll dp[13]={};
	dp[0] = 1;
	REV(s);
	ll ten = 0;
	for(char x:s){
		vector<ll> dp2(13,0);
		if(x=='?'){
			FOR(j,0,10){
				ll add = calc(10,ten,13)*j%13;
				FOR(i,0,13)(dp2[(add+i)%13] += dp[i])%=MOD;
			}
		}else{
			ll add = calc(10,ten,13)*(x-'0')%13;
			FOR(i,0,13)(dp2[(add+i)%13] += dp[i])%=MOD;
		}
		FOR(i,0,13) dp[i] = dp2[i];
		ten++;
		//FOR(i,0,13)cout<<dp[i]<<" ";
		//cout << endl;
	}
	cout << dp[5] << endl;
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin >> n;
    vector<int> x(n+1);
    for (int i = 0;i < n;i++) cin >> x[i];
    long long mini=1000000,sum;
    for (int i = 0;i <= 100;i++){
        //cout << x[i] << endl;
        sum = 0;
        for (int j = 0;j<n;j++){
            //cout << x[j]<< endl;
            sum += (x[j]-i)*(x[j]-i);

        }
        //cout << sum << endl;
        mini = min(sum,mini);
    }
    cout << mini << endl;

}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define repp(i,m,n) for(int (i)=(m);(i)<(n);(i)++)
#define repm(i,n) for(int (i)=(n);(i)>=0;(i)--)
#define INF (1ll<<60)
typedef long long lint;
const lint MOD =1000000007;

int main(){
    string s,a;
    lint n,ans=0;
    cin>>s;
    n=s.size()-1;
     bool x[n];
    rep(i,1<<n){     
        int v=0,c=0;
        rep(j,n){
           if(i&1<<j )x[j]=true;
           else x[j]=false;
            v++;
           if(x[j]==true){
               a=s.substr(c,v);
             // cout<<h[j]<<" ";
               c=j+1;
               v=0;
               ans+=stoi(a);
           }
        }
         if(x[n-1]==false){
              a=s.substr(c,v+1);
            // cout<<h[0]<<" ";
               ans+=stoll(a);
           }else {
              ans+=stoi(s.substr(n,1));
              //cout<<s.substr(n,1)<< " ";
           }
    }
    if(n==0)ans=stoi(s);
    cout<<ans;
}
 



  


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

using namespace std;

int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  string s;
  cin >> s;
  int n= s.length()-1;
  if (s[n]=='2' || s[n]=='4' || s[n]=='5' || s[n]=='7' || s[n]=='9')
    cout << "hon" << endl;
  else if (s[n]=='0' || s[n]=='1' || s[n]=='6' || s[n]=='8')
    cout << "pon" << endl;
  else if (s[n]=='3')
    cout << "bon" << endl;
  return 0;
}

Measured memory_bytes: 3648
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
typedef long long ll;
const int N = 1e5 + 5;
vector < int > DP(N, 2e9), v(N);
int main() {
    ios_base::sync_with_stdio(false);
    int n;
    cin >> n;
    vector < vector < int > > activities(n + 5, vector < int > (4));
    vector < vector < int > > DP(n + 5, vector < int > (4, -2e9));
    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= 3; j++) {
        cin >> activities[i][j];
      }
    }
    DP[1][1] = activities[1][1];
    DP[1][2] = activities[1][2];
    DP[1][3] = activities[1][3];
    for (int day = 2; day <= n; day++) {
      for (int i = 1; i <= 3; i++) {
        for (int j = 1; j <= 3; j++) {
          if (i == j) continue;
          DP[day][i] = max(DP[day][i], DP[day - 1][j] + activities[day][i]);
        }
      }
    }
    cout << max({DP[n][1], DP[n][2], DP[n][3]});
    return 0;
}

Measured memory_bytes: 12032
n = int(input())
a_li = list(map(int,input().split()))
low = a_li[0]
high = a_li[0]
old = a_li[0]
yen = 1000
for i in range(1,n):
    if old < a_li[i]:
        div, yen = divmod(yen, old)
        yen += div * a_li[i]
    old = a_li[i]
print(yen)

Measured memory_bytes: 9140
import sys

n= int(input())
a = list(map(int,input().split()))
ans = a[0]
ans_max = 10 ** 18

if 0 in a:
    print(0)
    sys.exit()

for i in range(1, n):
    ans *= a[i]
    if ans > ans_max:
        print("-1")
        sys.exit()

print(ans)

Measured memory_bytes: 21628
/*input
4
111 111 111 4
1000 1101 100 3
1010 001 101 4
010 101 000 4

*/
#include <bits/stdc++.h>
#include <stdlib.h>
#include <time.h> 

using namespace std;
long long mod=1e9+7;
typedef long long int lld;
#define rep(i,a,n) for(long long int i = (a); i <= (n); ++i)
#define repI(i,a,n) for(int i = (a); i <= (n); ++i)
#define repD(i,a,n) for(long long int i = (a); i >= (n); --i)
#define repDI(i,a,n) for(int i = (a); i >= (n); --i)
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define sc(a) scanf("%lld",&a)
#define sc2(a,b) scanf("%lld%lld",&a,&b)
#define sc3(a,b,c) scanf("%lld%lld%lld",&a,&b,&c)
#define scd(a) scanf("%d",&a)
#define scd2(a,b) scanf("%d%d",&a,&b)
#define scd3(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define scf(a) scanf("%lf",&a)
#define scf2(a,b) scanf("%lf%lf",&a,&b)
#define scf3(a,b,c) scanf("%lf%lf%lf",&a,&b,&c)
#define prL(a) printf("%lld\n",a)
#define prS(a) printf("%lld ",a)
#define prdL(a) printf("%d\n",a)
#define prdS(a) printf("%d ",a)
#define Error(x) cerr << #x << " = " << (x) <<endl;
#define Error2(a,b) cerr<<"( "<<#a<<" , "<<#b<<" ) = ( "<<(a)<<" , "<<(b)<<" )\n";
#define Error3(a,b,c) cerr<<"("<<#a<<" , "<<#b<<" , "<<#c<<" ) = ( "<<(a)<<" , "<<(b)<<" , "<<(c)<<")\n";
#define Error4(a,b,c,d) cerr<<"("<<#a<<" , "<<#b<<" , "<<#c<<" , "<<#d<<" ) = ( "<<(a)<<" , "<<(b)<<" , "<<(c)<<" , "<<(d)<<")\n";
#define errop(a) cerr<<#a<<" = ( "<<((a).x)<<" , "<<((a).y)<<" )\n";
#define popcount __builtin_popcountll
typedef pair<lld,lld> PA;
#define lim 1000010
#define lim2 3003
// inline lld sqr(lld x) { return x * x; }
// map<lld,lld>::iterator it;
// std::ios::sync_with_stdio(false);
// priority_queue<PA> Q;
// lld dp[1<<18];

lld A[lim],Fen[lim];

lld n,m,p,q;

lld P[lim];


lld powP(lld a,lld b){
    if(b==0) return 1%mod;
    lld k;
    k=powP(a,b/2);
    k=k*k%mod;
    if(b%2==0) return k;
    else return a*k%mod;
}


int main(){
    lld T,i,j,h,l,r,k,s,b,c,a,d,w,x,y,v,z,t,curr,prev,sum,ans,pos,val,countA,secondMin,indicator;
    string S;
    cin>>S;
    rep(i,0,3) cout<<S[i];
    printf(" ");
    rep(i,4,11) cout<<S[i];
    printf("\n");
    return 0;
}


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

char s[3][11];

int main(){
	scanf("%s %s %s", s[0], s[1], s[2]);
	if(s[0][strlen(s[0])-1] == s[1][0] && s[1][strlen(s[1])-1] == s[2][0])
		printf("YES\n");
	else printf("NO\n");
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6+10;
int n,a[303][303],d[303][303];
bool noroad[303][303];
int main()
{
	cin>>n;
	for(int i=0;i<n;++i)for(int j=0;j<n;++j)cin>>a[i][j],d[i][j]=a[i][j];
	for(int k=0;k<n;++k)for(int i=0;i<n;++i)for(int j=0;j<n;++j)
	{
		if(i == j || i == k || k == j)continue;
		d[i][j] = min(d[i][j], d[i][k]+d[k][j]);
		if(d[i][j] >= d[i][k] + d[k][j])
		{
			d[i][j] = d[i][k] + d[k][j];
			noroad[i][j] = noroad[j][i] = 1;
		}
	}
	for(int i=0;i<n;++i)for(int j=0;j<n;++j)
	{
		if(d[i][j] != a[i][j]) return !puts("-1");
	}
	ll sum = 0;
	for(int i=0;i<n;++i)for(int j=0;j<n;++j) if(!noroad[i][j])sum += d[i][j];
	cout << sum/2 << '\n';
}

Measured memory_bytes: 1024
# input()
# int(input())
# map(int, input().split())
# list(map(int, input().split()))
# list(map(int, list(input()))) # スペースがない数字リストを読み込み
import math
import fractions
import sys
import bisect
import heapq  # 優先度付きキュー(最小値取り出し)
import collections
from collections import Counter
from collections import deque
import pprint
import itertools

sr = lambda: input()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

"""nを素因数分解"""
"""2以上の整数n => [[素因数, 指数], ...]の2次元リスト"""


def factorization(n):
    arr = []
    temp = n
    if n == 1:
        return arr

    for i in range(2, int(-(-n ** 0.5 // 1)) + 1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append([i, cnt])

    if temp != 1:
        arr.append([temp, 1])

    if arr == []:
        arr.append([n, 1])

    return arr


# a^n
def power(a, n, mod):
    x = 1
    while n:
        if n & 1:
            x *= a % mod
        n >>= 1
        a *= a % mod
    return x % mod


# n*(n-1)*...*(l+1)*l
def kaijo(n, l, mod):
    if n == 0:
        return 1
    a = n
    tmp = n - 1
    while (tmp >= l):
        a = a * tmp % mod
        tmp -= 1
    return a

# Union Find
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

# 約数生成
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors

inf = 10 ** 18
mod = 10 ** 9 + 7

n,m = lr()
uf = UnionFind(n)
for i in range(m):
    a,b = lr()
    a-=1
    b-=1
    uf.union(a,b)
k = len(uf.roots())
print(k-1)


Measured memory_bytes: 83780
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

var sc, wr = bufio.NewScanner(os.Stdin), bufio.NewWriter(os.Stdout)

func scanString() string { sc.Scan(); return sc.Text() }
func scanInt() int { a,_ := strconv.Atoi(scanString()); return a }
func scanInt64() int64 { a,_ := strconv.ParseInt(scanString(),10,64); return a }
func scanFloat64() float64 { a,_ := strconv.ParseFloat(scanString(),64); return a }

func scanInts(n int) []int {
	res := make([]int, n); for i := 0; i < n; i++ { res[i] = scanInt() }; return res
}

func abs(a int) int { if a<0 { return -a }; return a }
func min(a,b int) int { if a<b { return a }; return b }
func max(a,b int) int { if a>b { return a }; return b }

//•*¨*•.¸¸♪Main•*¨*•.¸¸♪(　-ω-)ノ　(　・ω・)

func main() {
	sc.Split(bufio.ScanWords)
	sc.Buffer(make([]byte, 10000), 1000000)

	a := getPrimes(55555)

	n := scanInt()
	for i := 0; i < len(a); i++ {
		if a[i]%5 != 1 {
			continue
		}
		n--
		fmt.Printf("%d ", a[i])
		if n == 0 {
			break
		}
	}
	fmt.Println()
}

func getPrimes(n int) []int {
	res := make([]int, 0)
	f := make([]bool, n+1)
	var m int
	for m = 2; m*m <= n; m++ {
		if f[m] {
			continue
		}

		res = append(res, m)
		for i := 2; i*m < n+1; i++ {
			f[i*m] = true
		}
	}

	for i := m; i < n+1; i++ {
		if f[i] {
			continue
		}

		res = append(res, i)
	}

	return res
}


Measured memory_bytes: 896
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for (int i = 0; i < (int)n; i++)
#define ALL(a) (a).begin(), (a).end()
const ll mod = 1e9 + 7;

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

int main()
{
    int n, k, max = 0;
    cin >> n >> k;
    vector<int> a(n);
    rep(i, n)
    {
        cin >> a[i];
        if (max < a[i])
            max = a[i];
    }
    int g = a[0];
    rep(i, n - 1)
    {
        g = gcd(g, a[i + 1]);
    }
    if (max < k)
    {
        cout << "IMPOSSIBLE" << endl;
    }
    else
    {
        if (k % g == 0)
            cout << "POSSIBLE" << endl;
        else
            cout << "IMPOSSIBLE" << endl;
    }
    return 0;
}


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

#define debug(x) cout << #x << " = " << x << endl
#define fori(i, ini, lim) for(int i = int(ini); i < int(lim); i++)
#define ford(i, ini, lim) for(int i = int(ini); i >= int(lim); i--)

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;

const int MAX = 4e5 + 5;
const int ROOT = 2e5;
int arr[MAX], app[MAX], back[MAX];
int n;

ll roll(int limit) {
    memset(app, 0, sizeof app);
    ll total = 0, sum = 0, pref = 0;
    fori(i, 1, n + 1) {
        app[ROOT + sum]++;
        if(arr[i] > limit) {
            sum--;
            pref -= app[ROOT + sum];
        }
        else {
            pref += app[ROOT + sum];
            sum++;
        }
        total += pref;
    }
    return total;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin >> n;
    set<ii> all;
    fori(i, 1, n + 1) {
        cin >> arr[i];
        all.emplace(arr[i], i);
    }
    int k = 1;
    for(auto &each : all) {
        back[each.second] = each.first;
        arr[each.second] = k++;
    }
    ll total = (1LL * n * (n + 1)) / 2;
    ll median = total / 2 + 1;
    int left = 0, right = n - 1;
    int ans = -1;
    vector<ii> fodase(all.begin(), all.end());
    for(auto &each : fodase) {
        each.first = arr[each.second];
    }
    while(left <= right) {
        int mid = (left + right) / 2;
        if(roll(fodase[mid].first) >= median) {
            ans = fodase[mid].second;
            right = mid - 1;
        }
        else {
            left = mid + 1;
        }
    }
    cout << back[ans] << '\n';
    return 0;
}


Measured memory_bytes: 8704
#include<bits/stdc++.h>
using namespace std;
int main(){
    long long h,w,x,y;
    cin>>h>>w>>x>>y;
    cout<<h*w/2<<".";
    if(h*w%2)cout<<"500000000000"<<endl;
    else cout<<"000000000000"<<endl;
    if(x*2==h && y*2==w)cout<<"1"<<endl;
    else cout<<"0"<<endl;
    return 0;
}


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

int main() {
  int N;
  cin >> N;
  int M[N];
  int P[N];
  int ans = 0;

  for (int i=0; i<N; i++) {
    cin >> P[i];

    if (i==0) {
      M[i] = P[i];
    }
    else if (P[i] >= M[i-1]){
      M[i] = M[i-1];
    }
    else if (P[i] < M[i-1]) {
      M[i] = P[i];
    }
  }

  
  for (int i=0; i<N ; i++) {
    if (P[i] <= M[i]) ans++;
  }

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

Measured memory_bytes: 1792
import numpy as np
import copy

n,m = map(int,input().split())
max_l = 0
min_r = n

for i in range(m):
    l,r = map(int,input().split())
    max_l = max(max_l, l)
    min_r = min(min_r, r)

if max_l <= min_r:
    print(min_r - max_l + 1)
else:
    print(0)


Measured memory_bytes: 12488
class MyQueue(object):
    """
    My Queue class

    Attributes:
        queue: queue
        head
        tail
    """

    def __init__(self):
        """Constructor
        """
        self.length = 100010
        self.queue = []
        counter = 0
        while counter < self.length:
            self.queue.append(Process())
            counter += 1
        self.head = 0
        self.tail = 0

    def enqueue(self, name, time):
        """enqueue method

        Args:
            name: enqueued process name
            time: enqueued process time

        Returns:
            None
        """
        # if self.is_full():
        #     print("[ERROR] Queue Overflow")
        # else:
        self.queue[self.tail].name = name
        self.queue[self.tail].time = time
        self.tail = (self.tail + 1) % self.length

    def dequeue(self):
        """dequeue method

        Returns:
            None
        """
        # if self.is_empty():
        #     print("[ERROR] Queue Underflow")
        # else:
        self.queue[self.head].name = ""
        self.queue[self.head].time = 0
        self.head = (self.head + 1) % self.length

    def is_empty(self):
        """check queue is empty or not

        Returns:
            Bool
        """
        if self.head == self.tail:
            return True
        else:
            return False

    def is_full(self):
        """chech whether queue is full or not"""
        if self.tail - self.head >= len(self.queue):
            return True
        else:
            return False


class Process(object):
    """process class
    """

    def __init__(self, name="", time=0):
        """constructor
        Args:
            name: name
            time: time
        """
        self.name = name
        self.time = time

    def forward_time(self, time):
        """time forward method

        Args:
            time: forward time interval

        Returns:
            remain time

        """
        self.time -= time
        return self.time


def time_forward(my_queue, interval, current_time):
    """

    Args:
        my_queue: queue
        interval: time step interval
        current_time: current time
    """

    value = my_queue.queue[my_queue.head].forward_time(interval)
    if value <= 0:
        current_time += (interval + value)
        print my_queue.queue[my_queue.head].name, current_time
        my_queue.dequeue()

    elif value > 0:
        current_time += interval
        name, time = my_queue.queue[my_queue.head].name, \
                     my_queue.queue[my_queue.head].time
        my_queue.dequeue()
        my_queue.enqueue(name, time)

    return current_time


my_queue = MyQueue()
n, q = [int(x) for x in raw_input().split()]
counter = 0
while counter < n:
    name, time = raw_input().split()
    my_queue.enqueue(name, int(time))
    counter += 1

current_time = 0
while not my_queue.is_empty():
    current_time = time_forward(my_queue, q, current_time)

Measured memory_bytes: 44340
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define sz(x) (int)(x.size())
#define fi first
#define se second
#define pii pair<int,int>

signed main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n, k;
    cin >> n >> k;
    if(k > (n - 1) * (n - 2) / 2) {
        cout << "-1\n";
        return 0;
    }
    vector<pii> ans;
    int cnt = (n - 1) * (n - 2) / 2;
    for(int i = 2 ; i <= n; i++) {
        ans.push_back({1ll, i});
    }
    for(int i = 2; i <= n && cnt > k; i++) {
        for(int j = i + 1; j <= n && cnt > k; j++) {
            ans.push_back({i, j});
            cnt--;
        }
    }
    cout << sz(ans) << "\n";
    for(int i = 0; i < sz(ans); i++) {
        cout << ans[i].fi << " " << ans[i].se << "\n";
    }
}

Measured memory_bytes: 512
#include<bits/stdc++.h>
#include<iostream>
#include<string>
#include<cmath>
#include<cstdio>
#include<cctype>
#include<cstring>
#include<iomanip>
#include<cstdlib>
#include<ctime>
#include<set>
#include<map>
#include<utility>
#include<queue>
#include<vector>
#include<stack>
#include<sstream>
#include<algorithm>
#define forn(i,a,b)for(int i=(a),_b=(b);i<=_b;i++)
#define fore(i,b,a)for(int i=(b),_a=(a);i>=_a;i--)
#define rep(i,n)for(int i=0,_n=n;i<n;i++)
#define ll long long
#define pii pair<int,int>
#define vi vector<int>
#define vpii vector<pii>
#define m_p make_pair
#define re return
#define pb push_back
#define si set<int>
#define ld long double
#define X first
#define Y second
#define st string
#define ull unsigned long long
#define mod 1000000007
#define INF 1000000007
#define x1 XZVJDFADSPFOE
#define y1 GASDIJSLDAEJF
#define x2 DFDAJKVOHKWIW
#define y2 PSFSAODSXVNMQ
#define LLINF 0x3f3f3f3f3f3f3f3fLL
using namespace std;
inline void read(int &x)
{
	short negative=1;
    x=0;
    char c=getchar();
    while(c<'0' || c>'9')
    {
		if(c=='-')
			negative=-1;
		c=getchar();
	}
    while(c>='0' && c<='9')
        x=(x<<3)+(x<<1)+(c^48),c=getchar();
    x*=negative;
}
ll quickpower(ll n,ll k){
	ll ans=1;
	while(k){
		if(k%2){
			ans*=n;
			ans%=mod;
		}
		n*=n;
		n%=mod;
		k/=2;
	}
	return ans;
}
string int_to_string(int n)
{
	string s="";
	while(n)
	{
		int now=n%10;
		s+=now+'0';
		n/=10;
	}
	reverse(s.begin(),s.end());
	return s;
}
int string_to_int(string s)
{
	int n=0;
	rep(i,s.size())
	{
		n*=10;
		n+=s[i]-'0';
	}
	return n;
}
int a[200010],b[200010];
int main()
{
  
  int n;
  cin>>n;
  ll ans1=0,ans2=0;
  rep(i,n)
  {
  	cin>>a[i]>>b[i];
  }
  sort(a,a+n);
  sort(b,b+n);
  if(n%2==1)
  {
  	ans1=a[(n+1)/2-1];
  	ans2=b[(n+1)/2-1];
  }
  else
  {
  	ans1=a[n/2-1]+a[n/2];
  	ans2=b[n/2-1]+b[n/2];
  }
  cout<<(ans2-ans1+1)<<endl;
  return 0;
}


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

int main(){

  ll N,M;
  cin>>N>>M;

  Graph G(N);
  for (int i = 0; i < M; i++) {
        
    int a, b;
    cin >> a >> b;
    G[a-1].push_back(b-1);
    G[b-1].push_back(a-1);
    
  }

  vector<int> dist(N, -1);
  vector<int> trace(N, 0);
  queue<int> que;
  
  dist[0] = 0;
  trace[0]=1;
  que.push(0);

  while (!que.empty()) {
        
    int v = que.front();
    que.pop();
        
    for (int nv : G[v]) {
      
      if (dist[nv] != -1) continue; 
      dist[nv] = dist[v] + 1;
      trace[nv] = v;
      que.push(nv);
        
    }
    
  }

  
  cout<<"Yes"<<endl;
  
  for(int i=1;i<N;i++){cout<<trace[i]+1<<endl;}



}

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

#define sz(x) int(x.size())
#define pii pair<int, int>
#define Task "abc"
#define For(i, a, b) for(int i = (a), _b = (b); i <= b; ++i)
#define Debug(X) cout << #X << " = " << X << '\n'
#define All(x) (x).begin(), (x).end()
#define mp make_pair

typedef unsigned long long ull;
typedef long long ll;

const int maxn = 1e5 + 10;
const int inf = 0x3f3f3f3f;
const ll mod = 1e9 + 7;

int main(){
  ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);
//  freopen(Task".inp", "r", stdin);
//  freopen(Task".out", "w", stdout);
  ll n, a, b;
  cin >> n >> a >> b;
  cout << (n / (a + b)) * a + min( (n % (a + b) ), a);
}



Measured memory_bytes: 256
<?php
error_reporting(0);
$stdin = file_get_contents('php://stdin');
$line = explode("\n",$stdin);
$fi = 0;
$cnt = 0;
$list = array();
$key = new stdclass();
foreach($line as $l) {
  if (strlen($l)==0) continue;
  if ($fi == 0) {
    $a = explode(" ",$l);
    $key->A = $a;
    $fi++;
    continue;
  }
  if ($fi > 0) {
    $a = explode(" ",$l);
    $key->X[] = $a;
  }
}
$a = (int)($key->A[0]/15);
printf("%d\n",$key->A[0]*800-($a*200));


Measured memory_bytes: 3828
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n;
  cin>>n;
  vector<int> x(n);
  vector<int> y(n);
  for(int i=0;i<2*n;i++){
    cin>>x[i]>>y[i];
  }
  int sum=0;
  for(int i=0;i<n;i++){
    sum+=y[i]-x[i]+1;
  }
  cout<<sum<<endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n,h,maxh,r=1;
  cin>>n>>maxh;
  for(int i=1;i<n;++i){
    cin>>h;
    if(maxh<=h){
      r++;
      maxh=h;
    }
  }
  cout<<r;
  return 0;
}

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

using namespace std;

typedef long long int ll;
typedef pair<ll, ll> pll;

#define FOR(i, n, m) for(ll (i)=(m);(i)<(n);++(i))
#define REP(i, n) FOR(i,n,0)
#define OF64 std::setprecision(10)

const ll MOD = 1000000007;
const ll INF = (ll) 1e15;

ll A[200005];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    string S;
    cin >> S;
    memset(A, 0, sizeof(A));
    {
        ll s = 0;
        REP(i, S.length()) {
            if (S[i] == 'R') {
                s++;
                continue;
            }
            A[i - 1] += (s + 1) / 2;
            A[i] += s / 2;
            s = 0;
        }
    }
    {
        ll s = 0;
        for (ll i = S.length() - 1; i >= 0; --i) {
            if (S[i] == 'L') {
                s++;
                continue;
            }
            A[i] += s / 2;
            A[i + 1] += (s + 1) / 2;
            s = 0;
        }
    }

    REP(i, S.length()) {
        cout << A[i] << " ";
    }
    cout << endl;
    return 0;
}

Measured memory_bytes: 2256
import collections
N = int(input())
S = [input() for i in range(N)]
SI = [S[i][0] for i in range(N)]
cnt = collections.Counter(SI)
n = [cnt["M"],cnt["A"],cnt["R"],cnt["C"],cnt["H"]]
ans = 0
for i in range(3):
    for j in range(i+1,5):
        for k in range(j+1,5):
            ans += n[i]*n[j]*n[k]
print(ans)

Measured memory_bytes: 10880
use proconio::input;

fn main() {
    input! {
        _: usize,
        m: usize,
    };
    let mut ans = vec![];
    let es = m / 2; // 偶数個ズレた組の部屋の個数 (切り捨て)
    for i in 1..=es {
        ans.push((i, 2 * es + 1 - (i - 1)));
    }
    let os = (m + (2 - 1)) / 2; // 奇数個ズレた組の部屋の個数 (切り上げ)
    for i in 1..=os {
        let b = 2 * es + 1;
        ans.push((b + i, b + 2 * os - (i - 1)));
    }
    for (l, r) in ans {
        println!("{} {}", l, r);
    }
}


Measured memory_bytes: 3356
#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字くらい使った方がいいかも
    sizeは(int)とキャストしよう
    ごちゃごちゃ場合分けを考える前に全探索は考えましたか？
*/

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

    int ans = 0;
    for(int i=1; i<N-1; i++){
        if(p[i-1] < p[i] && p[i] < p[i+1]) ans++;
        else if(p[i+1] < p[i] && p[i] < p[i-1]) ans++;
    }

    cout << ans << endl;
}

Measured memory_bytes: 256
N = int(input())
B = list(map(int, input().split()))
A = [0] * N
for k in range(N):
    A[0] = B[0]
    if k == N-1:
        A[k] = B[k-1]
    else:
        A[k] = min([B[k-1], B[k]])
print(sum(A))

Measured memory_bytes: 3064
#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define llong long long
#define pb(a) push_back(a)
#define INF 999999999
using namespace std;
typedef pair<int, int> P;
typedef pair<llong, llong> LP;
typedef pair<int, P> PP;
typedef pair<llong, LP> LPP;

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

int main(){
  while(1){
    int n;
    scanf("%d", &n);
    if(n==0) return 0;
    vector<P> v(n);
    vector<vector<bool> > b(10010, vector<bool>(10010, 0));
    REP(i, n){
      scanf("%d%d", &v[i].first, &v[i].second);
      b[v[i].first][v[i].second]=1;
    }

    int ans=0;
    REP(i, n){
      FOR(j, i+1, n){
	int x=v[i].first, y=v[i].second;
	int x2=v[j].first, y2=v[j].second;
	int xd=x-x2;
	int yd=y-y2;

	if((x+yd>=0&&y-xd>=0&&x2+yd>=0&&y2-xd>=0)&&(b[x+yd][y-xd] && b[x2+yd][y2-xd])){
	  ans=max(ans, xd*xd+yd*yd);
	}
	if((x-yd>=0 && y+xd>=0 && x2-yd>=0 && y2+xd>=0)&&(b[x-yd][y+xd] && b[x2-yd][y2+xd])){
	  ans=max(ans, xd*xd+yd*yd);
	}
      }
    }
    
    printf("%d\n", ans);
  }
}

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

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    string s, t, ans = "";
    int n;
    cin >> n;
    cin >> s >> t;
    for (int i = 0; i < n; ++i) {
        ans += s[i];
        ans += t[i];
    }
    cout << ans << '\n';
    return 0;
}

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

using namespace std;
typedef long long ll;


template <typename T>
T bfs(vector<vector<T> > a, vector<bool> vis, T source)
{
    static_assert(is_same<T, int>::value || is_same<T, ll>::value, "this bfs function can only be in type \"int\" or \"long long int\"!\n");
    T element_num = 1;
    queue<T> q;
    q.emplace(source);
    vis.at(source) = true;
    while(!q.empty())
    {
        T top = q.front();
        q.pop();
        for(T i = 0; i < (T)a.at(top).size(); i++)
        {
            T tem = a.at(top).at(i);
            if(vis.at(tem)) continue;
            vis.at(tem) = true;
            q.emplace(tem);
            element_num++;
        }
    }
    return element_num;
}

template <typename T>
T dfs(vector<vector<T> > a, vector<bool> vis, T source)
{
    static_assert(is_same<T, int>::value || is_same<T, ll>::value, "this dfs function can only be in type \"int\" or \"long long int\"!\n");
    T element_num = 1;
    stack<T> s;
    s.push(source);
    vis.at(source) = true;
    while(!s.empty())
    {
        T top = s.top();
        s.pop();
        for(T i = 0; i < (T)a.at(top).size(); i++)
        {
            T tem = a.at(top).at(i);
            if(vis.at(tem)) continue;
            vis.at(tem) = true;
            s.emplace(top);
            s.emplace(tem);
            element_num++;
            break;
        }
    }
    return element_num;
}

template <typename T>
vector<vector<T> > input_graph(T array_num, T edge_num)
{
    static_assert(is_same<T, int>::value || is_same<T, ll>::value, "this input_graph function can only be in type \"int\" or \"long long int\"!\n");
    vector<vector<T> > a(array_num, vector<T>());
    for(T i = 0; i < edge_num; i++)
    {
        T d1, d2;
        cin >> d1 >> d2;
        a.at(d1-1).emplace_back(d2-1);
        a.at(d2-1).emplace_back(d1-1);
    }

    return a;
}

template <typename T>
vector<T> input_vector(T array_num)
{
    static_assert(is_same<T, int>::value || is_same<T, ll>::value, "this input_vector function can only be in type \"int\" or \"long long int\"!\n");
    vector<T> a(array_num, 0);
    for(T i = 0; i < array_num; i++)
    {
        cin >> a.at(i);
    }

    return a;
}

ll inf = 1e9+7;


int main() {
    int n, k, d;
    cin >> n >> k;
    string s;
    cin >> s;
    vector<int> a(n,0);
    bool is_a = false;
    for(int i = 0; i < s.size(); i++)
    {
        if(is_a)
        {
            if(s[i] == 'C')
            {
                a.at(i-1)++;
            }
            is_a = false;
        }
        if(s[i] == 'A')
        {
            is_a = true;
        }
    }
    for(int i = 1; i < n; i++)
    {
        a.at(i) += a.at(i-1);
    }
    for(int i = 0; i < k; i++)
    {
        int d1, d2;
        cin >> d1 >> d2;
        if(d1 < 2)
        {
            cout << a.at(d2-2) << endl;
        }
        else
        {
            cout << (a.at(d2-2) - a.at(d1-2)) << endl;
        }
    }

    return 0;
}


Measured memory_bytes: 1408
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
long long a[100010];
long long fact[200020], finv[200020], inv[200020];
void facti() {
	fact[0] = fact[1] = 1;
	finv[0] = finv[1] = 1;
	inv[1] = 1;
	for (int i = 2; i < 200020; i++) {
		fact[i] = fact[i - 1] * i % 1000000007;
		inv[i] = 1000000007 - inv[1000000007 % i] * (1000000007 / i) % 1000000007;
		finv[i] = finv[i - 1] * inv[i] % 1000000007;
	}
}
long long ncr(int n, int k) {
	if (n < k) return 0;
	if (n < 0 || k < 0) return 0;
	return fact[n] * (finv[k] * finv[n - k] % 1000000007) % 1000000007;
}
int main() {
	long long n, k;
	cin >> n >> k;
	for (long long i = 0; i < n; i++) {
		cin >> a[i];
	}
	sort(a, a + n);
	facti();
	long long ans = 0;
	for (long long i = 0; i < n; i++) {
		ans = (ans - ncr(n - i - 1, k - 1) * a[i]) % 1000000007;
		ans = (ans + ncr(i, k - 1) * a[i]) % 1000000007;
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 5760
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<stack>
#include<queue>
#include<cstring>
#include<vector>
#include<map>
using namespace std;
typedef long long ll;
#define N 301002
struct quji{int l,r,mid,mx,laz;}c[N<<2];
struct node{int x,y;}a[N];
struct qj{int st,va;}s1[N],s2[N];
int w,h,n,ans,tot1,tot2;
bool cmp(node n1,node n2){return n1.y<n2.y;}
void bt(int ind,int l,int r)
{
	c[ind].l=l;c[ind].r=r;c[ind].mid=(l+r)>>1;c[ind].laz=0;
	if(l==r){c[ind].mx=-a[l].y;return;}
	bt(ind<<1,l,c[ind].mid);bt(ind<<1|1,c[ind].mid+1,r);
	c[ind].mx=max(c[ind<<1].mx,c[ind<<1|1].mx);
}
void pushdown(int ind)
{
	c[ind<<1].laz+=c[ind].laz;
	c[ind<<1].mx+=c[ind].laz;
	c[ind<<1|1].laz+=c[ind].laz;
	c[ind<<1|1].mx+=c[ind].laz;
	c[ind].laz=0;
}
void chng(int ind,int l,int r,int x)
{if(l>r)return;if(l==0)return;
	if(l<=c[ind].l&&c[ind].r<=r)
	{
		c[ind].laz+=x;c[ind].mx+=x;
		return;
	}
	pushdown(ind);
	if(l<=c[ind].mid)chng(ind<<1,l,r,x);
	if(r>c[ind].mid)chng(ind<<1|1,l,r,x);
	c[ind].mx=max(c[ind<<1].mx,c[ind<<1|1].mx);
}
int ask(int ind,int l,int r)
{if(l>r)return -1e9;
	if(l<=c[ind].l&&c[ind].r<=r)return c[ind].mx;
	int ret=-1e9;pushdown(ind);
	if(l<=c[ind].mid)ret=max(ret,ask(ind<<1,l,r));
	if(r>c[ind].mid)ret=max(ret,ask(ind<<1|1,l,r));
	return ret;
}
void solve()
{
	sort(a+1,a+1+n,cmp);
	int ls=0,rs=w;
	for(int i=n;i;i--)
	{
		ans=max(ans,h-a[i].y+rs-ls);
		if(a[i].x<=w/2)ls=max(ls,a[i].x);
		else rs=min(rs,a[i].x);
	}ans=max(ans,h+rs-ls);
	tot1=tot2=0;
	bt(1,1,n);
	ls=0,rs=w;
	bool f1=false,f2=false;
	for(int i=1;i<=n;i++)
	{
		/*ls=0,rs=w;
		for(int j=i-1;j;j--)
		{
			ans=max(ans,a[i].y-a[j].y+rs-ls);
			if(a[j].x<=w/2)ls=max(ls,a[j].x);
			else rs=min(rs,a[j].x);
		}
		ans=max(ans,a[i].y+rs-ls);*/
		ans=max(ans,rs-ls+a[i].y);
		int tv=ask(1,1,i-1);
		ans=max(ans,tv+a[i].y);
		chng(1,i,i,w);
		if(a[i].x<=w/2)
		{
			ls=max(ls,a[i].x);
			int la=i-1;
			while(tot1&&a[i].x>s1[tot1].va)
			{
				chng(1,s1[tot1].st,la,s1[tot1].va-a[i].x);
				la=s1[tot1].st-1;tot1--;
			}
			if(la<i-1)s1[++tot1].st=la+1,s1[tot1].va=a[i].x;
		}
		else
		{
			rs=min(rs,a[i].x);
			int la=i-1;
			while(tot2&&a[i].x<s2[tot2].va)
			{
				chng(1,s2[tot2].st,la,a[i].x-s2[tot2].va);
				la=s2[tot2].st-1;tot2--;
			}
			if(la<i-1)s2[++tot2].st=la+1,s2[tot2].va=a[i].x;
		}
		s1[++tot1].st=i,s1[tot1].va=0;
		s2[++tot2].st=i,s2[tot2].va=w;
	}
	//puts("fin");
	//printf("%d\n",ans);
}
int main()
{
	scanf("%d%d%d",&w,&h,&n);
	if(!n){printf("%d\n",2*(w+h));return 0;}
	for(int i=1;i<=n;i++)scanf("%d%d",&a[i].x,&a[i].y);
	solve();
	for(int i=1;i<=n;i++)swap(a[i].x,a[i].y);
	swap(w,h);solve();
	printf("%d\n",ans*2);return 0;
}
/*
10 10 4
1 6
4 1
6 9
9 4
*/

Measured memory_bytes: 27776
import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    new Main().exec();
  }

  void exec() {
    Scanner sc = new Scanner(System.in);
    int n = readInt(sc);
    int x = readInt(sc);
    int xs[] = new int[n];
    for (int i = 0; i < n; i++) {
      xs[i] = Math.abs(x - readInt(sc));
    }

    int beforeG = x;
    for (int i = 0; i < n; i++) {
      if (n == 1)
        beforeG = xs[i];
      else if (i == 0)
        beforeG = gcb(xs[i], xs[i + 1]);
      else
        beforeG = gcb(beforeG, xs[i]);
    }
    System.out.println(beforeG);
  }

  int gcb(int a, int b) {
    if (b == 0) {
      return a;
    } else {
      return gcb(b, a % b);
    }
  }

  int readInt(Scanner sc) {
    return sc.nextInt();
  }

  String readString(Scanner sc) {
    return sc.next();
  }

}

Measured memory_bytes: 50840
def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a%b)

def main():
    N, K = map(int, input().split())
    A = tuple(map(int, input().split()))
    MAX_VAL = max(A)

    A_GCD = A[0]

    for a in A:
        A_GCD = gcd(A_GCD, a)
    
    if K <= MAX_VAL and K % A_GCD == 0:
        print("POSSIBLE")
    else:
        print("IMPOSSIBLE")

if __name__ == "__main__":
    main()

Measured memory_bytes: 19892
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for (int64_t i = (a); i < (b); i++)
#define REP(i,n) rep(i,0,n)
double dp[3000][3000];
void solve() 
{
    int n;cin>>n;
    dp[0][0]=1;
    double p;
    REP(i,n){//i枚目　ｊ枚は裏
        cin>>p;
        REP(j,i+1){
            dp[i+1][j]+=dp[i][j]*p;//表
            dp[i+1][j+1]+=dp[i][j]*(1-p);//裏　j+1
        }
    }
    p=0;
    REP(i,(n+1)/2)p+=dp[n][i];//裏<表
    //REP(i,n+1){REP(j,i+1)cout<<dp[i][j]<<" ";cout<<endl;}
    cout<<fixed<<setprecision(10)<<p<<endl;
}
int main()
{
    cin.tie(0);
	ios::sync_with_stdio(false);
    solve();
    return 0;
}


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

const int mod = 1000000007;

int main(){
    int n;
    cin >> n;
    ve<ve<int>> a(n,ve<int>(n));
    rep(i,n)rep(j,n) cin >> a[i][j];
    ve<ve<ll>> dp(n+1,ve<ll>(1<<n));
    dp[0][0] = 1;
    for(int i=0;i<n;i++){
        rep(k,1<<n){
            if(dp[i][k]==0)continue;
            rep(j,n){
                if(a[i][j]==0) continue;
                int mask = 1<<j;
                if(k&mask)continue;
                (dp[i+1][k|mask] += dp[i][k])%=mod;
            }
        }
    }
    cout << dp[n][(1<<n)-1] << endl;
    return 0;
}


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

typedef long long int ll;
typedef long double ld;
#define endl "\n"
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)

ll const inf = 1e18;
ll const maxn = 1e6+5;
ll const mod = 1e9+7;

// code begins here

int main(){
    fast;
    
    ll a,b,c,k;
    cin>>a>>b>>c>>k;
    
    ll ans = min(a,k);
    k -= ans;
    
    ll temp = max(0LL,min(b,k));
    k -= temp;
    
    temp = max(0LL,min(c,k));
    ans -= temp;
    
    cout<<ans<<endl;
    
    return 0;
}

Measured memory_bytes: 3612
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
/*
5 1
1 0 0 1 0

1 1 1 1 1
1 2 2 1 2

1 0 0 1 0
0 1 1 0 1
1 2 2 1 2

1 1 1 1 1
2 2 3 3 2

1 0 0 1 0
1 2 2 1 2
3 3 4 4 3
4 5 5 5 4
5 5 5 5 5
5 5 5 5 5

0 0 0 0 0
1 1 1 1 1
2 3 3 3 2
4 4 5 4 4

    0
    1
  1 1 1
1 2 3 2 1
3 4 3 4 3

0
1
1 1
2 2 1
2 3 3 2
3 4 4 3 3 2

*/
int main(){
  ll N,K; cin>>N>>K;
  vector<ll>A(N,0);
  for(ll i=0; i<N; i++)cin>>A[i];
  for(ll i=0; i<K; i++){
    vector<ll>B(N,0);
    ll cnt=0;
    for(ll j=0; j<N; j++){
      ll R=min(N-1,j+A[j]);
      ll L=max(0LL,j-A[j]);
      B[L]++;
      if(R+1>=N) continue;
      B[R+1]--;
      cnt++;
    }
    for(ll j=1; j<N; j++) B[j]+=B[j-1];
    A=B;
    if(cnt==0 && B[0]==N || i==K-1){
      for(ll j=0; j<N; j++){
        cout<<B[j];
        if(j<N-1) cout<<" ";
        else cout<<endl;
      }
      return 0;
    }
  }
}

Measured memory_bytes: 6424