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

public class Main {
	public static void main(String[] args) {
		FastScanner sc = new FastScanner();
		int N = sc.nextInt();
		boolean[] a = new boolean[N + 1];
		int result = 0;
		
		int beforeMenu = N;
		for (int i = 1; i <= N; ++i) {
			int temp = sc.nextInt();
			a[beforeMenu] = beforeMenu + 1 == temp;
			beforeMenu = temp;
		}
		
		for (int i = 0; i < N; ++i) {
			result += sc.nextInt();
		}
		
		for (int i = 1; i < N; ++i) {
			int temp = sc.nextInt();
			if (a[i]) result += temp;
		}
		
		System.out.println(result);
		
	}

}

class FastScanner {
    private final InputStream in = System.in;
    private final byte[] buffer = new byte[1024];
    private int ptr = 0;
    private int buflen = 0;
    private boolean hasNextByte() {
        if (ptr < buflen) {
            return true;
        }else{
            ptr = 0;
            try {
                buflen = in.read(buffer);
            } catch (IOException e) {
                e.printStackTrace();
            }
            if (buflen <= 0) {
                return false;
            }
        }
        return true;
    }
    private int readByte() { if (hasNextByte()) return buffer[ptr++]; else return -1;}
    private static boolean isPrintableChar(int c) { return 33 <= c && c <= 126;}
    public boolean hasNext() { while(hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++; return hasNextByte();}
    public String next() {
        if (!hasNext()) throw new NoSuchElementException();
        StringBuilder sb = new StringBuilder();
        int b = readByte();
        while(isPrintableChar(b)) {
            sb.appendCodePoint(b);
            b = readByte();
        }
        return sb.toString();
    }
    public long nextLong() {
        if (!hasNext()) throw new NoSuchElementException();
        long n = 0;
        boolean minus = false;
        int b = readByte();
        if (b == '-') {
            minus = true;
            b = readByte();
        }
        if (b < '0' || '9' < b) {
            throw new NumberFormatException();
        }
        while(true){
            if ('0' <= b && b <= '9') {
                n *= 10;
                n += b - '0';
            }else if(b == -1 || !isPrintableChar(b)){
                return minus ? -n : n;
            }else{
                throw new NumberFormatException();
            }
            b = readByte();
        }
    }
    public int nextInt() {
        long nl = nextLong();
        if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE) throw new NumberFormatException();
        return (int) nl;
    }
    public double nextDouble() { return Double.parseDouble(next());}
}


Measured memory_bytes: 23124
import java.util.*;
public class Main {
	public static void main(String[] args) {
		Scanner s = new Scanner(System.in);
			int mounth = s.nextInt();
			int day = s.nextInt();
			if(mounth>=1&&mounth<=12&&day>=1&&day<=31) {
				if(mounth>day) {
					System.out.println(mounth-1);
				}else {
					System.out.println(mounth);
				}
			}
}
}

Measured memory_bytes: 23764
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define MOD 1000000007
#define INF (1e9)
#define PI (acos(-1))
#define print(x) cout << x << endl
#define yes cout << "Yes" << endl
#define YES cout << "YES" << endl
#define no cout << "No" << endl
#define NO cout << "NO" << endl


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

    double res = 0;
    for (int i=1; i<=N; ++i) {
        for (int j=0; j<=20; ++j) {
            int temp = i * int(pow(2, j));
            if (temp >= K) {
                res += 1.0 / double(N * pow(2, j));
                break;
            }
        }
    }
    print(setprecision(10) << res);
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <set>
#include <list>
#include <map>
#include <string>
#include <algorithm>

void b(std::istream& in)
{
    int N;
    in >> N;

    int countAC = 0;
    int countWA = 0;
    int countTLE = 0;
    int countRE = 0;
    for (int i = 0; i < N; ++i)
    {
        std::string result;
        in >> result;
        if (result == "AC")
        {
            ++countAC;
        }
        else if (result == "WA")
        {
            ++countWA;
        }
        else if (result == "TLE")
        {
            ++countTLE;
        }
        else if (result == "RE")
        {
            ++countRE;
        }
        else
        {
            //assert(false);
        }
    }

    std::cout << "AC x " << countAC << std::endl;
    std::cout << "WA x " << countWA << std::endl;
    std::cout << "TLE x " << countTLE << std::endl;
    std::cout << "RE x " << countRE;
}

int main(int, char* [])
{
    b(std::cin);
    return 0;
}



Measured memory_bytes: 3248
function main(input){
  input = input.split("\n");
  var a = parseInt(input[0].split(" ")[0]);
  var b = parseInt(input[0].split(" ")[1]);

  if (a > 12) {
    console.log(b);
  } else if (a <= 12 && a >= 6) {
    console.log(b/2);
  }else {
    console.log(0);
  }
}

main(require('fs').readFileSync('/dev/stdin', 'utf8'));

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

int main(){
  int a,b,c;
  cin >> a >> b >> c;
  if((a==5)&&(b==5)&&(c==7))
    cout << "YES" << endl;
  else if((a==5)&&(b==7)&&(c==5))
    cout << "YES" << endl;
  else if((a==7)&&(b==5)&&(c==5))
    cout << "YES" << endl;
  else
    cout << "NO" << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <cstdio>
#include <string>
#include <stack>
#include <algorithm>
#include <iomanip>
#include <math.h>
#include <numeric>
using namespace std;

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

    int ans  = 0;

    for(int i = 0; i < S.size() ; i++){
        if(S.at(i) == '+'){
            ans = ans + 1;
        }else{
            ans = ans - 1;
        }
    }

    cout << ans << endl;
}

Measured memory_bytes: 256
#include<stdio.h>

int main(){
  int y,x,d;
  
  scanf("%d%d",&x,&y);
  
  
  while((d=x%y) !=0){
    x=y;
    y=d;
  }
  
  
  printf("%d\n",y);
  
  return 0;
}

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

int main(){
  
  string N;
  int num = 0;
  
  cin >> N;
  
  for(int i = 0;i < 4;++i){
    if(N[i] == '2'){
      num++;
    }
  }
  
  cout << num << endl;
 
}


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

#define REP(i,num) for(int i=0;i<(num);++i)
#define ALL(c) c.begin(),c.end()
#define PRINTALL(c) for(auto& x:c){cout<<x<<' ';}cout<<endl;
#define PAIRCOMP(c,comp) [](const pair<ll,ll>& lhs,const pair<ll,ll>& rhs){return lhs.c comp rhs.c;}

using namespace std;
using ll = long long;

constexpr ll atcoder_mod = 1e9+7;

template<typename T=int>
T in(){T x; cin >> x; return (x);}
template<typename T=int,typename C=vector<T>>
C vecin(int N){C x(N);REP(i,N){x[i]=in<T>();}return move(x);}

void vout(){cout << endl;}
template<typename Head,typename... Tail>
void vout(Head&& h,Tail&&... t){cout << ' ' << h;vout(forward<Tail>(t)...);}
void out(){cout << endl;}
template<typename Head,typename... Tail>
void out(Head&& h,Tail&&... t){cout << h;vout(forward<Tail>(t)...);}

