akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")

using namespace std;
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
typedef long long ll;
#define rep(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define REP(i,num,n) for(int i=num, i##_len=(n); i<i##_len; ++i)
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; }
#define print(x) (cout << (x) << endl)
#define pb push_back
#define mp make_pair
#define sz(x) int(x.size())
template<class T> inline void Yes(T condition){ if(condition) cout << "Yes" << endl; else cout << "No" << endl; }
#define fs first
#define sc second
// 多倍長
#include <boost/rational.hpp>
#include <boost/multiprecision/cpp_int.hpp>
using boost::rational;
using boost::multiprecision::cpp_int;

const int INF = 1e9;
const ll LLINF = 1e16;
const ll MOD = 1e9+7;
template<class T> inline void add(T &a, T b){a = ((a+b) % MOD + MOD) % MOD;};

template<typename T>
vector<T> make_v(size_t a){return vector<T>(a);}
 
template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts){
  return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}
 

// 指定した文字cが文字列に何文字入ってるか
ll stringcount(string s, char c) {
    return count(s.cbegin(), s.cend(), c);
}


// 割り算の切り上げ処理
template<typename T>
T rp(T a, T b) {
  return (a + b - 1) / b;
}

// 桁和
template<typename T>
T digsum(T n) {
    T res = 0;
    while(n > 0) {
        res += n%10;
        n /= 10;
    }
    return res;
}

// 回文判定
bool kai (string s) {
    string t{s};
    reverse(begin(t), end(t));
    return s == t;
}

using pint = pair<int, int>;
using pll = pair<ll, ll>;


int main(void)
{
    cout.tie(0);
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(20);
    int n;
    cin >> n;
    vector<int> a(n);
    rep(i, n) cin >> a[i];
    vector<int> cnt(1000005);
    for(int x : a){
        if(cnt[x] != 0){
            cnt[x] = 2;
            continue;
        }
        for(int i = x; i < 1000005; i += x) cnt[i]++;
    }
    int ans = 0;
    for(int x : a){
        if(cnt[x] == 1) ans++;
    }
    print(ans);

}



Measured memory_bytes: 7948
import sys


# get from std-I/O.
def loading_inputs():
    S = raw_input()
    S = int(S)
    return S


def an_func(an):
    if an%2==0: an = an/2
    else :      an = (3*an) + 1
    return an


def check_index(li, x, i, default=-1):
    if x in li: return i + 1
    else:       return default



def main():

    ans = 0
    an  = list()

    a_i = loading_inputs()
    an.append(a_i)
    for i in range(1, 10**6):

        a_i = an_func(a_i)
        ans = check_index(an, a_i, i)
        if(ans!=-1):
            break
        else:
            an.append(a_i)

    print ans



if __name__ == "__main__":
    main()

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

#define ft first
#define sd second
#define sz(x) ((int)x.size())

using namespace std;

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









int main() {
	int x, y;
	cin >> x >> y;
	cout << ((x % y)? x: -1);
	return 0;
}

