akhauriyash/Code-Regression huggingface dataset:
#pragma region header
#include <bits/stdc++.h>
using namespace std;

#define CPP_CAT(x,y) CPP_CAT_I(x,y)
#define CPP_CAT_I(x,y) x ## y
//#define CPP_STR(x) CPP_STR_I(x)
//#define CPP_STR_I(args...) #args
//#define ASSERT(expr...) assert((expr))

using i8 = int8_t;
using u8 = uint8_t;
using i16 = int16_t;
using u16 = uint16_t;
using i32 = int32_t;
using u32 = uint32_t;
using i64 = int64_t;
using u64 = uint64_t;
using f32 = float;
using f64 = double;
//using f80 = __float80;

constexpr i64 INF = 1'010'000'000'000'000'017LL;
constexpr i64 MOD = 1'000'000'007LL;
constexpr f64 EPS = 1e-12;
constexpr f64 PI = 3.14159265358979323846;
constexpr char EL[] = "\n";

#define FOR(i, start, end) for(i64 i = (start), CPP_CAT(i,xxxx_end)=(end); i < CPP_CAT(i,xxxx_end); ++i)
#define REP(i, n) FOR(i, 0, n)
#define all(x) (x).begin(),(x).end()
#define ALL(f,c,...) (([&](decltype((c)) cccc) { return (f)(std::begin(cccc), std::end(cccc), ## __VA_ARGS__); })(c))
#define UNIQUE(x) (x).erase(unique(all(x)), (x).end());
#define REPIT(x) for(auto it=(x).begin(), end=(x).end(); it!=end; ++it)
#define perm(c) sort(all(c)); for(bool c##p=1;c##p;c##p=next_permutation(all(c)))

template<typename T = i64>
T IN() { T x; cin >> x; return (x); }

template<typename C>
i64 SIZE(const C& c) { return static_cast<i64>(c.size()); }
template<typename T, size_t N>
i64 SIZE(const T(&)[N]) { return static_cast<i64>(N); }

template<typename T, typename U, typename Comp = less<>>
bool chmax(T& xmax, const U& x, Comp comp = {}) {
	if (comp(xmax, x)) {
		xmax = x;
		return true;
	}
	return false;
}
template<typename T, typename U, typename Comp = less<>>
bool chmin(T& xmin, const U& x, Comp comp = {}) {
	if (comp(x, xmin)) {
		xmin = x;
		return true;
	}
	return false;
}

void print() {
  cout << EL;
}
template <class Head, class... Tail>
void print(Head&& head, Tail&&... tail) {
  cout << head;
  if (sizeof...(tail) != 0) cout << " ";
  print(forward<Tail>(tail)...);
}
template <class T>
void print(vector<T> &vec) {
  for (auto& a : vec) {
	cout << a;
	if (&a != &vec.back()) cout << " ";
  }
  cout << EL;
}
template <class T>
void print(vector<vector<T>> &df) {
  for (auto& vec : df) {
	print(vec);
  }
}

struct ProconInit {
	static constexpr int IOS_PREC = 15;
	static constexpr bool AUTOFLUSH = false;

	ProconInit() {
		cin.tie(nullptr);
		ios::sync_with_stdio(false);
		cout << fixed << setprecision(IOS_PREC);
		if (AUTOFLUSH)
			cout << unitbuf;
	}
} PROCON_INIT;
#pragma endregion

signed solve()
{
	auto n = IN();
	if (n == 1)
	{
		print(1);
		return 0;
	}
	i64 l = 1, lm1 = 1, lm2 = 2;
	FOR(i, 2, n + 1)
	{
		i64 temp = l;
		l = lm1 + lm2;
		lm2 = lm1;
		lm1 = l;
	}
	print(l);
	return 0;
}

#ifndef LOCALCODE
signed main()
{
	return solve();
}
#endif


Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<vector>
#include<map>
#include<set>
#include<string>
#include<algorithm>
#include<math.h>
#include<numeric>
#include<iomanip>
#include<queue>
#include<functional>

using namespace std;

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

//const ll INF = 1e15;
const ll MOD = 1e9 + 7;

int main(){
	ll N, H;
	cin >> N >> H;
	vll A, B;
	ll i, j;
	for (i = 0; i < N; i++){
		ll a, b;
		cin >> a >> b;
		A.push_back(a);
		B.push_back(b);
	}
	ll a_max = *max_element(A.begin(), A.end());
	vll B_new;
	for (auto b : B){
		if (b > a_max){
			B_new.push_back(b);
		}
	}
	sort(B_new.begin(), B_new.end(), greater<ll>());
	ll B_sum = accumulate(B_new.begin(), B_new.end(), 0);
	ll ans = 0;
	if (B_sum >= H){
		i = 0;
		while (H > 0){
			H -= B_new[i];
			i++;
			ans++;
		}
	}
	else{
		ans = (H - B_sum) / a_max;
		if ((H - B_sum) % a_max != 0){
			ans++;
		}
		i = 0;
		H -= a_max * ans;
		while (H > 0){
			H -= B_new[i];
			i++;
			ans++;
		}
	}
	cout << ans << endl;
	return 0;
}

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

const int N = 2e5 + 7;

typedef long long ll;

const ll mod = 998244353;

ll tree[4 * N], n, q, a[N], fn[N], flag[4 * N];
ll ksm(ll x, ll y) {
    ll base = 1;
    x = x % mod;
    while (y) {
        if (y & 1) {
            base = base * x;
            base %= mod;
        }
        x = x * x;
        x %= mod;
        y = y / 2;
    }
    return base;
}

#define m (l + r) / 2
#define lson 2 * node
#define rson 2 * node + 1

void build(int l, int r, int node) {
    flag[node] = -1;
    if (l == r) {
        tree[node] =  ksm(10, n - l);
        tree[node] %= mod;
        return;
    }
    build(l, m, lson);
    build(m + 1, r, rson);
    tree[node] = (tree[lson] + tree[rson]) % mod;
}

void push_down(int node, int l, int r) {
    if (flag[node] != -1) {
        int r1 = n - l;
        int l1 = n - m;
        ll cnt = (fn[r1] - fn[l1 - 1] + mod) % mod;
        tree[lson] = cnt * flag[node] % mod;
        r1 = n - (m + 1);
        l1 = n - r;
        cnt = (fn[r1] - fn[l1 - 1] + mod) % mod;
        tree[rson] = cnt * flag[node] % mod;
        flag[lson] = flag[rson] = flag[node];
        flag[node] = -1;
    }
}

void update(ll v, int ql, int qr, int l, int r, int node) {
    if (ql <= l && qr >= r) {
        int r1 = n - l;
        int l1 = n - r;
        //cout << "l " << l1 << " " << r1 << endl;
        ll cnt = (fn[r1] - fn[l1 - 1] + mod) % mod;
       // cout << fn[r1] << endl;
        tree[node] = cnt * v;
        tree[node] %= mod;
        flag[node] = v;
        return;
    }
    push_down(node, l, r);
    if (ql <= m) update(v, ql, qr, l, m, lson);
    if (qr > m) update(v, ql, qr, m + 1, r, rson);
    tree[node] = (tree[lson] + tree[rson]) % mod;
}


