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

int main() {
    char s[101], t[101];
    cin>>s;
    cin>>t;
    sort(s, s+strlen(s));
    sort(t, t+strlen(t));
    reverse(t, t+strlen(t));
    if(strlen(s)<strlen(t)) {
        for(int i=0; i<strlen(s); i++) {
            if(s[i]<t[i]) {
                cout << "Yes" << endl;
                return 0;
            } else if(s[i]>t[i]) {
                cout<<"No"<<endl;
                return 0;
            }
        }
        cout<<"Yes"<<endl;
    } else{
        for(int i=0; i<strlen(t); i++) {
            if(s[i]<t[i]) {
                cout << "Yes" <<endl;
                return 0;
            }
        }
        cout<<"No"<<endl;
    }
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<map>
#include<set>
#define rep(i,n) for(int i=0;i<(n);i++)

using namespace std;

int main(){
    int n,a[10000];
    cin >> n;
    rep(i,n){
        cin >> a[i];
    }
    int ans;
    rep(j,n)rep(i,j){
        ans += a[i]*a[j];
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long 
// memo  fixed  setprecision(20);
using vvll = vector<vector<ll>>;
ll mod =1e9+7;
/*"itob" int to "N"base */           template<typename TypeInt> string itob(const TypeInt v, int base){static const char table[] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";string ret;static numeric_limits<TypeInt> t;TypeInt n = v;if (t.is_signed) {if (v < 0) n *= -1;}while (n >= base) {ret += table[n%base];n /= base;}ret += table[n];if (t.is_signed) {if (v < 0 && base == 10) ret += '-';}reverse(ret.begin(), ret.end());return ret;}
/*"chmin" a = MAX*/                  template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
/*"chmax" a = MIN*/                  template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
/*"ctoi"  char to int*/              int ctoi(char c) {return c-'0';}
/*"gcd"   MAX Euclidean */           ll gcd(ll a,ll b){if(b==0)return a; return gcd(b,a%b);}
    /*"lcm"   MIN*/                      ll lcm(ll a,ll b){ll g = gcd(a,b);return a/g*b;}
/*"primecheck"If prime,return true.*/bool primecheck(ll n){if(n < 2) return false;else{for(int i = 2; i * i <= n; i++){if(n % i == 0) return false;}return true;}}
string  reverserange(string s,ll a,ll b){reverse(s.begin()+a-1,s.begin()+b); return s;}
ll modpow(ll a,ll n, ll mod){ll res = 1;while(n>0){if (n%2==1){res = res * a % mod;}a = a * a % mod;n/=2;}return res;}
ll ncd(ll n,ll d){
    ll x = 1,y=1;
    for(int i=0;i<d;i++){
        x = x*(n-i)%mod;
        y = y*(i+1)%mod;
    }
    return x*modpow(y,mod-2,mod)%mod;
}
int main() {    
    srand(time(NULL));
    for(int j=0;j<10;j++){
    for(int i=0;i<26;i++){
        cout<<i+1<<endl;
    }
    }
    for(int i=0;i<1+26*4;i++){

          cout<<rand()%26+1<<endl;  
    }
}
    



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

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; }

using ll = long long;

const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
const int INF = 1<<30;
const ll mod = 1000000007LL;

int main() {
  ll N;
  cin>>N;
  vector<ll> v(N);
  for(ll i = 0; i < N; i++) cin>>v[i];
  map<ll,ll> m;
  for(ll i = 0; i < N; i++) m[v[i]]=i;
  sort(v.begin(),v.end());
  ll cnt = 0LL;
  for(ll i = 0; i < N; i++){
    ll t = i-m[v[i]];
    if(t%2LL!=0) cnt++;
  }
  cout<<cnt/2<<endl;
}

Measured memory_bytes: 7296
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vb = vector<bool>;
using vs = vector<string>;
using msi = map<string, int>;
using mii = map<int, int>;
using psi = pair<string, int>;
using pii = pair<int, int>;
using vlai = valarray<int>;
#define rep(i,n) for(int i=0;i<n;i++)
#define range(i,s,n) for(int i=s;i<n;i++)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define fs first
#define sc second
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define INF 1E9
#define LINF 1E18*5
#define EPS 1E-9
#define MOD 1000000007
#define PI 3.1415926535897932384

template<class S, class T>ostream& operator<<(ostream&os, pair<S, T>p) { os << "[" << p.first << ", " << p.second << "]"; return os; };
template<class S>auto&operator<<(ostream&os, vector<S>t) { bool a = 1; for (auto s : t) { os << (a ? "" : " ") << s; a = 0; } return os; }

//int dx[]={1,1,1,0,-1,-1,-1,0},dy[8]={1,0,-1,-1,-1,0,1,1,1};
//
constexpr ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }

class compare {
public:
	bool operator()(tuple<int, int> a, tuple<int, int> b) {
		return (get<1>(a) < get<1>(b));
	}

};

int main() {
	int n;
	cin >> n;
	cout << 1110-n << endl;
}


Measured memory_bytes: 256
#include <stdio.h>
int main(void){
    // Here your code !
    double a[100][100] = {0},b[100][100] = {0},c[100][100] = {0};
    int n,m,l;
    int i,j,k;
    
    scanf("%d%d%d",&n,&m,&l);
    for(i = 0;i < n;i++){
        for(j = 0;j < m;j++){
            scanf("%lf",&a[i][j]);
        }
    }
    for(i = 0;i < m;i++){
        for(j = 0;j < l;j++){
            scanf("%lf",&b[i][j]);
        }
    }
    for(i = 0;i < n;i++){
        for(j = 0;j < l;j++){
            for(k = 0;k < m;k++){
                c[i][j] += a[i][k]*b[k][j];
                if(k == m-1){
                    printf("%.0f",c[i][j]);
                    if(j == l-1){
                        puts("");
                    }
                    else{
                        printf(" ");
                    }
                }
            }
        }
    }
    return 0;
}

Measured memory_bytes: 908
#include <algorithm>
#include <cassert>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <vector>

#include <limits.h>

using namespace std;

typedef long long ll;

template<class T>
inline bool chmax(T &a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}

template<class T>
inline bool chmin(T &a, T b) {
    if(a > b) {
        a = b;
        return true;
    }
    return false;
}

const int INF = INT_MAX / 2;

vector<int> wes;
vector<int> eas;

int main(void) {
    int N;
    cin >> N;
    string S;
    cin >> S;
    const int slen = (int) S.size();

    for (int i = 0; i < slen; i++) {
        if (S[i] == 'E') {
            eas.push_back(i);
        } else {
            wes.push_back(i);
        }
    }

    int ans = INF;
    for (int i = 0; i < N; i++) {
        int cnt = 0;

        auto it_right = upper_bound(eas.begin(), eas.end(), i);
        cnt += distance(it_right, eas.end());
        auto it_left = lower_bound(wes.begin(), wes.end(), i);
        cnt += distance(wes.begin(), it_left);
        // printf("i: %d, right: %ld, left: %ld\n", i, distance(it_right, eas.end()), distance(wes.begin(), it_left));

        chmin(ans, cnt);
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 2812
#include <iostream>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <string>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <tuple>
#include <algorithm>
#include <functional>
#include <cstring>
#include <limits.h>
#define FOR(i,k,n)  for (int i=(k); i<(int)(n); ++i)
#define REP(i,n)    FOR(i,0,n)
#define FORIT(i,c)	for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define SZ(i) ((int)i.size())
#define pb          push_back
#define mp          make_pair
#define mt          make_tuple
#define get0(x)     (get<0>(x))
#define get1(x)     (get<1>(x))
#define get2(x)     (get<2>(x))
#define ALL(X)      (X).begin(),(X).end()
#define LLMAX       9223372036854775807LL
#define LLMIN       -9223372036854775808LL
#define IMAX        2147483647
#define IMIN        -2147483648
typedef long long LL;
using namespace std;

int main(void){
    LL N,M;
    cin>>N>>M;
    LL r=0;
    if(M-2*N>=0){
        r+=N;
        M-=N*2;
    }else{
        r+=M/2;
        M%=2;
    }
    r+=M/4;
    cout<<r<<endl;
     return 0;
}

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

using namespace std;

string s;
int a[50];

int main() {
    ios_base::sync_with_stdio(false);
    cin >> s;
    int len = s.length();
    for (int i = 0; i < len; ++i) {
        char c = s[i];
        int r = c - 'a';
        a[r]++;
    }
    for (int i = 0; i < 26; ++i) {
        if (a[i] == 0) {
            char c = 'z'- (25-i);
            cout << c << endl;
            return 0;
        }
    }
    cout << "None" << endl;
    return 0;
}


Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
struct A{
  string s;
  int n;
  bool operator<(const A&a)const{
    return s==a.s?n<a.n:s<a.s;
  }
};
int x,i;
string s;
main(){
  A a[1000];
  while(cin>>s>>x){
    a[i++]={s,x};
  }
  sort(a,a+i);
  
  cout<<a[0].s<<'\n'<<a[0].n;
  for(int j=1;j<i;++j){
    if(a[j].s==a[j-1].s)cout<<' '<<a[j].n;
    else cout<<'\n'<<a[j].s<<endl<<a[j].n;
  }
  cout<<endl;
}

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

int main() {
    //
    int n;
    long long waru = 1000000007;

    cin >> n;
    vector<int> vec(n);

    for (int i = 0; i < n; i++) cin >> vec.at(i);

    int kekka = 0;
    int x = 0;

    for (int i = 0; i < n; i++) {
        kekka = (kekka + (long long) vec.at(i) * x) % waru;
        x = (x + vec.at(i)) % waru;
    }

    cout << kekka;
    //
}

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


void solve(long long N, std::vector<long long> P, std::vector<long long> Q){
    vector<long long int> v(N);
    for (int i = 0; i < N; i++) {
        v[i] = i+1;
    }
    int idx_p = 0;
    int idx_q = 0;

    int i = 0;
    do {
        i++;
        if (P == v) {
            idx_p = i;
        }
        if (Q == v) {
            idx_q = i;
        }
    } while (next_permutation(v.begin(), v.end()));
    cout << abs(idx_p - idx_q) << endl;
}

// Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
int main(){
    long long N;
    scanf("%lld",&N);
    std::vector<long long> P(N);
    for(int i = 0 ; i < N ; i++){
        scanf("%lld",&P[i]);
    }
    std::vector<long long> Q(N);
    for(int i = 0 ; i < N ; i++){
        scanf("%lld",&Q[i]);
    }
    solve(N, std::move(P), std::move(Q));
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<sstream>
#include<fstream>
#include<string>
#include<vector>
#include<deque>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<algorithm>
#include<functional>
#include<utility>
#include<bitset>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<cstdio>
using namespace std;
long long n,a[444],dp[444][444];
int main()
{
	cin>>n;
	for(int i=0;i<n;i++)
	{
		cin>>a[i];
	}
	for(int i=n-1;i>=0;i--)
	{
		for(int j=i+1;j<n;j++)
		{
			dp[i][j]=1e18;
			long long ct=0;
			for(int k=i;k<=j;k++)
			{
				ct+=a[k];
			}
			for(int k=i;k<j;k++)
			{
				dp[i][j]=min(dp[i][j],ct+dp[i][k]+dp[k+1][j]);
			}
		}
	}
	cout<<dp[0][n-1]<<endl;
	return 0;
}

Measured memory_bytes: 1664
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int inf = 1000000000; 

int main(){
  string s;
  cin >> s;
  string a,b;
  a = s.substr(0,(s.size()-1)/2);
  b = s.substr((s.size()+3)/2-1);
  //cout << a << endl;
  //cout << b << endl;
  string t = s;
  for(int i=0; i<(t.size()+1)/2; i++){
    swap(t[i],t[t.size()-1-i]);
  }
  if(t != s){
    cout << "No" << endl;
    return 0;
  }
  string aa = a;
  for(int i=0; i<(aa.size()+1)/2; i++){
    swap(aa[i],aa[aa.size()-1-i]);
  }
  if(aa != a){
    cout << "No" << endl;
    return 0;
  }
  string bb = b;
  for(int i=0; i<(bb.size()+1)/2; i++){
    swap(bb[i],bb[bb.size()-1-i]);
  }
  if(bb != b){
    cout << "No" << endl;
    return 0;
  }
  cout << "Yes" << endl;
}

Measured memory_bytes: 256
// Charan Sriramula
 
#include<bits/stdc++.h>
using namespace std;
typedef long double ld;
typedef long long int ll;
 
const ll lg=22;
const ll N=1e5+5;
const ll M=5e8;
const ll INF=1e18;
const ll mod=1e9+7;
const double PI = 3.14159265358979323846;
 
#define is(n) scanf("%d",&n)
#define io(n) printf("%d\n",n)
#define ls(n) scanf("%lld",&n)
#define lo(n) printf("%lld\n",n)
 
#define f first
#define s second
#define pb(x) push_back(x)
#define pf(x) push_front(x)
#define mp(x,y) make_pair(x,y)
#define GCD(a,b) __gcd((a),(b))
#define all(v) v.begin(),v.end()
#define bits(x) __builtin_popcount(x)
#define LCM(a,b) ((a)*(b))/GCD((a),(b))
#define fast ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
template<typename T> T power(T x,T y,ll m){T ans=1;while(y>0){if(y&1LL) ans=(ans*x)%m;y>>=1LL;x=(x*x)%m;}return ans%m;}
 
inline ll mul(ll a, ll b, ll p){ return (a * 1ll * b) % p; }
inline ll sub(ll a, ll b, ll p){ ll c = a - b; if(c < 0) c += p; return c; }
inline ll add(ll a, ll b, ll p){ ll c = a + b; if(c > p) c -= p; return c; }
 
#define trace1(x)                cerr<<#x<<": "<<x<<endl
#define trace2(x, y)             cerr<<#x<<": "<<x<<" | "<<#y<<": "<<y<<endl
#define trace3(x, y, z)          cerr<<#x<<":" <<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl
#define trace4(a, b, c, d)       cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl
#define trace5(a, b, c, d, e)    cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<endl
#define trace6(a, b, c, d, e, f) cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<" | "<<#f<<": "<<f<<endl

ll n;
string s;
ll dp[N][14];

ll F(ll idx,ll rem)
{
    ll res=0;
    if(idx==n){return rem==5;}
    if(dp[idx][rem]!=-1){return dp[idx][rem];}
    if(s[idx]=='?')
    {
        for(ll i=0;i<=9;i++)
        {
            ll powx=power(10LL,n-idx-1,13LL)%13;
            powx=(powx*i)%13;
            powx%=13;
            res=add(res,F(idx+1,(rem+powx)%13),mod);
        }
    }
    else
    {
        ll powx=power(10LL,n-idx-1,13LL);
        powx=(powx*(s[idx]-'0'))%13;
        powx%=13;
        res=add(res,F(idx+1,(rem+powx)%13),mod);
    }
    return dp[idx][rem]=res;
}

int main()
{
    cin>>s;
    n=s.length();
    memset(dp,-1,sizeof(dp));
    cout<<F(0,0)<<endl;
}

Measured memory_bytes: 17664
#include "bits/stdc++.h"
using namespace std;

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

    int ans = 1;
    while(n--)
    {
        if(ans <= k)
        ans += ans;
        else
            ans += k;
    }
    cout<<ans;
    return 0;
}


Measured memory_bytes: 256
awk '$0=NR%2FS$NF' RS=\ |sort|uniq -c|sort -n|awk 's+=$1{$2?(b=a)>a=$1:(e=d)>d=$1;$2?c=$3:f=$3}END{print s-(c~f?a+e<b+d?b+d:a+e:a+d)}'

Measured memory_bytes: 11924
import static java.lang.Math.pow;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {

  public static void main(String[] args) throws IOException {
    BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

    int numOfDataset = Integer.parseInt(reader.readLine());
    for (int i = 0; i < numOfDataset; i++) {
      String[] sideLengths_Str = reader.readLine().split(" ");
      int[] sideLengths = new int[sideLengths_Str.length];
      for (int j = 0; j < sideLengths_Str.length; j++)
        sideLengths[j] = Integer.parseInt(sideLengths_Str[j]);

      Arrays.sort(sideLengths);

      if (pow(sideLengths[2], 2)
              == pow(sideLengths[1], 2) + pow(sideLengths[0], 2)) {
        System.out.println("YES");
      } else {
        System.out.println("NO");
      }
    }
  }

}

Measured memory_bytes: 20380
s=input()
k=int(input())
n=len(s)
cnt=1
ans=0
l=[]
for i in range(n-1):
  if s[i]==s[i+1]:
    cnt+=1
  else:
    l.append(cnt)
    cnt=1
l.append(cnt)
if len(l)==1:
  print(k*sum(l)//2)
else:
  if s[0]!=s[n-1]:
    for i in range(len(l)):
      ans+=k*(l[i]//2)
  else:
    for i in range(1,len(l)-1):
      ans+=k*(l[i]//2)
    ans+=(k-1)*((l[0]+l[len(l)-1])//2)
    ans+=l[0]//2+l[len(l)-1]//2
  print(ans)

Measured memory_bytes: 3064
dic = {"I":1,"V":5,"X":10,"L":50,"C":100,"D":500,"M":1000}

while(True):
    try:
        lis = list(input())
        ans = [dic[e] for e in lis]
        print(sum([-ans[i] if ans[i]<ans[i+1] else ans[i] for i in range(len(ans)-1)] + [ans[-1]]))
    except:
        break


Measured memory_bytes: 5564
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
C = [INT() for _ in range(N)]
dp = [0]*(N+1)
dp[0] = 1
dp2 = [-1]*(max(C)+1)  # 前に色iが出てきたインデックスを保存
for i in range(1, N+1):
	p = dp2[C[i-1]]  # 色C[i-1]が前に出てきたインデックス
	if i-p > 1 and p != -1:  # インデックスがあり，前の要素でない
		dp[i] += dp[p]
	dp2[C[i-1]] = i
	dp[i] += dp[i-1]
	dp[i] %= mod

print(dp[N])


Measured memory_bytes: 26736
#include<iostream>
#include<string>
#include<algorithm>
#include<stack>
#include<vector>
#include<math.h>
#include<utility>
#include<iomanip>

using namespace std;

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

	long long h;
	cin >> h;

	long long ans = 0;
	long long m = 1;
	while (h > 0) {
		ans += m;
		m *= 2;
		h /= 2;
	}
	cout << ans;
}

Measured memory_bytes: 256
n,m=map(int,input().split())
a=0
b=float('inf')
for i in range(m):
    l,r=map(int,input().split())
    if l >=a:
        a=l
    if r <=b:
        b=r
if a==b:
    print(1)
elif a>b:
    print(0)
else:
    print(b-a+1)

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

int main(){
  ll n;
  cin >> n;
  vector<ll> a(n);
  rep(i,n) cin >> a.at(i);
  sort(a.begin(),a.end());
  ll ans = 1;
  ll cnt = 1;
  ll pr=0;
  ll id;
  for(ll i=1;i<n;i++){
    ll diff = a.at(i) - a.at(i-1);
    if( diff == 0 ){
      cnt++;
      ans = max(ans,cnt);
    }else if( diff == 1 ){
      if( pr == 2 ){
        ans = max(ans,cnt);
        cnt = 1;
        pr = 0;
        if( i != n-1 ) i = id;
        else break;
       
      }else{
        pr++;
        cnt++;
        if( pr == 1 ){
          id = i;
          //cout << id << endl;
        }
        ans = max(ans,cnt);
      }
    }else{
      ans = max(ans,cnt);
      cnt = 1;
      pr = 0;
    }
  }
  
  cout << ans << endl;
      
  return 0;
}

Measured memory_bytes: 1024
#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#include <set>

using namespace std;
using ll = long long;
using ull = unsigned long long;
constexpr ll TEN(int n) { return (n==0) ? 1 : 10*TEN(n-1); }

int main() {
    ios::sync_with_stdio(0);
    int n, q;
    cin >> n >> q;
    //cout << n << " " << q << endl;
    using P = pair<int, ll>;
    set<P> s;
    s.insert(P(-1, 3*TEN(13)));
    s.insert(P(n-1, 0));

    for (int i = 0; i < q; i++) {
        int a; ll b;
        cin >> a >> b; a--;
        while (b) {
            auto it = s.lower_bound(P(a, -1));
            auto pr = *it; it--;
            auto pl = *it;
            int d = a-pl.first;            
            if (d == 0) return 0;
            if (a == pr.first) s.erase(pr);
            if (d*(pl.second-pr.second) <= b) {
                s.erase(pl); 
                s.insert(P(a, pl.second));
                b -= d*(pl.second-pr.second);
            } else {                
                s.insert(P(a, pr.second + b/d));
                if (b%d) {
                    s.insert(P(pl.first + b%d, pr.second + b/d + 1));
                }
                if (pr.second + (b+d-1)/d == pl.second) {
                    s.erase(pl);
                }
                b = 0;
            }
        }
    }

    ll res[n];
    int b = -1;
    for (auto p: s) {
        for (int i = b+1; i <= p.first; i++) {
            res[i] = p.second;
        }
        b = p.first;
    }

    for (int i = 0; i < n; i++) {
        cout << res[i] << endl;
    }
    return 0;
}



Measured memory_bytes: 8576
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> mp;
ll inf =  1e9;


int main(){
 string t,p;
 cin>>t>>p;
 int f=0,s=-1;// second 
 vector<bool> used(26,false);
 vector<int> alpha(26,-1);//最後に使われた位置
 for(ll i=0;i<t.size();i++){
  
  if( s != -1 ){
   if( t[i] == p[s] ) s++;
  }

  if( alpha[ t[i]-'a' ] != -1 ){
   s = max( s , alpha[t[i]-'a' ] );
  }



  if( f<p.size() && t[i] == p[f] ){
   f++;
   alpha[t[i]-'a'] = f;
  }


  if( s == p.size() ){
   cout<<"no"<<endl;
   return 0;
  }

 }

 if( f == p.size() ){
  cout<<"yes"<<endl;
 }else{
  cout<<"no"<<endl;
 }

    return 0;
}



Measured memory_bytes: 4256
use std::io::*;
use std::str::*;

fn read<T: FromStr>() -> Option<T> {
    let stdin = stdin();
    let s = stdin
        .bytes()
        .map(|c| c.unwrap() as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect::<String>();
    s.parse::<T>().ok()
}

fn average(numbers: &Vec<f64>) -> f64 {
    let mut total: f64 = 0.;
    for x in numbers.iter() {
        total += *x;
    }
    total / (numbers.len() as f64)
}

fn cost(x: f64, y: f64) -> f64 {
    (x - y) * (x - y)
}

fn main() {
    let n = read().unwrap();
    let mut v: Vec<f64> = Vec::new();
    for _ in 0..n {
        v.push(read().unwrap());
    }
    let avg = average(&v).round();
    let mut total_cost = 0.0;
    for v_i in v.iter() {
        total_cost += cost(*v_i, avg);
    }
    println!("{}", total_cost);
}

Measured memory_bytes: 4476
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <utility>
#include <string>
#include <stack>

using namespace std;

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

	stack<char> st;
	int ans = 0;

	for (char c: s) {
		if (st.empty()) {
			st.push(c);
		} else if (st.top() == c) {
			st.push(c);
		} else {
			st.pop();
			ans += 2;
		}
	}

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


Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n,a=1;string s;cin>>n>>s;
  if(n==1)cout<<1<<endl;
  else{
    char x=s.at(0);
    for(int i=1;i<n;i++){
      if(s.at(i)!=x){
        a++;
        x=s.at(i);
      }
    }
    cout<<a<<endl;
  }
}
      

Measured memory_bytes: 512
inf = 0x10101010
def solve(A,strt):
    cost = [inf]*m
    visited = [False]*m
    cost[strt] = 0
    while 1:
        min = inf
        next = -1
        visited[strt] = True
        for i in range(m):
            if visited[i]: continue
            if A[strt][i]:
                d = cost[strt] + A[strt][i]
                if d < cost[i]:
                    cost[i] = d
            if min > cost[i]:
                min = cost[i]
                next = i
        strt = next
        if next == -1: break
    return cost
     
while 1:
    n,m = map(int,raw_input().split())
    if n == 0: break
    T = [[0]*m for i in range(m)]
    C = [[0]*m for i in range(m)]
    for i in range(n):
        a,b,c,t = map(int,raw_input().split())
        T[a-1][b-1] = T[b-1][a-1] = t
        C[a-1][b-1] = C[b-1][a-1] = c
    TS = [solve(T,i) for i in range(m)]
    CS = [solve(C,i) for i in range(m)]
    for i in range(input()):
        a,b,q = map(int,raw_input().split())
        if q == 0:
            print CS[a-1][b-1]
        else:
            print TS[a-1][b-1]

Measured memory_bytes: 4812
#include <iostream>
#include <set>

using namespace std;
int main() {
    int N;
    int P[100000];
    cin >> N;
    for (int i=0; i<N; i++) cin >> P[i];
    int pos[100001];
    for (int i=0; i<N; i++) pos[P[i]] = i;
    
    set<int, greater<int>> L;
    set<int> R;
    long long score = 0;
    for (int i=N; i>=1; i--) {
        int p = pos[i];
        auto left1it = L.upper_bound(p);
        int left1 = -1;
        if (left1it != L.end()) left1 = *left1it;

        auto left2it = L.upper_bound(left1);
        int left2 = -1;
        if (left2it != L.end()) left2 = *left2it;

        auto right1it = R.upper_bound(p);
        int right1 = N;
        if (right1it != R.end()) right1 = *right1it;

        auto right2it = R.upper_bound(right1);
        int right2 = N;
        if (right2it != R.end()) right2 = *right2it;

        score += (long long)((left1 - left2) * (right1 - p) + (right2 - right1) * (p - left1)) * i;

        // cerr << "## " << p << " ##" << endl;
        // cerr << left1 << " " << left2 << endl;
        // cerr << right1 << " " << right2 << endl;
        // cerr << ": " << score << endl;
        L.insert(p);
        R.insert(p);
    }
    cout << score << endl;
    return 0;
}



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

int main(){
  int n,k,d;
  cin>>n>>k;
  vector<int> a(n,0);
  int i,j;
  rep(i,k){
    cin>>d;
    rep(j,d){
      int i1;
      cin>>i1;
      a[i1-1]++;
    }
  }
  int ans=0;
  rep(i,n)if(a[i]==0)ans++;
  cout<<ans;
  

  return 0;
}

Measured memory_bytes: 3628
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<(n); i++)
#define reps(i,s,n) for(int i=(s); i<(n); i++)
#define all(v) v.begin(),v.end()
#define res(n) resize(n)
#define rev(v) reverse(v.begin(),v.end())
#define so(v) sort(v.begin(),v.end())
#define outve(v) for(auto i : v) cout << i << " ";cout << endl
#define in(n,v) for(int i=0; i<(n); i++){cin >> v[i];}
#define out(n) cout << (n) << endl
#define fi first
#define se second
#define ve vector
#define pa pair
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef vector<string> vs;
typedef vector<vector<int>> vvi;
typedef vector<pair<int,int>> vpi;
typedef vector<pair<ll,ll>> vpl;
typedef vector<vector<pair<int,int>>> vvp;




int main()
{
    
    int a,b,c;
    cin >>a>>b>>c;
    a += b;
    a += c;
    if(a>=22) out("bust");
    else out("win");
    
    return 0;
}



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

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

  int p = 0;
  int p_ref = 0;
  string ref = "AKIHABARA";
  while(!(p_ref == ref.size() && p == s.size())){
    if(s[p] == ref[p_ref]){
      p++;
      p_ref++;
    }else if(ref[p_ref] == 'A'){
      p_ref++;
    }else{
      cout << "NO" << endl;
      return 0;
    }
  }
  cout << "YES" << endl;

  return 0;
}


Measured memory_bytes: 3580
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

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

S = sum(A)
best_diff = 10**18
best_i = -1
for i,x in enumerate(A):
    d = abs(x*N-S)
    if d < best_diff:
        best_diff = d
        best_i = i

print(best_i)

Measured memory_bytes: 3064
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
using ll = int64_t;
#define rep(i,n) for(int i = 0; i < ((int)(n)); i++)   // 0-indexed昇順

int main() {
    int N, M; cin >> N >> M;
    vector<map<string, int>> P(N); 
    rep(i, M) {
        int p; string s;
        cin >> p >> s;
        --p;
        if (s == "WA" && P[p]["AC"] > 0) continue;
        P[p][s]++;
    }
    int AC = 0;
    int WA = 0;
    for (int i = 0; i < N; i++) {
        if (P[i]["AC"] > 0) {
            AC++;
            WA += P[i]["WA"];
        }
    }
    printf("%d %d\n", AC, WA);
}

Measured memory_bytes: 26752
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<iostream>
#include<queue>
#include<vector>
#include<bitset>
#include<math.h>
using namespace std;
#define INF 110000000000
#define MOD 1000000007
typedef long long ll;
typedef pair<int,int> P;


int main(){
  ll ans=1;
  int N,pre=0;
  string s;
  cin>>N>>s;

  for(int i=0;i<(int)s.size();i++,ans%=MOD){
    if(s[i]==s[i+1]){
      i++;
      if(pre==0) ans*=6;
      else if(pre==1) ans*=2;
      else if(pre==2) ans*=3;
      pre=2; 
    }else{
      if(pre==0) ans*=3;
      else if(pre==1) ans*=2;
      else if(pre==2) ans*=1;
      pre=1;
    }
  }
  cout<<ans<<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define REP(i, n) for (ll i=(ll)0; i<(ll)n; ++i)
const int INF = 1<<29;
int a[305][305];
int main() {
    int n; cin >> n;
    REP(i, n) REP(j, n) cin >> a[i][j];
    
    REP(k, n) REP(i, n) REP(j, n)if (a[i][k] + a[k][j] < a[i][j]) {cout << -1 << endl; return 0;}
    REP(k, n) REP(i, n) REP(j, n){
        if (k==i || k==j || i==j) continue;
        if (a[i][k] + a[k][j] == a[i][j]) a[i][j] = INF;
    }

    ll S = 0;
    REP(i, n) REP(j, n) if (a[i][j] != INF) S += a[i][j];
    cout << S/2 << endl;

    return 0;
}


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

using namespace std;
typedef long long ll;
using pii = pair<ll, ll>;
const ll mx = 1000007;
const ll mod = 1e9 + 7;
const double pi = acos(-1);
#define ull unsigned long long
#define    ss   second
#define    ff   first
#define    pb   push_back
#define gcd(a, b) __gcd((a), (b))
#define lcm(a, b) ((a) / __gcd((a), (b)) * (b))

///--------------Graph Moves--------------------------------------
///const ll fx[] = {+1,-1,+0,+0};
///const ll fy[] = {+0,+0,+1,-1};
///const ll fx[] = {+0,+0,+1,-1,-1,+1,-1,+1}; ///King's move
///const ll fy[] = {-1,+1,+0,+0,+1,+1,-1,-1}; ///king's Move
///const ll fx[] = {-2,-2,-1,-1,+1,+1,+2,+2}; ///knight's move
///const ll fy[] = {-1,+1,-2,+2,-2,+2,-1,+1}; ///knight's move
///---------------------------------------------------------------

#define FIO ios_base::sync_with_stdio(false);  cin.tie(NULL);


int main() {
    FIO;
   string s; cin >> s;
   ll n = s.size();
   if(s[n - 1] == 's') cout << s << "es" << endl;
   else cout << s << "s" << endl;
}



Measured memory_bytes: 3660
#include<iostream>
using namespace std;int main(){int n,a,b,c,x,i;int y[100];int fl;for(;;){cin >> n >> a >> b >> c >> x;if(n==0&&a==0&&b==0&&c==0&&x==0)break;for(i=0;i<n;i++){cin >> y[i];}fl=i=0;int f=1;for(;;){if(fl==10001){f=0;break;}if(y[i]==x){i++;x=(a*x+b)%c;if(i==n)break;fl++;}else{fl++;x=(a*x+b)%c;}}if(f==1)cout << fl << endl;else cout << "-1" << endl;}}

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


int main(){
    
    int h, w;
    cin >> h >> w;
    int start_x, start_y, end_x, end_y;
    cin >> start_x >> start_y >> end_x >> end_y;
    
    start_x--;
    start_y--;
    end_x--;
    end_y--;
    
    vector<string>a(h);
    for(int i = 0; i < h; i++){
        cin >> a[i];
    }
    
    auto f = [&](int i, int j){
        if (i >= 0 && i < h && j >= 0 && j < w && a[i][j] == '.'){
            return true;
        }else{
            return false;
        }
    };
    
    vector<vector<int>>dist(h, vector<int>(w, 1e+9));
    deque<int>xs, ys;
    dist[start_x][start_y] = 0;
    xs.push_front(start_x);
    ys.push_front(start_y);
    
    vector<int>dx = {-1, 1, 0, 0};
    vector<int>dy = {0, 0, -1, 1}; 
    while(!xs.empty()){
        int cur_x = xs.front();
        int cur_y = ys.front();
        xs.pop_front();
        ys.pop_front();
        int cur_value = dist[cur_x][cur_y];  
        for(int i = 0; i < 4; i++){ 
            
            int n_x = cur_x + dx[i];
            int n_y = cur_y + dy[i];
            
            if(!f(n_x, n_y))continue;
            if(dist[n_x][n_y] > cur_value){
                xs.push_front(n_x);
                ys.push_front(n_y);
                dist[n_x][n_y] = cur_value;
            }
        }
        
        for(auto i : {-2, -1, 0, 1, 2}){
            for(auto j : {-2, -1, 0, 1, 2}){
                int n_x = cur_x + i;
                int n_y = cur_y + j;
                
                if(!f(n_x, n_y))continue;
                if(dist[n_x][n_y] > cur_value + 1){
                    xs.push_back(n_x);
                    ys.push_back(n_y);
                    dist[n_x][n_y] = cur_value + 1;
                }
                
            }
        }
          
    }
    
    if(dist[end_x][end_y] > 1e+7){
        cout << -1 << endl;
    }else{
        cout << dist[end_x][end_y] << endl;
    }
}


Measured memory_bytes: 9504
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace AtCorder
{
	public class Program
	{
		static void Main(string[] args)
		{
			Scanner cin = new Scanner();
			int n = cin.Int();
			int m = cin.Int();
			int max = 100001;
			List<long>[] map = new List<long>[max];
			for (int i = 0; i < max; i++) {
				map[i] = new List<long>();
			}

			for (int i = 0; i < n; i++) {
				int a = cin.Int();
				long b = cin.Long();
				map[a].Add(b);
			}

			long ans = 0;
			PriorityQueue<long> queue = new PriorityQueue<long>();
			for (int i = 1; i <= m; i++) {
				for (int j = 0; j < map[i].Count; j++) {
					queue.Push(map[i][j]);
				}

				if (queue.Count > 0) {
					ans += queue.Pop();
				}
			}

			Console.WriteLine(ans);
		}
	}

	class PriorityQueue<T> where T : IComparable<T>
	{
		List<T> buf;
		public bool rev = false;
		public PriorityQueue() { buf = new List<T>(); }
		int cmp(int i, int j) => buf[i].CompareTo(buf[j]) * (rev ? -1 : 1);
		void swap(int i, int j) { var t = buf[i]; buf[i] = buf[j]; buf[j] = t; }
		public void Push(T elem)
		{
			int n = buf.Count;
			buf.Add(elem);
			while (n > 0) {
				int i = (n - 1) >> 1;
				if (cmp(n, i) > 0)
					swap(i, n);
				n = i;
			}
		}
		public T Pop()
		{
			T ret = buf[0];
			int n = buf.Count - 1;
			buf[0] = buf[n];
			buf.RemoveAt(n);
			for (int i = 0, j; (j = (i << 1) + 1) < n; i = j) {
				if (j != n - 1 && cmp(j, j + 1) < 0)
					++j;
				if (cmp(i, j) < 0)
					swap(i, j);
			}
			return ret;
		}
		public T Top => buf[0];
		public int Count => buf.Count;
	}

	public class Scanner
	{
		private readonly char[] delimiter_ = new char[] { ' ' };
		private string[] buf_;
		private int index_;
		
		public Scanner()
		{
			buf_ = new string[0];
			index_ = 0;
		}

		public string Next()
		{
			if (index_ < buf_.Length) {
				return buf_[index_++];
			}

			string st = Console.ReadLine();
			while (st == "") {
				st = Console.ReadLine();
			}

			buf_ = st.Split(delimiter_, StringSplitOptions.RemoveEmptyEntries);
			if (buf_.Length == 0) {
				return Next();
			}

			index_ = 0;
			return buf_[index_++];
		}

		public int Int()
		{
			return int.Parse(Next());
		}
		public int[] ArrayInt(int N, int add = 0)
		{
			int[] Array = new int[N];
			for (int i = 0; i < N; i++) {
				Array[i] = Int() + add;
			}
			return Array;
		}

		public long Long()
		{
			return long.Parse(Next());
		}

		public long[] ArrayLong(int N, long add = 0)
		{
			long[] Array = new long[N];
			for (int i = 0; i < N; i++) {
				Array[i] = Long() + add;
			}
			return Array;
		}

		public double Double()
		{
			return double.Parse(Next());
		}

		public double[] ArrayDouble(int N, double add = 0)
		{
			double[] Array = new double[N];
			for (int i = 0; i < N; i++) {
				Array[i] = Double() + add;
			}
			return Array;
		}
	}
}


Measured memory_bytes: 26900
m = int(input())
def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

import collections

c = collections.Counter(prime_factorize(m))
#print(c)
#print(list(c.values()))
#print(list(c.values())[1])
keys =[]
k = len(list(c.values()))

for i in range(k):
  for j in range(45):
    if j*(j+1)/2 > list(c.values())[i]:
      break
  keys.append(j-1)

#print(keys)
print(sum(keys))

Measured memory_bytes: 9468
package main

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

type eadge struct {
	start int
	end   int
}

type eadgeArray []eadge

func (a eadgeArray) Len() int {
	return len(a)
}

func (a eadgeArray) Less(i, j int) bool {
	return a[i].start < a[j].start
}

func (a eadgeArray) Swap(i, j int) {
	a[i], a[j] = a[j], a[i]
}

func main() {
	scanner := bufio.NewScanner(os.Stdin)
	scanner.Scan()
	eadges := []eadge{}
	for scanner.Scan() {
		array := strings.Split(scanner.Text(), " ")
		robot, _ := strconv.Atoi(array[0])
		arm, _ := strconv.Atoi(array[1])
		var s int
		if robot < arm {
			s = 0
		} else {
			s = robot - arm
		}
		e := eadge{
			s,
			robot + arm - 1,
		}
		eadges = append(eadges, e)
	}
	//sort
	sort.Sort(eadgeArray(eadges))

	cnt := 0
	prev := eadges[0]
	eadges = eadges[1:]
	for _, e := range eadges {
		if prev.end < e.start {
			//no overlap
			prev = e
			cnt++
			continue
		}
		//overlap
		if prev.end < e.end {
			//keep pre
			continue
		}
		//change
		prev = e
	}
	cnt++
	fmt.Println(cnt)
}


Measured memory_bytes: 8064
#include<bits/stdc++.h>
using namespace std;
int n,D;
int main(){
	scanf("%d%d",&n,&D);
	int ds=2*D+1;
	if(n%ds==0)printf("%d\n",n/ds);
	else printf("%d\n",n/ds+1);
	return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cmath>
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <map>
#include <unordered_map>
#include <set>
#include <string>
#include <bitset>
#include <deque>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
#define print(x) cout<<(x)<<endl
#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define RREP(i, n) for (int i = (n)-1; i >= 0; --i)
#define INF10 1001001001 
#define INF5 100000
#define EPS 1e-10


int main() {
	int N; cin >> N;
	vector<int>a(N);
	REP(i, N)cin >> a[i];
	sort(a.begin(), a.end());

	int out = 0;
	REP(i, N) {
		out += a[i] - 1;
	}
	print(out);

	return 0;
}


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

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

bool f(const string &s){
  if(s=="ABC") return true;
  if(s.size()<=3) return false;
  int n=s.size();
  char c;
  if(s.substr(0, 3)=="ABC") c='A';
  else if(s.substr(n-3, 3)=="ABC") c='C';
  else c='B';
  string t="";
  rep(i, n){
    if(s.substr(i, 3)=="ABC"){
      t+=c;
      i+=2;
    }else{
      t+=s[i];
    }
  }
  if(s.size()==t.size()) return false;
  string u="";
  int m=t.size();
  rep(i, m){
    if(t[i]==c){
      u+="ABC";
    }else{
      u+=t[i];
    }
  }
  if(s==u) return f(t);
  else return false;
}

int main(){

  string s; cin>> s;

  bool ok=f(s);
  if(ok) cout<< "Yes"<< endl;
  else cout<< "No"<< endl;

  // cout<< ret<< endl;

  return 0;
}



Measured memory_bytes: 27932
#include <iostream>
#include <algorithm>
#include <vector>
#define rep(i,n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<=n;++i)
using namespace std;
typedef long long ll;
const ll MOD=1e+9+7;
struct mint{
  ll x;
  mint(ll x=0):x(x%MOD){}
  mint& operator+=(const mint a){
    if((x+=a.x)>=MOD) x-=MOD;
    return *this;
  }
  mint& operator-=(const mint a){
    if((x += MOD-a.x)>=MOD) x-=MOD;
    return *this;
  }
  mint& operator*=(const mint a){
    (x*=a.x)%=MOD;
    return *this;
  }
  mint operator+(const mint a) const{
    mint res(*this);
    return res+=a;
  }
  mint operator-(const mint a) const{
    mint res(*this);
    return res-=a;
  }
  mint operator*(const mint a) const{
    mint res(*this);
    return res*=a;
  }
  mint pow(ll t) const{
    if(!t) return 1;
    mint a = pow(t>>1);
    a*=a;
    if(t&1) a*=*this;
    return a;
  }
  
  //for prime mod
  mint inv() const{
    return pow(MOD-2);
  }
  mint& operator/=(const mint a){
    return (*this) *= a.inv();
  }
  mint operator/(const mint a) const{
    mint res(*this);
    return res/=a;
  }
};

int main()
{
  int n;
  cin >> n;
  vector<ll> a(n);
  rep(i,n) cin >> a[i];

  mint res(0);
  mint bi(1);
  rep(i,62){
    ll cnt = 0;
    rep(j,n){
      if((a[j]>>i)&1) cnt++;
    }
    ll z = n-cnt;
    mint c(cnt);
    mint d(z);
    res += c*d*bi;
    bi *= (mint)2;
  }

  cout << res.x << "\n";
  return 0;
}


Measured memory_bytes: 2560
#!/usr/bin/env python3

import sys


def lms(t, i):
    return i > 0 and not t[i-1] and t[i]


def induced_sort(s, k, t, lmss):

    sa = [-1] * len(s)
    cbin = [0]*k

    for c in s:
        cbin[c] += 1

    ssum = 0
    for i in range(k):
        ssum += cbin[i]
        cbin[i] = ssum

    count = [0] * k
    for i in reversed(lmss):
        c = s[i]
        sa[cbin[c]-1 - count[c]] = i
        count[c] += 1

    count = [0] * k
    for i in sa:
        if i <= 0 or t[i-1]:
            continue
        c = s[i-1]
        sa[cbin[c-1] + count[c]] = i-1
        count[c] += 1
        
    count = [0] * k
    for i in reversed(sa):
        if i <= 0 or not t[i-1]:
            continue
        c = s[i-1]
        sa[cbin[c]-1 - count[c]] = i-1
        count[c] += 1

    return sa


def sa_is(s, k):
    slen = len(s)
    t = [True] * slen # S -> True, T -> False
    for i in range(slen-2, -1, -1):
        #if s[i] < s[i+1]:   t[i] = True #'S'
        if s[i] > s[i+1]:
            t[i] = False # 'L'
        elif s[i] == s[i+1]:
            t[i] = t[i+1]

    lmss = []
    for i in range(1,slen):
        if not t[i-1] and t[i]: # lms(t, i):
            lmss.append(i)

    seed = lmss

    sa = induced_sort(s, k, t, seed)

    new_sa = []
    for i in sa:
        if lms(t, i): new_sa.append(i)

    nums = dict() #    nums = [[]] * (max(new_sa)+1)
    nums[new_sa[0]] = 0
    num = 0
    for o in range(len(new_sa)-1):
        i, j = new_sa[o], new_sa[o+1]
        diff, d = False, 0
        for d in range(slen):
            if s[i+d] != s[j+d] or lms(t, i+d) != lms(t, j+d):
                diff = True
                break
            elif d > 0 and (lms(t, i+d) or lms(t, j+d)):
                break
        if diff:
            num += 1
        nums[j] = num

#    for i in range(len(nums)-1,-1,-1):
#        if not nums[i]: nums.pop(i)
    nums = list(map(lambda x: x[1], sorted(nums.items())))

    if num + 1 < len(nums):
        sa = sa_is(nums, num+1)
    else:
        sa = [[]] * (max(nums)+1)
        for i, c in enumerate(nums):
            sa[c] = i

    seed = list(map(lambda x:lmss[x], sa))
    sa = induced_sort(s, k, t, seed)

    return sa


def strcmp(a, b):
    for i, bi in enumerate(b):
        if a[i] == bi: continue
        return a[i]-bi
    return 0


def search(s, sa, slen, q):
    ss = 0
    ee = slen
    while ss <= ee:
        mid = (ss+ee)//2
        if mid >= slen: break
        rr = strcmp(s[sa[mid]:], q)
        if rr==0: return 1
        if rr >= 0:
            ee = mid-1
        else:
            ss = mid+1
    return 0


if __name__ == '__main__':

    b = sys.stdin.readline().rstrip()
    b = (b+'$').encode()
    sa = sa_is(b, 128) #ord('z'))
    n = int(sys.stdin.readline())
    for _ in range(n):
        q = sys.stdin.readline().rstrip().encode()
        if search(b, sa, len(b), q) > 0:
            print(1)
        else:
            print(0)



Measured memory_bytes: 130620
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n,m,p=0,bona=0;
  cin>>n>>m;
  int x[m],y[101][101],z[101]={0};
  for(int i=0;i<m;i++)cin>>x[i];
  for(int i=0;i<m;i++){
    for(int j=1;j<=n;j++){
      cin>>y[i][j];
      if(y[i][j]!=x[p])bona++;
      if(y[i][j]==x[p])z[j]++;
    }
    z[x[p]]+=bona;
    p++;
    bona=0;
  }
  for(int i=1;i<=n;i++)cout<<z[i]<<endl;
  return 0;
}

Measured memory_bytes: 3116
// The very basic /////////////////////////////////////////////////////////////
#include <bits/stdc++.h>
using namespace std;
#define ALL_H 1

// Print elements of containers using << operator /////////////////////////////
// pair
template<typename T1, typename T2> ostream& operator<<(ostream& s, const pair<T1, T2>& p) {
  return s << "(" << p.first << ", " << p.second << ")";}
// vector
template<typename T> ostream& operator<<(ostream& s, const vector<T>& v) {
  for (auto &elem : v) {
    s << elem;
    if (&elem != &v.back()) s << " ";
  }
  return s;
}
// 2 dimentional vector
template<typename T> ostream& operator<<(ostream& s, const vector< vector<T> >& vv) {
  for (auto &elem : vv) {
    s << elem;
    if (&elem != &vv.back()) s << endl;
  }
  return s;
}
// map
template<typename T1, typename T2> ostream& operator<<(ostream& s, const map<T1, T2>& m) {
  s << "{" << endl;
  for (auto &elem: m) {
    s << " " << elem.first << " : " << elem.second << endl;
  }
  s << "}";
  return s;
}
//set
template<typename T> ostream& operator<<(ostream& s, const set<T>& m) {
  s << "{ ";
  for (auto &elem: m) {
    s << elem << " ";
  }
  s << "}";
  return s;
}

// Convenient macros //////////////////////////////////////////////////////////

// types
#define ll long long
#define ld long double
#define int ll
#define Pi pair<int, int>
#define Graph vector<vector<int>>
#define WeightGraph vector<vector<Pi>>

// other
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define all(x) (x).begin(),(x).end()
#define perm(c) sort(all(c));for(bool c##p=1;c##p;c##p=next_permutation(all(c)))

#define MOD 1000000007
#define INF LLONG_MAX/100

// update max or min //////////////////////////////////////////////////////////

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; }

// gcd
int gcd(int a,int b){return b?gcd(b,a%b):a;}

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


// Debug it by D(x) ///////////////////////////////////////////////////////////
#define DEBUG 0
#if DEBUG
#define D(x) x
#else
#define D(x)
#endif

///////////////////////////////////////////////////////////////////////////////
//                             Start Coding Here                             //
///////////////////////////////////////////////////////////////////////////////

signed main() {
  int N; cin >> N;
  vector<int> v(N);
  rep(i, N) v[i] = i+1;
  vector<int> P(N), Q(N);
  rep(i, N) cin >> P[i];
  rep(i, N) cin >> Q[i];
  int a = 1, b = 1;
  int fa, fb;
  perm(v) {
    int aa = 1, bb = 1;
    D(cout << v << endl;)
    rep(i, N) {
      if (v[i] != P[i]) {
        aa = 0;
      }
      if (v[i] != Q[i]) {
        bb = 0;
      }
    }
    if (aa != 1) {
      ++a;
    } else {
      fa = a;
    }
    if (bb != 1) {
      ++b;
    } else {
      fb = b;
    }
  }
  cout << abs(fa - fb) << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define FAST       			ios_base :: sync_with_stdio(false); cin.tie(NULL);

int main() {
  FAST;
  string S;
  cin >> S;
  for (int i = 0; i < 3; i++) {
    cout << S.at(i);
  }
  cout << endl;
}

Measured memory_bytes: 3608
#include<cstdio>
#include<iostream>
using namespace std;
string s;
int l;
int main()
{
    cin>>s;
    l=s.size();
    for(int i=0;i<l;i++)
    {
        if(s[i]=='C')
        {
            for(int j=i+1;j<l;j++)
            {
                if(s[j]=='F')
                {
                    cout<<"Yes"<<endl;
                    return 0;
                }
            }
        }
    }
    cout<<"No"<<endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,m;
    scanf("%d %d",&n,&m);
    if((n==1 && m==2) || (n==2 && m==1))
        printf("3");
    else if((n==1 && m==3) || (n==3 && m==1))
        printf("2");
    else
        printf("1");
}


Measured memory_bytes: 256