Measured memory_bytes: 256
#[allow(unused_macros)]
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };

    ($next:expr, mut $var:ident : $t:tt $($r:tt)*) => {
        let mut $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

#[allow(unused_macros)]
macro_rules! debug {
    ($($a:expr),*) => {
        #[cfg(debug_assertions)]
        writeln!(&mut std::io::stderr(), concat!("[DEBUG] ", $(stringify!($a), "={:?} "),*), $($a),*);
    }
}

#[allow(unused_imports)]
use std::cmp::{min, max};

#[allow(unused_imports)]
use std::io::Write;

fn main() {
    input!{
      n: usize,
      l: i64,
    }
    let mut ls: Vec<_> = (1..n+1).map(|i| l + i as i64 - 1).map(|v| (v.abs(), v)).collect();
    ls.sort();
    let ans = &(ls[1..n]).into_iter().map(|&(v1, v2)| v2).sum::<i64>();
    println!("{}", ans);
}


Measured memory_bytes: 4352
using System;
using System.Linq;

class C
{
	static void Main()
	{
		var h = Console.ReadLine().Split().Select(int.Parse).ToArray();
		var r = Enumerable.Range(10 * h[1], 10).FirstOrDefault(x => x * 2 / 25 == h[0]);
		Console.WriteLine(r > 0 ? r : -1);
	}
}


Measured memory_bytes: 28376
#include <bits/stdc++.h>
    using namespace std;
     
    int main(){
     	char c;cin>>c;
      if(c=='A')c='T';
      else if(c=='T')c='A';
      else if(c=='C')c='G';
      else if(c=='G')c='C';
      cout<<c<<endl;
    }

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

int main()
{
    int N ;
    cin>>N ;
    vector<long long int>arr(N);
    for(int i=0;i<N;i++)
        cin>>arr[i];
        
    long long int capital = 1000 , x = 0 ;
    for(int i=0;i<N;i++)
    {
        if(i<N-1 && arr[i]<arr[i+1])
        {
            x = (capital/arr[i]);
            capital-=(x*arr[i]);
            capital+=(x*arr[i+1]);
        }
    }
    cout<<capital;
    return 0;
}


Measured memory_bytes: 3632
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
int main(){
  ll N;
  cin>>N;
  map<ll,ll> data;
  for(ll i=0;i<N;i++){
    int num;
    cin>>num;
    data[num]++;
    if(data[num]==2){
      cout<<"NO"<<endl;
      return 0;
    }
  }
  cout<<"YES"<<endl;
}

Measured memory_bytes: 12800
def main():
    K, S = open(0).read().split()
    K = int(K)

    ans = ''
    len_S = len(S)
    if len_S <= K:
        ans = S
    else:
        ans = S[:K] + '.' * 3

    print(ans)
    return(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 9164
#include <bits/stdc++.h>
#define PB push_back
#define MP make_pair
#define REP(i,n) for (int i=0;i<(n);i++)
#define ALL(a) (a).begin(),(a).end()
#define INF 1000000001
#define MOD 10000
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
const ull B=100000007;
int dp[100][3][2];
int main(){
      int n,k,a[100],b[100];
      bool f[100][3];
      memset(f,true,sizeof(f));
      cin>>n>>k;
      REP(i,k){
            cin>>a[i]>>b[i];a[i]--;b[i]--;
            REP(j,3)if(j!=b[i])f[a[i]][j]=false;
      }
      REP(i,3)if(f[0][i])dp[0][i][0]++;
      REP(i,n){
            if(i==0)continue;
            REP(j,3){
                  if(!f[i][j])continue;
                  REP(k,6)if(j!=k/2)dp[i][j][0]=(dp[i][j][0]+dp[i-1][k/2][k%2])%MOD;
                  dp[i][j][1]=(dp[i][j][1]+dp[i-1][j][0])%MOD;
            }
      }
      int ans=0;
      REP(i,6)ans=(ans+dp[n-1][i/2][i%2])%MOD;
      cout<<ans%MOD<<endl;
}

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

const ll INF = 1LL << 60;

string N;
int main() {
    cin >> N;
    ll ans = 0;
    rep(i, N.size()) {
        if (N[i] == '2') ans++;
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
var
  s:string;
  i,c,f:longint;
 begin
  read(s);
  c:=maxlongint;
  f:=-maxlongint;
  for i:=length(s) downto 1 do 
  if s[i]='C'then c:=i;
   for i:=1 to length(s) do 
   if s[i]='F'then f:=i;
  if c<f then writeln('Yes')
else writeln('No');
 end.

Measured memory_bytes: 128
#include "bits/stdc++.h"
using namespace std;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
static const int INF = 0x3f3f3f3f; static const long long INFL = 0x3f3f3f3f3f3f3f3fLL;
typedef vector<int> vi; typedef pair<int, int> pii; typedef vector<pair<int, int> > vpii; typedef long long ll;
template<typename T, typename U> static void amin(T &x, U y) { if(y < x) x = y; }
template<typename T, typename U> static void amax(T &x, U y) { if(x < y) x = y; }

int main() {
	int A; int B; int C;
	while(~scanf("%d%d%d", &A, &B, &C)) {
		vi v = { A,B,C };
		sort(v.begin(), v.end());
		v.erase(unique(v.begin(), v.end()), v.end());
		printf("%d\n", (int)v.size());
	}
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<ll,ll>;
using vl = vector<ll>;
using Map = map<ll,ll>;
using T = tuple<ll,ll,ll>;
using vvl = vector<vector<ll>>;
#define all(v) v.begin(), v.end()
#define prt(v) cout<<(v)<<"\n";
#define fi(v) get<0>(v)
#define se(v) get<1>(v)
#define th(v) get<2>(v)
#define endl "\n"
template <typename T> bool chmax(T &a, const T &b){if (a<b){a=b;return 1;}return 0;}
template <typename T> bool chmin(T &a, const T &b){if (a>b){a=b;return 1;}return 0;}
const ll INF=1LL<<60;
const ll MOD=1000000007;


signed main(void){
    cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);
    ll N;
    cin >> N;
    ll x;
    cin >> x;
    vector<ll> A(N,0);
    for(ll i=0;i<N;++i)cin>>A[i];
    ll ans=0;
    if(A[0]>x){
        ans+=A[0]-x;
        A[0]=x;
    }
    for(ll i=1;i<N;++i){
        if(A[i-1]+A[i]<=x)continue;
        ans+=A[i-1]+A[i]-x;
        A[i]=x-A[i-1];
    }
    prt(ans)
    return 0;
}


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

using namespace std;

#define lli long long int
#define REP(i,n) for(int i=0;i<n;i++)
#define DEBUG 1

lli n,a[100100];

lli calc(lli s){
	lli sum=0,res = 0;
	for(lli i=0;i<n;i++,s *= -1){
		sum += a[i];
		if(sum * s > 0)continue;
		res += abs(sum-s);
		sum += s*abs(sum-s);
	}
	return res;
}


int main(){
	cin>>n;
	REP(i,n)cin>>a[i];
	cout<<min(calc(1),calc(-1))<<endl;

	return 0;
}

Measured memory_bytes: 1024
#include<iostream>
#include<algorithm>
using namespace std;
int h, w, x[1000][1000], y[1000][1000];
char T[11] = "0123456789"; char c;
int main() {
	cin >> h >> w;
	for (int i = 2; i < 1000; i++) { y[i][0] = 1000000; y[0][i] = 1000000; }
	for (int i = 1; i <= h; i++) {
		for (int j = 1; j <= w; j++) {
			cin >> c;
			for (int k = 0; k < 10; k++) {
				if (T[k] == c) {
					x[i][j] = k;
				}
			}
		}
	}
	for (int i = 1; i <= h; i++) {
		for (int j = 1; j <= w; j++) {
			y[i][j] = min(y[i - 1][j], y[i][j - 1]) + x[i][j];
		}
	}
	cout << y[h][w] << endl;
	return 0;
}

Measured memory_bytes: 7304
#include<iostream>
#include<algorithm>
using namespace std;
#include<stdio.h>
long long int dp[1001][1001], t[1000+1], s[1000+1];
#define INF 1000000000;
typedef long long llint;
int main()
{
	llint i, j, n, m,g;
	cin >> n >> m;
	for (i = 1; i <= n; i++)
	{
		cin >> s[i];
	}
	for (j = 1; j <= m; j++)
	{
		cin >> t[j];
	}
	for (i = 0; i <= n; i++)
	{
		for (j = 0; j <= m; j++)
		{
			if (i == 0)
				dp[i][j] = 0;
			else
				dp[i][j] = INF;
		}
	}
	for (i = 1; i <= n; i++)
	{
		for (j = 1; j <= m; j++)
		{
			g = s[i] * t[j]+dp[i-1][j-1];
			dp[i][j] = min(dp[i][j-1], g);
		}
	}
	/*for (i = 0; i < n+1; i++)
	{
		for (j = 0; j < m+1; j++)
		{
			cout << dp[i][j] << " ";
		}
		cout << endl;
	}*/
	cout << dp[n][m] << endl;
	return 0;
}

Measured memory_bytes: 9452
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
using Graph = vector<vector<ll>>;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define ALL(a) (a).begin(), (a).end()
#define SORT(c) sort(ALL((c)))
#define debug(x)                 \
    do {                         \
        std::cout << #x << ": "; \
        view(x);                 \
    } while (0)

template <typename T>
void view(T e) {
    std::cout << e << std::endl;
}
template <typename T>
void view(const std::vector<T>& v) {
    for (const auto& e : v) {
        std::cout << e << ", ";
    }
    std::cout << std::endl;
}
template <typename T>
void view(const std::vector<std::vector<T>>& vv) {
    for (const auto& v : vv) {
        view(v);
    }
}

int main() {
    ll K;
    cin >> K;
    vector<ll> a;
    a.push_back(7 % K);
    rep(i, K - 1) {
        ll tmp = a[a.size() - 1];
        a.push_back((tmp * 10 + 7) % K);
    }

    rep(i, a.size()) {
        if (a[i] == 0) {
            cout << (i + 1) << endl;
            return 0;
        }
    }

    puts("-1");
    return 0;
}


Measured memory_bytes: 11656
#include <stdio.h>
#define N 10

int main(void) {
    int h, w;
    scanf("%d %d", &h, &w);

    char a[N][N] = {{0}};
    for (int i = 0; i < h; i++) {
        scanf("%s", a[i]);
    }

    int count = 0;
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            if (a[i][j] == '#') {
                count++;
            }
        }
    }

    if (count == h + w - 1) {
        printf("Possible\n");
    } else {
        printf("Impossible\n");
    }

    return 0;
}

Measured memory_bytes: 128
#pragma warning(disable:4996)
#pragma comment(linker, "/STACK:336777216")
#pragma GCC optimize("Ofast")

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <functional>

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
#define int long long int
typedef complex<long double> cd;
const long double pi=acos(-1);
typedef double db;
typedef long double ldb;
typedef pair <int, int> pii;
typedef pair <db, db> pdd;
typedef vector<int> vi;
typedef vector<vector<int> > matrix;

#define m1 make_pair
#define pb push_back
#define flush fflush(stdout)
#define IOS std::ios::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL);
#define reset(x,v) memset(x,v,sizeof(x))

#define fi first
#define se second
#define endl "\n"
#define debug(x) (cerr << #x << ": " << x << "\n")
#define setbits(x) __builtin_popcount(x)
#define setbitsll(x) __builtin_popcountll(x)
#define all(x) x.begin(),x.end()
#define pii pair<int,int>

inline ll gcd(ll a,ll b){if(a==0) return b;return gcd(b%a,a);}
inline ll power(ll a,ll n,ll m){if(n==0)return 1;ll p=power(a,n/2,m);p=(p%m*p%m)%m;if(n%2) return (p%m*a%m)%m;else return p;}
const ll MOD =998244353;
const ll hell=1000000007;
const int INF = 1e17;
const ll LL_INF = 0x3f3f3f3f3f3f3f3f;
typedef tree<int, null_type, less<int>, rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;
auto seed = chrono::high_resolution_clock::now().time_since_epoch().count();
std::mt19937 rng(seed);

const int N=100005;

void solve()
{
   int n;
   cin>>n;
   int a[n];
   for(int i=0;i<n;i++)
   cin>>a[i];
   int mx=0,ans=0;
   for(int i=0;i<n;i++)
   {
       mx=max(mx,a[i]);
       ans=ans+mx-a[i];
   }
   cout<<ans<<endl;
    
}
int32_t main()
{
    IOS;
    //FILE *fin = freopen("in","r",stdin);
    //FILE *fout = freopen("out","w",stdout);
    int t;
    t=1;
   // cin>>t;
    while(t--)
    {
        solve();
    }
    return 0;
}





Measured memory_bytes: 5196
K, N = map(int, input().split())
A = sorted(map(int, input().split()))
D = [0] * N
for i in range (N-1):
    D[i] = A[i+1] - A[i]
D[N-1] = K - A[N-1] + A[0]

print(K - max(D))

Measured memory_bytes: 25840
#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int A, B, C; 
    cin >> A >> B >> C; 
  if(A % 2 == B % 2 && B % 2 == C % 2){
    int M = max(max(A, B), C); 
    cout << (M * 3 - A - B - C)/ 2 << endl;
  }
  else if(A % 2 == 1 && B % 2 == 0 && C % 2 == 0)
    {int D = A; 
     int E = B+1; 
     int F = C+1; 
     int M = max(max(D, E), F); 
    cout << (M * 3 - D - E - F + 2)/ 2 << endl;
  }
  else if(A % 2 == 0 && B % 2 == 1 && C % 2 == 0)
    {int D = A+1; 
     int E = B; 
     int F = C+1; 
     int M = max(max(D, E), F);
    cout << (M * 3 - D - E - F + 2)/ 2 << endl;
  }
  else if(A % 2 == 0 && B % 2 == 0 && C % 2 == 1)
    {int D = A+1; 
     int E = B+1; 
     int F = C; 
     int M = max(max(D, E), F);
    cout << (M * 3 - D - E - F + 2)/ 2 << endl;
  }
  else if(A % 2 == 1 && B % 2 == 1 && C % 2 == 0)
    {int D = A+1; 
     int E = B+1; 
     int F = C; 
     int M = max(max(D, E), F);
    cout << (M * 3 - D - E - F + 2)/ 2 << endl;
  }
  else if(A % 2 == 1 && B % 2 == 0 && C % 2 == 1)
    {int D = A+1; 
     int E = B; 
     int F = C+1; 
     int M = max(max(D, E), F);
    cout << (M * 3 - D - E - F + 2)/ 2 << endl;
  }
  else if(A % 2 == 0 && B % 2 == 1 && C % 2 == 1)
     {int D = A; 
     int E = B+1; 
     int F = C+1; 
     int M = max(max(D, E), F);
    cout << (M * 3 - D - E - F + 2)/ 2 << endl;
  }
}

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

typedef long long LL;

//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define DECIM8  fixed<<setprecision(8) 
#define SZ(a) int((a).size())
#define SORT(c) sort((c).begin(),(c).end())

//repetition
//------------------------------------------
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI  = acos(-1.0);

//clear memory
#define CLR(a) memset((a), 0 ,sizeof(a))

using namespace std;
int main(void)
{
  bool prime[262144];
  REP(i,262144) prime[i]=true;
  prime[0]=false;prime[1]=false;
  REP(i,sqrt(262144)) if(prime[i]) for(int j=i*i;j<262144;j+=i) prime[j]=false;
  vector<int> primev;
  REP(i,262144) if(prime[i]) primev.PB(i);
  for(;;){
    int n,p;
    cin >> n >> p;
    if(n==-1&&p==-1) return 0;
    vector<int> lp;
    vector<int> mnp;
    int i=0;
    while(primev[i]<=n) ++i;
    REP(j,100) lp.PB(primev[i+j]);
    for(auto x:lp) for(auto y:lp) if(x<=y) mnp.PB(x+y);
    SORT(mnp);
    cout << mnp[p-1] << endl;
  }
}

Measured memory_bytes: 1600
//#define _GLIBCXX_DEBUG
#include "bits/stdc++.h"

using namespace std;

//------------------------------- Type Names -------------------------------//

using i64 = int_fast64_t;

using seika = string;
//{akari : 1D, yukari : 2D, maki : 3D} vector
template <class kizuna>
using akari = vector<kizuna>;
template <class yuzuki>
using yukari = akari<akari<yuzuki>>;
template <class tsurumaki>
using maki = akari<yukari<tsurumaki>>;
//{akane : ascending order, aoi : decending order} priority queue
template <class kotonoha>
using akane = priority_queue<kotonoha, akari<kotonoha>, greater<kotonoha>>;
template <class kotonoha>
using aoi = priority_queue<kotonoha>;

//------------------------------- Libraries ---------------------------------//

//------------------------------- Dubug Functions ---------------------------//

inline void print()
{
    cout << endl;
}
template <typename First, typename... Rest>
void print(const First &first, const Rest &... rest)
{
    cout << first << ' ';
    print(rest...);
}

//------------------------------- Solver ------------------------------------//

void solve()
{
    int n, k, d;
    cin >> n >> k;
    set<int> kasi;
    while (k--)
    {
        cin >> d;
        while (d--)
        {
            int a;
            cin >> a;
            kasi.insert(a);
        }
    }
    cout << n - kasi.size() << endl;
}

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


Measured memory_bytes: 3596
n = int(input())
A = list(map(int,input().split()))

f = 0
i = 0
ans = 1
for i in range(n-1):
  if f==0 and A[i+1]-A[i] > 0:
    f = 1
  elif f==0 and A[i+1]-A[i] < 0:
    f = -1
  elif (f < 0 and A[i+1]-A[i] > 0) or (f > 0 and A[i+1]-A[i] < 0):
    f = 0
    ans += 1
    
print(ans)    

Measured memory_bytes: 14224
// In The Name Of Allah
#include <bits/stdc++.h>
using namespace std;
const long long inf = 1e10;
typedef long long ll;
typedef long double ld;
typedef pair <ll, ll> pii;
const ll mod = 1e9 + 7;

 
void faster()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

const ll M = 500 + 10;
const ll N = 100 * 1000 + 10;

ll a[N], b[N];

int main()	
{
	faster();
	int n;
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> a[i];
	}
	for (int i = 0; i < n; i++)
		cin >> b[i];
	multiset <int> s;
	ll sum = 0, ans = 0;
	for (int i = 0; i < n; i++)
	{
		if(a[i] >= b[i])
			s.insert(a[i] - b[i]);
		else
		{
			ans++;
			sum += a[i] - b[i];
		}
	}
	while(1)
	{
		if(s.size() == 0)
			break;
		if(sum >= 0)
			break;
		sum += *s.rbegin();
		s.erase(s.find(*s.rbegin()));
		ans++;
	}
	if(sum >= 0)
		cout << ans << endl;
	else
		cout << -1 << endl;
}


