akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
 
bool p[100005],a[100005];
int b[100005];
int main()
{
	p[1]=true;
	for(int i=2;i<=sqrt(100000);i++)
	{
		if(p[i]==false)
		{
			for(int j=i*i;j<=100000;j+=i)
				p[j]=true;
		}
	}
	for(int i=2;i<=100000;i++)
	{
		if(i!=2&&p[i]==false&&p[(i+1)/2]==false)
				a[i]=true;
	}
	for(int i=2;i<=100000;i++)
		b[i]=b[i-1]+a[i];
	int q,l,r;
	cin>>q;
	for(int i=1;i<=q;i++)
	{
		cin>>l>>r;
		cout<<b[r]-b[l-1]<<endl;
	}
	return 0;
}

Measured memory_bytes: 1152
#include <bits/stdc++.h>
#define X first
#define Y second
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define ini(x, y) memset(x, y, sizeof(x))
#define endl '\n'
#define fastio cin.sync_with_stdio(false); cin.tie(nullptr)
using namespace std;

using ll = long long;
using pii = pair<int, int>;
const int dx[] = { -1, 0, 1, 0, -1, 1, 1, -1 };
const int dy[] = { 0, 1, 0, -1, 1, 1, -1, -1 };

ll gcd(ll a, ll b) {
	return b ? gcd(b, a % b) : a;
}
bool is_prime(ll n) {
	if (n < 2) return false;
	if (n < 4) return true;
	for (ll i = 2; i < n; ++i) {
		if (i * i > n) return true;
		if (n % i == 0) return false;
	}
}
int main() {
	fastio;
	ll A, B;
	cin >> A >> B;

	ll g = gcd(A, B);
	int ans = 0;
	for (ll i = 1; i * i <= g; ++i) if (g % i == 0) {
		ans += is_prime(i);
		if (i * i != g) ans += is_prime(g / i);
	}

	cout << ans + 1;

	return 0;
}

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

int main() {

  int a, b, i;
  cin >> a >> b;
  
  int x1, x2, y1, y2, k, count = 0;
  for(k=a; k<=b; k++){
    i = k;
    x1 = i % 10; i /= 10;
    y1 = i % 10; i /= 100;
    y2 = i % 10; i /= 10;
    x2 = i % 10;
    if(x1 == x2 && y1 == y2) count++;
  }
  cout << count << endl;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0, i##_len = (n); i < i##_len; ++i)
#define rep2(i, x, n) for(int i = x, i##_len = (n); i < i##_len; ++i)
#define all(n) begin(n), end(n)
using ll = long long;
using P = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vs = vector<string>;
using vc = vector<char>;
using vb = vector<bool>;
using vd = vector<double>;
vi dir = {-1, 0, 1, 0, -1, -1, 1, 1, -1};

int main() {
  ll n;
  cin >> n;
  multiset<ll> st;
  rep(i, n) {
    ll a;
    cin >> a;
    a *= -1;
    auto it = st.upper_bound(a);
    if(it != st.end()) st.erase(it);
    st.insert(a);
  }
  cout << st.size() << endl;
}

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

inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}

template<class T> inline T sqr(T x) {return x*x;}

typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> P;
typedef long long ll;

#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())
#define REVERSE(c) reverse((c).begin(),(c).end())

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

const double EPS = 1e-10;
const double PI  = acos(-1.0);
const int INT_INF = 2147483647;
const long long LL_INF = 1LL<<60;
const long long MOD = 1000000007;

#define CLR(a) memset((a), 0 ,sizeof(a))

#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

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

int main(void){
    int N,M,Q; cin >> N >> M >> Q;
    vector<pair<int,int>> range(M);
    VI terminal(N,0);
    REP(i,M){
        int l,r; cin >> l >> r;
        l--; r--;
        range[i].first = l; range[i].second = r;
        terminal[r]++;
    }
    SORT(range); REVERSE(range);
    int ans[N][N]; REP(i,N)REP(j,N) ans[i][j] = 0;
    
    REP(i,N){
        while(range.size() && range.back().first < i){
            terminal[range.back().second]--;
            range.pop_back();
        }
        int n = 0;
        FOR(j,i,N){
            n += terminal[j];
            ans[i][j] = n;
        }
    }

    REP(i,Q){
        int p,q; cin >> p >> q;
        p--; q--;
        cout << ans[p][q] << endl;
    }
    return 0;
}

Measured memory_bytes: 3456
#include <iostream>
#include <stdio.h>
#include <algorithm>
using namespace std;

int A[1000000], n;

int main()
{
    cin >> n;
    for (int i = 0; i < n; i++) {
        scanf("%d", &A[i]);
    }

    int q, k, sum = 0;
    cin >> q;
    for (int i = 0; i < q; i++) {
        scanf("%d", &k);
        if (*lower_bound(A, A + n, k) == k) sum++;
    }

    cout << sum << endl;

    return 0;
}



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

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

class Mint{
    public:
    int v;
    const long long MOD = 1000000007;
    Mint():v(0){}
    Mint(signed v):v(v){}
    Mint(long long t){v=t%MOD; if(v<0)v+=MOD;}

    Mint pow(long long k){
        Mint res(1), tmp(v);
        while(k){
            if(k&1)res*=tmp;
            tmp*=tmp;
            k>>=1;
        }
        return res;
    }
    Mint inv(){return pow(MOD-2);}

    Mint& operator+=(Mint a){v+=a.v; if(v>=MOD)v-=MOD; return *this;}
    Mint& operator-=(Mint a){v+=MOD-a.v; if(v>=MOD)v-=MOD; return *this;}
    Mint& operator*=(Mint a){v=1LL*v*a.v%MOD; return *this;}
    Mint& operator/=(Mint a){return (*this)*=a.inv();}

    Mint operator+(Mint a) const{return Mint(v)+=a;};
    Mint operator-(Mint a) const{return Mint(v)-=a;};
    Mint operator*(Mint a) const{return Mint(v)*=a;};
    Mint operator/(Mint a) const{return Mint(v)/=a;};

    Mint operator-(){return v ? MOD-v : v;}
    bool operator==(Mint a)const{return v==a.v;}
    bool operator!=(Mint a)const{return v!=a.v;}

    Mint operator=(Mint a) {v=a.v;return a;}

    friend ostream& operator<<(ostream& os, const Mint& mint){
        os << mint.v;
        return os;
    }
};