int main() {
    scanf("%lld %lld", &n, &q);
    fn[0] = 1;
    for (int i = 1; i <= n; i++) {
        fn[i] = ksm(10, i);
        fn[i] = fn[i - 1] + fn[i];
        fn[i] %= mod;
    }
    build(1, n, 1);
  //  cout << tree[1] << endl;
    while (q--) {
        ll l, r, v;
        scanf("%lld %lld %lld", &l, &r, &v);
        update(v, l, r, 1, n, 1);
        printf("%lld\n", tree[1]);
    }

}

Measured memory_bytes: 13524
#include <set>
#include <string>
#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
    string S; int n;
    
    set<string> T;
    
    scanf("%d", &n);
    
    while(n--)
    {
        cin >> S;
        
        int c = 0;
        
        for(int i = 1; i < S.size(); i++)
        {
            c += (S[i - 1] == S[i] ? 1 : 0);
        }
        
        if(c + 1 == S.size())
        {
            printf("1\n");
        }
        else
        {
            T.clear();
            
            for(int j = 1; j < S.size(); j++)
            {
                string A = S.substr(0, j);
                string B = S.substr(j, S.size() - j);
                
                string C = A; reverse(C.begin(), C.end());
                string D = B; reverse(D.begin(), D.end());
                
                T.insert(A + B);
                T.insert(B + A);
                T.insert(A + D);
                T.insert(D + A);
                T.insert(C + B);
                T.insert(B + C);
                T.insert(C + D);
                T.insert(D + C);
            }
            
            printf("%d\n", T.size());
        }
    }
    
    return 0;
}

Measured memory_bytes: 3364
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
using namespace std;

int main()
{
	int n;
	cin >> n;
	vector<long long> v(n);
	for (int i = 0; i < n; i++) {
		cin >> v[i];
	}
	unordered_set<long long> s;
	for (int i = 0; i < n; i++) {
		if (s.find(v[i]) == s.end()) {
			s.insert(v[i]);
		}
		else {
			s.erase(v[i]);
		}
	}
	cout << s.size() << endl;
}

Measured memory_bytes: 5156
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
set<int> h[303030], w[303030]; // 爆破対象: 行方向, 列方向.

int main() {
    
    // 1. 入力情報取得.
    int H, W, M;
    int mhCnt = 0, mwCnt = 0; // 爆破対象の最大数(行方向, 列方向).
    scanf("%d %d %d", &H, &W, &M);
    rep(i, M){
        int a, b;
        scanf("%d %d", &a, &b);
        a--, b--;
        h[a].insert(b);
        w[b].insert(a);
        mhCnt = max(mhCnt, (int)h[a].size());
        mwCnt = max(mwCnt, (int)w[b].size());
    }
    
    // 2. 最大数を持つ行, 列 を 集約.
    set<int> mhSet, mwSet;
    rep(i, 303030){
        if(mhCnt == h[i].size()) mhSet.insert(i); // 行番号.
        if(mwCnt == w[i].size()) mwSet.insert(i); // 列番号.
    }
    
    // 3. 最大数を計算.
    int ans = mhCnt + mwCnt - 1;
    for(auto &p : mhSet){
        bool ok = false;
        for(auto &q : mwSet){
            // 列方向の最大数に該当する 列番号 q で, 行方向の最大数を取る 行番号 p を 含まない
            // ものが見つかった場合は, 終了.
            if(w[q].count(p) == 0){
                ans++;
                ok = true;
                break;
            }
        }
        if(ok) break;
    }
    
    // 4. 出力.
    printf("%d\n", ans);
    return 0;
    
}

Measured memory_bytes: 88248
import copy
n,m = map(int,input().split())
s = list(map(int,input().split()))
t = list(map(int,input().split()))
dp = [0 for i in range(max(n,m))]
mod = 10**9+7
if n > m:
    a = s
    b = t
else:
    a = t
    b = s
    c = copy.copy(n)
    n = copy.copy(m)
    m = copy.copy(c)
l = []
for i in range(m):
    now = b[i]
    bl = []
    for j in range(n):
        if now == a[j]:
            bl.append(j)
    l.append(bl)
for i in range(m):
    if len(l[i]) > 0:
        dp2 = copy.copy(dp)
        now1 = 0
        k = 0
        k1 = len(l[i])
        count = 0
        while k < k1:
            if now1 == l[i][k]:
                dp[now1] += 1
                dp[now1] += count
                dp[now1] %= mod
                k += 1
            count += dp2[now1]
            count %= mod
            now1 += 1
        #print(dp)
print((sum(dp)+1)%mod)

Measured memory_bytes: 74844
h, w = map(lambda x: int(x)+2, input().split())
MAZE = ['#'*w]
for _ in range(h-2):
    MAZE.append('#'+input()+'#')
else:
    MAZE.append('#'*w)

L = [[0]*w for _ in range(h)]
R = [[0]*w for _ in range(h)]
U = [[0]*w for _ in range(h)]
D = [[0]*w for _ in range(h)]

LAMP = [[0]*w for _ in range(h)]

for i in range(1, h-1):
    for j in range(1, w-1):
        if MAZE[i][j] == '#':
            continue
        L[i][j+1] = L[i][j]+1

for i in range(1, h-1):
    for j in reversed(range(1, w-1)):
        if MAZE[i][j] == '#':
            continue
        R[i][j-1] = R[i][j]+1

for j in range(1, w-1):
    for i in range(1, h-1):
        if MAZE[i][j] == '#':
            continue
        U[i+1][j] = U[i][j]+1

for j in range(1, w-1):
    for i in reversed(range(1, h-1)):
        if MAZE[i][j] == '#':
            continue
        D[i-1][j] = D[i][j]+1

ans = 0
for i in range(1, h-1):
    for j in range(1, w-1):
        if MAZE[i][j] == '#':
            continue
        LAMP[i][j] = L[i][j]+R[i][j]+U[i][j]+D[i][j]+1
        ans = max(ans, LAMP[i][j])

print(ans)


Measured memory_bytes: 212100
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
#define int ll
int B[82][82],A[82][82];
int h,w;
bool dp[81][81][12801];
int32_t main()
{
	#ifndef ONLINE_JUDGE
		freopen("in","r",stdin);
		freopen("out","w",stdout);
	#endif
	cin>>h>>w;
	for(int i=1;i<=h;i++)
		for(int j=1;j<=w;j++)
			cin>>A[i][j];

	for(int i=1;i<=h;i++)
		for(int j=1;j<=w;j++)
			cin>>B[i][j];


	dp[1][1][abs(A[1][1]-B[1][1])]=1;
	int d1,d2;
	for(int i=1;i<=h;i++)
	{
		for(int j=1;j<=w;j++)
		{

			for(int k=0;k<=12800;k++)
			{
				if(dp[i][j][k])
				{
					if(i+1<=h)
					{
						d1=abs(A[i+1][j]-B[i+1][j]);
						d2=k+d1;
						dp[i+1][j][d2]=1;
						d2=abs(k-d1);
						dp[i+1][j][d2]=1;
					}
					if(j+1<=w)
					{
						d1=abs(A[i][j+1]-B[i][j+1]);
						d2=k+d1;
						dp[i][j+1][d2]=1;
						d2=abs(k-d1);
						dp[i][j+1][d2]=1;
					}
				}
			}


		}
	}

	int ans=1e18;
	for(int i=0;i<=12800;i++)
	{
		if(dp[h][w][i]){ans=i;break;}
	}
	cout<<ans;
	

}

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

