akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
 
typedef pair<int, pair<int, int> > p;
 
#define MOD 1000000007

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

    int N;
    cin >> N;

    vector<ll> L(N);

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

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

    ll ans = 0;

    for(int i = 0; i < N - 2; i++) {
        for(int j = i + 1; j < N - 1; j++) {
            if(L[i] == L[j]) continue;
            for(int k = j + 1; k < N; k++) {
                if(L[j] == L[k]) continue;
                if(L[i] + L[j] > L[k]) {
                    //cerr << L[i] << L[j] << L[k] << endl;
                    ans++;
                }
            }
        }
    }

    cout << ans << endl;
}

Measured memory_bytes: 3632
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <cmath>
#include <utility>
using namespace std;


int main() {
	int x, a, b;
	cin >> x >> a >> b;	
	cout << ((abs(x - a) < abs(x - b)) ? "A" : "B") << endl;
}

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

int main() {
    map<int, int> lastMonth;
    map<int, int> thisMonth;
    string line;
    while (getline(cin, line)) {
        if (line.empty()) {
            break;
        }
        istringstream buff(line.substr(0, line.find_first_of(',')));
        int num;
        buff >> num;
        lastMonth[num]++;
    }
    while (getline(cin, line)) {
        istringstream buff(line.substr(0, line.find_first_of(',')));
        int num;
        buff >> num;
        thisMonth[num]++;
    }
    for (map<int, int>::iterator it = lastMonth.begin(); it != lastMonth.end(); it++) {
        if (thisMonth[it->first] > 0) {
            cout << it->first << " " << it->second + thisMonth[it->first] << endl;
        }
    }
}

Measured memory_bytes: 0
#include<iostream>
#include<string>
#include<algorithm>
#include<map>

using namespace std;

int main(){
    int N;
    cin >> N;
    string S[N];
    
    for(int i=0;i<N;i++){
        cin >> S[i];
        sort(S[i].begin(), S[i].end());
    }
    
    map<string, int> mp;
    long n = 0;

    for(int i=0;i<N;i++){
        if( mp.find(S[i]) == end(mp)){
            mp.emplace(S[i], 1);
        }
        else{
            mp.find(S[i]) -> second ++;
        }
    }
    for(auto itr = mp.begin(); itr != mp.end(); ++itr){
        long temp = itr -> second;
        n+= (temp-1)*temp/2;
    }

    cout << n << endl;

    return 0;
}

Measured memory_bytes: 18176
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_map>
#include <functional>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cstdlib>

using namespace std;
typedef long long llong;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<llong, llong> pll;

int main() {
    llong a, b, c;
    scanf("%lld%lld%lld", &a, &b, &c);
    if (a % 2 == 0 || b % 2 == 0 || c % 2 == 0) {
        printf("0\n");
        return 0;
    }
    llong ans = min({ b * c, a * b, c * a });
    printf("%lld\n", ans);
	return 0;
}


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

int main(){
	long long n;
	cin >> n;
	long long a,b,at,tmp=0,tlw=RAND_MAX;
	for(a=1;a<=(int)sqrt(n);a++){
		if(n%a==0){
			b=n/a;
			long long ac=0,bc=0;
			at = a;
			while(at>0){
				ac++;
				at/=10;
			}
			while(b>0){
				bc++;
				b/=10;
			}
			tmp = max(ac,bc);
			if(tmp<tlw)
				tlw=tmp;
			}
	}
	if(tlw==RAND_MAX)
		tlw = 1;
	cout << tlw << endl;
}


Measured memory_bytes: 256
use proconio::fastout;
use whiteread::parse_line;

#[fastout]
fn main() {
    let n: usize = parse_line().unwrap();
    let mut t = vec![];
    let mut a = vec![];
    for _ in 0..n {
        let (x, y): (usize, usize) = parse_line().unwrap();
        t.push(x);
        a.push(y);
    }
    for i in 0..n-1 {
        if t[i] > t[i+1] || a[i] > a[i+1] {
            let p = std::cmp::max((t[i] + t[i+1] - 1) / t[i+1] , (a[i] + a[i+1] - 1) / a[i+1]);
            t[i+1] = t[i+1] * p;
            a[i+1] = a[i+1] * p;
        }
    }
    println!("{}", t[n-1] + a[n-1]);
}

Measured memory_bytes: 2172
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
#define re(i,n) for(ll i=0;i<(n);++i)
#define itn int
#define ocut cout
#define ouct cout
#define outc cout

int main(){
    int h,n;
    cin >> h >> n;
    int a[n],v=0;
    re(i,n){
        cin >> a[i];
        v=v+a[i];
    }
    if(h>v){
        cout << "No";
    }
    else{
        cout << "Yes";
    }
}



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

using namespace std;

int main()
{
    int W,H,x,y,r;
    cin>>W>>H>>x>>y>>r;
    if(x+r<=W&&y+r<=H&&x-r>=0&&y-r>=0)
    {
        cout<<"Yes"<<endl;
    }
    else
    {
        cout<<"No"<<endl;
    }
    return 0;
}


Measured memory_bytes: 3104
#include<stdio.h>
int main(void){
  int i,n;
  scanf("%d",&n);
  
  int a[n];
  
  for (i = 0; i < n; i++) {  
    scanf("%d", &a[i]);
  }
  
  for (i = n-1 ; i >= 0; i--) {
    if(i==0){
      printf("%d", a[i]);
    }else{
      printf("%d ", a[i]);
    }
    
  }
  printf("\n");
  return 0;
}

Measured memory_bytes: 600
#include "bits/stdc++.h"
// Begin Header {{{
#define all(x)      x.begin(), x.end()
#define rep(i,n)    for (i64 i = 0; i < (n); ++i)
#define reps(i,s,t) for (i64 i = (s); i <= (t); ++i)
#define repr(i,s,t) for (i64 i = (s); i >= (t); --i)

#ifdef DBG
#define trace(...) _trace(#__VA_ARGS__, __VA_ARGS__);
#else
#define trace(...)
#endif

using namespace std;
using i64 = int_fast64_t;
using pii = pair<i64, i64>;
template<class T, class U>inline bool chmax(T &a, const U &b){return b>a ? (a=b,1) : 0;}
template<class T, class U>inline bool chmin(T &a, const U &b){return b<a ? (a=b,1) : 0;}
constexpr int INF  = 0x3f3f3f3f;
constexpr i64 LINF = 0x3f3f3f3f3f3f3f3fLL;

template<class T>
ostream& operator<< (ostream &os, const vector<T> &vec) {
    rep(i, vec.size()) os << vec[i] << (i+1 == vec.size() ? "" : " ");
    return os;
}

