Kyselyt

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, q;
    cin >> n >> q;
    int x[n], y[n];
    for (int i = 0; i < n; ++i) cin >> x[i];
    map<int, int> m;
    for (int i = 0; i < n; ++i) {
        auto it = m.find(x[i]);
        if (it != m.end()) y[i] = it->second;
        else {
            y[i] = i;
            m[x[i]] = i;
        }
    }
    const int K = 24;
    int l[q], g[q][K];
    int cnt[q][K] {};
    vector<pair<int, int>> ev[n];
    for (int i = 0; i < q; ++i) {
        int a, b;
        cin >> a >> b;
        a--; b--;
        l[i] = b-a+1;
        if (a) ev[a-1].push_back({i, -1});
        ev[b].push_back({i, 1});
        for (int j = 0; j < K; ++j) {
            g[i][j] = y[a+rand()%(b-a+1)];
        }
    }
    int z[n] {};
    for (int i = 0; i < n; ++i) {
        z[y[i]]++;
        for (auto [qi, c] : ev[i]) {
            for (int j = 0; j < K; ++j) {
                cnt[qi][j] += c * z[g[qi][j]];
            }
        }
    }
    for (int i = 0; i < q; ++i) {
        int res = -1;
        for (int j = 0; j < K; ++j) {
            if (cnt[i][j] > l[i]/2) res = x[g[i][j]];
        }
        cout << res << "\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: 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