#define REP(i, n, N) for(ll i=(n); i<(N); i++)
#define RREP(i, n, N) for(ll i=(N-1); i>=(n); i--)
#define LREP(lst,itr) for(auto itr = lst.begin(); itr != lst.end(); ++itr)
#define CK(n, a, b) ((a)<=(n)&&(n)<(b))
#define ALL(v) (v).begin(),(v).end()
#define MCP(a, b) memcpy(b,a,sizeof(b))
#define P(s) cout<<(s)<<endl
#define P2(a, b) cout<<(a)<<" "<<(b)<<endl
#define V2(T) vector<vector<T>>
typedef long long ll;
using namespace std;
const ll MOD = 1e9 + 7;
const ll INF = 1e18;

ll gcd(ll A,ll B){
    if(A<B) swap(A,B);
    return (B==0 ? A : gcd(B,A%B));
}

int main(){
    ll p,q,tar,ans=1;
    cin >> p >> q;

    tar = q/gcd(q,p);

    for(ll i=2;i*i<=tar;i++){
        if(tar%i==0){
            ans*=i;
            while(tar%i==0) tar/=i;
        }
    }
    cout << ans * tar << endl;
}


Measured memory_bytes: 3116
#include<bits/stdc++.h>
using namespace std;
int main(){
	string s;
	cin>>s;
	if(s=="Sunny") cout<<"Cloudy"<<endl;
	if(s=="Cloudy") cout<<"Rainy"<<endl;
	if(s=="Rainy") cout<<"Sunny"<<endl;
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#ifdef LOCAL_DEBUG
  #include "LOCAL_DEBUG.hpp"
#endif
#define int long long

signed main(){

  int n, m; cin >> n >> m;
  string s; cin >> s;

  vector<int> pos(n+1, -1);
  int left = 0;
  queue<int> q;
  for(int i = 0; i <= n; i++){
    if(s[i] == '1') continue;
    q.push(i);
    if(i - left <= m){
      pos[i] = left;
    }else {
      while(i - left > m){
        if(q.empty()) break;
        left = q.front();
        q.pop();
      }
      pos[i] = left;
    }
  }

  vector<int> dp(n+1, 1LL << 60);
  dp[n] = 0;
  vector<int> ans;
  int now = n;
  while(now != 0){
    if(s[now] == '1' || now == pos[now]){
      cout << -1 << endl;
      return 0;
    }
    ans.push_back(now - pos[now]);
    now = pos[now];
  }
  reverse(ans.begin(),ans.end());

  for(int p : ans){
    cout << p << " ";
  }
  cout << endl;

  return 0;
}


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

using namespace std;

#define pb push_back
#define mk make_pair
#define mod 1000000007
#define ff first
#define ss second

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

ll modpow(ll a, ll b){

    ll ans=1;
    while(b){
        if(b&1){
            ans=(ans*a)%mod;
        }
        a=(a*a)%mod;
        b=b/2;
    }
    return ans;
}

int main(){

    cin.tie(0);
    ios::sync_with_stdio(false);

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

    int a,b;
    cin>>a>>b;

    string u;
    cin>>u;

    if(u == s) a--;
    if(u == t) b--;

    cout<<a<<" "<<b<<endl;
    

}


Measured memory_bytes: 256
package main

import (
	"bufio"
	"container/heap"
	"fmt"
	"os"
	"sort"
	"strconv"
)

const (
	initialBufSize = 100000
	maxBufSize     = 10000000
)

var (
	sc = bufio.NewScanner(os.Stdin)
	wt = bufio.NewWriter(os.Stdout)
)

func next() string {
	sc.Scan()
	return sc.Text()
}

func nextInt() int {
	i, _ := strconv.Atoi(next())
	return i
}

func puts(a ...interface{}) {
	fmt.Fprintln(wt, a...)
}

type Job struct {
	a, b int
}

type Jobs []Job

func (a Jobs) Len() int           { return len(a) }
func (a Jobs) Swap(i, j int)      { a[i], a[j] = a[j], a[i] }
func (a Jobs) Less(i, j int) bool { return a[i].a < a[j].a }

type PriorityQueue []int

func (pq PriorityQueue) Len() int {
	return len(pq)
}

func (pq PriorityQueue) Less(i, j int) bool {
	return pq[i] > pq[j]
}

func (pq PriorityQueue) Swap(i, j int) {
	pq[i], pq[j] = pq[j], pq[i]
}

func (pq *PriorityQueue) Push(x interface{}) {
	*pq = append(*pq, x.(int))
}

func (pq *PriorityQueue) Pop() interface{} {
	old := *pq
	n := len(old)
	x := old[n-1]
	*pq = old[0 : n-1]
	return x
}

func main() {
	sc.Split(bufio.ScanWords)
	sc.Buffer(make([]byte, initialBufSize), maxBufSize)
	defer wt.Flush()

	n, m := nextInt(), nextInt()
	jobs := make(Jobs, n)
	for i := 0; i < n; i++ {
		a, b := nextInt(), nextInt()
		jobs[i] = Job{a, b}
	}
	sort.Sort(jobs)

	ans := 0
	pq := make(PriorityQueue, 0)
	for day, id := m-1, 0; day >= 0; day-- {
		for id < n && day+jobs[id].a <= m {
			heap.Push(&pq, jobs[id].b)
			id++
		}
		if pq.Len() > 0 {
			ans += heap.Pop(&pq).(int)
		}
	}

	puts(ans)
}


Measured memory_bytes: 7168
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <string>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int mod = 1000000007;

int main() {
    ios::sync_with_stdio(false);
    int n, m, d, q, l, r, a[328][328] = {};
    pii b[100005] = {};
    vector<int> c[100005] = {};
    cin >> n >> m >> d;
    for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) cin >> a[i][j], a[i][j]--, b[a[i][j]] = {i, j};
    for (int i = 0; i < d; i++) {
        c[i].push_back(0);
        for (int j = i + d; j < n * m; j += d) {
            c[i].push_back(c[i].back());
            c[i].back() += abs(b[j].first - b[j - d].first) + abs(b[j].second - b[j - d].second);
        }
    }
    cin >> q;
    while (q--) {
        cin >> l >> r; l--; r--;
        cout << c[l % d][r / d] - c[l % d][l / d] << '\n';
    }
}


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

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<int, pii> pipii;
typedef pair<pii, int> piipi;
typedef pair<pii, pii> piipii;

#define mp make_pair
#define fi first
#define se second
#define all(a) (a).begin(), (a).end()
#define sz(a) (int)(a).size()
#define eb emplace_back