Measured memory_bytes: 6144
#include<bits/stdc++.h> 
using namespace std;
typedef long long ll;
template<typename T1,typename T2> bool chmin(T1 &a,T2 b){if(a<=b)return 0; a=b; return 1;}
template<typename T1,typename T2> bool chmax(T1 &a,T2 b){if(a>=b)return 0; a=b; return 1;}
int dx[4]={0,1,-1,0};
int dy[4]={1,0,0,-1};
long double eps = 1e-6;
long double pi = acos(-1);


signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(20);

    string s,t;
    cin>>s>>t;
    int n = s.size();
    int ans = 0;
    for(int i=0;i<n;i++){
        if(s[i] != t[i])ans++;
    }
    cout << ans << endl;

}

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

int main(){
  int N;
  cin >> N;
  vector<double> v(N);
  for(int i = 0;i < N;i++)cin >> v[i];

  sort(v.begin(),v.end());

  double ans = v[0];
  for(int i = 1;i < N;i++){
    ans += v[i];
    ans/=2;
  }

  printf("%.14lf\n",ans);
}


Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<vector>
#include<string>
#include<sstream>
#include<iomanip>
#include<utility>
#include<cmath>
#include<set>
#include<list>
#include<queue>
#include<stack>
#include<deque>
#include<map>
#include<set>
#include<cstring>
#include<iterator>
#include<bitset>
#include<assert.h>
using namespace std;
 