string replace_string(string O,string S,string Q,string R){
	string::size_type pos(O.find(Q));

	while(pos!=string::npos){
		S.replace(pos,Q.length(),R);
		pos = O.find(Q,pos+R.length());
	}

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

	char str[1010];
	cin.getline(str,sizeof(str));
	string O(str),S(str);
	S = replace_string(O,S,"apple","peach");
	S = replace_string(O,S,"peach","apple");
	out(S);
	return 0;
}


Measured memory_bytes: 3004
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef long long ll;
const int MOD = (int)1e9 + 7;
const int INF = 1LL << 60;
#define REP(i, n) for (int i = 0; i < (n); i++)
#define ALL(obj) (obj).begin(), (obj).end() //コンテナじゃないと使えない!!
#define debug(x) cerr << #x << ": " << x << "\n";

signed main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    int N;
    cin >> N;
    vector<int> A(N);
    REP(i,N){
        cin >> A[i];
    }
    sort(A.begin(),A.end());
    int ans=0;
    REP(i,N){
        if (i&1){
            ans += A[i];
        }else{
            ans -= A[i];
        }
    }
    cout << abs(ans) << endl;
}


Measured memory_bytes: 256
/*
????°??????????????£? = ??????????????????
while(?????? == false){
    ????°??????????????£?++;
}

?????????:1 2 3 4 5 6 
???  ???:X X X O O O
X???1???????????????O???????°??????????

????°????O??¨?????§???X?????????????????????
??????????????????????????°??????
*/
//--- --- --- debug function --- --- ---
// #define DEBUG // switch this macro
#ifdef DEBUG
#include <cstdio>
typedef int (*printf_t)(const char* format, ...);
printf_t printfd = std::printf;
#else
int printfd(const char* format, ...){return 0;}
#endif
//--- --- --- debug function --- --- ---
#include <cassert>
#include <cmath>
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>

bool Check(const std::vector<int> Wi, int k, int P)
{
    if(*std::max_element(Wi.begin(), Wi.end()) > P) return false;
    int p = 0;
    --k;
    for(int i = 0; i < Wi.size(); ++i){
        if(P - p >= Wi[i]){
            p += Wi[i];
        }else{
            p = Wi[i];
            --k;
        }
    }
    return k >= 0;
}
int main()
{
    int n,k;
    std::cin >> n >> k;
    std::vector<int> Wi(n);
    for(int i = 0; i < n; ++i){
        std::cin >> Wi[i];
    }

    int MaxBad  = std::accumulate(Wi.begin(), Wi.end(), 0) / k - 1;
    int MinGood = std::ceil(((double)n / k)) * *std::max_element(Wi.begin(), Wi.end());
    int P = (MaxBad + MinGood) / 2;
    printfd("Max:%d, Min:%d, P:%d\n", MaxBad, MinGood, P);
    while(MaxBad + 1 != MinGood){
        if(Check(Wi, k, P)){
            MinGood = P;
        }else{
            MaxBad = P;
        }
        P = (MaxBad + MinGood) / 2;
        printfd("Max:%d, Min:%d, P:%d\n", MaxBad, MinGood, P);
    }
    std::cout << MinGood << std::endl;
    return 0;
}

Measured memory_bytes: 1796
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define pb push_back
#define mp make_pair
#define Would
#define you
#define please


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


	int N, A, B;
	cin >> N >> A >> B;
	int P[3] = {};
	rep(i, N) {
		int p;
		cin >> p;
		if (p <= A) P[0]++;
		else if (p <= B) P[1]++;
		else P[2]++;
	}

	co(*min_element(P, P + 3));

	Would you please return 0;
}

Measured memory_bytes: 256
/* AUTHOR :  SHIVANK JAIN */

#include<bits/stdc++.h>
#define fast ios_base::sync_with_stdio(false)
#define itt cin.tie(0)
#define now cout.tie(0)

using namespace std;

#define ll long long
#define li long int

#define pb push_back
#define rep(i,a,n) for(int i=a;i<n;i++)
#define reprev(i,n,a) for(int i=n;i>=a;i--)
#define endl "\n"

#define vi vector<int>
#define vll vector<ll>
#define vpi vector< pair<int , int> >
#define mapi map<int , int>
#define mapll map<ll ,ll >
#define seti set<int> 

#define fr first
#define se second
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define mp make_pair
#define sort(v) sort(v.begin() , v.end())

#define BIG 1000000007
int gcd(int a, int b) 
{ // builtin function __gcd(a,b)
    if (a == 0) 
        return b; 
    return gcd(b % a, a); 
} 
int main(){

     fast;itt;now;
 

   int n ;  cin>>n;
   ll sum = 0;
   rep(i,1,n+1){
   	rep(j,1,n+1){
   		rep(k,1,n+1)
   		 sum += __gcd(i,__gcd(j,k));
	   }
   }

  cout<<sum<<endl;
}

Measured memory_bytes: 3652
#include <iostream>

using namespace std;

int main() {
  int K, A, B; cin >> K >> A >> B;
  if(A % K == 0 || B % K == 0 || (B / K) - (A / K) >= 1) cout << "OK" << endl;
  else cout << "NG" << endl;
  return 0;
}

Measured memory_bytes: 3560
n, k = map(int, input().split())
r,s,p = map(int, input().split())
d = {"r":p, "s":r, "p":s}
t = input()
mode = [True]*n
score = 0
for i in range(n):
  score += d[t[i]]
  if i >= k and mode[i-k] and t[i] == t[i-k]:
    score -= d[t[i]]
    mode[i] = False
print(score)
    

Measured memory_bytes: 40560
from bisect import bisect_right, bisect_left

N = int(input())
A = [int(zz) for zz in input().split()]

A.sort()
B = set(A)

ans = []

for i in B:
    p = bisect_right(A, i) - bisect_left(A, i)
    if 4 > p >= 2:
        ans.append(i)
    elif p >= 4:
        ans.append(i)
        ans.append(i)
        

ans.sort(reverse=True)

if len(ans) >= 2:
    print(ans[0] * ans[1])
else:
    print(0)


Measured memory_bytes: 14484
using System;
using System.Collections.Generic;
using static System.Math;
using System.Linq;
 
class DandA {
    static void Main(string[] args) {
        string s = ReadLineStr();
        int length = s.Length;
        int cnt = (length / 2) + (length % 2);
        int rtn = 0;
        for (int i = 0; i < cnt; i++) {
            if (s.Substring(i, 1) != s.Substring(length - (i + 1), 1)) {
                rtn++;
            }
        }
        Console.WriteLine(rtn);
    }
  