int x[1005], y[1005], r[1005];
double dist[1005][1005];
double dp[1005];
bool vis[1005];
int main(){
    int xs, ys, xt, yt;
    scanf("%d%d%d%d", &xs, &ys, &xt, &yt);
    int n;
    scanf("%d", &n);   
    for(int i=1;i<=n;i++) scanf("%d%d%d", &x[i], &y[i], &r[i]);
    x[0] = xs;
    y[0] = ys;
    x[n+1] = xt;
    y[n+1] = yt;
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            dist[i][j] = dist[j][i] = sqrt((x[i]-x[j])*1.0*(x[i]-x[j]) + (y[i]-y[j])*1.0*(y[i]-y[j]));
            dist[i][j] = dist[j][i] = dist[i][j] - r[i] - r[j];
            if(dist[i][j] <= 0) dist[i][j] = dist[j][i] = 0;
        }
    }
    for(int i=1;i<=n;i++){
        dist[i][0] = dist[0][i] = sqrt((x[i]-x[0])*1.0*(x[i]-x[0]) + (y[i]-y[0])*1.0*(y[i]-y[0])) - r[i];
        dist[i][n+1] = dist[n+1][i] = sqrt((x[i]-x[n+1])*1.0*(x[i]-x[n+1]) + (y[i]-y[n+1])*1.0*(y[i]-y[n+1])) - r[i];
        if(dist[i][0] <= 0) dist[i][0] = dist[0][i] = 0;
        if(dist[i][n+1] <= 0) dist[i][n+1] = dist[n+1][i] = 0;
    }
    dist[0][n+1] = dist[n+1][0] = sqrt((x[n+1]-x[0])*1.0*(x[n+1]-x[0]) + (y[n+1]-y[0])*1.0*(y[n+1]-y[0]));

    priority_queue<pair<double, int> > pq;
    pq.push(mp(0, 0));
    dp[0] = 0;
    vis[0] = 1;
    while(!pq.empty()){
        int u = pq.top().second;
        double val = -pq.top().first;
        pq.pop();
        if(val != dp[u]) continue;
        for(int i=0;i<=n+1;i++){
            if(!vis[i] || (vis[i] && dp[i] > dp[u] + dist[u][i])){
                vis[i] = 1;
                dp[i] = dp[u] + dist[u][i];
                pq.push(mp(-dp[i], i));
            }
        }
    }
    printf("%.10lf\n", dp[n+1]);
}

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

inline int64_t in() { int64_t x = 0; cin >> x; return x; }

int main() {
  int n = in();

  vector<int> x(n);
  for (auto &i : x) cin >> i;

  int L = in();

  vector<vector<int>> d(20, vector<int>(n + 1, n));
  for (int i = 0; i < n; ++i) {
    d[0][i] = lower_bound(x.begin(), x.end(), x[i] + L + 1) - x.begin() - 1;
  }

  for (int i = 1; i < 20; ++i) {
    for (int j = 0; j < n; ++j) {
      d[i][j] = d[i - 1][d[i - 1][j]];
    }
  }

  int q = in();
  while (q--) {
    int a = in() - 1, b = in() - 1;
    if (b < a) swap(a, b);

    int ans = 1;
    for (int i = 19; i >= 0; --i) {
      if (d[i][a] < b) {
        ans += (1 << i);
        a = d[i][a];
      }
    }

    cout << ans << endl;
  }
}


Measured memory_bytes: 9080
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mo = 1000000007;
const int Maxn = 2005;
void upd(int & x,int y)
{
	x = (x + y) % mo;
}
int getinv(int x)
{
	if(x == 1)
		return 1;
	return (ll)getinv(mo%x) * (mo - mo/x) % mo;
}
int fac[Maxn * Maxn];
int invf[Maxn * Maxn];
void Init(int n)
{
	fac[0] = 1;
	for(int i=1;i<=n;i++)
		fac[i] = (ll)fac[i-1] * i % mo;
	invf[n] = getinv(fac[n]);
	for(int i=n;i;i--)
		invf[i-1] = (ll)invf[i] * i % mo;
}
int C(int n,int m)
{
	if(m > n)
		return 0;
	return (ll)fac[n] * invf[m] % mo * invf[n-m] % mo;
}
int dp[Maxn][Maxn];
int main()
{
	int n,K;
	cin >> n >> K;
	if(K == 1) {
		cout << 1 << endl;
		return 0;
	}
	Init(n*K + 1);

	dp[0][0] = 1;
	for(int i=0;i<=n;i++)
		for(int j=i;j<=n;j++) {
			if(i != 0)
				upd(dp[i][j] , dp[i-1][j]);
			if(j != 0 && i != j) {
				int t1 = (j-1)*(K-1) + i;
				int t2 = K-2;
				upd(dp[i][j] , (ll)dp[i][j-1] * C(t1+t2 , t1) % mo);
			}
		}
	cout << (ll)dp[n][n] * fac[n] % mo << endl;
	return 0;
}


Measured memory_bytes: 47360
import           Control.Monad
import           Data.List

main :: IO ()
main = do
    [n, m] <- fmap (map read . words) getLine :: IO [Int]
    cs     <- replicateM n $ fmap (map read . words) getLine :: IO [[Int]]
    print . solve m $ cs

solve :: Int -> [[Int]] -> Int
solve m cs = purchase m scs
    where scs = sortOn fst . map (\[a, b] -> (a, b)) $ cs

purchase :: Int -> [(Int, Int)] -> Int
purchase m ((a, b) : cs) | m <= b    = m * a
                         | otherwise = a * b + purchase (m - b) cs
purchase _ [] = 0


Measured memory_bytes: 138620
#include<iostream>
using namespace std;
int N,M,Q,p[509][509],i,j,L,R;
int main(){
  cin>>N>>M>>Q;
  for(i=1;i<=M;i++)cin>>L>>R,p[L][R]++;
  for(i=1;i<=N;i++)for(j=1;j<=N;j++)p[i][j]+=p[i][j-1];
  for(i=1;i<=N;i++)for(j=1;j<=N;j++)p[i][j]+=p[i-1][j];
  for(i=1;i<=Q;i++)cin>>L>>R,cout<<p[R][R]-p[L-1][R]-p[R][L-1]+p[L-1][L-1]<<endl;
  return 0;
}


Measured memory_bytes: 1920
typedef long long ll;
typedef long double ld;
#define mod 1000000007
#define INF 1000000000
#include <bits/stdc++.h>
using namespace std;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	int x, n;
	cin >> x >> n;
	set<int> s;
	for (int i = 0; i < n; ++i) {
		int k;
		cin >> k;
		s.insert(k);
	}
	int index, mn = INF;
	for (int i = x; i >= -1000; --i) {
		if (s.count(i) == 0) {
			if (mn > abs(x - i)) {
				mn = abs(x - i);
				index = i;
				break;
			}
		}
	}
	for (int i = x; i <= 1000; ++i) {
		if (s.count(i) == 0) {
			if (mn > abs(x - i)) {
				mn = abs(x - i);
				index = i;
				break;	
			}
		}
	}
	cout << index << '\n';
	
	return 0;
}


Measured memory_bytes: 3608
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public int minJumps(int[] heights, int K) {
        int n = heights.length;
        int[] memo = new int[n];
        Arrays.fill(memo, -1);
        return dfs(heights, 0, K, memo);
    }
    private int dfs(int[] heights, int currPosition, int K, int[] memo) {
        int n = heights.length;
        if (currPosition >= n - 1) {
            return 0;
        }
        if (memo[currPosition] != -1) {
            return memo[currPosition];
        }
        int result = Integer.MAX_VALUE;
        for (int i = 1; i <= K; i++) {
            if (currPosition + i >= n) {
                break;
            }
            result = Math.min(result, Math.abs(heights[currPosition] - heights[currPosition + i]) + dfs(heights, currPosition + i, K, memo));
        }
        return memo[currPosition] = result;
    }


    public static void main(String[] args)  {
        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
            String[] strs = br.readLine().split(" ");
            int n = Integer.parseInt(strs[0]);
            int K = Integer.parseInt(strs[1]);
            String heightsStr = br.readLine();
            String[] split = heightsStr.split(" ");
          	int[] heights = new int[n];
            for (int i = 0; i < n; i++) {
              	heights[i] = Integer.parseInt(split[i]);
            }
          	Main app = new Main();
            int result = app.minJumps(heights, K);
            System.out.println(result);
        } catch (IOException e) {
            e.printStackTrace();
        }
    }
}


