//#include <bits/stdc++.h>
#include <iostream>
#include <set>
#include <vector>
#include <cstdio>
#include <algorithm>
#include "teams.h"
#define pii pair<int,int>
#define ft first
#define sd second
#define MP make_pair
#define PB push_back
#define all(x) x.begin(),x.end()
#define sz(x) ((int)x.size())
using namespace std;
typedef long long ll;
const int oo = 2e9;
const int N = 500100;
const int BLOCK = 400;
set<pii> st;
set<pii>::iterator ite;
vector<pii> events, vc;
int n, f[N];
struct seg_tree{
seg_tree *l, *r;
int sm;
seg_tree(): l(0), r(0), sm(0) {}
seg_tree(seg_tree *v): l(v -> l), r(v -> r), sm(v -> sm) {}
void build(int tl, int tr){
sm = 0;
if (tl == tr) return;
int md = (tl + tr) >> 1;
l = new seg_tree();
r = new seg_tree();
l -> build(tl, md);
r -> build(md + 1, tr);
}
void update(int tl, int tr, int ps){
sm++;
if (tl == tr) return;
int md = (tl + tr) >> 1;
if (ps <= md){
l = new seg_tree(l);
l -> update(tl, md, ps);
} else {
r = new seg_tree(r);
r -> update(md + 1, tr, ps);
}
}
int sum(int tl, int tr, int ql, int qr){
if (ql > qr) return 0;
if (ql == tl && qr == tr) return sm;
int md = (tl + tr) >> 1;
return l -> sum(tl, md, ql, min(qr, md)) + r -> sum(md + 1, tr, max(md + 1, ql), qr);
}
};
seg_tree *root[N];
void init(int N, int A[], int B[]) {
n = N;
for (int i = 0; i < n; i++)
vc.PB(MP(A[i], B[i]));
sort(all(vc));
root[n] = new seg_tree();
root[n] -> build(1, n);
for (int i = n - 1; i >= 0; i--){
root[i] = new seg_tree(root[i + 1]);
root[i] -> update(1, n, vc[i].sd);
}
}
int calc(int x1, int y1, int x2, int y2){
int lf = lower_bound(all(vc), MP(x1, -oo)) - vc.begin();
int rt = upper_bound(all(vc), MP(x2, +oo)) - vc.begin();
return (root[lf] -> sum(1, n, y1, y2)) - (root[rt] -> sum(1, n, y1, y2));
}
int can(int M, int K[]) {
sort(K, K + M);
if (M < BLOCK) {
events.clear();
ll sum = 0ll;
for (int i = 0; i < M; ){
int j = i;
events.PB(MP(K[i], 0));
while (j < M && K[i] == K[j]){
sum += K[j];
events.back().sd++;
j++;
}
i = j;
}
if (sum > ll(n)) return 0;
for (int it = 0; it < sz(events); it++){
pii cr = events[it];
int cur_kol = cr.ft * cr.sd;
f[it] = calc(1, cr.ft, cr.ft, n) - cur_kol;
for (int pr = 0; pr < it; pr++)
f[it] = min(f[it], f[pr] + calc(events[pr].ft + 1, cr.ft, cr.ft, n) - cur_kol);
if (f[it] < 0)
return 0;
}
} else {
st.clear();
int it = 0;
for (int i = 0; i < M; i++){
while (it < n && vc[it].ft <= K[i]){
st.insert(MP(vc[it].sd, it));
it++;
}
for (int j = 0; j < K[i]; j++){
ite = st.lower_bound(MP(K[i], -oo));
if (ite == st.end())
return 0;
st.erase(ite);
}
}
}
return 1;
}