    static private string ReadLineStr() {return Console.ReadLine();}
    static private int ReadLineInt() {return int.Parse(Console.ReadLine());}
    static private string[] ReadLineStrArray() {return Console.ReadLine().Trim().Split();}
    static private int[] ReadLineIntArray() {return Console.ReadLine().Trim().Split().Select(a => int.Parse(a)).ToArray();}
    static private long[] ReadLineLongArray() {return Console.ReadLine().Trim().Split().Select(a => long.Parse(a)).ToArray();}
    static private string[][] ReadMLineStrArray(int arg) { return new int[arg].Select(_ => Console.ReadLine().Split()).ToArray();}
    static private int[][] ReadMLineIntArray(int arg) { return new int[arg].Select(_ => Console.ReadLine().Split().Select(int.Parse).ToArray()).ToArray();}

    static private bool IsPrime(int num) {
        if (num < 2) return false;
        if (num == 2) return true;
        else if (num % 2 == 0) return false;
        double sqrtNum = Math.Sqrt(num);
        for (int i = 3; i <= sqrtNum; i += 2) {
            if (num % i == 0) return false;
        }
        return true;
    }
}

Measured memory_bytes: 13140
// Being an artist , being me. Thats best excuse of me for being Crazy.
// 1 cheez uthao and finish that... 
// dp first... aaw se 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
	ll n, W;
	cin >> n >> W ;
	ll dp[n + 1][W+ 1] ;
	memset(dp, 0, sizeof(dp)) ;
	ll wt[n], val[n]; 
	for(ll i = 0; i < n; i ++ )
		cin >> wt[i] >> val[i] ;
	for(ll i = 1; i <= n; ++i ) { // log
		for(ll w = 1; w <= W; ++w ) { // wt kitta chahiye
				if( wt[i - 1] > w ) dp[i][w] = dp[i - 1][w];
				else dp[i][w] = max( dp[i - 1][w], dp[i - 1][ w - wt[i - 1]] + val[i - 1] );
		}
	}
	cout << dp[n][W] ;
}

Measured memory_bytes: 79104
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
long long D[101000];
int ck[101000], n, m;
vector<int>E[101000], L[101000];
void DFS(int a, long long d) {
	int i;
	ck[a] = 1;
	D[a] = d;
	for (i = 0; i < E[a].size(); i++) {
		if (!ck[E[a][i]])DFS(E[a][i], D[a] + L[a][i]);
	}
}
int main() {
	int i, a, b, c;
	scanf("%d%d", &n, &m);
	for (i = 1; i <= m; i++) {
		scanf("%d%d%d", &a, &b, &c);
		E[a].push_back(b);
		L[a].push_back(c);
		E[b].push_back(a);
		L[b].push_back(-c);
	}
	for (i = 1; i <= n; i++) {
		if (!ck[i]) {
			DFS(i, 0);
		}
	}
	for (i = 1; i <= n; i++)for (int j = 0; j < E[i].size(); j++) {
		if (D[E[i][j]] != D[i] + L[i][j]) {
			printf("No\n");
			return 0;
		}
	}
	printf("Yes\n");
}

Measured memory_bytes: 17280
N, M, X = map(int, input().split())
l = list(map(int, input().split()))

G0, GN = 0, 0

for i in range(X):
  if i in l:
    G0 += 1

for i in range(X, N):
  if i in l:
    GN += 1
    
print(min(G0, GN))

Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define drep(i,n) for(int i = (n-1); i >= 0; i--)
#define all(v) (v).begin(),(v).end()
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 (b < a) { a = b; return 1; } return 0; }
template <class T> T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }
template <class T> T lcm(T a, T b) { return a/gcd(a,b)*b; }
typedef pair<int, int> P;
typedef long long ll;
const int INF = 1001001001;
const ll LINF = 1001002003004005006ll;
const ll MOD = 1e9+7;

int main() {
	int n, q;
    string s;
	cin >> n >> s >> q;
    vector<set<int>> sv(26);
    rep(i,n) sv[s[i]-'a'].insert(i);
    rep(qi, q) {
        int type;
        cin >> type;
        if (type == 1) {
            int i;
            char c;
            cin >> i >> c;
            i--;
            sv[s[i]-'a'].erase(i);
            s[i] = c;
            sv[s[i]-'a'].insert(i);
        } else {
            int l, r;
            cin >> l >> r;
            l--;
            int ans = 0;
            rep(i,26) {
                auto it = sv[i].lower_bound(l);
                if (it != sv[i].end() && *it < r) ans++;
            }
            cout << ans << endl;
        }
    }
	return 0;
}


Measured memory_bytes: 24196
#include <cstdio>
#include <cstdint>
#include <iostream>
#include <iomanip>
#include <string>
#include <queue>
#include <stack>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <algorithm>
#include <utility>
#include <cmath>
#include <climits>
#include <bitset>

#define ll long long int
#define pb push_back
#define mk make_pair
#define pq priority_queue

using namespace std;
typedef pair<int, int> P;
typedef pair<ll, int> Pl;
typedef pair<ll, ll> Pll;
const int inf = 1e9;
const ll linf = 1LL << 50;
const double EPS = 1e-10;

int main(int argc, char const* argv[])
{
  int n;
  cin >> n;
  vector<int> a;
  vector<int> tr = vector<int>(n + 1, 0);
  for(int i = 0; i < n; i++){
    int x;
    cin >> x;
    a.pb(x);
    tr[x] = i;
  }
  set<int> st;
  ll res = 0;
  for(int i = 1; i <= n; i++){
    auto itr = st.upper_bound(tr[i]);
    int rd = (itr == st.end()) ? n: *itr;
    int ld;
    if(itr == st.begin())ld = -1;
    else {
      itr--;
      ld = *itr;
    }
    res += (ll)i * (tr[i] - ld) * (rd - tr[i]);

    st.insert(tr[i]);
  }
  cout << res << endl;
	return 0;
}


Measured memory_bytes: 11252
import sys
input = sys.stdin.readline

h,n = map(int,input().split())

dg = 10**5

ba = []
for _ in [0]*n:
    a,b = map(int,input().split())
    if a >= h:
        a = h
    ba.append(b*dg+a)
ba.sort()

d = [10**9]*(h+1)

d[0] = 0

for i in range(1,h+1):
    for e in ba:
        a,b = e%dg,e//dg
        if i<=a:
            if d[i] > b:
                d[i] = b
        else:
            if d[i] > d[i-a]+b:
                d[i] = d[i-a]+b

print(d[-1])


Measured memory_bytes: 41452
from collections import deque

def main():
    S = input()
    count = 0
    d = deque(list(S))
    while len(d) > 1:
        left = d.popleft()
        right = d.pop()
        if left != right:
            count += 1

    print(count)


if __name__ == "__main__":
    main()

Measured memory_bytes: 3316
#include <bits/stdc++.h>
#include <fstream>
#include <string>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repi(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define ll long long

