#include "teams.h"
#include <iostream>
#include <utility>
#include <algorithm>
#include <vector>
const int SZ = (1 << 20) + 5, SZ2 = 500005;
using namespace std;
struct p_node
{
int v = 0, l = -1, r = -1;
p_node() {}
};
int n, seg[SZ], lazy[SZ], pref[SZ2], suf[SZ2];
vector<p_node> p_seg;
vector<int> dt[SZ2];
int p_idx[SZ2];
void p_build(int idx, int L, int R)
{
if (L < R)
{
int M = L + R >> 1;
p_seg.push_back(p_node()); p_seg.push_back(p_node());
p_seg[idx].l = p_seg.size() - 2, p_seg[idx].r = p_seg.size() - 1;
p_build(p_seg[idx].l, L, M);
p_build(p_seg[idx].r, M + 1, R);
}
}
void p_upd(int idx, int odx, int L, int R, int x)
{
if (L <= R)
{
if (L == x && x == R) {p_seg[idx].v = p_seg[odx].v + 1;}
else
{
int M = L + R >> 1;
p_seg.push_back(p_node());
if (x <= M)
{
p_seg[idx].l = p_seg.size() - 1;
p_seg[idx].r = p_seg[odx].r;
p_upd(p_seg[idx].l, p_seg[odx].l, L, M, x);
}
else
{
p_seg[idx].r = p_seg.size() - 1;
p_seg[idx].l = p_seg[odx].l;
p_upd(p_seg[idx].r, p_seg[odx].r, M + 1, R, x);
}
p_seg[idx].v = p_seg[p_seg[idx].l].v + p_seg[p_seg[idx].r].v;
}
}
//cout << "UPD " << L << " " << R << " " << x << " " << p_seg[idx].v << "\n";
}
int p_qry(int idx, int L, int R, int l, int r)
{
l = max(L, l); r = min(R, r);
if (l <= r)
{
if (L == l && R == r) {return p_seg[idx].v;}
else
{
int M = L + R >> 1;
return p_qry(p_seg[idx].l, L, M, l, r) + p_qry(p_seg[idx].r, M + 1, R, l, r);
}
}
return 0;
}
void build(int idx, int L, int R)
{
if (L <= R)
{
if (L == R) {seg[idx] = pref[L - 1];}
else
{
int M = L + R >> 1;
build(2 * idx, L, M);
build(2 * idx + 1, M + 1, R);
seg[idx] = max(seg[2 * idx], seg[2 * idx + 1]);
}
}
}
inline void prop(int idx, int L, int R)
{
if (L <= R && lazy[idx])
{
seg[idx] += lazy[idx];
if (L < R)
{
lazy[2 * idx] += lazy[idx];
lazy[2 * idx + 1] += lazy[idx];
}
lazy[idx] = 0;
}
}
inline void upd(int idx, int L, int R, int l, int r, int v)
{
l = max(L, l); r = min(R, r);
prop(idx, L, R);
if (l <= r)
{
if (L == l && R == r) {lazy[idx] += v; prop(idx, L, R);}
else
{
int M = L + R >> 1;
upd(2 * idx, L, M, l, r, v);
upd(2 * idx + 1, M + 1, R, l, r, v);
seg[idx] = max(seg[2 * idx], seg[2 * idx + 1]);
}
}
}
void init(int N, int A[], int B[])
{
n = N;
for (int i = 0; i < n; i++)
{
pref[B[i]]++; suf[A[i]]++;
dt[B[i]].push_back(A[i]);
}
p_seg.push_back(p_node());
p_idx[0] = p_seg.size() - 1;
p_build(p_idx[0], 1, n);
for (int i = 1; i <= n; i++)
{
p_idx[i] = p_idx[i - 1];
for (auto &x : dt[i])
{
int nidx = p_seg.size();
p_seg.push_back(p_node());
p_upd(nidx, p_idx[i], 1, n, x);
p_idx[i] = nidx;
}
}
for (int i = 1; i <= n + 1; i++) {pref[i] += pref[i - 1];}
for (int i = n; i >= 0; i--) {suf[i] += suf[i + 1];}
build(1, 1, n);
}
int can(int M, int K[])
{
//cout << "New " << M << "\n";
sort(K, K + M);
int ret = 1;
for (int i = 0; i < M; i++)
{
upd(1, 1, n, 1, K[i], K[i]);
if (i)
{
//cout << i << " " << p_qry(p_idx[K[i] - 1], 1, n, K[i - 1] + 1, K[i] - 1) << "\n";
upd(1, 1, n, 1, K[i - 1], p_qry(p_idx[K[i] - 1], 1, n, K[i - 1] + 1, K[i] - 1));
}
upd(1, 1, n, 1, K[i], suf[K[i] + 1]);
if (seg[1] > n) {ret = 0;}
upd(1, 1, n, 1, K[i], -suf[K[i] + 1]);
}
for (int i = 0; i < M; i++)
{
upd(1, 1, n, 1, K[i], -K[i]);
if (i) {upd(1, 1, n, 1, K[i - 1], -p_qry(p_idx[K[i] - 1], 1, n, K[i - 1] + 1, K[i] - 1));}
}
return ret;
}
