#include "teams.h"
#include <bits/stdc++.h>
using namespace std;
struct Node {
vector<int> vals;
vector<pair<int, int>> mp;
int debt, lazy;
};
#define MAXN 500500
vector<int> byb[MAXN];
Node nodes[4*MAXN];
int gn=0;
void build(int n, int l, int r) {
Node &nd=nodes[n];
nd.debt=nd.lazy=0;
nd.vals.clear();
nd.mp.clear();
if(l==r) {
nd.vals=byb[l];
sort(nd.vals.begin(), nd.vals.end());
return;
}
int mid=(l+r)/2;
build(2*n, l, mid);
build(2*n+1, mid+1, r);
vector<int> &vl=nodes[2*n].vals, &vr=nodes[2*n+1].vals;
int i=0, j=0;
nd.mp.push_back({0, 0});
while(i<(int)vl.size()&&j<(int)vr.size()) {
if(vl[i]<=vr[j]) {
nd.vals.push_back(vl[i]);
++i;
} else {
nd.vals.push_back(vr[j]);
++j;
}
nd.mp.push_back({i, j});
}
while(i<(int)vl.size()) {
nd.vals.push_back(vl[i]);
++i;
nd.mp.push_back({i, j});
}
while(j<(int)vr.size()) {
nd.vals.push_back(vr[j]);
++j;
nd.mp.push_back({i, j});
}
}
void lazyPropagation(int n, int l, int r) {
Node &nd=nodes[n];
if(!nd.lazy) return;
nd.lazy=0;
if(l==r) return;
nodes[2*n].debt=nd.mp[nd.debt].first;
nodes[2*n+1].debt=nd.mp[nd.debt].second;
nodes[2*n].lazy=nodes[2*n+1].lazy=1;
}
int query(int n, int l, int r, int p, int a, int s) {
lazyPropagation(n, l, r);
if(p>r||!s) return 0;
Node &nd=nodes[n];
int mid=(l+r)/2;
if(p>l) {
int lv=query(2*n, l, mid, p, nd.mp[a].first, s);
nd.debt+=lv;
int rv=query(2*n+1, mid+1, r, p, nd.mp[a].second, s-lv);
nd.debt+=rv;
return lv+rv;
}
int can=max(0, a-nd.debt);
if(!can) return 0;
if(l==r) {
can=min(can, s);
nd.debt+=can;
return can;
}
if(can<=s) {
nd.debt+=can;
nd.lazy=1;
return can;
}
int lv=query(2*n, l, mid, p, nd.mp[a].first, s);
nd.debt+=lv;
int rv=query(2*n+1, mid+1, r, p, nd.mp[a].second, s-lv);
nd.debt+=rv;
return lv+rv;
}
void init(int N, int A[], int B[]) {
for(int i=0;i<N;i++) {
byb[B[i]].push_back(A[i]);
}
build(1, 1, N);
gn=N;
}
int can(int M, int K[]) {
sort(K, K+M);
int ans=1;
for(int i=0;i<M;i++) {
int r=query(1, 1, gn, K[i], (int)(upper_bound(nodes[1].vals.begin(), nodes[1].vals.end(), K[i])-nodes[1].vals.begin()), K[i]);
if(r<K[i]) {
ans=0;
break;
}
}
nodes[1].debt=0;
nodes[1].lazy=1;
return ans;
}
