akhauriyash/Code-Regression huggingface dataset:
// 参考
//   xorの掃き出し https://twitter.com/noshi91/status/1200702280128856064
//   https://atcoder.jp/contests/agc045/submissions/14100178
//   https://atcoder.jp/contests/agc045/submissions/14091582

#include <iostream>
#include <set>
#include <vector>
using namespace std;
typedef long long ll;
#define REP(i,n) for(int i = 0; i < (int)(n); ++i)
#define FOR(i,a,b) for(int i = (a); i < (int)(b); ++i)
#define ALL(c) (c).begin(), (c).end()
#define SIZE(v) ((int)v.size())
template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b; return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b; return true;
    }
    return false;
}


#define pb push_back
#define mp make_pair
#define mt make_tuple


int solve(int N, vector<ll> As, string S) {

    set<ll, greater<ll>> bases;
    // vector<ll> bases;

    for(int i = N - 1; i >= 0; --i) {
        ll a = As[i];
        if (S[i] == '0') {
            for (auto b: bases) chmin(a, a ^ b);
            if (a) {
                bases.insert(a);
                // bases.pb(a);
            }
        }
        else {
            for (auto b: bases) chmin(a, a ^ b);
            if (a) {
                return 1;
            }
        }
        // cout << "bases:" << endl;
        // for(auto b: bases) cout << "  " << b << endl;
    }
    return 0;
}


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

    int T; cin >> T;
    REP(t, T) {
        int N; cin >> N;
        vector<ll> As(N);
        REP(n, N) cin >> As[n];
        string S; cin >> S;

        cout << solve(N, As, S) << endl;
    }
    return 0;
}


Measured memory_bytes: 3568
#include <bits/stdc++.h>
#ifdef LOCAL_DEBUG
#define DEBUG 1
#define CERR if(DEBUG) cerr
#define MACRO(_1,_2,_3,_4,_5,_6,_7,_8,_9,_10,NAME,...) NAME
#define pr(...) CERR<<MACRO(__VA_ARGS__,pr10,pr9,pr8,pr7,pr6,pr5,pr4,pr3,pr2,pr1)(__VA_ARGS__)<<endl
#define pr1(a) (#a)<<"="<<(a)<<" "
#define pr2(a,b) pr1(a)<<pr1(b)
#define pr3(a,b,c) pr1(a)<<pr2(b,c)
#define pr4(a,b,c,d) pr1(a)<<pr3(b,c,d)
#define pr5(a,b,c,d,e) pr1(a)<<pr4(b,c,d,e)
#define pr6(a,b,c,d,e,f) pr1(a)<<pr5(b,c,d,e,f)
#define pr7(a,b,c,d,e,f,g) pr1(a)<<pr6(b,c,d,e,f,g)
#define pr8(a,b,c,d,e,f,g,h) pr1(a)<<pr7(b,c,d,e,f,g,h)
#define pr9(a,b,c,d,e,f,g,h,i) pr1(a)<<pr8(b,c,d,e,f,g,h,i)
#define pr10(a,b,c,d,e,f,g,h,i,j) pr1(a)<<pr9(b,c,d,e,f,g,h,i,j)
#define prArr(a){CERR<<(#a)<<"={";int i=0;for(auto t:(a))CERR<<(i++?", ":"")<<t;CERR<<"}"<<endl;}
#else
#define DEBUG 0
#define pr(...)
#define prArr(a)
#endif
using namespace std;
using Int = long long;
using _int = int;
using ll = long long;
using Double = long double;
const Int INF = (1LL<<60)+1e9; // ~ 1.15 * 1e18
const Int mod = (1e9)+7;
const Double EPS = 1e-8;
const Double PI = 6.0 * asin((Double)0.5);
using P = pair<Int,Int>;
template<class T> T Max(T &a,T b){return a=max(a,b);}
template<class T> T Min(T &a,T b){return a=min(a,b);}
template<class T1, class T2> ostream& operator<<(ostream& o,pair<T1,T2> p){return o<<"("<<p.first<<","<<p.second<<")";}
template<class T1, class T2, class T3> ostream& operator<<(ostream& o,tuple<T1,T2,T3> t){return o<<"("<<get<0>(t)<<","<<get<1>(t)<<","<<get<2>(t)<<")";}
template<class T1, class T2> istream& operator>>(istream& i,pair<T1,T2> &p){return i>>p.first>>p.second;}
template<class T> ostream& operator<<(ostream& o,vector<T> a){Int i=0;for(T t:a)o<<(i++?" ":"")<<t;return o;}
template<class T> istream& operator>>(istream& i,vector<T> &a){for(T &t:a)i>>t;return i;}
//INSERT ABOVE HERE


signed main(){
  srand((unsigned)time(NULL));
  cin.tie(0);
  ios_base::sync_with_stdio(0);
  cout << fixed << setprecision(12);

  int N;
  string S;
  cin>>N>>S;
  int ans = 0;
  for(int i=0;i<N-2;i++)
    if(S.substr(i, 3) == "ABC") ans++;
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
using namespace std;
#define rep(i,n) for(int i=1;i<(n);i++) 
int main(){
  int n;
  int counter[2000000];
  rep(x,400){
    rep(y,400){
      rep(z,400){
        counter[x*x+y*y+z*z+x*y+y*z+z*x]++;
      }
    }
  }
  cin >> n;
  rep(i,n+1){
    cout << counter[i] << endl;
  }
}

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

using namespace std;

const int N = 3005;
long long dp[N][N][4];
int v[N][N];

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

  int r, c, k;
  cin >> r >> c >> k;
  while (k--) {
    int x, y;
    cin >> x >> y >> v[x][y];
  }
  for (int i = 1; i <= r; ++i) {
    for (int j = 1; j <= c; ++j) {
      for (int jj = 0; jj < 4; ++jj) dp[i][j][0] = max(dp[i][j][0], dp[i - 1][j][jj]), dp[i][j][1] = max(dp[i][j][1], dp[i - 1][j][jj] + v[i][j]);
      for (int ii = 0; ii < 4; ++ii) {
        dp[i][j][ii] = max(dp[i][j][ii], dp[i][j - 1][ii]);
        if (ii) dp[i][j][ii] = max(dp[i][j][ii], dp[i][j - 1][ii - 1] + v[i][j]);
      }
    }
  }
  long long ans = 0;
  for (int i = 0; i < 4; ++i) ans = max(ans, dp[r][c][i]);
  cout << ans;

  return 0;
}


Measured memory_bytes: 320436
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, *A = map(int, read().split())

    ans = 0
    for a in A:
        while a % 2 == 0:
            ans += 1
            a //= 2

    print(ans)
    return


if __name__ == '__main__':
    main()


Measured memory_bytes: 10012
#define _USE_MATH_DEFINES
#include<iostream>
#include<sstream>
#include<vector>
#include<string>
#include<algorithm>
#include<map>
#include<unordered_map>
#include<math.h>
#include<iterator>

using namespace std;

