#include "teams.h"
#include <bits/stdc++.h>
using namespace std;
struct ptreenode
{
int left, right, val; // val = num
};
ptreenode ptree[20000000];
int upto;
void pupdate(int node, int curr, int oldcurr, int cstart = 0, int cend = 500010)
{
if (cstart == cend)
{
ptree[curr].val = ptree[oldcurr].val+1;
return;
}
int mid = (cstart+cend)/2;
if (node <= mid)
{
ptree[curr].left = ++upto;
ptree[curr].right = ptree[oldcurr].right;
pupdate(node, ptree[curr].left, ptree[oldcurr].left, cstart, mid);
}
else
{
ptree[curr].right = ++upto;
ptree[curr].left = ptree[oldcurr].left;
pupdate(node, ptree[curr].right, ptree[oldcurr].right, mid+1, cend);
}
ptree[curr].val = ptree[ptree[curr].left].val + ptree[ptree[curr].right].val;
}
int pquery(int s, int e, int curr, int cstart = 0, int cend = 500010)
{
if (s <= cstart && cend <= e) return ptree[curr].val;
int mid = (cstart+cend)/2;
if (e <= mid) return pquery(s, e, ptree[curr].left, cstart, mid);
else if (s > mid) return pquery(s, e, ptree[curr].right, mid+1, cend);
else return pquery(s, e, ptree[curr].left, cstart, mid) + pquery(s, e, ptree[curr].right, mid+1, cend);
}
struct otreenode
{
int left, right, val, last, lazy; // val = last in its subtree;
};
otreenode otree[20000000];
int upto2, n;
int roots[500010];
void push(int curr, int cstart, int mid, int cend)
{
if (!otree[curr].left) otree[curr].left = ++upto2;
if (!otree[curr].right) otree[curr].right = ++upto2;
if (!otree[curr].lazy) return;
int l = otree[curr].left;
int r = otree[curr].right;
otree[l].last = otree[r].last = otree[l].lazy = otree[r].lazy = otree[curr].lazy;
int a = pquery(cstart, mid, roots[otree[curr].lazy]);
int b = pquery(mid+1, cend, roots[otree[curr].lazy]);
// printf("%d %d %d a %d b %d\n", cstart, mid, cend, a, b);
otree[l].val = a;
otree[r].val = b;
otree[curr].lazy = 0;
}
void oupdate(int s, int e, int val, int curr, int cstart = 0, int cend = 500010)
{
if (s <= cstart && cend <= e)
{
// printf("updating %d %d %d\n", cstart, cend, val);
otree[curr].last = otree[curr].lazy = val;
int a = pquery(cstart, cend, roots[val]);
otree[curr].val = a;
// printf("a %d\n", a);
return;
}
int mid = (cstart+cend)/2;
push(curr, cstart, mid, cend);
if (e <= mid) oupdate(s, e, val, otree[curr].left, cstart, mid);
else if (s > mid) oupdate(s, e, val, otree[curr].right, mid+1, cend);
else
{
oupdate(s, e, val, otree[curr].left, cstart, mid);
oupdate(s, e, val, otree[curr].right, mid+1, cend);
}
otree[curr].val = otree[otree[curr].left].val + otree[otree[curr].right].val;
otree[curr].last = otree[otree[curr].right].last;
}
int treewalkfindfirstbelow(int val, int curr, int cstart = 0, int cend = 500010)
{
if (cstart == cend) return cstart;
int mid = (cstart+cend)/2;
push(curr, cstart, mid, cend);
if (otree[otree[curr].left].last <= val) return treewalkfindfirstbelow(val, otree[curr].left, cstart, mid);
else return treewalkfindfirstbelow(val, otree[curr].right, mid+1, cend);
}
int ROOT;
int othertreewalk(int amreq, int e, int curr, int cstart = 0, int cend = 500010, int amtoside = 0)
{
if (cstart == cend)
{
amtoside += otree[curr].val;
int hei = otree[curr].last;
//printf("%d %d %d - %d %d\n", amreq, e, cstart, pquery(cstart, e, roots[n]), amtoside);
if (pquery(cstart, e, roots[n])-amtoside < amreq)
{
// Impossible
// what a shame
return 0;
}
int S = hei;
int E = n;
while (S != E)
{
int mid = (S+E)/2;
if (pquery(cstart, e, roots[mid])-amtoside < amreq) S = mid+1;
else E = mid;
}
// printf("%d %d %d - %d, %d %d\n", cstart, e, S, amreq, pquery(cstart, e, roots[S]), amtoside);
oupdate(cstart, e, S, ROOT);
return 1;
}
int mid = (cstart+cend)/2;
push(curr, cstart, mid, cend);
// consider last in left subtree
int h = otree[otree[curr].left].last;
int am = -1;
if (mid+1 <= e) am = pquery(mid+1, e, roots[h]) - otree[otree[curr].right].val - amtoside;
// printf("%d %d am %d - %d mid+1, e, %d %d - query %d right val %d, amtoside %d\n", cstart, cend, am, h, mid+1, e, am+otree[otree[curr].right].val + amtoside, otree[otree[curr].right].val, amtoside);
if (am < amreq) // have to go to left
{
amtoside += otree[otree[curr].right].val;
return othertreewalk(amreq, e, otree[curr].left, cstart, mid, amtoside);
}
else
{
return othertreewalk(amreq, e, otree[curr].right, mid+1, cend, amtoside);
}
}
int lastA[500010];
int lastB[500010];
int x[500010], y[500010];
void init(int N, int A[], int B[]) {
n = N;
fill_n(lastA, 500010, 0);
fill_n(lastB, 500010, 0);
vector<pair<int, int> > sortedbyA;
for (int i = 0; i < n; i++)
{
sortedbyA.emplace_back(A[i], i);
}
sort(sortedbyA.begin(), sortedbyA.end());
for (int i = 0; i < n; i++)
{
if (i == n-1)
{
for (int j = sortedbyA[i].first; j <= N; j++) lastA[j] = i+1;
}
else if (sortedbyA[i].first != sortedbyA[i+1].first)
{
for (int j = sortedbyA[i].first; j < sortedbyA[i+1].first; j++)
{
lastA[j] = i+1;
}
}
x[sortedbyA[i].second] = i+1;
}
sortedbyA.clear();
for (int i = 0; i < n; i++)
{
sortedbyA.emplace_back(B[i], i);
}
sort(sortedbyA.begin(), sortedbyA.end());
for (int i = 0; i < n; i++)
{
if (i == n-1)
{
for (int j = sortedbyA[i].first; j <= N; j++) lastB[j] = i+1;
}
else if (sortedbyA[i].first != sortedbyA[i+1].first)
{
for (int j = sortedbyA[i].first; j < sortedbyA[i+1].first; j++)
{
lastB[j] = i+1;
}
}
y[sortedbyA[i].second] = i+1;
}
sortedbyA.clear();
for (int i = 0; i < n; i++)
{
// printf("%d %d\n", x[i], y[i]);
sortedbyA.emplace_back(y[i], x[i]);
}
sort(sortedbyA.begin(), sortedbyA.end());
for (auto a : sortedbyA)
{
// assert(!roots[a.first]);
roots[a.first] = ++upto;
// printf("at %d - updating %d\n", a.first, a.second);
pupdate(a.second, roots[a.first], roots[a.first-1]);
// printf("%d\n", pquery(0, n, roots[a.first]));
}
}
int can(int m, int k[]) {
sort(k, k+m);
int r = ++upto2;
ROOT = r;
for (int i = 0; i < m; i++)
{
int a = lastA[k[i]];
int b = lastB[k[i]-1];
int s = treewalkfindfirstbelow(b, r);
// printf("%d\n", s);
if (s <= n) oupdate(s, n, b, r);
int res = othertreewalk(k[i], a, r);
if (!res) return 0;
}
return 1;
}
