#include "teams.h"
#include <algorithm>
#include <vector>
#include <cassert>
#include <iostream>
int const nmax = 5000000;
std::pair<int,int> v[5 + nmax];
std::vector<int> frec[5 + nmax];
namespace PST{
struct Node{
int result;
Node* left;
Node* right;
Node(int val = 0) {
result = val;
left = right = nullptr;
}
void refresh() {
this->result = this->left->result + this->right->result;
}
};
Node* build(int from, int to) {
Node *node = new Node(0);
if(from < to) {
int mid = (from + to) / 2;
node->left = build(from, mid);
node->right = build(mid + 1, to);
}
return node;
}
Node* initialize(int n) {
return build(1, n);
}
Node* update(Node* base, int from, int to, int x, int val) {
if(from < to) {
int mid = (from + to) / 2;
Node* newNode = new Node();
(*newNode) = (*base);
if(x <= mid)
newNode->left = update(base->left, from, mid, x, val);
else
newNode->right = update(base->right, mid + 1, to, x, val);
newNode->refresh();
return newNode;
} else
return (new Node(val));
}
int query(Node* node, int from, int to, int x, int y) {
assert(from <= x && x <= y && y <= to);
if(from == x && to == y)
return node->result;
else {
int mid = (from + to) / 2;
if(x <= mid && y <= mid)
return query(node->left, from, mid, x, y);
else if(mid + 1 <= x && mid + 1 <= y)
return query(node->right, mid + 1, to, x, y);
else
return query(node->left, from, mid,x , mid) +
query(node->right, mid + 1, to, mid + 1, y);
}
}
Node* version[5 + nmax];
int n;
void buildVersions(int n_) {
n = n_;
Node* part = initialize(n);
for(int i = 0; i <= n; i++) {
for(auto pos : frec[i]) {
part = update(part, 0, n - 1, pos, 1);
}
version[i] = part;
}
}
int KthElement(int from, int to, int k) {
int x = 0;
for(int jump = (1 << 20); 0 < jump; jump /= 2)
if(x + jump <= n && query(version[x + jump], 0, n - 1, from, to) < k)
x += jump;
return x + 1;
}
};
int n;
void init(int N, int A[], int B[]) {
n = N;
for(int i = 0; i < n; i++) {
v[i].first = A[i];
v[i].second = B[i];
}
std::sort(v, v + n);
for(int i = 0; i < n; i++)
frec[v[i].second].push_back(i);
PST::buildVersions(n);
}
struct Interval{
int x;
int y;
int pos;
};
int can(int M, int K[]) {
std::vector<int> queries(M);
for(int i = 0; i < M; i++)
queries[i] = K[i];
std::sort(queries.begin(), queries.end());
int ptr = 0;
std::vector<Interval> st;
for(int i = 0; i < M; i++) {
int newPtr = ptr;
for(int jump = (1 << 20); 0 < jump; jump /= 2)
if(newPtr + jump <= n && v[newPtr + jump - 1].first <= queries[i])
newPtr += jump;
if(ptr < newPtr)
st.push_back({ptr, newPtr - 1, 0});
ptr = newPtr;
int acc = queries[i];
while(0 < acc) {
if(1 == st.size()) {
st[0].pos = std::max(st[0].pos, PST::query(PST::version[queries[i] - 1], 0, n - 1, st[0].x, st[0].y));
if(st[0].pos + acc <= (st[0].y - st[0].x + 1)) {
st[0].pos += acc;
acc = 0;
break;
} else
return 0;
} else {
int stSize = st.size();
st[stSize - 1].pos = std::max(st[stSize - 1].pos, PST::query(PST::version[queries[i] - 1], 0, n - 1, st[stSize - 1].x, st[stSize - 1].y));
st[stSize - 2].pos = std::max(st[stSize - 2].pos, PST::query(PST::version[queries[i] - 1], 0, n - 1, st[stSize - 2].x, st[stSize - 2].y));
int val = PST::KthElement(st[stSize - 2].x, st[stSize - 2].y, st[stSize - 2].pos);
int newElements = std::max(0, PST::query(PST::version[val - 1], 0, n - 1, st[stSize - 1].x, st[stSize - 1].y) - st[stSize - 1].pos);
if(newElements <= acc) {
st[stSize - 2].pos += st[stSize - 1].pos + newElements;
st[stSize - 2].y = st[stSize - 1].y;
st.pop_back();
acc -= newElements;
} else {
st[stSize - 1].pos += acc;
acc = 0;
}
}
}
}
return 1;
}