int main() {
    //入力
    int n;
    cin >> n;
    vector<int> h(n);
    rep(i, n) cin >> h[i];
    //
    int ans = 0;
    rep(i, n) {
        int flg = 0;
        rep(j, i) {
            if (h[j] > h[i]) {
                ++flg;
                break;
            }
        }
        if (flg == 0) {
            ++ans;
        }
    }

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

Measured memory_bytes: 3564
S = list(input())
l = [S.pop()]

while S:
    if S[-1] != l[-1]:
        l.append(S.pop())
    else:
        if len(S) == 1:
            break
        else:
            a = S.pop()
            b = S.pop()
            l.append(b + a)

print(len(l))

Measured memory_bytes: 7872
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < (n); i++)
using namespace std;
const int MAXI = 110;

int main() {
    cin.tie(0)->sync_with_stdio(false);

	int h, w; cin >> h >> w;
	vector<vector<char> > s(h + 1, vector<char>(w + 1));
	REP(i, h) REP(j, w)
		cin >> s[i+1][j+1];

	vector<vector<int> > dp(MAXI, vector<int>(MAXI, INT_MAX));
	dp[1][1] = (s[1][1] == '#');

	for (int i = 1; i <= h; i++) {
		for (int j = 1; j <= w; j++) {
			if (i * j != 1) {
				dp[i][j] = min(dp[i-1][j]+(s[i][j]=='#'&&s[i-1][j]=='.'), dp[i][j-1]+(s[i][j]=='#'&&s[i][j-1]=='.'));
			}
		}
	}
	cout << dp[h][w] << '\n';
    return 0;
}


Measured memory_bytes: 3720
#include<bits/stdc++.h>
using namespace std;
 
int main(){
	long long N;
	unsigned long long ans = 1;
	cin >> N;
 
	bool zero = false;
	bool ng = false;
	for(long long i = 0; i < N; i++) {
		unsigned long long tmp;
		cin >> tmp;
		if(tmp == 0) {
			zero = true;
		}
		if(!zero && 1000000000000000000/ans < tmp) {
			ng = true;
		}
		if(!zero && !ng) {
			ans *= tmp;
		}
	}
 
	if(zero) {
		cout << 0 << endl;
	} else if(ng) {
		cout << -1 << endl;
	} else {
		cout << ans << endl;
	}

}

Measured memory_bytes: 3572
#include <stdio.h>

int main(void){
  long N,p;
  scanf("%ld",&N);
  int flag[N+1];
  long ans = 0;

  for(int i = 0;i < N+1;i++) flag[i] = 0;
  for(int i = 1;i < N+1;i++){
    scanf("%ld",&p);
    if(i == p) flag[i-1] = 1;
  }

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

  printf("%ld\n",ans);

  return 0;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
#define REP(i,a,n) for(int i=(a); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define FOR(it,c) for(__typeof((c).begin()) it=(c).begin(); it!=(c).end(); ++it)
#define ALLOF(c) (c).begin(), (c).end()
typedef long long ll;
typedef unsigned long long ull;


int main(){
  int N, K, Q;
  cin >> N >> K >> Q;
  vector<int> v;
  rep(i,Q){
    int a;
    cin >> a;
    a--;
    v.push_back(a);
  }

  vector<int> w(N,0);
  rep(i,v.size()){
    w[v[i]] += 1;
  }

  int ret = 0;
  rep(i,w.size()){
    w[i] -= Q;
    w[i] += K;
    //cout << w[i] << endl;
    if(w[i] > 0) cout << "Yes" << endl;
    else cout << "No" << endl;
  }
  
  return 0;
}


Measured memory_bytes: 1528
#include <bits/stdc++.h>
using namespace std;
void Main();

using i8  = int8_t;   /* -128 ~ 127 */
using u8  = uint8_t;  /* 0 ~ 255 */
using i16 = int16_t;  /* -32,768 ~ 32,767 */
using u16 = uint16_t; /* 0 ~ 65,535 */
using i32 = int32_t;  /* -2,147,483,648 ~ 2,147,483,647 */
using u32 = uint32_t; /* 0 ~ 4,294,967,295 */
using i64 = int64_t;  /* -9,223,372,036,854,775,808 ~ 9,223,372,036,854,775,807 */
using u64 = uint64_t; /* 0 ~ 18,446,744,073,709,551,615 */
using f32 = float;    /* (-3.4 * 10^38) ~ (3.4 * 10^38) */
using f64 = double;   /* (-1.7 * 10^308) ~ (1.7 * 10^308) */
using f80 = __float80;
template <class T> using Vec = vector<T>;
constexpr i64 INF = 1010000000000000017;
constexpr i64 MOD = 1e9 + 7;
constexpr f64 EPS = 1e-12;
constexpr f64 PI = 3.14159265358979323846;
#define ALL(v) v.begin(), v.end()
#define GCD(a, b) __gcd(a, b) /* 最大公約数 */
#define LCM(a, b) a / __gcd(a, b) * b /* 最小公倍数 */

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(15);
    Main();
    return 0;
}

void Main() {
    string S;
    cin >> S;
    if (S.size() == 1) {
        cout << 0 << endl;
        return;
    }
    i32 sum = 0;
    for (i32 c = 0; c < S.size() / 2; c++) {
        if (S[c] != S[S.size() - 1 - c]) sum++;
    }
    cout << sum << endl;
}


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

using namespace std;
typedef long long ll;
typedef long double ld;
#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define REPR(i,n) for(int i=n; i>-1; --i)
#define ALL(a) (a).begin(),(a).end()
#define FILL(a,n,x); REP(i,(n)){ (a)[i]=(x); }
#define CINA(a,n); REP(i,(n)){ cin >> (a)[i]; }
#define FILL2(a,n,m,x); REP(i,(n)){ REP(j,(m)){(a)[i][j]=(x);} }
#define CINA2(a,n,m); REP(i,(n)){ REP(j,(m)){cin >> (a)[i][j];} }
#define Liny "Yes\n"
#define Linn "No\n"
#define LINY "YES\n"
#define LINN "NO\n"

//cout << setfill('0') << right << setw(4) << 12; // "0012"
int keta(ll x){ if(x<10){return 1;} else{return keta(x/10) + 1;}}
int keta_wa(ll x){ if(x<10){return x;} else{return keta_wa(x/10) + x%10;} }
int ctoi(char c){ return ( (c>='0' && c<='9')? c - '0': 0 );}
int __stoi(string s){ return atoi(s.c_str()); }
ll sum(ll a[],ll N){ return accumulate(a,a+N,0LL);}
ll gcd(ll a,ll b){if(a<b)swap(a,b); return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){if(a<b){swap(a,b);} return a/gcd(a,b)*b;}
template<class T> void chmax(T& a, T b){ if(a<b){a=b;} }
template<class T> void chmin(T& a, T b){ if(a>b){a=b;} }
const ll MOD = 1e9+7;
#define pii pair<int,int>
#define pll pair<ll,ll>


int main(){
    int N; cin>>N;
    int x = N%10;
    string ans = "hon";
    if(x==3){ ans = "bon";}
    else if(x==0||x==1||x==6||x==8){ ans = "pon";}
    cout << ans << "\n";
}

Measured memory_bytes: 3632
INF = 10 ** 15
MOD = 10 ** 9 + 7 

