Submission #73980

#	Time	Username	Problem	Language	Result	Execution time	Memory
73980		edisonhello	Teams (IOI15_teams)	C++14	77 / 100	4046 ms	338488 KiB

teams

// #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):l(0),r(0),sz(1),pri(rand()),val(v){}
} *root;

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();
    }
}
void del(node *&now){
    if(!now)return;
    del(now->l); del(now->r);
    delete now;
    now=0;
}

int solve(int m,int k[]){
    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,new node(p[ptr].second)),b);
            ++ptr;
        }
        node *a,*b;
        split_val(root,k[i]-1,a,b);
        del(a);
        if(!b || b->sz<k[i]){
            del(b);
            root=0;
            return 0;
        }
        node *c,*d;
        split_sz(b,k[i],c,d);
        del(c);
        root=d;
    }
    del(root);
    return 1;
}

}

#define BOUND 500
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 (stderr)

teams.cpp: In function 'naive::node* naive::merge(naive::node*, naive::node*)':
teams.cpp:68:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
     if(!a)return b; if(!b)return a;
     ^~
teams.cpp:68: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;
                     ^~

• Subtask 1: 21 / 21
• Subtask 2: 13 / 13
• Subtask 3: 43 / 43
• Subtask 4: 0 / 23