class cmbs{
    public:
    vector<Mint> fact, finv, inv;
    cmbs(){
        fact.clear(); finv.clear(); inv.clear();
    }
    void init(int n){
        if(n+1 <= (signed)fact.size())return;
        fact.assign(n+1,1);
        finv.assign(n+1,1);
        inv.assign(n+1,1);

        for(int i=1; i<=n; i++) fact[i] = fact[i-1]*Mint(i);
        finv[n] = Mint(1)/fact[n];
        for(int i=n; i>=1;i--) finv[i-1] = finv[i]*Mint(i);
        for(int i=1; i<=n; i++) inv[i] = finv[i]*fact[i-1];
    }
    Mint comb(long long n, int k){
        if(n<k||k<0)return Mint(0);
        Mint res(1);
        for(int i=0; i<k; i++){
            res *= Mint(n-i);
            res /= Mint(i+1);
        }
        return res;
    }
    Mint C(int n,int k){
        if(n<k||k<0)return Mint(0);
        init(n);
        return fact[n]*finv[n-k]*finv[k];
    }
    Mint P(int n, int k){
        if(n<k || k<0)return Mint(0);
        init(n);
        return fact[n]*finv[n-k];
    }
    Mint H(int n, int k){
        if(n<0||k<0)return Mint(0);
        if(!n&&!k)return Mint(1);
        init(n+k-1);
        return C(n+k-1,k);
    }
};

int main(){
    ll n,k;
    cin>>n>>k;
    cmbs cmb;
    cout<<cmb.C(n-1,k-1)<<endl;
    return 0;
}


Measured memory_bytes: 3156
#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <cstring>
#include <queue>
#include <stack>
#include <functional>
#include <set>
#include <map>
#include <deque>
#define WMAX 10000
#define HMAX 10000

//コメントアウトするとdebug()を実行しない
#define DEBUG

using namespace std;
template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}

typedef long long ll;

ll A,B,C,N,W,H,ans,dp[HMAX][WMAX];
string S;
static const ll dx[8] = {0,1,1,1,0,-1,-1,-1},
					dy[8] = {1,1,0,-1,-1,-1,0,1};

void solve(){

}

void debug(){

}

void answer(){
	cout << ans << "\n";
}

