Kyselyt

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

using namespace std;

struct Kysely {
    int i;
    int a;
    int b;
    int res;
};

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

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;
}

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

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

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

    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;
    }

    sort(kyselyt.begin(), kyselyt.end(), [&](const Kysely& x, const Kysely& y) {
        // constexpr int siirto = 9;
        // return make_pair(x.a >> siirto, x.b) < make_pair(y.a >> siirto, y.b);
        constexpr int jako = 450;
        return make_pair(x.a / jako, x.b) < make_pair(y.a / jako, y.b);
    });

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

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

    vector<int> montax(pura.size());
    vector<Solmu> listat(n + 1);
    for(int i = 0; i <= n; ++i) {
        listat[i].edellinen = &listat[i];
        listat[i].seuraava = &listat[i];
    }
    vector<Solmu> solmut(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 = pura[i];
    }

    int isoin = 0;

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

    int a = 0;
    int b = 0;
    for(Kysely& kys : kyselyt) {
        while(kys.b > b) {
            lisaa(taulPakkaa[b]);
            ++b;
        }
        while(kys.a < a) {
            --a;
            lisaa(taulPakkaa[a]);
        }
        while(kys.b < b) {
            --b;
            poista(taulPakkaa[b]);
        }
        while(kys.a > a) {
            poista(taulPakkaa[a]);
            ++a;
        }
        if(2 * isoin > b - a) {
            kys.res = listat[isoin].seuraava->x;
        } else {
            kys.res = -1;
        }
    }

    vector<int> res(q);
    for(Kysely& kys : kyselyt) {
        res[kys.i] = kys.res;
    }
    
    for(int r : res) {
        cout << r << "\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: TIME LIMIT EXCEEDED

Test 9

Group: 4

Verdict: ACCEPTED

Test 10

Group: 4

Verdict: TIME LIMIT EXCEEDED

Test 11

Group: 3, 4

Verdict: ACCEPTED

Test 12

Group: 4

Verdict: TIME LIMIT EXCEEDED

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