akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
 
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3") 
#pragma GCC optimization ("unroll-loops")
 
// #include <ext/pb_ds/detail/standard_policies.hpp>
using namespace std;
using namespace __gnu_pbds;
// const ll RANDOM = chrono::high_resolution_clock::now().time_since_epoch().count();
// gp_hash_table<int, int> table;
 
#define ll  long long
#define vii vector< ll >
#define pb push_back
#define pii pair<ll,ll>
#define ppi pair<pii,ll>
#define all(x) x.begin(),x.end()
#define S second
#define F first
#define ins insert
#define ld long double
#define lp(l,r) for(i=l;i<=r;++i)
 
#define lpj(l,r) for(j=l;j<=r;++j)
#define lpr(l,r) for(i=r;i>=l;--i)
#define lprj(l,r) for(j=r;j>=l;--j)
 
#define swap(a,b){ auto _t=a;a=b,b=_t;}
#define flush() cout.flush()
#define popcount __builtin_popcount
#define die() return 0;
#define sz() size() 


 
 
#define TRACE
 
#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
    cerr << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
    const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...)
#endif
 
#define MD          1000000007
#define M 			    1000111
#define N           14
#define fftmod      998244353
#define EPS         (double)1e-10
 
long long  md=MD;
ll inf=1e18;
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); 
 
 
inline ll exp(ll a,ll b){if(a==0&&b==0)return 1ll;if(a==0)return 0ll;ll r=1LL;while(b>0){if(b&1){r=(r%md)*(a%md);r=(r+md)%md;}b/=2;a=(a%md)*(a%md);a=(a+md)%md;}return (r+md)%md;}
ll gcd(ll a,ll b){if(b==0)return a;if(a==0)return b;return gcd(b,a%b);}
inline ll poww(ll a,ll b){ll r=1LL;while(b>0){if(b&1)r=r*a;b/=2;a=a*a;}return (ll)r;}
 
using cd=complex<double>;
const double PI=acos(-1);
 
inline ll rand(ll l,ll r){
    return l+rng()%(r-l+1);
}




int main(){
 
     
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
 
 
   // ifstream fin("input.txt");ofstream fout("outut.txt");
    ll t,i,j,m,n,z,k,p;string s1,s2;ll q;ll x,y;
    string s;
    cin>>s;
    p=0;
    for(i=0;i<s.sz();++i){
      char ch='g';
      if(i%2)ch='p';
      if(s[i]=='g'&&ch=='p')++p;
      if(s[i]=='p'&&ch=='g')--p;
    }
    cout<<p<<"\n";

}



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


void solve(long long X){
    for (int i = 1; i <= 360; i++) {
        if (X * i % 360 == 0) {
            cout << i << endl;
            return;
        }
    }
}

// Generated by 1.1.7.1 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 X;
    scanf("%lld",&X);
    solve(X);
    return 0;
}


Measured memory_bytes: 3712
#include <stdio.h>
#include <stdlib.h>

#define NIL -1

typedef struct{
  int p;
  int l;
  int r;
} node;


void print(node *, int);
int depth(node *, int);


int main(){
  node u[100001];
  int n, k, id, c, l, r;
  int i, j;
  

  scanf("%d", &n);
  
  for(i = 0; i < n; i++){
    u[i].p = NIL;
    u[i].l = NIL;
    u[i].r = NIL;
  }


  for(i = 0; i < n; i++){
    scanf("%d%d", &id, &k);

    for(j = 0; j < k; j++){
      scanf("%d", &c);
      if(j == 0) u[id].l = c;

      else u[l].r = c;

      l = c;
      u[c].p = id; 
    }
  }

  for(i = 0; i < n; i++) print(u, i);
  
  return 0;
}


void print(node *u, int i){
  int c;

  printf("node %d: ", i);
  printf("parent = %d, ", u[i]);
  printf("depth = %d, ", depth(u, i));

  if(u[i].p == NIL) printf("root, ");
  if(u[i].p != NIL && u[i].l == NIL) printf("leaf, ");
  if(u[i].p != NIL && u[i].l != NIL) printf("internal node, ");

  
  printf("[");

  if(u[i].l != NIL){
    printf("%d", u[i].l);
    c = u[i].l;

    while(u[c].r != NIL){
      printf(", %d", u[c].r);
      c = u[c].r;
    }
  }

  printf("]\n");
}


int depth(node *u, int x){
  int count = 0, temp;

  while(u[x].p != NIL){
    count++;
    temp = u[x].p;
    x = temp;
  }

  return count;
}



Measured memory_bytes: 2968
import java.util.*;
import java.math.RoundingMode;
import java.math.BigDecimal;
 
 
 
public class Main{
	public static void main (String[] args){
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		n=n%1000;
		if(n>0) {
			n=1000-n;
		}
		System.out.println(n);
	}
}

Measured memory_bytes: 35752
#include<bits/stdc++.h>
using namespace std;
 
int main()
{
    int n,k;
    cin>>n>>k;
    
    int a[n];
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    
    int dp[n];
    
    dp[0]=0;
    
    for(int i=1;i<n;i++)
    {
        dp[i]=INT_MAX;
        for(int j=i-1; j>=max(0,i-k); j--)
        {
            dp[i]=min(dp[j]+abs(a[i]-a[j]), dp[i]);
        }
    }
    
    cout<<dp[n-1];
    return 0;
}

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

int main(){
    string S,T="keyence";
    cin>>S;
    int cnt=0;
    for(int i=0;i<7;i++){
        if(S[i]==T[i]) cnt++;
        else break;
    }
    for(int j=0;j<7;j++){
        if(S[S.size()-1-j]==T[6-j]) cnt++;
        else break;
    }
    if(cnt>=7) cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
}


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