long long calc(string s,long long num){
  long long ans =0;
  if(s.length()==0)return num;
  for(int i=0;i<s.length();i++){
    ans+=calc(s.substr(i+1),num+stoll(s.substr(0,i+1)));
  }
  return ans;
}

int main(){
  string s;
  cin >> s;
  cout << calc(s,0) <<endl;
      return 0;
}



Measured memory_bytes: 384
#ifdef __APPLE__
    # include <iostream>
    # include <cmath>
    # include <algorithm>
    # include <stdio.h>
    # include <cstdint>
    # include <cstring>
    # include <string>
    # include <cstdlib>
    # include <vector>
    # include <bitset>
    # include <map>
    # include <queue>
    # include <ctime>
    # include <stack>
    # include <set>
    # include <list>
    # include <random>
    # include <deque>
    # include <functional>
    # include <iomanip>
    # include <sstream>
    # include <fstream>
    # include <complex>
    # include <numeric>
    # include <immintrin.h>
    # include <cassert>
    # include <array>
    # include <tuple>
    # include <unordered_map>
    # include <unordered_set>
    # include <thread>
#else
    # include <bits/stdc++.h>
#endif

#define F first
#define S second
#define MP make_pair
#define PB push_back

#define all(a) a.begin(),a.end()
#define mp make_pair
#define pb push_back
#define fir first
#define sec second

using namespace std;

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

const int max_n = -1, inf = 1000111222;

int main() {
//    freopen("barik.in", "r", stdin);
//    freopen("barik.out", "w", stdout);

    int l,r,d;
    cin>>l>>r>>d;
    int ans=0;
    for (int i=l;i<=r;i++){
        if (i%d==0){
            ans++;
        }
    }
    cout<<ans<<"\n";
}


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

int a, b, k, i;

int main() {
  	cin >> a >> b >> k;
  	for (i = min(a, b); i >= 1 && k; i--) {
      	if (a % i == 0 && b % i == 0)
          	k--;
    }
  	cout << i + 1 << '\n';
 	return 0; 
}

Measured memory_bytes: 256
import qualified Data.ByteString.Char8 as BC
import Data.Maybe(fromJust)
import Data.List

main :: IO()
main = BC.getContents >>= print.solve.map (fst.fromJust.BC.readInt).tail.BC.lines
 
solve          :: [Int] -> Int
solve (x:y:ys) = fst $ foldl' f (y - x, min x y) ys
    where f (x,y) z = (max (z-y) x, min z y) 

Measured memory_bytes: 71588
from collections import deque

N, Q = map(int, input().split())
edge = [[] for i in range(N)]
ops = []
ans = [0] * N

for _ in range(N - 1):
    a, b = map(int, input().split())
    edge[a - 1].append(b - 1)
    edge[b - 1].append(a - 1)
for _ in range(Q):
    ops.append(tuple(map(int, input().split())))

for op in ops:
    node = op[0] - 1
    pnt = op[1]
    ans[node] += pnt

stack = deque()
stack.append((0, -1))

while stack:
    st = stack.pop()
    node, parent = st[0], st[1]
    children = edge[node]
    for child in children:
        if child == parent:
            continue
        ans[child] += ans[node]
        stack.append((child, node))

print(*ans)

Measured memory_bytes: 86392
#include <bits/stdc++.h>
    using namespace std;
    #define ll long long int
    #define pb push_back
    #define mp make_pair
    #define mod 1e9+7
    #define sz 100000
    #define f(i,n) for(ll i=0;i<n;i++)
    #define fab(i,a,b) for(ll i=a;i<b;i++)
    #define fr(i,n) for(ll i=n-1;i>=0;i--)
    #define fba(i,b,a) for(ll i=b-1;i>=a;i--)
    #define tc(t) ll t;cin>>t;while(t--)
     
    ll pw(ll x,unsigned ll y) 
    { 
        if (y==0) 
            return 1; 
        else if (y%2==0) 
            return pw(x,y/2)*pw(x,y/2); 
        else
            return x*pw(x,y/2)*pw(x,y/2);
    }
     
    int main() 
    {
        ios_base::sync_with_stdio(0);
        cin.tie(NULL);
        cout.tie(NULL);
        string s, t, u;
        cin >> s;
        f(i, s.size())
            cout << 'x';
        return 0;
    }

Measured memory_bytes: 256
#include <stdio.h>
int fib(int);
int N[45];

int main(){
  int n,i;
  for(i=0;i<45;i++)N[i]=-1;
  scanf("%d",&n);
  printf("%d\n",fib(n));
  return 0;
}

int fib(int n){
  if(n==0||n==1)return N[n]=1;
  if(N[n]!=-1)return N[n];
  return N[n]=fib(n-1)+fib(n-2);
}



Measured memory_bytes: 2104
import bisect
N, Q = map(int, input().split())
S = input()
qlist = []
for i in range(Q):
    l, r = map(int, input().split())
    qlist.append((l,r))
Alist = [i for i, x in enumerate(S) if x == 'A']
Clist = [i for i, x in enumerate(S) if x == 'C']
AClist = []
for c in Clist:
    if Alist[bisect.bisect_left(Alist, c)-1] == c-1:
        AClist.append(Alist[bisect.bisect_left(Alist, c)-1])

for l, r in qlist:
    idxa = bisect.bisect_left(AClist, l-1)
    idxb = bisect.bisect_left(AClist, r-1)
    print(idxb - idxa)

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

#define rep(i, n) for (int i = 0; i < n; ++i)
#define all(x) (x).begin(),(x).end()
#define endl "\n"

using ll = long long;
using P = pair<int,int>;
using mp =  map<string,int>;

const int MOD = 1e9 + 7;
const int INF = 1001001001;


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

    string s;
    cin >> s;
    set<char> c;

    rep(i, s.size()){
        c.insert(s[i]);
    }

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

    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
int main() {
    int antennas[5];
    for(int i=0;i<5;i++){
    scanf("%d",&antennas[i]);
    }
    int f=0;
    int k;
    scanf("%d",&k);
    int i,j;
    for(i=0;i<5;i++){
        for(j=i;j<5;j++){
            if(antennas[j]-antennas[i]<=k){
                continue;
            }else{
                f=1;
                printf(":(");
                break;
            }
        }
        if (f==1){
            break;
        }
    }
    if (f==0){
        printf("Yay!");
    }
    return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(int)n; i++)
#define rep2(i,a,n) for(int i=(a); i<(int)(n); i++)
#define all(vec) vec.begin(),vec.end()
using ll = long long;
using vi = vector<int>;
using vs = vector<string>;
using vvi = vector<vi>;
using vll = vector<ll>;
using pii = pair<int, int>;
using psi = pair<string, int>;
const int dx[4] = {1, 0,-1, 0};
const int dy[4] = {0, 1, 0,-1};
//const ll mod = 1e9+7;
int gcd(int a, int b){if(a%b == 0){return(b);}else{return(gcd(b, a%b));}}
int lcm(int a, int b){return a * b / gcd(a, b);}

ll N, M, K, H, W, L, R;
string S, T;

