akhauriyash/Code-Regression huggingface dataset:
from time import time
start=time()
from copy import deepcopy

d=int(input())
c=list(map(int,input().split())) #scoreを減らす
s=[] #scoreを増やす
for i in range(d):
    t=list(map(int,input().split()))
    s.append(t)
last=[0]*26 #それぞれのコンテストが最後に行われたのは何日目か
ans_lst=[]

for i in range(1,d): #364日、1日目ならi=1
    temp_best=-100000000
    for j in range(26): #それぞれの日において、26個のコンテストを順番にピックアップ
        temp=s[i-1][j]
        for k in range(26): #ピックアップされていないコンテストは、スコアを減らす
            if j!=k:
                temp-=(c[k]*(i-last[k]))
        temp_last=deepcopy(last)
        temp_last[j]=i
        for k in range(26):
            temp+=s[i][k]
            for l in range(26):
                if k!=l:
                    temp-=(c[l]*(i+1-temp_last[l]))
        if temp>temp_best:
            temp_best=temp
            rem=j
    ans_lst.append(rem)
    last[rem]=i
    
temp_best=-100000000 #365日目は、次の日のことは考えなくてよい
for j in range(26): #26個のコンテストを順番にピックアップ
    temp=s[i-1][j]
    for k in range(26): #ピックアップされていないコンテストは、スコアを減らす
        if j!=k:
            temp-=(c[k]*(i-last[k]))
    if temp>temp_best:
        temp_best=temp
        rem=j
ans_lst.append(rem) #AtCoder運営お疲れ様です

score=0
las=[0]*26
for i in range(d):
    for j in range(26):
        las[j]+=1
    score+=s[i][ans_lst[i]]
    las[ans_lst[i]]=0
    for j in range(26):
        score-=c[j]*las[j]

for q in range(1,21):
    for p in range(d-q):
        las=[0]*26
        temp_score=0
        temp_ans_lst=deepcopy(ans_lst)
        temp_ans_lst[p],temp_ans_lst[p+q]=temp_ans_lst[p+q],temp_ans_lst[p]
        for i in range(d):
            for j in range(26):
                las[j]+=1
            temp_score+=s[i][temp_ans_lst[i]]
            las[temp_ans_lst[i]]=0
            for j in range(26):
                temp_score-=c[j]*las[j]
        if temp_score>score:
            score=temp_score
            ans_lst=temp_ans_lst

for i in ans_lst:
    print(i+1)


Measured memory_bytes: 79212
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))
ans = 0
pi = -2
for ai in a:
    i = ai - 1
    if pi + 1 == i:
        ans += c[i-1]
    ans += b[i]
    pi = i
print(ans)


Measured memory_bytes: 3060
h, w = map(int, input().split())
c = []
for i in range(h):#h:高さ
    c.append([str(m) for m in list(input())])
pcnt = 0
qcnt = 0
for i in range(h):
    for j in range(w):
        if c[i][j] == "#":
            for p in range(i + 1, h):
                if c[p][j] == "#":
                    pcnt = 1
            for q in range(j + 1, w):
                if c[i][q] == "#":
                    qcnt = 1
            if pcnt == 1 and qcnt == 1:
                print("Impossible")
                exit()
            pcnt = 0
            qcnt = 0
print("Possible")

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;
using namespace std::chrono;

#define ll long long
#define ld long double
#define pq priority_queue
#define ff first
#define ss second
#define pb push_back
#define pb push_back
#define all(c) (c).begin(), (c).end()
#define sz(c) ((ll)c.size())
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define MOD1 998244353
#define MOD2 1000000007

#ifdef LL
const ll INF = 1e18;
#else 
const ll INF = 1e9;
#endif

typedef pair<ll, ll> ii;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef vector<ii> vii;
typedef vector<vii> vvii;

high_resolution_clock::time_point setTime() { return high_resolution_clock::now(); }
bool sortbysec(const pair<int,int> &a,const pair<int,int> &b){return (a.second < b.second);} //Just add this as a third argument to sort() while sorting an array of pairs; NO NEED FOR ANY ARGUMENTS;
template <typename T>
T fact(T a, T mod){ int res = 1, i; for (i = 2; i <= a; i++){ res *= i; res%=mod;} return res; }
template <typename T>
ll powmod(T a,T b,ll m){ ll ans=1; while(b>0){if(b&1){ans*=a;ans%=m;}a*=a;a%=m;b>>=1;} return ans; }
template <typename T>
ll power(T a, T b){ ll ans=1; while(b>0){if(b&1){ans*=a;}a*=a;b>>=1;}return ans;}
template <typename T>
T max3(T a, T b, T c) { return max((max(a,b), max(b,c))); }
template <typename T>
T min3(T a, T b, T c) { return min((min(a,b), min(b,c))); }
template <typename T>
T mid3(T a, T b, T c) { return a+b+c-max3(a,b,c)-min3(a,b,c); }
template <typename T>
T mid(T a, T b) { return min(a,b)+((max(a,b)-min(a,b))/2); }
template <typename T>
T gcd(T a,T b){ return (b?__gcd(a,b):a); }
template <typename T>
T lcm(T a, T b){ return (a*(b/gcd(a,b))); }
template <typename T>
T cl(T a, T b){ return (a+b-1)/b; }
template <typename T>
T to_upper(T s){ return transform(s.begin(), s.end(), s.begin(), ::toupper); }
template <typename T>
T to_lower(T s){ return transform(s.begin(), s.end(), s.begin(), ::tolower); }

int main()
{
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);
    auto startTime = setTime();

    int n;
    cin>>n;
    ll a[n];
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }

    ll dp[n][n];
    for(int i=n-1;i>=0;i--)
    {
        for(int j=i;j<n;j++)
        {
            if(i==j) dp[i][j] = a[i];
            else
            {
                dp[i][j] = max(a[i]-dp[i+1][j], a[j]-dp[i][j-1]); //this does not mean anything
            }
        }
    }

    cout<<dp[0][n-1]<<endl;

    auto stopTime = setTime();
    auto duration = duration_cast<microseconds>(stopTime - startTime);
    //cout<<"Program ran for "<<(ld)duration.count()/1e6<<" "<<"seconds"<<endl;
}


Measured memory_bytes: 49708
#include <bits/stdc++.h>
using namespace std;
const int n=1e5+10;
bitset<n> isprime;
vector<int>answer;
void sieve()
{
    isprime[0]=isprime[1]=0;
    for(int p=2; p<=n; ++p)
        if(isprime[p])
            for(int m=2*p; m<n; m+=p)
                isprime[m]=0;

}


int the2017ers[n];
void is2017()
{
    int sum=0;
    for (int p=1; p<=n; p++)
    {
        sum+=(isprime[p]&&isprime[(p+1)/2]);
        the2017ers[p]=sum;

    }

}

int main()
{
     ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    isprime.set();
    sieve();
    is2017();
    int tc,l,r;
    cin>>tc;
    while(tc--)
    {
        cin>>l>>r;
        cout<<the2017ers[r]-the2017ers[l-1]<<endl;
    }


    return 0;
}