#define debug(args...) \
cout << "#" << __LINE__ << ": "; \
__dbg(split(#args, ',').begin(), args);
vector<string> split(const string& s, char c) {
	vector<string> v;
	stringstream ss(s);
	string x;
	while (getline(ss, x, c))
		v.emplace_back(x);
	return move(v);
}
template<typename T, typename... Args>
inline string to_str(T x) {
	stringstream ss; ss << "[";
	for (auto it = x.begin(); it != x.end(); it++) {
		if (it != x.begin()) ss << " ";
		ss << (*it);
	}
	ss << "]";
	return ss.str();
}
template<typename T, typename... Args>
inline string to_str(stack<T> x) {
	stringstream ss; ss << "[";
	bool first = 1;
	while (!x.empty()) {
		if (!first)
			ss << " ";
		ss << x.top();
		x.pop();
		first = 0;
	}
	ss << "]";
	return ss.str();
}
template<typename T> inline void __dbg_var(vector<T> x) { cout << to_str(x); }
template<typename T> inline void __dbg_var(list<T> x) { cout << to_str(x); }
template<typename T> inline void __dbg_var(set<T> x) { cout << to_str(x); }
template<typename T> inline void __dbg_var(unordered_set<T> x) { cout << to_str(x); }
template<typename T> inline void __dbg_var(stack<T> x) { cout << to_str(x); }
template<typename T> inline void __dbg_var(T val) { cout << val; }
inline void __dbg(vector<string>::iterator it) { cout << endl; }
template<typename T, typename... Args>
inline void __dbg(vector<string>::iterator it, T a, Args... args) {
	cout << it->substr((*it)[0] == ' ', it->length()) << "=";
	__dbg_var(a);
	cout << " ";
	__dbg(++it, args...);
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	int s, w;
	cin >> s >> w;
	if (w >= s)
		cout << "unsafe\n";
	else cout << "safe\n";
	
	return 0;
}


Measured memory_bytes: 3600
#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
#define in inline
#define reg register
//#define int long long
#define MAX 20030813
using namespace std;
namespace qwq{
	in void read(int &o) {
		o=0;
		int w=1;
		char c=getchar();
		while(c<'0'||c>'9') {
			if(c=='-')w*=-1;
			c=getchar();
		}
		while(c>='0'&&c<='9') {
			o=(o<<3)+(o<<1)+(c^48);c=getchar();
		}
		o*=w;
	}
	void write(int x){
	   	if(x<0)putchar('-'),x=-x;
    	if(x>9)write(x/10);
		putchar(x%10+48);
	}
	void Write(int x) {
		write(x);putchar(' ');
	}
	in int max(int x,int y){return x>y?x:y;}
	in int min(int x,int y){return x<y?x:y;}
}
using namespace qwq;
int N,M,ans; 
signed main()
{
	read(N);read(M);
	for(reg int i=1,a;i<=N;++i)
	{
		read(a);if(a>=M)++ans;
	}
	Write(ans);
	return 0;
}




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

// マクロ
// forループ
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=(a);i<=(ll)(b);i++)
#define FORD(i,a,b) for(ll i=(a);i>=(ll)(b);i--)
// xにはvectorなどのコンテナ
#define ALL(x) (x)begin(),(x).end()
#define SIZE(x) ((ll)(x).size())
#define MAX(x) *max_element(ALL(x))
#define MIN(x) *min_element(ALL(x))
// 出力
#define PRINT(x) cout<<(x)<<endl
#define PRINTA(x,n) REP(i,n)PRINT(x[i])
// 定数
#define INF 1000000000000 // 10^12
#define MOD 1000000007 // 10^9+7
// 略記
#define PB push_back
#define MP make_pair

const int MAX_N = 200000;

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

    if (N % 2 == 0) {
        int mid1 = N / 2 - 1;
        int mid2 = N / 2;
        int mid_A = A[mid2] + A[mid1];
        int mid_B = B[mid2] + B[mid1];
        count = mid_B - mid_A + 1;
    } else {
        int mid = (N - 1) / 2;
        int mid_A = A[mid];
        int mid_B = B[mid];
        count = mid_B - mid_A + 1;
    }
    PRINT(count);
    return 0;
}

Measured memory_bytes: 4780
#include<iostream>
#include<cmath>
#include<cstdlib>
#include<string>
#include<vector>
#include<algorithm>
#include<functional>
#include<bitset>

using namespace std;

typedef long long ll;

int main() {
   int N, K;
   cin >> N >> K;
   int a[N];
   ll s[N + 1];
   s[0] = 0;
   for (int i = 0; i < N; i++) {
      cin >> a[i];
      s[i + 1] = s[i] + a[i];
   }

   vector<ll> part;

   for (int i = 0; i < N; i++) {
      for (int j = i; j < N; j++) {
         ll tmp = s[j + 1] - s[i];
         part.push_back(tmp);
      }
   }

   int N2 = N * (N + 1) / 2;
   ll ans = 0;

   for (int i = 40; i >= 0; i--) {
      // cout << "------" << i << endl;
      // cout << (1ll << i) << endl;
      int count = 0;
      for (int j = 0; j < N2; j++) {
         ll tmp1 = ans + pow(2, i);
         ll tmp2 = part[j];
         // cout << tmp1 << ":" << bitset<5>(tmp1) << endl;
         // cout << tmp2 << ":" << bitset<5>(tmp2) << endl;
         // cout << "--->" << (tmp1 & tmp2) << endl;
         if ((tmp1 & tmp2) == tmp1) count++;
      }
      if (count >= K) {
         ans += pow(2, i);
         // cout << i << ": ok " << endl;
         // cout << ans << ": ans " << endl;
      }
   }
   
   cout << ans << endl;
   return 0;
}


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

namespace ConsoleApplication6
{
    class Program
    {
        static void Main(string[] args)
        {
            var each = spr(RL()).Select(x => c2i(x)).ToList();
            var ret = each.FindIndex(x => x == 0);
            Console.WriteLine(++ret);
            Console.ReadLine();

        }

        static string RL() { return Console.ReadLine().Trim(); }
        static IEnumerable<string> spr(string s) { return s.Split(' '); }
        static Int64 c2i(string c) { return Int64.Parse(c); }
        //static double c2d(string c) { return double.Parse(c); }
        static string bool2ret(bool b) { return b ? "Yes" : "No"; }
    }
}

Measured memory_bytes: 28028
#include<iostream>
#include<string>

using namespace std;

int main(void) {
	int a, b;
	cin >> a >> b;
	if (a==b) {
		cout << "Draw" << endl;
	}
	else if (a == 1) {
		cout << "Alice" << endl;
	}
	else if (b == 1) {
		cout << "Bob" << endl;
	}
	else if (a < b) {
		cout << "Bob" << endl;
	}
	else {
		cout << "Alice" << endl;
	}
}


Measured memory_bytes: 256
import sys

class Node:
    __slots__ = ['key', 'left', 'right']
    def __init__(self, key):
        self.key = key
        self.left = self.right = None

root = None

def insert(key):
    global root
    x, y = root, None
    while x != None: x, y = x.left if key < x.key else x.right, x
    if y == None: root = Node(key)
    elif key < y.key: y.left = Node(key)
    else: y.right = Node(key)

def inorder(node):
    return inorder(node.left) + f' {node.key}' + inorder(node.right) if node else ''
