Submission #74034

#	Time	Username	Problem	Language	Result	Execution time	Memory
74034		edisonhello	Teams (IOI15_teams)	C++14	34 / 100	1356 ms	525312 KiB

teams

// #include"teams.h"
#include<bits/stdc++.h>
#pragma GCC optimize("no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;

int root[500005],node[500005*45][3];
int ptr;

inline int gn(int ref=-1){
    ++ptr;
    if(~ref)memcpy(node[ptr],node[ref],3<<2);
    else memset(node[ptr],0,3<<2);
    return ptr;
}

int n;
pair<int,int> p[500005];

#define mid ((l+r)>>1)
void build(int now,int l,int r){
    if(l==r)return;
    build(node[now][0]=gn(),l,mid);
    build(node[now][1]=gn(),mid+1,r);
}

void modify(int now,int l,int r,int x){
    ++node[now][2];
    if(l==r){ return; }
    if(x<=mid)modify(node[now][0]=gn(node[now][0]),l,mid,x);
    else modify(node[now][1]=gn(node[now][1]),mid+1,r,x);
}

int query(int nl,int 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 node[nr][2]-node[nl][2];
    return query(node[nl][0],node[nr][0],l,mid,ql,qr)+query(node[nl][1],node[nr][1],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{
    int l,r,sz,pri,val;
    int lz();
    int rz();
    void pull(){ sz=lz()+rz()+1; }
    node(int v=0):l(-1),r(-1),sz(1),pri(rand()),val(v){}
} pool[500005];
int root=-1;
int node::lz(){ return ~l?pool[l].sz:0; }
int node::rz(){ return ~r?pool[r].sz:0; }

int _ptr;
int gnode(int v){
    pool[_ptr].l=-1;
    pool[_ptr].r=-1;
    pool[_ptr].sz=1;
    pool[_ptr].val=v;
    return _ptr++;
}

int merge(int a,int b){
    if(!~a)return b; if(!~b)return a;
    if(pool[a].pri>pool[b].pri){
        pool[a].r=merge(pool[a].r,b);
        pool[a].pull();
        return a;
    }
    else{
        pool[b].l=merge(a,pool[b].l);
        pool[b].pull();
        return b;
    }
}

void split_val(int now,int val,int &a,int &b){
    // if(now)cout<<"spliting "<<now<<endl;
    if(!~now){ a=b=-1; return; }
    if(pool[now].val<=val){
        a=now;
        split_val(pool[now].r,val,pool[a].r,b);
        pool[a].pull();
    }
    else{
        b=now;
        split_val(pool[now].l,val,a,pool[b].l);
        pool[b].pull();
    }
}

void split_sz(int now,int sz,int &a,int &b){
    if(!~now){ a=b=-1; return; }
    if(pool[now].lz()>=sz){
        b=now;
        split_sz(pool[now].l,sz,a,pool[b].l);
        pool[b].pull();
    }
    else{
        a=now;
        split_sz(pool[now].r,sz-1-pool[now].lz(),pool[a].r,b);
        pool[a].pull();
    }
}

int solve(int m,int k[]){
    _ptr=0;
    int ptr=1;
    for(int i=0;i<m;++i){
        // cout<<"solving i: "<<i<<endl;
        while(ptr<=n && p[ptr].first<=k[i]){
            int a,b;
            split_val(root,p[ptr].second,a,b);
            root=merge(merge(a,gnode(p[ptr].second)),b);
            ++ptr;
            // cout<<"now ptr: "<<ptr<<endl;
        }
        // cout<<"out while"<<endl;
        int a,b;
        split_val(root,k[i]-1,a,b);
        // cout<<"after split_val"<<endl;
        if(!~b || pool[b].sz<k[i]){
            root=0;
            return 0;
        }
        int c,d;
        split_sz(b,k[i],c,d);
        root=d;
    }
    return 1;
}

}

#define BOUND 385
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 'void init(int, int*, int*)':
teams.cpp:46:9: warning: declaration of 'ptr' shadows a global declaration [-Wshadow]
     int ptr=1;
         ^~~
teams.cpp:8:5: note: shadowed declaration is here
 int ptr;
     ^~~
teams.cpp: In function 'int naive::merge(int, int)':
teams.cpp:75:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
     if(!~a)return b; if(!~b)return a;
     ^~
teams.cpp:75:22: 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: 0 / 43
• Subtask 4: 0 / 23