#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 pb push_back #define fi first #define se second const int MAXN = 5e5+10; struct Node { int val; Node *l, *r; Node(int x) : val(x), l(nullptr), r(nullptr) {} Node(Node *ll, Node *rr) { l = ll, r = rr; val = 0; if(l) val += l->val; if(r) val += r->val; } Node(Node *cp) : val(cp->val), l(cp->l), r(cp->r) {} }; pii a[MAXN]; vector<int> ri[MAXN], li[MAXN]; int n, si =0; Node *pseg[MAXN]; bool tag = 1; Node *build(int l, int r) { if(l==r) return new Node(0); int mid = (l+r)/2; return new Node(build(l, mid), build(mid+1,r)); } Node *update(Node *i, int ti, int x, int l, int r) { if(l==r) return new Node(x+i->val); int mid = (l+r)/2; if(ti <= mid) return new Node(update(i->l, ti, x, l, mid), i->r); else return new Node(i->l,update(i->r, ti, x, mid +1, r)); } int find(Node *i, int tl, int k, int l , int r) { if(l==r) return l; int mid =(l+r)/2; int s = i->l->val; if(s>=k) return find(i->l,tl,k,l,mid); else return find(i->r,tl,k-s,mid+1,r); } int query(Node *i, int tl, int k, int l, int r) { if(tl>r) return 0; if(tl<=l) { if(tag && i->val >= k-si) { tag=0; return find(i,tl,k-si,l,r); } else { si+=i->val; return 0; } } int mid = (l+r)/2; return query(i->l,tl,k,l,mid) + query(i->r,tl,k,mid+1,r); } struct BIT { int bit[MAXN]; void update(int i, int x) { for(; i <= n; i+=(i&-i)) bit[i]+=x; } int query(int i) { int ans = 0; for(; i > 0; i-=(i&-i)) ans+=bit[i]; return ans; } int sum(int l, int r) { return query(r)-query(l-1); } } bit; void init(int N, int A[], int B[]) { n = N; rep(i,0,N-1) ri[A[i]].pb(B[i]), li[B[i]].pb(A[i]); pseg[1] = build(1,n); rep(i,1,n) { if(i>1) pseg[i] = new Node(pseg[i-1]); for(int &x : ri[i]) pseg[i] = update(pseg[i], x,1,1,n); } } int can(int M, int K[]) { vector<pii> op; sort(K, K+M); bool ok = 1; rep(i,0,M-1) { int x = K[i], cnt = x; while (cnt > 0) { tag=1; si=0; int kth = bit.query(x)+1; int j = query(pseg[x],x,kth,1,n); if (j==0 || li[j].size() == 0) { ok=0; i=M; break; } op.pb({li[j].back(),j}); bit.update(li[j].back(), 1); bit.update(j+1, -1); li[j].pop_back(); cnt--; } } for(auto &[L,R] : op) { bit.update(L,-1), bit.update(R+1,1), li[R].pb(L); } return ok; }