#include "teams.h" #include <bits/stdc++.h> using namespace std; #define rep(i,a,b) for (int i = a; i <= b; i++) #define pii pair<int,int> #define fi first #define se second const int MAXN = 5e5+10; // ONLY FOR LOCAL pii a[MAXN]; int n, cnt[MAXN]; bool tag = 1; struct Seg3 { int seg[4*MAXN]; void update(int ti, int x, int i = 1, int l = 1, int r = n) { if(l==r && ti == l) { seg[i] += x; return; } int mid = (l+r)/2; if(ti<= mid) update(ti, x, 2*i, l, mid); else update(ti, x, 2*i+1, mid +1, r); seg[i] = seg[2*i] + seg[2*i+1]; } int find(int i, int l, int r) { if(l==r) return l; int mid = (l+r)/2; if(seg[2*i] > 0) return find(2*i,l,mid); else return find(2*i+1,mid+1,r); } int query(int tl, int tr, int i = 1, int l = 1, int r = n) { if(tr < l || r < tl) return 0LL; if (tl <= l && tr >= r) { if(tag && seg[i]>0) { tag = 0; return find(i,l,r); } return 0; } int mid = (l+r)/2; return query(tl,tr,2*i,l,mid) + query(tl,tr,2*i+1,mid+1,r); } }; Seg3 seg; void init(int N, int A[], int B[]) { n = N; rep(i,0,N-1) a[i+1] = {B[i],A[i]}; sort(a+1, a+n+1); } int can(int M, int K[]) { int s = 0; rep(i,0,M-1) seg.update(K[i],K[i]), s+=K[i], cnt[K[i]]+=K[i]; rep(i,1,n) { tag=1; int k = seg.query(a[i].se, a[i].fi); //cout << a[i].se << ' ' << a[i].fi << ' ' << k << '\n'; if(k!=0) { cnt[k]--; s--; seg.update(k,-1); } } rep(i,0,M-1) { if(cnt[K[i]] == 0) continue; seg.update(K[i],-cnt[K[i]]); cnt[K[i]] = 0; } return s==0; }