Measured memory_bytes: 55064
#include<bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
#define ll long long
#define rep(i,n) for(int i = 0; i < int(n); i++)
#define vi vector<int>
#define INF (1<<30)-1
using namespace std;
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};
template<class T> inline bool chmax(T &a, const T &b){ if(a<b) { a=b; return 1; } return 0; }
template<class T> inline bool chmin(T &a, const T &b){ if(b<a) { a=b; return 1; } return 0; }

int main(){
  cin.tie(0), ios::sync_with_stdio(false);
  string s; cin >> s;
  stack<char> st;
  rep(i,s.size()){
    if(st.empty()) st.push(s[i]);
    else{
      if(s[i] == 'T' && st.top() == 'S') st.pop();
      else st.push(s[i]);
    }
  }
  cout << st.size();
  cout << "\n";
  return 0;
}


Measured memory_bytes: 3736
def main():
    n,k = map(int,input().split())
    p = list(map(int,input().split()))
    c = list(map(int,input().split()))

    ans=-10**18
    for i in range(n):
        start,count=i,1
        val=c[start]
        while p[start]-1 != i:
            start = p[start]-1
            count += 1
            val += c[start]
        start = i
        if val > 0:
            a = (k//count-1)*val
            ans=max(a,ans)
            num=count+k%count
        else:
            a=0
            num=min(k,count)
        for _ in range(num):
            a += c[start]
            start=p[start]-1
            ans=max(a,ans)
    print(ans)
if __name__ == "__main__":
    main()
    
    

Measured memory_bytes: 73908
#include <cstring>
#include <iostream>

using namespace std;

int main(int argc, char* argv[]) {
  int A[4][3][10];
  int n; cin >> n;

  memset(A, 0, sizeof(A));
  for (int i = 0; i < n; i++) {
    int b, f, r, v; cin >> b >> f >> r >> v;
    A[b-1][f-1][r-1] += v;
  }

  for (int i = 0; i < 4; i++) {
    for (int j = 0; j < 3; j++) {
      for (int k = 0; k < 10; k++) {
	cout << ' ' << A[i][j][k];
      }
      cout << endl;
    }
    if (i != 3)
      cout << "####################" << endl;
  }
  return 0;
}

Measured memory_bytes: 1160
#include <map>
#include <vector>
#include <iostream>
#include <numeric>
#include <utility>
#include <iomanip>
#include <algorithm>
#include <functional>
using namespace std;

#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl
#define EACH(i, s) for (__typeof__((s).begin()) i = (s).begin(); i != (s).end(); ++i)

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
template<class T1, class T2> ostream& operator << (ostream &s, pair<T1,T2> P)
{ return s << '<' << P.first << ", " << P.second << '>'; }
template<class T> ostream& operator << (ostream &s, vector<T> P)
{ for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; }
template<class T> ostream& operator << (ostream &s, vector<vector<T> > P)
{ for (int i = 0; i < P.size(); ++i) { s << endl << P[i]; } return s << endl; }
template<class T1, class T2> ostream& operator << (ostream &s, map<T1,T2> P)
{ EACH(it, P) { s << "<" << it->first << "->" << it->second << "> "; } return s << endl; }



map<int,int> ma;
int N, K;


int main() {
  while (cin >> N >> K) {
	ma.clear();
	for (int i = 0; i < N; ++i) {
	  int a; cin >> a;
	  ma[a]++;
	}
	vector<int> alt;
	for (map<int,int>::iterator it = ma.begin(); it != ma.end(); ++it) {
	  alt.push_back(it->second);
	}
	sort(alt.begin(), alt.end(), greater<int>());
	int res = 0;
	for (int i = 0; i < min(K, (int)alt.size()); ++i) res += alt[i];
	cout << N - res << endl;
  }
}


















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

int N, M, Q;
vector<long long> a, b, c, d;

long long score(const vector<int> &A) {
  long long res = 0;
  for (int i = 0; i < Q; i++)
    if (A[b[i]] - A[a[i]] == c[i]) res += d[i];
  return res;
}

long long dfs(vector<int> &A) {
  if (A.size() == N) {
    return score(A);
  }
  long long res = 0;
  int prev_last = (A.empty() ? 0 : A.back());
  for (int add = prev_last; add < M; add++) {
    A.push_back(add);
    res = max(res, dfs(A));
    A.pop_back();
  }
  return res;
}

int main() {
  cin >> N >> M >> Q;
  a.resize(Q);
  b.resize(Q);
  c.resize(Q);
  d.resize(Q);

  for (int q = 0; q < Q; q++) {
    cin >> a[q] >> b[q] >> c[q] >> d[q];
    --a[q], --b[q];
  }
  vector<int> A;
  cout << dfs(A) << endl;
}


Measured memory_bytes: 3628
#include <bits/stdc++.h>
using namespace std;
int main(void){
  int d,n,k=1,i,ans=0;
  cin >> d >> n;
  if (d==2) k=10000;
  else if (d==1) k=100;
  i=0;
  while (i<n){
    ans+=k;
    if ((ans/k)%100) i++;
  }
  cout << ans << endl;
  return 0;
}

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

int main(){
    
    int a,b,c;
    cin >> a >> b >> c;
    
    if( a < b && b < c){
        cout << "Yes" << endl;
    }
    else{
        cout << "No" << endl;
    }
    
    return 0;
    
}

Measured memory_bytes: 1156
def N():
    return int(input())
def L():
    return list(map(int,input().split()))
def NL(n):
    return [list(map(int,input().split())) for i in range(n)]
mod = pow(10,9)+7
#import numpy

s =input()
l = len(s)
if s[l-1] == 's':
    print(s + 'es')
else:
    print(s + 's')

Measured memory_bytes: 61736
[N,K]=list(map(int,input().split()))
x=list(map(int,input().split()))

lengthlist=[]

for i in range(N-K+1):
  #print(x[i+K-1],x[i])
  if x[i+K-1]*x[i]>=0:
    lengthlist.append(min(abs(x[i+K-1]),abs(x[i]))+abs(x[i+K-1]-x[i]))
  elif abs(x[i+K-1])>abs(x[i]):
    lengthlist.append(abs(x[i+K-1])+abs(x[i])*2)
  else:
    lengthlist.append(abs(x[i+K-1])*2+abs(x[i]))

#print(lengthlist)
print(min(lengthlist))

Measured memory_bytes: 14536
#include <cstdio>
#include <algorithm>
using namespace std;
struct node{
	int l,r;
}a[1000005];
int tot;
char s[1000005];
int cmp(node a,node b){
	return a.l-a.r>b.l-b.r;
}
int main(){
	int n,ri,le;
	int i,j;
	le=ri=0;
	scanf("%d",&n);
	for(i=1;i<=n;i++){
		int l=0,r=0;
		scanf("%s",s+1);
		for(j=1;s[j];j++)
			if(s[j]=='(')l++;
			else if(s[j]==')'){
				if(l)l--;
				else r++;
			}
		if(!l&&r)ri+=r;
		else if(l&&!r)le+=l;
		else if(l&&r)a[++tot]=(node){l,r};	
	}
	sort(a+1,a+1+tot,cmp);
	for(int i=1;i<=tot;i++){
		if(le<a[i].r)
			return puts("No"),0;
		le-=a[i].r,le+=a[i].l;
	}
	if(le!=ri)puts("No");
	else puts("Yes");
	return 0;
}

Measured memory_bytes: 3220
import math
def soinsu(N):
    sqr = int(math.sqrt(N))
    lis = []
    for i in range(2,sqr+2):
        while N % i == 0:
            lis.append(i)
            N = N // i
    if not N == 1:
        lis.append(N)
    return lis

def yakusu(N):
    sqr = int(math.sqrt(N))
    lis = []
    for i in range(1,sqr+2):
        if N % i == 0:
            lis.append(i)
            lis.append(N//i)
    return lis

mod = 1000000007
def modpow(a,b,MOD=mod):
    res = 1
    while b > 0:
        if (b & 1) == 1:
            res = (res*a) % MOD
        a = (a*a) % MOD
        b = b >> 1
    return res
fact = []
def ncrinit(MOD=mod):
    fact.append(1)
    for i in range(1,110005):
        fact.append((fact[i-1]*i)%MOD)

def calcnCr(n,r,MOD=mod):
    up = fact[n]
    down = modpow((fact[n-r]*fact[r])%mod,mod-2,mod)
    return (up*down)%mod

def compres(lis):
    li = []
    se = set(lis)
    for i in se:
        li.append(lis.count(i))
    return li
res = 1
N,M = list(map(int,input().split()))
co = yakusu(M)
co.sort()
for i in co:
    if M // i >= N:
        res = max(res,i)
print(res)


Measured memory_bytes: 3064
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp> 
//#include <ext/pb_ds/tree_policy.hpp> 
 
//using namespace __gnu_pbds;
using namespace std;
 
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define ff first
#define ss second
#define null 0
#define pi 3.14159265358979323846
#define all(x) x.begin(), x.end()
#define d0(x) cout<<x<<" ";
#define d1(x) cout<<x<<"\n";
#define d2(x,y) cout<<x<<" "<<y<<"\n";
#define d3(x,y,z) cout<<x<<" "<<y<<" "<<z<<"\n";
#define d4(x,y,z,w) cout<<x<<" "<<y<<" "<<z<<" "<<w<<"\n";
 
//#define ordered_set tree<pair<ll,ll>, null_type,less<pair<ll,ll>>, rb_tree_tag,tree_order_statistics_node_update> 
//#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> 
 
template<typename T, typename U> static inline void amin(T &x, U y){if (y < x)x = y;} 
template<typename T, typename U> static inline void amax(T &x, U y){if (y > x)x = y;} 
 
typedef long long int ll;
typedef unsigned long long int ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
 
const  ll mod= 1000000007  ; 
const long long inf = (ll)1e18+17;
const int inff = 1500000000;
const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, 1, 0, -1};
ll inv[10000];
void inn(ll n, ll prime) 
{ 
    ll dp[n + 1]; 
    dp[0] = dp[1] = 1; 
    for (int i = 2; i <= n; i++)  
        dp[i] = dp[prime % i] *  
               (prime - prime / i) % prime;     
  
    for (int i = 1; i <= n; i++)  
        inv[i]=dp[i];     
} 
ll cp(ll a,ll b){
    if(b==0)return 1;
    if(b==1)return a;
    ll op=cp(a-1,b-1);
    op= (op*a)%mod;
    op= (op*inv[b])%mod;
    return op%mod;
}
int test_case=0;
void solve(){
    ll n;cin>>n;
    inn(n,mod);
    if(n<3){cout<<"0\n";return;}
    ll ans=1;
    for(int i=2;i<n;i++){
        if(n-2*i-1<i-1)break;
        ans= (ans + cp(n-2*i-1,i-1))%mod;//d0(ans)
    }
    cout<<ans%mod<<endl;
}
 
int main()
{  
    clock_t tt;tt = clock(); 
    //ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int t=1;
    if(test_case==1)
    cin>>t;
    //pre();
    for(int i=1;i<=t;i++){
       //cout<<"Case #"<<i<<": ";
       solve();
    }
    tt = clock() - tt; double time_taken = ((double)tt)/CLOCKS_PER_SEC;   
    //printf("code took %f seconds to execute \n", time_taken); 
    return 0;
}
 
// ============== Notes =============== //
// common bugs
// - remove ios_base for interactive problems
// - int overflow (especially intermediate expressionns)
// - array bounds (indices bigger than MAXN?)
// - special cases (n=1? graph not connected?)
// - re-initialize efficiently between test cases

Measured memory_bytes: 3652
#include <iostream>
#include <string>
using namespace std ;
int main () {
    int N, a[210];
    cin >> N;
    int y = 0;
    
    for(int i = 0; i < N; i++)
    {
        cin >> a[i];
    }

    while(true){
        bool x = false;
        
        for(int i = 0; i < N; i++)
        {
            
            if (a[i]%2 == 1) {
                x = true;
            }
            
        }
        if(x)break;
        for(int i = 0; i < N; i++)
        {
            a[i] /= 2;
        }
        
        y++;
    }
    cout <<y <<endl;
    
} 

Measured memory_bytes: 384
#include <iostream>

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

void solve()
{
	double x[4], y[4];
	while(cin >> x[0] >> y[0] >> x[1] >> y[1] >> x[2] >> y[2] >> x[3] >> y[3])
	{
		if(y[0] > y[3] || y[1] < y[2] || x[0] > x[3] || x[1] < x[2])
		{
			cout << "NO" << endl;
		}
		else
		{
			cout << "YES" << endl;
		}
	}
}

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

Measured memory_bytes: 0
def main():
    global N, S
    N = int(input())
    S = tuple(map(int, input().split()))
    Q = int(input())
    T = tuple(map(int, input().split()))

    cnt = 0
    for i in T:
        cnt += binsearch(i)
    print(cnt)

def binsearch(key):
    left = 0
    right = N
    while left < right:
        mid = (left + right) // 2
        if key == S[mid]:
            return 1
        if key > S[mid]:
            left = mid + 1
        else:
            right = mid
    return 0

main()



Measured memory_bytes: 16944
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> P;
typedef pair<ll,ll> l_l;
const int INF=1001001000;
const int mINF=-1001001000;
const ll LINF=1010010010010010000;
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;
}
const int mod = 1000000007;
struct mint {
ll x;
mint(ll x=0):x((x%mod+mod)%mod){}
mint operator-() const { return mint(-x);}
mint& operator+=(const mint a) {
if ((x += a.x) >= mod) x -= mod;
return *this;
}
mint& operator-=(const mint a) {
if ((x += mod-a.x) >= mod) x -= mod;
return *this;
}
mint& operator*=(const mint a) {
(x *= a.x) %= mod;
return *this;
}
mint operator+(const mint a) const {
mint res(*this);
return res+=a;
}
mint operator-(const mint a) const {
mint res(*this);
return res-=a;
}
mint operator*(const mint a) const {
mint res(*this);
return res*=a;
}
mint pow(ll t) const {
if (!t) return 1;
mint a = pow(t>>1);
a *= a;
if (t&1) a *= *this;
return a;
}
mint inv() const {
return pow(mod-2);
}
mint& operator/=(const mint a) {
return (*this) *= a.inv();
}
mint operator/(const mint a) const {
mint res(*this);
return res/=a;
}
};
mint dp0[2005][2005];
mint dp1[2005][2005];
int main(){
    int n,m;cin >> n >> m;
    vector<int> s(2005),t(2005);
    for(int i=0;i<n;i++) cin >> s[i];
    for(int j=0;j<m;j++) cin >> t[j];
    dp0[0][0]=1;
    for(int i=0;i<=n;i++){
        for(int j=0;j<=m;j++){
            dp0[i+1][j]+=dp0[i][j];
            dp1[i][j]+=dp0[i][j];
            dp1[i][j+1]+=dp1[i][j];
            if(s[i]==t[j]) dp0[i+1][j+1]+=dp1[i][j];
        }
    }
    cout << dp1[n][m].x << endl;
    return 0;
}

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