Measured memory_bytes: 1024
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#include <cstdlib>  // abs() for integer
#include <math.h>     // math.h をインクルードする！
#include <iomanip> // 小数点以下のやつ
using namespace std;
using ll = long long;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
int main() {
    int x, y;
    cin >> x >> y;
    rep(i, x + 1) {
        if(i * 2 + (x - i) * 4 == y) {
            cout <<"Yes" << endl;
            return 0;
        }
    }
    cout << "No" << endl;
   
}

Measured memory_bytes: 3616
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
#define rep(i, n) for(int i=0;i<(int)n;i++)
#define PI acos(-1)
#define fast_io ios_base::sync_with_stdio(false) ; cin.tie(0); cout.tie(0);
ll mod=1e9+7;


int main(){
    fast_io

    int n, k;
    cin>>n>>k;
    vector<ll> h(n);
    rep(i, n) cin >> h[i];
    ll ans=100100100100;
    sort(h.begin(), h.end());
    
    for(int i=0;i<=n-k;i++){
        //cout<<h[i+k-1]<<"-"<<h[i]<<endl;
        ans=min(ans, h[i+k-1]-h[i]);
    }
    cout<<ans<<endl;
    return 0;
}


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

int main() {

    ll n , i , k , j ;
    string s ;
    cin >> n >> s ;

    vector<ll>v[3] ;
    map<ll,ll>mp ;
    for(i=0;i<n;i++) {
        if (s[i]=='R') v[0].pb(i) ;
        else if (s[i]=='G') v[1].pb(i) ;
        else { v[2].pb(i) ; mp[i] = 1 ; }
    }
    ll ans = 0 ;
   // cout << v[0].size() << ' ' <<  v[1].size() << ' ' << v[2].size() << endl ;
    for(i=0;i<v[0].size();i++) {
        for(j=0;j<v[1].size();j++) {
            ans+=v[2].size() ;
            ll dif = abs(v[0][i]-v[1][j]) ;
            if(mp[v[0][i]+dif]) ans-- ;
            if(mp[v[0][i]-dif]) ans-- ;
            if(mp[v[1][j]+dif]) ans-- ;
            if(mp[v[1][j]-dif]) ans-- ;
            if((v[0][i]+v[1][j])%2==0 and mp[(v[0][i]+v[1][j])/2] ) ans-- ;
           // ans-- ;
        }
        //cout << ans << ' ' ;
    }
    /// 5 RGBRG

    cout << max(0LL,ans) << endl ;


    return 0 ;
}


Measured memory_bytes: 4292
#ifdef _MSC_VER
#define _CRT_SECURE_NO_WARNINGS
#  include <intrin.h>
#  define __builtin_popcount __popcnt
#endif

#define _USE_MATH_DEFINES
#include <stdio.h>
#include <functional>
#include <algorithm>
#include <iomanip>
#include <iostream>
#include <map>
#include <vector>
#include <regex>
#include <queue>
#include <string>
#include <set>

typedef  long long lol;
using namespace std;

#define fori(i,j,k) for (int (i)=(j);(i) < (k);(i)++)
#define MOD 1000000007
#define EPS 0.000000001



int main() {

#if defined(_DEBUG) 
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif

	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int n, m;
	cin >> n >> m;
	vector<long long> fact(1e6);
	fact[0] = 1;
	for (int i = 1; i < 1e6; i++)
		fact[i] = (fact[i - 1] * i) % MOD;

	long long ans = 0;
	if (n == m || (n + 1) == m)
	{
		ans = (ans + fact[n] * fact[m]) % MOD;
	}

	if (n == m || (m + 1) == n)
	{
		ans = (ans + fact[n] * fact[m]) % MOD;
	}

	cout << ans;

	return 0;
}

Measured memory_bytes: 8064
#include<bits/stdc++.h>
#define Fst first
#define Snd second
#define RG register
#define mp make_pair
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long LL;
typedef long double LD;
typedef unsigned int UI;
typedef unsigned long long ULL;
template<typename T> inline void read(T& x) {
	char c = getchar();
	bool f = false;
	for (x = 0; !isdigit(c); c = getchar()) {
		if (c == '-') {
			f = true;
		}
	}
	for (; isdigit(c); c = getchar()) {
		x = x * 10 + c - '0';
	}
	if (f) {
		x = -x;
	}
}
template<typename T, typename... U> inline void read(T& x, U& ... y) {
	read(x), read(y...);
}
char s[200010];
//#define rua
int main() {
//	ios::sync_with_stdio(false);
#ifdef rua
	freopen("GG.in","r",stdin);
#endif
  int n,A,B,C,D; read(n,A,B,C,D);
  scanf("%s",s+1);
  for(int i=A+1;i<C;++i) {
    if(s[i]=='#'&&s[i+1]=='#') {
      return puts("No"),0;
    }
  }
  for(int i=B+1;i<D;++i) {
    if(s[i]=='#'&&s[i+1]=='#') {
      return puts("No"),0;
    }
  }
  if(C<D) puts("Yes");
  else {
    for(int i=B;i<=D;) {
      if(s[i-1]!='#'&&s[i+1]!='#') {
        return puts("Yes"),0;
      }
      if(s[i+1]=='#') i+=2;
      else ++i;
    }
    puts("No");
  }
  return 0;
}



Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
#define ll long long 
int h[40];
int n;
double r;
inline bool check(double t);
int main(){
    while(cin>>r>>n,r){
        for(int i=0;i<40;i++)h[i]=0;
        for(int i=0;i<n;i++){
            int a,b,c;cin>>a>>b>>c;
            for(int j=a+20;j<b+20;j++){
                h[j]=max(h[j],c);
            }
        }
        double ok=0,ng=21;
        for(int i=0;i<50;i++){
            double mid=(ok+ng)/2;
            if(check(mid))ok=mid;
            else ng=mid;
        }
        printf("%.9f\n",ok);
    }
    return 0;
}

inline bool check(double t){
    for(int i=20-r+1;i<20+r;i++){
        double x=sqrt(r*r-(i-20)*(i-20))-r+t;
        if((double)h[i]>=x && (double)h[i-1]>=x){
            continue;
        }else{
            //cout<<"false"<<endl;
            //printf("%.9f\n",t);
            return false;
        }
    }
    //cout<<"true"<<endl;
    //printf("%.9f\n",t);
    return true;
}

Measured memory_bytes: 3208
#include <bits/stdc++.h>
#define fr(i, n) for (int i = 0; i < n; i++)
#define frab(i, a, b) for (int i = a; i < b; i++)
#define pb push_back
#define mp make_pair

using namespace std;

typedef long long ll;
typedef long double ld;

const ll INF = 1e9 + 10;
const ll MOD = 1e9 + 7;
const ld EPS = 1e-9;
const ld PI = acos(-1);
const int M = 1e3 + 10;
const int N = 1e6 + 10;

bool used[N];
vector<int> g[N];

vector<int> tops;

void dfs(int v) {
    used[v] = true;
    for (auto u: g[v])
        if (!used[u])
            dfs(u);
    tops.pb(v);
}

