oj.uz

Submission #74036

# Submission time Handle Problem Language Result Execution time Memory
74036 2018-08-29T16:18:37 Z edisonhello Teams (IOI15_teams) C++14
77 / 100
 4000 ms 167656 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 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: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 21 ms 15992 KB Output is correct
2 Correct 21 ms 16156 KB Output is correct
3 Correct 22 ms 16156 KB Output is correct
4 Correct 30 ms 16156 KB Output is correct
5 Correct 19 ms 16156 KB Output is correct
6 Correct 20 ms 16216 KB Output is correct
7 Correct 22 ms 16264 KB Output is correct
8 Correct 22 ms 16264 KB Output is correct
9 Correct 18 ms 16264 KB Output is correct
10 Correct 23 ms 16264 KB Output is correct
11 Correct 23 ms 16264 KB Output is correct
12 Correct 25 ms 16288 KB Output is correct
13 Correct 21 ms 16288 KB Output is correct
14 Correct 21 ms 16288 KB Output is correct
15 Correct 19 ms 16288 KB Output is correct
16 Correct 21 ms 16288 KB Output is correct
17 Correct 25 ms 16288 KB Output is correct
18 Correct 19 ms 16288 KB Output is correct
19 Correct 21 ms 16288 KB Output is correct
20 Correct 20 ms 16288 KB Output is correct
21 Correct 30 ms 16288 KB Output is correct
22 Correct 29 ms 16288 KB Output is correct
23 Correct 21 ms 16288 KB Output is correct
24 Correct 21 ms 16288 KB Output is correct
25 Correct 24 ms 16288 KB Output is correct
26 Correct 20 ms 16288 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 42612 KB Output is correct
2 Correct 112 ms 42612 KB Output is correct
3 Correct 107 ms 42612 KB Output is correct
4 Correct 122 ms 42888 KB Output is correct
5 Correct 68 ms 42888 KB Output is correct
6 Correct 73 ms 42888 KB Output is correct
7 Correct 69 ms 42888 KB Output is correct
8 Correct 68 ms 42888 KB Output is correct
9 Correct 80 ms 42888 KB Output is correct
10 Correct 84 ms 42888 KB Output is correct
11 Correct 79 ms 42888 KB Output is correct
12 Correct 61 ms 42888 KB Output is correct
13 Correct 71 ms 42888 KB Output is correct
14 Correct 73 ms 42888 KB Output is correct
15 Correct 101 ms 42888 KB Output is correct
16 Correct 102 ms 42888 KB Output is correct
17 Correct 64 ms 42888 KB Output is correct
18 Correct 75 ms 42888 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 42920 KB Output is correct
2 Correct 135 ms 42936 KB Output is correct
3 Correct 288 ms 45820 KB Output is correct
4 Correct 126 ms 45820 KB Output is correct
5 Correct 1927 ms 45820 KB Output is correct
6 Correct 1621 ms 45820 KB Output is correct
7 Correct 73 ms 45820 KB Output is correct
8 Correct 1148 ms 45820 KB Output is correct
9 Correct 82 ms 45820 KB Output is correct
10 Correct 183 ms 45820 KB Output is correct
11 Correct 999 ms 45820 KB Output is correct
12 Correct 1697 ms 45820 KB Output is correct
13 Correct 331 ms 45820 KB Output is correct
14 Correct 287 ms 45820 KB Output is correct
15 Correct 172 ms 45820 KB Output is correct
16 Correct 170 ms 45820 KB Output is correct
17 Correct 266 ms 45820 KB Output is correct
18 Correct 265 ms 45820 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 547 ms 161708 KB Output is correct
2 Correct 631 ms 161708 KB Output is correct
3 Correct 1020 ms 167656 KB Output is correct
4 Correct 629 ms 167656 KB Output is correct
5 Execution timed out 4091 ms 167656 KB Time limit exceeded
6 Halted 0 ms 0 KB -