oj.uz

Submission #254339

# Submission time Handle Problem Language Result Execution time Memory
254339 2020-07-29T21:16:58 Z knon0501 Jousting tournament (IOI12_tournament) C++14
0 / 100
 1000 ms 10104 KB 
#include <bits/stdc++.h>
using namespace std;
const int MX=1e5+5;
vector<int> b[MX*2];
int seg[MX*4];
int seg2[MX*4];
int p[MX];
int a[MX];
int l[MX*2];
int r[MX*2];
int dp[MX*2];
int n,R,c;
int ans;
int nn;

int g(int lef,int rig,int x,int lev){
    if(lef==rig)return lef;
    int mid=lef+rig>>1;
    if(seg2[lev<<1]>x)return g(lef,mid,x,lev<<1);
    return g(mid+1,rig,x-seg2[lev<<1],(lev<<1)^1);
}
int f(int lef,int rig,int x,int y,int lev){
    if(x>rig|| lef>y)return -1;
    if(x<=lef && rig<=y)return seg[lev];
    int mid=(lef+rig)>>1;
    return max(f(lef,mid,x,y,lev<<1),f(mid+1,rig,x,y,(lev<<1)^1));
}
int h(int v){
    int ret=v;
    for(auto u: b[v]){
        int k=h(u);
        if(dp[u]+(f(0,nn-1,l[v],r[v]-1,1)<R)>dp[v]){
            dp[v]=dp[u]+(f(0,nn-1,l[v],r[v]-1,1)<R);
            ret=k;
        }
    }
    return ret;
}
int GetBestPosition(int N, int C, int rr, int *K, int *S, int *E) {
    n=N;
    c=C;
    R=rr;
    int i,j;
    for(nn=1 ; nn<n ; nn*=2);
    for(i=0 ; i<n-1 ; i++){
        a[i]=K[i];
        seg[nn+i]=a[i];
    }
    
     for(i=0 ; i<n ; i++){
        p[i]=i;
        seg2[nn+i]=1;
        l[i]=r[i]=i;
    }

    for(i=nn-1 ; i>=1 ; i--){
        seg[i]=max(seg[i*2],seg[i*2+1]);
        seg2[i]=seg2[i*2]+seg2[i*2+1];
    }
    for(i=0 ; i<c ; i++){
        int s=S[i];
        int e=E[i];
        l[n+i]=-1;
        vector<int> v(e-s+1);
        for(j=s ; j<=e ; j++){
            int k=g(0,nn-1,j,1);
            v.push_back(k);
            b[n+i].push_back(p[k]);
            if(l[n+i]==-1)l[n+i]=l[p[k]];
            r[n+i]=r[p[k]];
        }
        for(auto x: v){
            for(j=nn+x ; j>=1 ; j>>=1)seg2[j]--;
        }
        int k=v.back();
        p[k]=n+i;
        for(j=nn+k ; j>=1 ; j>>=1)seg2[j]++;
    }

    return h(n+c-1);
}

Compilation message

tournament.cpp: In function 'int g(int, int, int, int)':
tournament.cpp:18:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid=lef+rig>>1;
             ~~~^~~~

Subtask #1
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 4992 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 32.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1088 ms 5120 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 51.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1099 ms 10104 KB Time limit exceeded
2 Halted 0 ms 0 KB -