#include <bits/stdc++.h>
#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;
const int oo = 2e9;
const int N = 500100;
vector<pii> vc;
int n, kol, tt = 0;
struct seg_tree{
vector<int> ys, psh;
vector<pii> st;
seg_tree(): ys(0), st(0), psh(0) {}
void pull(int v){
st[v].ft = max(st[v + v].ft, st[v + v + 1].ft);
st[v].sd = 0;
if (st[v].ft == st[v + v].ft)
st[v].sd += st[v + v].sd;
if (st[v].ft == st[v + v + 1].ft)
st[v].sd += st[v + v + 1].sd;
}
void build(int v, int l, int r){
psh[v] = 0;
if (l == r){
st[v] = MP(0, 1);
return;
}
int md = (l + r) >> 1;
build(v + v, l, md);
build(v + v + 1, md + 1, r);
pull(v);
}
void push(int v, int l, int r){
if (psh[v] != 0){
if (psh[v] >= st[v].ft){
st[v] = MP(psh[v], r - l + 1);
}
if (l != r){
psh[v + v] = max(psh[v + v], psh[v]);
psh[v + v + 1] = max(psh[v + v + 1], psh[v]);
}
psh[v] = 0;
}
}
void update(int v, int tl, int tr, int l, int r, int vl){
push(v, tl, tr);
if (l > r) return;
if (tl == l && tr == r){
psh[v] = vl;
push(v, tl, tr);
return;
}
int md = (tl + tr) >> 1;
update(v + v, tl, md, l, min(r, md), vl);
update(v + v + 1, md + 1, tr, max(md + 1, l), r, vl);
pull(v);
}
pii get(int v, int tl, int tr, int l, int r){
push(v, tl, tr);
if (l > r) return MP(0, 0);
if (tl == l && tr == r) return st[v];
int md = (l + r) >> 1;
pii n1 = get(v + v, tl, md, l, min(r, md));
pii n2 = get(v + v + 1, md + 1, tr, max(md + 1, l), r);
pii res = MP(max(n1.ft, n2.ft), 0);
if (res.ft == n1.ft) res.sd += n1.sd;
if (res.ft == n2.ft) res.sd += n2.sd;
return res;
}
};
seg_tree st[4 * N];
pii psh[4 * N];
void build(int v, int l, int r){
psh[v] = MP(0, 0);
if (l == r){
st[v].ys.clear();
st[v].ys.PB(vc[l].sd);
st[v].st.resize(2);
st[v].psh.resize(2);
st[v].st[1] = MP(0, 1);
st[v].psh[1] = 0;
return;
}
int md = (l + r) >> 1;
build(v + v, l, md);
build(v + v + 1, md + 1, r);
merge(all(st[v + v].ys), all(st[v + v + 1].ys), back_inserter(st[v].ys));
st[v].st.resize(sz(st[v].ys) * 4 + 3);
st[v].psh.resize(sz(st[v].ys) * 4 + 3);
st[v].build(1, 0, sz(st[v].ys) - 1);
}
void push(int v){
if (psh[v] != MP(0, 0)){
int loc = upper_bound(all(st[v].ys), psh[v].sd) - st[v].ys.begin() - 1;
st[v].update(1, 0, sz(st[v].ys) - 1, 0, loc, psh[v].ft);
if (v + v + 1 < 4 * N){
psh[v + v] = max(psh[v + v], psh[v]);
psh[v + v + 1] = max(psh[v + v + 1], psh[v]);
}
psh[v] = MP(0, 0);
}
}
void real_search(int v, int l, int r, int vl){
// may be here should be push
if (l == r){
kol = 0;
psh[v] = MP(tt, vl);
return;
}
int md = (l + r) >> 1;
push(v + v);
push(v + v + 1);
int loc = upper_bound(all(st[v + v].ys), vl) - st[v + v].ys.begin() - 1;
int cur_kol = loc + 1;
pii gt = st[v + v].get(1, 0, sz(st[v + v].ys) - 1, 0, loc);
if (gt.ft == tt)
cur_kol -= gt.sd;
// if (cur_kol == kol) it may further optimize
if (cur_kol >= kol)
real_search(v + v, l, md, vl);
else {
psh[v + v] = MP(tt, vl);
kol -= cur_kol;
real_search(v + v + 1, md + 1, r, vl);
}
}
void search(int v, int l, int r, int vl){
push(v);
if (kol == 0) return;
if (vc[r].ft < vl) return;
if (vc[l].ft >= vl){
int loc = upper_bound(all(st[v].ys), vl) - st[v].ys.begin() - 1;
int cur_kol = loc + 1;
pii gt = st[v].get(1, 0, sz(st[v].ys) - 1, 0, loc);
if (gt.ft == tt)
cur_kol -= gt.sd;
if (cur_kol <= kol){
kol -= cur_kol;
psh[v] = MP(tt, vl);
} else real_search(v, l, r, vl);
return;
}
int md = (l + r) >> 1;
search(v + v, l, md, vl);
search(v + v + 1, md + 1, r, vl);
}
void init(int N, int A[], int B[]) {
n = N;
vc.clear();
for (int i = 0; i < n; i++)
vc.PB(MP(B[i], A[i]));
sort(all(vc));
build(1, 0, n - 1);
}
int can(int M, int K[]) {
sort(K, K + M);
tt++;
for (int i = 0; i < M; i++){
int k = K[i];
kol = k;
search(1, 0, n - 1, k);
if (kol > 0)
return 0;
}
return 1;
}
