Submission #38879

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

void putm_(int p,int num){
    p+=ele; idx[p]=num;
    for(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; 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;
}

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

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

    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,sum=0;
    for(int i=0;i<n;i++){
        sum+=res[i];
        if(mx<sum){
            mx=sum;
            mxpos=i;
        }
    }

    return mxpos;
}

Compilation message (stderr)

tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:99:12: warning: 'mxpos' may be used uninitialized in this function [-Wmaybe-uninitialized]
     return mxpos;
            ^

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