oj.uz

Submission #73990

# Submission time Handle Problem Language Result Execution time Memory
73990 2018-08-29T14:03:43 Z edisonhello Teams (IOI15_teams) C++14
77 / 100
 4000 ms 328364 KB 
#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].l=0;
    pool[_ptr].r=0;
    pool[_ptr].sz=1;
    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;
    }
    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:77:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
     if(!a)return b; if(!b)return a;
     ^~
teams.cpp:77: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.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 258 ms 309556 KB Output is correct
2 Correct 235 ms 309556 KB Output is correct
3 Correct 263 ms 309556 KB Output is correct
4 Correct 255 ms 309696 KB Output is correct
5 Correct 263 ms 309696 KB Output is correct
6 Correct 231 ms 309716 KB Output is correct
7 Correct 230 ms 309776 KB Output is correct
8 Correct 244 ms 309784 KB Output is correct
9 Correct 268 ms 309792 KB Output is correct
10 Correct 267 ms 309792 KB Output is correct
11 Correct 241 ms 309868 KB Output is correct
12 Correct 263 ms 309944 KB Output is correct
13 Correct 277 ms 309944 KB Output is correct
14 Correct 228 ms 309944 KB Output is correct
15 Correct 252 ms 309944 KB Output is correct
16 Correct 249 ms 309944 KB Output is correct
17 Correct 270 ms 309944 KB Output is correct
18 Correct 303 ms 309944 KB Output is correct
19 Correct 320 ms 309944 KB Output is correct
20 Correct 250 ms 309944 KB Output is correct
21 Correct 249 ms 309944 KB Output is correct
22 Correct 226 ms 309944 KB Output is correct
23 Correct 231 ms 309944 KB Output is correct
24 Correct 254 ms 309944 KB Output is correct
25 Correct 281 ms 309944 KB Output is correct
26 Correct 272 ms 309944 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 286 ms 312172 KB Output is correct
2 Correct 309 ms 312172 KB Output is correct
3 Correct 296 ms 312300 KB Output is correct
4 Correct 312 ms 312692 KB Output is correct
5 Correct 261 ms 312692 KB Output is correct
6 Correct 260 ms 312692 KB Output is correct
7 Correct 301 ms 312692 KB Output is correct
8 Correct 285 ms 312692 KB Output is correct
9 Correct 308 ms 312692 KB Output is correct
10 Correct 264 ms 312692 KB Output is correct
11 Correct 297 ms 312692 KB Output is correct
12 Correct 265 ms 312692 KB Output is correct
13 Correct 295 ms 312692 KB Output is correct
14 Correct 290 ms 312692 KB Output is correct
15 Correct 346 ms 312692 KB Output is correct
16 Correct 342 ms 312692 KB Output is correct
17 Correct 307 ms 312692 KB Output is correct
18 Correct 271 ms 312692 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 304 ms 312700 KB Output is correct
2 Correct 339 ms 312772 KB Output is correct
3 Correct 530 ms 315500 KB Output is correct
4 Correct 328 ms 315500 KB Output is correct
5 Correct 3284 ms 315500 KB Output is correct
6 Correct 2457 ms 315500 KB Output is correct
7 Correct 316 ms 315500 KB Output is correct
8 Correct 2182 ms 315500 KB Output is correct
9 Correct 304 ms 315500 KB Output is correct
10 Correct 398 ms 315500 KB Output is correct
11 Correct 1332 ms 315500 KB Output is correct
12 Correct 1592 ms 315500 KB Output is correct
13 Correct 684 ms 315500 KB Output is correct
14 Correct 534 ms 315500 KB Output is correct
15 Correct 405 ms 315500 KB Output is correct
16 Correct 407 ms 315500 KB Output is correct
17 Correct 496 ms 315500 KB Output is correct
18 Correct 516 ms 315500 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 805 ms 322492 KB Output is correct
2 Correct 831 ms 322556 KB Output is correct
3 Correct 1403 ms 328364 KB Output is correct
4 Correct 836 ms 328364 KB Output is correct
5 Execution timed out 4030 ms 328364 KB Time limit exceeded
6 Halted 0 ms 0 KB -