oj.uz

Submission #74066

# Submission time Handle Problem Language Result Execution time Memory
74066 2018-08-30T01:43:39 Z edisonhello Teams (IOI15_teams) C++14
77 / 100
 4000 ms 235760 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[]){
    srand(clock());
    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;
    }
    root=0;
    return 1;
}

}

#define BOUND 450
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
// tutorial

Compilation message

teams.cpp: In function 'void init(int, int*, int*)':
teams.cpp:42:16: warning: conversion to 'unsigned int' from 'clock_t {aka long int}' may alter its value [-Wconversion]
     srand(clock());
           ~~~~~^~
teams.cpp:47: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 'naive::node* naive::merge(naive::node*, naive::node*)':
teams.cpp:74:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
     if(!a)return b; if(!b)return a;
     ^~
teams.cpp:74: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 20 ms 16120 KB Output is correct
2 Correct 19 ms 16184 KB Output is correct
3 Correct 20 ms 16240 KB Output is correct
4 Correct 19 ms 16388 KB Output is correct
5 Correct 20 ms 16388 KB Output is correct
6 Correct 23 ms 16640 KB Output is correct
7 Correct 20 ms 16640 KB Output is correct
8 Correct 19 ms 16640 KB Output is correct
9 Correct 19 ms 16640 KB Output is correct
10 Correct 19 ms 16640 KB Output is correct
11 Correct 19 ms 16640 KB Output is correct
12 Correct 22 ms 16640 KB Output is correct
13 Correct 20 ms 16640 KB Output is correct
14 Correct 21 ms 16640 KB Output is correct
15 Correct 19 ms 16640 KB Output is correct
16 Correct 19 ms 16640 KB Output is correct
17 Correct 19 ms 16640 KB Output is correct
18 Correct 19 ms 16640 KB Output is correct
19 Correct 19 ms 16640 KB Output is correct
20 Correct 19 ms 16640 KB Output is correct
21 Correct 19 ms 16640 KB Output is correct
22 Correct 20 ms 16640 KB Output is correct
23 Correct 20 ms 16640 KB Output is correct
24 Correct 19 ms 16640 KB Output is correct
25 Correct 25 ms 16708 KB Output is correct
26 Correct 19 ms 16708 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 44072 KB Output is correct
2 Correct 78 ms 45196 KB Output is correct
3 Correct 82 ms 46348 KB Output is correct
4 Correct 91 ms 48140 KB Output is correct
5 Correct 73 ms 48464 KB Output is correct
6 Correct 63 ms 49240 KB Output is correct
7 Correct 57 ms 50032 KB Output is correct
8 Correct 60 ms 50808 KB Output is correct
9 Correct 78 ms 51088 KB Output is correct
10 Correct 70 ms 51440 KB Output is correct
11 Correct 71 ms 53176 KB Output is correct
12 Correct 54 ms 53176 KB Output is correct
13 Correct 61 ms 54800 KB Output is correct
14 Correct 62 ms 54984 KB Output is correct
15 Correct 80 ms 56596 KB Output is correct
16 Correct 75 ms 57724 KB Output is correct
17 Correct 59 ms 59076 KB Output is correct
18 Correct 60 ms 60188 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 61820 KB Output is correct
2 Correct 86 ms 63316 KB Output is correct
3 Correct 199 ms 68212 KB Output is correct
4 Correct 85 ms 68212 KB Output is correct
5 Correct 2883 ms 68212 KB Output is correct
6 Correct 2037 ms 69140 KB Output is correct
7 Correct 64 ms 70012 KB Output is correct
8 Correct 1560 ms 71340 KB Output is correct
9 Correct 75 ms 71340 KB Output is correct
10 Correct 172 ms 71880 KB Output is correct
11 Correct 902 ms 74180 KB Output is correct
12 Correct 1327 ms 74248 KB Output is correct
13 Correct 276 ms 76612 KB Output is correct
14 Correct 194 ms 79452 KB Output is correct
15 Correct 159 ms 79588 KB Output is correct
16 Correct 168 ms 81092 KB Output is correct
17 Correct 258 ms 82884 KB Output is correct
18 Correct 253 ms 84368 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 504 ms 209232 KB Output is correct
2 Correct 541 ms 216796 KB Output is correct
3 Correct 915 ms 230900 KB Output is correct
4 Correct 517 ms 231920 KB Output is correct
5 Execution timed out 4022 ms 235760 KB Time limit exceeded
6 Halted 0 ms 0 KB -