template<class T, class U>
ostream& operator<< (ostream &os, const pair<T, U> &p) {
    return os << p.first << ' ' << p.second;
}

template <class T>
void _trace(const char *s, T&& x)
{
    clog << '{';
    while(*s != '0' && *s != ',') clog << *(s++);
    clog << ":" << setw(3) << x << '}' << endl;
}

template <class Head, class... Tail>
void _trace(const char *s, Head&& head, Tail&&... tail)
{
    clog << '{';
    while(*s != ',') clog << *(s++);
    clog << ":" << setw(3) << head << "}, ";
    for (++s; !isgraph(*s); ++s);
    _trace(s, std::forward<Tail>(tail)...);
}
// }}} End Header

signed main()
{
    // ios::sync_with_stdio(false); cin.tie(nullptr);
    int N, M;
    cin >> N >> M;

    vector<int> cnt(N);

    rep(i, M) {
        int a, b;
        cin >> a >> b;
        --a, --b;
        cnt[a] += 1;
        cnt[b] += 1;
    }

    rep(i, N) {
        cout << cnt[i] << endl;
    }

    return 0;
}


Measured memory_bytes: 256
S = str(input())

first0= 0
first1 = 0

nextStr = 1
for s in S:
    if int(s) != nextStr:
        first1 += 1 
        
    if nextStr == 1:
        nextStr = 0 
    else: nextStr = 1 

nextStr = 0
for s in S:
    if int(s) != nextStr:
        first0 += 1 
        
    if nextStr == 1:
        nextStr = 0 
    else:
        nextStr = 1 
    
print(min(first0, first1))

Measured memory_bytes: 3188
#include <iostream>
#include <iomanip>
#include <string>
#include <string.h>
#include <math.h>
#include <cmath>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <algorithm>
#include <utility>
#include <deque>
#include <queue>
#include <functional>
//#include <boost/multiprecision/cpp_int.hpp>

#define rep(i, n) for(int i = 0; i < n; ++i)
#define REP(i, m, n) for(int i = m; i < n; ++i)
#define rrep(i,n) for(int i = n; i >= 0; --i)
#define RREP(i, m, n) for(int i = n; i >= m; --i)
#define llrep(i, n) for(ll i = 0; i < n; ++i)
#define llREP(i, m, n) for(ll i = m; i < n; ++i)
#define llrrep(i,n) for(ll i = n; i >= 0; --i)
#define llRREP(i, m, n) for(ll i = n; i >= m; --i)

using ll = long long;
using ull = unsigned long long;
using pii = std::pair<int, int>;
using pll = std::pair<long long, long long>;
using pil = std::pair<int, long long>;
using pli = std::pair<long long, int>;
using plpii = std::pair<long long, std::pair<int, int>>;
using pdd = std::pair<double, double>;
using pis = std::pair<int, std::string>;

const long long INF = 1000000000000000001;
const long long _MOD = 1000000007;
const long long MOD = 998244353;
const int ALPHABET = 27;
const double pi = 3.14159265358979;

using namespace std;
//namespace mp = boost::multiprecision;

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

	int n;
	cin >> n;
	ll* a = new ll[n];
	rep(i, n) cin >> a[i];

	pll* b = new pll[n];
	b[0].first = a[0];
	b[0].second = a[0] * (-1);
	REP(i, 1, n-1) {
		b[i].first = max(a[i] + b[i - 1].first, a[i] * (-1) + b[i - 1].second);
		b[i].second = max(a[i] * (-1) + b[i - 1].first, a[i] + b[i - 1].second);
	}

	cout << max(a[n - 1] + b[n - 2].first, a[n - 1] * (-1) + b[n - 2].second) << "\n";

	return 0;
}


Measured memory_bytes: 5980
#include <cstdio>
#include <iostream>
#include <cmath>
#include <algorithm>

using namespace std;

int main(){
	
	string str, str1, str2;
	
	cin >> str;
	
	str1 = str.substr(0,4);
	str2 = str.substr(4,8);
	
	cout << str1 << " " << str2 << endl;
	
	return 0;
}



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

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define foru(i, a, b) for(int i = a; i <= b; i++) 
#define ford(i, a, b) for(int i = a; i >= b; i--) 
#define endl "\n"
#define scv(a, b, c) #a#b#c
#define com(a,b) a ## b

using namespace std;

typedef long long ll;
typedef double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pii> vii;
typedef vector<pll> v2l;
typedef pair<char, int> pci;
typedef vector<pci> vci;

const int N = 1e6 + 1;
const int NN = 3e3 + 1;
const ll MOD = 998244353;
const ll oo = 1e18 + 7;
const int BASE = 10000;

class solve {
public: 
    solve() {
        int n;
        cin >> n;
        ld  res = 0;
        for (int i = 1; i <= n; i++) {
            ld x;
            cin >> x;
            res += (1 / x);
        }
        cout << 1 / res;
    }
};

