akhauriyash/Code-Regression huggingface dataset:
def swap(array, n1, n2)
  tmp = array[n2]
  array[n2] = array[n1]
  array[n1] = tmp
end

def bubble_sort(array)
  count = 0
  for i1 in 0...array.size do
    for i2 in i1...array.size-1 do
      index = array.size - 1 - i2 + i1
      if (array[index] < array[index-1]) then
        swap(array, index, index-1)
        count += 1
      end
    end
  end
  return count
end

n = gets.strip.to_i
array = gets.split(' ').map(&:to_i)
swap_count = bubble_sort(array)
puts array.join(' ')
puts swap_count

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

using namespace std;

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

    vector<string> A(N), B(N);
    for(int i = 0; i < N; i++){
        cin >> A.at(i) >> B.at(i);
    }

    int a = 0, b = 0;
    for(int i = 0; i < N; i++){
        if(A.at(i) == B.at(i)){
            a++;
            b++;
        }else if(A.at(i) > B.at(i)){
            a += 3;
        }else{
            b += 3;
        }
    }
    cout << a << " " << b << endl;
}


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

#define INF INT_MAX/2;
#define MOD 1000000007

using namespace std;

using ll = long long;
using ull = unsigned long long ;

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

   ll N,Z,W;
   cin>>N>>Z>>W;
   vector<ll>a(N);
   for(int i=0;i<N;i++)cin>>a[i];
   if(N==1)cout<<abs(a[N-1]-W);
   else cout<<max(abs(a[N-2]-a[N-1]),abs(a[N-1]-W));
   return 0; 
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ar array
#define endl '\n'
#define ll long long
#define in insert
#define pb push_back
#define vt vector
#define P_Q(x) priority_queue<x>
#define p_q(x) priority_queue<x, vector<x>, greater<x>>
#define Rep(i,a,b) for(int i=a;i<=b;i++)
#define Rev(i,a,b) for(ll i=a;i>=b;i--)
#define FOR(m) Rep(i,1,m)
#define For(m) Rep(i,0,m-1)
#define Rbl(x,a) for(auto &x : a)
#define FIO ios::sync_with_stdio(0);   cin.tie(0);
#define F first
#define S second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define mp make_pair
#define vpii vector<pii>
#define vpll vector<pll>
#define all(x) (x).begin(),(x).end()
#define sz(x) (int) (x).size()
const ll INF = 0x3f3f3f3f3f3f3f3fll;
#define mod 1000000007
 
const int mxN = 1e5 + 1;
ll a[mxN], dp[mxN] = {};
ll n;
 
 
int main()
{
FIO
 
    cin >> n;
    FOR(n) cin >> a[i];
    dp[2] = abs(a[2] - a[1]); 
    Rep(i,3,n)
    {
        dp[i] = min( dp[i-1] + abs(a[i] - a[i-1]), dp[i-2] + abs(a[i] - a[i-2]) );
    }
    cout << dp[n] << endl;
}

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

#define int long long int
#define ff first
#define ss second
#define pb push_back
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int mod = 1e9 + 7;
const int cmod = 998244353;
const int N = 3e5 + 5;
const int inf = 1e18 + 2;


void solve(int Case) {
    int n ;
    cin >> n;
    int ans = 0;
    for(int  i = 1 ; i <= n ; i ++) ans += (n - 1) / i ;
    cout << ans << '\n';
}
/*
 */

int32_t main()
{
    fastio
    int testcase = 1;
    //cin >> testcase;
    int Case = 1;
    while(testcase --) {
        solve(Case);
    }
    return 0;
}


Measured memory_bytes: 3652
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  vector<int> data(5);
  for (int i=0; i < 5; i++) cin >> data.at(i);
  int smallest = data.at(0);
  int smallestindex = 0;
  int answer = 0;
  for (int i=1; i < 5; i++) {
    if (data.at(i)%10 < smallest%10 && data.at(i)%10 != 0) {
      smallest = data.at(i);
      smallestindex = i;
    }
  }
  answer += data.at(smallestindex);
  for (int i=0; i < 5; i++) {
    data.at(i) = (data.at(i) + 9) / 10;
    data.at(i) *= 10;
  }
  for (int i=0; i < 5; i++) {
    answer += data.at(i);
  }
  answer -= data.at(smallestindex);
  cout << answer << endl;
}



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

using namespace std;
using ll = long long;

void _cin(){} template <class Head, class... Tail> void _cin(Head&& head, Tail&&... tail){ cin >> head; _cin(forward<Tail>(tail)...); }
void _cout(){ cout << "\n"; } template <class Head, class... Tail> void _cout(Head&& head, Tail&&... tail){ cout << head; _cout(forward<Tail>(tail)...); }
int gcd(int a, int b){ return (b == 0) ? a : gcd(b, a % b); }

#define Sq(x) (x)*(x)
#define For(i, n) for(int i = 0; i < (n); i ++)
#define Rep(n) For(_, n)
#define Range(c) c.begin(), c.end()
#define RevRange(c) c.rbegin(), c.rend()
#define Contains(c, x) (find(Range(c), x) != c.end())
#define Search(rb, re, x) distance(rb, find(rb, re, x))
#define Sort(a) sort(Range(a))
#define DeSort(a) sort(RevRange(a))
#define Reverse(c) reverse(Range(c))
#define Unique(a) a.erase(unique(Range(a)), a.end())
#define Cusum(T, xs, sxs) vector<T> sxs(xs.size()+1); For(i, (int)xs.size()) sxs[i+1] = sxs[i] + xs[i]
#define Cin(T, ...) T __VA_ARGS__; _cin(__VA_ARGS__)
#define Cins(T, n, xs) vector<T> xs(n); For(i, n) cin >> xs[i]
#define Cins2(T, n, xs, ys) vector<T> xs(n), ys(n); For(i, n) cin >> xs[i] >> ys[i]
#define Cins3(T, n, xs, ys, zs) vector<T> xs(n), ys(n), zs(n); For(i, n) cin >> xs[i] >> ys[i] >> zs[i]
#define Cinss(T, n, m, xs) Vec2(T, n, m, xs); For(i, n) For(j, m) cin >> xs[i][j]
#define Cinm(T, n, map) unordered_map<T, int> map; Rep(n){ Cin(T, x); map[x] ++; }
#define Cout(...) _cout(__VA_ARGS__)
#define Couts(xs) { for(const auto &e : xs) cout << e << " "; cout << "\n"; }
#define Coutyn(cond) Cout((cond) ? "yes" : "no")
#define CoutYn(cond) Cout((cond) ? "Yes" : "No")
#define CoutYN(cond) Cout((cond) ? "YES" : "NO")
#define vc vector
#define Mini(a, x) a = min(a, x)
#define Maxi(a, x) a = max(a, x)

constexpr int MOD = 1e9+7;

