oj.uz

Submission #73991

# Submission time Handle Problem Language Result Execution time Memory
73991 2018-08-29T14:06:29 Z edisonhello Teams (IOI15_teams) C++14
77 / 100
 4000 ms 328364 KB 
// #include"teams.h"
#include<bits/stdc++.h>
#pragma GCC optimize("no-stack-protector")
#pragma GCC target("avx,avx2,sse,sse2,sse3,ssse3,sse4,tune=native")
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:79:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
     if(!a)return b; if(!b)return a;
     ^~
teams.cpp:79: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 272 ms 309572 KB Output is correct
2 Correct 264 ms 309724 KB Output is correct
3 Correct 234 ms 309724 KB Output is correct
4 Correct 240 ms 309756 KB Output is correct
5 Correct 311 ms 309756 KB Output is correct
6 Correct 272 ms 309772 KB Output is correct
7 Correct 266 ms 309772 KB Output is correct
8 Correct 282 ms 309772 KB Output is correct
9 Correct 250 ms 309772 KB Output is correct
10 Correct 236 ms 309772 KB Output is correct
11 Correct 237 ms 309772 KB Output is correct
12 Correct 260 ms 309828 KB Output is correct
13 Correct 253 ms 309828 KB Output is correct
14 Correct 284 ms 309876 KB Output is correct
15 Correct 285 ms 309876 KB Output is correct
16 Correct 292 ms 309876 KB Output is correct
17 Correct 280 ms 309876 KB Output is correct
18 Correct 267 ms 309876 KB Output is correct
19 Correct 256 ms 309876 KB Output is correct
20 Correct 246 ms 309876 KB Output is correct
21 Correct 240 ms 309876 KB Output is correct
22 Correct 243 ms 309876 KB Output is correct
23 Correct 275 ms 309876 KB Output is correct
24 Correct 318 ms 309936 KB Output is correct
25 Correct 252 ms 309936 KB Output is correct
26 Correct 255 ms 309936 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 306 ms 312164 KB Output is correct
2 Correct 297 ms 312216 KB Output is correct
3 Correct 349 ms 312216 KB Output is correct
4 Correct 304 ms 312580 KB Output is correct
5 Correct 338 ms 312580 KB Output is correct
6 Correct 297 ms 312580 KB Output is correct
7 Correct 293 ms 312580 KB Output is correct
8 Correct 302 ms 312580 KB Output is correct
9 Correct 301 ms 312580 KB Output is correct
10 Correct 337 ms 312580 KB Output is correct
11 Correct 332 ms 312580 KB Output is correct
12 Correct 320 ms 312580 KB Output is correct
13 Correct 300 ms 312580 KB Output is correct
14 Correct 269 ms 312580 KB Output is correct
15 Correct 300 ms 312580 KB Output is correct
16 Correct 337 ms 312580 KB Output is correct
17 Correct 302 ms 312580 KB Output is correct
18 Correct 294 ms 312580 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 361 ms 312580 KB Output is correct
2 Correct 312 ms 312580 KB Output is correct
3 Correct 509 ms 315544 KB Output is correct
4 Correct 340 ms 315544 KB Output is correct
5 Correct 3383 ms 315544 KB Output is correct
6 Correct 2425 ms 315544 KB Output is correct
7 Correct 315 ms 315544 KB Output is correct
8 Correct 1985 ms 315544 KB Output is correct
9 Correct 280 ms 315544 KB Output is correct
10 Correct 382 ms 315544 KB Output is correct
11 Correct 1267 ms 315544 KB Output is correct
12 Correct 1713 ms 315544 KB Output is correct
13 Correct 580 ms 315544 KB Output is correct
14 Correct 530 ms 315544 KB Output is correct
15 Correct 436 ms 315544 KB Output is correct
16 Correct 372 ms 315544 KB Output is correct
17 Correct 460 ms 315544 KB Output is correct
18 Correct 428 ms 315544 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 783 ms 322444 KB Output is correct
2 Correct 782 ms 322444 KB Output is correct
3 Correct 1416 ms 328364 KB Output is correct
4 Correct 873 ms 328364 KB Output is correct
5 Execution timed out 4050 ms 328364 KB Time limit exceeded
6 Halted 0 ms 0 KB -