#ifdef NYAOWO
#include "grader.cpp"
#endif
#include "teams.h"
#include <bits/stdc++.h>
#define For(i, a, b) for(int i = a; i <= b; i++)
#define Forr(i, a, b) for(int i = a; i >= b; i--)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define sz(x) ((int)x.size())
#define eb emplace_back
using namespace std;
using LL = long long;
using pii = pair<int, int>;
const int MAXN = 500'000;
const int MAXND = 10'000'000;
namespace SegTree {
struct Node {
Node *l, *r;
int sum;
Node(): l(nullptr), r(nullptr), sum(0) {}
} _nodes[MAXND + 10];
int _node_count = 0;
Node* new_node(Node* nd) {
_node_count++;
if(nd) _nodes[_node_count] = (*nd);
else _nodes[_node_count] = Node();
return (_nodes + _node_count);
}
Node* add(Node* rt, int l, int r, int i, int x) {
Node* nd = new_node(rt);
nd->sum += x;
if(l == r) return nd;
int m = (l + r) / 2;
if(i <= m) nd->l = add(nd->l, l, m, i, x);
else nd->r = add(nd->r, m + 1, r, i, x);
return nd;
}
int get_sum(Node* rt, int l, int r, int L, int R) {
if(!rt) return 0;
if(l >= L && r <= R) return rt->sum;
int m = (l + r) / 2;
int res = 0;
if(L <= m) res += get_sum(rt->l, l, m, L, R);
if(R > m) res += get_sum(rt->r, m + 1, r, L, R);
return res;
}
}
int n;
vector<int> v[MAXN + 10];
SegTree::Node* seg[MAXN + 10];
// int sum(int u, int d, int l, int r) {
// d--; l--;
// return ps[r][u] + ps[l][d] - ps[l][u] - ps[r][d];
// }
int sum(int u, int d, int l, int r) {
return SegTree::get_sum(seg[r], 1, n, d, u) - SegTree::get_sum(seg[l - 1], 1, n, d, u);
}
pii find_pos(int u, int d, int l, int r, int &rem){
For(y, d, u) For(x, l, r) {
int s = sum(y, y, x, x);
if(rem < s) return pii(x, y);
rem -= s;
}
assert(false);
}
void init(int N, int A[], int B[]) {
n = N;
For(i, 1, n) {
v[A[i - 1]].eb(B[i - 1]);
}
seg[0] = nullptr;
For(i, 1, n) {
seg[i] = seg[i - 1];
for(auto &x:v[i]) seg[i] = SegTree::add(seg[i], 1, n, x, 1);
}
// Forr(y, n, 1) For(x, 1, n) cerr << sum(y, y, x, x) << " \n"[x == n];
}
struct Ayaya {
int l, u, d, minus;
};
int can(int M, int K[]) {
sort(K, K + M);
vector<Ayaya> stk;
stk.eb((Ayaya){ 1, n, 1, 0 });
// auto out = [&]() {
// for(auto &i:stk) {
// cerr << i.l << " " << i.u << "~" << i.d << " (-" << i.minus << ")\n";
// }
// };
bool fail = false;
For(iter, 0, M - 1) {
int x = K[iter];
while(sz(stk) && (stk.back().u < x || stk.back().l > x)) stk.pop_back();
if(stk.empty()) {
fail = true;
goto END;
}
if(stk.back().d < x) stk.back().d = x;
// out();
int rem = x;
while(rem > 0) {
if(stk.empty()) {
fail = true;
goto END;
}
Ayaya aya = stk.back();
stk.pop_back();
int su = sum(aya.u, aya.d, aya.l, x) - aya.minus;
if(su <= rem) {
// cerr << su << " " << rem << " take all\n";
rem -= su;
continue;
}
rem += aya.minus;
pii pos = find_pos(aya.u, aya.d, aya.l, x, rem);
if(pos.S < aya.u) stk.eb((Ayaya){ aya.l, aya.u, pos.S + 1, 0 });
stk.eb((Ayaya){ pos.F, pos.S, pos.S, rem });
rem = 0;
}
if(stk.empty()) stk.eb((Ayaya){ x + 1, n, 1, 0 });
else if(stk.back().d > 1) stk.eb((Ayaya){ x + 1, stk.back().d - 1, 1, 0 });
}
END:
// cerr << "--- end of test ---\n";
if(fail) return 0;
return 1;
}
