#include "teams.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (l); --x)
typedef std::pair<int,int> pii;
typedef long long ll;
using namespace std;
const int N = 500010;
int n;
namespace seg {
vector<int> nds;
vector<int> ls;
int nxt = 1;
struct node {
int cnt, l, r;
} nd[(1<<27)/sizeof(node)];
int get(int t, int l, int r, int b, int e) {
if (l <= b && e <= r)
return nd[t].cnt;
int ans = 0;
if (l < (b+e)/2 && nd[t].l)
ans += get(nd[t].l, l, r, b, (b+e)/2);
if ((b+e)/2 < r && nd[t].r)
ans += get(nd[t].r, l, r, (b+e)/2, e);
return ans;
}
int add(int t, int p, int b, int e) {
int ans = nxt++;
nd[ans].cnt = nd[t].cnt+1;
nd[ans].l = nd[t].l;
nd[ans].r = nd[t].r;
if (e-b == 1)
return ans;
if (p < (b+e)/2)
nd[ans].l = add(nd[t].l, p, b, (b+e)/2);
else
nd[ans].r = add(nd[t].r, p, (b+e)/2, e);
return ans;
}
void mk_seg(const vector<pii> &vec) {
nds = {0};
int p = 0;
Loop (i,1,N+1) {
int t = nds.back();
while (p < vec.size() && vec[p].first < i)
t = add(t, vec[p++].second, 0, N);
nds.push_back(t);
}
}
int get(int l1, int r1, int l2, int r2) {
if (l2 == r2)
return 0;
if (l2 < r2)
return get(nds[r1], l2, r2, 0, N)
- get(nds[l1], l2, r2, 0, N);
else
return get(nds[l1], r2, l2, 0, N)
- get(nds[r1], r2, l2, 0, N);
}
}
namespace lichao {
struct fn {
int val;
int p;
};
int eval(fn f, int x) {
return seg::get(0, x+1, x+1, f.p+1) + f.val;
}
struct node {
fn f;
int l, r;
} nds[(1<<27)/sizeof(node)];
int nxt = 1;
int get(int t, int p, int b, int e) {
if (!t)
return 1e9;
int ans = eval(nds[t].f, p);
if (e-b == 1)
return ans;
if (p < (b+e)/2)
ans = min(ans, get(nds[t].l, p, b, (b+e)/2));
else
ans = min(ans, get(nds[t].r, p, (b+e)/2, e));
return ans;
}
int get(int t, int p) { return get(t, p, 0, N); }
void up(int &t, fn f, int b, int e) {
if (!t) {
t = nxt++;
nds[t].f = f;
return;
}
int m = (b+e)/2;
bool b1 = eval(nds[t].f, b) > eval(f, b);
bool b2 = eval(nds[t].f, m) > eval(f, m);
if (b2)
swap(nds[t].f, f);
if (e-b == 1)
return;
if (b1 != b2)
up(nds[t].l, f, b, m);
else
up(nds[t].r, f, m, e);
}
void up(int &t, fn f) { return up(t, f, 0, N); }
}
int cnt[N];
vector<pii> vec;
void init(int n, int a[], int b[]) {
Loop (i,0,n) {
cnt[a[i]]++;
cnt[b[i]+1]--;
vec.push_back({a[i], b[i]+1});
}
Loop (i,1,N)
cnt[i] += cnt[i-1];
::n = n;
sort(vec.begin(), vec.end());
seg::mk_seg(vec);
}
int can(int m, int k[]) {
ll sum = 0;
Loop (i,0,m)
sum += k[i];
if (sum > n)
return 0;
sort(k, k+m);
int li = 0;
lichao::fn tmp;
lichao::up(li, tmp = { .val = 0, .p = n+1 });
vector<int> dp(m);
LoopR (i,0,m) {
dp[i] = lichao::get(li, k[i]) - k[i];
lichao::up(li, { .val = dp[i], .p = k[i] });
if (dp[i] < 0)
return 0;
}
return 1;
}
