Kyselyt

#include <bits/stdc++.h>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    int n, q;
    cin >> n >> q;
    vector<int> luvut(n+1, -1);
    unordered_map<int, map<int, int>> summataulu;
    set<int> uniikit;
    for (int i = 1; i <= n; i++) {
        cin >> luvut[i];
        summataulu[luvut[i]][i] = 1;
        uniikit.insert(luvut[i]);
    }
    for (auto& rivi : summataulu) {
        rivi.second[0] = 0;
        rivi.second[1000000001] = 0;
        auto i = rivi.second.begin();
        int edellinen = 0;
        while (i != rivi.second.end()) {
            i->second += edellinen;
            edellinen = i->second;
            i++;
        }
    }

    for (int i = 0; i < q; i++) {
        int a, b;
        cin >> a >> b;
        int vastaus = -1;
        for (int luku : uniikit) {
            auto it_a = prev(summataulu[luku].lower_bound(a));
            auto it_b = prev(summataulu[luku].upper_bound(b));
            int val_a = it_a->second;
            int val_b = it_b->second;
            int maara = val_b - val_a;
            if (maara > (b - a + 1) / 2) {
                vastaus = luku;
            }
        }
        cout << vastaus << "\n";
    }
}

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: TIME LIMIT EXCEEDED

Test 14

Group: 4

Verdict: TIME LIMIT EXCEEDED

Test 15

Group: 4

Verdict: TIME LIMIT EXCEEDED

Test 16

Group: 4

Verdict: ACCEPTED