Kyselyt

#include <algorithm>
#include <iostream>
#include <optional>
#include <set>
#include <tuple>
#include <map>
#include <vector>

using namespace std;

struct Kysely {
    int i;
    int a;
    int b;
    int pot1 = -1;
    int pot2 = -1;
    int montax1 = -1;
    int montax2 = -1;
    int res = -1;
};

struct Solmu {
    Solmu* edellinen;
    Solmu* seuraava;
    int x;
};

constexpr int N = 1 << 18;

vector<Kysely*> spuu[2 * N];

vector<int> taul;
vector<int> montax;
vector<Solmu> listat;
vector<Solmu> solmut;
int isoin = 0;

void poistaSolmu(Solmu* solmu) {
    solmu->edellinen->seuraava = solmu->seuraava;
    solmu->seuraava->edellinen = solmu->edellinen;
}

void lisaaSolmu(Solmu* solmu, Solmu* edeltaja) {
    solmu->edellinen = edeltaja;
    solmu->seuraava = edeltaja->seuraava;
    solmu->edellinen->seuraava = solmu;
    solmu->seuraava->edellinen = solmu;
}

void lisaa(int x) {
    poistaSolmu(&solmut[x]);
    ++montax[x];
    lisaaSolmu(&solmut[x], &listat[montax[x]]);
    if(montax[x] > isoin) {
        isoin = montax[x];
    }
};
void poista(int x) {
    poistaSolmu(&solmut[x]);
    if(listat[isoin].seuraava == &listat[isoin]) {
        --isoin;
    }
    --montax[x];
    lisaaSolmu(&solmut[x], &listat[montax[x]]);
};

void ratko(int v, int a, int b) {
    if(v >= 2 * N) {
        return;
    }
    int m = (a + b) / 2;
    ratko(2 * v, a, m);
    ratko(2 * v + 1, m, b);

    if(spuu[v].empty()) {
        return;
    }

    vector<pair<int, Kysely*>> vasenJarj;
    vector<pair<int, Kysely*>> oikeaJarj;
    for(Kysely* kysely : spuu[v]) {
        vasenJarj.push_back({kysely->a, kysely});
        oikeaJarj.push_back({kysely->b, kysely});
    }
    sort(vasenJarj.rbegin(), vasenJarj.rend());
    sort(oikeaJarj.begin(), oikeaJarj.end());

    int k = m;
    for(auto& p : vasenJarj) {
        Kysely& kysely = *p.second;
        while(k > p.first) {
            --k;
            lisaa(taul[k]);
        }
        kysely.pot1 = listat[isoin].seuraava->x;
        kysely.montax1 = isoin;
    }
    while(k < m) {
        poista(taul[k]);
        ++k;
    }
    for(auto& p : oikeaJarj) {
        Kysely& kysely = *p.second;
        while(k < p.first) {
            lisaa(taul[k]);
            ++k;
        }
        kysely.pot2 = listat[isoin].seuraava->x;
        kysely.montax2 = isoin;
    }
    while(k > m) {
        --k;
        poista(taul[k]);
    }

    for(auto& p : vasenJarj) {
        Kysely& kysely = *p.second;
        while(k > p.first) {
            --k;
            lisaa(taul[k]);
        }
        if(kysely.pot2 == -1) throw 5;
        if(2 * (kysely.montax2 + montax[kysely.pot2]) > kysely.b - kysely.a) {
            kysely.res = kysely.pot2;
        }
    }
    while(k < m) {
        poista(taul[k]);
        ++k;
    }
    for(auto& p : oikeaJarj) {
        Kysely& kysely = *p.second;
        while(k < p.first) {
            lisaa(taul[k]);
            ++k;
        }
        if(kysely.pot1 == -1) throw 5;
        if(2 * (kysely.montax1 + montax[kysely.pot1]) > kysely.b - kysely.a) {
            kysely.res = kysely.pot1;
        }
    }
    while(k > m) {
        --k;
        poista(taul[k]);
    }
}

int main() {
    cin.sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q;
    cin >> n >> q;

    vector<int> taulRaaka(n);
    for(int& x : taulRaaka) {
        cin >> x;
    }

    vector<int> pura = taulRaaka;
    sort(pura.begin(), pura.end());
    pura.erase(unique(pura.begin(), pura.end()), pura.end());

    taul.resize(n);
    for(int i = 0; i < n; ++i) {
        taul[i] = (int)(lower_bound(pura.begin(), pura.end(), taulRaaka[i]) - pura.begin());
    }

    montax.resize(pura.size());
    listat.resize(n + 1);
    for(int i = 0; i <= n; ++i) {
        listat[i].edellinen = &listat[i];
        listat[i].seuraava = &listat[i];
    }
    solmut.resize(pura.size());
    for(int i = 0; i < (int)pura.size(); ++i) {
        Solmu& solmu = solmut[i];
        solmu.seuraava = listat[0].seuraava;
        solmu.edellinen = &listat[0];
        solmu.seuraava->edellinen = &solmu;
        solmu.edellinen->seuraava = &solmu;
        solmu.x = i;
    }

    vector<Kysely> kyselyt(q);
    for(int i = 0; i < q; ++i) {
        Kysely& kys = kyselyt[i];
        kys.i = i;
        cin >> kys.a >> kys.b;
        --kys.a;
    }

    // vector<Kysely*> kyselytP;
    // for(Kysely& kysely : kyselyt) {
    //     kyselytP.push_back(&kysely);
    // }
    // ratko(kyselytP, 0, n);

    for(Kysely& kysely : kyselyt) {
        int a = 0;
        int b = N;
        int v = 1;
        while(true) {
            if(a >= b) throw 5;
            int m = (a + b) / 2;
            if(kysely.b < m) {
                v = 2 * v;
                b = m;
            } else if(kysely.a > m) {
                v = 2 * v + 1;
                a = m;
            } else {
                if(!(kysely.a <= m && kysely.b >= m)) {
                    throw 5;
                }
                spuu[v].push_back(&kysely);
                break;
            }
        }
    }

    ratko(1, 0, N);

    for(Kysely& kysely : kyselyt) {
        if(kysely.res != -1) {
            cout << pura[kysely.res] << "\n";
        } else {
            cout << -1 << "\n";
        }
    }

    return 0;
}

Test 1

Group: 1, 2, 3, 4

Verdict: ACCEPTED

Test 2

Group: 1, 2, 3, 4

Verdict: ACCEPTED

Test 3

Group: 1, 3, 4

Verdict: ACCEPTED

Test 4

Group: 2, 3, 4

Verdict: ACCEPTED

Test 5

Group: 2, 3, 4

Verdict: ACCEPTED

Test 6

Group: 2, 3, 4

Verdict: ACCEPTED

Test 7

Group: 3, 4

Verdict: ACCEPTED

Test 8

Group: 4

Verdict: ACCEPTED

Test 9

Group: 4

Verdict: ACCEPTED

Test 10

Group: 4

Verdict: ACCEPTED

Test 11

Group: 3, 4

Verdict: ACCEPTED

Test 12

Group: 4

Verdict: ACCEPTED

Test 13

Group: 3, 4

Verdict: ACCEPTED

Test 14

Group: 4

Verdict: ACCEPTED

Test 15

Group: 4

Verdict: ACCEPTED

Test 16

Group: 4

Verdict: ACCEPTED