oj.uz

Submission #74029

# Submission time Handle Problem Language Result Execution time Memory
74029 2018-08-29T16:02:12 Z edisonhello Teams (IOI15_teams) C++14
77 / 100
 4000 ms 167532 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;
    }
    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 20 ms 15992 KB Output is correct
2 Correct 21 ms 16032 KB Output is correct
3 Correct 21 ms 16232 KB Output is correct
4 Correct 21 ms 16232 KB Output is correct
5 Correct 19 ms 16232 KB Output is correct
6 Correct 21 ms 16292 KB Output is correct
7 Correct 23 ms 16292 KB Output is correct
8 Correct 22 ms 16292 KB Output is correct
9 Correct 20 ms 16292 KB Output is correct
10 Correct 21 ms 16292 KB Output is correct
11 Correct 20 ms 16292 KB Output is correct
12 Correct 28 ms 16292 KB Output is correct
13 Correct 24 ms 16292 KB Output is correct
14 Correct 29 ms 16292 KB Output is correct
15 Correct 25 ms 16292 KB Output is correct
16 Correct 25 ms 16292 KB Output is correct
17 Correct 22 ms 16292 KB Output is correct
18 Correct 24 ms 16336 KB Output is correct
19 Correct 22 ms 16336 KB Output is correct
20 Correct 19 ms 16336 KB Output is correct
21 Correct 19 ms 16336 KB Output is correct
22 Correct 19 ms 16336 KB Output is correct
23 Correct 28 ms 16336 KB Output is correct
24 Correct 23 ms 16336 KB Output is correct
25 Correct 24 ms 16336 KB Output is correct
26 Correct 27 ms 16336 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 42500 KB Output is correct
2 Correct 124 ms 42544 KB Output is correct
3 Correct 104 ms 42544 KB Output is correct
4 Correct 120 ms 42852 KB Output is correct
5 Correct 71 ms 42852 KB Output is correct
6 Correct 71 ms 42852 KB Output is correct
7 Correct 64 ms 42852 KB Output is correct
8 Correct 73 ms 42852 KB Output is correct
9 Correct 98 ms 42852 KB Output is correct
10 Correct 92 ms 42852 KB Output is correct
11 Correct 87 ms 42920 KB Output is correct
12 Correct 66 ms 42920 KB Output is correct
13 Correct 74 ms 42920 KB Output is correct
14 Correct 76 ms 42920 KB Output is correct
15 Correct 106 ms 42920 KB Output is correct
16 Correct 107 ms 42920 KB Output is correct
17 Correct 57 ms 42944 KB Output is correct
18 Correct 62 ms 42944 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 42944 KB Output is correct
2 Correct 124 ms 42944 KB Output is correct
3 Correct 336 ms 45872 KB Output is correct
4 Correct 113 ms 45872 KB Output is correct
5 Correct 1862 ms 45872 KB Output is correct
6 Correct 1736 ms 45872 KB Output is correct
7 Correct 68 ms 45872 KB Output is correct
8 Correct 1300 ms 45872 KB Output is correct
9 Correct 85 ms 45872 KB Output is correct
10 Correct 207 ms 45872 KB Output is correct
11 Correct 982 ms 45872 KB Output is correct
12 Correct 1471 ms 45872 KB Output is correct
13 Correct 339 ms 45872 KB Output is correct
14 Correct 320 ms 45872 KB Output is correct
15 Correct 188 ms 45872 KB Output is correct
16 Correct 181 ms 45872 KB Output is correct
17 Correct 304 ms 45872 KB Output is correct
18 Correct 299 ms 45872 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 696 ms 161728 KB Output is correct
2 Correct 693 ms 161728 KB Output is correct
3 Correct 1066 ms 167532 KB Output is correct
4 Correct 665 ms 167532 KB Output is correct
5 Execution timed out 4021 ms 167532 KB Time limit exceeded
6 Halted 0 ms 0 KB -