struct edge {int /*from,*/to,cost;};
typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,pair<int,int> > PP;
typedef vector<int> VI;
typedef vector<long long int> VL;
typedef vector<edge> VE;
static const int MOD = 1000000007;
//static const int INF = 2147483647;
//static const long long INF = 9223372000000000000;
//static const long long INF = 9223372000000000000/2;
//static const int INF = 1000010000;
//int dx4[4] = {0,1,0,-1}, dy4[4] = {-1,0,1,0};
//int dx5[5] = {-1,0,0,0,1}, dy5[5] = {0,-1,0,1,0};
//int dx8[8] = {-1,0,1,1,1,0,-1,-1}, dy8[8] = {1,1,1,0,-1,-1,-1,0};
//int dx9[9] = {-1,0,1,1,1,0,-1,-1,0}, dy9[9] = {1,1,1,0,-1,-1,-1,0,0};
#define PB push_back
#define MP make_pair
#define FI first
#define SE second
#define NP next_permutation
#define PQ priority_queue
#define UB upper_bound
#define LB lower_bound
#define ALL(x) (x).begin(),(x).end()
#define SZ(a) int((a).size())
#define LEN(a) int((a).length())
#define MAX(a,b,c) max((a),max((b),(c)))
#define MIN(a,b,c) min((a),min((b),(c)))
#define SORT(c) sort((c).begin(),(c).end())
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,x) for(int i=0;i<(int)(x);i++)
#define REP1(i,x) for(int i=1;i<=(int)(x);i++)
#define RREP(i,x) for(int i=((int)(x)-1);i>=0;i--)
#define RREP1(i,x) for(int i=((int)(x));i>0;i--)
//#define int ll

