oj.uz

Submission #74012

# Submission time Handle Problem Language Result Execution time Memory
74012 2018-08-29T15:38:59 Z edisonhello Teams (IOI15_teams) C++14
77 / 100
 4000 ms 167476 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;

int root[500005],node[500005*24][3];

inline int gn(int ref=-1){
    static int ptr=-1; ++ptr;
    if(~ref)memcpy(node[ptr],node[ref],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{
    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 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

teams.cpp: In function 'naive::node* naive::merge(naive::node*, naive::node*)':
teams.cpp:71:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
     if(!a)return b; if(!b)return a;
     ^~
teams.cpp:71: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 25 ms 15992 KB Output is correct
2 Correct 23 ms 16160 KB Output is correct
3 Correct 24 ms 16160 KB Output is correct
4 Correct 22 ms 16192 KB Output is correct
5 Correct 22 ms 16240 KB Output is correct
6 Correct 21 ms 16240 KB Output is correct
7 Correct 21 ms 16240 KB Output is correct
8 Correct 21 ms 16240 KB Output is correct
9 Correct 26 ms 16240 KB Output is correct
10 Correct 24 ms 16240 KB Output is correct
11 Correct 20 ms 16240 KB Output is correct
12 Correct 24 ms 16240 KB Output is correct
13 Correct 21 ms 16240 KB Output is correct
14 Correct 22 ms 16240 KB Output is correct
15 Correct 27 ms 16280 KB Output is correct
16 Correct 31 ms 16280 KB Output is correct
17 Correct 24 ms 16280 KB Output is correct
18 Correct 26 ms 16280 KB Output is correct
19 Correct 20 ms 16280 KB Output is correct
20 Correct 19 ms 16280 KB Output is correct
21 Correct 24 ms 16280 KB Output is correct
22 Correct 23 ms 16280 KB Output is correct
23 Correct 21 ms 16280 KB Output is correct
24 Correct 22 ms 16280 KB Output is correct
25 Correct 26 ms 16376 KB Output is correct
26 Correct 23 ms 16376 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 42476 KB Output is correct
2 Correct 117 ms 42476 KB Output is correct
3 Correct 94 ms 42500 KB Output is correct
4 Correct 113 ms 42940 KB Output is correct
5 Correct 72 ms 42940 KB Output is correct
6 Correct 67 ms 42940 KB Output is correct
7 Correct 62 ms 42940 KB Output is correct
8 Correct 63 ms 42940 KB Output is correct
9 Correct 81 ms 42940 KB Output is correct
10 Correct 98 ms 42940 KB Output is correct
11 Correct 82 ms 42988 KB Output is correct
12 Correct 60 ms 42988 KB Output is correct
13 Correct 66 ms 42988 KB Output is correct
14 Correct 66 ms 42988 KB Output is correct
15 Correct 108 ms 42988 KB Output is correct
16 Correct 102 ms 42988 KB Output is correct
17 Correct 62 ms 42988 KB Output is correct
18 Correct 65 ms 42988 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 42988 KB Output is correct
2 Correct 117 ms 42988 KB Output is correct
3 Correct 309 ms 45936 KB Output is correct
4 Correct 118 ms 45936 KB Output is correct
5 Correct 1721 ms 45936 KB Output is correct
6 Correct 1430 ms 45936 KB Output is correct
7 Correct 67 ms 45936 KB Output is correct
8 Correct 1255 ms 45936 KB Output is correct
9 Correct 74 ms 45936 KB Output is correct
10 Correct 196 ms 45936 KB Output is correct
11 Correct 1111 ms 45936 KB Output is correct
12 Correct 1690 ms 45936 KB Output is correct
13 Correct 420 ms 45936 KB Output is correct
14 Correct 315 ms 45936 KB Output is correct
15 Correct 172 ms 45936 KB Output is correct
16 Correct 195 ms 45936 KB Output is correct
17 Correct 314 ms 45936 KB Output is correct
18 Correct 259 ms 45936 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 677 ms 161692 KB Output is correct
2 Correct 670 ms 161820 KB Output is correct
3 Correct 1239 ms 167476 KB Output is correct
4 Correct 656 ms 167476 KB Output is correct
5 Execution timed out 4115 ms 167476 KB Time limit exceeded
6 Halted 0 ms 0 KB -