def preorder(node):
    return f' {node.key}' + preorder(node.left) + preorder(node.right) if node else ''

input()
for e in sys.stdin:
    if e[0] == 'i': insert(int(e[7:]))
    else:
        print(inorder(root))
        print(preorder(root))


Measured memory_bytes: 63324
from statistics import mean, median,variance,stdev
import numpy as np
import sys
import math
import fractions
import itertools
import copy
import collections
from operator import itemgetter
#以下てんぷら
def j(q):
    if q==1: print("Yes")
    else:print("No")
    exit(0)


def ct(x,y):
    if (x>y):print("+")
    elif (x<y): print("-")
    else: print("?")

def ip():
    return int(input())
def printrow(a):
    for i in range(len(a)):
        print(a[i])
def combinations(n,r):
    if n<r:return 0
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
def permutations(n,r):
    if n<r:return 0
    return math.factorial(n) // math.factorial(n - r)

#n = ip()                                     #入力整数1つ
#n,m= (int(i) for i in input().split())       #入力整数横2つ以上
#a = [int(i) for i in input().split()]        #入力整数配列
## a = input()                                  #入力文字列
#a = input().split()                          #入力文字配列
#k = ip()                      #入力セット(整数改行あり)(1/2)
#a=[ip() for i in range(n)]    #入力セット(整数改行あり)(2/2)
#a=[input() for i in range(h)]    #入力セット(整数改行あり)(2/2)
#jの変数はしようできないので注意
#全足しにsum変数使用はsum関数使用できないので注意
#こっから本文
a = [[int(i) for i in input().split()] for k in range(3)]
for i in range(3):
    m = min(a[i])
    for k in range(3):
        a[i][k]-=m
for i in range(3):
    if not(a[0][i] == a[1][i] and a[1][i] == a[2][i]) :j(0)
j(1)


Measured memory_bytes: 13484
import sys
sys.setrecursionlimit(10 ** 8)

def Z(): return int(input())
def ZZ(): return [int(_) for _ in input().split()]

def main():
    H, W = ZZ()
    A = [ZZ() for _ in range(H)]
    done = [[False] * W for _ in range(H)]
    path = []
    operation = []

    for i in range(H):
        if i%2:
            for j in range(W)[::-1]: path.append([i, j])
        else:
            for j in range(W): path.append([i, j])
    for i in range(H*W-1):
        x, y = path[i]
        nx, ny = path[i+1]
        if A[x][y]%2:
            operation.append([x, y, nx, ny])
            A[x][y] -= 1
            A[nx][ny] += 1

    print(len(operation))
    for i, j, k, l in operation: print(i+1, j+1, k+1, l+1)

    return

if __name__ == '__main__':
    main()


Measured memory_bytes: 51936
#include<bits/stdc++.h>
#include<math.h>
#define N 100005
#define K 200005
#define MOD (int)1e9+7
#define ll long long int
using namespace std;


int main() {
   int n;
   cin>>n;
   
   vector<double> dp(n+1);
   dp[0]=1;
  for(int i=0;i<n;i++)
  {
      double p;
      cin>>p;
      for(int j=i+1;j>=0;--j)
      {
          dp[j]=(j==0? 0:dp[j-1]*p)+dp[j]*(1-p);
      }
  }
    double ans=0;
    for(int i=0;i<=n;i++)
    {   
        int t=n-i;
        if(i>t)
        ans+=dp[i];
    }
   cout << setprecision (10) << fixed << ans;
}

Measured memory_bytes: 256
import numpy as np
N, M, K =  map(int, input().split())

if N <= M:
    A_list = list(map(int, input().split()))
    B_list = list(map(int, input().split()))

if N > M:
    B_list = list(map(int, input().split()))
    A_list = list(map(int, input().split()))

    N, M = M, N

A_cum = np.cumsum([0] + A_list)
B_cum = np.cumsum(B_list)

# A list is always smaller

max_books = 0

for ind in range(len(A_cum)):
    A_books = ind
    budget = K - A_cum[ind]

    if budget < 0:
        continue

    if budget == 0:
        Total = A_books

    if budget > 0:
        B_books = np.searchsorted(B_cum, budget, side="right")
        Total = A_books + B_books

    if Total > max_books:
        max_books = Total


print(max_books)

Measured memory_bytes: 58508
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <numeric>
#include <string>

#define SCAN_INT(i) scanf("%d",i)
#define FOR(i,start,end) for(int i = start;i < end;i++)
#define PRINT_INT(i) printf("%d \n",i)
#define PRINT_TWO_INT(i,j) printf("%d %d \n",i,j)
#define PRINT_THREE_INT(i,j,k) printf("%d %d %d \n",i,j,k)