class SegmentTree():
    f = min
    unit = INF
   
    def __init__(self,array):
        self.N = len(array)
        self.tree = [self.unit] * (2*self.N)
        self._build(array)
    
    def _build(self,array):
        for i,x in enumerate(array,self.N):
            self.tree[i] = x
        for i in range(self.N - 1,0,-1):
            self.tree[i] = self.f(self.tree[i << 1],self.tree[i << 1|1])
    
    def update(self,k,x):
        k += self.N
        if self.tree[k] <= x:
            return 
        self.tree[k] = x
        while k > 1:
            k >>= 1
            self.tree[k] = self.f(self.tree[k << 1],self.tree[k << 1|1])
    
    def query(self,l,r):
        l += self.N
        r += self.N
        vl = self.unit
        vr = self.unit
        while l < r:
            if l&1: 
                vl = self.f(vl,self.tree[l])
                l += 1
            if r&1:
                r -= 1
                vr = self.f(self.tree[r],vr)
            l >>= 1
            r >>= 1
        return self.f(vl,vr)
    
    def __str__(self):
        return '\n'.join(' '.join(str(v) for v in self.tree[1<<i:1<<(i + 1)]) for i in range((2*self.N).bit_length()))

N,M = map(int,input().split())
paths = [[] for _ in range(N)]
for _ in range(M):
    l,r,c = map(int,input().split())
    l -= 1
    r -= 1
    paths[l].append((r,c))

dp = SegmentTree([0] + [INF] * (N - 1))
for l,path in enumerate(paths):
    for r,c in path:
        before_min = dp.query(l,N)
        dp.update(r,before_min + c)
ans = dp.query(N - 1,N)
print(ans if ans < INF else -1)

Measured memory_bytes: 79648
#include <bits/stdc++.h>
using namespace std;
int main(){
  while (1){
    int n;
    cin >> n;
    if (n == 0){
      break;
    }
    vector<string> a(n), b(n);
    for (int i = 0; i < n; i++){
      cin >> a[i] >> b[i];
    }
    string S;
    cin >> S;
    string T;
    cin >> T;
    map<string, int> mp;
    mp[S] = 0;
    queue<string> Q;
    Q.push(S);
    while (!Q.empty()){
      string v = Q.front();
      int sz = v.size();
      Q.pop();
      for (int i = 0; i < n; i++){
        string w = "";
        for (int j = 0; j < sz; j++){
          if (j <= sz - a[i].size()){
            if (v.substr(j, a[i].size()) == a[i]){
              w += b[i];
              j += a[i].size() - 1;
            } else {
              w += v[j];
            }
          } else {
            w += v[j];
          }
        }
        if (!mp.count(w) && w.size() <= 10){
          mp[w] = mp[v] + 1;
          Q.push(w);
        }
      }
    }
    if (!mp.count(T)){
      cout << -1 << endl;
    } else {
      cout << mp[T] << endl;
    }
  }
}


Measured memory_bytes: 3268
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pi = pair<int, int>;

int h,w,a,b;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> h >> w >> a >> b;
    for(int i=0;i<h;i++)
    {
        for(int j=0;j<w;j++)
        {
            cout << ((i < b) ^ (j < a));
        }
        cout << '\n';
    }
}

Measured memory_bytes: 1280
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cctype>
#include<math.h>
#include<string>
#include<string.h>
#include<stack>
#include<queue>
#include<vector>
#include<utility>
#include<set>
#include<map>
#include<stdlib.h>
#include<iomanip>

using namespace std;

#define ll long long
#define ld long double
#define EPS 0.0000000001
#define INF 1e9
#define LINF (ll)INF*INF
#define MOD 1000000007
#define rep(i,n) for(int i=0;i<(n);i++)
#define loop(i,a,n) for(int i=a;i<(n);i++)
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)

#define int ll //!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

typedef vector<int> vi;
typedef vector<string> vs;
typedef pair<int,int> pii;
typedef vector<pii> vp;

int gcd(int a, int b){
    if(b==0) return a;
    return gcd(b,a%b);
}
int lcm(int a, int b){
    return a/gcd(a,b)*b;
}

vi a;
int n;

int f(int ind, int col){
    int ret = 0;
    int l = ind;
    int r = ind+1;
    while(1){
        int cnt = 0;
        while(l >= 0 && a[l] == col){
            cnt++;
            l--;
        }
        while(r < n && a[r] == col){
            cnt++;
            r++;
        }
        if(cnt >= 4){
            ret += cnt;
            if(l < 0 || r >= n) break;
            if(a[l] == a[r])col = a[l];
        }else{
            break;
        }
    }
    return ret;
}

signed main(void) {
    while(cin >> n, n){
        a = vi (n);
        rep(i,n)cin >> a[i];

        int ans = 0;
        rep(i,n)rep(j,3){
            int t = a[i];
            a[i] = j;
            ans = max(ans, f(i,j));
            a[i] = t;
        }
        cout << n - ans << endl;
    }
}



Measured memory_bytes: 3180
from itertools import product
from collections import defaultdict

h,w=list(map(int,input().split()))
maze=[list(input()) for _ in range(h)]
edges=defaultdict(list)
def neibors(x,y):
    return ((i,j)
     for i,j in [(x,y-1),(x,y+1),(x-1,y),(x+1,y)] 
            if 0<=i and i<h and 0<=j and j<w
     )
for x,y in product(range(h),range(w)):
    if maze[x][y]=='#':
        continue
    for adjx,adjy in neibors(x,y):
        if maze[adjx][adjy]=='.':
            edges[(x,y)].append((adjx,adjy))
distance_pairs=[[] for _ in range(h*w+1)]
distance_pairs[0]=[(s,s) for s in edges]
distances=defaultdict(dict)
for s in edges:
    distances[s][s]=0

for k in range(h*w+1):
    for s,t in distance_pairs[k]:
        for new_t in edges[t]:
            if new_t in distances[s]:
                continue
            distance_pairs[k+1]+=[(s,new_t)]
            distances[s][new_t]=k+1
    
    if len(distance_pairs[k+1])==0:
        break
print(k)



Measured memory_bytes: 25836
#!python3

LI = lambda: list(map(int, input().split()))

# input
H, W = LI()
A = ["#" + input() + "#" for _ in range(H)]


def main():
    x = ["#" * (W + 2)]
    ans = x + A + x
    print("\n".join(ans))


if __name__ == "__main__":
    main()


Measured memory_bytes: 3060
n,m = map(int,input().split())
c = 0
k = []
for i in range(n):
  x = list(map(int,input().split()))
  x = x[1:]
  k.append(x)
for i in range(1,m+1):
  if all(i in k[j] for j in range(n)):
    c += 1
print(c)

Measured memory_bytes: 3060
#include <iostream>

using namespace std;

int main() {
  int n;
  cin >> n;
  double sum = 0;
  for (int i = 0; i < n; ++i) {
    double x;
    char u[4];
    cin >> x >> u;
    sum += u[0] == 'J' ? x : x * 380000;
  }
  printf("%f",sum);
}