#define rep(i,n) for(int i = 0; i < n; i++)
#define REP(i,n) for(int i = 1; i < n; i++)
#define per(i,n) for(int i = n; i >= 0; i--)
#define sz(x) int(x.size())
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define YesorNo(a) printf(a ? "Yes\n" : "No\n")
#define endl '\n'
#define fi first
#define se second
using ll = long long;
using P = pair<int,int>;
using Pl = pair<ll,ll>;
using vi = vector<int>;
using vii = vector<vi>;
using vl = vector<ll>;
using vll = vector<vl>;
using vs = vector<string>;
using vb = vector<bool>;
using vc = vector<char>;
using vcc = vector<vc>;
const int dx[] = {0,1,0,-1,1,1,-1,-1};
const int dy[] = {1,0,-1,0,1,-1,-1,1};
const int inf = (1<<30)-1;
const ll infll = (1LL<<62)-1;
ll ceil(const ll &a, const ll &b){return ((a)+(b)-1)/b;}
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }

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

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

  ll a, b;
  ll c, d;
  cin >> a >> b >> c >> d;
  ll e =lcm(c,d);
  ll ans = 0;
  ans += b/c - (a-1)/c;
  ans += b/d - (a-1)/d;
  ans -= b/e - (a-1)/e;
  ans = (b-a+1) - ans;
  cout << ans << endl;
}

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

