Submission #38873

#	Time	Username	Problem	Language	Result	Execution time	Memory
38873		andy627	Jousting tournament (IOI12_tournament)	C++14	0 / 100	33 ms	5792 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];
set<pii> eff;

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

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,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+1,k[i]);

    for(int i=0;i<c;i++){
        int del=e[i]-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(r,max_(s[i]+1,e[i]))){
            eff.insert({s[i],1});
            eff.insert({e[i]+1,-1});
        }
    }
/*
    set<pii>::iterator itt=eff.begin();
    while(itt!=eff.end()) printf("%d %d\n",itt->ff,itt->ss),itt++;
    printf("\n");
*/
    int mx=0,res=0;
    set<pii>::iterator it=eff.begin();
    for(int i=0;i<n;i++){
        while(it!=eff.end() && it->ff==i) res+=it->ss,it++;
        mx=max(mx,res);
    }

    return mx;
}

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