oj.uz

Submission #73992

# Submission time Handle Problem Language Result Execution time Memory
73992 2018-08-29T14:07:34 Z edisonhello Teams (IOI15_teams) C++14
77 / 100
 4000 ms 445732 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*35];

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 354 ms 427000 KB Output is correct
2 Correct 329 ms 427108 KB Output is correct
3 Correct 322 ms 427144 KB Output is correct
4 Correct 345 ms 427224 KB Output is correct
5 Correct 338 ms 427224 KB Output is correct
6 Correct 363 ms 427224 KB Output is correct
7 Correct 351 ms 427268 KB Output is correct
8 Correct 358 ms 427272 KB Output is correct
9 Correct 355 ms 427272 KB Output is correct
10 Correct 336 ms 427324 KB Output is correct
11 Correct 339 ms 427324 KB Output is correct
12 Correct 340 ms 427324 KB Output is correct
13 Correct 349 ms 427324 KB Output is correct
14 Correct 325 ms 427324 KB Output is correct
15 Correct 364 ms 427376 KB Output is correct
16 Correct 328 ms 427376 KB Output is correct
17 Correct 320 ms 427376 KB Output is correct
18 Correct 372 ms 427376 KB Output is correct
19 Correct 351 ms 427376 KB Output is correct
20 Correct 368 ms 427376 KB Output is correct
21 Correct 370 ms 427376 KB Output is correct
22 Correct 367 ms 427376 KB Output is correct
23 Correct 355 ms 427376 KB Output is correct
24 Correct 354 ms 427376 KB Output is correct
25 Correct 354 ms 427376 KB Output is correct
26 Correct 361 ms 427376 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 505 ms 429820 KB Output is correct
2 Correct 435 ms 429820 KB Output is correct
3 Correct 482 ms 429820 KB Output is correct
4 Correct 457 ms 429948 KB Output is correct
5 Correct 410 ms 429948 KB Output is correct
6 Correct 387 ms 429948 KB Output is correct
7 Correct 405 ms 429948 KB Output is correct
8 Correct 380 ms 429948 KB Output is correct
9 Correct 394 ms 429948 KB Output is correct
10 Correct 396 ms 429948 KB Output is correct
11 Correct 394 ms 429948 KB Output is correct
12 Correct 367 ms 429948 KB Output is correct
13 Correct 386 ms 429948 KB Output is correct
14 Correct 396 ms 429948 KB Output is correct
15 Correct 440 ms 429948 KB Output is correct
16 Correct 403 ms 429948 KB Output is correct
17 Correct 405 ms 429948 KB Output is correct
18 Correct 364 ms 429948 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 421 ms 429948 KB Output is correct
2 Correct 430 ms 429952 KB Output is correct
3 Correct 604 ms 432996 KB Output is correct
4 Correct 412 ms 432996 KB Output is correct
5 Correct 3126 ms 432996 KB Output is correct
6 Correct 2400 ms 432996 KB Output is correct
7 Correct 351 ms 432996 KB Output is correct
8 Correct 1923 ms 432996 KB Output is correct
9 Correct 360 ms 432996 KB Output is correct
10 Correct 500 ms 432996 KB Output is correct
11 Correct 1376 ms 432996 KB Output is correct
12 Correct 1848 ms 432996 KB Output is correct
13 Correct 677 ms 432996 KB Output is correct
14 Correct 684 ms 432996 KB Output is correct
15 Correct 540 ms 432996 KB Output is correct
16 Correct 510 ms 432996 KB Output is correct
17 Correct 531 ms 432996 KB Output is correct
18 Correct 580 ms 432996 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 916 ms 439856 KB Output is correct
2 Correct 858 ms 439980 KB Output is correct
3 Correct 1568 ms 445732 KB Output is correct
4 Correct 898 ms 445732 KB Output is correct
5 Execution timed out 4099 ms 445732 KB Time limit exceeded
6 Halted 0 ms 0 KB -