Submission #1035327

#	Time	Username	Problem	Language	Result	Execution time	Memory
1035327		Warinchai	Jousting tournament (IOI12_tournament)	C++14	100 / 100	686 ms	9784 KiB

tournament

#include<bits/stdc++.h>
using namespace std;
int n;
struct segpos{
    int info[400005];
    void use(int i){upd(1,n,1,i);}
    void upd(int st,int en,int i,int pos){
        if(st==en){
            info[i]=0;
            //cerr<<st<<" "<<en<<" "<<i<<":"<<info[i]<<"\n";
            return;
        }
        int m=(st+en)/2;
        if(pos<=m)upd(st,m,i*2,pos);
        else upd(m+1,en,i*2+1,pos);
        info[i]=info[i*2]+info[i*2+1];
        //cerr<<st<<" "<<en<<" "<<i<<":"<<info[i*2]<<"+"<<info[i*2+1]<<"\n";
    }
    int get(int st,int en,int i,int pos){
        //cerr<<st<<' '<<en<<":"<<info[i]<<"\n";
        if(st==en){
            //cerr<<"get:"<<st<<"\n";
            return st;
        }
        int m=(st+en)/2;
        if(pos<=info[i*2])return get(st,m,i*2,pos);
        else return get(m+1,en,i*2+1,pos-info[i*2]);
    }
    int get(int i){return get(1,n,1,i);}
    void build(int st,int en,int i){
        if(st==en)return void(info[i]=1);
        int m=(st+en)/2;
        build(st,m,i*2);
        build(m+1,en,i*2+1);
        info[i]=info[i*2]+info[i*2+1];
    }
}pst,pen;
int val[100005];
int add[100005];
struct segmax{
    int info[400005];
    void build(int st,int en,int i){
        if(st==en)return void(info[i]=val[st]);
        int m=(st+en)/2;
        build(st,m,i*2);
        build(m+1,en,i*2+1);
        info[i]=max(info[i*2],info[i*2+1]);
    }
    int fmax(int st,int en,int i,int l,int r){
        if(st>r||en<l)return 0;
        if(st>=l&&en<=r)return info[i];
        int m=(st+en)/2;
        return max(fmax(st,m,i*2,l,r),fmax(m+1,en,i*2+1,l,r));
    }
}tr;
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
    n=N;
    for(int i=0;i<N-1;i++){
        val[i+1]=K[i];
    }
    tr.build(1,N-1,1);
    vector<pair<int,int>>op;
    pst.build(1,n,1);
    pen.build(1,n,1);
    for(int i=0;i<C;i++){
        /*cerr<<"info:"<<"\n";
        for(int i=1;i<=n;i++)cerr<<pst.get(i)<<" ";
        cerr<<"\n";
        for(int i=1;i<=n;i++)cerr<<pen.get(i)<<" ";
        cerr<<"\n";*/
        S[i]++,E[i]++;
        int st=pst.get(S[i]);
        int en=pen.get(E[i]);
        cerr<<"range:"<<st<<" "<<en<<"\n";
        op.push_back({st,en});
        vector<int>upst,upen;
        for(int j=S[i];j<=E[i];j++){
            if(j!=S[i])upst.push_back(pst.get(j));
            if(j!=E[i])upen.push_back(pen.get(j));
        }
        for(auto x:upst)/*cerr<<"upd:"<<x<<"\n",*/pst.use(x);
        //cerr<<"\n";
        for(auto x:upen)/*cerr<<"upd:"<<x<<"\n",*/pen.use(x);
    }
    vector<pair<int,int>>rop;
    for(auto x:op){
        int mx=tr.fmax(1,n-1,1,x.first,x.second-1);
        if(R>=mx)add[x.first]++,add[x.second+1]--;
    }
    pair<int,int>ans={INT_MIN,INT_MIN};
    int cans=0;
    for(int i=1;i<=N;i++){
        cans+=add[i];
        cerr<<cans<<" ";
        ans=max(ans,{cans,-i});
    }
    cerr<<"\n";
    return -ans.second-1;

}

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