#include "teams.h"
#include <bits/stdc++.h>
using namespace std;
// #define int int64_t
int n;
struct Query {
struct seg {
struct node {
int val = 0;
int l = -1;
int r = -1;
};
vector<node> tree = {{0, -1, -1}};
void build(int v, int rl, int rr) {
if (rl == rr) return;
tree[v].l = tree.size();
tree.push_back(node());
tree[v].r = tree.size();
tree.push_back(node());
int rm = (rl + rr)/2;
build(tree[v].l, rl, rm);
build(tree[v].r, rm+1, rr);
}
int update(int v, int rl, int rr, int pos, int val) {
if (rl == rr) {
int newV = tree.size();
tree.push_back(tree[v]);
tree[newV].val = val;
return newV;
}
int rm = (rl + rr)/2;
int newV = tree.size();
tree.push_back(tree[v]);
if (pos <= rm) tree[newV].l = (update(tree[newV].l, rl, rm, pos, val));
else tree[newV].r = (update(tree[newV].r, rm+1, rr, pos, val));
tree[newV].val = tree[tree[newV].l].val + tree[tree[newV].r].val;
return newV;
}
int query(int v, int rl, int rr, int ql, int qr) {
if (ql > qr) return 0;
if (rl == ql && rr == qr) return tree[v].val;
int rm = (rl + rr)/2;
return query(tree[v].l, rl, rm, ql, min(rm, qr)) + query(tree[v].r, rm+1, rr, max(rm+1, ql), qr);
}
};
vector<pair<pair<int, int>, pair<int, int>>> rangesWithSortedIndicies;
vector<pair<int, int>> beginWithIndicies;
vector<pair<int, int>> endWithIndicies;
vector<int> startTimes;
seg tree;
void initQuery(vector<pair<int, int>> &ranges) {
rangesWithSortedIndicies.resize(n);
beginWithIndicies.resize(n);
endWithIndicies.resize(n);
for (int i = 0; i<n; i++) {
rangesWithSortedIndicies[i].first.first = ranges[i].first;
rangesWithSortedIndicies[i].second.first = ranges[i].second;
}
sort(rangesWithSortedIndicies.begin(), rangesWithSortedIndicies.end());
for (int i = 0; i<n; i++) {
rangesWithSortedIndicies[i].first.second = i;
swap(rangesWithSortedIndicies[i].first, rangesWithSortedIndicies[i].second);
beginWithIndicies[i] = rangesWithSortedIndicies[i].second;
}
sort(rangesWithSortedIndicies.begin(), rangesWithSortedIndicies.end());
for (int i = 0; i<n; i++) {
rangesWithSortedIndicies[i].first.second = i;
swap(rangesWithSortedIndicies[i].first, rangesWithSortedIndicies[i].second);
endWithIndicies[i] = rangesWithSortedIndicies[i].second;
}
sort(rangesWithSortedIndicies.begin(), rangesWithSortedIndicies.end());
assert(is_sorted(beginWithIndicies.begin(), beginWithIndicies.end()));
assert(is_sorted(endWithIndicies.begin(), endWithIndicies.end()));
// ----------- rangesWithSortedIndicies: {valBegin, indBegin}, {valEnd, indEnd}; sorted by begin. -----------
tree.build(0, 0, n-1);
startTimes.resize(n);
for (int i = 0; i<(int)n; i++) {
assert(i == rangesWithSortedIndicies[i].first.second);
startTimes[i] = tree.update(i == 0 ? 0 : startTimes[i-1], 0, n-1, rangesWithSortedIndicies[i].second.second, 1);
}
}
int query(int indexBeginL, int indexBeginR, int indexEndL, int indexEndR) {
int right = tree.query(startTimes[indexBeginR], 0, n-1, indexEndL, indexEndR);
int left = tree.query(indexBeginL == 0 ? 0 : startTimes[indexBeginL-1], 0, n-1, indexEndL, indexEndR);
return right-left;
}
};
vector<int> allBeginR, allEndL;
Query queryEngine;
void makeAll() {
allBeginR.assign(n+1, -1);
allEndL.assign(n+1, -1);
for (int i = 1; i<=n; i++) {
auto pBeginR = lower_bound(queryEngine.beginWithIndicies.begin(), queryEngine.beginWithIndicies.end(), pair<int, int>{i, 1e9});
auto pEndL = lower_bound(queryEngine.endWithIndicies.begin(), queryEngine.endWithIndicies.end(), pair<int, int>{i-1, 1e9});
if (pBeginR != queryEngine.beginWithIndicies.begin()) allBeginR[i] = (*prev(pBeginR)).second;
if (pEndL != queryEngine.endWithIndicies.end()) allEndL[i] = (*pEndL).second;
}
}
void init(signed _N, signed A[], signed B[]) {
n = _N;
vector<pair<int, int>> ranges(n);
for (int i = 0; i<n; i++) {
ranges[i].first = A[i];
ranges[i].second = B[i];
}
queryEngine.initQuery(ranges);
makeAll();
}
signed can(signed m, signed K[]) {
map<int, int> projects;
for (int i = 0; i<m; i++) {
projects[K[i]]++;
}
vector<pair<int, int>> s;
s.push_back({-1, n-1});
for (pair<int, int> i: projects) {
int groupsize = i.first;
int people = i.first * i.second;
int cnt = 0;
int beginR = allBeginR[groupsize], endL = allEndL[groupsize];
if (beginR == -1 || endL == -1) {return 0;}
// esay case: this group is out of the range
while (s.back().second < endL) {
s.pop_back();
if (s.empty()) return 0;
}
while (true) {
int add = queryEngine.query(s.back().first+1, beginR, endL, s.back().second);
if (cnt+add >= people) break;
cnt += add;
endL = s.back().second+1;
s.pop_back();
if (s.empty()) return 0;
}
int beginL = s.back().first+1;
int l = endL, r = s.back().second;
while (l<r) {
int mid = (l+r)/2;
int res = queryEngine.query(beginL, beginR, endL, mid);
if (res + cnt >= people) r = mid;
else l = mid+1;
}
s.push_back({beginR, l});
}
return 1;
}