void solve() {
    int n, m;
    scanf("%d %d", &n, &m);
    int v, u;
    fr(i, n + m - 1) {
        scanf("%d %d", &v, &u);
        v--, u--;
        g[v].pb(u);
    }

    fr(i, n)
        if (!used[i])
            dfs(i);
    reverse(tops.begin(), tops.end());
    vector<int> backp(n);
    fr(i, n)
        backp[tops[i]] = i;

    vector<int> r(n, -1);

    fr(v, n)
        for (auto u: g[v]) {
            r[u] = max(r[u], backp[v]);
        }

    fr(i, n) {
        if (r[i] == -1)
            cout << 0 << endl;
        else
            cout << tops[r[i]] + 1 << "\n";
    }
}

int main() {
    //ios_base::sync_with_stdio(false);
    //freopen("a.in", "r", stdin);
    solve();
}


Measured memory_bytes: 31988
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>

using namespace std;

typedef long long ll;
typedef pair<int, int> P;

const int INF = 1001001001;

int main(){
    int A, B, C;
    cin >> A >> B >> C;
    
    if(A % 2 != 0 || B % 2 != 0 || C % 2 != 0){
        cout << 0 << endl;
        return 0;
    }
    if(A == B == C){
        cout << -1 << endl;
        return 0;
    }
    
    int cnt = 0;
    for(int i = 0; i < 100; ++i){
        int a = A / 2;
        int b = B / 2;
        int c = C / 2;
        
        A = a + b;
        B = b + c;
        C = c + a;
        cnt++;
        
        if(A % 2 != 0 || B % 2 != 0 || C % 2 != 0){
            cout << cnt << endl;
            return 0;
        }
    }
    
    cout << -1 << endl;
}

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

#define REP(i, n) for(int64_t i = 0; i < n; i++)
#define REPR(i, n) for(int64_t i = n; i >= 0; i--)
#define FOR(i, m, n) for(int64_t i = m; i < n; i++)
#define FORR(i, m, n) for(int64_t i = m; i >= n; i--)
#define ALL(v) v.begin(), v.end()
typedef long long ll;
template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    fill( (T*)array, (T*)(array+N), val );
}
template<class T>
inline bool chmax(T &a, T b) {if(a < b) {a = b;return true;}return false;}
template<class T>
inline bool chmin(T &a, T b) {if(a > b) {a = b;return true;}return false;}
const ll INF= 1ll << 60;
const ll MOD = 1000000007;
double EPS = 1e-10;
//----------------------------------------------------------

ll H;

int main(){
    cin >> H;
    ll cnt=0;
    ll t=1;
    while(true)
    {
        if(H==1){cnt+=t;break;}
        else
        {
            H=floor(H/2);
            cnt+=t;
            t*=2;
        }
    }
    cout << cnt << endl;
    return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int X = sc.nextInt();
        int t = sc.nextInt();

        if (X <= t) {
            System.out.println(0);
        } else {
            System.out.println(X - t);
        }
        sc.close();

    }
}

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

ll a,b,c,K;
ll ans=0;

int main(){
	cin>>a>>b>>c>>K;
	if(K>a){
		ans+=a;
		K -=a;
	}
	else{
		cout<<K<<endl;
		return 0;
	}
	if(K>b){
		K -=b;
	}
	else{
		cout<<ans<<endl;
		return 0;
	}
	cout<<ans-K<<endl;
	return 0;
}

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

#define LIMIT 320
// sqrt(10000) ~= 320!

bool P[100001];// false -> 소수, true -> 합성수
int accu[50002]; // accu[i] -> 1부터 2i-1 까지의 2017 similar 수의 개수. accu[0]은 항상 0;
bool is_prime(int n) {
    // if (n==2) return true;
    int limit = ((int)sqrt(n))+1;
    limit = min(limit, n-1);
    for (int i=2; i <= limit; i++) {
        if (n % i == 0) return false;
    }
    return true;
}
void set_sieve() {
    for (int i=2; i <= LIMIT; i++) {
        if (P[i]) continue;
        if (is_prime(i)) {
            // printf("set sieve, %d is prime\n", i);
            int base = i;
            int checker = i+i;
            while (checker <= 100000) {
                P[checker] = true;
                checker += base;
            }
        }
    }
}
inline bool similar(int n) {
    return P[n] == false and P[(n+1)/2] == false;
}
void set_accu() {
    int cnt = 0;
    int val = 1;
    for (int i=1; i<= 50000; i++) {
        if (similar(val)) cnt++;
        accu[i] = cnt;
        val += 2;
    }
}
int main() {
    P[0] = P[1] = true;
    int q;
    scanf("%d", &q);
    set_sieve();
    set_accu();
    
    // for (int i=1; i <15; i++) {
    //     if (similar(i)) printf("%d is similar\n", i);
    // }
    // for (int i=0; i< 10; i++) {
    //     printf("accu[%d] (%d ~ %d) = %d\n", i, 1, 2*i-1, accu[i]);
    // }
    while(q--) {
        int l, r;
        scanf("%d %d", &l, &r);
        int cnt = accu[(r+1)/2] - accu[(l+1)/2-1];
        // int cnt = 0;
        // for (int i=l; i <= r; i+=2) {
        //     if (similar(i)) {
        //         // printf("%d and %d is prime\n", i, (i+1)/2);
        //         cnt++;
                
        //     }
        // }
        printf("%d\n", cnt);
    }
    
    
    return 0;
}

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

using namespace std;

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

    int n, k;
    cin >> n >> k;
    vector<int> v(n);

    for(auto &num : v) cin >> num;

    vector<int> dp(n);

    dp[0] = 0;
    dp[1] = abs(v[1] - v[0]);

    for(int i = 2; i < n; i++)
    {
        auto minn = numeric_limits<int>::max();
        for(int j = i - 1; j + k >= i && j >= 0; j--)
        {
            minn = std::min(minn, dp[j] + abs(v[i] - v[j]));
        }
        dp[i] = minn;
    }

    cout << dp[n - 1] << '\n';
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define REP(i,n) for(int i=0;i<(n);i++)
#define ALL(a)  (a).begin(),(a).end()
#define SORT(c) sort((c).begin(),(c).end())
#define REV(c) reverse((c).begin(),(c).end())

using namespace std;
typedef pair<int,int> P;

// 最大公約数
int64_t gcd(int64_t a, int64_t b) {
  return b != 0 ? gcd(b, a % b) : a;
}

// 最小公倍数
int64_t lcm(int64_t a, int64_t b) {
  return a * b / gcd(a, b);
}

int ctoi(char c){
  return c - '0';
}

vector<long long> a;
int n;