int main(void){
    Cin(int, n, k);
    Cins(int, n, a);
    
    vc<int> m(2001);
    For(i, n) m[a[i]] ++;
    Cusum(ll, m, sm);

    ll ans = 0;
    For(i, n){
        ll c = 0;
        for(int j = i+1; j < n; j ++){
            if(a[i] > a[j]) c ++;
        }
        c = c * k % MOD;
        c = (c + (ll)k*(k-1)/2 % MOD * sm[a[i]] % MOD) % MOD;
        ans = (ans + c) % MOD;
    }
    Cout(ans);
}




Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define all(v) v.begin(), v.end()
typedef long long ll;
typedef pair<ll,ll> P;
typedef vector<ll> vec;
typedef vector<vec> mat;
int f(ll b,ll n){
    if(n<b) return n;
    else return f(b,n/b)+n%b;
}
int main(){
    ll n,s;
    cin>>n>>s;
    for(ll i=2;i<=sqrt(n);i++)if(f(i,n)==s){
        cout<<i<<"\n";
        return 0;
    }
    for(ll i=sqrt(n);i>=1;i--){
        if(n/i==1) continue;
        ll a=f(n/i,n);
        if(a%i==s%i&&0<=(s-a)/i&&(s-a)/i<n/i-n/(i+1)){cout<<n/i-(s-a)/i<<"\n";return 0;}
    }
    if(n==s){
        cout<<n+1<<"\n";
        return 0;
    }
    cout<<-1<<"\n";
}

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

typedef long long ll;

typedef pair<int, int> pii;
typedef pair<ll,ll> pll;

typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pii> vpii;
typedef vector<pll> vpll;

#define FOR(i, a, b) for (ll i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (ll i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)

#define ALL(s) (s).begin(),(s).end()
#define ALLn(s,n) s,s+n
#define F first
#define S second
#define pb push_back
#define tc(t) int t; cin >> t; while(t--)
#define _ ios_base::sync_with_stdio(false); cin.tie(NULL);

const ll MOD = 1e9 + 7;
const ll MAXN = 1e6 + 7;
const ll INF = INT_MAX;

void solve() {
	ll a,b,n;
	cin >>a >> b >> n;

	ll ans = 0;
	
	//FORd(i, 1, n+1) {
		////cout << i << " " << (a * i)/b + a * (i/b) << "\n";
		//if(ans < floor(a*((1.0 * i)/b)) + a * (i/b)){
			//ans = floor(a*((1.0 * i)/b)) + a * (i/b);
	
		//}
		//else if(floor(a*((1.0 * i)/b)) + a * (i/b)){
			//break;
		//}
	//}
	ll x = min(n,b-1);
	cout << fixed << (ll)(floor(a*((1.0 * x)/b)) + a * (x/b)) <<  "\n";
	
}

int32_t main() {_
	//tc(t)
		solve();
}



Measured memory_bytes: 3612
#include<iostream>
#include<stdio.h>
//#include <bits/stdc++.h>
#include<vector>
#include<float.h>
#include<iomanip>
#include<algorithm>
#include<string>
#include<cstring>
#include<math.h>
#include<cmath>
#include<sstream>
#include<set>
#include<map>
#include<queue>
#include <cassert>
#include <cmath>
#include<cstdint>

#define INF 1e9
#define rep(i,n)for(int i=0;(i)<(int)(n);i++)
#define REP(i,a,b)for(int i=(int)(a);(i)<=(int)(b);i++)
#define VEC(type, c, n) std::vector<type> c(n);for(auto& i:c)std::cin>>i;
#define vec(type,n) vector<type>(n)
#define vvec(m,n) vector<vector<int>> (int(m),vector<int>(n))
#define ALL(a)  (a).begin(),(a).end()

using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
using P = pair<int,int>;

vector<int>bitSearch(int bit,int n){
    vector<int>S;
    rep(i,n)if(bit&(1<<i))S.push_back(i);
    return S;
}



int main(){
    int n,m,X,Y;cin>>n>>m>>X>>Y;
    VEC(int,x,n);sort(ALL(x));
    VEC(int,y,m);sort(ALL(y));
    int yy = min(y[0],Y);
    int xx = max(x[n-1],X);
    if(yy-xx>0)cout<<"No War";
    else cout<<"War";
}



Measured memory_bytes: 256
S = input()

left = int(S[:2])
right = int(S[2:])
left_mm_flag = False
left_yy_flag = False
right_mm_flag = False
right_yy_flag = False

if 0 <= left <= 99:
    left_yy_flag = True
    if 1 <= left <= 12:
        left_mm_flag = True


if 0 <= right <= 99:
    right_yy_flag = True
    if 1 <= right <= 12:
        right_mm_flag = True


if left_mm_flag and right_yy_flag and left_yy_flag and right_mm_flag:
    print('AMBIGUOUS')
elif left_yy_flag and right_mm_flag:
    print('YYMM')
elif left_mm_flag and right_yy_flag:
    print('MMYY')
else:
    print('NA')


Measured memory_bytes: 3064
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<bitset>
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<deque>
#include<list>
#include<iomanip>
#include<cmath>
#include<cstring>
#include<functional>
using namespace std;

#define repr(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define rep(i, n) repr(i, 0, n)
#define INF 2e9
#define MOD 1000000007
//#define MOD 998244353
#define LINF (long long)4e18
#define jck 3.141592

using ll = long long;
using Pi = pair<int,int>;
using Pl = pair<ll,ll>;

ll COM[1010][1010];
 
void init(){
	rep(i,1010)rep(j,1010) COM[i][j] = 0;
	COM[0][0] = 1;
	repr(i,1,1010){
		COM[i][0] = 1;
		repr(j,1,1010){
			COM[i][j] = COM[i-1][j-1] + COM[i-1][j];
		}
	}
}


int main(){
    init();
    int N,A,B; cin >> N >> A >> B;
    vector<ll> v(N);
    rep(i,N) cin >> v[i];
    sort(v.begin(),v.end(),greater<ll>());
    ll sum = 0;
    bool same = true;
    ll last = 0;
    rep(i,A){
        sum += v[i];
        if(i >= 1){
            if(v[i] != v[i-1] ) same = false;
        }
        last = v[i];
    }
    double average = (double)sum/A;
    cout << fixed << setprecision(7) << average << endl;

    if(!same){
        int cnt1 = 0;
        int cnt2 = 0;
        rep(i,N){
            if(i < A && v[i] == last) cnt1++;
            if(v[i] == last) cnt2++;
        }
        ll ans = COM[cnt2][cnt1];
        cout << ans << endl;
    }
    else{
        int cnt = 0;
        rep(i,N){
            if(v[i] == last) cnt++;
        }
        ll ans = 0;
        repr(i,A,B+1){
            ans += COM[cnt][i];
        }
        cout << ans << endl;
    }

}



Measured memory_bytes: 8192
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7
#import numpy as np
#from decimal import *

N = INT()

ans = 0
for i in range(1, N+1):
	k = N//i
	ans += i * k*(k+1)//2

print(ans)

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

#ifdef _PRINTDEBUG
  #include "lib/printdebug.hpp"
#else
  #define printdebug(...) 1