int main() {
    #ifdef DEBUG
        com(fre, open) (scv(solve, ., inp), "r", stdin);
        com(fre, open) (scv(solve, ., out), "w", stdout);
    #endif
    ios_base::sync_with_stdio(1);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cout.precision(10);
    solve kAN;
    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
 
int main() {
    const int MOD = 1e9 + 7;
    long long n, k;
    cin >> n >> k;
 
    long long ans = 0;
    for (int i = k; i < n + 2; i++) {
        ans = (ans + i * (n - i + 1) + 1) % MOD;
    }
 
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3644
import java.util.Scanner;

public class Main {

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

		Scanner sc = new Scanner(System.in);
		for(int i =0;i <= 6;i++) {
		int a = sc.nextInt();
		int b = sc.nextInt();
		System.out.println(a - b);
	  }
   }
}

Measured memory_bytes: 17356
#include<bits/stdc++.h>
using namespace std;
int w[200];
int v[200];
typedef long long ll;
ll dp[200000];
int main()
{
    int n,W;
    int ans=0;
    int m=0;
    scanf("%d%d",&n,&W);
    for(int i=0;i<n;i++){
        scanf("%d%d",&w[i],&v[i]);
        m=max(v[i],m);
    }
    memset(dp,0x3f,sizeof(dp));
    dp[0]=0;
    m=m*n;
    for(int i=0;i<n;i++){
        for(int j=m;j>=v[i];j--){
            dp[j]=min(dp[j],dp[j-v[i]]+w[i]);
            if(dp[j]<=W){
                ans=max(ans,j);
            }
        }
    }
    cout<<ans;
}


Measured memory_bytes: 1792
#include<iostream>
using namespace std;
class Dice{
    int x[7] = {};
    public:
    void input(int I, int num){
        x[I] = num;
    }
   
    void move(char order){
        int oldx[7];
        for(int i = 1; i <= 7; i ++){
            oldx[i] = x[i];
        }
        if(order == 'N'){
            x[1] = oldx[2];
            x[2] = oldx[6];
            x[6] = oldx[5];
            x[5] = oldx[1];
        } 
        else if(order == 'S'){
            x[1] = oldx[5];
            x[2] = oldx[1];
            x[6] = oldx[2];
            x[5] = oldx[6];
        }
        else if(order == 'W'){
            x[1] = oldx[3];
            x[4] = oldx[1];
            x[6] = oldx[4];
            x[3] = oldx[6];
        }
        else if(order == 'E'){
            x[1] = oldx[4];
            x[4] = oldx[6];
            x[6] = oldx[3];
            x[3] = oldx[1];
        }
    }
     void rotation(int top, int flont){
       for(int i = 0; i < 4; i++){
           move('S');
           if(x[2] == top){
               for(int j = 0; j < 4; j++){
                   move('W');
                   if(x[6] == flont){
                       move('N');
                       break;
                   }
               }
           }
           else if(x[2] == flont){
               for(int j = 0; j < 4; j++){
                   move('E');
                   if(x[1] == top) break;
                   
               }
               
           }
           
     
           
           
       }
        
    }
    void print(int num){
        
        cout << x[num]<< endl;
      
        }
    
};

int main(){
    Dice dice;
    int val, n, up , flont;
    for(int i = 1;i <= 6; i++){
        cin >> val;
        dice.input(i,val);
    }
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> up >> flont;
        dice.rotation(up,flont);
        dice.print(3);
    }
    return 0;
}


Measured memory_bytes: 3096
# coding: utf-8
N = int(input())
L = input().split()
for i in range(N):
  L[i]=int(L[i])

L.sort()
L.reverse()

A=0
B=0

for i in range(N):
  if i%2==0:
    A += L[i]
  else:
    B += L[i]

print(A-B)


Measured memory_bytes: 3064
#include "bits/stdc++.h"
// Begin Header {{{
#define all(x)          (x).begin(), (x).end()
#define rep(i, s, n)    for (i64 i = (s), i##_limit = (n); i < i##_limit; ++i)
#define repr(i, s, t)   for (i64 i = (s), i##_limit = (t); i >= i##_limit; --i)
#define var(type, ...)  type __VA_ARGS__; read(__VA_ARGS__);
#ifndef DBG
#define dump(...)
#endif
using namespace std;
using i64 = int_fast64_t;
using pii = pair<i64, i64>;
template <class T, class U> inline bool chmax(T &a, const U &b) { return b > a && (a = b, true); }
template <class T, class U> inline bool chmin(T &a, const U &b) { return b < a && (a = b, true); }
constexpr int INF  = 0x3f3f3f3f;
constexpr i64 LINF = 0x3f3f3f3f3f3f3f3fLL;

template <class T>
inline vector<T> makeV(const T &initValue, size_t sz) {
    return vector<T>(sz, initValue);
}

template <class T, class... Args>
inline auto makeV(const T &initValue, size_t sz, Args... args) {
    return vector<decltype(makeV<T>(initValue, args...))>(sz, makeV<T>(initValue, args...));
}

template <class T>
inline istream& operator>> (istream &is, vector<T> &vec) {
    for (auto &e : vec) is >> e;
    return is;
}

inline void read() {}

template <class Head, class... Tail>
inline void read(Head &head, Tail&... tail) { cin >> head; read(tail...); }

inline void print() { cout << "\n"; }

template <class Head, class... Tail>
inline void print(Head &&head, Tail&&... tail) {
    cout << head;
    if (sizeof...(tail)) cout << ' ';
    print(forward<Tail>(tail)...);
}

template <class T>
inline ostream& operator<< (ostream &os, const vector<T> &vec) {
    static constexpr const char *delim[] = { " ", "" };
    for (const auto &e : vec) os << e << delim[&e == &vec.back()];
    return os;
}

template <class Container>
struct Rev {
    Container &x_;
    inline Rev(Container &x): x_(x) {}
    inline auto begin() { return rbegin(x_); }
    inline auto end() { return rend(x_); }
};
// }}} End Header

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);

    var(int, N);
    vector<string> a(N);
    read(a);

    vector<int> cntmin(128, INF);
    for (const auto &s : a) {
        rep(ch, 'a', 'z' + 1) {
            chmin(cntmin[ch], count(all(s), ch));
        }
    }

    string ans = "";
    rep(ch, 'a', 'z' + 1) {
        ans += string(cntmin[ch], ch);
    }

    print(ans);

    return 0;
}


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

int main(){
  int n, m, a[10000], need_days=0;
  
  cin >> n >> m;
  for(int i=0; i<m; i++){
    cin >> a[i];
    need_days += a[i];
  }
  
  int play_days = n - need_days;
  
  if(play_days < 0){
    play_days = -1;
  }
  
  cout << play_days << endl;
}

Measured memory_bytes: 3652
#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <queue>
#include <unordered_map>

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

using namespace std;

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

int main(){
    ll l,r; cin >> l >> r;
    ll a = l%2019;
    ll b = r%2019;
    ll ans = 2019;
    if(a > b || r - l >= 2019) {
        cout << 0 << endl;
        return 0;
    }
    for(int i = a; i <= b; i++) {
        for(int j = i + 1; j <= b; j++) {
            ll tmp = i*j%2019;
            if(ans > tmp)
                ans = tmp;
        }
    }
    cout << ans << endl;

}


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

int main()
{
    string s ;
    int arr[205] = {0} ;
    while(getline(cin , s))
    {
        if(!cin) break ;
        for(int i = 0 ; i < s.length() ; i++)
        {
            char z = s[i] ;
            z = tolower(z) ;
            arr[(int)z]++ ;
        }
    }
    for(int i = 97 ; i <= 122 ; i++) cout << (char)i << " : " << arr[i] << endl ;
}


Measured memory_bytes: 3184
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication6
{
    class Program
    {
        static void Main(string[] args)
        {
            var abc = Console.ReadLine().Split().Select(int.Parse).ToArray();
            var a = abc[0];
            var b = abc[1];
            var c = abc[2];
            if (a < b && b < c)
            {
                Console.WriteLine("Yes");
            } else {
                Console.WriteLine("No");
            }
        }
    }
}