long long Go(int from, int to, long long ca, long long cb) {
  if (to - from == 1) {
    return 0;
  }
  long long best;
  best = (long long) 1e18;
  for (int i = from + 1; i < to; i++) {
    long long cur = a[i] * (ca + cb) + Go(from, i, ca, ca + cb) + Go(i, to, ca + cb, cb);
    best = min(best, cur);
  }
  return best;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> n;
  a.resize(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  cout << Go(0, n - 1, 1, 1) + a[0] + a[n - 1] << '\n';
  return 0;
}



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

int main() {
    int A, B, C, D;
    cin >> A >> B >> C >> D;
    if (B <= C){
        cout << '0' << endl;
    }else if (D <= A){
        cout << '0' << endl;
    }else{
        cout << min(B, D) - max(A, C) << endl;
    }
    return 0;
}

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

int main(){
    int n;cin>>n;
    vector<int> a(n);for(int i=0;i<n;i++)cin>>a[i];
    sort(a.begin(),a.end());
    int sum=0;
    for(int i=0;i<n;i++){
        sum+=a[i];
        //cout<<a[i]<<endl;
    }
    int i;
    if(sum%10==0){
        for(i=0;i<n;i++){
            if(a[i]%10!=0){
                sum-=a[i];
                break;
            }
        }
        //cout<<"i="<<i<<endl;
    }
    cout<<((i==n)?0:sum)<<endl;
}

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

#define REP(i,s,n) for(int (i)=s; (i)<(int)(n);(i)++)
#define RIT(it,c) for(__typeof(c.begin()) it = c.begin();it!=c.end();it++)
#define ALL(x) x.begin(), x.end()
#define SZ(x) (int)(x).size()
#define MSET(m,v) memset(m,v,sizeof(m))


using namespace std;


typedef long long LL;
typedef vector<int> vi;
typedef pair<int,int> ii;
typedef pair<int,ii> iii;
typedef vector<LL> vL;
typedef vector<bool> vb;
typedef pair<int,vi> iv;
typedef pair<LL,LL> pLL; 
typedef long double LD;

const long double pi = 3.141592653589793238L;

bool extra(int x1,int y1,int x2, int y2, vector<ii> ft){
	bool ok = true;
	if((LL)(x1-x2)*(LL)(y1-y2) <0) ok = false;
	int n = (int)ft.size();
	int xm = min(x1,x2), xM = max(x1,x2), ym = min(y1,y2), yM = max(y1,y2);
	if(n==xM-xm+1){
		if(!ok) reverse(ft.begin(),ft.end());
		for(int i=1;i<n;++i) if(ft[i].second<ft[i-1].second)  return false;
		return true;
	}
	if(n==yM-ym+1){
		if(!ok) reverse(ft.begin(),ft.end());
		for(int i=0;i<n;++i) if(ft[i].second != ym+i) return false;
		return true;
	}
	return false;
}

int longestAsc(vi A){
	int n = (int)A.size();
	set<ii> ans;
	ans.insert(ii(A[0],1));
	for(int i=1;i<n;++i){
		auto it = ans.upper_bound(ii(A[i],0));
		auto it1 = it;
		int l = 1;
		if(it!=ans.begin()){
			it--;
			l = it->second + 1;
		}
		while(it1!=ans.end() && it1->second <= l) it1 = ans.erase(it1);
		ans.insert(ii(A[i],l));
	}
	return (--ans.end())->second;
}

LD minDis(int x1,int y1, int x2, int y2, vector<ii> ft){
	if(x1 == x2){
		LD ans = 100.*LD(abs(y1-y2));
		if(ft.empty()) return ans;
		ans += (pi-2.)*(LD)10.;
		return ans;
	}
	if(y1 == y2){
		LD ans = 100.*LD(abs(x1-x2));
		if(ft.empty()) return ans;
		ans += (pi-2.)*(LD)10.;
		return ans;
	}
	LD ans = 100.*LD(abs(x1-x2) + abs(y1-y2));
	if(ft.empty()) return ans;
	sort(ft.begin(),ft.end());
	int cnt = 1;
	bool ok = true, ed = false;
	if((LL)(x1-x2)*(LL)(y1-y2) <0) ok = false;
	int L = (int)ft.size();
	if(ok){
		vi tmp(L);
		for(int i=0;i<L;++i) tmp[i] = ft[i].second;
		cnt = longestAsc(tmp);
	}
	else{
		vi tmp(L);
		for(int i=L-1;i>=0;--i) tmp[L-i-1] = ft[i].second;
		cnt = longestAsc(tmp);
	}
	ans -= (LD)cnt*10.*(2.-pi/2.);
	if(extra(x1,y1,x2,y2,ft)) ans += pi/2.*(LD)(10.);
	return ans;
}

int main(){
	int x1,x2,y1,y2,N;
	cin>>x1>>y1>>x2>>y2>>N;
	int xm = min(x1,x2),xM = max(x1,x2), ym=min(y1,y2),yM=max(y1,y2);
	vector<ii> ft;
	for(int i=0;i<N;++i){
		int x,y;
		cin>>x>>y;
		if(x>=xm && x<=xM && y>=ym && y<=yM) ft.push_back(ii(x,y));
	}
	cout << setprecision(31);
	cout << minDis(x1,y1,x2,y2,ft)<<endl;
	return 0;
}

Measured memory_bytes: 14320
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <cstring>
#include <math.h>
#include <bitset>
#include <queue>
#include <set>
#include <iomanip>
#include <math.h>
#include <assert.h>
// #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr long long int INFLL = 1001001001001001LL;
constexpr long long int infll = 1001001001001001LL;
constexpr int INF = 1000000007;
constexpr int inf = 1000000007;
const int mod = 1000000007;

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

ll gcd(ll a, ll b)
{
    if (a % b == 0)
    {
        return (b);
    }
    else
    {
        return (gcd(b, a % b));
    }
}

ll lcm(ll a, ll b)
{
    return a / gcd(a, b) * b;
}

inline double nCr(const int n, int r)
{
    if (n == 0)
    {
        return 0;
    }
    if (r == 0)
    {
        return 1;
    }
    if (r == 1)
    {
        return n;
    }
    if (n == r)
    {
        return 1;
    }

    if (r > n / 2)
    {
        r = n / 2;
    }

    double result = 1;
    for (double i = 1; i <= r; i++)
    {
        result *= (n - i + 1) / i;
    }

    return (result);
}

template <typename T>
T seinomi(T a)
{
    if (a > 0)
    {
        return a;
    }
    else
    {
        return 0;
    }
}

template <typename T>
map<T, T> soinsuubunkai(T n) //連想配列[素因数f.first][個数f.second]
{
    map<T, T> ret;
    for (T i = 2; i * i <= n; i++)
    {
        while (n % i == 0)
        {
            ret[i]++;
            n /= i;
        }
    }
    if (n != 1)
        ret[n] = 1;
    return ret;
}

template <typename T>
T ketasuu(T num)
{
    return std::to_string(num).length();
}

int kaizyou(int k)
{
    int sum = 1;
    for (int i = 1; i <= k; ++i)
    {
        sum *= i;
    }
    return sum;
}

template <class ForwardIt, class T>
void iota(ForwardIt first, ForwardIt last, T value)
{
    while (first != last)
    {
        *first++ = value;
        ++value;
    }
}

//nの階乗を計算
int factorial(int n)
{
    int answer = 1;
    while (n > 1)
    {
        answer *= n;
        n--;
    }
    return answer;
}
int comb(int n, int r)
{
    return factorial(n) / (factorial(r) * factorial(n - r));
}

long long modpow(long long a, long long n, long long mod)
{
    long long res = 1;
    while (n > 0)
    {
        if (n & 1)
            res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}


template <typename T>
T amarinasi(T a,T b){
    if(a%b==0)
{
    return a/b;
}
else if(a%b>0)
{
    return a/b+1;
}
else
{
    return a/b-1;
}
}

//小数点以下10桁テンプレート（main関数内の最初に貼付け）
//std::cout << std::fixed << std::setprecision(10);

//----------------------------------------------------------------

int main(){
ll n;
cin>>n;
ll ans=1;
for(ll i=1;i<n;i++){
    if(i*i<=n){
        chmax(ans,i*i);
    }else{
        break;
    }
}
cout<<ans<<endl;
}












Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>
#include <cmath>
#include <map>

int main(void) {

	int a, b;

	std::cin >> a >> b;

	int sa = b - a;

	std::cout << ((sa - 1) * (sa)) / 2 - a << std::endl;

	return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <stdio.h>
#include <string>
#include <string.h>
#include <algorithm>
#include <vector>
using namespace std;


#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define RFOR(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define REP(n) for (int i=0;i<(n);i++)
#define RREP(i,n) for (int i=(n)-1;i>=0;i--)

int main(){
	int A,B,C;
	scanf("%d",&A);
	scanf("%d",&B);
	scanf("%d",&C);

	if(C >= A && C <= B){
		printf("Yes\n");
	}
	else{
		printf("No\n");
	}
}

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

int main(void){
    int n;
    cin>>n;
    vector<int> a(1<<n);
    rep(i,1<<n) cin>>a[i];
    using P = pair<int,int>;
    vector<set<P>> dp(1<<n);
    rep(i,1<<n){
        dp[i].insert({a[i],i});
        while((int)dp[i].size()>2){
            dp[i].erase(dp[i].begin());
        }
        for(P p : dp[i]){
            rep(k,n){
                dp[(1<<k)|i].insert(p);
            }
        }
    }
    ll mx = 0;
    rep1(i,(1<<n)-1){
        assert((int)dp[i].size() == 2);
        ll res = 0;
        for(P p : dp[i]){
            res += p.first;
        }
        mx = max(res,mx);
        cout<<mx<<endl;
    }
    return 0;
}


Measured memory_bytes: 49152
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using intpair=pair<int,int>;
using llpair=pair<ll,ll>;
using llvec=vector<ll>;
using llmat=vector<vector<ll>>;
#define llmattp(name,a,b,num) name(a,vector<ll>(b,num))
#define INTINF 1<<30
#define LLINF 1LL<<60
#define ABS(x) ( (x)>0 ? (x) : -(x) )

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

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

ll gcd(ll a, ll b) {
	if(a==0||b==0) return 0;
	if(a<b) swap(a,b);
	ll tmp = a%b;
	while(tmp!=0) {
		a = b;
		b = tmp;
		tmp = a%b;
	}
	return b;
}

ll factorial(ll x) {
	ll f=1;
	for(ll i=2; i<x; i++) {
		f*=i;
	}
	return f;
}

ll nPr(ll n, ll r) {
	ll result=1;
	for(ll i=r+1; i<=n; i++) result*=i;
	return result;
}

ll nCr(ll n, ll r) {
	if (n == r) { return 1; }
	if (r > n) { return 0; }

	if (r > n / 2) { r = n - r; }

	if (n == 0) { return 0; }
	if (r == 0) { return 1; }
	if (r == 1) { return n; }

	double result = 1;
	for (double i = 1; i <= r; i++) {
		result *= (n - i + 1) / i;
	}

	return (ll)result;
}

bool IsPrime(ll num) {
	if (num < 2) return false;
	else if (num == 2) return true;
	else if (num % 2 == 0) return false; // 偶数はあらかじめ除く

	double sqrtNum = sqrt(num);
	for (ll i = 3; i <= sqrtNum; i += 2)
	{
		if (num % i == 0)
		{
			// 素数ではない
			return false;
		}
	}

	// 素数である
	return true;
}

ll GreaterBinarySearch(ll *array, ll key, ll max, ll min) {
	if(array[max]<array[min]) {
		return NULL;
	} else {
		ll mid = max + (min-max)/2;
		if(array[mid]<key) {
			return GreaterBinarySearch(array,key,max,mid-1);
		} if(array[mid]>key) {
			return GreaterBinarySearch(array,key,mid+1,min);
		} else {
			return mid;
		}
	}
}

int main() {
	int N; cin>>N;
	int A[N];
	ll abssum=0LL;
	int u0num=0;
	int minnum=INTINF;

	for(int i=0; i<N; i++) {
		cin>>A[i];
		int absa=abs(A[i]);
		abssum+=absa;
		if(A[i]<0) u0num++;
		chmin(minnum,absa);
	}

	if(u0num%2) 
		cout<<abssum-2*minnum<<endl;
    else
		cout<<abssum<<endl;
}


Measured memory_bytes: 640
#include<iostream> 
#include<iomanip> 
#include<vector> 
#include<map> 
#include<set> 
#include<algorithm> 
#include<numeric> 
#include<limits> 
#include<bitset> 
#include<functional> 
#include<type_traits> 
#include<queue> 
#include<stack> 
#include<array> 
#include<random> 
#include<utility> 
#include<cstdlib> 
#include<ctime>
//#define _LIBCPP_DEBUG 0
//#define _GLIBCXX_DEBUG
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define all(a) (a).begin(),(a),end()
#define rep(i,n) for (int i = 0; i < (n); ++i)	
//setprecision(16)

void outi(int x) { cout << x << endl;}
void soutl(ll x) { cout << x << endl;}
void outs(string x) { cout << x << endl;}
ll max(ll a, ll b) {
	ll max;
	if (a > b) max = a;
	else max = b;
	return max;
}
ll min(ll a, ll b) {
	ll min;
	if (a < b) min = a;
	else min = b;
	return min;
}
//---------------------------------------------------------------

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

	int cnt = 0;
	int k =0;
	while (n > k) {
		k++;
		k += 2 * d;
		cnt++;
	}

	outi(cnt);
}

Measured memory_bytes: 256
//INCLUDE
//------------------------------------------
#include <bits/stdc++.h>
//DEFINE
//------------------------------------------
#define ll long long
#define ld long double
#define ALLv(a)  (a).begin(),(a).end()
#define ALL(a,n)  (a),(a)+n
#define vi vector<long long>
#define vd vector<long double>
#define vs vector<string>
//CONST
//------------------------------------------
#define INF 1010000000000000017LL
#define MOD 1000000007LL
#define EPS 1e-12
#define PI 3.14159265358979323846
//REPEAT
//------------------------------------------
#define   FOR(i,m,n) for(ll (i)=(m);   (i)<(n);  (i)++)
#define   REP(i,n)   for(ll (i)=0;     (i)<(n);  (i)++)
#define  REPS(i,x)   for(ll (i)=1;     (i)<=(x); (i)++)
#define  RREP(i,x)   for(ll (i)=(x)-1; (i)>=0;   (i)--)
#define RREPS(i,x)   for(ll (i)=(x);   (i)> 0;   (i)--)
#define  WREP(i,in,j,jn) REP(i,in)REP(j,jn)
//-----------------------------------------
#define ifYN(x) cout<<(x?"YES":"NO")<<"\n" 
#define dcml(n) fixed<<setprecision(n)

 
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; } 
ll Factorial(ll n){ ll m=1;while(n>=1)m*=n--;return m; } 
ll modPow(ll x,ll n,ll mod=MOD){ 
    return (!n?1:!n%2?modPow(x*x,n/2,mod)%mod:x%mod*modPow(x,n-1,mod)%mod); 
} 
using namespace std;
//-------------------------------------------
typedef pair<ll,ll> P;
int main(void){
    string S;cin>>S;
    reverse(ALLv(S));
    string ss[4]={"resare","esare","remaerd","maerd"};
    REP(i,4){
        while(S.find(ss[i])!=string::npos){
            S.erase( S.find(ss[i]),ss[i].size() );
        }
    }
    ifYN(S.size()==0);
}


Measured memory_bytes: 512
#include <iostream>
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <climits>
#include <vector>
#include <iomanip>
#include <string>
#include <queue>
#include <numeric>
#include <functional>
#include <array>
#include <map>
#include <set>

#define INF 1000000007 //1000000000000000003
#define MOD 1000000007
#define MAX 2000005

#define ll long long

//printf("%.10f", );
//cout << fixed << setprecision(10) << heikin << endl;
//vector<vector<int>> data(3, vector<int>(4, -1));
//left + 1 < top

using namespace std;
using P = pair<int, int>;
using Pc = pair<double, int>;
using T = tuple<int, int, int>;
using edge = struct { int to; long long dist; };
const double PI = 3.141592653589793;
long long fact[MAX], inv[MAX];
int dx[] = { -1,0,1,0 };
int dy[] = { 0,-1,0,1 };

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

vector<vector<int>> bingo(3, vector<int>(3));
vector<vector<int>> tree(100005);
int color[100005];
map<P, int>colorMap;
int m = 0;

struct BridgeInfo {
	int town1;
	int town2;
	int year;
	BridgeInfo(int t1, int t2, int y) {
		town1 = t1;
		town2 = t2;
		year = y;
	}
};

struct People {
	int index;
	int town;
	int year;
	People(int i, int t, int y) {
		index = i;
		town = t;
		year = y;
	}
};

bool compare_by_second(pair<int, int> a, pair<int, int> b) {
	if (a.second != b.second) {
		return a.second < b.second;
	}
	else {
		return a.first < b.first;
	}
}

struct UnionFind {
	vector<int>uf;

	UnionFind(int size) :uf(size, -1) {};

	int root(int target) {
		if (uf[target] < 0)return target;
		else return uf[target] = root(uf[target]);
	}

	void merge(int a, int b) {
		a = root(a);
		b = root(b);
		if (a == b)return;
		if (uf[b] < uf[a])swap(a, b);
		uf[a] += uf[b];
		uf[b] = a;
	}
};

ll CalcPow(ll num, ll power) {
	if (power == 0)return 1;
	if (power % 2 == 0) {
		ll half = CalcPow(num, power / 2);
		return (half * half) % MOD;
	}
	else return (num * CalcPow(num, power - 1)) % MOD;
}

ll combination(ll all, ll select) {
	if (all < select) return 0;
	if (all < 0 || select < 0) return 0;
	return fact[all] * (inv[select] * inv[all - select] % MOD) % MOD;
}

void initCombination(int max) {
	fact[0] = fact[1] = 1;
	for (int i = 2; i <= max; ++i) {
		fact[i] = fact[i - 1] * i % MOD;
	}

	inv[max] = CalcPow(fact[max], MOD - 2);
	for (int i = max - 1; 0 <= i; --i) {
		inv[i] = (inv[i + 1] * (i + 1)) % MOD;
	}
}

struct Connection {
	vector<int>friends;
	vector<int>block;
	vector<int>friendable;
	Connection() {};
};

int main() {

	int N, M;
	cin >> N >> M;

	int ans = 1 < N ? N * (N - 1) / 2 : 0;
	ans += 1 < M ? M * (M - 1) / 2 : 0;

	cout << ans << endl;
}



Measured memory_bytes: 2560
#include <stdio.h>
int main() {
	char c[2][4];
	scanf("%s",&c[0]);
	scanf("%s",&c[1]);
	if(c[0][0] == c[1][2] && c[0][1] == c[1][1] && c[0][2] == c[1][0]) printf("YES\n");
	else printf("NO\n");
	return 0;
}

Measured memory_bytes: 128
#include <iostream>
using namespace std;
int main(){
	int i,count=0;
	char a[16];
	for(i=0;i<=15;i++){
		cin>>a[i];
	}
	if(a[0]!='C')count++;
	if(a[1]!='O')count++;
	if(a[2]!='D')count++;
	if(a[3]!='E')count++;
	if(a[4]!='F')count++;
	if(a[5]!='E')count++;
	if(a[6]!='S')count++;
	if(a[7]!='T')count++;
	if(a[8]!='I')count++;
	if(a[9]!='V')count++;
	if(a[10]!='A')count++;
	if(a[11]!='L')count++;
	if(a[12]!='2')count++;
	if(a[13]!='0')count++;
	if(a[14]!='1')count++;
	if(a[15]!='6')count++;
	

	cout<<count<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;//d, v
const int max_n = 1e4;
const ll INF = 1e18;
ll n,m,k,q;
int color[max_n] = {0};
struct edge{
  ll to, cost;
};
vector<edge> G[max_n];
ll h,w;
ll d[max_n][max_n]={0};
bool used[max_n][max_n]={false};
int main(){
  cin >> n >> m;
  int dd[m];
  for(int i=0 ; i<m ; i++){
    cin >> dd[i];
  }
  sort(dd,dd+m);
  int sa[m-1];
  for(int i=0 ; i+1<m ; i++){
    sa[i] = dd[i+1] - dd[i];
  }
  sort(sa,sa+m-1);
  ll sum = 0;
  for(int i=0 ; i<m-1-(n-1) ; i++){
    sum += sa[i];
  }
  cout << sum << endl;
  return 0;
}


Measured memory_bytes: 1280
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define all(x) x.begin(),x.end()
#define dbg(x) cout<<#x<<":"<<x<<endl
typedef long long ll;
typedef pair<ll,ll> P;
typedef pair<ll,P> PP;

int main(){
  int n,m;
  cin>>n>>m;
  int box[111111];
  int red[111111]={};
  fill_n(box,111111,1);
  red[1]=1;
  for(int i=0;i<m;i++){
    int x,y;
    cin>>x>>y;
    box[x]--;
    box[y]++;
    if(red[x]==1)red[y]=1;
    if(box[x]==0)red[x]=0;
  }
  int sum=0;
  for(int i=1;i<=n;i++)sum+=red[i];
  cout<<sum<<endl;
  return 0;
}


Measured memory_bytes: 1152
#include <iostream>
#include <cstdlib>
#include <string>
#include <vector>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
#include <numeric>
#include <math.h>
#include <stdio.h>
#include <ctype.h>
#include <ios> 
#include <iomanip>
using namespace std;

#define N_MAX   (100000)
#define LL_MAX_NUM (1LL<<60)
#define INF 1e7

typedef long long ll;
typedef long long int lli;

int main() {
    string S, T; cin >> S >> T;
    int res = 0;
    for (int i = 0; i < S.size(); i++)
    {
        if (S[i] == T[i]) { res++; }
    }
    cout << res << endl;
	return 0;
}

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




const int nil=0;
int func(int a,int b){
	return max(a,b);
}



class SparseRMQ{
	map<int,int,greater<int> > mp;
public:
	void insert(int x,int v){
		map<int,int,greater<int> >::iterator it,s,e;
		it=mp.lower_bound(x);
		if(it==mp.end()){
			it=mp.insert(it,make_pair(x,v));
		}else if(it->first==x){
			if(v<=it->second)return;
			it->second=v;			
		}else{
			if(v<=it->second)return;
			it=mp.insert(it,make_pair(x,v));
		}
		s=e=it;
		while(s!=mp.begin()&&s->second<=v)
			it=s--;
		if(s->second>v)s=it;
		mp.erase(s,e);
	}
	int max(int xe)const{//(-inf,xe)
		map<int,int,greater<int> >::const_iterator it;
		it=mp.upper_bound(xe);
		if(it==mp.end())return nil;
		return it->second;
	}
};


class Dynamic2DRMQ_BIT{
	std::vector<SparseRMQ*> bit;
public:
	Dynamic2DRMQ_BIT(int xsize):bit(xsize+1,(SparseRMQ*)NULL){}
	~Dynamic2DRMQ_BIT(){
		for(int i=0;i<(int)bit.size();i++)
			if(bit[i])delete bit[i];
	}
	void insert(int x,int y,int v){
		x++;
		while(x<(int)bit.size()){
			if(!bit[x])bit[x]=new SparseRMQ();
			bit[x]->insert(y,v);
			x+= x&-x;
		}
	}
	int query(int xe,int ye)const{//[0,xe)*[0,ye)
		int res=nil;
		while(0<xe){
			if(bit[xe])res=func(res,bit[xe]->max(ye));
			xe-= xe&-xe;
		}
		return res;
	}
};




int m,n,A,B;

int r() {
	static const int C = ~(1<<31), M = (1<<16)-1;
	A = 36969 * (A & M) + (A >> 16);
	B = 18000 * (B & M) + (B >> 16);
	return (C & ((A << 16) + B)) % 1000000;
}
 

int main(){
	while(cin>>m>>n>>A>>B,m|n){
		vector<pair<int,pair<int,int> > > v(n+m),w;
		for(int i=0;i<m;i++){
			cin>>v[i].first>>v[i].second.first>>v[i].second.second;
		}
		for(int i=m;i<m+n;i++){
			v[i].first=r();
			v[i].second.first=r();
			v[i].second.second=r();
		}
		sort(v.begin(),v.end());
		int ans=0;
		Dynamic2DRMQ_BIT rmq2d(2000000);
		int prevx=-1;
		for(int i=0;i<m+n;i++){
			if(prevx<v[i].first){
				for(int j=0;j<w.size();j++)
					rmq2d.insert(w[j].second.first,w[j].second.second, w[j].first);
				w.clear();
				prevx=v[i].first;
			}
			int t=rmq2d.query(v[i].second.first,v[i].second.second)+1;
			ans=max(ans,t);
			w.push_back(make_pair(t,make_pair(v[i].second.first,v[i].second.second) ) );
		}

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

Measured memory_bytes: 92156
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>

#define fo(i,a,b) for(int i=a;i<=b;i++)

typedef long long LL;
	
using namespace std;

LL mi10[20];
LL a[10];
int l;
int cnt;

void dfs(int x,LL d,int c){
	if (x>l){
		if (d==0)cnt+=c;
		return;
	}
	if (d>=1ll*a[x]*10||d<=-1ll*a[x]*10)return;
	fo(i,1,9){
		if (x==1)dfs(x+1,d-1ll*i*a[x],c*(9-i));
		else dfs(x+1,d-1ll*i*a[x],c*(10-i));
	}
	if (x==1)dfs(x+1,d,c*9);
	else dfs(x+1,d,c*10);
	fo(i,-9,-1){
		if (x==1)dfs(x+1,d-1ll*i*a[x],c*(9+i));
		else dfs(x+1,d-1ll*i*a[x],c*(10+i));
	}
}

int main(){
	mi10[0]=1;
	fo(i,1,18)mi10[i]=mi10[i-1]*10;
	int d;
	scanf("%d",&d);
	int ans=0;
	for(int len=2;len<=18;len++){
		for(int i=1;i<=len/2;i++)a[i]=mi10[len-i]-mi10[i-1];
		l=len/2;
		cnt=0;
		dfs(1,d,1);
		if (len&1)cnt=cnt*10;
		ans=ans+cnt;
	}
	printf("%d\n",ans);
	return 0;
}

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

vector<pair<int, bool>> testimony[20];
bool honest[20];
int ans = 0;

void backtrack(int cur, int n){

    if(cur > n){

        bool valid = true;
        int cnt_of_honest = 0;
        
        for(int i = 1; i<=n; i++){

            if(honest[i]){
                cnt_of_honest++;
                for(auto p : testimony[i]){
                    /// p.first -> p.second
                    if(honest[p.first] != p.second){
                        valid = false;
                    }
                }
            }

        }


        if(valid == true){
            /// I have found cnt_of_honest;
            ans = max(ans, cnt_of_honest);
        }



        return;
    }


    honest[cur] = true;
    backtrack(cur+1, n);


    honest[cur] = false;
    backtrack(cur+1, n);
}

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


    int n;
    cin>>n;

    for(int i = 1; i<=n; i++){
        int k;
        cin>>k;
        for(int j = 0; j<k; j++){
            int x, y;
            cin>>x>>y;
            bool z;
            if(y == 1)
                z = true;
            else
                z = false;

            pair<int, bool> p = make_pair(x, z);
            testimony[i].push_back(p);
        }
    }

    backtrack(1, n);


    cout<<ans<<endl;

    return 0;
}



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

int main(){
  stack<int> ss;
  list<pair<int, int> > lm;
  string str;
  cin >> str;
  int ans = 0, count = 0;
  for(int i = 0; str[i] != '\0'; i++){
    char c = str[i];
    if(c == '\\'){
      ss.push(i);
    }else if(c == '/'){
      if(!ss.empty()){
        int si = ss.top(); ss.pop();
        int addi = si;
        int addm = i - si;
        while(!lm.empty()){
          pair<int, int> pl;
          pl = lm.back();
          if(addi < pl.first){
            addm += pl.second;
            ans -= pl.second;
            lm.pop_back();
            count--;
          }else break;
        }
        ans += addm;
        lm.push_back(make_pair(addi, addm));
        count++;
      }
    }
  }
  
  cout << ans << endl;
  cout << count;
  
  for(list<pair<int, int> >::iterator itr = lm.begin(); itr != lm.end(); itr++){
    cout << " " << itr->second;
  }
  
  cout << endl;
  
  return 0;
}


Measured memory_bytes: 3304
#include<stdio.h>
long long int n, k;
long long int next[200005];
long long int f(long long int i)
{
	if (i < next[i])
		return next[i] - i + 1;
	else
		return n + next[i] - i + 1;
}
int main()
{
	scanf("%lld %lld", &n, &k);
	k *= n;
	long long int i;
	long long int a[200005];
	for (i = 0; i < n; i++)
		scanf("%lld", &a[i]);
	long long int c[200005];
	for (i = 0; i < 200005; i++)
		c[i] = -1;
	for (i = 0; i < n; i++)
		next[i] = -1;
	for (i = n - 1; i >= 0; i--)
	{
		if (c[a[i]] >= 0)
			next[i] = c[a[i]];
		c[a[i]] = i;
	}
	for (i = n - 1; i >= 0; i--)
	{
		if (next[i] < 0)
			next[i] = c[a[i]];
		c[a[i]] = i;
	}
	long long int cnt = 0;
	i = 0;
	for (;;)
	{
		cnt += f(i);
		i = (next[i] + 1) % n;
		if (i == 0)
			break;
	}
	k %= cnt;
	i = 0;
	long long int ans[200005], m = 0;
	while (k > 0)
	{
		while (k >= f(i))
		{
			k -= f(i);
			i = (next[i] + 1) % n;
		}
		if (k == 0)
			break;
		ans[m] = a[i];
		m++;
		i = (i + 1) % n;
		k--;
	}
	if (m > 0)
		printf("%lld", ans[0]);
	for (i = 1; i < m; i++)
		printf(" %lld", ans[i]);
	printf("\n");
}

Measured memory_bytes: 7904
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+10,p=1e9+7;
int inc(int x,int y){x+=y;return x>=p?x-p:x;}
int dec(int x,int y){x-=y;return x<0?x+p:x;}
int mul(int x,int y){return (ll)x*y%p;}
int power(int x,int y){
    int ans=1;
    for (;y;y>>=1,x=mul(x,x))
        if (y&1) ans=mul(ans,x);
    return ans;
}
int n,x[N],y[N];
int fac[N],ifac[N];
int C(int n,int m){
    return mul(fac[n],mul(ifac[m],ifac[n-m]));
}
int dp[4010][4010];
int main()
{
    scanf("%d",&n);
    for (int i=1;i<=n;i++){
		scanf("%d%d",&x[i],&y[i]);
		dp[2001-x[i]][2001-y[i]]++;
    }
	for (int i=1;i<=4001;i++)
	for (int j=1;j<=4001;j++)
		dp[i][j]=inc(dp[i][j],inc(dp[i-1][j],dp[i][j-1]));
	fac[0]=1;
    for (int i=1;i<=8000;i++) fac[i]=mul(fac[i-1],i);
    ifac[8000]=power(fac[8000],p-2);
    for (int i=7999;i>=0;i--) ifac[i]=mul(ifac[i+1],i+1);
    int ans=0;
    for (int i=1;i<=n;i++){
		ans=inc(ans,dp[2001+x[i]][2001+y[i]]);
		ans=dec(ans,C((x[i]+y[i])*2,x[i]*2));
	}
    printf("%d\n",mul(ans,(p+1)>>1));
    return 0;
}


Measured memory_bytes: 66176
N = int(input())
A = list(map(int, input().split()))

print(*A)

for i in range(1, len(A)):
    v = A[i]
    j = i - 1
    while j >= 0 and A[j] > v:
        A[j + 1] = A[j]
        j -= 1
    A[j + 1] = v
    print(*A)

Measured memory_bytes: 8000
#include<stdio.h>

static const int MAX = 500;
static const int INFTY = (1<<21);

int main(){
  int n,i,j;
  int M[MAX][MAX];
  int k,c,u,v;
  int minv;
  int D[MAX];
  int vis[MAX];

  scanf("%d", &n);
  for ( i = 0; i< n; i++ ){
    for ( j = 0; j < n; j++ ){
      M[i][j] = INFTY;
    }
  }

  for ( i = 0; i < n; i++ ){
    scanf("%d %d", &u, &k);
    for ( j = 0; j < k; j++ ){
      scanf("%d %d", &v, &c);
      M[u][v] = c;
    }
  }

  for ( i = 0; i < n; i++ ) {
    D[i] = INFTY;
    vis[i] = 0;
  }

  D[0] = 0;

  while(1){
    minv = INFTY;
    u = -1;
    for ( i = 0; i < n; i++ ){
      if ( minv > D[i] && !vis[i] ){
        u = i;
        minv = D[i];
      }
    }
    if ( u == -1 ) break;
    vis[u] = 1;
    for ( v = 0; v < n; v++ ){
      if ( !vis[v] && M[u][v] != INFTY ){
        if ( D[v] > D[u] + M[u][v] ){
          D[v] = D[u] + M[u][v];
        }
      }
    }
  }

  for ( i = 0; i < n; i++ ){
    printf("%d %d\n", i, (D[i]==INFTY?-1:D[i]));
  }

  return 0;
}


Measured memory_bytes: 2060
#!/usr/bin/env python3
import sys


def solve(X: int, K: int, D: int):
    st = abs(X) - K*D    
    if abs(X) >= K*D:
        print(st)
    elif abs(X) < K*D:
        st = K*D - abs(X)
        p = st // (2*D)
        pp = st - (2*D)*p
        print(min(pp, abs(pp-(2*D))))

    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    X = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    D = int(next(tokens))  # type: int
    solve(X, K, D)

if __name__ == '__main__':
    main()


Measured memory_bytes: 9204
n = int(input())
p_list = list(map(int,input().split()))

ans = 0
for i in range(n-2):
    Max = max(p_list[i], p_list[i+1], p_list[i+2])
    Min = min(p_list[i], p_list[i+1], p_list[i+2])
    Middle = p_list[i] + p_list[i+1] + p_list[i+2] - Max - Min
    if(p_list[i+1] == Middle):
        ans += 1
print(ans)




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

#ifdef LOCAL
#include "dump.hpp"
#else
#define dump(...)
#define dumpv(...)
#endif

#define rep(i, n) for (int i = 0; i < (n); i++)
#define mins(x, y) (x = min(x, y))
#define maxs(x, y) (x = max(x, y))
typedef long long ll;
typedef pair<int, int> P;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
const int MOD = 1e9 + 7;
const int INF = 1001001001;
const ll LINF = 1001002003004005006ll;

void solve() {
  ll n, k, s;
  cin >> n >> k >> s;
  rep(i, n) {
    if (i < k) {
      cout << s << " ";
    } else {
      if (s == 1000000000)
        cout << s - 1 << " ";
      else
        cout << 1000000000 << " ";
    }
  }
  cout << endl;
}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(15);
  // freopen("temp.1", "r", stdin);
  solve();
  return 0;
}

Measured memory_bytes: 1280