int main(){
  int A, B, X; cin >> A >> B >> X;
  if(X>=A && X<= A+B) cout << "YES" << endl;
  else cout << "NO" << endl;
  
  return 0;
}

Measured memory_bytes: 3592
#include<bits/stdc++.h>
const int maxn = 100010;
using namespace std;
int cnt[505][505];
int main()
{
//    freopen("out.txt", "w", stdout);
    ios::sync_with_stdio(0); cin.tie(0);
    int n, m, q, l, r;
    cin >> n >> m >> q;
    while (m--){
        cin >> l >> r;
        ++cnt[l][r];
    }
    for (int i = 1; i <= n; ++i){
        for (int j = 1; j <= n; ++j){
            cnt[i][j] += cnt[i][j - 1];
        }
    }
    for (int i = 1; i <= n; ++i){
        for (int j = 1; j <= n; ++j){
            cnt[i][j] += cnt[i - 1][j];
        }
    }
    while (q--){
        cin >> l >> r;
        cout << cnt[n][r] - cnt[l - 1][r] << endl;
    }
//    fclose(stdout);
    return 0;
}


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

using namespace std;




int main()
{
  string V[100];

  int H,W;
  cin>>H>>W;

  int f[100];
  int g[100];

  vector<vector<int>> book;

  for(int i=0;i<H;i++){
	  cin>>V[i];
  }



  for(int i=0;i<H;i++){
	  bool flag =true;
	  for(int j=0;j<W;j++){
		  if(V[i][j]=='#'){
			  flag = false;
			  break;
		  }

	  }

	  f[i] = flag;



  }


  for(int j=0;j<W;j++){
	  bool flag = true;
	  for(int i=0;i<H;i++){
		  if(V[i][j]=='#'){
			  flag = false;
			  break;
		  }
	  }


	  g[j] = flag;
  }


  for(int i=0;i<H;i++){
	  if(f[i]){
		  continue;
	  }
	  for(int j=0;j<W;j++){
		  if(g[j]){
			  continue;
		  }

		  cout<<V[i][j];

	  }
	  cout<<endl;
  }






    return 0;
}




Measured memory_bytes: 256
# Dice for AOJ
class Dice
  def initialize(input)
    @t, @s, @e, @w, @n, @b = input
  end

  def roll_e
    tmp = @e
    @e = @t
    @t = @w
    @w = @b
    @b = tmp
  end

  def roll_n
    tmp = @n
    @n = @t
    @t = @s
    @s = @b
    @b = tmp
  end

  def roll_w
    tmp = @w
    @w = @t
    @t = @e
    @e = @b
    @b = tmp
  end

  def roll_s
    tmp = @s
    @s = @t
    @t = @n
    @n = @b
    @b = tmp
  end

  def spin_r
    tmp = @s
    @s = @e
    @e = @n
    @n = @w
    @w = tmp
  end

  def sameto(dice2)
    return true if same(dice2)

    roll_n
    return true if same(dice2)

    3.times do
      roll_e
      return true if same(dice2)
    end
    roll_n
    return true if same(dice2)

    false
  end

  def same(dice2)
    return false unless @t == dice2.t && @b == dice2.b
    return true if @s == dice2.s && @e == dice2.e \
        && @w == dice2.w && @n == dice2.n

    3.times do
      spin_r
      return true if @s == dice2.s && @e == dice2.e \
          && @w == dice2.w && @n == dice2.n
    end
    false
  end

  attr_reader :t
  attr_reader :s
  attr_reader :e
  attr_reader :w
  attr_reader :n
  attr_reader :b
end

n = gets.to_i
dices = []
n.times do |i|
  g = gets.split.map(&:to_i)
  dices[i] = Dice.new(g)
end

flag = false
(n - 1).times do |i|
  ((i + 1)...n).each do |j|
    flag |= dices[i].sameto(dices[j])
  end
end

if flag
  puts 'No'
else
  puts 'Yes'
end



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

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

    bool flg=true;
    for(int i=1;i<N.size();i++){
        if(N[i]!='9') flg=false;
    }
    int t=N[0]-'0';
    if(flg) cout << (9*(N.size()-1)+t) << endl;
    else cout << (9*(N.size()-1)+t-1) << endl;

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
  
using namespace std;
  
#define rep(i,n) REP(i,0,n)
#define REP(i,s,e) for(int i=(s); i<(int)(e); i++)
#define pb push_back
#define all(r) r.begin(),r.end()
#define rall(r) r.rbegin(),r.rend()
#define fi first
#define se second
  
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
const int INF = 1e9;
const ll MOD = 1e9 + 7;
double EPS = 1e-8;

//#define DEBUG_MODE
#ifdef DEBUG_MODE
#define dump(x) cout << #x << " : " << x << endl
#define LINE cout << "line : " << __LINE__ << endl
#define dumpV(v) cout << #v << " : ["; for(auto& t : v) cout << t << ", "; cout<<"]" << endl;
#define STOP assert(false);
#else
#define dump(x) ;
#define LINE 	;
#define dumpV(v);
#define STOP 	;
#endif

namespace std{
  template<class S,class T>
  ostream &operator <<(ostream& out,const pair<S,T>& a){
    out<<'('<<a.fi<<", "<<a.se<<')';
    return out;
  }
}


int main(){
	ll n, m;
	cin >> n >> m;
	vl a(n);
	rep(i, n) cin >> a[i];
	vl x(m), y(m);
	rep(i, m) cin >> x[i] >> y[i], x[i]--;
	vl cover(n+1), cnt(n+1);
	rep(i, n) cnt[a[i]]++;
	REP(i, 1, n+1) {
		for(int j = i-cnt[i]; j < i; j++) {
			cover[max(0, j)]++;
		}
	}
	ll ans = 0LL;
	rep(i, n) if(cover[i] == 0) ans++;
	dump(ans);
	dumpV(a);
	dumpV(cnt);
	dumpV(cover);
	rep(i, m) {
		int tmp = max(0LL, a[x[i]] - cnt[a[x[i]]]);
		dump(i);
		dump(x[i]);
		dump(y[i]);
		dump(a[x[i]]);
		LINE;
		dump(tmp);
		dumpV(cnt);
		dumpV(cover);
		if(cover[tmp] == 1) ans++;
		cover[tmp]--;
		cnt[a[x[i]]]--;
		cnt[y[i]]++;
		a[x[i]] = y[i];
		tmp = max(0LL, y[i] - cnt[y[i]]);
		if(cover[tmp] == 0) ans--;
		cover[tmp]++;
		LINE;
		dump(tmp);
		dumpV(cnt);
		dumpV(cover);
		cout << ans << endl;
	}
	return 0;
}

Measured memory_bytes: 9344
/*

                                  In the name of Allah, Most Gracious, Most Merciful


*/
#include<bits/stdc++.h>
#include<numeric>
using namespace std;

//*** constant value ***
const long double PI = 3.141592653589793238;
const double EPS = 1e-6 ;
//*** constant value ***