signed main(){
    int n;
    scanf("%d",&n);
    string s;
    cin >> s;
    int p=0,q=0;
    int r=0,l=0;
    REP(i,n){
        if(s[i]==')') p++;
        else q++;
        l = max(l,p-q);
    }
    p = 0,q = 0;
    RREP(i,n){
        if(s[i]=='(') p++;
        else q++;
        r = max(r,p-q);
    }

    string right,left;
    REP(i,l) left += '(';
    REP(i,r) right += ')';

    cout << left << s << right << endl;
    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#define rep(i,n) for(int i=0; i<(int)(n); i++)

int main(){
    int n; scanf("%d",&n);
    int a[101010];
    rep(i,n) scanf("%d",a+i);

    if(n==1){puts("1"); return 0;}
    int up=0,ans=1;
    rep(i,n-1){
        if(up==0){
            if(a[i]<a[i+1]) up=1;
            if(a[i]>a[i+1]) up=-1;
        }else{
            if((up==1&&a[i]>a[i+1])||(up==-1&&a[i]<a[i+1])){
                ans++;
                up=0;
            }
        }
    }
   
    printf("%d\n",ans);
}

Measured memory_bytes: 2116
use {
    proconio::{input, marker::Usize1},
    std::{
        collections::{BTreeSet, BTreeMap},
        ops::Bound::Included,
    },
};

const M: usize = usize::max_value();

fn main() {
    input! {
        h: usize,
        w: usize,
        ab: [(Usize1, Usize1); h],
    }

    let mut es = BTreeSet::new();
    let mut dc = BTreeMap::new();
    for j in 0..w {
        es.insert((j, j));
    }
    dc.insert(0, w);

    for i in 0..h {
        let (a, b) = ab[i];
        let mut rm = vec![];
        let mut add = None;
        let rng = es.range((Included(&(a, 0)), Included(&(b, w))));
        if let Some(&(_, s)) = rng.clone().last() {
            let e = if b == w - 1 { M } else { b + 1 };
            add = Some((e, s));
        }
        for &(e, s) in rng {
            rm.push((e, s));
        }

        for (e, s) in rm {
            es.remove(&(e, s));

            let d = e - s;
            if let Some(v) = dc.get_mut(&d) {
                if *v <= 1 {
                    dc.remove(&d);
                } else {
                    *v -= 1;
                }
            }
        }

        if let Some((e, s)) = add {
            es.insert((e, s));
            *dc.entry(e - s).or_insert(0) += 1;
        }

        let d = if let Some(f) = dc.iter().next() { *f.0 } else { M };
        if d >= w {
            println!("-1");
        } else {
            println!("{}", d + i + 1);
        }
    }
}


Measured memory_bytes: 14980
n = int(input())
A = map(int,input().split())

mod = 1000000007

ans = 0
tmp1, tmp2 = 0, 0

for m in A:
  tmp1 = (tmp1+m) %mod
  tmp2 = (tmp2+m*m%mod)%mod
  
ans = ((tmp1*tmp1)%mod-tmp2)%mod

if ans%2 ==0:
  ans = ans/2
else:
  ans =(ans+mod)/2

print(int(ans))

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

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

using namespace std;
using ll = long long;

constexpr ll atcoder_mod = 1e9+7;

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

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

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	cout<<fixed<<setprecision(10);

	string W=in<string>();
	int N=W.size();
	stack<int> S,T;
	REP(i,N){
		if(W[i]=='T'){
			if(!S.empty()){
				S.pop();
			}
			else{
				T.emplace(0);
			}
		}
		else S.emplace(0);
	}
	
	out(S.size()+T.size());
	return 0;
}

Measured memory_bytes: 1300
//https://atcoder.jp/contests/ddcc2020-qual/tasks/ddcc2020_qual_d
#include <bits/stdc++.h>
#if LOCAL
#include "dump.hpp"
#else
#define dump(...)
#endif
using namespace std;
using ll=long long;
const ll LINF = 0x1fffffffffffffff;
#define FOR(i,a,b) for(ll i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
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;}
int main() {
#if LOCAL&01
  std::ifstream in("./test/sample-1.in");
  //std::ifstream in("./input.txt");
  std::cin.rdbuf(in.rdbuf());
#else
  cin.tie(0);
  ios::sync_with_stdio(false);
#endif
  ll M; cin>>M;
  ll keta=0;
  ll sum=0;
  REP(i,M){
    ll d,c; cin>>d>>c;
    keta += c;
    sum += (d*c);
  }
  ll ans=keta-1+((sum-1)/9);
  cout<<ans<<endl;
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <stack>
#include <queue>
#include <map>
#include <algorithm>
#include <iomanip>
#include <math.h>
#include <string.h>
#include <cstdio>
#include <tuple>
#include <numeric>
using namespace std; using ll = long long; using ld = long double;  using pll = pair<ll, ll>;
using vl = vector<ll>; using vll = vector<vl>; using vpll = vector<pll>;
using vs = vector<string>; using tll = tuple<ll, ll, ll>; using vtll = vector<tll>;
const ld PI = 3.1415926535897932;
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define co(i) cout << i << endl;
#define co2(i,j) cout << i << " " << j << endl;
#define co3(i) cout << i << " ";
#define po(i) cout << i.first << " " << i.second << endl;
void in() {}
void debug_out() { cerr << endl; }
template<typename Head, typename... Tail>
void debug_out(Head h, Tail... t) {
	cerr << " " << h;
	if (sizeof...(t) > 0) cerr << " :";
	debug_out(t...);
}
template <typename T>
ostream& operator<<(ostream& os, vector<T> vec) {
	for (size_t i = 0; i < vec.size(); i++)os << vec[i] << (i + 1 == vec.size() ? "" : " ");
	return os;
}
ll ctoi(char c) {
	switch (c) {
	case '0': return 0; case '1': return 1; case '2': return 2;
	case '3': return 3; case '4': return 4; case '5': return 5;
	case '6': return 6; case '7': return 7; case '8': return 8;
	case '9': return 9;  default: return 0;
	}
}
bool pairCompare(const pll firstElof, pll secondElof)
{
	return firstElof.first > secondElof.first;
}
//**Snippetリスト**//
//rep, vin, all, iteLoop, bitSearch, bitList, nod, digitDP, treeDP//
//gcdlcm, isPrime, eratos, primeFactorize, Npow, combination, divisor, modinv, doubling//
//dfs, bfs, dijkstra, WarshallFloyd, BellmanFord, UnionFind, Kruskal, RMQ, LCA//
ll i, j, k, l; ll N, M, K, H, W, L, X, Y, Z, R, Q;
ll MOD = 1000000007, INF = 1LL << 60, ans = 0, z = 0, o = 1;
vl flag, D; vll path;
//***********//
vl bitList(ll n, ll k, ll f) {
	vl bitList(k);
	for (ll i = 0; i < k; i++) {
		bitList[i] = f % n;
		f /= n;
	}
	return bitList;
}
int main() {
	cin >> H >> W >> K;
	vs C(H);
	for (i = 0; i < H; i++) {
		cin >> C[i];
	}
	for (i = 0; i < pow(2,H); i++) {
		for (j = 0; j < pow(2,W); j++) {
			vl P = bitList(2, H, i);
			vl Q = bitList(2, W, j);
			ll pre = 0;
			for (k = 0; k < H; k++) {
				for (l = 0; l < W; l++) {
					if (!P[k] && !Q[l] && C[k][l] == '#') pre++;
				}
			}
			if (pre == K) ans++;
		}
	}
	co(ans);
}

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

int main() {
    int a, b, c;
    cin >> a >> b >> c;
    if ((a < c && c < b) || (b < c && c < a)) {
        puts("Yes");
    } else {
        puts("No");
    }
}


Measured memory_bytes: 3540
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include <iomanip>
#include <math.h>
#include <string.h>
#include <cstdio>
#include <tuple>
#include <numeric>
#define FOR(i,a,b) for(ll i=a;i<b;i++)
#define CST(x) cout<<fixed<<setprecision(x)//小数点以下の桁数指定
#define ct(a) cout<<a<<endl
static const double pi = 3.141592653589793;
using namespace std;
typedef long long ll;
const ll MOD = 1e9 + 7;
const ll INF = 1e9+7;
const ll mod= 1e9 + 7;

ll mod_pow(ll x, ll n) {
	if (n == 0) return 1;
	ll res = mod_pow(x*x % mod, n / 2);
	if (n & 1) res = res * x % mod;
	return res;
}

ll comb(ll n, ll x) {
	ll ret = 1, k = 1;
	FOR(i, 0, x)ret = (ret * (n - i)) % mod;
	FOR(i, 1, x + 1)k = (k*i + mod) % mod;
	k = mod_pow(k, mod - 2);
	ret = (ret*k + mod) % mod;
	return ret;
}

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

	ll N, K; cin >> N >> K;
	K--;
	ll ans = 0;

	vector<ll> A(N);
	FOR(i, 0, N)cin >> A[i];
	sort(A.begin(), A.end());
	
	vector<ll> C(N+1,0);
	C[K] = 1;
	FOR(i, K+1, N) {
		C[i] = (((C[i-1] * i)%mod) *mod_pow(i  - K, mod - 2))%mod;
		
	}
	


	if (K == 0)cout << 0 << endl;
	else {
		FOR(i,0,N)if(i>=K)ans = (ans + (A[i] * C[i])%mod)%mod;
		FOR(i, 0, N)if (N - i - 1 >= K)ans = (ans - (A[i] * C[N - i - 1])%mod) % mod;
		cout << (ans+2*mod)%mod << endl;
	}
	

	return 0;
}