Measured memory_bytes: 256
import collections

N = int(input())
cNum = collections.Counter(list(map(int, input().split())))
ans = 1
if cNum[0] != 0:
  print("0")
  exit()
for n in cNum.keys():
  ans *= n**cNum[n]
  if ans > 10**18:
    ans = -1
    break
print(ans)

Measured memory_bytes: 23992
#include<bits/stdc++.h>
#define For(i,l,r) for(int i = (l),i##end = (r);i <= i##end;i++)
#define Fordown(i,r,l) for(int i = (r),i##end = (l);i >= i##end;i--)
#define debug(x) cout << #x << " = " << x << endl

using namespace std;

typedef long long ll;

template <typename T> inline bool chkmin(T &x,T y) { return y < x ? x = y,1 : 0; }
template <typename T> inline bool chkmax(T &x,T y) { return x < y ? x = y,1 : 0; }

const int INF = 0x3f3f3f3f;
const int N = 1e5 + 10;

int A[N],B[N],fa[N],id[N],to[N << 1],nex[N << 1],beg[N],vis[N];
ll Sum[N],dp[N];
int e;

bool Cmp(const int &lhs,const int &rhs) {
	return A[lhs] < A[rhs];
}

inline void add(int x,int y) {
	to[++e] = y,nex[e] = beg[x],beg[x] = e;
}

inline int find(int x) {
	return fa[x] == x ? x : fa[x] = find(fa[x]);
}

inline int read() {
	int x = 0,flag = 1;
	char ch = getchar();
	while(!isdigit(ch) && ch != '-')ch = getchar();
	if(ch == '-')flag = -1,ch = getchar();
	while(isdigit(ch))x = (x << 3) + (x << 1) + (ch - '0'),ch = getchar();
	return x * flag;
}

int main() {

	int n = read(),m = read();
	For(i,1,n) {
		A[i] = read(),B[i] = read(),A[i] = max(A[i] - B[i],0);
		fa[i] = id[i] = i,Sum[i] = B[i],dp[i] = A[i];
	}
	For(i,1,m) {
		int x = read(),y = read();
		add(x,y),add(y,x);
	}
	sort(id + 1,id + n + 1,Cmp);
	For(i,1,n) {
		vis[id[i]] = true;
		for(int j = beg[id[i]];j;j = nex[j]) {
			if(!vis[to[j]]) continue;
			int x = find(id[i]),y = find(to[j]);
			if(x == y) continue;
			fa[y] = x,Sum[x] += Sum[y];
			chkmin(dp[x],max(dp[y],A[x] - Sum[y]));
		}
	}

	printf("%lld\n",dp[id[n]] + Sum[id[n]]);

	return 0;
}

Measured memory_bytes: 5760
from collections import defaultdict

n = int(input())
S = input()


# 0〜9までの各数字が左から何桁目に登場するか
d = defaultdict(list)
for i in range(n):
    d[int(S[i])].append(i)

pw = []
for i in d.keys():
    for j in d.keys():
        for k in d.keys():
            first = d[i][0]
            for l in d[j]:
                if l > first:
                    second = l
                    break
            else:
                continue
            for m in d[k]:
                if m > second:
                    third = m
                    break
            else:
                continue
            pw.append(S[first]+S[second]+S[third])
print(len(set(pw)))

Measured memory_bytes: 4712
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <string>
#include <algorithm>
using namespace std;

map <string,int> mp;
int n,Max,cnt;
string s[200005],b[200005];

int main()
{
	scanf("%d",&n);
	for (int i=1;i<=n;i++) {
		cin>>s[i];
		mp[s[i]]++;
		Max=max(Max,mp[s[i]]);
	}
	for (auto i:mp) {
		if (i.second==Max) b[++cnt]=i.first;
	}
	sort(b+1,b+cnt+1);
	for (int i=1;i<=cnt;i++) cout << b[i] << endl;
	
	return 0;
}

Measured memory_bytes: 29696
#include <bits/stdc++.h>
#include <iomanip>
#include <math.h>
//#include <unistd.h>
//#include <stdio.h>
#define rep(i,x) for(ll i = 0;i<x;i++)
#define all(a) (a).begin(),(a).end()
using ll = long long;
using ld = long double;
using namespace std;
using dou = double;
const ll INF = 1LL << 60;
const ll mod = 1000000007;
typedef pair<ll,ll> P;
using graph = vector<vector<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;}
ll gcd(ll a,ll b){
    if(a < b)swap(a,b);
    if(a % b == 0)return b;
    else return gcd(b,a%b);
}
bool isp(ll n){
    bool res = true;
    if(n == 1)return false;
    else{
        for(ll i = 2;i * i <= n;i++){
            if(n % i == 0){
                res = false;
                break;
            }
        }
        return res;
    }
}
const int MAX = 510000;

long long fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % mod;
        inv[i] = mod - inv[mod%i] * (mod / i) % mod;
        finv[i] = finv[i - 1] * inv[i] % mod;
    }
}

// 二項係数計算
long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % mod) % mod;
}
/*
int main() {
    // 前処理
    COMinit();

    // 計算例
    cout << COM(100000, 50000) << endl;
}*/

//printf("%.10f\n", N);
/*
ll fibo(ll n){
    if(memo[n] != 0)return memo[n];
    if(n <= 1)return n;
    else return memo[n] = fibo(n - 1)+ fibo(n - 2);
}*/
/*  vector<ll> vec = {1,2,5,6,8,9,10};
    cout << binary_search(all(vec),5) << endl; -> true*/
/*
    vector<ll> vec = {1,2,5,6,8,9,10};
    auto n = upper_bound(all(vec),4);
    cout << *n << endl; -> 5*/
/*
    cout << fixed << setprecision(15);
    */
int main(){
    ll N;
    cin >> N;
    for(ll i = 1;;i++){
        if(N <= (i + i * i)/ 2){
            cout << i << endl;
            break;
        }
    }
}

Measured memory_bytes: 384
#include<iostream>
#include<cstdio>
#include<cstring>
#include<map>
#include<bitset>

const int N=101,MOD=998244353;
typedef long long ll;
typedef unsigned long long ull;
typedef std::bitset<N> bits;

std::map<ull,int> f;

ull calc(bits &A,int len)
{
	ull ret=817;
	for(int i=0;i<len;i++)
		ret=ret*2333+(int)A[i];
	return ret;
}

int n;

int dfs(bits A,int len)
{
	if(!len)return 1;

	ull h=calc(A,len);
	if(f.count(h))return f[h];

	int ret;
	ret=(ll)(1+A[0])*dfs(A>>1,len-1)%MOD;

	bits B;

	for(int i=1;i<=len;i++)
	{
		B=A;
		for(int j=2;i*j<=len;j++)
		{
			B&=(A>>(i*(j-1)));
			ret=(ret+(ll)dfs(B,i)*dfs(A>>(i*j),len-i*j))%MOD;
		}
	}

	f[h]=ret;
	return ret;
}