#endif
#define MOD_1_000_000_007 (1000000007)
#define IINF (1<<28)
#define LINF (1LL<<60)
#define rep(i, n)      REP(i, 0, (n))
#define repc(i, n)     REPC(i, 0, (n))
#define REP(i, n, m)   for (int i = (int)(n); i <  (int)(m); i++)
#define REPC(i, n, m)  for (int i = (int)(n); i <= (int)(m); i++)
#define REPCM(i, n, m) for (int i = (int)(n); i >= (int)(m); i--)
#define yesno(cond)       YESNO((cond), "Yes", "No")
#define YESNO(cond, a, b) cout << ((cond) ? (a) : (b)) << "\n"

namespace solver {
  using namespace std;
  typedef long long ll;

  int N, ans;

  void init() {
    cin >> N;
  }

  void rec(int n, int d, int three, int five, int seven, int last) {
    if(d > 8 || last == 0) {
      if (three && five && seven && 1 <= n && n <= N) {
        ans++;
      }
      return;
    }
    rec(n + 0 * pow(10, d), d+1, three+0, five+0, seven+0, 0);
    rec(n + 3 * pow(10, d), d+1, three+1, five+0, seven+0, 3);
    rec(n + 5 * pow(10, d), d+1, three+0, five+1, seven+0, 5);
    rec(n + 7 * pow(10, d), d+1, three+0, five+0, seven+1, 7);
  }

  void solve() {
    rec(0, 0, 0, 0, 0, -1);
    cout << ans << "\n";
  }
}

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(0);
  solver::init();
  solver::solve();
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <limits>

using namespace std;

#define FOR(i, n) for(int i = 0; i < (int) n; i++)
#define all(v) v.begin(), v.end()
#define F first
#define S second


typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;

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

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

	string s, t; cin >> s >> t;

	vector<vi> dp(s.size()+1, vi(t.size()+1));

	FOR(i, s.size()+1){
		FOR(j, t.size()+1){
			if(i == 0 || j == 0) dp[i][j] = 0;
			else if(s[i-1] == t[j-1]) dp[i][j] = dp[i-1][j-1]+1;
			else dp[i][j] = max(dp[i][j-1], dp[i-1][j]);
		}
	}

	string ans = "";
	int a = s.size(), b = t.size();
	while(dp[a][b]){
		if(dp[a-1][b] == dp[a][b])
			a--;
		else if(dp[a][b-1] == dp[a][b])
			b--;
		else{
			ans.push_back(t[b-1]);
			b--; a--;
		}
	}

	reverse(all(ans));
	
	cout << ans << '\n';

	return 0;
}

Measured memory_bytes: 35584
//  Friendly NUKE is ready!!
#include <bits/stdc++.h>
#define SPEED ios::sync_with_stdio(false); cin.tie(0)
#define loop(i,a,b) for(int i=a;i<b;i++)
#define ll long long
#define vi vector<int>
#define vl vector<ll>
#define pii pair<int,int>
#define pll pair<long long int,long long int>
#define dbg(x) cout<<#x<<": "<<x<<endl
#define ff first
#define ss second
#define mp make_pair
#define pb push_back
#define mo 1000000007
#define inf 1e18
#define eps 0.0000000001
#define stp setprecision(20)
#define all(v) v.begin(),v.end()
#define endl '\n'
using namespace std;
//mt19937 rng32(chrono::steady_clock::now().time_since_epoch().count());
 
#define N  int(2e5)+10
ll h[N] , dp[N] ;
int main()
{    SPEED;
      int n;
      cin>>n;
      loop(i,1,n+1)cin>>h[i] ;
      dp[1] =0;dp[2] = abs(h[1]-h[2]) ;
      loop(i,3,n+1){
      	 dp[i] = min(dp[i-2]+abs(h[i]-h[i-2]),dp[i-1]+abs(h[i]-h[i-1])) ;
      }      
      cout<<dp[n] ;
}

Measured memory_bytes: 5092
#include<cstdio>
#include<utility>
using namespace std;

int n;
int A[114514];

int partition() {
	int i,part = 0;
	int r = A[n-1];
	for (i = 0; i < n - 1; i++) {
		if (A[i] <= r) {
			swap(A[i], A[part]);
			part++;
		}
	}
	swap(A[part],A[n-1]);
	return part;
}

int main() {
	int i;
	scanf("%d",&n);
	for (i = 0; i < n; i++) {
		scanf("%d", &A[i]);
	}
	int x = partition();
	for (i = 0; i < n; i++) {
		if (i)printf(" ");
		if (i == x) printf("[%d]",A[i]);
		else printf("%d", A[i]);
	}
	printf("\n");
	return 0;
}


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

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

    int n;
    cin >> n;
    vector<int> p(n);
    vector<bool> is_idx(n, false);
    rep(i, n) {
        int p;
        cin >> p;
        --p;
        if(i==p){
            is_idx[i] = true;
        }
    }

    int res = 0;
    int cnt = 0;
    rep(i, n){
        if(is_idx[i]) ++cnt;
        else{
            if(cnt){
                res += (cnt+1) / 2;
                cnt = 0;
            }
        }
    }
    if(cnt) res += (cnt+1) / 2;
    cout << res << endl;
}

Measured memory_bytes: 640
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<math.h>
#include<complex>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<functional>
#include<assert.h>
#include<numeric>
using namespace std;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
using ll = long long;
const int inf=1e9+7;
const ll longinf=1LL<<60 ;
const ll mod=1e9+7 ;

int main(){
    int n;
    cin>>n;
    rep(i,10)rep(j,10){
        if(i*j==n){
            cout<<"Yes"<<endl;
            return 0;
        }
    }
    cout<<"No"<<endl;
    return 0;
}

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

const double pi = 3.14159265358979;

int main(void){
	int n;
	
 	while (cin >> n, n != -1){
		double x = 0.0, y = 0.0, angle = 0.0;
		for(int i = 0; i < n; i++){
			x += cos(angle);
			y += sin(angle);
			angle = atan2(y , x) + pi / 2.0;
		}
		cout << x << endl << y << endl;
	}
	
	return 0;
}

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

// ABC129B - Balance
// https://atcoder.jp/contests/abc129/tasks/abc129_b
void ABC129B() {


	int N;
	cin >> N;

	vector<int> W(N);
	int W_sum = 0;
	for (int i = 0; i < N; i++)
	{
		cin >> W[i];
		W_sum += W[i]; //重さの合計を出しておく
	}

	
	int ans = INT_MAX; //答え
	for (int t = 0; t < N; t++)
	{
		//S1の重さを計算
		int S1 = 0;
		for (int i = 0; i <= t; i++) {
			S1 += W[i];
		}
		//S2の重さは、重さの合計からS1の重さを引いたもの
		int S2 = W_sum - S1;

		//差の絶対値の最小を更新
		if (abs(S1 - S2) < ans) {
			ans = abs(S1 - S2);
		}
	}

	cout << ans << endl;
}

int main() {
	ABC129B();

	return 0;
}



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

struct st{
  int a,num;
};

int compare_int(const void *a,const void *b){
  struct st A= *(struct st*)a,B= *(struct st*)b;
  return A.a-B.a;
}