Measured memory_bytes: 9384
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll N = 2e5 + 10, MOD = 998244353;
ll dp[N], n, k, l[N], r[N];
int f(ll l, ll r) {
    if(l > r || r <= 0) return 0;
    l = max(l, 1ll);
    r = min(r, n);
    return (MOD + dp[r] - dp[l - 1]) % MOD;
}
int main() {
    cin >> n >> k;
    for(int i = 1; i <= k; ++i) {
        cin >> l[i] >> r[i];
    }
    dp[1] = 1;
    for(int i = 2; i <= n; ++i) {
        dp[i] = dp[i - 1];
        for(int j = 1; j <= k; ++j) {
            dp[i] = (dp[i] + f(i - r[j], i - l[j])) % MOD;
        }
    }
    cout << (MOD + dp[n] - dp[n - 1]) % MOD << endl;
}

Measured memory_bytes: 5148
#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.at(i);
  }

  bool flag = true;

  for (int i = 0; i < N; i++)
  {
    if (A.at(i) % 2 == 0)
    {
      if (A.at(i) % 3 == 0 || A.at(i) % 5 == 0)
      {
      }
      else
      {
        flag = false;
      }
    }
  }

  if (flag)
  {
    cout << "APPROVED" << endl;
  }
  else
  {
    cout << "DENIED" << endl;
  }
}


Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace AOJ
{
	class Program
	{
		static void Main(string[] args)
		{
			var paper = new int[10 + 4][];
			for (int i = 0; i < 14; i++)
				paper[i] = new int[10 + 4];
			var px = new int[3, 4] { { 0, 0, -1, 1 }, { -1, -1, 1, 1 }, { 0, 0, -2, 2 } };
			var py = new int[3, 4] { { -1, 1, 0, 0 }, { -1, 1, -1, 1 }, { -2, 2, 0, 0 } };
			
			var line = "";
			while ((line = Console.ReadLine()) != null)
			{
				var xys = line.Split(',').Select(i => int.Parse(i)).ToArray();
				int x = xys[0] + 2, y = xys[1] + 2, s = xys[2];

				paper[x][y]++;
				for (int i = 0; i < s; i++)
				{
					for (int j = 0; j < 4; j++)
					{
						paper[x + px[i, j]][y + py[i, j]]++;
					}
				}
			}
			var a = paper.Skip(2).Take(10).Sum(i => i.Skip(2).Take(10).Count(j => j == 0));
			var b = paper.Skip(2).Take(10).Max(i => i.Skip(2).Take(10).Max());
			Console.WriteLine(a);
			Console.WriteLine(b);
		}
	}
}

Measured memory_bytes: 6108
#include<bits/stdc++.h>
using namespace std;
using Int = long long;
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
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; }

long long calc(long long A) {
  long long cnt = (A+1)/2;
  long long ans = cnt % 2;
  if (A%2 == 0) ans ^=A;
  return ans;
}

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

  long long A; cin >> A;
  long long B; cin >> B;

  cout << (calc(B)^calc(A-1)) << endl;
}

Measured memory_bytes: 256
s = input()
k = int(input())

a = list()

ch = 0
cn = 0
for i in range(1,27):
    b = set()
    for j in range(len(s)):
        if(ord(s[j])==(i+96)):
            for m in range(j,j+k):
                #print(s[j:m+1])
                b.add(s[j:m+1])
                cn += 1
                

    a.append(list(b))
    

for i in range(26):
    a[i].sort()
    
cn = 0
for i in range(26):
    if(len(a[i])+cn>=k):
        for j in range(len(a[i])):
            cn += 1
            if(cn == k):
                print(a[i][j])
    else:
        cn += len(a[i])
        
#print(a)

Measured memory_bytes: 40560
import java.io.*;

public class Main {
	
	public static void main(String[] args) throws IOException{
		BufferedReader br= new
				BufferedReader(new InputStreamReader(System.in));
			String snow = br.readLine();
			int inow = Integer.parseInt(snow);
			while(true){
				String kigo = br.readLine();
				if(kigo.equals("="))break;
				String snum = br.readLine();
				int inum = Integer.parseInt(snum);
				if(kigo.equals("+"))inow+=inum;
				else if(kigo.equals("-"))inow-=inum;
				else if(kigo.equals("*"))inow*=inum;
				else inow/=inum;
			}
			System.out.println(inow);
	}

}

Measured memory_bytes: 16868
#include<stdio.h>
int main()
{	int n,k;
	scanf("%d %d", &n, &k);
	int a[n];
	int i, j;
	for( i=0; i<n; i++)
	{
		scanf("%d", &a[i] );
	}
	int dp[k+1];
	dp[0]=0;
	for( i=1; i<=k; i++)
	{	int status=0;
		for( j=0; j<n; j++)
		{
			int p = i - a[j];
			if( p>=0 && dp[p]==0)
			{	status=1;	 	 
				break;
			}
		}
		dp[i]=status;
	}
	if(dp[k]==1)
		printf(" First ");
	else
		printf(" Second ");
	return 0;
}


Measured memory_bytes: 512
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int N = scanner.nextInt();
        String S = scanner.next();
        int countW[] = new int[N];
        int countE[] = new int[N];
        int total[] = new int[N];
        int min = N;

        char c[] = new char[N];
        for(int i = 0; i < N; i++){
            c[i] = S.charAt(i);
        }
        for(int i = 0; i < N; i++){
            if(c[i] == 'W'){
                    countW[i] += 1;
            }
            if(c[N - i -1] == 'E'){
                    countE[N - i -1] += 1;
            }
        }
        for(int i = 1; i < N; i++){
            countW[i] += countW[i - 1];
            countE[N - i -1] += countE[N - i];
        }
        for(int i = 0; i < N; i++){
            if(i == 0){
                total[i] = countE[1];
            }else if(i == N - 1){
                total[i] = countW[N -2];
            }else{
                total[i] = countW[i - 1] + countE[i + 1];
            }
        }
        for(int i = 0; i < N; i++){
            if(total[i] < min){
                min = total[i];
            }
        }
        System.out.println(min);
    }
}

Measured memory_bytes: 34464
#include <bits/stdc++.h>
using namespace std;
int main(){
long long counter=0;
long long N,x,c,b;
cin>>N>>x;
pair<long long,long long> a[100009];
for(long long i=0;i<N;i++){
cin>>c>>b;
a[i]=make_pair(c,b);}
sort(a,a+N);
for(long long i=0;i<N;i++){
if(x-a[i].second>=0){
counter+=(a[i].first)*(a[i].second);
x-=a[i].second;}
else{counter+=(a[i].first)*(x);
break;}}
cout<<counter<<endl;}