//****** define ********
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ll long long
#define dd double
#define vll vector<ll>
#define vs vector<string>
#define fn(i,n) for(ll i = 0; i<n; i++)
#define f(i,a,b) for(i=a;i<b;i++)
#define f1(i,a,b) for(i=b-1;i>=a;i--)
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pls pair<ll,string>
#define vpl vector<pll>
#define pb push_back
#define mk make_pair
#define x first
#define y second
#define tt cout<<"Came here"<<endl;
//****** define ********
void solve()
{
   int n,m;
   cin>>n>>m;
    vector<double>v(n);
    int sum = 0;
    int ans = 0;

    fn(i,n) {
      cin>>v[i];
      sum += v[i];
    }

    fn(i,n)
    {
        if(v[i]*4*m < sum)
            continue;
        else
            ans++;
    }

    if(ans >= m )
        cout<<"Yes"<<endl;
    else
        cout<<"No"<<endl;

}

int main()
{
    IOS;
    ll tc = 1;
    while(tc--)
    {
        solve();
    }


return 0;
}



Measured memory_bytes: 3740
using System;
using System.Drawing;
using System.Windows.Forms;
using System.IO;




namespace aoj
{

public class program{
	static void Main(){
	ReverseNumber RevNum = new  ReverseNumber(int.Parse(Console.ReadLine()));
	RevNum.rev();
	Console.WriteLine();

}

}


class ReverseNumber{
	int[] numlist;
	public ReverseNumber(int n){
		numlist = new int[n];
		string[] tmp = Console.ReadLine().Split(' ');
		for(int i=0; i<tmp.Length; i++)
			numlist[i]=int.Parse(tmp[i]);
	}
	public void rev(){
		for(int i=numlist.Length-1; i > -1 ;i--){
			if(i<numlist.Length-1) Console.Write(' ');
			Console.Write(numlist[i]);
		}
	}
}

}

Measured memory_bytes: 5616
#include<bits/stdc++.h>
using namespace std;
int main(){
  string s;cin>>s;
  for(int i=0;i<3;i++){
    if(s[i]=='A'&&s[i+1]=='C'){
      cout<<"Yes"<<endl;
      return 0;
    }
  }
  cout<<"No"<<endl;
}

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

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

    int ans = 0;
    for (int i = 1; i + 1 < n; i++) {
        bitset<26> fh, sh;
        for (int fi = 0; fi < i; fi++) fh.set(s[fi] - 'a');
        for (int si = i; si < n; si++) sh.set(s[si] - 'a');
        ans = max(ans, (int) (fh & sh).count());
    }

    cout << ans << endl;
}


Measured memory_bytes: 256
import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String[] hw = scanner.nextLine().split(" ", 2);
        int h = Integer.parseInt(hw[0]);
        int w = Integer.parseInt(hw[1]);

        for (int i = 0; i < w + 2; i++) {
            System.out.print("#");
        }
        System.out.print("\n");
        for (int i = 0; i < h; i++) {
            String line = scanner.nextLine();
            System.out.printf("#%s#\n", line);
        }
        for (int i = 0; i < w + 2; i++) {
            System.out.print("#");
        }
        System.out.print("\n");
    }
}


Measured memory_bytes: 23124
#define _USE_MAT_DEFINES
#include<iostream>
#include <iomanip>
#include<stdio.h>
#include<string>
#include<vector>
#include<algorithm>
#include<cmath>
#include <queue>
#include <utility>
#include <map>
#include <set>
#include <stack>
#include <deque>
#include <numeric>
#include <functional>
using namespace std;

void root(int sx, int sy, int tx, int ty) {
    if (sx<tx) {
        for (int i = 0; i < abs(sx - tx); i++)cout << "R";
        for (int i = 0; i < abs(sy - ty); i++)cout << "U";
    }else{
        for (int i = 0; i < abs(sx - tx); i++)cout << "L";
        for (int i = 0; i < abs(sy - ty); i++)cout << "D";
    }
    return;
}

int main() {

    int sx, sy, tx, ty;
    cin >> sx >> sy >> tx >> ty;

    cout << "D";
    root(sx, sy - 1, tx + 1, ty);
    cout << "LU";
    root(tx, ty + 1, sx - 1, sy);
    root(sx - 1, sy, tx, ty);
    root(tx, ty, sx, sy);

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <fstream>
#include <cassert>
#include <typeinfo>
#include <vector>
#include <stack>
#include <cmath>
#include <set>
#include <map>
#include <string>
#include <algorithm>
#include <cstdio>
#include <queue>
#include <iomanip>
#include <cctype>
#include <random>
#include <complex>
#define syosu(x) fixed<<setprecision(x)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef pair<double,double> pdd;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<char> vc;
typedef vector<vc> vvc;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<pll> vpll;
typedef pair<P,int> pip;
typedef vector<pip> vip;
const int inf=1<<29;
const ll INF=1ll<<58;
const double pi=acos(-1);
const double eps=1e-7;
const ll mod=1e9+7;
const int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};

ll q,h,s,d,n;

int main(){
	cin>>q>>h>>s>>d>>n;
	ll tmp=min(4*q,min(2*h,s));
	if(2*tmp>d) cout<<n/2*d+n%2*tmp<<endl;
	else cout<<n*tmp<<endl;
}

Measured memory_bytes: 256
n,k = map(int,input().split())
X = [0]*(n+1)
import math as ma
ans = 0
for i in range(1,n+1):
    temp = ma.ceil(ma.log2(k/i)) if k >  i else 0 
    ans += (1/n)*(0.5**temp)
print(ans)

Measured memory_bytes: 3828
#include <bits/stdc++.h>
using namespace std;
#define INT(a) scanf("%d",&a)
#define STR(a) scanf("%s",a)
#define DBL(a) scanf("%lf",&a)
#define LNG(a) scanf("%lld",&a)
#define PI acos(-1)

int main(){
	int a, b;
	cin>>a>>b;
	if(a>=13) cout<<b<<endl;
	else if(a<=12 && a>=6) cout<<b/2<<endl;
	else cout<<0<<endl;
	return 0;
}

Measured memory_bytes: 256
//#include<bits/stdc++.h>	// 全てのヘッダーファイルをinclude
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<cmath>
#include<set>
#define REP(i,n) for(int i=0;i<n;i++)
#define REPR (i,n) for(int i=n;i>0;i--)
#define FOR(i,m,n) for(int i=m;i<n;i++)
#define MOD 1e9+7	// int 1000000007
const int inf{int(1e9)};	// inf = 1000000000 // 1e9 はdouble型
using namespace std;
typedef long long ll;


int main(void) {
	string a, b;
	cin >> a >> b;

	if (a.length() > b.length()) cout << "GREATER" << endl;
	else if (a.length() < b.length()) cout << "LESS" << endl;
	else if (a == b) cout << "EQUAL" << endl;
	else {
		int l = a.length();
		REP(i, l) {
			int x = a[i] - '0';
			int y = b[i] - '0';
			if (x != y) {
				cout << (x > y ? "GREATER" : "LESS") << endl;
				break;
			}
		}
	}

	return 0;
}