int main(){
  int n,i;
  struct st a[100001];
  scanf("%d",&n);
  for(i=0;i<n;i++)scanf("%d",&a[i].a),a[i].num=i+1;
  qsort(a,n,sizeof(a[0]),compare_int);
  for(i=0;i<n;i++)printf("%d ",a[i].num);
  return 0;
}


Measured memory_bytes: 1788
def main():
     import heapq
     import sys
     input=sys.stdin.readline

     ans=0
     N,M=map(int,input().split())
     Ar=[]
     for _ in range(M):
           Ar.append([])
     for _ in range(N):
          A,B=map(int,input().split())
          if A <= M:
              Ar[A-1].append(-B)
     An=[]
     for i in range(M):
          for j in Ar[i]:
              heapq.heappush(An,j)
          if len(An)>0:
              ans+=-heapq.heappop(An)
     print(ans)

if __name__ =='__main__':
    main()

Measured memory_bytes: 64816
D = {}
N = int(input())
for i in range(N):
  s = input()
  if not(s in D):
    D[s] = 0
  D[s] += 1
M = int(input())
for i in range(M):
  t = input()
  if not(t in D):
    D[t] = 0
  D[t] -= 1
r = max(0, max(D.values()))
print(r)


Measured memory_bytes: 3064
weather = list(input())

i = 0
j = 0
days = 0
consecutive = []

while i <= 2:
    while i + j <= 2:
        if weather[i+j] == "R":
            days += 1
            j += 1
        else:
            break
    i += 1
    j = 0
    consecutive.append(days)
    days = 0

print(max(consecutive))


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

using namespace std;

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

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



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

	cin >> H >> W;
	vector<string>s(H);
	for (auto &i : s)cin >> i;
	auto r = s;
	auto b = s;
	for (int i = 0; i < H; i++) {
		r[i][0] = '#';
		b[i][W - 1] = '#';
		for (int j = 1; j < W - 1; j++) {
			if (i & 1)r[i][j] = '#';
			else b[i][j] = '#';
		}
	}
	for (auto i : r)cout << i << endl;
	cout << endl;
	for (auto i : b)cout << i << endl;
}


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

#define DUMP(x) cerr << #x << "=" << x << endl
#define DUMP2(x, y) cerr<<"("<<#x<<", "<<#y<<") = ("<<x<<", "<<y<<")"<< endl
#define BINARY(x) static_cast<bitset<16> >(x)

#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define REP(i,m,n) for (int i=m;i<(int)(n);i++)

#define in_range(x, y, w, h) (0<=(int)(x) && (int)(x)<(int)(w) && 0<=(int)(y) && (int)(y)<(int)(h))
#define ALL(a) (a).begin(),(a).end()

typedef long long ll;
const int INF   = 1e9;
const ll  INFLL = 1e18;
typedef pair<int, int> PII;
int dx[4]={0, -1, 1, 0}, dy[4]={-1, 0, 0, 1};

int main()
{
    ios::sync_with_stdio(false);
    int N; cin >> N;
    vector<ll> A(N);
    rep(i, N) cin >> A[i];
    ll sum1 = A[0], sum2 = 0;
    REP(i, 1, N) sum2 += A[i];

    ll ans = llabs(sum1 - sum2);
    for (int i=1; i<N-1; i++) {
        sum1 += A[i];
        sum2 -= A[i];
        ans = min(ans, llabs(sum1 - sum2));
    }

    cout << ans << endl;
}

Measured memory_bytes: 1792
#include <iostream>
#include <stdio.h>
#include <vector>
#include <functional>
#include <unordered_set>
#include <algorithm>
#include <set>
#include <map>
#include <cmath>
#include <string>
#include <cstring>
#include <ctime>
#include <cassert>
#include <queue>
#include <stack>
#include <bitset>

using namespace std;

const int N = 1e5 + 1;

bool was[N];
vector <int> G[N];
int dp[N];

vector<int> ans;
void dfs(int n) {
	if (was[n]) return;
	was[n] = true;
	for (auto x : G[n]) {
		dfs(x);
	}
	ans.push_back(n);
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n, m;
	cin >> n >> m;
	for (int i = 0; i < m; ++i) {
		int a, b;
		cin >> a >> b;
		--a;
		--b;
		G[a].push_back(b);
	}
	fill(was, was + n, 0);
	for (int i = 0; i < n; ++i) {
		dfs(i);
	}
	reverse(ans.begin(), ans.end());
	for (auto x : ans) {
		for (auto y : G[x]) {
			dp[y] = max(dp[y], dp[x] + 1);
		}
	}
	cout << *max_element(dp, dp + n) << endl;
	return 0;
}

Measured memory_bytes: 8824
#include <iostream>
#include <fstream>
#include <utility>
#include <vector>
#include <algorithm>

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

typedef long long ll;

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

    vector<int> d(n);

    REP(i, n)
    {
        cin >> d[i];
    }

    int sum = 0;
    for (int i = 0; i < n; ++i)
    {
        for (int j = i + 1; j < n; ++j)
        {
            if (j == i)
                continue;
            sum += d[i] * d[j];
        }
    }
    cout << sum;
    return 0;
}

Measured memory_bytes: 256
//
#include <vector>
#include <set>
#include <array>
#include <iostream>
#include <cstdio>
#include <cstdint>
//
using ll = long long;
using namespace std;
#define rep(i,n) for(int i=0;i<(n);++i)
void yes(bool cond) { cond ? puts("Yes") : puts("No"); }
//
int main()
{
    cin.tie(0); ios::sync_with_stdio(false);
    std::string S;
    cin >> S;
    yes(!((S[0] == S[1]) && (S[1] == S[2])));
}

Measured memory_bytes: 2992
//package atcoderdp;
import java.util.*;
class Main {
    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        int n = s.nextInt();
        int k = s.nextInt();
        int a[] = new int[n];
        for (int i = 0; i <n ; i++) {
            a[i] = s.nextInt();
        }
        System.out.println(find(a,n,k));
    }
    public static int find(int a[],int n,int k){
        int dp[] = new int [n];
        Arrays.fill(dp,Integer.MAX_VALUE);
        dp[0]=0;
        dp[1]=Math.abs(a[0]-a[1]);
        for(int i=2;i<n;i++){
            int min = Integer.MAX_VALUE;
            for(int j=1;j<=Math.min(k,i);j++){
                min = Math.min(min,dp[i-j]+Math.abs(a[i]-a[i-j]));
            }
            dp[i] = min;
        }
      //  System.out.println(Arrays.toString(dp));
        return dp[n-1];
    }
}


Measured memory_bytes: 59576
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <climits>
#include <random>
#include <iomanip>

using namespace std;
using P = pair<long, long>;

typedef long long int ll;

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))

#define fillInt(xs, x)        \
  for (int i = 0; i < (x); i++) \
    scanf("%d", &xs[i]);
#define fillLong(xs, x)       \
  for (int i = 0; i < (x); i++) \
    scanf("%ld", &xs[i]);
#define fillString(xs, x)       \
  for (int i = 0; i < (x); i++) \
    cin >> xs[i];