int main(){
	cin >> A >> B >> C;
	if(B == 0){
		ans = 1;
	}else if(A == 0){
		ans = B/C+1;
	}else{
		ans = B/C - (A-1)/C;
	}
	cout << ans << "\n";
	return 0;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
#define REP(i, n) for(ll i = 0;i < n;i++)
#define ll long long
#define MOD 1000000007
using vi = vector<ll>; // intの1次元の型に vi という別名をつける
using vvi = vector<vi>; // intの2次元の型に vvi という別名をつける

ll n,k,x,y;

int main(){
  ll ans=0;
  cin>>n;
  n%=26;
  string s;cin>>s;
  ll l=s.length();
  REP(i,l)
  {
    s[i]=(s[i]-65+n)%26+65;
  }
  cout<<s<<endl;
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <math.h>
#include <map>
#include <time.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;

#define pb push_back
#define rep(i, a, n) for(int i = (a); i < (n); i++)
#define dep(i, a, n) for(int i = (a); i >= (n); i--)
#define mod (ll)(1e9+7)
#define int ll

__attribute__((constructor))
void initial() {
  cin.tie(0);
  ios::sync_with_stdio(false);
}

signed main() {


  int x;
  cin>>x;
  if(3==x||5==x||7==x)cout<<"YES"<<endl;
  else cout<<"NO"<<endl;
}


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

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

  int n,m;
  while(true) {
    if(cin.eof()) break;
    cin >> n;
    if(n == 0) break;

    map<char,char> tables;
    char bf,en;
    for(int i=0;i<n;i++) {
      cin >> bf >> en;
      tables[bf] = en;
    }
    cin >> m;
    char c;
    for(int i=0;i<m;i++) {
      cin >> c;
      if(tables.count(c)) {
        c = tables[c];
      }
      cout << c;
    }
    tables.clear();
    cout << "\n";
  } // end while
}

Measured memory_bytes: 1184
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
using namespace std;
int main()
{
  int h, w;
  cin >> h >> w;
  char c = 'A';
  rep(i, h)
  {
    rep(j, w)
    {
      string s;
      cin >> s;
      if (s == "snuke")
        cout << (char)('A' + j) << (i + 1) << endl;
    }
  }
  return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<cstddef>
#include<queue>
#include<math.h>
#include<iomanip>
using namespace std;

const int INF = 1001001001;

int main()
{
    int N, X, Y;
    cin >> N >> X >> Y;
    --X; --Y;
    vector<int> ans(N);
    for(int sv = 0; sv < N; sv++){ // sv:start-vertex
        vector<int> dist(N,INF);
        queue<int> q;
        auto push = [&](int v, int d){
            if(dist.at(v) != INF) return;
            dist.at(v) = d;
            q.push(v);
        };
        push(sv, 0);
        while(!q.empty()){
            int v = q.front(); q.pop();
            int d = dist.at(v);
            if(v - 1 >= 0) push(v - 1, d + 1);
            if(v + 1 < N) push(v + 1, d + 1);
            if(v == X) push(Y, d + 1);
            if(v == Y) push(X, d + 1);
        }
        for(int i = 0; i < N; ++i){
            ans.at(dist.at(i))++;
        }
    }
    for(int i = 0; i < N; ++i){
        ans.at(i) /= 2;
    }
    for(int i = 1; i <= N - 1; ++i){
        cout << ans.at(i) << endl;
    }
    return 0;
}

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

ll a, b;

ll f(ll c) {
    ll res = b/c - (a-1)/c;
    return res;
}

int main() {
    ll c, d;
    cin >> a >> b >> c >> d;
    ll cd = c*d/__gcd(c,d);
    ll dis = f(c)+f(d)-f(cd);
    ll ans = b-a+1-dis;
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3636
// B.

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <vector>

using namespace std;

typedef long long LL;

int main(int argc, char *argv[])
{
	int k;
	cin >> k;
	vector<LL> a(k);
	for (int i = 0; i < k; ++i) {
		cin >> a[i];
	}
	reverse(a.begin(), a.end());
	LL l = -1, r = -1;
	if (a[0] == 2) {
		l = 2, r = 3;
		for (int i = 1; i < (int)a.size(); ++i) {
			LL x = a[i];
			LL p = ((l + x - 1) / x) * x;
			LL q = (r / x) * x + x - 1;
			if (p > q) {
				l = -1;
				break;
			}
			l = p;
			r = q;
		}
	}
	if (l < 0) {
		cout << l << endl;
	} else {
		cout << l << " " << r << endl;
	}
	return 0;
}


Measured memory_bytes: 1024
#include <stdio.h>

int main(void)
{
    int r,g,b;
    int n=0;
    
    scanf("%d %d %d",&r,&g,&b);
    
    n = 100*r + 10*g + b;
    n = n%4;
    
    if(n==0)
    {
        printf("YES\n");
    }
    else
    {
        printf("NO\n");
    }
    
    return 0;
}



Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(int)n;i++)
using Graph = vector<vector<int> >;
using GraphC = vector<vector<char> >;
const int INF = 1000000000;
typedef pair<int, int> P;
const int MAX_N = 1000000000;
typedef int64_t ll;
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; }




int main() {
	int N;
	cin >> N;
	vector<int> T(N);
	int tmp = 0;
	rep(i, N) {
		cin >> T.at(i);
		tmp += T.at(i);
	}
	int M;
	cin >> M;
	
	rep(i, M) {
		int num, a,add;
		cin >> num >> a; num--;
		add = a - T.at(num);
		cout << tmp + add << endl;
	}
}

Measured memory_bytes: 3632
import java.util.*;
import java.io.*;
import java.awt.geom.*;
import java.math.*;

public class Main {

	static final Scanner in = new Scanner(System.in);
	static final PrintWriter out = new PrintWriter(System.out,false);
	static boolean debug = false;

	static boolean solve() {
		int h = in.nextInt();
		int w = in.nextInt();
		if (h + w == 0) return false;

		int d = h*h + w*w;
		int min = 1<<30;
		int ansh = 1<<30, answ = 1<<30;

		for (int i=1; i<200; i++) {
			for (int j=i+1; j<200; j++) {
				if (d < i*i + j*j || (d == i*i + j*j && h < i))
				if (min > i*i + j*j || (min == i*i + j*j && ansh > i)) {
					min = i*i + j*j;
					ansh = i;
					answ = j;
				}
			}
		}

		out.println(ansh+" "+answ);

		return true;
	}

	public static void main(String[] args) {
		debug = args.length > 0;
		long start = System.nanoTime();

		while(solve());
		out.flush();

		long end = System.nanoTime();
		dump((end - start) / 1000000 + " ms");
		in.close();
		out.close();
	}

	static void dump(Object... o) { if (debug) System.err.println(Arrays.deepToString(o)); }
}

Measured memory_bytes: 27528
N,M = (int(x) for x in input().split())
a = list(map(int,input().split()))
x = sum(a)*1/(4*M)

pick = 0
for (a_i) in a:
    if (a_i) >= x:
        pick += 1

if pick >= M:
    print("Yes")
else:
    print("No")

Measured memory_bytes: 3060
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

class Main {
	public static void main(String[] args){
		
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		String s;
		try {
			s = new String(in.readLine());
			s = s.replaceAll(" ", "");
			int i = Integer.parseInt(s);
			String opt;
			if(i%4 == 0) opt = "YES";
			else opt = "NO";
			System.out.println(opt);
		} catch (IOException e) {
			// TODO 自動生成された catch ブロック
			e.printStackTrace();
		}
	}
}

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

int main(){
  int D,G;
  cin >> D >> G;

  vector<int> stock(D);
  vector<int> bonus(D);
  for(int i=0; i<D; i++){
    cin >> stock.at(i);
    cin >> bonus.at(i);
  }

  int ans= INT_MAX;
  for(int tmp=0; tmp<(1<<D); tmp++){
    bitset<10> bits(tmp); // コンプリートする大問を管理

    int cnt= 0;
    int score= 0;
    for(int i=0; i<D; i++){
      if( bits.test(i) ){
        cnt+= stock.at(i);
        score+= (i+1)*100*stock.at(i)+ bonus.at(i);
      }
    }
    for(int i=D-1; i>=0; i--){
      if( !bits.test(i) ){
        int needed_score= max(0, G-score);
        int diff_score_max= (i+1)*100*(stock.at(i)-1);
        if( diff_score_max >= needed_score ){
          cnt+= (needed_score+ (i+1)*100- 1)/ ((i+1)*100);
          score+= needed_score; // 本当の差分は違うが、ここではscore>=Gであるかを判定できればよいので横着した
          break;
        }
        else{
          cnt+= stock.at(i)-1;
          score+= diff_score_max;
        }
      }
    }

    if( score>=G && ans>cnt ) ans= cnt;
  }

  cout << ans << endl;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <math.h>
#include <string.h>
#define rep(i,n) for(i=0;i<n;i++)
int in_i(void){
	int i;
	scanf("%d",&i);
	return i;
}
long long in_ll(void){
	long long i;
	scanf("%lld",&i);
	return i;
}
int cnt(long long a){
	int c=0;
	while(a){
		c++;
		a/=10;
	}
	return c;
}
int min(int a,int b){
	return a<b?a:b;
}
int max(int a,int b){
	return a>b?a:b;
}
int f(long long a,long long b){
	return max(cnt(a),cnt(b));
}
int main(void){
	long long n,i,ans=10000;
	n=in_ll();
	for(i=1;i*i<=n;i++){
		if(n%i){
			continue;
		}
		ans=min(ans,f(i,n/i));
	}
	printf("%d\n",ans);
	return 0;
}

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

#include <atcoder/all>
using namespace atcoder;
using namespace std;
using ll = long long;
using vi = vector<int>;
using vll = vector<ll>;
using pi = pair<int, int>;
using pll = pair<ll, ll>;
template <class T>
using vv = vector<vector<T>>;
#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 rrep(i, n) for (int i = (int)(n)-1; i >= 0; i--)
#define rrepi(i, a, b) for (int i = (int)(b)-1; i >= (int)(a); i--)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define bit(n) (1LL << (n))
template <class T>
inline bool chmax(T &a, const T &b) {
    if (a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
inline bool chmin(T &a, const T &b) {
    if (a > b) {
        a = b;
        return 1;
    }
    return 0;
}
const int INF = 1002003004;
const ll LINF = 1002003004005006007ll;
struct preprocess {
    preprocess() {
        cin.tie(nullptr);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(20);
    }
} ____;
#pragma endregion head

#pragma region library
#pragma endregion library
int f(int a, int b) {
    return max(a, b);
}
int e() {
    return -1;
}
int val;
bool check(int a) {
    return a < val;
}
int main() {
    int n, q; cin >> n >> q;
    vi a(n);
    rep(i, n) cin >> a[i];
    segtree<int, f, e> sg(a);
    while (q--) {
        int t, x, y;
        cin >> t >> x >> y;
        x--;
        if (t == 1) {
            sg.set(x, y);
        } else if (t == 2) {
            cout << sg.prod(x, y) << '\n';

        } else if (t == 3) {
            val = y;
            cout << sg.max_right<check>(x)+1 << '\n';
        }
    }
}

Measured memory_bytes: 6140
import java.util.Scanner;


public class Main {

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ

		Scanner sc = new Scanner(System.in);
		String S = sc.next();
		sc.close();

		S = S.replace("hi", "");
		int ans = S.length();

		if(ans==0) {
			System.out.println("Yes");
		}else {
			System.out.println("No");
		}



	}
}


Measured memory_bytes: 21972
N,M = map(int, input().split())
grid = []
for i in range(M):
    array = list(map(int, input().strip().split(' ')))
    grid.append([i+1,array[0],array[1]])
grid.sort(key=lambda x:x[2])

dic = {}
for i in range(N):
  dic[i+1] = 1

for arrays in grid:
  arrays.append(arrays[1]*1000000+dic[arrays[1]])
  dic[arrays[1]] += 1
  
grid.sort(key=lambda x:x[0])

for arrays in grid:
  s = str(arrays[3])
  print('0'*(12-len(s))+s)

Measured memory_bytes: 42820
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a;i<(b);++i)
#define debug(x) cerr<<#x<<": "<<x<<endl
#define trav(a,x) for(auto &a:x)
#define all(x) x.begin(),x.end()
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll l;
    int n;
    cin >> l >> n;
    vector<ll> a(n), b(n);
    rep(i,0,n) cin >> a[i];
    rep(i,0,n) b[i] = l-a[i];
    vector<ll> suma(n+1), sumb(n+1);
    rep(i,0,n) {
        suma[i+1]=suma[i]+a[i];
        sumb[i+1]=sumb[i]+b[i];
    }
    ll ans = 0;
    rep(i,0,n+1) {
        int k = min(i,n-i);
        ll suml = suma[i]-suma[i-k];
        ll sumr = sumb[i+k]-sumb[i];
        ll can1 = 2*(suml+sumr);
        if(i-1>=0) can1-=a[i-1];
        ll can2 = 2*(suml+sumr);
        if(i<n) can2-=b[i];
        if(i-k-1>=0) can1+=2*a[i-k-1];
        if(i+k<n) can2+=2*b[i+k];
        ans=max(ans,max(can1,can2));
        // debug(ans);
        // debug(i);
    }
    cout<<ans<<"\n";
}


Measured memory_bytes: 6528
#include <bits/stdc++.h>
#define rep(i,a) for(int i=0;i<int(a);++i)
#define REP(i,a,b) for(int i=int(a);i<int(b);++i)
#define pb push_back
#define mp make_pair
#define F first
#define S second
using ll = long long;
using itn = int;
using namespace std;
using Graph = vector<vector<int>>;
static const long double GRATIO=(long double)(1+sqrt(5))/2;
ll GCD(ll a, ll b){
    return b ? GCD(b, a%b) : a;
}
ll LCM(ll a, ll b){
    return a/GCD(a,b)*b;
}
int main(){
    int A,B;
    cin>>A>>B;
    if(A-(B*2)<0) cout<<"0"<<endl;
    else cout<<A-(B*2)<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define endl            "\n"
#define ff              first
#define ss              second
#define int             long long
#define pb              emplace_back
#define mp              make_pair
#define bs              binary_search
#define pqb             priority_queue<int>
#define setbits(x)      __builtin_popcountll(x)
#define mod             1000000007
#define ps(x,y)         fixed<<setprecision(y)<<x
#define test(x)         int x; cin>>x; while(x--)
#define pi              3.14159265358979323846
void c_p_c()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
}
// int pow(int a, int b, int c)
// {
// 	int res = 1;
// 	while (b > 0)
// 	{
// 		if (b % 2)
// 			res = (res * a) % c;
// 		a = (a * a) % c;
// 		b >>= 1;
// 	}
// 	return res;
// }
/*********************CODE BEGINS*******************/
void solve()
{
	char ch;
	cin >> ch;
	int x = ch;
	if (x >= 65 && x <= 90)
		cout << "A";
	else
		cout << "a";
}
int32_t main()
{
	c_p_c();
	// test(x)
	solve();
}

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

#define int long long

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

int N, M;
int mod = 1e9 + 7;

int fact(int a) {
    if (a == 0) {
        return 1;
    }
    return fact(a - 1) * a % mod;
}

signed main() {
    cin >> N >> M;
    if (abs(N - M) >= 2) {
        cout << 0 << endl;
        return 0;
    }
    if (abs(N - M) == 1) {
        cout << fact(N) * fact(M) % mod << endl;
        return 0;
    }
    cout << 2 * fact(N) % mod * fact(M) % mod << endl;
    return 0;
}


Measured memory_bytes: 1792
#include <cassert>
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <cwchar>
#include <cwctype>
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <array>
#include <atomic>
#include <chrono>
#include <codecvt>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#define rep(i, n) for(ll i = 0; i < (ll)(n); 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 all(x) (x).begin(),(x).end()
#pragma GCC optimize("Ofast")
using namespace std;
typedef long long int ll;
typedef long double ld;
const ll INF=(1LL<<62);
const ld pi=acosl((ld)-1);
// const ll mod = 1000000007;
const ll mod = 1234567;
const int dx[4]={0,1,0,-1};
const int dy[4]={1,0,-1,0};
const int ddx[8]={1,0,-1,-1,-1,0,1,1};
const int ddy[8]={1,1,1,0,-1,-1,-1,0};
#define endn "\n"

bool solve(){
  ll n;cin>>n;
  vector<pair<pair<string,ll>,ll>>v(n);
  rep(i,n){
    string s;cin>>s;
    ll p;cin>>p;
    v[i]=make_pair(make_pair(s,-p),i+1);
  }
  sort(all(v));
  rep(i,n)cout<<v[i].second<<endl;
  return false;
}

signed main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout<<fixed<<setprecision(30);
  solve();
}


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

