IOI 2012 Tournament

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define FOR(i, a, b) for (int i = a; i < (b); i++)
#define F0R(i, a) for (int i = 0; i < (a); i++)
#define FORd(i, a, b) for (int i = (b) - 1, i >= a; i--)
#define F0Rd(i, a) for (int i = (a) - 1; i >= 0; i--)

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb emplace_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()

const int MOD = 1000000007;

void fast_io(){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
}

int ranks[100005];
vector<pii> games;
Tree<pii> players;
vector<pii> won_games;
int diff[100005];

template<class T, int SZ> struct RMQ {
    T stor[SZ][32-__builtin_clz(SZ)];

    T comb(T a, T b) {
        return max(a,b);
    }

    void build(vector<T>& x) {
        F0R(i,sz(x)) stor[i][0] = x[i];
        FOR(j,1,32-__builtin_clz(SZ)) F0R(i,SZ-(1<<(j-1)))
            stor[i][j] = comb(stor[i][j-1],stor[i+(1<<(j-1))][j-1]);
    }

    T query(int l, int r) {
        int x = 31-__builtin_clz(r-l+1);
        return comb(stor[l][x],stor[r-(1<<x)+1][x]);
    }
};

RMQ<int, 100005> DS;

int main(){
    int N, C, R; cin >> N >> C >> R;

    vector<int> v;

    for (int i = 0; i < N - 1; i++){
        cin >> ranks[i];
        v.push_back(ranks[i]);
        players.insert(pii(i, i));
    }

    DS.build(v);

    players.insert(pii(N - 1, N - 1));

    for (int i = 0; i < C; i++){

        int S, E; cin >> S >> E;
        pii k = *players.find_by_order(S);
        pii r = *players.find_by_order(E);

        games.push_back(pii(k.first, r.second));

        for (int i = S; i <= E; i++){
            players.erase(players.find_by_order(S));
        }

        players.insert(pii(k.first, r.second));
    }

    for (int i = 0; i < games.size(); i++){
        int a = games[i].first; int b = games[i].second;
        if (DS.query(a, b - 1) < R){
            won_games.push_back(pii(a, b));
        }
    }

    for (int i = 0; i < won_games.size(); i++){
        int a = won_games[i].first; int b = won_games[i].second;
        diff[a]++;
        diff[b + 1]--;
    }
    int res = 0;
    int bes = 0;
    int x = 0;
    for (int i = 0; i < N; i++){
        x += diff[i];
        if (x > res){
            res = x; bes = i;
        }
    }
    cout << bes << endl;



    return 0;
}