void solve()
{
	static char tmp[N];
	bits A;A.reset();
	scanf("%s",tmp);
	n=strlen(tmp);
	for(int i=0;i<n;i++)
		A[i]=tmp[i]-'0';
	f.clear();
	printf("%d\n",dfs(A,n));
}

int main()
{
	solve();
	return 0;
}

Measured memory_bytes: 3072
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <math.h>
#define MAXNUM 1000000

using namespace std;

int main(void){
	int flag[MAXNUM + 1], a, d, n, i, j, count;
	fill(flag,flag + MAXNUM,1);
	flag[0] = flag[1] = 0;
	for(i = 2;i <= sqrt((double)MAXNUM);i++){
		if(flag[i]){
			for(j = i * 2;j <= MAXNUM;j += i)
				flag[j] = 0;
		}
	}
	while(1){
		scanf("%d%d%d",&a,&d,&n);
		if(a == 0 && d == 0 && n == 0)
			break;
		i = count = 0;
		while(1){
			if(flag[a + d * i]){
				count++;
				if(count == n)
					break;
			}
			i++;
		}
		printf("%d\n",a + d * i);
	}
	return 0;
}

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

int main(){

	long h, w, i, x, ans;
	cin >> h >> w;
  	i = h;
  	x = w;
  	if (h == 1 || w == 1){
        ans = 1;
    }
    else{
  		if(h%2!=0) i = h-1, h++;
  		if(w%2!=0) x = w-1, w++;
  		ans = (h/2)*(w/2)+(i/2)*(x/2);
    }
  	cout << ans << endl;
	return 0;
}

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

int dp[2001][2];
int n,z,w,t;
vector <int> v;


int func(int idx,int turn)
{
	if(dp[idx][turn]!=-1)
	{
		return dp[idx][turn];
	}

	int res;
	if(turn==0)
	{
		if(idx==0)
		{
			res = abs(v[n-1]-w);
		}
		else
		{
			res = abs(v[idx-1]-v[n-1]);
		}
		for(int j=idx;j<n-1;j++)
		{
			res = max(res,func(j+1,1-turn));
		}
	}
	else
	{
		res = abs(v[idx-1]-v[n-1]);
		for(int j=idx;j<n-1;j++)
		{
			res = min(res,func(j+1,1-turn));
		}
	}
	dp[idx][turn] = res;
	return res;
}

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

	cin >> n >> z >> w;

	for(int i=0;i<n;i++)
	{
		cin >> t;
		v.push_back(t);
	}

	memset(dp,-1,sizeof(dp));

	cout << func(0,0) << '\n';
	return 0;
}


Measured memory_bytes: 384
import java.util.*;

class Main
{
    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        
        int n = sc.nextInt();
        int a = sc.nextInt();
        int b = sc.nextInt();
        
        
        if (n * a <= b) {
            System.out.println(n * a);
        } else {
            System.out.println(b);
        }
        
        
    }
}
        

Measured memory_bytes: 24916
#include<limits>
using ll=long long;constexpr int INF=std::numeric_limits<int>::max()/2;constexpr ll LNF=std::numeric_limits<ll>::max()/2;constexpr double EPS=1e-8;constexpr int DX[]={1,0,-1,0,1,1,-1,-1};constexpr int DY[]={0,1,0,-1,-1,1,1,-1};
#ifdef PA_DEBUG
#define PD(stmt)stmt
#else
#define PD(stmt)
#endif
#include<iostream>
#include<vector>
namespace pcl{namespace utility{template<typename T>std::ostream&operator<<(std::ostream&os,std::vector<T>const&v){os<<'[';for(size_t i=0;i<v.size();i++){if(i!=0)os<<",";os<<v[i];}os<<']';return os;}template<typename T>std::istream&operator>>(std::istream&is,std::vector<T>&v){for(size_t i=0;i<v.size();i++)is>>v[i];return is;}}}using namespace pcl::utility;
#include<bits/stdc++.h>
using namespace std;int cost(int N,int base){int cnt=0;while(N!=0){cnt+=N%base;N/=base;}return cnt;}int main(){int N;cin>>N;int total=INF;for(int i=0;i<=N;i++){total=min(total,cost(i,6)+cost(N-i,9));}cout<<total<<endl;}

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

using namespace std;

int main(){
  int l, N;
  cin >> l >> N;
  vector<char> s(l);
  vector<int> c(l);
  int counter = 0;
  cin >> s[0];
  for(int i = 1; i < l; i++){
    cin >> s[i];
    if(s[i-1] == 'A' && s[i] == 'C'){
      counter++;
    }
    c[i-1] = counter;
  }  
  for(int i = 0; i < N; i++){
    int l,u;
    cin >> l >> u;
    cout << c[u-2] - c[l - 2] << endl;
  }
}

Measured memory_bytes: 1280
#include <iostream>
#include <vector>

using namespace std;

int main() {
    cin.tie(0);
   	ios::sync_with_stdio(false);
    
    int N;
    cin >> N;
    vector<int> A(N);
    for (int i=0; i<N; ++i) cin >> A[i];
    
    int swp;
    int cnt = 0;
    for (int i=0; i<N; ++i) {
        for (int j=N-1; j>i; --j) {
            if (A[j-1] > A[j]) {
                swp = A[j-1];
                A[j-1] = A[j];
                A[j] = swp;
                ++cnt;
            }
        }
    }
    for (int i=0; i<N-1; ++i) cout << A[i] << " ";
    cout << A.back() << "\n" << cnt << "\n";
    return 0;
}


Measured memory_bytes: 3216
#include<iostream>
#include<math.h>
#include<vector>
#include<string>
#include<stack>
#include<queue>
#include<map>
#include<algorithm>
#include<bitset>
#include <climits>
using namespace std;
#define _GLIBCXX_DEBUG
#define pq priority_queue
#define mp make_pair
#define pb push_back
#define ff first
#define ss second
#define vit vector<lint>::iterator
#define all(x) (x).begin(),(x).end()
#define rep(x) for(int i = 0;i < (x);i++)
#define repj(x) for(int j = 0;j < (x);j++)
#define REP(i,x) for(int (i) = 0;(i) < (x);(i)++)
#define rrep(x) for(int i = (x);i >= 0;i--)
#define mins(x,y) x = min(x,y)
#define maxs(x,y) x = max(x,y)
#define mod 1000000007
#define graph_set(n) struct edge{int to,int cost;} vector<edge> G((n))
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
#define range(x,y) ((x) >= 0 && (x) < h && (y) >= 0 && (y) < w)
#define pyes cout << "Yes" << endl
#define pno cout << "No" << endl
typedef vector<long long> vi;
typedef vector<pair<long long, long long>> vp;
typedef vector<vector<long long>> vvi;
typedef pair<long long, long long> pi;
typedef long long lint;
typedef long long ll;
lint qp(int a, ll b) { int ans = 1; do { if (b & 1)ans = 1ll * ans*a; a = 1ll * a*a; } while (b >>= 1); return ans; }
lint qp(int a, ll b, int mo) { int ans = 1; do { if (b & 1)ans = 1ll * ans*a%mo; a = 1ll * a*a%mo; } while (b >>= 1); return ans; }
lint gcd(int a, int b) { return b ? gcd(b, a%b) : a; }
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
long long INF = 1e14;