#ifdef NON_SUBMIT
#define TEST(n) (n)
#define tout cerr
#else
#define TEST(n) ((void)0)
#define tout cin
#endif

using namespace std;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	TEST(freopen("input.txt","r",stdin));
	TEST(freopen("output.txt","w",stdout));
	TEST(freopen("debug.txt","w",stderr));
	int h1, m1, h2, m2, t1, t2, K;
	cin>>h1>>m1>>h2>>m2>>K;
	t1=h1*60+m1;
	t2=h2*60+m2;
	cout<<t2-t1-K<<'\n';
	return 0;
}

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

using namespace std;
typedef long long ll;
const int N=1e5+10;

int main()
{
    int k,a,b;
    cin>>k>>a>>b;
    for(int i=a;i<=b;i++){
        if(i%k==0){
            cout<<"OK"<<endl;
            return 0;
        }
    }
    cout<<"NG"<<endl;
}



Measured memory_bytes: 3600
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<LL,LL> pll;
const int maxn=1E5+5;

vector<int> a;
int main(){
    int k,n;
    cin>>k>>n;
    a.resize(n);
    for(int i=0;i<n;i++) cin>>a[i];
    int ans=k-a[n-1]+a[0];
    for(int i=0;i<n-1;i++){
        ans=max(ans,abs(a[i+1]-a[i]));
    }
    cout<<k-ans<<endl;
    return 0;
}

