oj.uz

Submission #74034

# Submission time Handle Problem Language Result Execution time Memory
74034 2018-08-29T16:16:55 Z edisonhello Teams (IOI15_teams) C++14
34 / 100
 1356 ms 525312 KB 
// #include"teams.h"
#include<bits/stdc++.h>
#pragma GCC optimize("no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;

int root[500005],node[500005*45][3];
int ptr;

inline int gn(int ref=-1){
    ++ptr;
    if(~ref)memcpy(node[ptr],node[ref],3<<2);
    else memset(node[ptr],0,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{
    int l,r,sz,pri,val;
    int lz();
    int rz();
    void pull(){ sz=lz()+rz()+1; }
    node(int v=0):l(-1),r(-1),sz(1),pri(rand()),val(v){}
} pool[500005];
int root=-1;
int node::lz(){ return ~l?pool[l].sz:0; }
int node::rz(){ return ~r?pool[r].sz:0; }

int _ptr;
int gnode(int v){
    pool[_ptr].l=-1;
    pool[_ptr].r=-1;
    pool[_ptr].sz=1;
    pool[_ptr].val=v;
    return _ptr++;
}

int merge(int a,int b){
    if(!~a)return b; if(!~b)return a;
    if(pool[a].pri>pool[b].pri){
        pool[a].r=merge(pool[a].r,b);
        pool[a].pull();
        return a;
    }
    else{
        pool[b].l=merge(a,pool[b].l);
        pool[b].pull();
        return b;
    }
}

void split_val(int now,int val,int &a,int &b){
    // if(now)cout<<"spliting "<<now<<endl;
    if(!~now){ a=b=-1; return; }
    if(pool[now].val<=val){
        a=now;
        split_val(pool[now].r,val,pool[a].r,b);
        pool[a].pull();
    }
    else{
        b=now;
        split_val(pool[now].l,val,a,pool[b].l);
        pool[b].pull();
    }
}

void split_sz(int now,int sz,int &a,int &b){
    if(!~now){ a=b=-1; return; }
    if(pool[now].lz()>=sz){
        b=now;
        split_sz(pool[now].l,sz,a,pool[b].l);
        pool[b].pull();
    }
    else{
        a=now;
        split_sz(pool[now].r,sz-1-pool[now].lz(),pool[a].r,b);
        pool[a].pull();
    }
}

int solve(int m,int k[]){
    _ptr=0;
    int ptr=1;
    for(int i=0;i<m;++i){
        // cout<<"solving i: "<<i<<endl;
        while(ptr<=n && p[ptr].first<=k[i]){
            int a,b;
            split_val(root,p[ptr].second,a,b);
            root=merge(merge(a,gnode(p[ptr].second)),b);
            ++ptr;
            // cout<<"now ptr: "<<ptr<<endl;
        }
        // cout<<"out while"<<endl;
        int a,b;
        split_val(root,k[i]-1,a,b);
        // cout<<"after split_val"<<endl;
        if(!~b || pool[b].sz<k[i]){
            root=0;
            return 0;
        }
        int 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 'void init(int, int*, int*)':
teams.cpp:46:9: warning: declaration of 'ptr' shadows a global declaration [-Wshadow]
     int ptr=1;
         ^~~
teams.cpp:8:5: note: shadowed declaration is here
 int ptr;
     ^~~
teams.cpp: In function 'int naive::merge(int, int)':
teams.cpp:75:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
     if(!~a)return b; if(!~b)return a;
     ^~
teams.cpp:75:22: 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 15 ms 10104 KB Output is correct
2 Correct 15 ms 10104 KB Output is correct
3 Correct 14 ms 10168 KB Output is correct
4 Correct 18 ms 10272 KB Output is correct
5 Correct 18 ms 10348 KB Output is correct
6 Correct 18 ms 10348 KB Output is correct
7 Correct 14 ms 10348 KB Output is correct
8 Correct 17 ms 10348 KB Output is correct
9 Correct 15 ms 10380 KB Output is correct
10 Correct 19 ms 10380 KB Output is correct
11 Correct 21 ms 10380 KB Output is correct
12 Correct 25 ms 10380 KB Output is correct
13 Correct 19 ms 10380 KB Output is correct
14 Correct 16 ms 10448 KB Output is correct
15 Correct 20 ms 10448 KB Output is correct
16 Correct 19 ms 10448 KB Output is correct
17 Correct 17 ms 10448 KB Output is correct
18 Correct 17 ms 10448 KB Output is correct
19 Correct 17 ms 10448 KB Output is correct
20 Correct 16 ms 10448 KB Output is correct
21 Correct 20 ms 10448 KB Output is correct
22 Correct 18 ms 10448 KB Output is correct
23 Correct 19 ms 10448 KB Output is correct
24 Correct 17 ms 10448 KB Output is correct
25 Correct 21 ms 10448 KB Output is correct
26 Correct 15 ms 10448 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 36664 KB Output is correct
2 Correct 117 ms 36664 KB Output is correct
3 Correct 112 ms 36664 KB Output is correct
4 Correct 133 ms 37116 KB Output is correct
5 Correct 68 ms 37116 KB Output is correct
6 Correct 67 ms 37116 KB Output is correct
7 Correct 62 ms 37116 KB Output is correct
8 Correct 64 ms 37116 KB Output is correct
9 Correct 88 ms 37116 KB Output is correct
10 Correct 81 ms 37116 KB Output is correct
11 Correct 74 ms 37116 KB Output is correct
12 Correct 49 ms 37116 KB Output is correct
13 Correct 57 ms 37116 KB Output is correct
14 Correct 71 ms 37116 KB Output is correct
15 Correct 95 ms 37116 KB Output is correct
16 Correct 97 ms 37116 KB Output is correct
17 Correct 62 ms 37116 KB Output is correct
18 Correct 61 ms 37116 KB Output is correct

Subtask #3
0 / 43.0

# Verdict Execution time Memory Grader output
1 Runtime error 909 ms 525312 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 1356 ms 525312 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -