akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <math.h>
using namespace std;

int IsPrime(int num)
{
    if (num < 2) return 0;
    else if (num == 2) return num;
    else if (num % 2 == 0) return 0; // 偶数はあらかじめ除く

    double sqrtNum = sqrt(num);
    for (int i = 3; i <= sqrtNum; i += 2)
    {
        if (num % i == 0)
        {
            // 素数ではない
            return 0;
        }
    }

    // 素数である
    return num;
}

int main(){
  	int X, ans;
  	bool check = false;
  	cin >> X;
  	do {
    	ans = IsPrime(X);
      	if(ans!=0){
        	check=true;
        }
      	X++;
    }while(check==false);
  	cout << ans << endl;
}

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

const int base = 1e5+5;

int main(){
    int n;
    cin>>n;
    vector<vector<int>> c(base*2,vector<int>());
    rep(i,n){
        int x,y;
        cin>>x>>y;
        y+=base;
        c[x].push_back(y);
        c[y].push_back(x);
    }
    vector<bool> visited(base*2,false);
    ll cnt=0;
    rep(i,base){
        if(!visited[i]){
            ll cnt_x=0;
            ll cnt_y=0;
            visited[i]=true;
            queue<int> que;
            que.push(i);
            if(i<base){
                cnt_x++;
            }else{
                cnt_y++;
            }
            while(que.size()){
                ll p=que.front();
                que.pop();
                for(int k:c[p]){
                    if(!visited[k]){
                        visited[k]=true;
                        que.push(k);
                        if(k<base){
                            cnt_x++;
                        }else{
                            cnt_y++;
                        }
                    }
                }
            }
            cnt+=cnt_x*cnt_y;
        }
    }
    cout<<cnt-n<<endl;
}


Measured memory_bytes: 8064
class Imos:
    def __init__(self, n):
        self.B = [0] * n
        self.n = n
        from itertools import accumulate
        self.ac = accumulate

    def __call__(self, l, r):
        l, r = max(l, 0), min(r, self.n - 1)
        self.B[l] += 1
        if r + 1 != self.n:
            self.B[r + 1] -= 1

    def out(self):
        *res, = self.ac(self.B)
        return res

from collections import defaultdict
d = defaultdict(list)
imos = Imos(10 ** 5 + 1)

(N, C), *D = [[*map(int, o.split())] for o in open(0)]
for s, t, c in D:
    d[c] += (s, t),
for p in d.values():
    p.sort()
    ps, pt = p[0]
    for s, t in p[1:] + [[0,0]]:
        if pt == s:
            pt = t
        else:
            imos(ps - 1, pt - 1)
            ps, pt = s, t
print(max(imos.out()))

Measured memory_bytes: 36756
N, M, X, Y = map(int, input().split())
x = sorted(map(int, input().split()))
y = sorted(map(int, input().split()))

if x[-1] < y[0]:
  if Y <= x[-1] or y[0] <= X:
    print('War')
  else:
    print('No War')
else:
  print('War')

Measured memory_bytes: 3060
# ABC150D

import sys
input=sys.stdin.readline
from math import gcd,ceil