Measured memory_bytes: 1024
import sys

sys.setrecursionlimit(4100000)


def inputs(num_of_input):
    ins = [input() for i in range(num_of_input)]
    return ins


def solve(inputs):
    [M1, D1] = string_to_int(inputs[0])
    [M2, D2] = string_to_int(inputs[1])
    if M1 != M2:
        return 1
    return 0


def string_to_int(string):
    return list(map(lambda x: int(x), string.split()))


if __name__ == "__main__":
    ret = solve(inputs(2))
    print(ret)


Measured memory_bytes: 38384
#include<stdio.h>

int main(){
	int a,b;
	char op;
	while(1){
		scanf("%d %c %d",&a,&op,&b);
		if(op == '?'){
			break;
		}
		else if(op == '+'){
			printf("%d\n",a+b);//加算
		}
		else if(op == '-') {
			printf("%d\n",a-b);  //減算
		}
		else if(op == '*'){
			printf("%d\n",a*b);  //乗算
		}
		else if(op == '/'){
			printf("%d\n",a/b);  //除算
		}
	}
	
	return 0;
}


Measured memory_bytes: 2052
#include <bits/stdc++.h> 
using namespace std;
///////////////////////////////////////////
const long long int INF = INT32_MAX;
const long long int Mod = 1000000007;
const long long int mod = 100000;//10^5
using ll = long long int; //long long int は64bit
using ci = const int; using vi = vector<int>; using Vi = vector<long long int>; using pii = pair<int,int>;
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define mt make_tuple
#define all(x) (x).begin(),(x).end()
#define rep(i,N) for(int i=0;i<N;i++)
#define np nullptr
template<class T>bool chmax(T &former, const T &b) { if (former<=b) { former=b; return true; } return false; }
template<class T>bool chmin(T &former, const T &b) { if (b<former) { former=b; return true; } return false; }
template<class T>T sqar(T x){ return x*x; }//sqrt(x)は平方根;
#define Sort(v) std::sort(v.begin(), v.end(), std::greater<decltype(v[0])>()) //降順でVをソート
#define fill(x,num) memset(x,num,sizeof(x));
typedef vector<vector<ll> > matrix;
//       cin.tie(0);ios::sync_with_stdio(false);
void cinit(){cin.tie(0);ios::sync_with_stdio(false);}
//////////////////////////^^ *Emile ^^^//////////////////////////////////////////////////////

ll m[3][3]={0};

int main(){
	rep(i,3){
		rep(j,3){
			cin>>m[i][j];
		}
	}
	ll tmp = 0;
	bool key=true;
	rep(j,2){
		rep(i,3){
			if(i!=0 && tmp!=m[j+1][i]-m[j][i])key = false;
			tmp = m[j+1][i]-m[j][i];
		}
	}
	rep(i,2){
		rep(j,3){
			if(j!=0 && tmp!=m[j][i+1]-m[j][i])key = false;
			tmp = m[j][i+1]-m[j][i];
		}
	}
	if(key)cout<<"Yes"<<endl;
	else cout<<"No"<<endl;
	return 0;
}

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

int main(){
    int n;
    cin >> n;
    int m = n%10;
    
    if(m == 2 || m == 4 || m == 5 || m == 7 || m == 9) cout << "hon" << endl;
    if(m == 0 || m == 1 || m == 6 || m == 8) cout << "pon" << endl;
    if(m == 3) cout << "bon" << endl;
    
}

Measured memory_bytes: 3636
using System;
//using System.Collections;
using System.Collections.Generic;
using System.Linq;

namespace solution
{
  class Class1
  {
    static void Main()
    {
      string W = Console.ReadLine().ToUpper();
      string T = "";
      var T2 = new List<string>();
      int count = 0;

      while ((T = Console.ReadLine()) != "END_OF_TEXT")
      {
        T2 = T.Split().Select(x => x.ToUpper()).ToList();
        foreach (var i in T2)
        {
          if (i == W) count++;
        }
      }
      Console.WriteLine(count);
    }
  }
}


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

using namespace std;
using ll = long long;
using ull = unsigned long long;

#ifndef __MACRO_H__
#define __MACRO_H__

#define all(collection)  (collection).begin(), (collection).end()		// begin to end
#define rep(i, begin, end) for (ll i = begin; i < end; i++)			// repeat
#define repr(i, begin, end) for (ll i = begin; end < i; i--)			// repeat reverse
#define size(collection) ((ll) (collection).size())				// collection size

#endif

struct Edge
{
	ll vertex;	// 頂点
	Edge(ll v)
	{
		vertex = v;
	}
};

using Graph = vector<vector<Edge>>;

/**
@brief 深さ優先探索
@param v 頂点
@param r 根
@param g 処理するグラフ
@param memo 前処理したメモ(加算するべきカウンタの値)
@param ans 出力する答えを格納する配列
@note
 DFSで全てのノードを処理する。
**/
void DFS(ll v, ll r, Graph& g, vector<ll>& memo, vector<ll>& ans)
{
	if (r != -1)
		ans[v] = ans[r] + memo[v];

	for (const auto& e : g[v])
	{	// 後戻りしないようにする
		if (e.vertex == r)
			continue;

		DFS(e.vertex, v, g, memo, ans);
	}
}