Measured memory_bytes: 256
#include<stdio.h>

int main(void)
{
  int w,h,n,x,y,a,s[2],t[2],i,ans=0;
  scanf("%d %d %d",&w,&h,&n);
  s[0]=0; s[1]=w;
  t[0]=0; t[1]=h;
  for(i=0;i<n;i++)
    {
      scanf("%d %d %d",&x,&y,&a);
      if(a == 1 && s[0] < x)
	{
	  s[0] = x;
	}
      else if(a == 2 && s[1] > x)
	{
	  s[1] = x;
	}
      else if(a == 3 && t[0] < y)
	{
	  t[0] = y;
	}
      else if(a == 4 && t[1] > y)
	{
	  t[1] = y;
	}
    }
  if(s[0] > s[1] || t[0] > t[1])
    {
      ans = 0;
    }
  else
    {
      ans = (s[1]-s[0]) * (t[1]-t[0]);
    }
  printf("%d\n",ans);
  return 0;
}


Measured memory_bytes: 128
#include <iostream>
#include <algorithm>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <string.h>
#include <vector>
#include <queue>
#include <cmath>
#include <bitset>
#include <complex>
#include <functional>
#include <numeric>
#include <iomanip>

// output
#define SPBR(w, n) std::cout<<(w + 1 == n ? '\n' : ' ');
#define YES cout << "YES" << endl
#define Yes cout << "Yes" << endl
#define NO cout << "NO" << endl
#define No cout << "No" << endl
// utility
#define ALL(i) (i).begin(), (i).end()
#define FOR(i, a, n) for(int i=(a);i<(n);++i)
#define RFOR(i, a, n) for(int i=(n)-1;i>=(a);--i)
#define REP(i, n) for(int i=0;i<int(n);++i)
#define RREP(i, n) for(int i=int(n)-1;i>=0;--i)
#define IN(a, x, b) (a<=x && x<b)
#define OUT(a, x, b) (x<a || b<=x)
template<class T> inline T chmax(T & a, const T b) { return a = (a < b) ? b : a; }
template<class T> inline T chmin(T& a, const T b) { return a = (a > b) ? b : a; }

// type/const
#define int ll
using ll = long long;
using ull = unsigned long long;
using ld = long double;
const int MOD = 1000000007;
/* const int MOD = 998244353; */
const int INF = 1e18;
const double PI = acos(-1);

using namespace std;
struct INIT { INIT(){
  cin.tie(0); ios::sync_with_stdio(false);
  cout << fixed << setprecision(10);
}}INIT;


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

  int N = 10;
  vector<vector<int>> c(N, vector<int>(N));
  REP(i, N) REP(j, N) cin >> c[i][j];

  REP(k, N) REP(i, N) REP(j, N){
    chmin(c[i][j], c[i][k]+c[k][j]);
  }

  int ans = 0;
  REP(i, H) REP(j, W){
    int A;
    cin >> A;
    if(A == -1) continue;
    ans += c[A][1];
  }

  cout << ans << "\n";

  return 0;
}

Measured memory_bytes: 256
#include<string.h>#include<stdio.h>

int main(){
  int ct1=0,ct2=0;
  char buf[16];
  scanf("%s",buf);
  for(int i = 0;i < strlen(buf);i++){
    if(buf[i]=='o'){ct1++;}
    else if(buf[i]=='x'){ct2++;}
  }if(15-ct2 >= 8){printf("YES\n");}
  else{printf("NO\n");}
  return 0;
}

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

#define REP(i, n) for(int (i)=0; (i)<(n); (i)++)
#define OUT(a) cout << (a) << "\n"
#define ll long long
#define uint unsigned int
#define ushort unsigned short
#define ulong unsigned long

ll MOD = 10e9 + 7;

int main() {
    int a,b;
    cin >> a >> b;
    double ans = (a/2.0+b/2.0);
    if (ceil(ans) == floor(ans)) printf("%d\n", (int)ans);
    else cout << "IMPOSSIBLE" << endl;
    return 0;
}



Measured memory_bytes: 256
b=[list(map(int,input().split()))for i in range(3)]
n=int(input())
nums=set([int(input())for i in range(n)])
for i in range(3):
    for j in range(3):
        if b[i][j] in nums:
            b[i][j]=0
flag=False
for i in range(3):
    if b[i][0] == b[i][1] == b[i][2] == 0:
        flag=True
    if b[0][i] == b[1][i] == b[2][i] == 0:
        flag=True
if b[0][0] == b[1][1] == b[2][2] == 0:
    flag=True
if b[2][0] == b[1][1] == b[0][2] == 0:
    flag=True

print("Yes" if flag else "No")

Measured memory_bytes: 3064
import java.util.*;

public class Main{

	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int A1 = sc.nextInt();
		int A2 = sc.nextInt();
		int A3 = sc.nextInt();
		
		if(A1+A2+A3>=22)
			System.out.println("bust");
		else
			System.out.println("win");

	}
}

Measured memory_bytes: 21588
#include<iostream>
#include<iostream>
#include<string>
int main(){
    std::string s1, s2;
    std::cin >> s1 >> s2;
    int result;
    result = s2.compare(0, s1.length(), s1);
    if(result == 0){
        std::cout << "Yes"<< "\n";
    }else{
        std::cout << "No"<< "\n";
    }
    return 0;
}

Measured memory_bytes: 3080
import sys

a = int(sys.stdin.readline())
b = int(sys.stdin.readline())
c = int(sys.stdin.readline())
d = int(sys.stdin.readline())
e = int(sys.stdin.readline())
k = int(sys.stdin.readline())
ret = ':(' if k < (e - a) else "Yay!"
print(ret)

Measured memory_bytes: 3060
#include <iostream>
#include <string>
#include <algorithm>

using namespace std;


