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

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 = 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());
    }

    vector<int> montax(pura.size());
    auto lisaa = [&](int x) {
        ++montax[x];
    };
    auto poista = [&](int x) {
        --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;
        }
        int isoin = -1;
        int isoinX = -1;
        for(int i = 0; i < (int)montax.size(); ++i) {
            if(montax[i] > isoin) {
                isoin = montax[i];
                isoinX = i;
            }
        }
        if(2 * isoin > b - a) {
            kys.res = pura[isoinX];
        } 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: ACCEPTED

Test 5

Group: 2, 3, 4

Verdict: ACCEPTED

Test 6

Group: 2, 3, 4

Verdict: ACCEPTED

Test 7

Group: 3, 4

Verdict: TIME LIMIT EXCEEDED

Test 8

Group: 4

Verdict: ACCEPTED

Test 9

Group: 4

Verdict: ACCEPTED

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