int main(void)
{
	ll n, q; cin >> n >> q;

	ll u, v;
	Graph g;
	g.resize(n);
	rep(ei, 0, n - 1)
	{
		cin >> u >> v;
		--u; --v;
		g[u].push_back(Edge(v));
		g[v].push_back(Edge(u));
	}

	vector<ll> p(q), x(q);
	rep(i, 0, q)
	{
		cin >> p[i] >> x[i];
		p[i]--;
	}

	// 頂点xで加算するべきカウンタの値をメモしておく。
	vector<ll> memo(n);
	rep(i, 0, q)
		memo[p[i]] += x[i];

	vector<ll> ans(n);
	ans[0] = memo[0];
	DFS(0, -1, g, memo, ans);

	for(auto& e: ans)
		cout << e << " ";

	return 0;
}

Measured memory_bytes: 35200
#include <algorithm>
#include <complex>
#include <cstdlib>
#include <ctime>
#include <time.h>
#include <iomanip>
#include <iostream>
#include <map>
#include <math.h>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <numeric>
#include <limits>
#include <type_traits>
#include <locale>
#include <omp.h>

using namespace std;
#define SAY_YES cout << "YES" << endl;
#define SAY_Yes cout << "Yes" << endl;
#define SAY_NO cout << "NO" << endl;
#define SAY_No cout << "No" << endl;
#define IFYES(TRUE_OR_FALSE)   \
    if (TRUE_OR_FALSE)         \
    {                          \
        cout << "YES" << endl; \
    }                          \
    else                       \
    {                          \
        cout << "NO" << endl;  \
    }
#define IFYes(TRUE_OR_FALSE)   \
    if (TRUE_OR_FALSE)         \
    {                          \
        cout << "Yes" << endl; \
    }                          \
    else                       \
    {                          \
        cout << "No" << endl;  \
    }
#define IFyes(TRUE_OR_FALSE)   \
    if (TRUE_OR_FALSE)         \
    {                          \
        cout << "yes" << endl; \
    }                          \
    else                       \
    {                          \
        cout << "no" << endl;  \
    }
#define DEBUG_OUTPUT_ARRAY(XXX, ONE)                            \
    for (int i = 0; i < (ONE); i++)                             \
    {                                                           \
        cout << "DEBUG: i = " << i << " -> " << XXX[i] << endl; \
    }
#define DEBUG_OUTPUT_ARRAY2(XXX, ONE, TWO)                             \
    for (int i = 0; i < (ONE); i++)                                    \
    {                                                                  \
        cout << "<<< i = " << i << " >>>" << endl;                     \
        for (int j = 0; j < (TWO); j++)                                \
        {                                                              \
            cout << "DEBUG: j = " << j << " -> " << XXX[i][j] << endl; \
        }                                                              \
    }
#define DEBUG_OUTPUT_ARRAY2_BOX(XXX, ONE, TWO) \
    for (int i = 0; i < (ONE); i++)            \
    {                                          \
        cout << i << "  ";                     \
        for (int j = 0; j < (TWO); j++)        \
        {                                      \
            cout << XXX[i][j] << " ";          \
        }                                      \
        cout << endl;                          \
    }

typedef pair<long long int, long long int> pll;
typedef pair<long long int, pll> lpll;

const long long int mod = 1000000007;
const long long int INF = 1e18;
const long double PI=3.14159265358979323; 
//const long long int pl=1000000;


long long int M1,M2,D1,D2;
int main(){
    cout << fixed << setprecision(18);
    cin>>M1>>D1>>M2>>D2;
    if(D2==1){cout<<1<<endl;}
    else{cout<<0<<endl;}
    
}



Measured memory_bytes: 3644
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<iomanip>
#include<cmath>

#define REP(i,n) for (int i = 0; (i) < (n); ++ (i))
#define FOR(i,n) for (int i = 1; (i) <= (n); ++ (i))
#define dump(x)  cout << #x << " = " << (x) << endl;
#define pb push_back
#define int long long

const int INF = 1e18;
const int MOD = 1e9+7;
//const lint LINF = 1e18;
const double eps = 0.000000001;//もとの値の10^(-16)まで

using namespace std;

//typedef pair<int, int> P;
//priority_queue< P, vector<P>, greater<P> > q;//ダイクストラの時、greaterで小さい順
//cout << fixed << setprecision(10) << ans << endl;
//int gcd(int a,int b){return b?gcd(b,a%b):a;}
map <int,int> cc;
signed main(){
    int n;
    cin >> n;
    REP(i,n){
        int a1;
        cin >> a1;
        if(cc[a1]==1){
            cout << "NO" << endl;
            return 0;
        }
        cc[a1]= 1;
    }
    cout << "YES" << endl;
    return 0;
}

Measured memory_bytes: 12800
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <utility>
#include <queue>
#include <set>
#include <map>

using namespace std;
typedef long long ll;
double L;
int main() {
  scanf("%lf", &L);
  printf("%.10f\n", L * L * L / 27.0); 
  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<map>
#include<algorithm>
#include<math.h>
#include<queue>
#include<stack>
#include<iomanip>
#include<cstring>
#include<string>
#include<set>

#define REP(i, n) for (int i = 0; i < n; i++)
#define ALL(v) v.begin(), v.end()

using namespace std;
using ll = long long int;

const ll INF = 1<<30;
const ll LINF = 1LL<<60;
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; }

int main(void) {
    ll n, m, k; cin >> n >> m >> k;
    vector<ll> a(n), b(m), suma(n + 1), sumb(m + 1);
    REP(i, n) cin >> a[i];
    REP(i, m) cin >> b[i];
    for (int i = 1; i < n + 1; i++) suma[i] = suma[i - 1] + a[i - 1];
    for (int i = 1; i < m + 1; i++) sumb[i] = sumb[i - 1] + b[i - 1];
    ll ans = 0;
    for (int i = 0; i < n + 1; i++) {
        if (suma[i] > k) break;
        auto itr = upper_bound(sumb.begin(), sumb.end(), k - suma[i]);
        chmax(ans, i + (ll)distance(sumb.begin(), itr) - 1);
    }
    cout << ans << endl;
}

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

using ll=long long; 

