#include <bits/stdc++.h>
#define pb push_back
using namespace std;
#define mp(x...) array<int, 2>({x})
#include "teams.h"
constexpr static int DEBUG_SIZE = 10;
void __print(size_t i) { cerr << i; }
void __print(const char* s) { cerr << s; }
void __print(string s) { cerr << s; }
void __print(int* i) { cerr << "{"; cerr << i[0]; for (int j = 1; j < DEBUG_SIZE; j++) cerr << ", " << i[j]; cerr << "}"; }
void __print(int i) { cerr << i; }
template<typename T>
void __print(T& t) {cerr <<"{";int f = 0; for (auto& i : t) { cerr << ((f++) ? ", ": ""); __print(i); } cerr <<"}";}
void _print() { cerr << "]\n"; }
template<typename T, typename... V>
void _print(T t, V... v) { __print(t); if(sizeof...(v)) cerr << ", "; _print(v...); }
//#define DEBUGGING
#ifdef DEBUGGING
#define debug(x...) cerr << "[" << (#x) << "] = ["; _print(x)
#else
#define debug(x...)
#endif
constexpr static int MXSIZE = 1e6;
constexpr static int MXSEG = 1e8;
int n, st[MXSEG], l[MXSEG], r[MXSEG];
array<int, 2> intervals[MXSIZE];
array<int, 2> updates[MXSIZE+1];
int last = 1;
int query(int ll, int rr, int index, int ss, int ee)
{
if (ll >= ee || ss >= rr || index == -1)
return 0;
if (ee >= rr && ll >= ss)
return st[index];
int m = ll+rr>>1;
int lres = query(ll, m, l[index], ss, ee);
int rres = query(m, rr, r[index], ss, ee);
return lres + rres;
}
int update(int ll, int rr, int index, int i, int val)
{
if (ll + 1 == rr)
{
st[last] = val;
return last++;
}
int m = ll+rr>>1;
int lindex, rindex;
if (i < m)
{
lindex = update(ll, m, l[index], i, val);
rindex = (index == -1) ? -1 : r[index];
}
else
{
lindex = (index == -1) ? -1 : l[index];
rindex = update(m, rr, r[index], i, val);
}
l[last] = lindex;
r[last] = rindex;
st[last] = (lindex == -1) ? 0 : st[lindex];
st[last] += (rindex == -1) ? 0 : st[rindex];
return last++;
}
void config_st()
{
l[0] = r[0] = -1;
}
void init(int N, int A[], int B[])
{
n = N;
for (int i = 0; i < n; i++)
intervals[i] = mp(A[i], B[i]);
sort(intervals, intervals + n);
int last_root = 0;
updates[0] = mp(0, 0);
for (int i = 0; i < n; i++)
{
int old_count = query(0, n, last_root, intervals[i][1]-1, intervals[i][1]);
int new_root = update(0, n, last_root, intervals[i][1]-1, old_count+1);
updates[i+1] = mp(intervals[i][0], new_root);
debug(i+1, intervals[i][0], new_root);
last_root = new_root;
}
}
int can(int m, int k[])
{
sort(k, k+m);
vector<array<int, 2>> teams;
for (int i = 0; i < m; i++)
{
if (!teams.size() || end(teams)[-1][0] != k[i])
teams.pb(mp(k[i], 0));
end(teams)[-1][1]++;
}
debug(teams.size());
vector<array<int, 3>> stck; // Root, ending, additional (if at there are some free left in the ending)
for (int i = 0; i < teams.size(); i++)
{
int current_index = upper_bound(updates, updates + n, mp(teams[i][0] + 1, -1)) - updates;
if (teams[i][0] + 1 > updates[current_index][0])
current_index++;
if (!current_index)
return 0;
current_index--;
int current_root = updates[current_index][1];
int current_val = teams[i][0] * teams[i][1];
int last_l = teams[i][0] - 1;
debug(teams[i][0], teams[i][1], current_val, current_root, last_l);
while (stck.size())
{
if (last_l < end(stck)[-1][1])
{
debug("hi");
int prev_used = query(0, n, end(stck)[-1][0], last_l, end(stck)[-1][1]) - end(stck)[-1][2];
int current_available = query(0, n, current_root, last_l, end(stck)[-1][1]);
if (current_val + prev_used <= current_available)
break;
current_val += prev_used - current_available;
last_l = end(stck)[-1][1];
}
stck.pop_back();
}
int ending = n+1;
if (stck.size())
ending = end(stck)[-1][1]+1;
int ll = last_l, rr = ending;
debug(last_l, ending, current_val);
while (rr - ll > 1)
{
int m = ll+rr>>1;
int val = query(0, n, current_root, last_l, m);
if (stck.size())
{
val -= query(0, n, end(stck)[-1][0], last_l, m);
if (m == end(stck)[-1][1])
val += end(stck)[-1][2];
}
if (val >= current_val)
rr = m;
else
ll = m;
}
if (rr == ending)
return 0;
debug(current_root, last_l, rr, query(0, n, current_root, last_l, rr), query(0, n, current_root, 0, n));
int last_val = query(0, n, current_root, last_l, rr);
if (stck.size())
{
last_val -= query(0, n, end(stck)[-1][0], last_l, rr);
if (rr == end(stck)[-1][1])
last_val += end(stck)[-1][2];
}
stck.pb({current_root, rr, last_val - current_val});
debug(stck);
}
return 1;
}
