Submission #38889

#	Time	Username	Problem	Language	Result	Execution time	Memory
38889		andy627	Jousting tournament (IOI12_tournament)	C++14	100 / 100	129 ms	8336 KiB

tournament

#include <stdio.h>
#include <algorithm>
#define ff first
#define ss second
#define pii pair<int,int>
#define ele 131072
using namespace std;

int n,c,r;
int k[111111],s[111111],e[111111];
int ed[111111],res[111111];
int max_idx[333333],era[333333],sum_idx[333333];

void putm_(int p,int num){
    p+=ele-1; max_idx[p]=num;
    for(p>>=1;p;p>>=1) max_idx[p]=max(max_idx[2*p],max_idx[2*p+1]);
}

void puts_(int p,int num){
    for(p+=ele-1;p;p>>=1) sum_idx[p]+=num;
}

int max_(int s,int e){
    int mx=0;
    s+=ele-1; e+=ele-1;
    while(s<e){
        if(s%2==1) mx=max(mx,max_idx[s++]);
        if(e%2==0) mx=max(mx,max_idx[e--]);
        s/=2; e/=2;
    }
    if(s==e) mx=max(mx,max_idx[s]);

    return mx;
}

int get_real_pos(int n,int l,int r,int p){
    int m=(l+r)/2;

    if(l==r) return m;
    if(p<=sum_idx[2*n]) return get_real_pos(2*n,l,m,p);
    return get_real_pos(2*n+1,m+1,r,p-sum_idx[2*n]);
}

void erase_(int n,int l,int r,int s,int e){
    if(r<s || l>e) return;
    if(s<=l && r<=e){
        era[n]=1;
        sum_idx[n]=0;
        return;
    }

    int m=(l+r)/2;
    erase_(2*n,l,m,s,e);
    erase_(2*n+1,m+1,r,s,e);

    if(era[n]) sum_idx[n]=0;
    else sum_idx[n]=sum_idx[2*n]+sum_idx[2*n+1];
}

int GetBestPosition(int N,int C,int R,int *K,int *S,int *E){
    n=N; c=C; r=R+1;
    for(int i=0;i<N-1;i++) k[i+1]=K[i]+1;
    for(int i=0;i<C;i++) s[i]=S[i]+1;
    for(int i=0;i<C;i++) e[i]=E[i]+1;

    for(int i=1;i<n;i++) putm_(i,k[i]);
    for(int i=1;i<=n;i++) puts_(i,1);
    for(int i=1;i<=n;i++) ed[i]=i;

    for(int i=0;i<c;i++){
        int ss=get_real_pos(1,1,ele,s[i]);
        int ee=get_real_pos(1,1,ele,e[i]); ee=ed[ee];
        s[i]=ss; e[i]=ee;
        erase_(1,1,ele,ss+1,ee);
        ed[ss]=ee;
    }

    for(int i=0;i<c;i++){
        if(r>max_(s[i],e[i]-1)){
            res[s[i]]++;
            res[e[i]+1]--;
        }
    }

    int mx=0,mxpos=1,tmp=0;
    for(int i=1;i<=n;i++){
        tmp+=res[i];
        if(mx<tmp){
            mx=tmp;
            mxpos=i;
        }
    }

    return mxpos-1;
}

• Subtask 1: 17 / 17
• Subtask 2: 32 / 32
• Subtask 3: 51 / 51