int main(void) {
	int cnt[26] = { 0 };
	string s;
	cin >> s;
	for(auto c : s) {
		if (cnt[c - 'a']++) {
			cout << "no" << endl;
			return 0;
		}
	}
	cout << "yes" << endl;
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <utility>
#include <tuple>
#include <vector>
#include <string>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <algorithm>
#include <functional>
#include <climits>
#include <numeric>
#include <queue>
int main() {
	int n; std::cin >> n;
	std::vector<std::string> words(n); for (auto& w : words) std::cin >> w;
	std::vector<std::pair<int, int>> positive, negative;
	for (const auto& w : words) {
		int m{ 0 }, d{ 0 };
		for (const auto c : w) {
			if (c == '(') ++d;
			else --d;
			m = std::min(m, d);
		}
		if (d >= 0) {
			positive.emplace_back(m, d);
		}
		else {
			negative.emplace_back(m, d);
		}
	}
	std::sort(positive.begin(), positive.end(), [](const std::pair<int, int>& a, const std::pair<int, int>& b) {return a.first > b.first; });
	std::sort(negative.begin(), negative.end(), [](const std::pair<int, int>& a, const std::pair<int, int>& b) {return - a.second + a.first > -b.second + b.first; });

	int pos_current{ 0 };
	for (auto i = 0; i < positive.size(); ++i) {
		if (pos_current + positive[i].first < 0) {
			std::cout << "No\n"; return 0;
		}
		pos_current += positive[i].second;
	}
	int neg_current{ 0 };
	for (auto i = 0; i < negative.size(); ++i) {
		if (neg_current - negative[i].second + negative[i].first < 0) {
			std::cout << "No\n"; return 0;
		}
		neg_current -= negative[i].second;
	}
	if (neg_current != pos_current) {
		std::cout << "No\n";
	}
	else {
		std::cout << "Yes\n";
	}
}


Measured memory_bytes: 42492
#include <bits/stdc++.h>
#include <string>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define repp(i,n,m) for (int i = m; i < (n); ++i)
#define repl(i,n) for (long long i = 0; i < (n); ++i)
#define reppl(i,n,m) for (int i = m; i < (n); ++i)
using namespace std;
using ll = long long;

int main(){
    int n, m;
    cin >> n >> m;
    int ans = pow(100,n);
    if (m < 100){
        ans *= m;
    }
    else {
        ans *= 101;
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int a[100];
void ser(int d){
  for(int i = 0; i < d; i++){
    int ai;
    cin >> ai;
    a[ai-1] = 1;
  }
}
int main(){
  int n, k;
  cin >> n >> k;
  
  for(int i = 0; i < 100; i++) a[i] = 0;
  for(int i = 0; i < k; i++){
    int d;
    cin >> d;
    ser(d);
  }
  int sum = 0;
  for(int i = 0; i < n; i++) {
    sum += a[i];
  }
  cout << n-sum << endl;
}

Measured memory_bytes: 3632
#include<bits/stdc++.h>
#define ll long long int
using namespace std;
ll i,j;
ll t[102][100002];
ll v[102],wt[102];
ll knapsack(ll n,ll w)
{
	if(n==0||w==0)
	return 0;
	if(t[n][w]!=-1)
	return t[n][w];
	else
	{
	if(wt[n-1]<=w)
	return t[n][w]=max(v[n-1]+knapsack(n-1,w-wt[n-1]),knapsack(n-1,w));
	else if(wt[n-1]>w)
	return t[n][w]= knapsack(n-1,w);
 	}
}
int main()
{
	memset(t,-1,sizeof(t));
	cin>>i>>j;
	for(int k=0;k<i;k++)
	cin>>wt[k]>>v[k];
	ll z=knapsack(i,j);
	cout<<z<<endl;
	return 0;
	
}

Measured memory_bytes: 83196
from collections import deque
K=int(input())
ans =deque([i for i in range(1,10)])
for i in range(K):
    x = ans.popleft()
    mod_x=x%10
    if mod_x != 0:
        ans.append(x*10+mod_x-1)
    ans.append(x*10+mod_x)
    if x%10!=9:
        ans.append(x*10+mod_x+1)
print(x)

Measured memory_bytes: 11948
import copy

def solve():
    x, y = map(int, input().split())
    i = copy.copy(x)
    while i >= 0:
        tmp = 2 * i + 4 * (x - i)
        if tmp == y:
            print('Yes')
            exit()
        if tmp > y:
            print('No')
            exit()
        i -= 1
    print('No')


if __name__ == '__main__':
    solve()


Measured memory_bytes: 9344
import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        String str = sc.next();
        if(str.equals("SUN")){
            System.out.println("7");
        }else if(str.equals("MON")){
            System.out.println("6");
        }else if(str.equals("TUE")){
            System.out.println("5");
        }else if(str.equals("WED")){
            System.out.println("4");
        }else if(str.equals("THU")){
            System.out.println("3");
        }else if(str.equals("FRI")){
            System.out.println("2");
        }else if(str.equals("SAT")){
            System.out.println("1");
        }
}
}


Measured memory_bytes: 21844
def f h,r,a,b
$h[[h,r]]||=(*c,(d,e)=a
*c,(d,e)=c until !d||h>d&&r>e
*o,(p,q)=b
*o,(p,q)=o until !p||h>p&&r>q
[d ?f(d,e,c,b)+1:0,p ?f(p,q,a,o)+1:0].max)end
def g;gets.split.map &:to_i;end
while 0<n=g[0]
a=(1..n).map{g}
b=(1..g[0]).map{g}
$h={}
p f 1e3,1e3,a,b
end

Measured memory_bytes: 9148
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0;i < (int)n;i++)
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

//char -> int
int inline ctoi(char c) {
	if (c >= '0' && c <= '9') {
		return c - '0';
	}
	return 0;
}

int main()
{
    string S;
    cin >> S;
    int a = ctoi(S[0]);
    int b = ctoi(S[1]);
    int c = ctoi(S[2]);
    int d = ctoi(S[3]);
    int h[8] = {a+b+c+d,a+b+c-d,a+b-c+d,a+b-c-d,a-b+c+d,a-b+c-d,a-b-c+d,a-b-c-d};
    string op1,op2,op3;
    if(h[0] == 7)
    {
        op1 = "+";
        op2 = "+";
        op3 = "+";
    }
    
    if(h[1] == 7)
    {
        op1 = "+";
        op2 = "+";
        op3 = "-";
    }
    
    if(h[2] == 7)
    {
        op1 = "+";
        op2 = "-";
        op3 = "+";
    }
    
    if(h[3] == 7)
    {
        op1 = "+";
        op2 = "-";
        op3 = "-";
    }
    
    if(h[4] == 7)
    {
        op1 = "-";
        op2 = "+";
        op3 = "+";
    }
    
    if(h[5] == 7)
    {
        op1 = "-";
        op2 = "+";
        op3 = "-";
    }
    
    if(h[6] == 7)
    {
        op1 = "-";
        op2 = "-";
        op3 = "+";
    }

    if(h[7] == 7)
    {
        op1 = "-";
        op2 = "-";
        op3 = "-";
    }
    cout << a << op1 << b << op2 << c << op3 << d << "=7\n";
}


Measured memory_bytes: 256
n=int(input())
l=[0]*(n+1)
for i in range(1,10**2+1):
  for j in range(1,10**2+1):
    for k in range(1,10**2+1):
      tmp=i*i+j*j+k*k+i*j+j*k+k*i
      if tmp<=n:
        l[tmp]+=1
for li in l[1:]:
  print(li)