#define sortv(xs) sort(xs.begin(), xs.end())
#define sortvinv(xs) sort(xs.begin(), xs.end(), std::greater<long>())
#define lbv(xs, x) lower_bound(xs.begin(), xs.end(), x) - xs.begin()
#define ubv(xs, x) upper_bound(xs.begin(), xs.end(), x) - xs.begin()
#define bs(xs, x) binary_search(xs.begin(), xs.end(), x)
#define index_of(as, x) \
  distance(as.begin(), lower_bound(as.begin(), as.end(), x))

#define rep(i,n) for(auto i=0; i<(n); i++)

const int mod = 1000000007;

int ballCnt[200005];
bool canRed[200005];

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

  int n, m;
  cin >> n >> m;

  canRed[1] = true;
  rep(i, n) {
    ballCnt[i+1] = 1;
  }

  rep(i,m) {
    int a, b;
    cin >> a >> b;

    if (canRed[a]) {
      canRed[b] = true;
    }
    ballCnt[a]--;
    ballCnt[b]++;
    if(ballCnt[a] == 0) {
      canRed[a] = false;
    }
  }

  int cnt = 0;
  rep(i, n) {
    if(canRed[i+1]) cnt++;
  }

  cout << cnt << endl;
}


Measured memory_bytes: 768
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

a,b = inpl()
if a>0 and b>0:
    res = 1
elif a*b<=0:
    res = 0
else:
    if abs(a-b)%2:
        res = 1
    else:
        res = -1
if res == 1:
    print('Positive')
elif res == 0:
    print('Zero')
else:
    print('Negative')

Measured memory_bytes: 5076
#include <bits/stdc++.h>
using namespace std;
int n,used[10][10][4],mp[10][10];

void saiki(int x,int y,int d,int cnt){
  int dx[]={0,1,-1,1},dy[]={1,-1,1,0};

  if(used[y][x][d])return;
  used[y][x][d]=1;
  mp[y][x]=min(mp[y][x],cnt);

  int nx=x+dx[d],ny=y+dy[d];
  if(d==0){ 
    if(ny<n)saiki(nx,ny,x==0?1:2,cnt+1); 
    else saiki(x,y,3,cnt);
  }
  if(d==1){ 
    if(nx==n) saiki(x,y,0,cnt);
    else if(ny<0)saiki(x,y,3,cnt);
    else  saiki(nx,ny,1,cnt+1);
  }
  if(d==2){
    if(ny>=n)saiki(x,y,3,cnt);
    else if(nx<0) saiki(x,y,0,cnt);
    else saiki(nx,ny,2,cnt+1);
  }
  if(d==3){
    if(nx>=n) saiki(x,y,0,cnt);
    else saiki(nx,ny,ny==0? 2:1,cnt+1);
  }
}

int main(){
  int cnt=0;
  while(cin>>n,n){ 
    cnt++;
    memset(used,0,sizeof(used));
    for(int i=0;i<10;i++)for(int j=0;j<10;j++)mp[i][j]=1000;
    saiki(0,0,3,1);
    cout <<"Case "<<cnt<<":"<<endl;
    for(int i=0;i<n;i++){
      for(int j=0;j<n;j++)printf("%3d",mp[i][j]);
      cout <<endl;
    }
  }
    return 0;
}

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

#define rep(i,n) for(int i=0;i<(n);i++)

using namespace std;

int main(){
	int n,q; scanf("%d%d",&n,&q);
	rep(_,q){
		int u,v; scanf("%d%d",&u,&v); u--; v--;

		if(n==1){
			printf("%d\n",min(u,v)+1);
			continue;
		}

		while(u!=v){
			if(u>v) u=(u-1)/n;
			else    v=(v-1)/n;
		}
		printf("%d\n",u+1);
	}

	return 0;
}


Measured memory_bytes: 1280
#include"bits/stdc++.h"
#include <ext/pb_ds/assoc_container.hpp> 
using namespace __gnu_pbds; 
using namespace std;

#define double long double
#define int long long
#define pb push_back 
#define Z(c) (int)(c).size()
#define L(c) c[Z(c)-1]
#define F first
#define S second
#define nl "\n"
#define mii map<int,int> 
#define all(c) (c).begin(),(c).end()
#define rall(c) (c).rbegin(),(c).rend()
#define rep(i,iv,n) for(int (i)=(iv);(i)<(n);++(i))
#define FO fflush(stdout) 
#define D1(x) cerr <<"At line "<<__LINE__<<" "<<#x<<"="<<x<<nl
#define D2(x,y) cerr <<"At line "<<__LINE__<<" "<<#x<<"="<<x<<" "<<#y<<"="<<y<<nl
#define D3(x,y,z) cerr <<"At line "<<__LINE__<<" "<<#x<<"="<<x<<" "<<#y<<"="<<y<<" "<<#z<<"="<<z<<nl
#define tr(it,ct) for(auto &(it) : (ct))
#define pi acos(-1)
#define prt(ct) for(auto &(it) : (ct)) cerr<<it<<" "; cerr<<nl
#define prtp(ct) for(auto &(it) : (ct)) cerr<<it.F<<" "<<it.S<<nl; cerr<<nl

typedef vector< int > vi;
typedef vector< vi > vvi;
typedef pair< int,int > pii;
typedef vector< pii > vp;
typedef tree<int, null_type, less<int>, rb_tree_tag, 
             tree_order_statistics_node_update> baap;

void swap(char &a,char &b)
{ auto tm=a; a=b; b=tm; }

void mina(int &a,int b)
{ a=(a<b?a:b); }

void maxa(int &a,int b)
{ a=(a>b?a:b); }

  const int mod=1000000007;
  const int mod2=998244353;
  const int INF=1e16+18;
  const int N=1e5+15;
  const int M=1e3+13;

  int dp[M][M];

 void fft()              
 {
   int n,m; cin>>n>>m;
   string s[n]; rep(i,0,n) cin>>s[i];

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

     for(int j=0;j<m;++j)
      {
         if(i==0&&j==0) dp[i][j]=1;
         else if(s[i][j]=='#') dp[i][j]=0;
         else {
            if(i-1>=0) dp[i][j]=dp[i-1][j];
            if(j-1>=0) dp[i][j]+=dp[i][j-1];
            dp[i][j]%=mod;
         }
      }
   }

   cout<<dp[n-1][m-1];

 }

signed main()
{ 
   ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
   int tc=1;                         
 //  cin>>tc;

  rep(i,1,tc+1)
  { // cout<<"Case #"<<i<<": ";
   fft();
   if(i<tc)
   cout<<nl;
  }
  
 return 0; 
}

Measured memory_bytes: 9216
n,a,b=map(int,input().split())

ans=0

for i in range(n+1):
    str_n=str(i)
    sum_n=0
    
    for j in range(len(str_n)):
        sum_n += int(str_n[j])
    if sum_n>=a and sum_n<=b:
        ans+=i
            
print(ans)

