#include "teams.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct segment
{
int l, r;
segment(int _l = 0, int _r = 0)
{
l = _l;
r = _r;
}
};
const int maxn = 5e5 + 10;
struct node
{
node *lc, *rc;
int sum;
node(int _sum = 0)
{
lc = rc = NULL;
sum = _sum;
}
};
node *update(node *root, int left, int right, int pivot)
{
if (left == right)
{
int val = 1;
if (root != NULL)
val += root -> sum;
return new node(val);
}
int mid = (left + right) / 2;
node *new_root = new node();
if (root != NULL)
{
new_root -> lc = root -> lc; /// try to change this
new_root -> rc = root -> rc;
}
if (pivot <= mid)
new_root -> lc = update(new_root -> lc, left, mid, pivot);
else
new_root -> rc = update(new_root -> rc, mid + 1, right, pivot);
new_root -> sum = 0;
if (new_root -> lc != NULL)
new_root -> sum += new_root -> lc -> sum;
if (new_root -> rc != NULL)
new_root -> sum += new_root -> rc -> sum;
return new_root;
}
int query(node *root, int left, int right, int qleft, int qright)
{
if (left > qright || right < qleft || root == NULL)
return 0;
if (left >= qleft && right <= qright)
return root -> sum;
int mid = (left + right) / 2;
return query(root -> lc, left, mid, qleft, qright) +
query(root -> rc, mid + 1, right, qleft, qright);
}
int n;
segment s[maxn];
node *root[maxn];
vector < int > upd[maxn];
void init(int N, int A[], int B[])
{
n = N;
for (int i = 1; i <= n; i ++)
{
s[i] = segment(A[i - 1], B[i - 1]);
upd[A[i - 1]].push_back(B[i - 1]);
}
root[0] = NULL;
for (int i = 1; i <= n; i ++)
{
root[i] = root[i - 1];
for (int pivot : upd[i])
{
root[i] = update(root[i], 1, n, pivot);
}
}
///exit(0);
}
int zeta(int a, int b)
{
if (a >= b)
return 0;
return query(root[b], 1, n, b, n) - query(root[a], 1, n, b, n);
/**int cnt = 0;
for (int i = 1; i <= n; i ++)
{
if (s[i].l <= a && s[i].r >= a)
continue;
if (s[i].l <= b && s[i].r >= b)
cnt ++;
}
return cnt;*/
}
int pivot_change(int a, int b, int diff)
{
/// dp_a + z(a, i) > dp_b + z(b, i)
/// dp_b - dp_a < z(a, i) - z(b, i)
/// diff < ....
int lf = b, rf = n;
while(lf <= rf)
{
int mf = (lf + rf) / 2;
if (diff < zeta(a, mf) - zeta(b, mf))
lf = mf + 1;
else
rf = mf - 1;
}
return lf;
}
int dp[maxn];
int can(int M, int K[])
{
sort(K, K + M);
set < int > act;
set < pair < int, int > > event;
for (int i = 0; i < M; i ++)
{
while(!event.empty() && (*event.begin()).first <= K[i])
{
set < int > :: iterator it = act.find((*event.begin()).second);
event.erase({pivot_change(K[*prev(it)], K[*it], dp[*it] - dp[*prev(it)]), *it});
if (next(it) != act.end())
{
event.erase({pivot_change(K[*it], K[*next(it)], dp[*next(it)] - dp[*it]), *next(it)});
event.insert({pivot_change(K[*prev(it)], K[*next(it)], dp[*next(it)] - dp[*prev(it)]), *next(it)});
}
act.erase(it);
}
dp[i] = zeta(0, K[i]) - K[i];
if (!act.empty())
{
int bk = *act.rbegin();
dp[i] = min(dp[i], dp[bk] + zeta(K[bk], K[i]) - K[i]);
}
/**for (int j : act)
{
dp[i] = min(dp[i], dp[j] + zeta(K[j], K[i]) - K[i]);
}*/
if (dp[i] < 0)
return 0;
if (!act.empty())
{
int bk = *act.rbegin();
event.insert({pivot_change(K[bk], K[i], dp[i] - dp[bk]), i});
}
act.insert(i);
}
return 1;
}
