Submission #251188

#	Time	Username	Problem	Language	Result	Execution time	Memory
251188		eohomegrownapps	Jousting tournament (IOI12_tournament)	C++14	100 / 100	207 ms	17528 KiB

tournament

#include <bits/stdc++.h>
using namespace std;
#include <bits/extc++.h>
using namespace __gnu_pbds;

template <typename T>
using pbds_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template <typename T, typename V>
using pbds_map = tree<T, V, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

int n,c;

int sparsetable[17][100000];
int lg2[100001];

void gentable(int *K){
    lg2[1]=0;
    for (int i = 2; i<=n; i++){
        lg2[i]=lg2[i/2]+1;
    }
    for (int i = 0; i<n-1; i++){
        sparsetable[0][i]=K[i];
    }
    sparsetable[0][n-1]=-1;
    for (int i = 1; (1<<i)<=n; i++){
        for (int x = 0; x+(1<<i)<=n; x++){
            sparsetable[i][x]=max(sparsetable[i-1][x],sparsetable[i-1][x+(1<<(i-1))]);
        }
    }
}

int rmq(int a, int b){
    int l2 = lg2[b-a+1];
    return max(sparsetable[l2][a],sparsetable[l2][b-(1<<l2)+1]);
}

int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
    n=N;c=C;
    vector<pair<int,int>> pos(n);
    for (int i = 0; i<n; i++){
        pos[i]={i,i};
    }
    pbds_set<pair<int,int>> items(pos.begin(), pos.end());
    vector<pair<int,bool>> ranges; //false -- add, true -- remove
    gentable(K);
    for (int i = 0; i<c; i++){
        auto its = items.find_by_order(S[i]);
        auto ite = items.find_by_order(E[i]);
        int a = its->first;
        int b = ite->second;
        //cout<<"rmq "<<a<<" "<<b-1<<" "<<rmq(a,b-1)<<'\n';
        if (rmq(a,b-1)<R){
            //cout<<"range "<<a<<" "<<b<<'\n';
            ranges.push_back({a, false});
            ranges.push_back({b, true});
        }
        //ranges[i]={its->first,ite->second};
        for (int j = 0; j<E[i]-S[i]+1; j++){
            its = items.erase(its);
        }
        items.insert({a,b});
        /*for (auto i : items){
            cout<<i.first<<" "<<i.second<<", ";
        }cout<<'\n';*/
    }
    /*for (auto i : ranges){
        cout<<i.first<<" "<<i.second<<'\n';
    }*/
    /*for (int i = 0; i<100; i++){
        int a,b;
        cin>>a>>b;
        cout<<rmq(a,b)<<'\n';
    }*/
    sort(ranges.begin(), ranges.end());
    int maxnum = 0;
    int maxind = 0;
    int curval = 0;
    for (auto p : ranges){
        if (p.second){
            curval--;
        } else {
            curval++;
        }
        if (curval>maxnum){
            maxnum=curval;
            maxind=p.first;
        }
    }
    //cout<<maxnum<<'\n';
    return maxind;
}

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