int main()
{
    int n;
    double sum = 0;
    
    scanf("%d", &n);
    for(int i = 0;i < n;i++)
    {
        double cash;
        char u[3];
        scanf("%lf", &cash);
        scanf("%s", u);
        if(u[0] == 'B')
        {
            sum += cash * 380000;
        }
        else
        {
            sum += cash;
        }
    }
    
    printf("%lf \n", sum);
    return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <math.h>
#include <limits>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <stdio.h>
#include <map>
using namespace std;
#define rep(i, n) for (int i =0; i < (int)(n); i++)
typedef pair<int, string> P;


int main() {
    string S;
    cin >> S;
    int ans = 0;
    char st, en;
   rep(i, S.size()) {
        st = S.at(i);
        en = S.at(S.size() - 1 - i);
        if(st != en )ans++;
        
    }
    cout << ans/2 << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <cstdlib>
#include <cstdio>
#include <queue>
#include <stack>
#include <list>
#include <utility>
#include <vector>
#include <set>
#include <algorithm>
#include <cmath>
#include <climits>
#include <map>
#include <unordered_map>
#include <string.h>
#include<iomanip>
#include <iterator>
#include <locale>

#define all(a) a.begin(),a.end()
#define VV(T) vector<vector< T > >
#define rep(i,N) for(int i = 0; i <N; i++)
#define repsg(i,s,g) for(int i = s; i <g; i++)
#define name(x) #x
using namespace std;

const int INF = INT_MAX;
const long long INFL =LONG_LONG_MAX;
const double PI = atan(1)*4;
const int MOD = pow(10,9)+7;
int dy[]={0, 0, 1, -1, 0};
int dx[]={1, -1, 0, 0, 0};

typedef long long ll,LL;
typedef vector<int> vint;
typedef vector<vector<int> > vvint;
typedef vector<long long> vll, vLL;
typedef vector<vector<long long> > vvll, vvLL;
typedef pair<int,int> pii;
typedef pair<LL, LL> pLL;


// vector入力
template<typename T>
istream& operator >> (istream& is, vector<T>& vec){
    for(T& x: vec) is >> x;
    return is;
}
// vector出力
template<typename T>
ostream& operator << (ostream& os, vector<T>& vec){
    for(int i=0; i<vec.size(); i++){
        os << vec[i] << ( i+1 == vec.size() ? "" : " " );
    }
    return os;
}


int main() {
    int h,w;cin>>h>>w;
    vector<string> A(h);
    rep(i,h)cin>>A[i];
    int count = 0;
    rep(i,h)rep(j,w){if(A[i][j]=='#')count++;}
    
    if(count ==h+w-1) cout<<"Possible"<<endl;
    else puts("Impossible");
    
    return 0;
}








Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
const int MOD = 1e9 + 7;
typedef long long lint;
typedef pair<int,int> P;
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define rep(i, n) for (lint i = 0; i < (n); i++)
#define INF 1e+8
#define all(x) (x).begin(),(x).end()
#define pb push_back
int d[205][205]={0};
int n,m,r;
vector<int> vr;
int res=INF;
int main(){
    cin>>n>>m>>r;
    rep(i,n){
        rep(j,n){
            if(i!=j){
                d[i][j]=INF;
            }
        }
    }
    vr.resize(r);
    rep(i,r) {
        cin>>vr[i];
        vr[i]--;
    }   
    rep(i,m){  
        lint a,b,c;
        cin>>a>>b>>c;
        a--;
        b--;
        d[a][b]=c;
        d[b][a]=c;
    }     
    for(int k=0;k<n;k++){
        for(int i=0;i<n;i++){
             for(int j=0;j<n;j++){
                d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
            }  
        }
    }
    sort(vr.begin(),vr.end());
    do{
        int sum=0;
        for(int i=0;i<r-1;i++){
            sum+=d[vr[i]][vr[i+1]];
        }
        res=min(res,sum);
    }while (next_permutation(vr.begin(), vr.end()));
    cout<<res<<endl;
    return 0;
}


Measured memory_bytes: 384
#include <stdio.h>
int main(void)
{
	int a,b,i;
	scanf("%d",&a);
	do{
		for(i=1;i<=9;a-=b,i++)scanf("%d",&b);
		printf("%d\n",a);
		scanf("%d",&a);
	}while(a!=0);
	return 0;
}



Measured memory_bytes: 2032
#include <iostream>
#include <iomanip>

#define WRITE fwrite_unlocked

constexpr int buffer_size = 1 << 18;
static int output_pos = 0;
char Output[buffer_size];

inline void put_char(const char c){
    if(output_pos == buffer_size){ WRITE(Output, 1, buffer_size, stdout); output_pos = 0; }
    Output[output_pos++] = c;
}
inline void println(int x){
    if(x){
        static char bbb[20];
        char t = 0; do{ bbb[t++] = x % 10; } while(x /= 10);
        while(t--){ put_char(bbb[t] ^ 48); }
    }
    else put_char('0');
    put_char('\n');
}


constexpr int mod = 998244353;

int height = 0;
int length;
int sum_arr[1 << 20];
int value[1 << 20];
char belong[1 << 20];

void build(int n){
    height = 31 - __builtin_clz(n); if((length = (1 << height)) < n){ length *= 2; ++height; }

    for(int i = n - 1, v = 1; i >= 0; --i){ sum_arr[i + length] = v; v = 10LL * v % mod; }
    for(int i = length - 1; i > 0; --i){
        sum_arr[i] = sum_arr[2 * i] + sum_arr[2 * i + 1];
        if(sum_arr[i] >= mod) sum_arr[i] -= mod;
    }
}

inline void propagate(const int x){
    for(int shift = height; shift ; --shift){
        const int idx = x >> shift;
        if(belong[idx]){
            belong[2 * idx] = belong[idx];
            belong[2 * idx + 1] = belong[idx];
            value[idx] = static_cast<long long int>(sum_arr[idx]) * belong[idx] % mod;
            belong[idx] = 0;
        }
    }
    if(belong[x]){ value[x] = static_cast<long long int>(sum_arr[x]) * belong[x] % mod; belong[x] = 0; }
}

inline void calculateData(int x){
    while(x >>= 1){
        const int c1 = 2 * x, c2 = c1 + 1;
        const int a = belong[c1] ? static_cast<long long int>(sum_arr[c1]) * belong[c1] % mod : value[c1];
        const int b = belong[c2] ? static_cast<long long int>(sum_arr[c2]) * belong[c2] % mod : value[c2];
        value[x] = a + b; if(value[x] >= mod) value[x] -= mod;
    }
}

inline void update(int l, int r, char c){
    propagate(l += length); propagate(r += length - 1);
    for(int li = l, ri = r + 1; li < ri; li >>= 1, ri >>= 1){
        if(li & 1) belong[li++] = c;
        if(ri & 1) belong[--ri] = c;
    }
    calculateData(l); calculateData(r);
}

inline int sum_all(void){
    return value[1];
}


int main(void){
    std::cin.tie(nullptr); std::ios_base::sync_with_stdio(false); 
    std::cout << std::fixed << std::setprecision(16);
    int n, q; std::cin >> n >> q;
    build(n);
    update(0, n, 1);

    while(q--){
        int l, r; char c; std::cin >> l >> r >> c; --l;
        update(l, r, c - '0');
        println(sum_all());
    }
    WRITE(Output, 1, output_pos, stdout);
    return 0;
}


Measured memory_bytes: 7624
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
#define INT(...) int __VA_ARGS__;in(__VA_ARGS__)
#define LL(...) ll __VA_ARGS__;in(__VA_ARGS__)
#define ULL(...) ull __VA_ARGS__;in(__VA_ARGS__)
#define STR(...) string __VA_ARGS__;in(__VA_ARGS__)
#define CHR(...) char __VA_ARGS__;in(__VA_ARGS__)
#define DBL(...) double __VA_ARGS__;in(__VA_ARGS__)
#define vec(type,name,...) vector<type> name(__VA_ARGS__)
#define VEC(type,name,size) vector<type> name(size);in(name)
#define vv(type,name,h,...) vector<vector<type>>name(h,vector<type>(__VA_ARGS__))
#define VV(type,name,h,...) vector<vector<type>>name(h,vector<type>(__VA_ARGS__));in(name)
#define vvv(type,name,h,w,...) vector<vector<vector<type>>>name(h,vector<vector<type>>(w,vector<type>(__VA_ARGS__)))
#define SYOU(x) fixed<<setprecision(x) //小数点桁数を指定する
inline int scan(){ return getchar(); }
inline void scan(int &a){ scanf("%d", &a); }
inline void scan(unsigned &a){ scanf("%u", &a); }
inline void scan(long &a){ scanf("%ld", &a); }
inline void scan(long long &a){ scanf("%lld", &a); }
inline void scan(unsigned long long &a){ scanf("%llu", &a); }
inline void scan(char &a){ cin >> a; }
inline void scan(float &a){ scanf("%f", &a); }
inline void scan(double &a){ scanf("%lf", &a); }
inline void scan(long double &a){ scanf("%Lf", &a); }
inline void scan(vector<bool> &vec){ for(unsigned i = 0; i < vec.size(); i++) { int a; scan(a); vec[i] = a; } }
inline void scan(string &a){ cin >> a; }
template<class T> inline void scan(vector<T> &vec);
template<class T, size_t size> inline void scan(array<T, size> &vec);
template<class T, class L> inline void scan(pair<T, L> &p);
template<class T, size_t size> inline void scan(T (&vec)[size]);
template<class T> inline void scan(vector<T> &vec){ for(auto &i : vec) scan(i); }
template<class T, size_t size> inline void scan(array<T, size> &vec){ for(auto &i : vec) scan(i); }
template<class T, class L> inline void scan(pair<T, L> &p){ scan(p.first); scan(p.second); }
template<class T, size_t size> inline void scan(T (&vec)[size]){ for(auto &i : vec) scan(i); }
template<class T> inline void scan(T &a){ cin>>a; }
inline void in(){}
template <class Head, class... Tail> inline void in(Head &head, Tail&... tail){ scan(head); in(tail...); }
inline constexpr ll gcd(ll a,ll b){if(!a||!b)return 0;while(b){ll c=b;b=a%b;a=c;}return a;}
inline constexpr ll lcm(ll a,ll b){if(!a||!b)return 0;return a*b/gcd(a,b);}
inline ll mod(ll val, ll m) {long long res = val % m;if (res < 0) res += m;return res;}
inline int divisor_count(int n) {int j, c = 1;for (int i = 2; i * i <= n; i++, c *= j)for (j = 1; !(n % i); j++) n /= i;return (1 < n) ? c * 2 : c;}
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
using Graph = vector<vector<int>>;
/* 4方向への隣接頂点への移動を表すベクトル */
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

const long long INF = 1LL << 60;
const ll MOD = 1000000007;
int main(){
    INT(a,b);
    cout << a*b << endl;
    return 0;
}

Measured memory_bytes: 3676
#define _USE_MATH_DEFINES
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <climits>
#include <clocale>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <regex>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

#define IOS ios::sync_with_stdio(false); cin.tie(0);
#define FOR(i, s, n) for(int i = (s), i##_len=(n); i < i##_len; ++i)
#define FORS(i, s, n) for(int i = (s), i##_len=(n); i <= i##_len; ++i)
#define VFOR(i, s, n) for(int i = (s); i < (n); ++i)
#define VFORS(i, s, n) for(int i = (s); i <= (n); ++i)
#define REP(i, n) FOR(i, 0, n)
#define REPS(i, n) FORS(i, 0, n)
#define VREP(i, n) VFOR(i, 0, n)
#define VREPS(i, n) VFORS(i, 0, n)
#define RFOR(i, s, n) for(int i = (s), i##_len=(n); i >= i##_len; --i)
#define RFORS(i, s, n) for(int i = (s), i##_len=(n); i > i##_len; --i)
#define RREP(i, n) RFOR(i, n, 0)
#define RREPS(i, n) RFORS(i, n, 0)
#define IREP(i, v) for(auto i = (v).begin(); i != (v).end(); ++i)
#define IRREP(i, v) for(auto i = (v).rbegin(); i != (v).rend(); ++i)
#define ALL(v) (v).begin(), (v).end()
#define SORT(v) sort(ALL(v))
#define RSORT(v) sort(ALL(v), greater<decltype(v[0])>())
#define SZ(x) ((int)(x).size())
#define REV(x) reverse(ALL(x))
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define MT make_tuple
#define BIT(n) (1LL<<(n))
#define UNIQUE(v) v.erase(unique(ALL(v)), v.end())

using ld = long double;
using ll = long long;
using ui = unsigned int;
using ull = unsigned long long;
using Pi_i = pair<int, int>;
using Pll_ll = pair<ll, ll>;
using VB = vector<bool>;
using VC = vector<char>;
using VD = vector<double>;
using VI = vector<int>;
using VLL = vector<ll>;
using VS = vector<string>;
using VSH = vector<short>;
using VULL = vector<ull>;

const int MOD = 1000000007; 
const int INF = 1000000000; //1e9
const int NIL = -1;
const ll LINF = 1000000000000000000; // 1e18
const double EPS = 1E-10;

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


int main(){
    int K, N, ans; cin >> K >> N;
    VI A(N);
    REP(i, N) cin >> A[i];
    ans = A[N-1] - A[0];
    FOR(i, 1, N)
        chmin(ans, K + A[i-1] - A[i]);
    cout << ans << endl;
    return 0;
}


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

static class Program
{
    static void Main()
    {
        var s = Console.ReadLine();
        var t = Console.ReadLine();

        var answer =
            t.Length -
            Substrings(s, t.Length)
                .Max(substr => substr
                    .Select((c, i) => c == t[i])
                    .Count(b => b));
        Console.WriteLine(answer);
    }

    static IEnumerable<string> Substrings(string input, int length)
    {
        if (length == 0)
        {
            yield return "";
        }
        else
        {
            for (var i = 0; i < input.Length - length + 1; i++)
            {
                yield return input.Substring(i, length);
            }
        }
    }
}

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

// typedef long long int ll;
// typedef vector<int> vi; 
// typedef pair<int,int> pi; 
// typedef vector<ll> vll; 


// #define F first;
// #define S second;
// #define PB push_back;
// #define MP make_pair;
// #define rep(i, a, b) for (int i=a; i<b; i++)


#include<bits/stdc++.h>
using namespace std;
int cnt1[100003],cnt2[100003],n,x,mx1,mx2,x1,x2;
int main(){
	cin>>n;
	for(int i=0;i<n;i++)
	{
		cin>>x;
		if(i%2==0)
		{
			cnt1[x]++;
			if(mx1<cnt1[x])
				mx1=cnt1[x],
				x1=x;
		}
		else
		{
			cnt2[x]++;
			if(mx2<cnt2[x])
				mx2=cnt2[x],
				x2=x;
		}
	}
	sort(cnt1,cnt1+100003);
	sort(cnt2,cnt2+100003);
	if(x1!=x2)
		cout<<n-mx1-mx2;
	else
		cout<<n-max(mx1+cnt2[100001],mx2+cnt1[100001]);
}



// int main(){
// 	ll t;
// 	cin >>t;
//     ll a[t],b[t];
// 	rep(i,0,t){
// 		cin>>a[i];
//         b[i]=0;
// 	}
//     ll n ;
//     rep(i,0,t){
//         rep(j,0,t){
//             if(a[j]==a[i]){
//                 b[i] +=1;
//             }
//         }
//     }

//     ll f=INT32_MIN,s=INT32_MIN;
//     rep(i,0,t){
//         if(b[i]>f){
//             s = f;
//             f = b[i];
//         }
        
//         else if(b[i]>s && b[i]<f )
//         {
//             s = b[i];
//         }

        
        
//     }
//     ll num;
//     if(f==s){
//         cout <<"0";
//     }
//     else if(s<t/2 && f >t/2 ){
//         cout << (t/2)-s;
//     }
//     else if(s<t/2 && f<t/2){
//         cout << t - (f+s);
//     }
//     cout << num;


// 	return 0;
// }

Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
 
#pragma GCC                   target ("avx2")
#pragma GCC                   optimize("Ofast")
#pragma GCC                   optimization ("O3")
#pragma GCC                   optimization ("unroll-loops")
#pragma GCC                   target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define mod                   1000000007
#define INF                   1000000000000000000
#define int                   long long
#define PI                    3.14159265359
#define Author                std::ios_base::sync_with_stdio(0);
#define ABHISHEK_SHARMA       cout.tie(0);
#define IIIT_ALLAHABAD        cin.tie(0);
#define all(v)                v.begin(),v.end()
#define pb(a)                 push_back(a)
#define lb(v,t)               lower_bound(all(v),t)-v.begin()
#define ub(v,t)               upper_bound(all(v),t)-v.begin()
 
clock_t time_p=clock();
 
void abhishhh1(){
    time_p=clock()-time_p;
    cerr<<"Time Taken : "<<(double)(time_p)/(1.0*CLOCKS_PER_SEC)<<"\n";
}
 
void solve() {
    int n,m;
    cin>>n>>m;
    vector<int> adj[n+1];
    for(int i=1;i<=m;i++) {
        int u,v;
        cin>>u>>v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    queue<int> q;
    int ans[n+1];
    q.push(1);
    vector<int> vis(n+1);
    vis[1]=1;
    while(!q.empty()) {
        int x=q.front();
        q.pop();
        for(auto it:adj[x]) {
            if(!vis[it]) {
                ans[it]=x;
                q.push(it);
                vis[it]=1;
            }
        }
    }
    cout<<"Yes\n";
    for(int i=2;i<=n;i++) {
        cout<<ans[i]<<"\n";
    }
    cout<<"\n";
    
}
 
signed main(){
    //file reader-writer
#ifndef ONLINE_JUDGE
   freopen("input.txt","r",stdin);
   freopen("output.txt","w",stdout);
#endif
    //Booster
    Author
    ABHISHEK_SHARMA
    IIIT_ALLAHABAD
    //Driver Code here
    int t=1;
    //cin>>t;
    for(int i=1; i<=t; i++){
        //cout<<"Case #"<<i<<": ";
        solve();
    }
    abhishhh1();
}

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


int32_t main(){
	ios_base::sync_with_stdio(false);cin.tie(0);
	int n;
	cin >> n;
	int res=0;
	for(int i=1;i<=n;i++){
		if(i%3!=0 && i%5!=0){
			res+=i;
		}
	}
	cout << res << endl;
	return 0;
}


Measured memory_bytes: 3648
while True:
    n=int(input())
    x=[]
    if n==0:
        break
    else:
        for i in range(n):
            s=int(input())
            x.append(s)
        a=min(x)
        b=max(x)
        ave=(sum(x)-a-b)/(n-2)
        print(int(ave))


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

const int MAXN = 3000 + 15;

ll f[MAXN][MAXN][5];
int a[MAXN][MAXN];

int main() {

    int r, c, k;
    scanf("%d %d %d", &r, &c, &k);

    for(int i = 1; i <= k; i++) {
        int x, y, val;
        scanf("%d %d %d", &x, &y, &val);
        a[x][y] = val;
    }

    for(int i = 1; i <= r; i++) {
        for(int j = 1; j <= c; j++) {
            for(int z = 0; z <= 3; z++) { // 由上转移
                f[i][j][0] = max(f[i][j][0], f[i - 1][j][z]);

                f[i][j][1] = max(f[i][j][1], f[i - 1][j][z] + a[i][j]);
            }

            for(int z = 0; z <= 3; z++) { // 由左转移
                f[i][j][z] = max(f[i][j][z], f[i][j - 1][z]);

                if(z > 0) f[i][j][z] = max(f[i][j][z], f[i][j - 1][z - 1] + a[i][j]);
            }

        }
    }

    ll res = 0;

    for(int z = 0; z <= 3; z++) res = max(res, f[r][c][z]);
    printf("%lld\n", res);
    return 0;
}

Measured memory_bytes: 392464
#include <bits/stdc++.h>
using namespace std;
using int64 = long long;
#define int int64
#define rep(i, n) for(int i=0; i<n; i++)
#define FOR(i, a, b) for(int i=a; i<b; i++)
#define SORT(x) sort(x.begin(), x.end())
#define GSORT(x) sort(x.begin(), x.end(), greater<int>())
#define mk make_pair
#define fi first
#define se second
#define pb push_back
#define ALL(x) x.begin(), x.end()
#define V(T) vector<T>
typedef pair<int, int> P;
typedef pair<P, P> PP;
typedef vector<int> vi;
typedef vector<vi> vvi;
int max(int a, int b) {if(b>a) return b; else return a;}
int min(int a, int b) {if(b<a) return b; else return a;}

const int MOD = 1000000007;
const int MAX = 200010;
int fac[MAX], finv[MAX];

int mmul(int a, int b) {
    return ((a%MOD)*(b%MOD))%MOD;
}

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

int mdiv(int a, int b) {
    return (a * mpow(b, MOD-2)) % MOD;
}

int mcomb(int n, int k) {
    if(n<k || k<0) return 0;
    else return mmul(mmul(fac[n], finv[k]), finv[n-k]);
}

inline void INIT_F(){
    fac[0] = finv[0] = 1;
    for(int i=1; i<MAX-1; i++) {
        fac[i] = (fac[i-1]*i) % MOD;
        finv[i] = mdiv(finv[i-1], i);
    }
}

signed main() {
    INIT_F();
    int n, k;
    cin >> n >> k;
    vi a(n);
    rep(i, n) cin >> a[i];
    SORT(a);

    int misum = 0, mxsum = 0;
    FOR(i, k-1, n) {
        int tx = mmul(a[i], mcomb(i, k-1));
        int ti = mmul(a[n-1-i], mcomb(i, k-1));
        mxsum = ((mxsum%MOD) + (tx%MOD))%MOD;
        misum = ((misum%MOD) + (ti%MOD))%MOD;
    }

    int res = ((mxsum%MOD) - (misum%MOD))%MOD;
    cout << res << endl;
    
    return 0;
}

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

int main() {
    int N;
    cin >> N;
    vector<ll> A(N);
    map<ll, ll> cnt;
    for (int i = 0; i < N; i++) {
        cin >> A[i];
        cnt[A[i]]++;
    }

    sort(A.begin(), A.end());
    int ans = 0;
    for (int i = N - 1; i >= 0; i--) {
        if (cnt[A[i]] == 0)
            continue;
        cnt[A[i]]--;
        ll nxt = 1;
        while (nxt <= A[i]) {
            nxt *= 2;
        }

        if (cnt[nxt - A[i]] > 0) {
            ans++;
            cnt[nxt - A[i]]--;
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 26752
n, a, b = [int(i) for i in input().split()]

if ((b - a) % 2 == 0):
    print((b - a) // 2)
else:
    print(n - b + (b - a + 1) // 2 if (a - 1) > (n - b) else a - 1 + (b - a + 1) // 2)


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

int main(){
    string S;
    cin >> S;
    int s=S.size();
    vector<char> vec(s);
    for(int i=0;i<s;i++){
        vec[i] = S[i];
    }
    for(int i=0;i<s;i++){
        for(int j=i+1;j<s;j++){
            if(vec[i]==vec[j]){
                cout << "no" << endl;
                return 0;
            }
        }
    }
    cout << "yes" << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = (int)1e9 + 7;
const int INF = (int)100100100;

int main() {
    //ll N; cin >> N;
    ll A,B; cin >> A >> B;
    //string S; cin >> S;
    //ll H,W; cin >> H >> W;
    int K;
    cin >> K;
    for(int i=0;i<K;i++){
        if(i%2==0){
          A=A/2;
          B+=A;
        }
        else{
          B=B/2;
          A+=B;
        }
    }
    


    cout << A << ' ' << B << endl;
}

/*



 */



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

#define FOR(i, a, b) for(int i=(a); i<(b); i++)
#define RFOR(i, a, b) for(int i=(a); i>=(b); i--)
#define REP(i, n) FOR(i, 0, n)
#define RREP(i, n) RFOR(i, n, 0)
#define CEIL(n, m) ceil(n/pow(10.0, m))*pow(10.0, m)
#define FLOOR(n, m) floor(n/pow(10.0, m))*pow(10.0, m)
#define ROUND(n, m) round(n/pow(10.0, m))*pow(10.0, m)
#define ALL(x) (x).begin(),(x).end()
#define SORT(x) sort((x).begin(),(x).end())
#define RSORT(x) sort((x).begin(),(x).end(),greater<int>())
#define SZ(x) ((int)(x).size())
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );
#define llong long long
#define dump(x)  cout << #x << " = " << (x) << endl;
#define debug(x) cout << #x << " = " << (x) " (L" << __LINE__ << ") " << __FILE__ << endl;

void solve()
{
  int n; cin >> n;
  vector<int> s(n); REP(i, n) cin >> s[i];

  vector<vector<int>> dp(n+1, vector<int>(10010, 0));
  dp[0][0] = 1;

  for (int i=0; i<n; i++) {
    for (int j=0; j<10010; j++) {
      if (j>=s[i]) {
        dp[i+1][j] = dp[i][j] + dp[i][j-s[i]];
      } else {
        dp[i+1][j] = dp[i][j];
      }
    }
  }
  int ans = 0;
  for (int i=10010-1; i>=0; i--) {
    if (dp[n][i]>0 && i%10!=0) {
      ans = max(ans, i);
    }
  }

  cout << ans << endl;
}

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


Measured memory_bytes: 4224
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <queue>
#include <iostream>
#include <bitset>
using namespace std;
#define N 200005
char s[N];int n,a[N];
int main()
{
	scanf("%d%s",&n,s+1);int ans=n;
	for(int i=1;i<=n;i++)a[i]=a[i-1]+(s[i]=='.');
	for(int i=0;i<=n;i++)ans=min(ans,(i-a[i])+(a[n]-a[i]));
	printf("%d\n",ans);
}

Measured memory_bytes: 1280
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,m,sum=0,i,j;
    cin>>n>>m;
    for(i=n-1;i>0;i--)
    sum=sum+i;
    for(j=m-1;j>0;j--)
    sum=sum+j;
    cout<<sum;
}

Measured memory_bytes: 256
#include "iostream"
#include "climits"
#include "list"
#include "queue"
#include "stack"
#include "set"
#include "functional"
#include "algorithm"
#include "string"
#include "map"
#include "unordered_map"
#include "unordered_set"
#include "iomanip"
#include "cmath"
#include "random"
#include "bitset"
#include "cstdio"
#include "numeric"
#include "ctime"

using namespace std;

const long long int MOD = 1000000007;
//const int MOD = 998244353;

//long long int N, M, K, H, W, L, R;
long long int N, M, K, H, W, L, R;

struct range {
	int l;
	int r;
	int num;
};

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

	cin >> N;
	vector<int>v(N);
	for (auto &i : v)cin >> i;
	R = N;
	L = 0;
	while (R - L > 1) {
		long long int mid = (R + L + 1) / 2;
		stack<range>st;
		st.push({ 1,v[0],1 });
		bool flag = true;
		for (int i = 1; i < N; i++) {
			if (v[i] > st.top().r) {
				st.push({ st.top().r + 1,v[i],1 });
				continue;
			}
			while (v[i] < st.top().l)st.pop();
			auto box = st.top();
			if (box.num != mid) {
				st.pop();
				if (box.l != v[i]) {
					st.push({ box.l,v[i] - 1,box.num });
				}
				st.push({ v[i],v[i],box.num + 1 });
				continue;
			}
			while (!st.empty() && st.top().num == mid) {
				st.pop();
			}
			if (st.empty()) {
				flag = false;
				break;
			}
			box = st.top();
			st.pop();
			if (box.l != box.r) {
				st.push({ box.l,box.r - 1,box.num });
			}
			st.push({ box.r,box.r,box.num + 1 });
			if (box.r != v[i]) {
				st.push({ box.r + 1, v[i], 1 });
			}
		}
		if (flag)R = mid;
		else L = mid;
	}
	cout << R << endl;
	return 0;
}


Measured memory_bytes: 3524
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
using namespace std;
int main() {
    double a,b,x;
    static const double pi = acos(-1);
    cin>>a>>b>>x;

    double s,e;

    double deg;
    double h;
    double w;

    if (x/a>=(a*b)/2){
        s=0;
        e=90;

        h = 2*b-((2*x)/(a*a));

        deg = abs(s - e) / 2 + min(e, s);

        for (int i = 0; i < 100000; ++i)  {

            if (tan(deg * pi / 180) == h / a){
                printf("%.10f\n", deg);
                return 0;
            }else if (tan(deg * pi / 180) < h / a){
                s = deg;
                deg = abs(e - deg) / 2 + min(deg, e);

            }else if(tan(deg * pi / 180) > h / a){
                e = deg;
                deg = abs(deg - s) / 2 + min(deg, s);

            }
        }
        printf("%.10f\n", deg);
        return 0;

    }else {

        s = 0;
        e = 90;

        w = (2*x)/(a*b);
        deg = abs(s - e) / 2 + min(e, s);


        for (int j = 0; j < 100000; ++j) {


            if (tan(deg * pi / 180) == b / w) {
                printf("%.10f\n", deg);
                return 0;
            } else if (tan(deg * pi / 180) < b / w) {
                s = deg;
                deg = abs(e - deg) / 2 + min(deg, e);
            } else if (tan(deg * pi / 180) > b / w) {
                e = deg;
                deg = abs(deg - s) / 2 + min(deg, s);

            }
        }
        printf("%.10f\n", deg);
    }
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <cstdlib>
#include <cstdio>
#include <queue>
#include <stack>
#include <list>
#include <utility>
#include <vector>
#include <set>
#include <algorithm>
#include <cmath>
#include <climits>


#define REP(i,N) for(auto i = 0; i <N; i++)
using namespace std;
typedef long long ll;


int in(){
    int temp;
    scanf("%d",&temp);
    return temp;
}

ll lin(){
    ll temp;
    scanf("%lld",&temp);
    return temp;
}



int main() {

    int N = in();
    
    vector< pair<int,int> > a;
    vector< pair<int,int> > b;
    
    for(auto i = 0; i <N; i++){
        a.push_back(make_pair(in(),in()));
    }

    for(auto i = 0; i <N; i++){
        b.push_back(make_pair(in(),in()));
    }
    
    sort(a.begin(),a.end(),[](pair<int,int> t1, pair<int,int> t2){return t1.first > t2.first;});
    sort(b.begin(),b.end(),[](pair<int,int> t1, pair<int,int> t2){return t1.second < t2.second;});
    
    int used[2*N];
    for(auto i = 0; i <2*N; i++){
        used[i] = 0;
    }
    
    int ans = 0;
    
    for(auto red: a){
        
        auto point = upper_bound(b.begin(),b.end(),red,[](const pair<int,int> &t1, const pair<int,int> &t2)->bool{return t1.second < t2.second;});
        
        if (point == b.end()) continue;
        
        while(1){
            
            if (point == b.end()) break;
            if (used[(*point).second] == 0 && (*point).first > red.first) break;
            
            point++;
        }
        
        if (point != b.end()){
            used[(*point).second] = 1;
            ans +=1;
        }
        
    }
    
    cout << ans << endl;
    
    return 0;
}




                          




Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <algorithm>
#include <cctype>
#include <cmath>
#include <queue>
#include <map>
#include <numeric>
#include <unordered_map>
#include <iomanip>
#include <functional>
#include <bitset>
#include <complex>
#include <stack>



#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define repi(i,a,b) for(int i=int(a);i<int(b);i++)
#define all(x) (x).begin(),(x).end()

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

typedef long long ll;

using namespace std;


class UnionFind
{
public:
  UnionFind(int n)//0~n-1までitemを初期化
  {
    parent=vector<int>(n,-1);//親なら-size
    weight=vector<int>(n,0);
  }
  int root(int a)
  {
    if(parent[a]<0)return a;
    root(parent[a]);
    weight[a]+=weight[parent[a]];
    return parent[a]=root(parent[a]);
  }
  int size(int a)
  {
    return -parent[root(a)];
  }
  bool connect(int a,int b,int cost)
  {
    int A=root(a);
    int B=root(b);
    cost+=weight[a];
    cost-=weight[b];
    if(A==B && cost!=0)return false;
    if(A==B)return true;
    if(size(A)>size(B))
    {
      swap(A,B);
    }
    else cost=-cost;
    weight[A]=cost;
    parent[B]+=parent[A];
    parent[A]=B;
    return true;

  }
private:
  vector<int> parent;
  vector<int> weight;

};
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;cin>>n;
  int m;cin>>m;
  UnionFind uf(n+1);
  rep(i,m)
  {
    int x,y,z;
    cin>>x>>y>>z;
    x--;y--;
    uf.connect(x,y,z%2);
  }
  int res=0;
  rep(i,n)
  {
    if(uf.root(i)==i)res++;
  }
  cout<<res<<endl;
  return 0;

}


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

int main() {
  string S ;
  cin >> S ;
  int ans = S[0] - '0' ;
  //int anstest = S[1] - '0' ;
  //cout << ans << endl ;
  rep(i,1<<3){
    rep(j,3){
      if( i>>j & 1 ) ans += ( S[j+1] - '0' ) ;
      else ans -= ( S[j+1] - '0' );
    }
    //cout << ans << endl ;
    if( ans == 7 ){
      rep(j,3){
        cout << S[j] ;
        if( i>>j & 1 ) cout << '+' ;
        else cout << '-' ;
      }
      cout << S[3] << "=7" << endl;
      return 0 ;
    }
    ans = S[0] - '0'  ;
  }
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define re register
#define Maxn 10010
signed main(){
	ll n,f[87]={2,1};
	cin>>n;
	for(int i=2;i<=n;i++) f[i]=f[i-1]+f[i-2];
	printf("%lld\n",f[n]);
    return 0;
}

Measured memory_bytes: 256