Measured memory_bytes: 1792
#include<bits/stdc++.h>
#define watch(x) cout << (#x) << " is " << (x) << endl
typedef long long ll;
using namespace std;
int static fast = [](){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0); return 0;
}();

int main() {
    int n;
    cin >> n;
    if (n % 2 == 0) {
        cout << 0.5000000000 << endl;
    } else {
        int odd = n / 2 + 1;
        double p = double(odd)/double(n);
        cout << fixed << setprecision(12) << p << endl;
    }
    return 0;
}




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


int i, j, k;
int g[2*1000][2*1000];
int d[2000];
int min(int a, int b){
  if(a>b)return b;
  else return a;
}

int abs(int a){
  if (a<0)a*=-1;
  return a;
}

int main(){
   int n,a,b;
   scanf("%d %d %d", &n, &a, &b);
   for(i=0;i<n-1;i++)g[i][i+1]=g[i+1][i]=1;
   for(i=1;i<n+1;i++)d[i]=0;
   g[a-1][b-1]=g[b-1][a-1]=1;


   for(i=1;i<n;i++){
     for(j=i+1;j<n+1;j++){
       d[min(j-i, abs(a-i)+abs(b-j)+1)]+=1;
     }
   }

   for(i=1;i<n;i++)printf("%d\n", d[i]);


   return 0;
 }


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

#define MOD 1000000007
#define f first
#define s second
#define es " "
#define pb push_back
#define endl "\n"
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3f
#define ll long long int
#define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)