Measured memory_bytes: 1792
n=int(input())

s = [0] * n
p = [0] * n
for i in range(n):
    s[i], p[i] = map(str,input().split())
    
P = [int(s) for s in p]
L=[]

for i in range(n):
    count=1
    for j in range(n):
        if i==j:
            continue
        if s[i]>s[j]:
            count=count+1
        if s[i]<s[j]:
            continue
        if s[i]==s[j]:
            if P[i]<P[j]:
                count=count+1
            else:
                continue
    L.append(count)

for i in range(n):
    print(L.index(i+1)+1)

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

#define MOD 1000000007ll
#define pb     push_back
#define mp     make_pair
#define MAX 100005
#define all(v) v.begin() , v.end()
#define allr(v) v.rbegin(), v.rend()

string s;
bool done[35];

int main(int argc, char const *argv[])
{
  cin>>s;
  int siz = s.size();

  for(int i = 0 ; i < 30 ; i++){
  	done[i] = false;
  }

  for(int i = 0 ; i < siz ; i++){
  	int x = s[i] - 'a';

  	if(done[x]){
  		cout << "no";
  		return 0;
  	}
  	else
  		done[x] = true;
  }
  cout << "yes";

  return 0;
}  

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <cmath>
using namespace std;

double calcDis(double x1, double y1, double z1, double x2, double y2, double z2){
  return sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2) + (z1-z2)*(z1-z2));
}

int main(){
  int n;
  while(cin >> n, n){
    double x[100], y[100], z[100], r[100];
    for(int i = 0; i < n; i++) cin >> x[i] >> y[i] >> z[i] >> r[i];
    
    set<int> cell;
    double ans = 0;
    
    multimap<double, int> corridor;
    corridor.insert(make_pair(0.0, 0));
    
    while(cell.size() < n) {
      double len = corridor.begin()->first;
      int c = corridor.begin()->second;
      corridor.erase(corridor.begin());
      
      if(!cell.insert(c).second) continue;
      ans += len;
      
      for(int i = 0; i < n; i++){
        if(cell.find(i) == cell.end()){
          corridor.insert(make_pair(max(0.0, calcDis(x[i], y[i], z[i], x[c], y[c], z[c]) - r[i] - r[c]), i));
        }
      }
    }
    printf("%.3f\n", ans);
  }
  return 0;
}

Measured memory_bytes: 1140
// [[ABC134C] Exception Handling] https://www.luogu.com.cn/problem/AT4843
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
int dp[100005];
int main() {
  int n, k;
  cin >> n >> k;

  int h[n + 3];
  for (int i = 1; i <= n; i++) {
    scanf("%d", &h[i]);
    dp[i] = 0x3f3f3f3f;
  }

  dp[1] = 0;
  for (int i = 2; i <= n; i++) 
    for (int j = i - 1; j >= max(i - k, 1); j--) 
      dp[i] = min(dp[i], dp[j] + abs(h[i] - h[j]));
    
  printf("%d\n", dp[n]);
  return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define ll long long
#define elif else if
#define endl "\n"
#define _  <<" "<<
#define eb(x) emplace_back(x)
#define maxelem(v) *max_element(v.begin(),v.end())
#define minelem(v) *min_element(v.begin(),v.end())
#define FOR(a,b) for(int i=int(a);i<int(b);++i)

using namespace std;

const int mod = 1e9+7;

void izlaz(string br)
{
  if(!br.size())
    exit(EXIT_SUCCESS);
  cout<<br;
  exit(EXIT_SUCCESS);

}

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

  int ans,x,y;
  bool f=0;
  ans=0;
  int test;
  cin>>test;
  while(test--)
  {
      cin>>x>>y;
      if(x==y)
      {
          ++ans;
          if(ans>=3)
             f=1;
      }
      else
        ans=0;
  }
  if(f)
    cout<<"Yes";
  else
    cout<<"No";



 return 0;
}


Measured memory_bytes: 3648
#include <bits/stdc++.h>
using namespace std;
using Int = long long int;
template<typename T> void swap(T *t1, T *t2){ T* tmp=t1; t1=t2; t2=tmp;}
Int tmp = 0;
double tmpd = 0.0;


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

    Int a, b;
    cin >> a >> b;

    if(a >= 13){
        cout << b << endl;
    }else if(a <= 5){
        cout << 0 << endl;
    }else{
        cout << b/2 << endl;
    }

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cmath>
using namespace std;