Measured memory_bytes: 3060
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
#define mod ((int)1e9+7)
#define lim 1000000000000000007
#define lim1 18446744073709551615  //Unsigned
#define sq(a) ((a)*(a))
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define mms(v,i) memset(v,i,sizeof(v))
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define REP(i,a,b) for (int i = a; i <= b; i++)
#define REPN(i,a,b) for (int i = a; i >= b; i--)
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef pair<int,int> pi;
typedef pair<ll,ll> PL;
typedef pair<ll,int> PLI;
typedef pair<int,ll> PIL;
typedef pair<int,pair<int,int> > pii;
typedef pair<double,double> pdd;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> indexed_set;
ll power(ll a,ll b) {
   ll res=1;
   while(b){
      if(b%2==1) res=(res*a)%mod;
      a=(a*a)%mod;
      b>>=1;
   }
   return res;
}
ll gcdll(ll a,ll b) {
    if (b==0) return a;
    return gcdll(b,a%b);
}
int gcd(int a,int b) {
    if (b==0) return a;
    return gcd(b,a%b);
}

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

const int N = (int)1e5+5;
const int M = (int)1e3+5;
const int Q = 301;
const int logN = 19;

int dp[101][N], p[N];
void solve() {
    int n,k,a;
    cin>>n>>k;
    dp[0][k] = p[k+1] = 1;
    REP(i,1,n) {
        cin>>a;
        REP(r,0,k) {
            dp[i][r] = (p[r+min(a,k-r)+1]-p[r]);
            if(dp[i][r]<0) dp[i][r] += mod;
        }
        p[0] = 0;
        REP(r,0,k) {
            p[r+1] = (p[r] + dp[i][r]);
            if(p[r+1]>0) p[r+1] -= mod;
        }
    }
    cout<<dp[n][0];
}
int main() {
    //freopen("output.txt","r",stdin);
    //freopen("output.txt","w",stdout);

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

    int T=1;
    //cin>>T;
    REP(TC,1,T) {
        //cout<<"Case #"<<TC<<": ";
        solve();
        cout<<"\n";
    }
}


Measured memory_bytes: 39680
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);i++)
#define ll long long
using namespace std;
int main(){
  string s,ans;
  cin>>s;
  rep(i,s.size()){
    if (s[i]=='0') ans+="0";
    if (s[i]=='1') ans+="1";
    if (s[i]=='B' and ans.size()!=0) ans.pop_back();

  }
  cout<<ans<<endl;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	static Scanner in = new Scanner(System.in);

	public static void main(String[] args) {
		int a = in.nextInt(), b = in.nextInt(), c = in.nextInt();
		if(a == b && b == c){
			if(a % 2 == 0){
				System.out.println("-1");
			}else{
				System.out.println("0");
			}
		}else{
			int i = 0;
			while(a %2 == 0 && b % 2 == 0 && c % 2 == 0){
				int ta, tb, tc;
				ta = (b + c) / 2;
				tb = (a + c) / 2;
				tc = (a + b) / 2;
				a = ta;
				b = tb;
				c = tc;
				i++;
			}
			System.out.println(i);
		}
	}
}


Measured memory_bytes: 21972
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(ll i = 0;i<((ll)(n));i++)
#define reg(i,a,b) for(ll i = ((ll)(a));i<=((ll)(b));i++)
#define irep(i,n) for(ll i = ((ll)(n)-1);i>=0;i--)
#define ireg(i,a,b) for(ll i = ((ll)(b));i>=((ll)(a));i--)

/*
*/

ll n,k,a[200010],before[200010],pre[200010],nex[200010],l[200010],r[200010],visit[200010]={},cnt=0,cost;
vector<ll> v;

void init(){
	cin>>n>>k;
	rep(i,n)cin>>a[i];
	rep(i,2e5+1){
		before[i]=-1;
		pre[i]=-1;
		nex[i]=1e9;
		l[i]=1e9;
		r[i]=-1;
		visit[i]=-1;
	}
}

int main(void){
	init();
	rep(i,n){
		l[a[i]]=min(l[a[i]],i);
		r[a[i]]=max(r[a[i]],i);
		pre[i]=before[a[i]];
		nex[before[a[i]]]=i;
		before[a[i]]=i;
	}
	rep(i,n){
		if(nex[i]==1e9)nex[i]=l[a[i]];  // ループさせる
	}
	ll p=0;
	cnt=0;
	while(1){
		if(visit[p]!=-1){
			cost = cnt-visit[p];
			break;
		}
		visit[p]=cnt;
		if(p>=nex[p])cnt++;
		if(nex[p]==n-1)cnt++;
		p = (nex[p]+1)%n;
	}
	// rep(i,n)cout<<visit[i]<<" ";
	// cerr<<endl;
	// cerr<<"cost: "<<cost<<endl;
	// cerr<<"p: "<<p<<endl;
	if(k<=visit[p]){
		// 愚直にシミュレーション
		p = 0;
		for(cnt=0;cnt<k;){
			if(p>=nex[p]){
				if(cnt+1>=k){
					// 増やさない
					v.push_back(a[p]);
				}else{
					cnt++;
				}
			}
			if(nex[p]==n-1){
				cnt++;
			}
			p = (nex[p]+1)%n;
		}
	}else{
		k-=visit[p];  // まずpまで行く
		k %= cost;// 次にそこからループする
		// 最後に愚直にシミュレーション
		for(cnt=0;cnt<k;){
			// cerr<<cnt<<" "<<p<<endl;
			if(p>=nex[p]){
				if(cnt+1>=k){
					// 増やさない
					v.push_back(a[p]);
					p++;  // これを入れ忘れて撃沈
					if(p==n)break;
					continue;
				}else{
					cnt++;
				}
			}
			if(nex[p]==n-1){
				cnt++;
			}
			p = (nex[p]+1)%n;
		}
	}
	// 答え
	rep(i,v.size())cout<<v[i]<<" ";
	cout<<endl;
	return 0;
}

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

long long num_div(long long num){
    map<long long, long long> T;
    for(long long i = 2; i*i <= num+1; i++){
        if(num % i != 0){
            continue;
        }
        while(num % i == 0){
            if(T.find(i) == T.end()){
                T[i] = 1;
                num /= i;
            }
            else{
                T[i]++;
                num /= i;
            }
        }
    }
    if(num != 1){
        T[num] = 1;
    }

    long long sum = 1;
    map<long long, long long>::iterator it;
    for(it = T.begin(); it != T.end(); it++){
        sum = sum*(it->second+1);
    }
    return sum;
}

vector<long long> num_divisors_table(long long n){
    vector<long long> table(n+1, 0);

    for(long long i = 1; i <= n+1; i++){
        for(long long j = i; j <= n+1; j = j+ i){
            table[j] += 1;
        }
    }
    return table;
}

int main(){
    long long n;
    cin >> n;
    vector<long long> table;
    table = num_divisors_table(1e7);

    long long sum = 0;

    for(long long i = 1; i <= n; i++){
        sum += i*table[i];
    }

    cout << sum << endl;
    
    return 0;
}