/********************/
const int MAX_V = 3e5 + 100;
struct edge { int to, cost; };
int n;
vector<edge> G[MAX_V];
int d[MAX_V];
void dijkstra(int s) {
	pq<pi, vp, greater<pi>> que;
	fill(d, d + n, INF);
	d[s] = 0;
	que.push(pi(0, s));

	while (!que.empty()) {
		pi p = que.top(); que.pop();
		int v = p.ss;
		if (d[v] < p.ff) continue;
		for (int i = 0; i < G[v].size(); i++) {
			edge e = G[v][i];
			if (d[e.to] > d[v] + e.cost) {
				d[e.to] = d[v] + e.cost;
				que.push(pi(d[e.to], e.to));
			}
		}
	}
}
/********************/

int main() {
	int v, m; cin >> v >> m;
	n = 3 * v;
	rep(m) {
		int x, y; cin >> x >> y;
		x--, y--;
		int c = 1;

		edge e = { y,c };
		G[x + 2 * v].push_back(e);

		e = { y + v,c };
		G[x].pb(e);

		e = { y + 2 * v,c };
		G[x + v].pb(e);
	}

	int s, t; cin >> s >> t; s--, t--;
	dijkstra(s);
	if (d[t] >= 3 * 1e5) {
		cout << -1 << endl;
	}
	else cout << d[t]/3 << endl;
	return 0;
}

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

using namespace std;

void Main() {
    int A, B, C, D;
    cin >> A >> B >> C >> D;

    int ans = 0;
    if (D <= A || B <= C) {
        ans = 0;
    }
    else {
        ans = min(B, D) - max(A, C);
    }
    cout << ans << endl;
}

int main() {
    std::cout << std::fixed << std::setprecision(15);
    Main();
    return 0;
}


Measured memory_bytes: 3628
// B
// DeP
#include <cstdio>
#include <cstring>

const int MAXN = 105;

int n;
char S[MAXN];

bool check(int L, int R) {
    int p1 = L, p2 = R;
    while (p1 < p2) {
        if (S[p1] != S[p2]) return false;
        ++p1, --p2;
    }
    return true;
}

int main() {
    scanf("%s", S+1);
    n = strlen(S+1);
    puts((check(1, n) && check(1, (n-1) / 2) && check((n+3) / 2, n))? "Yes": "No");
    return 0;
}

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

bool eq(int i, string s, string t)
{
	int siz= s.size();
	for (int j = 0; j < siz; ++j)
		if(s[j] != t[(i+j)%siz])
			return false;
	return true;
}

int main()
{
	string s, t;
	cin >> s >> t;
	bool res = false;
	for (int i = 0; i < s.size(); ++i)
		if(eq(i, s, t))
			res = true;
	if(res)
		cout << "Yes";
	else
		cout << "No";
}

Measured memory_bytes: 256
class UnionFind
    def initialize(size)
        @parent = Array.new(size, -1)
    end

    def root(x)
        if @parent[x] < 0
            x
        else
            @parent[x] = root(@parent[x])
        end
    end

    def same_parent?(x, y)
        root(x) == root(y)
    end

    def merge(x, y)
        x_root = root(x)
        y_root = root(y)

        return false if x_root == y_root

        # merge technique
        if @parent[x_root] > @parent[y_root]
            x_root, y_root = y_root, x_root
        end

        @parent[x_root] += @parent[y_root]
        @parent[y_root] = x_root

        return true
    end

    def size(x)
        return -@parent[root(x)]
    end
end


def solve()
    n, m = gets.strip.split.map(&:to_i)
    abs = m.times.map { gets.strip.split.map(&:to_i) }.reverse

    ans = []
    uf = UnionFind.new(n)

    # 不便さ
    cur = (n * (n - 1)) / 2

    # 逆順にみていく(辺がない状態から辺を足していく)
    abs.each do |ab|
        ans.push(cur)

        a = ab.first - 1
        b = ab.last - 1

        # 同じ連結成分なら不便さは変わらない
        next if uf.same_parent?(a, b)

        # aとbをつなげると、
        # それぞれが属する連結成分の大きさをかけた数だけ行き来できるルートが増えるので
        # そのぶん不便さが減る
        size_a = uf.size(a)
        size_b = uf.size(b)
        cur -= size_a * size_b

        uf.merge(a, b)  # aとbをつなげる
    end

    ans.reverse.each { |a| puts a }
end


solve()


Measured memory_bytes: 13944
#include<stdio.h>
#include<string>
#include<map>
#include<algorithm>
#include<vector>
#include<iostream>
using namespace std;
int main(){
  int n,r;
  scanf("%d %d\n",&n,&r);
  if(n<10){
    printf("%d\n",r+100*(10-n));
  }
  else{
    printf("%d\n",r);
  }
  return 0;
}

Measured memory_bytes: 256
import sys
readline = sys.stdin.buffer.readline

n, m = map(int, readline().split())
ac_lst = [False] * (n + 1)
wa_lst = [0] * (n + 1)
w = 0
for _ in range(m):
    a, b = readline().split()
    a = int(a)
    if ac_lst[a]:
        continue
    if b == b'WA':
        wa_lst[a] += 1
    else:
        w += wa_lst[a]
        ac_lst[a] = True
print(sum(ac_lst), w)


Measured memory_bytes: 4596
#include <iostream>
#include <string>
int main()
{
    int k;
    std::string s;
    std::cin >> k >> s;

    if(s.size()<=k){
        std::cout << s << std::endl;
        return 0;
    }

    std::cout << s.substr(0,k) +"..." << std::endl;
    return 0;
}

Measured memory_bytes: 3580
module AOJ_Volume0092;

import std.stdio,std.string,std.conv,std.algorithm;

int w[1001][1001];
int main()
{
	string s[1001];
	while(true)
	{
		int n = readln.chomp.to!int;
		if(n == 0) break;

		foreach(i;0..1001)
		{
			foreach(j;0..1001)
			{
				w[i][j] = 0;
			}
		}

		foreach(i;0..n)
		{
			s[i] = readln.chomp;
		}

		foreach(i;0..n)
		{
			foreach(j;0..n)
			{
				if(s[i][j] == '*') w[i][j] = 0;
				else w[i][j] = 1;
			}
		}

		int ans = 0;
		foreach(i;1..n)
		{
			foreach(j;1..n)
			{
				if(s[i][j] == '*')
				{
					w[i][j] = 0;
				}
				else
				{
					w[i][j] = min(w[i-1][j-1],min(w[i-1][j],w[i][j-1])) + 1;
					ans = max(ans,w[i][j]);
				}
			}
		}

		ans.writeln;


	}
	return 0;
}

Measured memory_bytes: 6988