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

constexpr int MaxN = 1 << 18;
pair<int, int> spuu[2 * MaxN];

int N;

void muuta(int v, int d) {
    v += N;
    spuu[v].first += d;
    v >>= 1;
    while(v > 0) {
        spuu[v] = max(spuu[2 * v], spuu[2 * v + 1]);
        v >>= 1;
    }
}

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

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

    N = 1;
    while(N < n) {
        N *= 2;
    }
    for(int i = 0; i < N; ++i) {
        spuu[N + i] = {0, i};
    }

    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 = 7;
        return make_pair(x.a >> siirto, x.b) < make_pair(y.a >> siirto, 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());
    }

    int a = 0;
    int b = 0;
    for(Kysely& kys : kyselyt) {
        while(kys.b > b) {
            muuta(taulPakkaa[b], 1);
            ++b;
        }
        while(kys.a < a) {
            --a;
            muuta(taulPakkaa[a], 1);
        }
        while(kys.b < b) {
            --b;
            muuta(taulPakkaa[b], -1);
        }
        while(kys.a > a) {
            muuta(taulPakkaa[a], -1);
            ++a;
        }
        if(2 * spuu[1].first > b - a) {
            kys.res = pura[spuu[1].second];
        } else {
            kys.res = -1;
        }
    }
    
    sort(kyselyt.begin(), kyselyt.end(), [&](const Kysely& x, const Kysely& y) {
        return x.i < y.i;
    });

    for(Kysely& kys : kyselyt) {
        cout << kys.res << "\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: TIME LIMIT EXCEEDED

Test 5

Group: 2, 3, 4

Verdict: TIME LIMIT EXCEEDED

Test 6

Group: 2, 3, 4

Verdict: TIME LIMIT EXCEEDED

Test 7

Group: 3, 4

Verdict: TIME LIMIT EXCEEDED

Test 8

Group: 4

Verdict: TIME LIMIT EXCEEDED

Test 9

Group: 4

Verdict: TIME LIMIT EXCEEDED

Test 10

Group: 4

Verdict: TIME LIMIT EXCEEDED

Test 11

Group: 3, 4

Verdict: TIME LIMIT EXCEEDED

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