#include "teams.h"
#include <bits/stdc++.h>
using namespace std;
#define rep(i , j ,k) for (int i = j; i < (int)k; i++)
#define lid id<<1
#define rid lid|1
typedef pair<int , int> pii;
typedef vector<int> vi;
inline bool smax(int &a, int b) {
if (a < b) {
a = b;
return true;
}
return false;
}
const int MAXN = 5e5 + 10;
int N;
pii arr[MAXN];
vi seg[MAXN << 2], Lp[MAXN << 2] , Rp[MAXN << 2];
int rem[MAXN << 2] , lazy[MAXN << 2];
void build(int l = 0, int r = N, int id = 1) {
rem[id] = 0;
lazy[id] = 0;
seg[id].resize(r - l);
Lp[id].resize(r - l + 1);
Rp[id].resize(r - l + 1);
if (l == r - 1) {
seg[id][0] = arr[l].second;
return;
}
int mid = l + r >> 1;
build(l , mid , lid);
build(mid , r ,rid);
int lptr = 0, rptr = 0;
int lsz = mid - l, rsz = r - mid;
auto Lm = [&]() {
int pos = lptr + rptr;
Lp[id][pos] = lptr;
Rp[id][pos] = rptr;
seg[id][pos] = seg[lid][lptr++];
};
auto Rm = [&]() {
int pos = lptr + rptr;
Lp[id][pos] = lptr;
Rp[id][pos] = rptr;
seg[id][pos] = seg[rid][rptr++];
};
while (lptr < lsz && rptr < rsz)
seg[lid][lptr] < seg[rid][rptr] ? Lm() : Rm();
while (lptr < lsz) Lm();
while (rptr < rsz) Rm();
Lp[id][lptr + rptr] = lptr;
Rp[id][lptr + rptr] = rptr;
}
inline void shift(int id) {
smax(lazy[lid] , Lp[id][lazy[id]]);
smax(lazy[rid] , Rp[id][lazy[id]]);
smax(rem[lid] , lazy[lid]);
smax(rem[rid] , lazy[rid]);
rem[id] = rem[lid] + rem[rid];
}
void segRem(int pos , int p2 , int& need , int l = 0, int r = N, int id= 1) {
if (r <= pos || need <= 0 || p2 <= rem[id]) return;
if (l >= pos && p2 - rem[id] <= need ) {
need -= p2 - rem[id];
rem[id] = p2;
lazy[id] = p2;
return;
}
int mid = l + r >> 1;
shift(id);
segRem(pos , Lp[id][p2] , need , l , mid , lid);
segRem(pos , Rp[id][p2] , need , mid , r, rid);
rem[id] = rem[lid] + rem[rid];
}
void segClear(int l = 0, int r = N, int id = 1) {
lazy[id] = rem[id] = 0;
if (l == r - 1) return;
int mid = l + r >> 1;
if (rem[lid]) segClear(l , mid , lid);
if (rem[rid]) segClear(mid , r, rid);
}
void init(int N2, int A[], int B[]) {
N = N2;
rep(i , 0 , N)
arr[i] = pii(B[i] , A[i]);
sort(arr ,arr + N);
build();
}
int can(int M, int K[]) {
bool flag = true;
sort(K , K + M);
for (int i = 0; i < M && flag; i++) {
int id = lower_bound(arr, arr + N , pii(K[i] , -1)) - arr;
int id2 = upper_bound(seg[1].begin() , seg[1].end() , K[i]) - seg[1].begin();
int need = K[i];
segRem(id , id2 , need);
if (need)
flag = false;
}
segClear();
return flag ? 1 : 0;
}