def main():
    N,M=map(int,input().split())
    A=list(map(lambda x: int(x)//2,input().split()))
    lcm=A[0]
    for i in range(1,N):
        lcm=lcm*A[i]//gcd(lcm,A[i])
    allo=1
    for i in range(N):
        allo&=(lcm//A[i])%2
    if allo:
        print(ceil(int(M//lcm)/2))
    else:
        print(0)
    
    
if __name__=="__main__":
    main()


Measured memory_bytes: 20192
#include<iostream>
using namespace std;
int main()
{
	int n,m;
	cin>>n>>m;
	int a[n+1]={0};
	for(int i =0;i<m;i++)
	{
		int x,y;
		cin>>x>>y;
		a[x]++;
		a[y]++;
	}
	for(int i =1;i<n+1;i++)
	      cout<<a[i]<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <algorithm>
using namespace std;
int N, W;
int w[101], v[101];
int dp[101][10001];
void solve() {
    for (int i = 0; i <= W; i++) dp[0][i] = 0;
    for (int i = 0; i < N; i++) dp[i][0] = 0;

    for (int i = 0; i < N; i++) {
        for (int j = 0; j <= W; j++) {
            if (j < w[i]) dp[i+1][j] = dp[i][j];
            else dp[i+1][j] = max(dp[i][j], dp[i+1][j-w[i]]+v[i]);
        }
    }
    printf("%d\n", dp[N][W]);
}

int main()
{
    scanf("%d %d", &N, &W);
    for (int i = 0; i < N; i++) scanf("%d %d", &v[i], &w[i]);
    solve();
    return 0;
}



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

using namespace std;

const int inf = 1<<20;

int dp[1<<18][51];

int main() {
  int n; cin >> n;
  vector<int> la(n), lb(n);
  for (int &a: la) cin >> a;
  for (int &b: lb) cin >> b;
  for (int mask = 0; mask < (1<<n); ++mask) {
    for (int s = 0; s <= 50; ++s) dp[mask][s] = inf;
  }
  dp[0][0] = 0;
  for (int mask = 0; mask < (1<<n); ++mask) {
    int cnt = __builtin_popcount(mask);
    for (int s = 0; s <= 50; ++s) { 
      if (dp[mask][s] == inf) continue;
      int p = 0;
      for (int j = 0; j < n; ++j) { 
        int flag = 1<<j;
        if (mask & flag) continue;
        int t = (abs(j-cnt) % 2) ? lb[j] : la[j];
        if (t >= s) {
          dp[mask|flag][t] = min(dp[mask|flag][t], dp[mask][s] + p);
          // cerr << mask << " " << (mask|flag) << " " << s << " " << t << " " << dp[mask][s] << " " << p << " " << dp[mask|flag][t] << endl;
        }
        ++p;
      }
    }
  }
  int ans = inf;
  for (int t = 1; t <= 50; ++t) {
    ans = min(ans, dp[(1<<n)-1][t]);
  }
  if (ans == inf) {
    cout << -1 << endl;
  }
  else {
    cout << ans << endl;
  }
}



Measured memory_bytes: 52608
import java.util.*;

public class Main {

    public static void main(String args[]) {

        // 入力
        Scanner sc = new Scanner(System.in);
        long n = Long.parseLong(sc.next());
        sc.close();

        // 主処理
        List<Integer> divDigitList = divDigitList(n);
        int min = divDigitList.stream().mapToInt(i -> i).min().orElse(0);
        int result = min;

        // 出力
        System.out.println(result);
    }

    public static List<Integer> divDigitList(long num) {
        List<Integer> list = new ArrayList<>();
        long max = (long) Math.sqrt(num);
        for (long i = 1; i <= max; i++) {
            if (num % i == 0) {
                long a = i;
                long b = num / i;
                int digit = Math.max(Long.toString(a).length(), Long.toString(b).length());
                list.add(digit);
            }
        }
        return list;
    }
}


Measured memory_bytes: 36092
#include <cstdio>
#include <cmath>
#include <algorithm>

int main()
{
  int a, b, c, k;
  scanf("%d %d %d %d", &a, &b, &c, &k);
  int max = std::max(a, std::max(b, c));
  printf("%d\n", a + b + c - max + max * (1 << k));
  return 0;
}

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

#define pb push_back
#define eb emplace_back

typedef long long ll;
typedef unsigned long long ull;

using namespace std;



void oneCase() {
    int n;
    cin >> n;
    int ok = 0;
    auto s = to_string(n);
    ok |= s[0] == s[1] && s[1] ==  s[2];
    ok |= s[2] == s[3] && s[1] ==  s[2];
    cout << (ok ? "Yes\n"  : "No\n");
}

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

    int t = 1;
//    cin >> t;
    while (t--) {
       oneCase();
    }

    return 0;
}


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

using namespace std;


int main(int argc, char *argv[])
{
  int dx[4] = {1,0,-1,0};
  int dy[4] = {0,1,0,-1};
  int H,W,x,y;
  char tmp;
  int w_count = 0;
  queue<int> queue_x,queue_y;
  cin >> H >> W;
  vector<vector<int> > c(H,vector<int>(W));
  vector<vector<int> > visited(H,vector<int>(W));
  for (int i = 0; i < H; i++) {
    for (int j = 0; j < W; j++) {
      cin >> tmp;
      if(tmp == '#')
        c.at(i).at(j) = 0;
      else{
        c.at(i).at(j) = 1;
        w_count++;
      }
      visited.at(i).at(j) = 0;
    }
  }
  //迷路の確認
  //for (int i = 0; i < H; i++) {
  //  for (int j = 0; j < W; j++) {
  //    cout << c.at(i).at(j);
  //  }
  //  cout << endl;
  //}
  queue_x.push(0);
  queue_y.push(0);
  visited.at(0).at(0) = 1;
  while(!queue_x.empty() && !queue_y.empty()){
    x = queue_x.front();
    y = queue_y.front();
    //cout << "x: " << x << " y: " << y << endl;
    queue_x.pop();queue_y.pop();
    for (int n = 0; n < 4; n++) {
      if(x+dx[n] >= 0 && x+dx[n] < H && y+dy[n] >= 0 && y+dy[n] < W &&
          c.at(x+dx[n]).at(y+dy[n]) == 1 &&
          visited.at(x+dx[n]).at(y+dy[n]) == 0){
        queue_x.push(x+dx[n]);
        queue_y.push(y+dy[n]);
        visited.at(x+dx[n]).at(y+dy[n]) = visited.at(x).at(y) + 1;
      }
    }
  }
  //for (int i = 0; i < H; i++) {
  //  for (int j = 0; j < W; j++) {
  //    cout << visited.at(i).at(j);
  //  }
  //  cout << endl;
  //}
  if(visited.at(H-1).at(W-1) == 0)
    cout << -1 << endl;
  else
    cout << w_count - visited.at(H-1).at(W-1) << endl;
  return 0;
}


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

int main()
{
    int n, k;
    cin >> n >> k;
    string s;
    cin >> s;
    
    vector<int> arr;
    if (s[0] == '0') arr.push_back(0);
    int cnt = 1;
    for (int i = 1; i != n; ++i)
    {
        if (s[i] != s[i - 1])
        {
            arr.push_back(cnt);
            cnt = 1;
        }
        else ++cnt;
    }
    arr.push_back(cnt);
    if (s[n - 1] == '0') arr.push_back(0);
    
    if (arr.size() - 1 < 2 * k)
    {
        cout << n << endl;
        return 0;
    }
    int ans = 0;
    int curr = arr[0];
    int j = 1;
    for (int i = 1; i != arr.size(); i += 2)
    {
        curr += arr[i] + arr[i + 1];
        if (i - j == k << 1)
        {
            curr -= arr[j] + arr[j - 1];
            j += 2;
        }
        ans = max(ans, curr);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 1020
#include<iostream>
using namespace std;
 
int main(int, char**)
{
    int n;
 
    cin >> n;
 
    long long result = 0;
    for (int i = 1; i <= n; i++)
        if (i % 3 != 0 && i % 5 != 0) result += i;
 
    cout << result << endl;
 
    return 0;
}

Measured memory_bytes: 3636
n,c,k=map(int,input().split())
t=[int(input())for i in range(n)]
cnt=0
ans=[]
t.sort()
ans.append(t[0])
for i in range(1,n):
    if t[i]<=ans[0]+k and len(ans)<c:
        ans.append(t[i])
    else:
        ans=[]
        cnt+=1
        ans.append(t[i])
print(cnt+1)


Measured memory_bytes: 7384
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int X,Y,Z;
    cin >> X >> Y >> Z;
    int remain = X % (Y + Z);
    if(remain >= Z)
        cout << X / (Y + Z);
    else    
        cout << X / (Y + Z) - 1;
    cout << '\n';
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std ;
long long arr[89] ;
int main()
{
    arr[0] = 2 ;
    arr[1] = 1 ;
 
    for(int i = 2 ; i <= 86 ; i++)
    {
        arr[i] = arr[i-1] + arr[i-2] ;
        //cout << arr[i] << endl ;
    }
    int n ;
    cin >> n ;
    cout << arr[n] << endl ;
 
}

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

int main(){
	int n,d;
	cin >> n >> d;
	int i=0;
	while(n > (d*2+1) * i){
		i++;
	}
	cout << i << endl;
	return 0;
}



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

int main() {
    int a, b;
    cin >> a >> b;
    
    int count = 0;
    int ans = 0;
    while(count < 2)
    {
        if (a > b)
        {
            ans += a;
            a -= 1;
        }
        else if (b > a)
        {
            ans += b;
            b -= 1;
        }
        else
        {

            ans += a;
            a -= 1;

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





Measured memory_bytes: 256
check=dict()
N,z,d=0,[],0
#ttfは235、chaはabc

def dfs_sub(n,ttf,cha):
    global check,d

    #-1ずつしていく場合
    check[0]=min(check[n]+n*d,check[0])

    #最寄りまで-してく場合
    x1,x2=n//ttf,n%ttf
    if x1 in check:
        if check[x1]>check[n]+x2*d+cha:
            check[x1]=check[n]+x2*d+cha
            dfs(x1)
    else:
        check[x1]=check[n]+x2*d+cha
        dfs(x1)

    #最寄りまで+1してく場合
    x1,x2=n//ttf+1,ttf-n%ttf
    if x1 in check:
        if check[x1]>check[n]+x2*d+cha:
            check[x1]=check[n]+x2*d+cha
            dfs(x1)
    else:
        check[x1]=check[n]+x2*d+cha
        dfs(x1)


def dfs(n):
    global z
    for i,j in z:
        dfs_sub(n,i,j)

t=int(input())
for i in range(t):
    N,*b,d=map(int,input().split())
    z=list(zip([2,3,5],b))
    check={N:0,0:N*d}
    dfs(N)
    print(check[0])


Measured memory_bytes: 138908
import sys
def input(): return sys.stdin.readline().rstrip()

def main():
    X, Y, A, B, C = map(int, input().split())
    p = sorted(map(int, input().split()), reverse=True)
    q = sorted(map(int, input().split()), reverse=True)
    r = list(map(int, input().split()))

    print(sum(sorted(p[:X] + q[:Y] + r, reverse=True)[:X+Y]))

if __name__ == '__main__':
    main()


Measured memory_bytes: 23328
#include <bits/stdc++.h>
 
#define _overload(_1,_2,_3,name,...) name
#define _rep(i,n) _range(i,0,n)
#define _range(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
#define rep(...) _overload(__VA_ARGS__,_range,_rep,)(__VA_ARGS__)
 
#define _rrep(i,n) _rrange(i,n,0)
#define _rrange(i,a,b) for(int i=(int)(a)-1;i>=(int)(b);--i)
#define rrep(...) _overload(__VA_ARGS__,_rrange,_rrep,)(__VA_ARGS__)
 
#define _all(arg) begin(arg),end(arg)
#define uniq(arg) sort(_all(arg)),(arg).erase(unique(_all(arg)),end(arg))
#define bit(n) (1LL<<(n))
 
// #define DEBUG
 
#ifdef DEBUG
    #define dump(...) fprintf(stderr, __VA_ARGS__)
#else
    #define dump(...)
#endif
 
template<class T>bool chmax(T &a, const T &b) { return (a<b)?(a=b,1):0;}
template<class T>bool chmin(T &a, const T &b) { return (b<a)?(a=b,1):0;}
 
using namespace std;
using ll=long long;
using vi=vector<int>;
using vll=vector<ll>;
 
const double EPS = 1e-10;
const double PI = acos(-1.0);
const int inf = INT_MAX;
const ll INF = LLONG_MAX;
const ll MOD = 1000000007LL;
const int dx[4]={1,0,-1,0};
const int dy[4]={0,1,0,-1};
 
ll extgcd(ll a,ll b,ll& x,ll& y){x=1,y=0;ll g=a;if(b!=0) g=extgcd(b,a%b,y,x),y-=a/b*x;return g;}
ll ADD(const ll &a, const ll &b, const ll mod=MOD) { return (a+b)%mod;}
ll SUB(const ll &a, const ll &b, const ll mod=MOD) { return (a-b+mod)%mod;}
ll MUL(const ll &a, const ll &b, const ll mod=MOD) { return (1LL*a*b)%mod;}
ll DIV(const ll &a, const ll &b, const ll mod=MOD) {ll x,y; extgcd(b,mod,x,y);return MUL(a,(x+mod)%mod,mod);}
 
int main(void){
    cin.tie(0);
    ios::sync_with_stdio(false);

    int n; cin >> n;
    int res = 0;
    rep(i, 1, n+1){
        int cnt = 0;
        int x = i;
        while(x > 0){
            x /= 10;
            cnt++;
        }
        if(cnt % 2 == 1){
            res++;
        }
    }
    
    cout << res << endl;

    return 0;
}


Measured memory_bytes: 256
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    int M = sc.nextInt();
    int[] A = new int[M];
    for (int i = 0; i < M; i++) {
      A[i] = sc.nextInt();
    }
    Main abc118D = new Main();
    System.out.println(abc118D.solve(N, M, A));
  }

  public String solve(int N, int M, int[] A) {
    ABC118DSolve abc118DSolve = new ABC118DSolve(A);
    return abc118DSolve.solve(N);
  }

  class ABC118DSolve {
    int[] dp = new int[10001];
    int[] costs = {2, 5, 5, 4, 5, 6, 3, 7, 6};
    int[] A;
    Map<Integer, Integer> numCosts = new HashMap();

    public ABC118DSolve(int[] A) {
      this.A = A;
      Arrays.fill(dp, -1);
      Arrays.sort(this.A);
      for (int i = 0; i < this.A.length; i++) {
        numCosts.put(costs[this.A[i] - 1], this.A[i]);
      }
      dp[0] = 0;
      for (Map.Entry<Integer, Integer> numCost : numCosts.entrySet()) {
        dp[numCost.getKey()] = 1;
      }
    }

    public String solve(int N) {
      for (int i = 1; i <= N; i++) {
        for (Map.Entry<Integer, Integer> numCost : numCosts.entrySet()) {
          int cost = numCost.getKey();
          if (i > cost && dp[i - cost] > 0) {
            dp[i] = Math.max(dp[i], dp[i - cost] + 1);
          }
        }
      }
      StringBuilder sb = new StringBuilder();
      while(N > 0){
        for(int i = this.A.length -1; i >= 0; i--){
          int cost = this.costs[this.A[i]-1];
          if(N-cost >= 0 && dp[N] - 1 == dp[N-cost]) {
            sb.append(this.A[i]);
            N -= cost;
            break;
          }
        }
      }
      return sb.toString();
    }
  }
}


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

#define ll long long
#define Fi first
#define Se second
#define Pb push_back
#define vi vector<int>
#define vp vector<pair<int,int>>
#define vvi vector<vector<int>>
#define vvp vector<vector<pair<int,int>>>

const int INF = 1e9;
const int MOD = 1e9+7;
using Graph = vector<vector<int>>; //Caution!! Segmentation Fault!! Don't forget to add +1!

#define all(v) v.begin(),v.end()
#define output_s(a) printf("%s\n",(a).c_str())

#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define Rep(i,n,m) for(int i=(int)(n);i<(int)(m);i++)
#define RepS(i,n,m) for(int i=(int)(n);i<=(int)(m);i++)
#define RRepS(i,n,m) for(int i=(int)(n);i>=(int)(m);i--)
#define RepA(x) for(auto &item:(x))

void CINT(){}
template <class Head,class... Tail>
void CINT(Head&& head,Tail&&... tail){
    cin>>head;
    CINT(move(tail)...);
}    
#define CIN(...) int __VA_ARGS__;CINT(__VA_ARGS__)
#define LCIN(...) ll __VA_ARGS__;CINT(__VA_ARGS__)
#define SCIN(...) string __VA_ARGS__;CINT(__VA_ARGS__)

template<typename TypeInt> //最大公約数
TypeInt GCD(TypeInt a,TypeInt b){
    if(a%b==0) return b;
    else return GCD(b,a%b);
}
template<typename TypeInt> //最小公倍数
TypeInt LCM(TypeInt a,TypeInt b){
    return a*b/GCD(a,b);
}

int IN_int(){
    int x;
    scanf("%d",&x);
    return x;
}

//library----------------------------------------------

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

const int NMAX = 100;
bool flag;


int main(){
    SCIN(x);
    int s=0,n=0,e=0,w=0;
    rep(i,x.size()){
        if(x[i]=='N') n+=1;
        else if(x[i]=='S') s+=1;
        else if(x[i]=='E') e+=1;
        else if(x[i]=='W') w+=1;
    }
    flag=false;
    if((n>0&&s>0)&&(e>0&&w>0))flag=true;
    else if((n>0&&s>0)&&(e==0&&w==0))flag=true;
    else if((n==0&&s==0)&&(e>0&&w>0))flag=true;

    printf(flag?"Yes":"No");
    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

int main(){
  char s;scanf("%s",&s);
  if(s=='A'){
    printf("%s","T");
  }else if(s=='T'){
    printf("%s","A");
  }else if(s=='C'){
    printf("%s","G");
  }else if(s=='G'){
    printf("%s","C");
  }
  return 0;
}

Measured memory_bytes: 128
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<queue>
#include<cmath>
#include<cstdio>
#include<tuple>
#include<bitset>

using namespace std;
//#define int long long
#define rep(i,n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<=n;++i)
#define ALL(x) x.begin(),x.end()
#define ll long long
const int inf=0;
const int MOD=1000000007;
struct Query{
  int tag;
  int i;
  char c;
  int l;
  int r;
};
class Seg_Tree{
    private:
    int n;
    vector<int> node;
    public:
    int process(int left,int right){
        return (left|right);
    }
    Seg_Tree(vector<int> v){
        int num=1;
        int size=v.size();
        while(num<size){
            num*=2;
        }
        n=num;
        node.resize(2*num-1,inf);
        for(int i=0;i<size;i++)node[i+num-1]=v[i];
        for(int i=n-2;i>=0;i--)node[i]=process(node[i*2+1],node[i*2+2]);
    }
    void update(int x,int val){
        x+=(n-1);
        node[x]=val;
        while(x>0){
            x=(x-1)/2;
            node[x]=process(node[x*2+1],node[x*2+2]);
        }
    }
    int out(int a,int b,int k=0,int l=0,int r=-1){
        if(r<0)r=n;
        if(a>=r||b<=l)return inf;
        if(a<=l&&b>=r)return node[k];
        int vl=out(a,b,k*2+1,l,(l+r)/2);
        int vr=out(a,b,k*2+2,(l+r)/2,r);
        if(k==0)return __builtin_popcount(process(vl,vr));
        else return process(vl,vr);
    }
};
signed main(){
  int n;cin>>n;
  string s;cin>>s;
  int q;cin>>q;
  vector<Query> query(q);
  rep(i,q){
    int a;cin>>a;
    query[i].tag=a;
    if(a==1){
      int B;cin>>B;
      char C;cin>>C;
      query[i].i=B;
      query[i].c=C;
    }
    else{
      int b,c;cin>>b>>c;
      query[i].l=b;
      query[i].r=c;
    }
  }
  Seg_Tree tree(vector<int>(n,inf));
  rep(i,n){
    int k=s[i]-'a';
    int bit=0;
    bit=(1ull<<k);
    tree.update(i+1,bit);
  }
  rep(i,q){
    if(query[i].tag==1){
      int bit=0;
      bit=(1ull<<(query[i].c-'a'));
      tree.update(query[i].i,bit);
    }
    else{
      if(n==1){
        cout<<1<<endl;
        continue;
      }
      int res=tree.out(query[i].l,query[i].r+1);
      cout<<res<<endl;
    }
  }
  return 0;
}


Measured memory_bytes: 7300
long M=1e9+7,s[1<<17],a,i,f;long p(long a,int b){return b?p(a,b-1)*a%M:1;}main(n){for(scanf("%d",&n);~scanf("%d",&a);s[a]++);for(f|=*s-n%2;++i<n;)f|=((n+i)%2?s[i]-2:s[i])?1:0;printf("%d\n",f?0:p(2,n/2));}

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

using namespace std;

#define sqr(x) ((x) * (x))
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()

typedef vector<int> vi;
typedef long long ll;

void solve() {
  string S;
  cin >> S;
  for (int i = 0; i < S.size() - 1; i++) {
    if (S[i] == S[i + 1]) {
      cout << "Bad" << endl;
      return;
    }
  }
  cout << "Good" << endl;
}

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

  solve();

  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long int 
#define pii pair<int,int> 
#define pb push_back
#define INF INT_MAX 
#define mod 1000000007ll
#define fi first
#define se second
#define f(i,p,q) for(int i=p;i<q;i++)
#define si(a) scanf("%d",&a)
#define sii(a,b) scanf("%d %d",&a,&b)
#define siii(a,b,c) scanf("%d %d %d",&a,&b,&c)
#define pi(a) printf("%d\n",a)
#define psi(a) printf(" %d",a)
#define poi(a) printf("%d",a)
#define sl(a) scanf("%lld",&a)
#define pl(a) printf("%lld\n",a)
#define Nline() printf("\n")
#define sstr(str) scanf("%s",str)
#define pstr(str) printf("%s\n",str)
#define SET(a) memset(a,-1,sizeof(a))
#define CLR(a) memset(a,0,sizeof(a))
#define vi vector<int>
#define vvi vector<vi>
#define all(v) (v).begin(),(v).end()
#define SORT(v) sort(all(v))
#define RSORT(v) sort(all(v), greater<int>())
#define ios ios::sync_with_stdio(false); cin.tie(0);cout.tie(NULL);
#define MAX(a, b) ((a) > (b) ? (a) : (b))
#define MIN(a, b) ((a) < (b) ? (a) : (b))
#define ABS(X) ( (X) > 0 ? (X) : ( -(X) ) )
#define S(X) ( (X) * (X) )
#define SZ(V) (int )V.size()
#define FORN(i, n) for(i = 0; i < n; i++)
#define FORAB(i, a, b) for(i = a; i <= b; i++)
#define ALL(V) V.begin(), V.end()
#define IN(A, B, C)  (B) <= (A) && (A) <= (C)
#define AIN(A, B, C) assert(IN(A, B, C))
ll power(ll x, unsigned int y) {ll res = 1;	while (y > 0) { if (y & 1) res = res*x%mod; y = y>>1; x = x*x;} return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
void solve(){
    int n;cin>>n;
    vi ar(n+2);
    ar[0]=1000000;
    ar[n+1]=-1000;
    f(i,1,n+1)cin>>ar[i];
    ll ans=1000;
    ll stocks=0;
    f(i,1,n+1){
      // if stocks are 0
    	if(stocks==0 && ar[i-1]>=ar[i] && ar[i]<=ar[i+1]){
    		ll number =ans/ar[i];
    		stocks+=number;
    		ans-=number*(ar[i]);
    	}
    	else if(ar[i-1]>ar[i] && ar[i]<ar[i+1]){
    		ll number =ans/ar[i];
    		stocks+=number;
    		ans-=number*(ar[i]);
    	}else if(ar[i-1]<=ar[i] && ar[i]>=ar[i+1]){
    		ans+=stocks*(ar[i]);
    		stocks=0;
    	}
    	
    }
    cout<<ans<<"\n";
}
int main() {
    ios;
	int t=1;
	//cin>>t;
	while(t--)solve();
 
    
}


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

int main(){

	char ch;
	int counter[26] = {};

	while(cin >> ch){
		if(islower(ch)) counter[ch - 'a']++;
		if(isupper(ch)) counter[ch - 'A']++;
	}

	for(int i = 0; i < 26; i++){
		char ch2 = i + 'a';
		cout << ch2 << " : "<< counter[i] << endl;
	}

	return 0;
}

Measured memory_bytes: 1140
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define PI 3.141592653589793
#define rep(i, n) for (int i = 0; i < (n); i++)
#define REP(i, a, n) for (int i = a; i < (n); i++)
#define rrep(i, n, k) for (int i = (n); i >= (k); i--);
#define all(x) (x).begin(), (x).end()
#define vi vector<int>
template<class T> istream &operator>>(istream&is,vector<T>&v){for(auto &elemnt:v)is>>elemnt;return is;}
template<class T,class U> istream &operator>>(istream&is,pair<T,U>&p){is>>p.first>>p.second;return is;}
template<class T>vector<T> make_vector(size_t a){return vector<T>(a);}
template<class T, class... Ts>auto make_vector(size_t a, Ts... ts){return vector<decltype(make_vector<T>(ts...))>(a, make_vector<T>(ts...));}
const int inf = 6e18;
const int mod = 1e9 + 7;

signed main() {
    int N, K, S;
    cin >> N >> K >> S;
    int count = 0;
    for (int i = 0; i < N; i++) {
        if (count < K) {
            cout << S << (i == N - 1 ? '\n' : ' ');
            ++count;
        } else {
            if (S ==(int)1e9) {
                cout << 1 << (i == N - 1 ? '\n' : ' ');
            } else {
                cout << S + 1 << (i == N - 1 ? '\n' : ' ');
            }

        }
    }
}

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


int main()
{
    double w,h,x,y,n,i,j,k;
    cin>>w>>h>>x>>y;
    int f=0; if((w/2)==x && (h/2)==y) f=1;
    cout<<fixed<<setprecision(10)<<(w*h)/2<<" "<<f;

    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define N 200000
#define mod1 1000000007
#define mod2 1000000009
#define mod3 998244353
#define endl '\n'
#define IO ios_base::sync_with_stdio(false);cin.tie(NULL);

int main()
{
    IO
	clock_t begin = clock();
    ll n,k;
    cin>>n>>k;
    ll a[n+1];
    for(ll i=1;i<=n;i++)
    	cin>>a[i];
    ll dp[n+1][k+1],dp1[n+1][k+1];
    for(ll i=0;i<=n;i++)
    {
    	for(ll j=0;j<=k;j++)
    	{
    		dp[i][j] = dp1[i][j] = 0;
    	}
    }
    for(ll i=0;i<=a[n];i++)
    	dp[n][i] = 1;
    dp1[n][0] = dp[n][0];
    for(ll i=1;i<=k;i++)
    	dp1[n][i] = dp[n][i] + dp1[n][i-1];
    for(ll i=n-1;i>=1;i--)
    {
    	for(ll j=0;j<=k;j++)
    	{
    		dp[i][j] = ((dp1[i+1][j] - ((j-a[i]-1)>=0?dp1[i+1][j-a[i]-1]:0))%mod1 + mod1)%mod1;;
    	}
    	dp1[i][0] = dp[i][0];
    	for(ll j=1;j<=k;j++)
    		dp1[i][j] = (dp[i][j] + dp1[i][j-1])%mod1;;
    }
    // for(ll i=1;i<=n;i++)
    // {
    // 	for(ll j=0;j<=k;j++)
    // 		cout<<dp[i][j]<<' ';
    // 	cout<<endl;
    // }
    cout<<dp[1][k]<<endl;
    // cout<<double(clock() - begin)/CLOCKS_PER_SEC<<endl;
    return 0;
}

Measured memory_bytes: 161284
#include <algorithm>
#include <bitset>
#include <climits>
#include <cmath>
#include <deque>
#include <iostream>
#include <iomanip>
#include <locale>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>

using namespace std;

int INT_MAX_SQRT = sqrt(INT_MAX);
int pwi(int x, int p) {
    if (p == 0) return 1;
    if (p == 1) return x;
    int tmp = pwi(x, p / 2);
    if (tmp > INT_MAX_SQRT) return 0;  // overflow
    if (p % 2 == 0)
        return tmp * tmp;
    else
        return tmp * tmp * x;
}

long LONG_MAX_SQRT = sqrt(LONG_MAX);
long pwl(long x, long p) {
    if (p == 0) return 1;
    if (p == 1) return x;
    long tmp = pwl(x, p / 2);
    if (tmp > LONG_MAX_SQRT) return 0;  // overflow
    if (p % 2 == 0)
        return tmp * tmp;
    else
        return tmp * tmp * x;
}

map<long, long> factorization(long N) {
    map<long, long> res;
    long SQRT_N = ceil(sqrt(N));
    for (long i = 2; i < SQRT_N; i++) {
        while (N % i == 0) {
            if (res.find(i) == res.end()) {
                res[i] = 1;
            } else {
                res[i] += 1;
            }
            N /= i;
        }
    }
    if (N > SQRT_N) res[N] = 1;
    return res;
}

void debug_vec(string name, vector<int> vec) {
    cout << name << endl;
    for (auto e: vec) cout << e << endl;
}

void debug_vec(string name, vector<long> vec) {
    cout << name << endl;
    for (auto e: vec) cout << e << endl;
}

void debug_mat(string name, vector<vector<long>> mat) {
    cout << name << endl;
    for (auto vec: mat) {
        for (auto e: vec) cout << e << "   ";
        cout << endl;
    }
}

int main() {
    int D;
    cin >> D;
    int I = 26;

    vector<int> C(I);
    for (int i = 0; i < I; i++) cin >> C[i];

    vector<vector<int>> S(D, vector<int>(I));
    for (int d = 0; d < D; d++) {
        for (int i = 0; i < I; i++) {
            cin >> S[d][i];
        }
    }

    vector<int> L(I, 1);
    for (int d = 0; d < D; d++) {
        for (int i = 0; i < I; i++) {
            S[d][i] -= L[i] * C[i];
            L[i]++;
        }
        int ind = distance(S[d].begin(), max_element(S[d].begin(), S[d].end()));
        L[ind] = 1;
        cout << ind + 1 << endl;
    }

    return 0;
}


Measured memory_bytes: 3744
#include<iomanip>
#include <string>
#include<iostream>
#include<vector>
#include <bits/stdc++.h>
#include <stdio.h>
#include <numeric>
#include<math.h>
#include <ctype.h>
#include <algorithm> // sort
#include <map> // pair
using namespace std;
#define nin(n) int n; cin >> n;
int main(){
  long long int a,b;
  cin >> a >> b;
  long long int n=__gcd(a,b);
  long long  int ans=1;
  long long int t=sqrt(n)+1;
  for(long long int i=2;i*i<=n;i++){
    if(n%i==0){
      ans++;
      while(n%i==0){
      n=n/i;
      }
    }
  }
  if(n!=1) ans++;
  cout << ans << endl;
}


Measured memory_bytes: 256
using System;

namespace abc144_c
{
    class Program
    {
        static void Main(string[] args)
        {
            long n = long.Parse(Console.ReadLine());

            long n_sqrt = (long)Math.Round(Math.Sqrt(n));

            long i = 1;
            long j = 1;


            for (long index = n_sqrt; index >= 1; index--)
            {
                long a = n % index;
                if (a == 0)
                {
                    long b = n / index;
                    i = index;
                    j = b;

                    break;

                }



            }


            Console.WriteLine((i - 1) + (j - 1));
        }
    }
}


Measured memory_bytes: 13140
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <numeric>
#include <stdio.h>
#include <stack>
#include <queue>
#include <cstdio>
#include <cmath>
#include <iterator>
#include <map>
#include <fstream>
#include <list>
#include <cctype>

using namespace std;

#define Int int64_t

void printVec(std::vector<int>& vec) {
	std::cout << "";
	for (auto it = vec.begin(); it != vec.end(); ++it) {
		std::cout << *it << " ";
	}
	std::cout << std::endl;
}
void printVec1(std::vector<string>& vec) {
	std::cout << "";
	for (auto it = vec.begin(); it != vec.end(); ++it) {
		std::cout << *it << " ";
	}
	std::cout << std::endl;
}

template<typename T>
void remove(std::vector<T>& vector, unsigned int index)
{
	vector.erase(vector.begin() + index);
}

int vector_finder(std::vector<string> vec, string number) {
	auto itr = std::find(vec.begin(), vec.end(), number);
	size_t index = std::distance(vec.begin(), itr);
	if (index != vec.size()) { // 発見できたとき
		return 1;
	}
	else { // 発見できなかったとき
		return 0;
	}
}

#include <sstream> 
std::vector<std::string> StringSplit(const std::string& str, char sep)
{
	std::vector<std::string> v;
	std::stringstream ss(str);
	std::string buffer;
	while (std::getline(ss, buffer, sep)) {
		v.push_back(buffer);
	}
	return v;
}

Int gcd(Int a, Int b) {
	return b != 0 ? gcd(b, a % b) : a;
}
Int lcm(Int a, Int b) {
	return a * b / gcd(a, b);
}

bool comp(const string a, const string b) {
	return a.length() < b.length();
}


int main() {
	vector<int> mod(2019);
	for (int i = 0; i < 2019; i++) {
		mod[i] = i;
	}

	int over2019 = 0;
	Int l,r; cin >> l>>r;
	if (r - l >= 2019) over2019 = 1;

	r = r % 2019; l = l % 2019;
	//cout << l << " " << r << endl;

	int minz = 10000000;

	if (over2019 == 1) {
		cout << 0;
	}
	else {
		if (r - l > 0) {
			for (int i = l; i < r; i++) {
				for (int j = i+1; j <= r; j++) {
					minz = min(minz, (j % 2019 * i % 2019) % 2019);
				}
			}
			cout << minz;
		}
		else cout << 0;
	}

	




	cout << endl;
	return 0;
}

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

int main()
 {
  ll n,ans=0;
  cin>>n;
  for(ll i=2; i<=sqrt(n); i++)  // factorization , this way only primes divides the N
  {
    if(n%i==0)
    {
       ll cnt=0,prev=0;
       while(n%i==0)
       {
          cnt++;
          n/=i;
          if(cnt>prev)
          {
            ans++;
            prev=cnt;
            cnt=0;
          }
       }

    }
  }
if(n>1) // n itself is prime
  ans++;
cout<<ans<<endl;
return 0;
  }

Measured memory_bytes: 3684
#define _USE_MATH_DEFINES
#include<stdio.h>
#include<string>
#include<iostream>
#include<cctype>
#include<cstdio>
#include<vector>
#include<stack>
#include <algorithm>
#include<math.h>
#include<set>
#include<map>
#include<iomanip>

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



using namespace std;




int main() {

	vector<long long int> a(3);
	cin>>a[0]>>a[1]>>a[2];
	sort(a.begin(),a.end());
	for(int i=0;i<=2;i++){
		if(a[i]%2==0){
			cout<<"0"<<endl;
			return 0;
		}
	}
	cout<<a[1]*a[0]<<endl;
    return 0;
}

	
	


	

Measured memory_bytes: 256
//minamoto
#include<bits/stdc++.h>
#define R register
#define fp(i,a,b) for(R int i=(a),I=(b)+1;i<I;++i)
#define fd(i,a,b) for(R int i=(a),I=(b)-1;i>I;--i)
#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)
template<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,1:0;}
template<class T>inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;}
using namespace std;
typedef long long ll;
int h[15],a[15],vis[15],n,c,lim;
ll f[2][305][(1<<5)+5];double ans,pw;
void solve(){
	memset(f,0,sizeof(f));
	R int t=0;
	f[t][min(c*n,a[n]*n)][0]=1;
	fp(i,1,c*n-1)if(i%n){
		memset(f[t^1],0,sizeof(f[t^1]));
		R int to=i%n-1;
		fp(j,i,c*n)fp(k,0,lim-1)if(f[t][j][k]){
			f[t^1][j][k]+=f[t][j][k];
			if(k>>to&1^1)f[t^1][min(c*n,max(j,i+a[h[to+1]]*n))][k^(1<<to)]+=f[t][j][k];
		}
		t^=1;
	}
	ans+=f[t][c*n][lim-1];
}
void dfs(int dep){
	if(dep>=n)return solve();
	fp(i,1,n-1)if(!vis[i]){
		h[dep]=i,vis[i]=1;
		dfs(dep+1);
		vis[i]=0;
	}
}
int main(){
//	freopen("testdata.in","r",stdin);
	scanf("%d%d",&n,&c);
	fp(i,1,n)scanf("%d",&a[i]);
	sort(a+1,a+1+n),lim=(1<<(n-1));
	dfs(1);
	pw=1;fp(i,1,n-1)pw*=c;
	ans*=1.0/pw;
	pw=1;fp(i,2,n-1)pw*=i;
	ans*=1.0/pw;
	printf("%.12lf\n",ans);
	return 0;
}

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

struct Node{
    int n, d;
};

vector<int> g[200005];
bool visited[200005]={0};

int main(){
    int n, m;
    cin >> n >> m;
    for(int i=0;i<m;++i){
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }

    queue<Node> que;
    que.push((Node){1, 0});
    visited[1] = true;
    while(!que.empty()){
        Node curr = que.front(); que.pop();
        if(curr.n == n){
            cout << "POSSIBLE" << endl;
            return 0;
        }
        for(int i=0;i<g[curr.n].size();++i){
            if(!visited[g[curr.n][i]] && curr.d < 2){
                que.push((Node){g[curr.n][i], curr.d + 1});
            }
        }
    }

    cout << "IMPOSSIBLE" << endl;

    return 0;
}


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

#define rep(i, n) for(int (i) = 0; (i) < (n); (i)++)
#define repn(i, n) for(int (i) = 1; (i) <= (n); (i)++)
#define repr(i, n) for(int (i) = (n-1); (i) >= 0; (i)--)
#define all(x) (x).begin(), (x).end()
#define lint long long
#define ulint unsigned long long
#define fi first
#define se second
#define setpre(x) cout << fixed << setprecision(x)
#define ii(x) int x; cin >> (x)
#define ii2(x, y) int x, y; cin >> (x) >> (y)
#define ii3(x, y, z) int x, y, z; cin >> (x) >> (y) >> (z)
#define out(x) cout << (x) << endl
#define yn(x) cout << ((x)?("Yes"):("No")) << endl
#define YN(x) cout << ((x)?("YES"):("NO")) << endl
#define bit_c(x) __builtin_popcountll(x)

inline void logger(){ cout << endl; }
template<typename A, typename... B>
void logger(const A& a, const B&... b){
    cout << a << " , ";
    logger(b...);
}

typedef pair<lint, lint> P;
const lint MOD = 1000000007;
const lint MOD9 = 998244353;
const lint INF = MOD * MOD;
const int MAX = 100005;

/* ...o(^-^)o... */

lint dp[105][5][2];

int main(){
    string n; int k; cin >> n >> k;
    int d = n.size();
    repn(i, d){
        int l = n[i-1] - '0';
        if(i == 1){
            dp[1][0][0] = 0; dp[1][0][1] = 1;
            dp[1][1][0] = 1; dp[1][1][1] = l-1;
            continue;
        }
        dp[i][0][1] = 1;
        repn(j, k){
            if(l != 0){
                dp[i][j][0] = dp[i-1][j-1][0];
                dp[i][j][1] = dp[i-1][j-1][0] * (l-1) + dp[i-1][j-1][1] * 9 + dp[i-1][j][0] + dp[i-1][j][1];
            }
            else{
                dp[i][j][0] = dp[i-1][j][0];
                dp[i][j][1] = dp[i-1][j-1][1] * 9 + dp[i-1][j][1];
            }
        }
    }
    out(dp[d][k][0] + dp[d][k][1]);
}


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


int main()
{
    int N, A, B, C, D;
    cin >> N >> A >> B >> C >> D;
    --A, --B, --C, --D;
    string S;
    cin >> S;


    string ans = "Yes";
    for( int i = A+1; i < max(C, D); ++i ){
        if( S[i] == '#' and S[i-1] == '#' ){
            ans = "No";
            break;
        }
    }

    if( D < C ){  // A が B を追い越すので ... が必要
        bool isThreeDots = false;
        for( int i = B; i <= D; ++i ){
            if( S[i-1] == '.' and S[i] == '.' and S[i+1] == '.' ){
                isThreeDots = true;
                break;
            }
        }
        if( !isThreeDots ) ans = "No";
    }

    cout << ans << endl;


    return 0;
}

Measured memory_bytes: 640
#include <iostream>
#include <cmath>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <set>

using namespace std;
using Data = pair<long long, vector<int>>;
typedef long long ll;

int main() {
    ll K;
    vector<ll> N(3);
    for(int i=0;i<3;i++){
        cin >> N[i];
    }
    cin >> K;
    vector<vector<ll>> v(3);
    for(int i=0;i<3;i++){
        v[i].resize(N[i]);
        for(int j=0;j<N[i];j++){
            cin >> v[i][j];
        }
        sort(v[i].rbegin(),v[i].rend());
    }
    priority_queue<Data> q;
    set<Data> se;
    q.push(Data(v[0][0]+v[1][0]+v[2][0],vector<int>({0,0,0})));
    for(int k=0;k<K;k++){
        auto c=q.top();q.pop();
        cout << c.first << endl;
        for(int i=0;i<3;i++){
            if(c.second[i]+1<N[i]){
                ll sum = c.first-v[i][c.second[i]] + v[i][c.second[i]+1];
                auto num = c.second; 
                num[i]++;
                auto d = Data(sum,num);
                if(!se.count(d)){
                    se.insert(d);
                    q.push(d);
                }
            }
        }
    }
}

Measured memory_bytes: 1408
// #pragma GCC optimize("O3,no-stack-protector")
// 実数の場合
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC target("avx")
// AtCoder新ジャッジ以降
// #pragma GCC target("avx2")
#pragma GCC optimize("unroll-loops")
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define dump(x) cout << x << endl
typedef int64_t Int;

using namespace std;
using Graph = vector<vector<Int>>;

const double pi = M_PI;
const Int MOD = 1000000007;

bool isOK(const vector<Int> &A, int index, Int key) {
    if (A[index] < key) {
        return true;
    } else {
        return false;
    }
}

int b_search(const vector<Int> &A, Int key) {
    int ng = -1;
    int ok = (int)A.size();

    while (ok - ng > 1) {
        int mid = ng + (ok - ng) / 2;

        if (isOK(A, mid, key)) {
            ok = mid;
        } else {
            ng = mid;
        }
    }

    return ok;
}

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

    int n;
    cin >> n;
    vector<Int> a(n), ans(n, -1);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    ans[0] = a[0];
    int color = 1;
    for (int i = 1; i < n; i++) {
        auto index = b_search(ans, a[i]);
        if (ans[index] == -1) {
            ans[color] = a[i];
            color++;
        } else {
            ans[index] = a[i];
        }
    }

    cout << color << endl;

    return 0;
}


Measured memory_bytes: 1792
N = int(input())
ans = N*(N-1)
mod = 10**9 + 7
ans %= mod
ans = 1
A = 1
B = 1
C = 1
for i in range(N):
    A *= 10
    B *= 9
    C *= 8
    A %= mod
    B %= mod
    C %= mod

print((A-B*2+C) % mod)


Measured memory_bytes: 9180
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
#define rep(i,s,e) for(int (i) = (s);(i) <= (e);(i)++)
#define all(x) x.begin(),x.end()

int main() {
  int n, k;
  string s;
  cin >> n >> k >> s;
  k--;
  s[k] = s[k] - 'A' + 'a';
  cout << s << endl;
}


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

int main() {
  int N;
  cin >> N;
  
  int z=0;
  
  
  
  for (int i=0 ; i < N ; i++) {
    
    int x,y;
    cin >> x >> y;
    z += y-x+1;
  }
  cout << z << endl;
}

Measured memory_bytes: 256
/******************************************
*    AUTHOR:         julianferres         *
******************************************/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll,ll> ii;
#define FIN ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define forr(i, a, b) for(int i = (a); i < (int) (b); i++)
#define forn(i, n) forr(i, 0, n)
#define pb push_back
#define mp make_pair
#define all(c) (c).begin(),(c).end()
#define DBG(x) cerr << #x << " = " << (x) << endl
#define esta(x,c) ((c).find(x) != (c).end())
#define RAYA cerr << "===============================" << endl
const int INF = 2000000000;
#define MOD 1000000007
#define MAXN 200005



ll knapsack(ll x, vi wt, vi val, ll n)
{
    ll prev[x + 1];
    ll act[x + 1];
    forn(i, n + 1)
    {
        forn(w, x + 1)
        {
            if (i == 0 || w == 0)
                act[w] = 0;
            else if (wt[i - 1] <= w)
                act[w] = max(val[i - 1] + prev[w - wt[i - 1]], prev[w]);
            else
                act[w] = prev[w];
        }
        forn(l, x + 1) prev[l] = act[l];
    }
    return prev[x];
}

int main(){
    FIN;
    ll n, w;
    cin >> n >> w;
    vi val(n), wt(n);
    forn(i, n) cin >> wt[i] >> val[i];

    ll ans = knapsack(w, wt, val, n);
    cout << ans << endl;

    return 0;
}


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

int main()
{
    int N;
    vector<int> X;
    cin >> N;
    istream_iterator<int> in_begin(cin);
    copy_n(in_begin, N, back_inserter(X));
    array<int, 100> vital_sums;

    for (int i = 1; i <= 100; ++i)
    {
        vital_sums[i - 1] = accumulate(
            X.begin(), X.end(), 0, [i](int acc, auto x) {
                return acc + (x - i) * (x - i);
            });
    }

    cout << *min_element(vital_sums.begin(), vital_sums.end()) << endl;
    return 0;
}


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

int main() {
  int a, b, kotae;
  char enzanshi;
  cin >> a;
  cin >> enzanshi;
  cin >> b;
  
  if (enzanshi == '+') 
    kotae = a + b;
  else if (enzanshi == '-')
    kotae = a - b;
  
  cout << kotae << endl;
  
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main()
{
	int n, x;
	while (cin >> n >> x, !(n == 0 && x == 0)) {
		int counter = 0;
		for (int i = 1; i <= n - 1; i++) {
			for (int j = i + 1; j <= n; j++) {
				int k = x - i - j;
				if (k <= n &&  k > j) {
					//cout << i << " " << j << " " << k << " " << i + j + k << endl;
					counter++;
				}
			}
		}
		cout << counter << endl;
	}
	return 0;
}

Measured memory_bytes: 1164
import sys

stdin = sys.stdin
inf = 1 << 60
mod = 1000000007

ni      = lambda: int(ns())
nin     = lambda y: [ni() for _ in range(y)]
na      = lambda: list(map(int, stdin.readline().split()))
nan     = lambda y: [na() for _ in range(y)]
nf      = lambda: float(ns())
nfn     = lambda y: [nf() for _ in range(y)]
nfa     = lambda: list(map(float, stdin.readline().split()))
nfan    = lambda y: [nfa() for _ in range(y)]
ns      = lambda: stdin.readline().rstrip()
nsn     = lambda y: [ns() for _ in range(y)]
ncl     = lambda y: [list(ns()) for _ in range(y)]
nas     = lambda: stdin.readline().split()

n = ni()

def digit(x):
    res = 1
    while x // 10 != 0:
        x //= 10
        res += 1
    return res

ans = digit(n)
i = 2
while i * i <= n:
    if n % i == 0:
        ans = min(ans, digit(n // i))
    i += 1

print(ans)

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

int main() {
  int W, H, N;
  cin >> W >> H >> N;

  vector<vector<int>> board(W, vector<int>(H, true));

  for (int i = 0; i < N; i++) {
    int x, y, a;
    cin >> x >> y >> a;

    // 長方形の x < xi を満たす領域
    if (a == 1) {
      for (int i = 0; i < x; i++) {
        for (int j = 0; j < H; j++) {
          board.at(i).at(j) = false;
        }
      }
    // 長方形の x > xi を満たす領域
    } else if (a == 2) {
      for (int i = x; i < W; i++) {
        for (int j = 0; j < H; j++) {
          board.at(i).at(j) = false;
        }
      }
    // 長方形の y < yi を満たす領域
    } else if (a == 3) {
      for (int i = 0; i < W; i++) {
        for (int j = 0; j < y; j++) {
          board.at(i).at(j) = false;
        }
      }
    // 長方形の y > yi を満たす領域
    } else if (a == 4) {
      for (int i = 0; i < W; i++) {
        for (int j = y; j < H; j++) {
          board.at(i).at(j) = false;
        }
      }
    } else {
      cout << "error" << endl;
      return 1;
    }
  }

  int ans = 0;
  for (auto v : board) {
    for (auto b : v) {
      if (b) {
        ans++;
      }
    }
  }

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

Measured memory_bytes: 256
#include <iostream>
using namespace std;
int v[100001];
int main(){
  int N, M; cin >> N >> M;
  for (int i = 0; i < M; i++){
    int a, b; cin >> a >> b;
    v[a]++, v[b]++;
  }
  for (int i = 1; i <= N; i++){
    if (v[i]&1){
      cout << "NO" << endl;
      return 0;
    }
  }
  cout << "YES" << endl;
}

Measured memory_bytes: 640
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace AtCoder
{
	class Program
	{
		static void Main(string[] args)
		{
			var firstLine = Console.ReadLine().Split(' ').Select(value => long.Parse(value)).ToList();
			var n = firstLine[0];
			var a = firstLine[1];
			var b = firstLine[2];

			var cities = Console.ReadLine().Split(' ').Select(value => long.Parse(value)).ToList();

			long cost = 0;

			for(int i = 0; i < n - 1; i++)
			{
				cost += Math.Min(a * (cities[i + 1] - cities[i]), b);
			}

			Console.WriteLine(cost);
		}
	}
}


Measured memory_bytes: 20064
#include<iostream>
using namespace std;
int main(){
    long int n , m,k;
    cin >> n >> m >> k;
    
    if(k > n+m&&4*n*m<(k-n-m)*(k-n-m) ){
        cout << "Yes";
    }else{
        cout << "No";
    }
  return 0;
}


Measured memory_bytes: 256
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		HashMap<String, Integer> s = new HashMap<>();
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int max = 0;
		String in ;
		for(int i=0;i<n;i++) {
			in = sc.next();
			if(s.containsKey(in)) {
				s.put(in, s.get(in)+1);
			}else {
				s.put(in, 1);
			}
			max = Math.max(max, s.get(in));
		}

		ArrayList<String> out = new ArrayList<>();
		for( String key : s.keySet()) {
			if(s.get(key) == max) {
				out.add(key);
			}
		}
		Collections.sort(out);
		for(int i=0;i<out.size();i++) {
			System.out.println(out.get(i));
		}
	}
}


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

int main()
{
    ll N, A, B;
    cin >> N >> A >> B;
    ll AB = A + B;
    ll mod = N % AB;

    if (mod >= 0 && mod <= A)
    {
        cout << (N / AB * A) + mod << endl;
    }
    else
    {
        cout << (N / AB * A) + A << endl;
    }
}

Measured memory_bytes: 256