void solve(){
	string s;
	cin>>s;
	int mini=1000;
	for(int i=2; i<s.size(); i++){
		int x=stoi(s.substr(i-2, 3));
		mini=min(mini, abs(753-x));
	}
	cout<<mini<<endl;
}

signed main(){
	//while(1)
	solve();
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <unordered_map>

using namespace std;

int main () {
	string s;
	cin >> s;
	bool a = false;
	bool b = false;
	bool c = false;
	for(auto i : s){
		if(i == 'a'){
			if(a) break;
			else a = true;
		}	
		else if (i == 'b'){
			if(b) break;
			else b = true;
		}
		else if (i == 'c'){
			if(c) break;
			else c = true;
		}
		else break;
	}
	if (a&b&c){
		cout << "Yes";
	}
	else {
		cout << "No";
	}
	return 0;
}

Measured memory_bytes: 256
n, p = map(int, input().split())
S = list(map(int, list(input())))

if p == 2 or p == 5:
  ans = 0
  for i, x in enumerate(S[::-1]):
    if x % p == 0:
      ans += n - i
else:
  mods = [0 for _ in range(p)]
  mods[0] = 1

  num = 0
  digit = 1
  for s in S[::-1]:
    num = (s * digit + num) % p
    mods[num] += 1
    digit = (digit * 10) % p
  
  ans = 0
  for m in mods:
    ans += m * (m - 1) // 2

print(ans)


Measured memory_bytes: 6436
// AtCoder-Template.cpp : このファイルには 'main' 関数が含まれています。プログラム実行の開始と終了がそこで行われます。
//

#include <iostream>
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <deque>
#include <fstream>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <vector>
using namespace std;
using ll = long long;
#define fst first
#define snd second
#define FOR(i,N) for(auto i=0; i<N; ++i)
#define FORREV(i,N,_cnt) for(auto i=N-1,cnt=_cnt; cnt > 0; --i, --cnt)
#define ALL(x) x.begin(), x.end()

/* clang-format off */
template <class T, size_t D> struct _vec { using type = vector<typename _vec<T, D - 1>::type>; };
template <class T> struct _vec<T, 0> { using type = T; };
template <class T, size_t D> using vec = typename _vec<T, D>::type;
template <class T> vector<T> make_v(size_t size, const T& init) { return vector<T>(size, init); }
template <class... Ts> auto make_v(size_t size, Ts... rest) { return vector<decltype(make_v(rest...))>(size, make_v(rest...)); }
template <class T> inline void chmin(T& a, const T& b) { if (b < a) a = b; }
template <class T> inline void chmax(T& a, const T& b) { if (b > a) a = b; }
/* clang-format on */

int main() {
#ifdef DEBUG
	ifstream ifs("in.txt");
	cin.rdbuf(ifs.rdbuf());
#endif
	ll N; cin >> N;
	vector<ll> A(N); FOR(i, N) cin >> A[i];

	int accumu = 0;
	int nowLen = 0;

	vector<ll> to(N, -1);
	vector<ll> cnt(N, 0);

	//////////////////////////////////////////////////////////////////////////////

//  backforwrd LIS
//////////////////////////////////////////////////////////////////////////////
	vector<pair<ll, ll> > backLIS; // value, index
	FOR(_i, N) {
		auto i = N - 1 - _i;
		if (backLIS.empty()) {
			to[i] = -1;
			backLIS.emplace_back(A[i], i);
		}
		else {
			if (backLIS.back().first >= A[i]) { // 1,3,5, 7 で 4が来た場合
				auto it = lower_bound(backLIS.begin(), backLIS.end(), make_pair(A[i], 0), [](auto a, auto b) { return a.first < b.first; } );
				ll dis = distance(backLIS.begin(), it);
				backLIS.resize(dis);
				if (dis == 0) {

				}
				else {
					auto v = backLIS[dis-1];
					to[i] = v.second;
					cnt[v.second] += 1;
				}
				
				backLIS.emplace_back(A[i], i);
			}
			else { // 入っているやつのほうが小さい場合 // 1,3,5, で、6が来た場合、
				auto v = backLIS.back();
				to[i] = v.second;
				cnt[v.second] += 1;

				backLIS.emplace_back(A[i], i);				

			}
		}
	}


	ll ans = 0;
	FOR(i, N) {
		if (to[i] == -1) {
			ans += A[i] * (cnt[i] + 1) * (N - i);
		}
		else {
			ans += A[i] * (cnt[i] + 1) * (to[i] - i);
			cnt[to[i]] += cnt[i];
		}
	} 
	cout << ans << endl;


	return 0;
}


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

const int MAXN = 101010;

int a[MAXN];

class Node {
public:
	int v;
	Node *l, *r;
	int key;
	
	Node(int x) {
		v = a[x];
		l = r = 0;
		key = 1;
	}
};

//set<pair<int,int> > s;

class Road {
public:
	int t, next;
}e[MAXN * 2];
int p[MAXN];
int z = -1;

int vis[MAXN];

void add(int u, int v) {
	++z;
	e[z].t = v;
	e[z].next = p[u];
	p[u] = z;
}

Node *root[MAXN];

int getkey(Node *now) {
	return now ? now->key : 0;
}

void update(Node *now) {
	now->key = getkey(now->r) + 1;
}

Node* merge(Node *&l, Node *&r) {
	if(!l)
		return r;
	if(!r)
		return l;
//	cout<<l->v<<" "<<r->v<<endl;
	if(l->v < r->v) {
		l->r = merge(l->r, r);
		if(getkey(l->l) < getkey(l->r))
			swap(l->l, l->r);
		update(l);
		return l;
	}
	else {
		r->r = merge(l, r->r);
		if(getkey(r->l) < getkey(r->r))
			swap(r->l, r->r);
		update(r);
		return r;
	}
}

void dfs(int u, int fa, int tag) {
	vis[u] = tag;
	if(u != tag) {
		root[tag] = merge(root[tag], root[u]);
		root[u] = 0;
	}
	for(int tmp = p[u]; tmp != -1; tmp = e[tmp].next) {
		if(e[tmp].t != fa) {
			dfs(e[tmp].t, u, tag);
		}
	}
} 

void del(Node *&now) {
	//print(now);
	now = merge(now->l, now->r);
}


int n, m;

int main() {
	scanf("%d%d", &n, &m);
	for(int i = 0; i < n; ++i) {
		scanf("%d", &a[i]);
		root[i] = new Node(i);
	}
	int u, v;
	memset(p, -1, sizeof(p));
	
	for(int i = 1; i <= m; ++i) {
		scanf("%d%d", &u, &v);
		add(u, v);
		add(v, u);
	}
	memset(vis, -1, sizeof(vis));
	
	int cnt = 0;
	long long ss = 0;
	Node *tmp = 0;
	for(int i = 0; i < n; ++i) {
		if(vis[i] == -1) {
			++cnt;
			dfs(i, -1, i);
			ss += root[i]->v;
			del(root[i]);
			tmp = merge(tmp, root[i]);
		}
	}
	if((n - 1 - m) * 2 > n) {
		puts("Impossible");
		return 0;
	}
	if(m == n - 1) {
		puts("0");
		return 0;
	}
	
	int need = (n - 1 - m) * 2 - cnt;
	for(int i = 1; i <= need; ++i) {
		ss += tmp->v;
		del(tmp);
	}
	
	//if(cnt >= n - 1) {
		printf("%lld\n", ss);
	//}
	/*else {
		puts("Impossible");
	}*/

	return 0;
}

Measured memory_bytes: 8448
import java.util.Scanner;
import java.util.Random;
import java.util.Arrays;
import java.util.Comparator;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Main {
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int k = sc.nextInt();
		int m = 1;
		for (int i = 0; i < n; i++) {
		    if (m >= k) {
		        m += k;
		    } else {
		        m *= 2;
		    }
		}
		System.out.println(m);
	}
	
	
}