using ll = long long;
using P = pair<int, int>;

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

// 4近傍、8近傍
int dx[] = {1, 0, -1, 0, 1, -1, -1, 1};
int dy[] = {0, 1, 0, -1, 1, 1, -1, -1};

int main() {
  // 入力
  int N;
  cin >> N;

  ll L[N+1];
  L[0] = 2; L[1] = 1;
  for (int i = 2; i <= N; i++) {
    L[i] = L[i-1] + L[i-2];
  }

  // 解答
  cout << L[N] << endl;

  return 0;
}


Measured memory_bytes: 256
using System;
using static System.Console;

class Program
{
    static void Main(string[] args)
    {
        int N = int.Parse(ReadLine());
        string[] input = ReadLine().Split(' ');
        string S = input[0];
        string T = input[1];
        string ans = "";
        for(int i = 0; i < N; i++)
        {
            ans += S[i];
            ans += T[i];
        }
        WriteLine(ans);
    }
}

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

using namespace std;

int main() {
	long long a, b, c;

	cin >> a >> b >> c;

	c -= a + b;

	if(c < 0) {
		cout << "No" << '\n';
	} else if(c * c > 4LL * a * b) {
		cout << "Yes" << '\n';
	} else {
		cout << "No" << '\n';
	}
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int main(){
	ll N,A,B,C,D;	
	cin >> N >> A >> B >> C >> D;
	ll X = B-A;
	ll m1 = C*(N-1)-X;	
	ll m2 =D*(N-1)-X;	
	for(int i=0;i<=N-1;i++)
	if(m2 >=i*(C+D) && m1<=i*(C+D)){
		cout << "YES";
		return 0;
	}	
	cout << "NO";
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
using namespace std;
long long a,b;
char x; 
int main()
{
    scanf("%d %c %d",&a,&x,&b);
    if(x=='+')
    {
        printf("%d",a+b);
    }
    else if(x=='-')
    {
        printf("%d",a-b);
    }
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define Rep(i, n) for(int i=0;i<n;i++)
#define MAX_N (2<<17)
using namespace std;

int n, dat[2*MAX_N-1];

void init(int n_){
  n = 1;
  while(n < n_) n *= 2;
  Rep(i, 2*n-1) dat[i] = INT_MAX;
}

void update(int k, int a){
  int r = k+n-1;
  dat[r] = a;
  while(r > 0){
    r = (r-1)/2;
    dat[r] = min(dat[r*2+1], dat[r*2+2]);
  }
}

int rec(int a, int b, int k, int l, int r){
  if(r <= a || b <= l) return INT_MAX;
  
  if(a <= l && r <= b) return dat[k];
  else{
    int vl = rec(a, b, k*2+1, l, (l+r)/2);
    int vr = rec(a, b, k*2+2, (l+r)/2, r);
    return min(vl, vr);
  }
}

int query(int a, int b){
  return rec(a, b+1, 0, 0, n);
}

int main(){
  int q;
  cin >> n >> q;
  init(n);
  Rep(i, q){
    int com, x, y;
    cin >> com >> x >> y;
    if(com == 0) update(x, y);
    else cout << query(x, y) << endl;
  }
}

Measured memory_bytes: 2188
#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<vector>

using namespace std;

int a[100001];
int w[100001];
int abs(int a)
{
	if (a < 0)
		return -a;
	else
		return a;

}
int main()
{
	int n;
	cin >> n;
	w[0] = 0;
	a[0] = 0;
	for (int i = 1; i <= n; i++)
	{
		cin >> a[i];
		w[i] = w[i - 1] + abs(a[i] - a[i - 1]);
	}
	int all = w[n] + abs(a[n]);
	for (int i = 1; i <= n; i++)
	{
		if (i == n)
		{
			cout << w[n - 1] + abs(a[n - 1]);
			break;
		}
		int ans = all - abs(a[i] - a[i - 1]) - abs(a[i + 1] - a[i]) + abs(a[i + 1] - a[i - 1]);
		cout << ans << "\n";
	}
	return 0;
}

Measured memory_bytes: 2048
# -*- coding: utf-8 -*-
 
import math
import itertools
import sys
import copy
 
# 入力
#A, B, C, D = map(int, input().split())
#L = list(map(int, input().split()))
#S = list(str(input()))
N = int(input())
S = str(input())
K = int(input())

c = S[K-1]
ans = ""
for i in range(N) :
  if S[i] == c :
    ans += c
  else :
    ans += "*"
    
print (ans)





Measured memory_bytes: 3436
//raja1999
#include <bits/stdc++.h>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <utility>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <iomanip> 
//setbase - cout << setbase (16)a; cout << 100 << endl; Prints 64
//setfill -   cout << setfill ('x') << setw (5); cout << 77 <<endl;prints xxx77
//setprecision - cout << setprecision (14) << f << endl; Prints x.xxxx
//cout.precision(x)  cout<<fixed<<val;  // prints x digits after decimal in val

using namespace std;
#define f(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) f(i,0,n)
#define fd(i,a,b) for(i=a;i>=b;i--)
#define pb push_back
#define mp make_pair
#define vi vector< int >
#define vl vector< ll >
#define ss second
#define ff first
#define ll long long
#define pii pair< int,int >
#define pll pair< ll,ll >
#define sz(a) a.size()
#define inf (1000*1000*1000+5)
#define all(a) a.begin(),a.end()
#define tri pair<int,pii>
#define vii vector<pii>
#define vll vector<pll>
#define viii vector<tri>
#define mod (1000*1000*1000+7)
#define pqueue priority_queue< int >
#define pdqueue priority_queue< int,vi ,greater< int > >

//std::ios::sync_with_stdio(false);
#define EPS 1e-12
int a[100005];
vi v;
int main(){
	std::ios::sync_with_stdio(false);
	int n,i,id;
	double minn=inf;
	double val;
	cin>>n;
	rep(i,n){
		cin>>a[i];
		v.pb(a[i]);
	}	
	sort(all(v));
	val=(double)v[n-1]/2.0;
	rep(i,n-1){
		if(fabs(v[i]-val)-minn<EPS){
			minn=fabs(v[i]-val);
			id=i;
		}
	}
	cout<<v[n-1]<<" "<<v[id]<<endl;
} 
	

Measured memory_bytes: 1148
#include "bits/stdc++.h"
#define DEBUG(x) cout<<#x<<": "<<x<<endl;
#define DEBUG_VEC(v) cout<<#v<<":";for(int i=0;i<v.size();i++) cout<<" "<<v[i]; cout<<endl
using namespace std;
#define vi vector<int>
#define vl vector<ll>
#define vii vector< vector<int> >
#define vll vector< vector<ll> >
#define vs vector<string>
#define pii pair<int,int>
#define pis pair<int,string>
#define psi pair<string,int>
#define pll pair<ll,ll>
#define rep(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
#define MOD 1000000007
#define mod 1000000009
#define pi 3.14159265358979323846
#define Sp(p) cout<<setprecision(15)<< fixed<<p<<endl;
#define pb push_back
template<class T> void print(const T& x){cout << x << endl;}
int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 };
int dx2[8] = { 1,1,0,-1,-1,-1,0,1 }, dy2[8] = { 0,1,1,1,0,-1,-1,-1 };
typedef long long ll;
const int inf = 1000000001;
const ll INF = 1e18 * 4;

int ma = 80*80*2+10;

int dp[81][81][80*80*2+10];

int main(){
    int H, W; cin >> H >> W;
    int N = 81;
    vii A(H, vi(W));
    vii B(H, vi(W));
    rep(i, 0, H){
        rep(j, 0, W){
            cin >> A[i][j];
        }
    }
    rep(i, 0, H){
        rep(j, 0, W){
            cin >> B[i][j];
        }
    }
    rep(i, 0, N){
        rep(j, 0, N){
            rep(k, 0, ma){
                dp[i][j][k] = 0;
            }
        }
    }
    int ofs = 80*80+5;
    // score: r - b
    dp[0][0][ofs + A[0][0]-B[0][0]]++;
    dp[0][0][ofs + B[0][0]-A[0][0]]++;

    rep(i, 0, H+2){
        rep(j, 0, W+2){
            rep(s, 0, ma){
                if(i+1 < H && j < W && dp[i][j][s] != 0){
                    int s1 = s+A[i+1][j]-B[i+1][j];
                    if(0 <= s1) dp[i+1][j][s1] = dp[i][j][s];

                    int s2 = s+B[i+1][j]-A[i+1][j];
                    if(0 <= s2) dp[i+1][j][s2] = dp[i][j][s];
                }

                if(j+1 < W && i < H && dp[i][j][s] != 0){
                    int s3 = s+A[i][j+1]-B[i][j+1];
                    if(0 <= s3) dp[i][j+1][s3] = dp[i][j][s];

                    int s4 = s+B[i][j+1]-A[i][j+1];
                    if(0 <= s4) dp[i][j+1][s4] = dp[i][j][s];
                }
            }
        } 
    }
    int ans = inf;
    int cnt = 0;
    rep(s, 0, ma){
        if(dp[H-1][W-1][s] > 0){
            cnt += dp[H-1][W-1][s];
            ans = min(ans, abs(s-ofs));
        }
    }
    cout << ans << endl;

    return 0;
}




Measured memory_bytes: 331964
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define ll long long
#define M 1000000007
#define sz(a) (ll)a.size()
#define pll pair<ll,ll>
#define rep(i,a,b) for(ll i=(ll)a;i<(ll)b;i++)
#define sep(i,a,b) for(ll i=(ll)a;i>=(ll)b;i--)
#define mll map<ll,ll>
#define vl vector<ll>
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define all(a) a.begin(),a.end()
#define F first
#define S second
using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
ll n,k,a[200005],f[200005];
bool check(ll m)
{
    ll ans=0;
    rep(i,0,n)
        ans+=max(0LL,a[i]-m/f[i]);
    return ans<=k;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>k;
    rep(i,0,n)
        cin>>a[i];
    rep(i,0,n)
        cin>>f[i];
    sort(a,a+n);
    sort(f,f+n,greater<ll>());
    ll l=0,h=1e12+5;
    while(h-l>1)
    {
        ll m=(l+h)/2;
        if(check(m))
            h=m;
        else
            l=m;
    }
    if(check(l))
        cout<<l;
    else
        cout<<h;
}


Measured memory_bytes: 3328
program main 
 implicit none
 integer N,K,ans,i
 integer,allocatable::h(:)
 
 read(*,*) N,K
 allocate(h(N))
 read(*,*) h
 
 ans = 0
 do i=1,N
  if(h(i) >= K) then
   ans = ans+1
  end if
 end do
 
 write(*,*) ans
end program main

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,n) for(int i=0; i<(int)n; i++)
#define rep1(i,n) for(int i=1; i<(int)n; i++)
#define repa(i,a,n) for(int i=(a); i<(int)(n); i++)
#define all(vec) vec.begin(),vec.end()
#define COUT(x) cout<<(x)<<endl
#define YES(x) cout<<(x?"YES":"NO")<<endl
#define Yes(x) cout<<(x?"Yes":"No")<<endl
using vi = vector<int>;
using vs = vector<string>;
using vvi = vector<vi>;
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 int 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 / gcd(a, b)*b;}
//cout << fixed << setprecision(15);
int N, M, K, H, W, L, R, X;
string S, T;

