#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;
typedef long long ll;
const int oo = 2e9;
const int N = 500100;
vector<int> lf, rt;
vector<pii> vc, events;
int n, kol, tt = 0;
ll mx[4 * N], psh[4 * N]; // constraints here can be smaller
struct seg_tree{
vector<int> ys;
seg_tree(): ys(0) {}
};
seg_tree st[4 * N];
void build(int v, int l, int r){
if (l == r){
st[v].ys.clear();
st[v].ys.PB(vc[l].sd);
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));
}
int calc(int v, int l, int r, int min_x, int max_y){
if (vc[r].ft < min_x) return 0;
if (vc[l].ft >= min_x){
int kol = upper_bound(all(st[v].ys), max_y) - st[v].ys.begin();
return kol;
}
int md = (l + r) >> 1;
return calc(v + v, l, md, min_x, max_y) + calc(v + v + 1, md + 1, r, min_x, max_y);
}
void init(int N, int A[], int B[]) {
n = N;
vc.clear();
for (int i = 0; i < n; i++) {
vc.PB(MP(A[i], B[i]));
lf.PB(A[i]);
rt.PB(B[i]);
}
sort(all(vc));
sort(all(lf));
sort(all(rt));
build(1, 0, n - 1);
}
void new_build(int v, int l, int r){
mx[v] = 0;
if (l == r) return;
int md = (l + r) >> 1;
new_build(v + v, l, md);
new_build(v + v + 1, md + 1, r);
}
void push(int v){
if (psh[v] != 0){
mx[v] += psh[v];
if (v + v + 1 < 4 * N){
psh[v + v] += psh[v];
psh[v + v + 1] += psh[v];
}
psh[v] = 0;
}
}
void update(int v, int tl, int tr, int l, int r, ll vl){
push(v);
if (l > r) return;
if (tl == l && tr == r) {
psh[v] = vl;
push(v);
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);
mx[v] = max(mx[v + v], mx[v + v + 1]);
}
int can(int M, int K[]) {
sort(K, K + M);
tt++;
events.clear();
for (int i = 0; i < M; ){
int j = i;
events.PB(MP(K[i], 0));
while (j < M && K[i] == K[j]){
events.back().sd++;
j++;
}
i = j;
}
new_build(1, 0, sz(events) - 1);
ll sum = 0;
for (int it = 0; it < sz(events); it++){
pii cr = events[it];
if (it > 0){
if (events[it - 1].ft + 1 <= events[it].ft - 1){
int kol = calc(1, 0, n - 1, events[it - 1].ft + 1, events[it].ft - 1);
update(1, 0, sz(events) - 1, 0, it - 1, kol);
}
}
int kol_up = n - (upper_bound(all(lf), events[it].ft) - lf.begin());
int kol_lo = lower_bound(all(rt), events[it].ft) - rt.begin();
update(1, 0, sz(events) - 1, it, it, kol_lo);
update(1, 0, sz(events) - 1, 0, it, ll(cr.sd) * ll(cr.ft));
if (mx[1] + ll(kol_up) > ll(n))
return 0;
}
return 1;
}
