#include "teams.h"
#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define X first
#define Y second
#define all(x) x.begin(), x.end()
const int maxn = 1e5 + 5;
int n;
pii p[maxn];
int rec[maxn];
vector<int> tree[maxn];
int used[maxn];
int sz[maxn];
int bsearch(int x, int val) {
int l = used[x], r = sz[x]-1, mid, pos = used[x];
while(l<=r) {
mid = (l+r)/2;
if(tree[x][mid]<=val) {
pos = mid;
l = mid+1;
}
else r = mid-1;
}
return pos;
}
void add(int x, int y) {
while(x<=n) {
// printf("\t\tadd %d : %d\n",x,y);
tree[x].push_back(y);
x += x&-x;
}
}
int query(int x, int y) {
int res = 0;
while(x>0) {
// printf("\t\tquery %d : %d\n",x,y);
if(!tree[x].empty()) {
// printf("\t\t\t");
// for(auto t : tree[x]) {
// if(t==used[x]) printf("*");
// printf("%d ",t);
// }
// printf("\n");
auto it = bsearch(x, y);
res += it - used[x];
}
x -= x&-x;
}
return res;
}
void change(int x, int y) {
while(x>0) {
if(!tree[x].empty()) {
if(used[x] < y) {
used[x] = bsearch(x, y);
// printf("used %d : %d (%d)\n",x,used[x],y);
}
}
x -= x&-x;
}
}
void reset(int x) {
while(x>0) {
if(!tree[x].empty()) {
used[x] = 0;
// printf("used %d : %d\n",x,used[x]);
}
x -= x&-x;
}
}
bool cmp(pii x, pii y) {
return x.Y < y.Y;
}
int bsearch2(int x) {
int l,r,mid,pos1,pos2;
l = 1; r = n; pos1 = 0;
while(l<=r) {
mid = (l+r)/2;
if(rec[mid]<x) {
pos1 = mid;
l = mid+1;
}
else r = mid-1;
}
l = 1; r = n; pos2 = 0;
while(l<=r) {
mid = (l+r)/2;
if(rec[mid]>=rec[pos1]) {
pos2 = mid;
r = mid-1;
}
else l = mid+1;
}
// printf("bsearch2 %d = %d\n",x,pos);
return pos2;
}
void init(int N, int A[], int B[]) {
n = N;
for(int i=0;i<n;i++) p[i] = {A[i],B[i]};
sort(p,p+n,cmp);
for(int i=0;i<n;i++) rec[i+1] = p[i].Y, p[i].Y = i+1;
for(int i=0;i<n;i++) add(p[i].X,p[i].Y);
for(int i=1;i<=n;i++) {
tree[i].push_back(0);
sort(all(tree[i]));
used[i] = 0;
sz[i] = tree[i].size();
}
}
int can(int m, int K[]) {
int res = 1;
sort(K, K+m);
for(int i=0;i<m;i++) reset(K[i]);
for(int i=0;i<m;i++) {
change(K[i], bsearch2(K[i]));
// printf("i = %d\n",i);
int l = 1, r = n, mid, pos = -1;
while(l<=r) {
mid = (l+r)/2;
// printf("---- bsearch : %d\n",mid);
if(query(K[i],mid) >= K[i]) {
pos = mid;
r = mid-1;
}
else l = mid+1;
}
if(pos==-1) res = 0;
change(K[i], pos);
// printf("------------------------------\n");
}
return res;
}