Measured memory_bytes: 22996
import java.util.*;
public class Main{
	public static void main(String[] args){
		Scanner scan = new Scanner(System.in);
		int a = scan.nextInt();
		int b = scan.nextInt();
		int c = scan.nextInt();
		int d = scan.nextInt();
		int e = scan.nextInt();
		int k = scan.nextInt();
		if(b-a>k||c-a>k||d-a>k||e-a>k||c-b>k||d-b>k||e-b>k||d-c>k||e-c>k||e-d>k){
			System.out.println(":(");
		}
		else{
			System.out.println("Yay!");
		}
	}
}

Measured memory_bytes: 23252
import java.io.InputStream;
import java.io.PrintStream;
import java.util.*;

public class Main {

  public static void main(String[] args) {
    solve(System.in, System.out);
  }

  static void solve(InputStream is, PrintStream os) {
    Scanner sc = new Scanner(is);

    /* read */

    int n = sc.nextInt();
    int[] a = new int[n + 1];
    int[] b = new int[n];

    for (int i = 0; i < n + 1; i++) {
      a[i] = sc.nextInt();
    }
    for (int i = 0; i < n; i++) {
      b[i] = sc.nextInt();
    }

    long sum = 0;

    long remain = 0;
    long kill;
    for (int i = 0; i < n; i++) {
      if (a[i] <= remain) {
        kill = a[i];
        remain = b[i];
      } else {
        kill = Math.min(a[i], remain + b[i]);
        remain = b[i] - (kill - remain);
      }
      sum += kill;
    }
    kill = Math.min(a[n], remain);
    sum += kill;

    os.println(sum);
  }
}

Measured memory_bytes: 66976
N = STDIN.gets.chomp.to_i
info = Array.new(0)
result = Array.new(N, -1)

while (line = STDIN.gets) != nil do
  info.push(line.chomp.split(' ').map(&:to_i))
end

tree = Array.new(N).map{Array.new(0)}

info.each { |a|
  # info[i-1][0] に u
  # info[i-1][1] に v
  u, v, w = a
  bin = w % 2
  tree[u-1].push([v-1, bin])
  tree[v-1].push([u-1, bin])
}

result[0] = 0
# queueに何かある
queue = Array.new(0)
queue.push(0)
while (queue.size > 0) do
  position = queue.shift
  tree[position].each{ |infoList|
    nodeNum, cost = infoList
    if result[nodeNum] == -1 then
      result[nodeNum] = (result[position] + cost % 2) % 2
      queue.push(nodeNum)
    end
  }
end

result.each { |a|
  puts a
}


Measured memory_bytes: 29436
import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7




n = input()

cnt = 0
for i in range(len(n) - 1):
    if n[i] != n[i + 1]:
        cnt += 1



print(cnt)

Measured memory_bytes: 39408
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;cin>>n;
    vector<int> p(n);
    int m=n+1;
    int ans=0;
    for(int i=0;i<n;i++){
        cin>>p[i];
        if(p[i]<m){
            ans++;
        }
        m=min(m,p[i]);
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 1024
short*p,v[2][104];main(c,n,m,i,y){for(;m=scanf("%d %[^\n] %[^\n]",&n,v,v+1)*n;printf(m>n?"NA\n":"%d\n",m))for(i=2;i--;m=c)for(c=0,y=n;y-->1&c<m;y+=y==n|*p&2?2:*p&p[-1]&1?0:~!++c)p=y+v[c+i&1];}

Measured memory_bytes: 600
fn main() {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).unwrap();
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).unwrap();
    let a: Vec<usize> = s.trim().split_whitespace().map(|x| x.parse().unwrap()).collect();

    let mut x: isize = 0;
    let mut y: isize = 0;
    let mut z: isize = 0;

    for i in &a {
        if *i % 4 == 0 {x += 1;}
        else if *i % 2 == 0 {y += 1;}
        else {z += 1;}
    }

    if y == 0 {z -= 1;}
    println!("{}", if z <= x {"Yes"} else {"No"});
}



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

int main() {
    int N;
    cin >> N;
    ll a = 2, b = 1;
    rep(i, N-1) {
        ll c = a + b;
        a = b;
        b = c;
    }
    cout << b << endl;
}

Measured memory_bytes: 256
a,b,c,d = [int(i) for i in input().split()]
if c >= b or d <= a:
  print(0)
else:
  if a <= c and b >= d:
    print(d-c)
  elif c < a and b < d:
    print(b-a)
  elif a <= c < b <= d:
    print(b-c)
  else:
    print(d-a)

Measured memory_bytes: 3060
n = int(input())
s = input()

ans = 0
for i in range(1, n):
    x = s[0:i] 
    y = s[i:n]
    xl = list(x)
    yl = list(y)
    cnt = 0
    pre = []
    for j in range(len(xl)):
        if xl[j] in yl and xl[j] not in pre:
            cnt += 1
            pre.append(xl[j])
    if ans < cnt:
        ans = cnt
print(ans)

Measured memory_bytes: 39024