Measured memory_bytes: 74700
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <cstring>
#include <cmath>
#include <ctime>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <vector>
#include <set>
#include <map>
#define EPS 1e-9
#define PI acos(-1.0)
#define INF 0x3f3f3f3f
#define LL long long
const int MOD = 1E9 + 7;
const int N = 1000000 + 5;
const int dx[] = {0, 0, -1, 1, -1, -1, 1, 1};
const int dy[] = {-1, 1, 0, 0, -1, 1, -1, 1};
using namespace std;
LL bucket[10];
pair<int, int> node[N];
map<pair<int, int>, int> mp;
int main()
{
    LL h, w, n;
    scanf("%lld%lld%lld", &h, &w, &n);
    for (int i = 1; i <= n; i++)
    {
        int x, y;
        scanf("%d%d", &node[i].first, &node[i].second);
        mp[node[i]] = 1; //涂黑的格子贡献度为1
    }

    for (int i = 1; i <= n; i++)
    {
        for (int j = 0; j < 8; j++)
        { //统计涂黑的格子周围格子的贡献度
            int nx = node[i].first + dx[j];
            int ny = node[i].second + dy[j];
            if (nx >= 1 && nx <= h && ny >= 1 & ny <= w)
            { //越界判断
                pair<int, int> temp(nx, ny);
                mp[temp]++;
            }
        }
    }

    LL sum = 0;
    LL tot = (h - 2) * (w - 2); //总共的矩形数
    map<pair<int, int>, int>::iterator it;
    for (it = mp.begin(); it != mp.end(); it++)
    { //枚举所有涉及到的格子
        int x = it->first.first;
        int y = it->first.second;
        int val = it->second;
        if (x >= 2 && x <= h - 1 && y >= 2 & y <= w - 1)
        { //统计除去最外一圈的格子
            bucket[val]++;
            sum++;
        }
    }
    bucket[0] = tot - sum; //为0的数量是总共的矩形减去所有非零的矩形

    for (int i = 0; i <= 9; i++)
        printf("%lld\n", bucket[i]);

    return 0;
}

Measured memory_bytes: 57344
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int ksiz,ans,c[N],s[N],anss[N];
struct node{int l,r,id;}a[N];
void read(int &x){
	int f=1;x=0;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	x*=f;
}
bool cmp(node q,node p){
	int t1=(q.l-1)/ksiz,t2=(p.l-1)/ksiz;
	return t1^t2?t1<t2:q.r<p.r;
}
void add(int x){
	if(!c[s[x]])ans++;
	c[s[x]]++;
}
void del(int x){
	c[s[x]]--;
	if(!c[s[x]])ans--;
}
int main(){
	int n,m,i,x,y;
	read(n),read(m),ksiz=sqrt(n);
	for(i=1;i<=n;i++)read(s[i]);
	for(i=1;i<=m;i++)
		read(x),read(y),a[i]=(node){x,y,i};
	sort(a+1,a+1+m,cmp);
	int l=1,r=0;
	for(i=1;i<=m;i++){
		int ql=a[i].l,qr=a[i].r;
		while(l<ql)del(l++);
		while(l>ql)add(--l);
		while(r<qr)add(++r);
		while(r>qr)del(r--);
		anss[a[i].id]=ans;
	}
	for(i=1;i<=m;i++)
		printf("%d\n",anss[i]);
	return 0;
}


Measured memory_bytes: 15504
#include<bits/stdc++.h>
#define vi vector<int>
#define ii pair<int,int>
#define vii vector < ii >
#define pb push_back
#define fi first
#define se second
#define all(v) v.begin(),v.end()
#define cl(v) memset(v,0,sizeof v)
#define set(a,v) memset(v,a,sizeof v)
#define vl vector<long>
#define vll vector<long long>
#define mp make_pair
#define MAX (1<<32) -1

using  namespace std;
long x[100005];
int n;
long seg[400005];

void build(int st,int l,int r)
{
    if(l==r)
      {
          seg[st]=x[l];

          return ;
      }

    int mid=(l+r)/2;

    build( 2 * st , l , mid );

    build( 2 * st + 1, mid+1,r);

    seg[st]=min(seg[2*st],seg[2*st+1]);

}

int query(int st,int ql,int qr,int l,int r)
{
    if( ql==l && qr==r ) return seg[st];

    int mid=(l+r)/2;

    if(qr<=mid)
        return query(2*st,ql,qr,l,mid);

    else if(ql>mid)
        return query(2*st + 1,ql,qr,mid+1,r);

    int v1=query(2*st,ql,mid,l,mid);
    int v2=query(2*st+1,mid+1,qr,mid+1,r);

    return min(v1,v2);

}
void update (int st,int l,int r,int index,int val)

{
    if(index>r||index<l)return ;
    if(l==r){seg[st]=val;return;}
    int mid=(l+r)/2;
        update(2*st,l,mid,index,val);
        update(2*st+1,mid+1,r,index,val);
    seg[st]=min(seg[2*st],seg[2*st+1]);

}

int RMQ(int left,int right)
{
    return query(1,left,right,0,n-1);

}





int main()
{

    int Q;
    cin>>n>>Q;


    for(int i=0;i<n;i++)x[i]=INT_MAX;


    build(1,0,n-1);
    while(Q--)
    {
         int type;
        int l,r;
        cin>>type>>l>>r;
        if(type==1)
        cout<<RMQ(l,r)<<endl;
        else
            update(1,0,n-1,l,r);

   }

    return 0;
}

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

#define rep(i, x, n) for (int i = x; i < n; i++)
typedef long long ll;

const int INF = 1e9 + 7;

using namespace std;

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

	int n;
	cin >> n;

	vector<int> a(n);
	rep (i, 0, n)
		cin >> a[i];

	int res = 0;
	int counter = 1;
	rep (i, 0, n) {
		if (a[i] != counter)
			res++;
		else
			counter++;
	}

	if (res == n)
		cout << -1 << endl;
	else
		cout << res << endl;
	return 0;
}


Measured memory_bytes: 1152
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <cmath>
#include <algorithm>
#include <map>
#include <queue>
#include <set>
#define rep(i,n) for (ll i = 0; i < (n); ++i)
#define all(x) (x).begin(), (x).end()
#define P_B push_back
#define PO_B pop_back
#define E_B emplace_back
#define M_P make_pair
#define fi first
#define se second
#define debug(x) cout << #x << ": " << x << endl

using namespace std;
using ll = long long;
using Pii = pair<int,int>;
using Pll = pair<ll,ll>;
using VI = vector<int>;
using VL = vector<ll>;
using VVI = vector<vector<int> >;
using VVL = vector<vector<ll> >;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
//const ll LINF = (ll)1e18 - 1;
//const int INF = 1e9 - 1;
//int:±2*10^9くらい　ll:±9*10^18くらい


void Main(){
  int H, W, K, x1, x2, y1, y2;
  bool done = false;

  cin >> H >> W >> K >> x1 >> y1 >> x2 >> y2;

  vector<string> c(H+2);
  VVI D(H+2, VI(W+2,-1));

  rep(i, W+2){
    c[0] += '@';
    c[H+1] += '@';
  }
  rep(i, H){
    string C;
    cin >> C;
    c[i+1] = '@' + C + '@';
  }

  queue<Pii> Q;
  D[x1][y1] = 0;

  Q.push(M_P(x1, y1));

  while(!Q.empty()){
    int xp, yp, xn, yn;
    xp = Q.front().fi;
    yp = Q.front().se;
    Q.pop();

    rep(i, 4){
      xn = xp; yn = yp;
      rep(k, K){
        xn += dx[i]; yn += dy[i];
        if(c[xn][yn] == '@') break;
        if(D[xn][yn] >= 0 && D[xn][yn] <= D[xp][yp]) break;
        if(D[xn][yn] != -1) continue;
        D[xn][yn] = D[xp][yp] + 1;
        if(x2==xn && y2==yn){
          done = true;
          break;
        }
        Q.push(M_P(xn, yn));
      }
      if(done) break;
    }
    if(done) break;
  }

  if(done) cout << D[x2][y2] << endl;
  else cout << -1 << endl;

}

