#include"teams.h"
#include<bits/stdc++.h>
using namespace std;
struct node{
node *l,*r;
int v;
node():l(0),r(0),v(0){}
} *root[500005],pool[500005*25];
node *gn(node *ref=0){
static int ptr=-1; ++ptr;
if(ref){
pool[ptr].l=ref->l;
pool[ptr].r=ref->r;
pool[ptr].v=ref->v;
}
return &pool[ptr];
}
int n;
pair<int,int> p[500005];
#define mid ((l+r)>>1)
void build(node *now,int l,int r){
if(l==r)return;
build(now->l=gn(),l,mid);
build(now->r=gn(),mid+1,r);
}
void modify(node *now,int l,int r,int x){
++now->v;
if(l==r){ return; }
if(x<=mid)modify(now->l=gn(now->l),l,mid,x);
else modify(now->r=gn(now->r),mid+1,r,x);
}
int query(node *nl,node *nr,int l,int r,int ql,int qr){
if(r<ql || qr<l)return 0;
// cout<<"query range "<<l<<" to "<<r<<" cur v: "<<nl->v<<" and "<<nr->v<<endl;
if(ql<=l&&r<=qr)return nr->v-nl->v;
return query(nl->l,nr->l,l,mid,ql,qr)+query(nl->r,nr->r,mid+1,r,ql,qr);
}
void init(int _n,int _a[],int _b[]){
n=_n;
for(int i=0;i<n;++i)p[i+1]={_a[i],_b[i]};
sort(p+1,p+n+1);
build(root[0]=gn(),1,n);
int ptr=1;
for(int i=1;i<=n;++i){
root[i]=gn(root[i-1]);
while(ptr<=n && p[ptr].first<=i)modify(root[i]=gn(root[i]),1,n,p[ptr].second),++ptr;
}
}
namespace naive{
struct node{
node *l,*r;
int sz,pri,val;
int lz(){ return l?l->sz:0; }
int rz(){ return r?r->sz:0; }
void pull(){ sz=lz()+rz()+1; }
node(int v=0):l(0),r(0),sz(1),pri(rand()),val(v){}
} *root,pool[500005];
int _ptr;
node *gnode(int v){
pool[_ptr].val=v;
return &pool[_ptr++];
}
node *merge(node *a,node *b){
if(!a)return b; if(!b)return a;
if(a->pri>b->pri){
a->r=merge(a->r,b);
a->pull();
return a;
}
else{
b->l=merge(a,b->l);
b->pull();
return b;
}
}
void split_val(node *now,int val,node *&a,node *&b){
if(!now){ a=b=0; return; }
if(now->val<=val){
a=now;
split_val(now->r,val,a->r,b);
a->pull();
}
else{
b=now;
split_val(now->l,val,a,b->l);
b->pull();
}
}
void split_sz(node *now,int sz,node *&a,node *&b){
if(!now){ a=b=0; return; }
if(now->lz()>=sz){
b=now;
split_sz(now->l,sz,a,b->l);
b->pull();
}
else{
a=now;
split_sz(now->r,sz-1-now->lz(),a->r,b);
a->pull();
}
}
int solve(int m,int k[]){
_ptr=0;
int ptr=1;
for(int i=0;i<m;++i){
while(ptr<=n && p[ptr].first<=k[i]){
node *a,*b;
split_val(root,p[ptr].second,a,b);
root=merge(merge(a,gnode(p[ptr].second)),b);
++ptr;
}
node *a,*b;
split_val(root,k[i]-1,a,b);
if(!b || b->sz<k[i]){
root=0;
return 0;
}
node *c,*d;
split_sz(b,k[i],c,d);
root=d;
}
del(root);
return 1;
}
}
#define BOUND 580
int dp[BOUND+4];
int can(int m,int k[]){
sort(k,k+m);
// return naive::solve(m,k);
if(m>BOUND)return naive::solve(m,k);
else{
memset(dp,0x3f,sizeof(dp));
for(int i=0;i<m;++i){
int mn=9897788;
for(int j=0;j<=i;++j){
if(j==0)mn=query(root[0],root[k[i]],1,n,k[i],n);
else mn=min(mn,dp[j-1]+query(root[k[j-1]],root[k[i]],1,n,k[i],n));
// cout<<"j: "<<j<<" , mn: "<<mn<<endl;
}
dp[i]=mn-k[i];
// cout<<"at "<<i<<" , dp: "<<dp[i]<<endl;
if(dp[i]<0)return 0;
}
return 1;
}
}
#ifdef WEAK
int l[500005],r[500005];
int main(){
int n; cin>>n;
for(int i=0;i<n;++i)cin>>l[i]>>r[i];
init(n,l,r);
int m; cin>>m; while(m--){
int k; cin>>k;
int *a=new int[k];
for(int i=0;i<k;++i)cin>>a[i];
cout<<can(k,a)<<endl;
}
}
#endif
Compilation message
teams.cpp: In function 'naive::node* naive::merge(naive::node*, naive::node*)':
teams.cpp:73:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
if(!a)return b; if(!b)return a;
^~
teams.cpp:73:21: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
if(!a)return b; if(!b)return a;
^~
teams.cpp: In function 'int naive::solve(int, int*)':
teams.cpp:134:5: error: 'del' was not declared in this scope
del(root);
^~~