Measured memory_bytes: 81388
#include<stdio.h>
int N, K, A[200200];
int main(){
	scanf("%d%d", &N, &K);
	for(int i=0; i<N; i++){
		scanf("%d", A+i);
	}
	int l=0, r=1<<30;
	while(r-l > 1){
		int mid = (l+r)/2;
		int cnt = 0;
		for(int i=0; i<N; i++){
			cnt += (A[i]+mid-1)/mid-1;
		}
		if(cnt > K)l = mid;
		else r = mid;
	}
	printf("%d\n", r);
}

Measured memory_bytes: 2456
import java.util.Scanner;

class Main {
	public static void main(String[] args) {
	
	Scanner stdIn = new Scanner(System.in);
	
	int n = stdIn.nextShort();
	int n1 = 1;
	int n2;
	
	do {
	
		n2 = 100*n1 + 10*n1 + n1;
		
		if (n <= n2) {
			System.out.println(n2);
			return;
		}
		
		n1 = n1 + 1;
		
	} while (n1 <= 9);
	
	}
	
}

Measured memory_bytes: 21844
class Bit:
  def __init__(self,n):
    self.bl = n.bit_length()
    self.size = n
    self.tree = [0]*(n+1)
 
  def sum(self,i):
    s = 0
    while i > 0:
      s += self.tree[i]
      i -= i & -i
    return s

  def add(self,i,x):
    while i <= self.size:
      self.tree[i] += x
      i += i & -i

  #二分探索、x[未満or以下]のインデックス+1を返します
  def bs(self,x,side="l"):
    k = 1<<(self.bl-1)
    i = 0
    sm = 0
    flg = int(side!="l")
    while k:
      while i+k > self.size:
        k //= 2
      if sm+self.tree[i+k] < x+flg:
        sm += self.tree[i+k]
        i += k
      k //= 2
    return i+1

n = int(input())
a = list(map(int,input().split()))
da = {a[i]:i+1 for i in range(n)}
ans = 0
bit = Bit(n)
for i in range(n,0,-1):
  idx = da[i]
  x = bit.sum(idx)
  l2 = bit.bs(x-1,"l")
  l1 = bit.bs(x,"l")
  r1 = bit.bs(x+1,"l")
  r2 = bit.bs(x+2,"l")
  if i == n:
    bit.add(idx,1)
    continue
  if l1 == 1 or x == 1:
    l2 = 0
  if r1 == n+1:
    r2 = n+2
  if x == 0:
    ans += idx*(r2-r1)*i
  elif r1 == n+1:
    ans += (n-idx+1)*(l1-l2)*i
  else:
    if r1 < r2:
      ans += (r2-r1)*(idx-l1)*i
    if l2 < l1:
      ans += (l1-l2)*(r1-idx)*i
  bit.add(idx,1)
print(ans)

Measured memory_bytes: 66408
# -*- coding: utf-8 -*-

S = input().strip()
T = input().strip()
#-----
S=S[::-1]
T=T[::-1]

i=0
ans=""
flag = False
while i < len(S):

    if ( S[i] == T[0] or S[i] == "?" )  and  (len(S) - i) >= len(T):
        for j,word_t in enumerate(T):
            if word_t == S[i+j] or S[i+j] == "?":
                continue
            else:
                ans += S[i]
                i += 1 
                break
        
        else:
            ans += T + S[i+j+1:]
            flag = True
            break
            #i += (j+1)
            i = len(S)
    
    else:
        ans += S[i]
        i += 1
    
ans=ans[::-1]

if flag:
    ans = ans.replace('?','a')
    print(ans)

else:
    print("UNRESTORABLE")


Measured memory_bytes: 3064
n, h, w = map(int, input().split())
al, bl = [], []
for _ in range(n):
    a, b = map(int, input().split())
    al.append(a)
    bl.append(b)

ans = 0
for a, b in zip(al, bl):
    if a >= h and b >= w:
        ans += 1
print(ans)

Measured memory_bytes: 3060
#include<stdio.h>
    int main(){
    int n,a,b,i,j,max=0;
    scanf("%d%d%d",&n,&a,&b);
    if((n==5 && a==5 && b==7) ||(n==5 && a==7 && b==5)||(n==7 && a==5 && b==5)){
        printf("YES\n");
    }
    else{
        printf("NO\n");
    }


        return 0;
}

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

using namespace std;

const long long int MOD = 1e9 + 7;
long long int mypow(long long int x,long long int n)
{
	long long int res = 1;
	while(n > 0)
	{
		if(n%2==1)
		{
			res = ((res%MOD) * (x%MOD)%MOD);
			res%=MOD;
		}
		x = ((x%MOD)*(x%MOD)%MOD);
		x%=MOD;
		n/=2;
	}
	return res;
}
long long int dp[100001];

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

	int n,k;

	cin >> k >> n;

	long long int res = 0;
	
	for(int i=n;i>=1;i--)
	{
		dp[i] = mypow(n/i,k);
		for(int j=2*i;j<=n;j+=i)
		{
			dp[i] -= dp[j];
			if(dp[i] < 0)
			{
				dp[i] += MOD;
			}
		}
		res = ((res%MOD) + ((i%MOD)*(dp[i]%MOD)%MOD)%MOD);
		res%=MOD;
	}

	cout << res << '\n';

	return 0;
}

Measured memory_bytes: 4440
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<string>
#include<queue>
#include<utility>
#include<cmath>

using namespace std;


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

  vector<int> P(N);
  for(int i = 0; i < N; i++){
    cin >> P[i];
  }

  int cnt = 0;
  for(int i = 0; i < N; i++){
    if(P[i] != i+1){
      cnt++;
      if(cnt == 2){
        cout << "NO" << endl;
        return 0;
      }
      for(int j = i; j < N; j++){
        if(P[j] == i+1){
          int temp = P[i];
          P[i] = P[j];
          P[j] = temp;

          break;
        }
      }
    }
  }

  cout << "YES" << endl;

  return 0;
}


Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main(){
    int N;
    cin>>N;
    int x[N];
    for(int i=0;i<N;i++){
        cin>>x[i];
    }
    for(int i=N-1;i>=0;i--){
        cout<<x[i];
        if(i!=0){
            cout<<' ';
        }

    }
    cout<<endl;
}


Measured memory_bytes: 3088
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define R cin>>
#define ll long long
#define ln cout<<'\n'
#define in(a) insert(a)
#define pb(a) push_back(a)
#define pd(a) printf("%.10f\n",a)
#define mem(a) memset(a,0,sizeof(a))
#define all(c) (c).begin(),(c).end()
#define iter(c) __typeof((c).begin())
#define rrep(i,n) for(ll i=(ll)(n)-1;i>=0;i--)
#define REP(i,m,n) for(ll i=(ll)(m);i<(ll)(n);i++)
#define rep(i,n) REP(i,0,n)
#define tr(it,c) for(iter(c) it=(c).begin();it!=(c).end();it++)
ll check(ll n,ll m,ll x,ll y){return x>=0&&x<n&&y>=0&&y<m;}void pr(){ln;}
template<class A,class...B>void pr(const A &a,const B&...b){cout<<a<<(sizeof...(b)?" ":"");pr(b...);}
template<class A>void PR(A a,ll n){rep(i,n)cout<<(i?" ":"")<<a[i];ln;}
const ll MAX=1e9+7,MAXL=1LL<<61,dx[8]={-1,0,1,0,-1,-1,1,1},dy[8]={0,1,0,-1,-1,1,1,-1};
typedef pair<ll,ll> P;