int main()
{
	cin.tie(nullptr);
  ios_base::sync_with_stdio(false);
	cout << fixed << setprecision(15);
	Main();

  return 0;
}


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

typedef long long ll;

const int MOD = 1e9 + 7;
int n, a, b;

ll power(ll a, int b) {
    ll res = 1;
    while (b) {
        if (b & 1)
            res = (res * a) % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return res;
}

ll inv(ll a) {
    return power(a, MOD - 2) % MOD;
}

ll c(int m, int n) {
    ll up = 1, down = 1;
    for (int i = m - n + 1; i <= m; ++i) up = up * i % MOD;
    for (int i = 1; i <= n; ++i) down = down * i % MOD;
    return up * inv(down) % MOD;
}

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

    cin >> n >> a >> b;

    ll res = (power(2, n) - 1 - c(n, a) - c(n, b) + MOD + MOD) % MOD;
    cout << res << endl;

    return 0;
}



Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define N 100000
 
int compare_int(const void *a, const void *b){
    return *(int*)a - *(int*)b;
}
int main(int argc, char *argv[]){
    int c=0,t,rm=0,i,n,s[N];
    scanf("%d",&n);
    for(i=0;i<n;i++)
        scanf("%d",&s[i]);
    qsort(s,n, sizeof(int), compare_int);
    for(i=0;i<n;i++){
        t=s[i];
        c=0;
        while(s[i++]==t)
            c++;
        i-=2;
        if(c>t)
            rm+=c-t;
        else if(c<t)
            rm+=c;
    }
    printf("%d\n",rm);
    return 0;
}

Measured memory_bytes: 892
#include <iostream>                                                             
using namespace std;
 
int main()
{
    int a, b, c, cnt=0;
    cin >> a >> b >> c;
    for(int i = a; i <= b; i++)
    {
        if (i <= c && c%i == 0)
            cnt ++;
    }
    cout << cnt << endl;
    return 0;
}



Measured memory_bytes: 3120
program prob4
    implicit none
    integer :: N
    integer(8), allocatable :: A(:)
    integer :: i
    integer :: ans, mode
    read(*,*) N
    allocate(A(N))
    read(*,*) A

    ans = 1
    mode = 0 !0:未定 1:増加 2:減少

    do i = 2, N
        if(A(i) == A(i-1)) then
            cycle
        else if(A(i) > A(i-1)) then
            if(mode == 0) then
                mode = 1
            else if(mode == 1) then
                mode = 1
            else 
                ans = ans + 1
                mode = 0
            end if
        else
            if(mode == 0) then
                mode = 2
            else if(mode == 1) then
                ans = ans + 1
                mode = 0
            else 
                mode = 2
            end if            
        end if

    end do
    write(*,*) ans

    deallocate(A)

    stop
contains
end program prob4

Measured memory_bytes: 3724
import java.util.*;
import java.math.*;

public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		// 整数の入力

		List<Integer> list = new ArrayList<>();
		for(int i=0;i<3;i++){
			list.add(sc.nextInt());
		}

		Collections.sort(list);

		System.out.println(list.get(0)+list.get(1)+10*list.get(2));



	}

}

Measured memory_bytes: 25044
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<cmath>
#include<climits>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<bitset>
#include<iomanip>
using namespace std;

#define rep(i,j,n) for(int i=(j);i<(n);i++)
#define rep2(i,j,n) for(int i=(j);i<=(n);i++)
#define all(i) i.begin(),i.end()
#define rall(i) i.rbegin(),i.rend()
#define INF 1e9

typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<string> vs;
typedef vector<vector<string>> vvs;
typedef pair<int, int> pi;
typedef long long i64;
typedef vector<long long int> vll;

int main() {
	int n, k;
	cin >> n >> k;
	set<string> st;
	rep(i, 0, k) {
		string d;
		cin >> d;
		st.insert(d);
	}
	while (1) {
		string s = to_string(n);
		bool ok = true;
		rep(i, 0, s.size()) {
			if (st.count(s.substr(i, 1))) {
				ok = false;
				break;
			}
		}
		if (ok) {
			cout << n << endl;
			return 0;
		}
		n++;
	}
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;

int main(){
	ios::sync_with_stdio(0);
	cout << setprecision(10) << fixed;
	long long n, k;
	cin >> n >> k;
	long long mi = 0, mx = 0;
	for (int i = 1; i < k; ++i){
		mi = (mi + i - 1 + MOD) % MOD;
		mx = (mx + n - i + 1 + MOD) % MOD;
	}
	long long ans = 0;
	for (int i = k; i <= n + 1; ++i){
		mi = (mi + i - 1 + MOD) % MOD;
		mx = (mx + n - i + 1 + MOD) % MOD;
		ans = (ans + mx - mi + MOD + 1 + MOD) % MOD;
	}
	cout << ans;
	return 0;
}



Measured memory_bytes: 3652
using System;
using System.Collections.Generic;
using System.Linq;


namespace ConsoleApp15
{
    class Class364
    {
        static int[] dy = new int[4] { 0, 1, 0, -1 };
        static int[] dx = new int[4] { 1, 0, -1, 0 };
        static void Main()
        {
            var HW = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
            int H = HW[0], W = HW[1];
            var A = new bool[H, W];
            var que = new Queue<Tuple<int,int,int>>();
            for(int i = 0; i < H; i++)
            {
                var r = Console.ReadLine();
                for(int j = 0; j < W; j++)
                {
                    if (r[j] == '#')
                    {
                        A[i, j] = true;
                        que.Enqueue(Tuple.Create(i, j, 0));
                    }
                }
            }
            var frags = new int[H, W];
            for(int i = 0; i < H; i++)
            {
                for(int j = 0; j < W; j++)
                {
                    frags[i, j] = A[i,j]?0:int.MaxValue;
                }
            }
            while (que.Count > 0)
            {
                var t = que.Dequeue();
                int y = t.Item1, x = t.Item2, c = t.Item3;
                for (int i = 0; i < 4; i++)
                {
                    int ny = y + dy[i], nx = x + dx[i];
                    if (0 <= ny && ny < H && 0 <= nx && nx < W)
                    {
                        if (frags[ny, nx] > c + 1)
                        {
                            frags[ny, nx] = c + 1;
                            que.Enqueue(Tuple.Create(ny,nx,c+1));
                        }
                    }
                }
                
            }
int max = 0;
                for (int i = 0; i < H; i++)
                {
                    for (int j = 0; j < W; j++)
                    {
                        max = Math.Max(frags[i,j], max);
                    }
                }
                Console.WriteLine(max);
        }
    }
}


Measured memory_bytes: 58800