Submission #38877

#	Time	Username	Problem	Language	Result	Execution time	Memory
38877		andy627	Jousting tournament (IOI12_tournament)	C++14	0 / 100	1000 ms	5032 KiB

tournament

#include <stdio.h>
#include <set>
#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 nxt[111111],idx[333333],res[111111];

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

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

    return mx;
}

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

    for(int i=0;i<n;i++) nxt[i]=i+1;
    for(int i=0;i<n-1;i++) put_(i,k[i]);

    for(int i=0;i<c;i++){
        int bef=s[i],del=e[i]-s[i];
        s[i]=0;
        for(int j=0;j<bef;j++) s[i]=nxt[s[i]];
        e[i]=s[i];
        for(int j=0;j<=del;j++) e[i]=nxt[e[i]];
        nxt[s[i]]=e[i]; e[i]--;
    }
/*
    for(int i=0;i<c;i++) printf("%d %d\n",s[i],e[i]);
    printf("\n");
*/
    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,sum=0;
    for(int i=0;i<n;i++) sum+=res[i],mx=max(mx,sum);

    return mx;
}

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