void Main() {
  int n;
  R n;
  pr((1000-n%1000)%1000);
}

int main(){ios::sync_with_stdio(0);cin.tie(0);Main();return 0;}


Measured memory_bytes: 3608
s = input()
sum = 0
count = [0] * 4
for i in range(4):
    for j in range(i + 1,4):
        if s[i] == s[j]:
            count[i] += 1

for num in range(4):
    sum += count[num]

if sum == 2:
    print("Yes")
else:
    print("No")


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

typedef long long ll;
const int N = 105, MOD = 1e9 + 7;
int n, m, k, fac[N << 1], ifac[N << 1];

int fpow(int a, int m) {
	int ans = 1;
	for(; m; m >>= 1) {
		if(m & 1) ans = ans * 1ll * a % MOD;
		a = a * 1ll * a % MOD;
	}
	return ans;
}

struct Edge {
	int nxt, v;
}e[N << 1];
int bccno[N], bcc_cnt,siz_e[N], siz_p[N], dfs_clock, low[N], pre[N], head[N], cnt, top;
pair<int, int> stk[N];

void add(int u, int v) {
	e[++cnt] = (Edge){head[u], v}, head[u] = cnt;
	e[++cnt] = (Edge){head[v], u}, head[v] = cnt;
}
void dfs(int u, int fa) {
    low[u] = pre[u] = ++dfs_clock;
    for(int i = head[u]; ~i; i = e[i].nxt) {
    	int v = e[i].v;
    	if(v == fa) continue;
    	if(!pre[v]) {
    		stk[++top] = make_pair(u, v);
    		dfs(v, u);
    		low[u] = min(low[u], low[v]);
    		if(low[v] >= pre[u]) {
    			bcc_cnt++;
    			while(523) {
                    int x = stk[top].first, y = stk[top].second;
    			    top--;
    			    siz_e[bcc_cnt]++;
    			    if(bccno[x] != bcc_cnt) {bccno[x] = bcc_cnt; siz_p[bcc_cnt]++;}
    			    if(bccno[y] != bcc_cnt) {bccno[y] = bcc_cnt; siz_p[bcc_cnt]++;}
    			    if(x == u && y == v) break;
    			}
    		}
    	}
    	else if(pre[v] < pre[u]) {stk[++top] = make_pair(u, v); low[u] = min(low[u], pre[v]);}
    }
}
int C(int n, int m) {
	return fac[n] * 1ll * ifac[m] % MOD * ifac[n - m] % MOD;
}
int gcd(int a, int b) {
	return b == 0 ? a : gcd(b, a % b);
}

int main() {
    memset(head, -1, sizeof head);
    scanf("%d %d %d", &n, &m, &k);
    fac[0] = ifac[0] = ifac[1] = 1;
    for (int i = 1; i <= m + k; ++i) fac[i] = fac[i - 1] * 1ll * i % MOD;
    for (int i = 2; i <= m + k; ++i) ifac[i] = (MOD - MOD / i) * 1ll * ifac[MOD % i] % MOD;
    for (int i = 2; i <= m + k; ++i) ifac[i] = ifac[i - 1] * 1ll * ifac[i] % MOD;
    for(int i = 1; i <= m; i++) {
    	int u, v;
    	scanf("%d %d", &u, &v);
    	add(u, v);
    }
    for(int i = 1; i <= n; i++) {
    	if(!pre[i]) dfs(i, 0);
    }
    int ans1 = 1, ans2 = 1, ans3 = 1;
    for(int i = 1; i <= bcc_cnt; i++) {
    	if(siz_e[i] == 1) ans1 = ans1 * 1ll * k % MOD;
    	else if(siz_e[i] == siz_p[i]) {
            int sum = 0;
            for(int j = 0; j < siz_e[i]; j++) {
                sum += fpow(k, gcd(siz_p[i], j));
                if(sum >= MOD) sum -= MOD;
            }
            ans2 = ans2 * 1ll * sum % MOD * fpow(siz_e[i], MOD - 2) % MOD; 
    	} else ans3 = ans3 * 1ll * C(siz_e[i] + k - 1, k - 1) % MOD;
    }
    printf("%lld\n", ans1 * 1ll * ans2 % MOD * ans3 % MOD);
    return 0;
}

Measured memory_bytes: 3800
n = int(input())
a_list = list(map(int , input().split()))

first_flg = True
before_tall = 0
add_dai = 0
for now_tall in a_list:
    if first_flg:
        before_tall = now_tall
        first_flg = False
    else:
        if before_tall > now_tall:
            add_dai += before_tall - now_tall
            before_tall = now_tall + (before_tall - now_tall)
        else:
            before_tall = now_tall
print(add_dai)

Measured memory_bytes: 32220
#include <bits/stdc++.h>
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define pb push_back
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define rep(i, n) FOR(i, 0, n)
#define ll long long
using namespace std;

const ll P = 1000000007;
int gcd(int a, int b) { return b != 0 ? gcd(b, a % b) : a; }
int lcm(int a, int b) { return a / gcd(a, b) * b; }

int main()
{
  cout << fixed << setprecision(10);
  int N,i;
  cin >> N >> i;
  cout << N-i+1 << 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;

int main() {
	int n;
	while (cin >> n, n) {
		int sum = 0;
		int Max = 0, Min = 1000;
		rep(i, n) {
			int s; cin >> s;
			Max = max(Max, s);
			Min = min(Min, s);
			sum += s;
		}
		cout << (sum - Max - Min) / (n - 2) << endl;
	}
}

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

int main() {
    string s, t;
    cin>>s>>t;
    if (s + t[t.size()-1] == t) {
        cout<<"Yes"<<endl;
    } else {
        cout<<"No"<<endl;
    }
    return 0;
}

Measured memory_bytes: 3608
N = int(input())
a = list(map(int, input().split()))
s = []

b = 0
for i in range(N):
  b += a[i]
  s.append(b)
  
ans = abs(2*s[0]-s[N-1])
for i in range(N-1):
  ans = min(ans, abs(2*s[i]-s[N-1]))
  
print(ans)


Measured memory_bytes: 26228
import math
n=int(input())
p=list(map(int,input().split()))
q=list(map(int,input().split()))
arrayp=[1]
for iii in range(n-1):
    arrayp+=[1]
arrayq=[1]
for jjj in range(n-1):
    arrayq+=[1]
pnum=0
qnum=0
for i in range(n-1):
    prank=0
    for ii in range(p[i]):
        if arrayp[ii]==1:
            prank+=1
    pnum=pnum+(prank-1)*math.factorial(n-i-1)
    arrayp[p[i]-1]=0
for j in range(n-1):
    qrank=0
    for jj in range(q[j]):
        if arrayq[jj]==1:
            qrank+=1
    qnum=qnum+(qrank-1)*math.factorial(n-j-1)
    arrayq[q[j]-1]=0
print(abs(pnum-qnum))

Measured memory_bytes: 3064