using namespace std;

typedef long long ll;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	int n, m;
	cin >> n >> m;
	
	int ret = 0;
	
	// Even with even
	for (int i = 0; i < n; i++)
	for (int j = 0; j < n; j++) 
		if (j > i) ret++;
	
	// Odd with odd
	for (int i = 0; i < m; i++)
	for (int j = 0; j < m; j++) 
		if (j > i) ret++;
	
	cout << ret << endl;
    return 0;
}

Measured memory_bytes: 256
n = int(input())
a = list(map(int, input().split()))
q = int(input())

mp = {}
for i in a:
    mp[i] = mp.get(i, 0) + 1

total = sum(list(map(lambda item: item[0]*item[1], mp.items())))

for i in range(q):
    b, c = map(int, input().split())
    total -= b * mp.get(b, 0)
    total += c * mp.get(b, 0)
    mp[c] = mp.get(c, 0) + mp.get(b, 0)
    mp[b] = 0
    print(total)

Measured memory_bytes: 23952
#include<bits/stdc++.h>
using namespace std;
const int maxn = 100005;
struct edge
{
	int v,w,nxt;
}e[maxn<<2];

int head[maxn],n,dis[maxn],cnt;
bool vis[maxn];
queue<int> q;

inline void add(int u,int v,int w)
{
	e[++cnt] = (edge){v,w,head[u]};
	head[u] = cnt;
}

int main()
{
	scanf("%d",&n);
	memset(dis,0x3f,sizeof(dis));
	for(int i=1;i<n;i++)
	{
		add(i,(i+1)%n,1);
		add(i,(i*10)%n,0);
	}
	vis[1] = true;
	q.push(1);
	dis[1] = 1;
	while(!q.empty())
	{
		int u = q.front();
		q.pop();
		vis[u] = false;
		for(int i=head[u];i;i=e[i].nxt)
		{
			int v = e[i].v;
			if(dis[v] > dis[u] + e[i].w)
			{
				dis[v] = dis[u] + e[i].w;
				if(!vis[v])
				{
					vis[v] = true;
					q.push(v);
				}
			}
		}
	}
	cout << dis[0] << endl;
	return 0;
}


Measured memory_bytes: 4480
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
template<class T>inline bool chmax(T &a, const T &b){if(a < b){a = b; return 1;}return 0;}
template<class T>inline bool chmin(T &a, const T &b){if(a > b){a = b; return 1;}return 0;}
typedef long long ll;

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  int N, K; cin >> N >> K;
  string S; cin >> S;
  int cnt = 0; // 切り替わり点
  int ans = 0; // 幸福な人数
  REP(i, N-1){
    if(S[i] == S[i+1]) ans++;
    if(S[i] != S[i+1]) cnt++;
  }
  ans = ans + min(K*2, cnt);
  cout << ans << endl;
}

Measured memory_bytes: 512
#include <stdio.h>
#include <algorithm>
long long n, k, x, ans;
long long a[200005];
long long c[200005];
int main() {
	scanf("%lld%lld", &n, &k);
	for (int i = 0; i < n; i++) {
		scanf("%lld", a + i);
		a[i]--;
		a[i] %= k;
	}
	c[0] = 0;
	for (int i = 0; i < n; i++) {
		c[i + 1] = a[i] + c[i];
		c[i + 1] %= k;
	}
	c[n + 1] = k;
	for (int i = 0; i < n + 2; i++) {
		c[i] = c[i] * 2000000000 + i;
	}
	std::sort(c, c + n + 2);
	for (long long i = 1; i < n + 2; i++) {
		while (c[i] - c[x] >= k) {
			x++;
		}
		ans += i - x;
	}
	printf("%lld\n", ans);
}

Measured memory_bytes: 3328
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
signed main(){
  ll n,ans=0;
  cin >> n;
  ll a[n],b[n];
  vector<ll> point;
  for(int i=0;i<n;i++){
    cin >> a[i]>>b[i];
    point.push_back(a[i]+b[i]);
    ans-=b[i];
  }
  sort(point.begin(),point.end(),greater<ll>());
  for(int i=0;i<n;i+=2){
    ans+=point[i];
  }
  cout << ans << endl;
}


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

using namespace std;

#define FOR(n) for(int i=0;i<n;i++)
#define IN(n,a) for(int i=0;i<n;i++) cin>>a[i]

int main()
{
	string s, t;
	cin >> s >> t;
	int count = 0;
	FOR(3)
	{
		if (s[i] == t[i])count++;
	}
	cout << count;
}

Measured memory_bytes: 256
package main

import "fmt"

