Submission #38841

#	Time	Username	Problem	Language	Result	Execution time	Memory
38841		andy627	Jousting tournament (IOI12_tournament)	C++14	0 / 100	36 ms	7624 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 mp[111111];
int idx[333333],qur[333333];
set<pii> st,eff;

void putm_(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]);
}

void putq_(int p,int num){
    for(p+=ele-1;p;p>>=1) qur[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,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;
}

void clear_(int p){
    qur[p]=0;
    if(p<ele){
        if(qur[2*p]) clear_(2*p);
        if(qur[2*p+1]) clear_(2*p+1);
    }
}

int sum_(int s,int e){
    int sum=0;
    s+=ele-1; e+=ele-1;
    while(s<e){
        if(s%2==1){
            if(qur[s]) sum+=qur[s],clear_(s);
            s++;
        }
        if(e%2==0){
            if(qur[e]) sum+=qur[e],clear_(e);
            e--;
        }
        s/=2; e/=2;
    }
    if(s==e && qur[s]) sum+=qur[s],clear_(s);

    return sum;
}

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

    for(int i=0;i<c;i++){
        while(int ran=sum_(s[i]+1,e[i]+1)){
            set<pii>::iterator it=st.lower_bound({s[i]+1,0});
            while(it!=st.end() && it->ff<=e[i]) putq_(it->ff,-it->ss),st.erase(it++);
            e[i]+=ran;
        }
        putq_(s[i]+1,e[i]-s[i]);
        st.insert({s[i]+1,e[i]-s[i]});

        /*
        for(int j=1;j<16;j++) printf("%d %d\n",j,qur[j]);
        printf("\n");
        */
    }
/*
    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