oj.uz

Submission #73980

# Submission time Handle Problem Language Result Execution time Memory
73980 2018-08-29T13:08:48 Z edisonhello Teams (IOI15_teams) C++14
77 / 100
 4000 ms 338488 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):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

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.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 240 ms 293884 KB Output is correct
2 Correct 232 ms 294056 KB Output is correct
3 Correct 238 ms 294056 KB Output is correct
4 Correct 241 ms 294056 KB Output is correct
5 Correct 247 ms 294056 KB Output is correct
6 Correct 249 ms 294056 KB Output is correct
7 Correct 264 ms 294056 KB Output is correct
8 Correct 236 ms 294056 KB Output is correct
9 Correct 240 ms 294056 KB Output is correct
10 Correct 242 ms 294056 KB Output is correct
11 Correct 227 ms 294128 KB Output is correct
12 Correct 241 ms 294128 KB Output is correct
13 Correct 238 ms 294128 KB Output is correct
14 Correct 247 ms 294128 KB Output is correct
15 Correct 246 ms 294128 KB Output is correct
16 Correct 244 ms 294128 KB Output is correct
17 Correct 250 ms 294128 KB Output is correct
18 Correct 252 ms 294160 KB Output is correct
19 Correct 238 ms 294228 KB Output is correct
20 Correct 250 ms 294228 KB Output is correct
21 Correct 264 ms 294228 KB Output is correct
22 Correct 285 ms 294228 KB Output is correct
23 Correct 270 ms 294228 KB Output is correct
24 Correct 243 ms 294228 KB Output is correct
25 Correct 281 ms 294228 KB Output is correct
26 Correct 249 ms 294228 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 344 ms 296456 KB Output is correct
2 Correct 304 ms 296556 KB Output is correct
3 Correct 320 ms 296556 KB Output is correct
4 Correct 294 ms 296940 KB Output is correct
5 Correct 335 ms 296940 KB Output is correct
6 Correct 266 ms 296940 KB Output is correct
7 Correct 275 ms 296940 KB Output is correct
8 Correct 284 ms 296940 KB Output is correct
9 Correct 286 ms 301356 KB Output is correct
10 Correct 284 ms 301356 KB Output is correct
11 Correct 282 ms 301356 KB Output is correct
12 Correct 257 ms 301356 KB Output is correct
13 Correct 251 ms 301356 KB Output is correct
14 Correct 255 ms 301356 KB Output is correct
15 Correct 283 ms 301356 KB Output is correct
16 Correct 272 ms 301356 KB Output is correct
17 Correct 239 ms 301356 KB Output is correct
18 Correct 278 ms 301356 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 289 ms 301356 KB Output is correct
2 Correct 336 ms 301356 KB Output is correct
3 Correct 456 ms 301356 KB Output is correct
4 Correct 279 ms 301356 KB Output is correct
5 Correct 3381 ms 301356 KB Output is correct
6 Correct 2784 ms 301464 KB Output is correct
7 Correct 276 ms 302348 KB Output is correct
8 Correct 2003 ms 303600 KB Output is correct
9 Correct 280 ms 308828 KB Output is correct
10 Correct 411 ms 309872 KB Output is correct
11 Correct 1543 ms 310580 KB Output is correct
12 Correct 1554 ms 310580 KB Output is correct
13 Correct 618 ms 310580 KB Output is correct
14 Correct 585 ms 311920 KB Output is correct
15 Correct 412 ms 311992 KB Output is correct
16 Correct 395 ms 313444 KB Output is correct
17 Correct 478 ms 314844 KB Output is correct
18 Correct 482 ms 316188 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 833 ms 325944 KB Output is correct
2 Correct 828 ms 326104 KB Output is correct
3 Correct 1409 ms 333336 KB Output is correct
4 Correct 838 ms 334644 KB Output is correct
5 Execution timed out 4046 ms 338488 KB Time limit exceeded
6 Halted 0 ms 0 KB -