int main(){
    fastio;
    string s;
    cin >> s;
    int mem[1005];
    bool ok=true;
    memset(mem, 0, sizeof(mem));
    mem[s[0]]++;
    mem[s[1]]++;
    mem[s[2]]++;
    mem[s[3]]++;
    for(int i=0; i<(int)s.size(); i++){
        if(mem[s[i]]!=2){
            ok=false;
        }
    }
    if(ok){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define fs first
#define sc second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define All(A) A.begin(),A.end()
#define RAll(A) A.rbegin(),A.rend()
typedef long long LL;
typedef pair<LL,LL> P;
const LL mod=1e9+7;
const LL LINF=1LL<<62;
const LL INF=1<<30;


LL f[2][1000005];
    LL s[4][1000005],t[4][1000005];


bool check(LL x,LL a,int N){
    LL imos[N+3];
    memset(imos,0,sizeof(imos));
    for(int i=1;i<=N;i++){
        if(x<=f[1][i]){
            imos[1]++;
            imos[N+1]--;
            continue;
        }
        else if(a+f[1][i]-x<0){
            return false;
        }
        LL u=(LL)sqrt(a+f[1][i]-x);
        imos[max(i-u,1LL)]++;
        imos[min((LL)N+1,i+u+1)]--;
    }
    LL sum=0;
    for(int i=1;i<=N+1;i++){
        sum+=imos[i];
        if(sum==N) return true;
    }
    return false;
}



int main(){
    int N,M;
    while(cin >> N >> M){
        if(N==0&&M==0) break;
        memset(s,0,sizeof(s));
        memset(t,0,sizeof(t));
        memset(f,0,sizeof(f));
        for(int i=0;i<M-1;i++){
            LL a,x;
            cin >> a >> x;
            LL tm=min(N-x,(LL)sqrt(a));
            t[0][x+tm+1]-=2;
            t[0][x+1]+=1;
            t[0][x+2]+=1;
            t[1][x+tm+1]-=2*tm-1;
            t[2][x+tm+1]-=tm*tm;
            LL sm=min((LL)sqrt(a),x-1);
            s[0][x-sm-1]-=2;
            s[0][x-1]+=1;
            s[0][x-2]+=1;
            s[1][x-sm-1]-=2*sm-1;
            s[2][x-sm-1]-=sm*sm;
            f[0][x+tm+1]-=a;
            f[0][x-sm]+=a;
        }
        for(int i=0;i<3;i++){
            LL sum=0;
            for(int j=1;j<=N+1;j++){
                sum+=t[i][j];
                t[i+1][j]+=sum;
            }
            sum=0;
            for(int j=N;j>=0;j--){
                sum+=s[i][j];
                s[i+1][j]+=sum;
            }
        }
        LL sum=0;
        for(int i=1;i<=N;i++){
            sum+=f[0][i];
            f[1][i]+=sum;
            f[1][i]-=t[3][i]+s[3][i];
        }
        LL a;
        cin >> a;
        LL l=0,r=LINF;
        while(l+1!=r&&l!=r){
            LL m=(l+r)/2;
            if(check(m,a,N)) l=m;
            else r=m;
        }
        cout << l << endl;
    }
    return 0;
}


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

using namespace std;

#define FAST_IO ios_base::sync_with_stdio(0); cin.tie(nullptr)
#define FOR(i,a,b) for(int i = (a); i <= (b); i++)
#define REP(n) FOR(O, 1, (n))
#define pb push_back
#define f first
#define s second
#define INF 10000000000000000
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef vector<ll> vl;
typedef vector<pii> vii;
typedef pair<pii, pii> piiii;

const int MAXN = 1100, MAXK = 35;
const ll MOD = 1e9+7;

int n;
int a[MAXN][MAXN];
int curId[MAXN];
bool vis[MAXN];

int main()
{
    FAST_IO;

    cin >> n;
    FOR(i, 1, n) FOR(j, 1, n-1) cin >> a[i][j];
    FOR(i, 1, n) curId[i] = 1;

    bool ok = true;
    int cnt = 0;
    while (ok) {
        bool stop = true;
        FOR(i, 1, n) vis[i] = false;
        FOR(i, 1, n) {
            if (curId[i] > n-1 || vis[i]) continue;
            int en = a[i][curId[i]];
            if (!vis[en] && a[en][curId[en]] == i) {
                curId[i]++;
                curId[en]++;
                vis[i] = true;
                vis[en] = true;
               // cout << " day " << cnt+1  << " - " << i << " vs " << en << endl;
                stop = false;
            }
        }

        if (stop) {ok = false; break;}
        cnt++;
    }

    ok = true;
    FOR(i, 1, n) if (curId[i] < n) ok = false;

    if (ok) cout << cnt << endl;
    else cout << -1 << endl;

    return 0;
}


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

int main(){
  int n,l;
  cin>>n>>l;
  int sum=0,minl=1000;
  for(int i=1;i<=n;i++){
  	sum+=(l+i-1);
    if(abs(minl)>abs(l+i-1)) minl=l+i-1;
   
  }
  cout << sum-minl << endl;
  
}

Measured memory_bytes: 256
#include <stdio.h>
int main(void)
{ 
	int a, b, c;
	int x;
	int i=1;
	for (;scanf("%d%d", &a, &b) != EOF;)
	{
		c=0;
		x=0;
		i=1;
		c=a+b;
    	x=c;
		for (;;)
		{
			x=x/10;
			if (x!=0)
			{
				i=i+1;
			}
			if (x==0)
			{
				break;
			}
		}
		if (c==0)
		{
			printf("0\n");
		}
		else
			printf("%d\n", i);
		
	}
	return 0;
}

Measured memory_bytes: 600
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")

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

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

int main() {
  int N;
  cin >> N;
  vector<string> S(N);
  REP(i, N) cin >> S[i];
  sort(ALL(S));
  vector<string> T;
  int tmp1 = 1, tmp2 = 1;
  REP(i, N-1) {
    if (S[i] == S[i+1]) {
      tmp1++;
    } else {
      if (tmp1 > tmp2) tmp2 = tmp1;
      tmp1 = 1;
    }
  }
  if (tmp1 > tmp2) tmp2 = tmp1;
  tmp1 = 1;
  REP(i, N-1) {
    if (S[i] == S[i+1]) {
      tmp1++;
    } else {
      if (tmp1 == tmp2) cout << S[i] << endl;
      tmp1 = 1;
    }
  }
  if (tmp1 == tmp2) cout << S[N-1] << endl;
  return 0;
}

Measured memory_bytes: 14208
#include <bits/stdc++.h>
#define rep(i, m, n) for(int i = m; i < (n); i++)
#define print(x) cout << (x) << endl;
#define printa(x,n) for(int i = 0; i < n; i++){ cout << (x[i]) << " ";} cout << endl;
#define printa2(x,m,n) for(int i = 0; i < m; i++){ for(int j = 0; j < n; j++){ cout << x[i][j] << " ";} cout << endl;}
#define printp(x,n) for(int i = 0; i < n; i++){ cout << "(" << x[i].first << ", " << x[i].second << ") "; } cout << endl;
#define INF (1e18)
using namespace std;
typedef long long ll;
const ll MOD = 1e9 + 7;
typedef struct{
    int x;
    int y;
} P;
typedef struct{
    ll to;
    ll cost;
} edge;
typedef pair<ll, ll> lpair;
const ll max_N = 200000;
ll fac[max_N + 1000], facinv[max_N + 1000];
ll N,K;

ll power(ll x, ll n){
    if(n == 0) return 1LL;
    ll res = power(x * x % MOD, n/2);
    if(n % 2 == 1){
        res = res * x % MOD;
    }
    return res;
}

ll nck(ll n, ll k){
    if(k == 0 || n == k){
        return 1;
    }
    return fac[n] * facinv[k] % MOD * facinv[n-k] % MOD;
}

ll npk(ll n, ll k){
    if(k == 0 || n == k){
        return 1;
    }
    return fac[n] * facinv[n-k] % MOD;
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll H,W,A,B;
    cin >> H >> W >> A >> B;
    fac[0] = 0;
    fac[1] = 1;
    rep(i,2,max_N){
        fac[i] = (fac[i-1] * i) % MOD;
    }
    rep(i,0,max_N){
        facinv[i] = power(fac[i], MOD - 2);
    }
    ll all_c = nck(H+W-2, H-1);
    ll ab_min = min(A,B);
    ll ex_c = 0;
    rep(i,0,ab_min){
        ex_c += nck(H-A+B-1, B-i-1) * nck(W-B+A-1,A-i-1);
        ex_c %= MOD;
    }
    ll ans = (all_c - ex_c + MOD) % MOD;
    print(ans);

}


Measured memory_bytes: 3328
#include<bits/stdc++.h>
using namespace std;
#define pcc pair<char,char>
#define mid ((head+tail)/2)
int chkdir(int p,string s,vector<pcc> arr){
  int n=s.length(),q=arr.size();
  for(int i=0;i<q;++i){
    if(s[p]==arr[i].first){
      p+=(arr[i].second=='R'?1:-1);
      if(p<0)return -1;
      if(n<=p)return 1;
    }
  }
  return 0;
}

int binsrc(int dir,string s,vector<pcc> arr){
  int n=s.length(),head=0,tail=n-1;
  while(tail-head){
    if(tail-head==1){
      bool h=false,t=false;
      h=(chkdir(head,s,arr)==dir);
      t=(chkdir(tail,s,arr)==dir);
      if(!(h||t))return (dir==1?n:-1);
      if(dir==1)return (h?head:tail);
      if(dir==-1)return (t?tail:head);
    }
    if(chkdir(mid,s,arr)==dir) (dir==1?tail:head)=mid;
    else (dir==1?head:tail)=mid+(dir==1?1:-1);
  }
  if(chkdir(head,s,arr)==dir)return head;
  else return (dir==1?n:-1);
}

int main(){
  int n,q,l,r;
  string s;
  cin>>n>>q>>s;
  vector<pcc> v(q);
  for(int i=0;i<q;++i)cin>>v[i].first>>v[i].second;
  l=binsrc(-1,s,v);
  r=binsrc(1,s,v);
  cout<<r-l-1<<endl;
  return 0;
}

Measured memory_bytes: 1924
n = int(input())
xyp = [list(map(int,input().split())) for i in range(n)]

def caldp(a):
    n = len(a)
    a.sort()
    dp = [[float("INF")]*(n+1) for i in range(n+1)]
    dp[0][0] = 0
    for l in range(n):
        for r in range(l+1,n+1):
            now = float("INF")
            for k in range(l,r):
                count = 0
                for i in range(l,r):
                    count += abs(a[i][0]-a[k][0])*a[i][1]
                    if count >= now:
                        break
                now = min(now,count)
            for j in range(n):
                dp[r][j+1] = min(dp[r][j+1],dp[l][j]+now)

            now = 0
            for i in range(l,r):
                now += abs(a[i][0])*a[i][1]
            for j in range(n+1):
                dp[r][j] = min(dp[r][j],dp[l][j]+now)

    res = [float("INF")]*(n+1)
    for i in range(n+1):
        res[i] = dp[-1][i]
    return res

ans = [float("INF")]*(n+1)

for s in range(1<<n):
    lx = []
    ly = []
    for i in range(n):
        if s >> i & 1:
            lx.append((xyp[i][0],xyp[i][2]))
        else:
            ly.append((xyp[i][1],xyp[i][2]))
    lx = caldp(lx)
    ly = caldp(ly)
    for i in range(len(lx)):
        for j in range(len(ly)):
            ans[i+j] = min(ans[i+j],lx[i]+ly[j])

for i in ans:
    print(i)

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


int main(){

  int n;
  cin>>n;
  unordered_map<string,int> umap;

  for(int i=0;i<n;i++){
    string s;
    cin>>s;
    umap[s]++;
  }

  // for( auto i : umap){
  //   cout<<i.first<<" "<<i.second<<"\n";
  // }
   
    cout<<umap.size()<<"\n";


  return 0;
}

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

int main() {
    int N;
    cin >> N;
    vector<int> s1(N+1), s2(N+1);
    s1[0] = 0;
    for(int i = 1; i <= N; i++){
        cin >> s1[i];
        s1[i] += s1[i-1];
    }
    s2[0] = 0;
    for(int i = 1; i <= N; i++){
        cin >> s2[i];
        s2[i] += s2[i-1];
    }

    int ans = -1;
    for(int i = 1; i <= N; i++) {
        ans = max(ans, s1[i] + s2[N] - s2[i-1]);
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<iomanip>
#include<cmath>
#include<string>
#include<cstring>
#include<vector>
#include<list>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<stack>
using namespace std;
typedef long long ll;
#define fi first
#define se second
#define mp make_pair
#define mt make_tuple
#define pqueue priority_queue
const int inf=1e9+7;
const ll mod=1e9+7;
const ll mod1=998244353;
const ll big=1e18;
const double PI=2*asin(1);

ll gcd(ll a, ll b) {
  ll v0=a, v1=b, v2=v0%v1;
  while(v2>0) {
    v0 = v1;
    v1 = v2;
    v2 = v0%v1;
  }
  return v1;
}

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

int main() {
  ll N, M;
  cin>>N>>M;
  vector<ll> A(N), B(N);
  for(int i=0;i<N;++i) cin>>A[i];
  sort(A.begin(), A.end());
  for(int i=0;i<N;++i) B[i] = A[i]/2;
  ll tmp;
  if(N==1) tmp = B[0];
  else tmp = lcm(B[0], B[1]);
  for(int i=2;i<N;++i) tmp = lcm(tmp, B[i]);
  bool can = true;
  for(int i=0;i<N;++i) {
    if(tmp/B[i]%2==0) can = false;
  }
  if(tmp>M || !can) cout<<0<<endl;
  else cout<<1+(M-tmp)/(2*tmp)<<endl;
}



Measured memory_bytes: 4796
#include <bits/stdc++.h>
using namespace std;
const int maxn = 100100;
int uf[maxn];
int find(int x){
	if(x == uf[x]) return x;
	return uf[x] = find(uf[x]);
}
int main(){
	iota(uf, uf + maxn, 0);
	int n; cin >> n;
	vector<pair<int,int>> a(n), b(n);
	for(int i = 0; i < n; i++){
		int x; cin >> x;
		a[i] = {x, i};
	}
	for(int i = 0; i < n; i++){
		int x; cin >> x;
		b[i] = {x, i};
	}
	auto bad = [&](){
		cout << "No" << endl;
		exit(0);
	};
	sort(a.begin(), a.end());
	sort(b.begin(), b.end());
	for(int i = 0; i < n; i++){
		if(a[i].first > b[i].first) bad();
		uf[find(a[i].second)] = find(b[i].second);
	}
	int cmps = 0;
	for(int i = 0; i < n; i++) cmps += i == find(i);
	if(cmps > 1){
		cout << "Yes" << endl;
	} else {
		int can = 0;
		for(int i = n - 1; i >= 1; i--){
			if(a[i].first <= b[i - 1].first) can = 1;
		}
		if(can) cout << "Yes" << endl;
		else bad();
	}
	return 0;
}


Measured memory_bytes: 3712
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using vb = vector<bool>;
using vc = vector<char>;
using vs = vector<string>;
using vvi = vector<vector<int>>;
using vvc = vector<vector<char>>;
using pii = pair<int, int>;
#define rep(i,n) for(int i=0; i<(int)(n);i++)

void port(long &a,long &b){
  if(a <= b){
    b = a;
  }
  return;
}

int main(){
  long n,a,b,c,d,e;
  cin >> n >> a >> b >> c >> d >> e;
  port(a,b);
  port(b,c);
  port(c,d);
  port(d,e);
  long t = (n+e-1)/e;
  t += 4;
  cout << t << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
	int N,A,B,C=0,D=0,E=0,x;
	scanf("%d%d%d",&N,&A,&B);
	while(N--){
		scanf("%d",&x);
		if(x <= A)C++;else
		if(x > B)D++;else
			E++;
	}
	printf("%d\n",min(C,min(D,E)));
	return 0;
}


Measured memory_bytes: 256
N,M,Q= list(map(int, input().split()))
LR = [list(map(int, input().split())) for _ in range(M)]
PQ = [list(map(int, input().split())) for _ in range(Q)]

import numpy as np

trains = np.array([[0]*N for _ in range(N)])

for l, r in LR:
  trains[l-1][r-1] +=1

# 二次元累積和
row_sum = trains.cumsum(axis=1)
matrix_sum = row_sum.cumsum(axis=0)

for p,q in PQ:
  if p==1:
    print(matrix_sum[q-1, q-1])
  else:
    print(matrix_sum[q-1,q-1] - matrix_sum[p-2,q-1])

Measured memory_bytes: 82788
// ALDS1_5_B.cpp
// Divide and Conquer - Merge Sort
// ???????????????
// 1. ?????????L???R????????°??´???????????????????????¨???
// 2. ??????????¬???°??¶??????cnt++??????if??????if?????????????????¨?????????
// 3. vector????§??????????????????°???vector<int> nums'(n)'!

#include <iostream>
#include <vector>
using namespace std;
long long cnt = 0;
const int SENTINEL = 1E9 + 5;
void trace(vector<int>& nums)
{
	for (int i = 0; i < nums.size(); i++) {
		if (i > 0) cout << " ";
		cout << nums[i];
	}
	cout << endl;
}

void merge(vector<int>& nums, int left, int mid, int right)
{
	vector<int> L(nums.begin() + left, nums.begin() + mid);
	vector<int> R(nums.begin() + mid, nums.begin() + right);
	L.push_back(SENTINEL);
	R.push_back(SENTINEL);
	int i = 0;
	int j = 0;
	for (int k = left; k < right; k++) {
		if (L[i] <= R[j]) {
			nums[k] = L[i++];
		}
		else {
			nums[k] = R[j++];
			cnt += L.size() - 1 - i;
		}
	}
}

void MergeSort(vector<int>& nums, int left, int right)
{
	if (left + 1 >= right) return;
	int mid = left + (right - left) / 2;
	MergeSort(nums, left, mid);
	MergeSort(nums, mid, right);
	merge(nums, left, mid, right);
}

// FILE *stream1, *stream2;

int main()
{
//	freopen_s(&stream1, "in.txt", "r", stdin);
//	freopen_s(&stream2, "out.txt", "w", stdout);
	int n;
	cin >> n;
	vector<int> nums(n);
	for (int i = 0; i < n; i++) {
		cin >> nums[i];
	}
	MergeSort(nums, 0, n);
//	trace(nums);
	cout << cnt << endl;
	return 0;
}

Measured memory_bytes: 5240
#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<map>
#include<algorithm>
#include<cmath>
using namespace std;
const int maxn=1e5+50;
int n,h,th,wi,a,b,cnt;

struct data{
    int num,l,r;
}num[maxn<<1];


bool cmp(data a,data b){
    return a.num>b.num;
}

int main(){
    while(cin>>n){
        cin>>h;
        cnt=0;
        for(int i=0;i<(n<<1);i++){
            cin>>a>>b;
            num[i].l=1;
            num[i].num=a;
            num[++i].r=1;
            num[i].num=b;
        }
        sort(num,num+(n<<1),cmp);
        for(int i=0;i<(n<<1);i++){
            if(num[i].r){
                h-=num[i].num;//5
                cnt++;//1
                if(h<=0)
                    break;
                //cout<<"cnta:"<<cnt<<endl;
            }
            else if(num[i].l){
                cnt+=ceil((h*1.0)/num[i].num);
                //cout<<"cnt:"<<cnt<<"h:"<<h<<"num:"<<ceil(h/num[i].num)<<endl;
                break;
            }
        }
        cout<<cnt<<endl;
    }
    return 0;
}


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



int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    int n,k;
    cin>>n;

    for(k=2;k<450;k++){
        if(n==k*(k+1)/2)break;
    }
    if(n==1){
        cout<<"Yes"<<endl;
        cout<<2<<endl;
        cout<<1<<' '<<1<<endl;
        cout<<1<<' '<<1<<endl;
        return 0;
    }

    if(k==450){
        cout<<"No"<<endl;
        return 0;
    }
    
    cout<<"Yes"<<endl;
	cout<<k+1<<endl;
  
    vector<vector<int>>s(k+3);
    int a=1;
	
  	
    rep(i,k)forx(j,i+1,k+1){
        s[i].push_back(a);
        s[j].push_back(a);
        a++;
    }
    rep(i,k+1){
        cout<<k<<' ';
        for(auto x:s[i]){
            cout<<x<<' ';
        }
        cout<<endl;
    }
    return 0;
}


Measured memory_bytes: 2304
//#include<bhaai.h>
#include<bits/stdc++.h>
using namespace std;
#define to int64_t
#define mo 1000000007
#define fr(a,e) for(int i=a;i<=e;i++)
#define yah_faster_baby ios_base::sync_with_stdio(0);cin.tie(0);

to ans,n,k,m,r[100005],p[100005],a,b;
//vector <int> v[100005];
//char s[100005];
double d,x;
int main()
 {  yah_faster_baby
    cin>>n>>d;
    while(n--)
    {cin>>a>>b;
     x=(double)sqrt(pow(a,2)+pow(b,2));
     if(x<=d)
     ++ans;
    }
    cout<<ans<<"\n";
	return 0;
}



Measured memory_bytes: 3800
using System;
using System.Collections;
using System.Collections.Generic;
using System.Text;
using System.Linq;
using static MyIO;


public class D
{
	public static void Main()
	{
		int N = GetInt();
		int numToEat = 0;
		bool[] exist = new bool[100001]; 
		for(int i = 0; i < N; i++)
		{
			int A = GetInt();
			if(exist[A])
			{
				numToEat++;
			}
			else
			{
				exist[A] = true;
			}
		}

		int numRest = N - numToEat;
		Console.WriteLine((numToEat % 2 == 0) ? numRest : numRest - 1);
	}
}


public static class MyIO
{
	private static string[] args = null;
	private static int num = -1;
	private static int used = -1;

	private static string getArg()
	{
		if(used == num)
		{
			args = Console.ReadLine().Split(' ');
			num = args.Length;
			used = 0;
		}
		return args[used++];
	}

	public static int GetInt(){ return int.Parse(getArg()); }
	public static long GetLong(){ return long.Parse(getArg()); }
	public static double GetDouble(){ return double.Parse(getArg()); }
	public static string GetString(){ return getArg(); }
}





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

const int INF = 100100100;
const int MOD = (int)1e9 + 7;
typedef long long ll;
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) for (int i = 0; i < (n); ++i)

int main() {
  int a,b,c;
	cin >> a >> b >> c;
	string ans = "win";
	if (a+b+c>21) ans = "bust";
  cout << ans << endl;
}


Measured memory_bytes: 3592
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)
#define sz(x) int(x.size())
#define pb push_back
#define eb emplace_back
using ll=long long;
using P = pair<int,int>;
#define chmax(x,y) x = max(x,y)
#define chmin(x,y) x = min(x,y)
const ll MOD=1000000007,MOD2=998244353;



int main() {
    int N,K;
    cin>>N>>K;
    vector<ll> V(N);
    vector<P> gomi(N);
    rep(i,N){
        cin>>V.at(i);
        gomi.at(i).first=V.at(i);
        gomi.at(i).second=i;
    }
    sort(gomi.begin(),gomi.end());//捨てるべきやつ
    vector<ll> lsum(N+1),rsum(N+1);//左右からi個の和
    rep(i,N){
        lsum.at(i+1)=lsum.at(i)+V.at(i);
        rsum.at(i+1)=rsum.at(i)+V.at(N-i-1);
    }
    ll ans=0;
    rep(cat,K+1){//cat個とってK-cat個捨てる
        ll now=0;
        int rel=K-cat;
        if(cat>=N){
            now=lsum.at(N);
            rep(i,min(rel,N)){
                if(gomi.at(i).first<0){now-=gomi.at(i).first;}
            }
            chmax(ans,now);
        }
        else{
            ll nownow=0;
            rep(left,cat+1){//左からleft個、右からcat-left個
                nownow=lsum.at(left)+rsum.at(cat-left);
                int count=0;
                rep(i,N){
                    if(gomi.at(i).second<left || gomi.at(i).second>N-1-cat+left){
                        if(count<rel && gomi.at(i).first<0){
                            nownow-=gomi.at(i).first;
                            count++;
                        }
                    }
                }
                //chmax(now,nownow);
                chmax(ans,nownow);
            }
            //chmax(ans,now);
        }
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 256