signed main(){
  cin >> N >> M;
  vi A(N);
  rep(i,N) cin >> A[i];
  vvi B(M,vi(2));
  rep(i,M) cin >> B[i][1] >> B[i][0];
  sort(all(A));
  sort(all(B));
  reverse(all(B));
  
  int a = 0;
  rep(i,M){
    while (B[i][1]>0){
      if(B[i][0] > A[a]){
        A[a] = B[i][0];
        B[i][1]--;
        a++;
      }else{
        break;
      }
    }
  }
  int ans = 0;
  rep(i,N) ans += A[i];
  
  COUT(ans);
  return 0;

}

Measured memory_bytes: 9604
N=int(input())

if N==100000:
  print(90000+900+9)
elif N>=10000:
  print(N-10000+1+900+9)
elif N>=1000:
  print(909)
elif N>=100:
  print(N-100+1+9)
elif N>=10:
  print(9)
else:
  print(N)

Measured memory_bytes: 3064
# import bisect
# from collections import Counter, deque
# import copy
# from heapq import heappush, heappop, heapify
# from fractions import gcd
# import itertools
from operator import attrgetter, itemgetter
# import math

import sys

# import numpy as np

ipti = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    n = int(input())
    ab = [[0] * 2 for _ in range(n)]
    for i in range(n):
        ab[i] = list(map(int,ipti().split()))

    ab.sort(key=itemgetter(1))
    time = 0

    for i in range(n):
        time += ab[i][0]
        if time > ab[i][1]:
            print('No')
            break
    else:
        print('Yes')


if __name__ == '__main__':
    main()

Measured memory_bytes: 88940