func main() {
	var n int64
	fmt.Scan(&n)

	var sum int64
	for i := int64(1); i <= n; i++ {
		if i%3 != 0 && i%5 != 0 {
			sum += i
		}
	}
	fmt.Println(sum)
}


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

// iterator
#define REP(i,init, n) for(lli i=init;i<n;i++)
#define REPE(i,init, n) for(lli i=init;i<=n;i++)
#define REPIT(it,container) for(auto it = container.begin(); it != container.end(); it++)
#define REPIT_R(it,container) for(auto it = container.rbegin(); it != container.rend(); it++)

// input
#define cin1(x)             cin >> x
#define cin2(x, y)          cin >> x >> y
#define cin3(x, y, z)       cin >> x >> y >> z
#define ncin1(n, x)         REP(i, 0, n) {cin1(x[i]);}
#define ncin2(n, x, y)      REP(i, 0, n) {cin2(x[i], y[i]);}
#define ncin3(n, x, y, z)   REP(i, 0, n) {cin3(x[i], y[i], z[i]);}

// output
#define cout1(x)         cout << #x << ": " << x << endl;
#define ncout1(n, x)     REP(i, 0, n) {cout << #x << "[" << i << "]: "<< x[i] << endl;}

// sort
#define sort_r(x, y)        sort(x, y, greater<lli>()); // 降順(5,4,3,,,)

#define ARRAY_LENGTH(array) (sizeof(array) / sizeof(array[0]))

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

int main() {
    string s;
    cin1(s);
    s[3] = '8';
    cout << s << endl;
}


Measured memory_bytes: 256
object Main {
  def main(args: Array[String]): Unit = {
    solve
  }

  def solve(): Unit = {
    val sc = new java.util.Scanner(System.in)
    var h = sc.nextLong

    var count = 0
    while (h > 1) {
      count += 1
      h = h / 2
    }

    var num = 0L
    for (i <- 0 to count) {
      num += math.pow(2, i).toLong
    }
    println(num)

  }
}


Measured memory_bytes: 27220
INF = 10000000000
sl = [60,  80,  100,  120,  140,  160,  INF]
wl = [2,   5,   10,   15,   20,   25,   INF]
pl = [600, 800, 1000, 1200, 1400, 1600, 0  ]

def le(n, l):
  for i, v in enumerate(l):
    if v >= n:
      return i

while True:
  N = input()
  if not N:
    break
  s = 0
  for i in range(N):
    x, y, h, w = map(int, raw_input().split())
    s += pl[max(le(x + y + h, sl), le(w, wl))]
  print(s)

Measured memory_bytes: 4528
#include<stdio.h>

int main() {
	int a;
  	scanf("%d",&a);
  	char str[a+1];
	scanf("%s",str);
	if(a % 2 == 1){
		puts("No");
	}else{
		int flag = 1;
		for(int i = 0;i<a/2;i++){
			if(str[i] != str[i+a/2]){
				flag = 0;
			}
		}
		if(flag){
			puts("Yes");
		}else{
			puts("No");
		}
	}	
  return 0;
}

Measured memory_bytes: 1592
#include <iostream>
#include <algorithm>
#include <cmath>
#include <map>
#include <vector>
#include <queue>
#include <functional>
#include <string>
#include <stack>
#include <set>
#include <sstream>
#include <iomanip>
#include <limits>
#include <cstring>

using namespace std;
using ll = long long;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
typedef pair<double, double >pd;
typedef pair<string, string> sP;
typedef pair<ll, pair<ll, ll>> PP;


const ll mod = 1e4;
const ll MOD = 1e9 + 7;
const ll MOD2 = 998244353;
const ll INF = 1 << 30;
const ll INF2 = 9e18;
const double INF3 = 9e14;
const double eps = 1e-10;
const double PI = 3.14159265358979323846;
const int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 };
const int tx[8] = { -1,0,1,-1,1,-1,0,1 }, ty[8] = { -1,-1,-1,0,0,1,1,1 };

#define ALL(x) (x).begin(),(x).end()
#define ALLR(x) (x).rbegin(),(x).rend()
#define pb push_back
#define eb emplace_back
#define fr first
#define sc second

ll bit[100010], ma = 100010;

void add(ll a,  ll w) {
	for (int x = a; x <= ma + 2; x += x & -x) bit[x] += w;
}
int SUM(ll a) {
	ll ret = 0;
	for (int x = a; x > 0; x -= x & -x) ret += bit[x];
	return ret;
}


int main() {
	ll n, a[100010], b[100010], t[100010], ans = 0;
	cin >> n;
	vector<ll>e, o;
	map<ll, bool>even;
	for (int i = 0;i < n;i++) {
		cin >> a[i];
		if (i % 2 == 0) e.eb(a[i]);
		else o.eb(a[i]);
	}
	sort(a, a + n);
	for (int i = 0;i < n;i++) {
		if (i % 2 == 0)even[a[i]] = 1;
	}
	for (auto u:o) {
		if (even[u])ans++;
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 8052
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)n;i++)
#define all(c) (c).begin(),(c).end()
#define pb push_back
#define dbg(...) do{cerr<<__LINE__<<": ";dbgprint(#__VA_ARGS__, __VA_ARGS__);}while(0);

using namespace std;

namespace std{template<class S,class T>struct hash<pair<S,T>>{size_t operator()(const pair<S,T>&p)const{return ((size_t)1e9+7)*hash<S>()(p.first)+hash<T>()(p.second);}};template<class T>struct hash<vector<T>>{size_t operator()(const vector<T> &v)const{size_t h=0;for(auto i : v)h=h*((size_t)1e9+7)+hash<T>()(i)+1;return h;}};}
template<class T>ostream& operator<<(ostream &os, const vector<T> &v){os<<"[ ";rep(i,v.size())os<<v[i]<<(i==v.size()-1?" ]":", ");return os;}template<class T>ostream& operator<<(ostream &os,const set<T> &v){os<<"{ "; for(const auto &i:v)os<<i<<", ";return os<<"}";}
template<class T,class U>ostream& operator<<(ostream &os,const map<T,U> &v){os<<"{";for(const auto &i:v)os<<" "<<i.first<<": "<<i.second<<",";return os<<"}";}template<class T,class U>ostream& operator<<(ostream &os,const pair<T,U> &p){return os<<"("<<p.first<<", "<<p.second<<")";}
void dbgprint(const string &fmt){cerr<<endl;}template<class H,class... T>void dbgprint(const string &fmt,const H &h,const T&... r){cerr<<fmt.substr(0,fmt.find(","))<<"= "<<h<<" ";dbgprint(fmt.substr(fmt.find(",")+1),r...);}
typedef long long ll;typedef vector<int> vi;typedef pair<int,int> pi;const int inf = (int)1e9;const double INF = 1e12, EPS = 1e-9;

vi v[100010];

int main(){
	cin.tie(0); cin.sync_with_stdio(0);
	int n, m; cin >> n >> m;
	rep(i, n){
		int a, b; cin >> a >> b;
		if(m >= a) v[m - a].pb(b);
	}
	priority_queue<int> q;
	ll ans = 0;
	for(int i = m - 1; i >= 0; i--){
		for(int j : v[i]) q.push(j);
		if(!q.empty()){
			ans += q.top();
			q.pop();
		}
	}
	cout << ans << endl;
	
	return 0;
}

Measured memory_bytes: 5632