//i submitted the others on oj.uz
#include <bits/stdc++.h>
#include "teams.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 1 << 19;
//#define debug(...) fprintf(stderr, __VA_ARGS__)
#define debug(...)
#define fi first
#define se second
#define all(v) (v).begin(), (v).end()
#define fillchar(a, s) memset((a), (s), sizeof(a))
int N;
//persistent segment tree
struct node {
node *ch[2];
int lt, rt;
int val; //value
node() {
ch[0] = ch[1] = NULL;
}
node (int _lt, int _rt) {
lt = _lt;
rt = _rt;
val = 0;
if (rt - lt == 1) {
ch[0] = ch[1] = NULL;
} else {
int mid = (lt + rt) / 2;
ch[0] = new node(lt, mid);
ch[1] = new node(mid, rt);
}
}
node *update (int pos) {
//this is the update of x
if (lt <= pos && pos < rt) {
node *res = new node();
res->lt = this->lt;
res->rt = this->rt;
res->val = this->val + 1;
if (rt == lt + 1) {
res->ch[0] = res->ch[1] = NULL;
} else {
for (int i = 0; i < 2; i++) {
res->ch[i] = this->ch[i]->update(pos);
}
}
return res;
} else {
return this;
}
}
int query (int a, int b) {
if (this->rt <= a || b <= this->lt) {
return 0;
}
if (a <= this->lt && this->rt <= b) {
return this->val;
}
return this->ch[0]->query(a, b) + this->ch[1]->query(a, b);
}
};
node* state[MAXN]; //state at certain point of time
void build (int n, int a[], int b[]) {
vector<pii> v;
for (int i = 0; i < n; i++) {
v.push_back({a[i], b[i]});
}
sort(all(v));
state[0] = new node(0, MAXN);
for (int i = 1, ptr = 0; i <= n; i++) {
state[i] = state[i - 1];
while (ptr < v.size() && v[ptr].fi == i) {
//then update this
state[i] = state[i]->update(v[ptr].se);
ptr++;
}
}
}
//ok this is used every query
#define ctime sdjfkj
#warning UPDATE CTIME ALWAYS!!!
int taken[2 * MAXN];
int lazy[2 * MAXN]; //used for ALL TAKEN only.
vector<int> vupds;
//ok this is now done every query - every query.
void reset() {
for (int i : vupds) {
taken[i] = 0;
lazy[i] = 0;
}
vupds.clear();
}
void put (int cur, int lt, int rt, int v) {
vupds.push_back(cur);
//tree[cur] += v;
//lazy[cur] += v;
taken[cur] = state[v]->query(lt, rt); //is this really it???? change "ctime" to "v"??
lazy[cur] = v;
}
void down (int cur, int lt, int rt) {
if (lazy[cur] != 0) {
int mid = (lt + rt) / 2;
put(2 * cur, lt, mid, lazy[cur]);
put(2 * cur + 1, mid, rt, lazy[cur]);
lazy[cur] = 0;
}
}
void update_all (int a, int b, int v, int cur = 1, int lt = 0, int rt = MAXN) {
if (rt <= a || b <= lt) {
return;
}
if (a <= lt && rt <= b) {
put(cur, lt, rt, v);
return;
}
down(cur, lt, rt);
int mid = (lt + rt) / 2;
update_all(a, b, v, 2 * cur, lt, mid);
update_all(a, b, v, 2 * cur + 1, mid, rt);
taken[cur] = taken[2 * cur] + taken[2 * cur + 1];
vupds.push_back(cur);
}
void update_single (int x, int v) {
//taken[x] += v;
for (int sh = 19, lt = 0, rt = MAXN; sh >= 1; sh--) {
int cur = (x + MAXN) >> sh;
down(cur, lt, rt);
int mid = (lt + rt) / 2;
if (x < mid) {
//(lt, rt) -> (lt, mid)
rt = mid;
} else {
//(lt, rt) -> (mid, rt)
lt = mid;
}
}
for (int i = x + MAXN; i > 0; i >>= 1) {
vupds.push_back(i);
taken[i] += v;
}
}
int taken_query (int a, int b, int cur = 1, int lt = 0, int rt = MAXN) {
if (rt <= a || b <= lt) {
return 0;
}
if (a <= lt && rt <= b) {
return taken[cur];
}
down(cur, lt, rt);
int mid = (lt + rt) / 2;
return taken_query(a, b, 2 * cur, lt, mid) + taken_query(a, b, 2 * cur + 1, mid, rt);
}
void init (int nnn, int a[], int b[]) {
N = nnn;
build(N, a, b);
for (int i = 0; i < 2 * MAXN; i++) {
taken[i] = 0;
lazy[i] = 0;
}
}
int can (int M, int K[]) {
debug("-------------------START OF QUERY, M = %d---------------\n", M);
if (accumulate(K, K + M, 0ll) > N) {
return false;
}
reset();
sort(K, K + M);
for (int i = 0; i < M; i++) {
int ctime = K[i];
//check ptree.state[i]
//binary search for it
int nrem = state[ctime]->query(ctime, MAXN) - taken_query(ctime, MAXN);
//how many are there left to take?
if (K[i] > nrem) {
debug("NOT ENOUGH!\n");
return false;
}
//when will it be >= K[i]? And when is it < K[i]?
int lo = ctime, hi = MAXN;
while (hi - lo > 1) {
int mid = (lo + hi) / 2;
nrem = state[ctime]->query(ctime, mid) - taken_query(ctime, mid);
if (nrem >= K[i]) {
hi = mid;
} else {
lo = mid;
}
}
int nall = state[ctime]->query(ctime, lo) - taken_query(ctime, lo);
//[ctime, lo): take ALL.
update_all(ctime, lo, ctime);
//lo: take the remaining
nrem = K[i] - nall;
update_single(lo, nrem);
}
assert(taken[1] == accumulate(K, K + M, 0));
return true;
}
