Kyselyt

#include <bits/stdc++.h>

constexpr auto N = 200000;

std::vector<int> X(N);
std::vector<int> XMB(N);
std::vector<std::vector<int>> F(N);

std::random_device rd;
std::mt19937 mt(rd());

int brute(int a, int b) {
    const auto len = (b - a + 1);
    std::map<int, int> map;
    for (; a <= b; ++a) {
        ++map[X[a]];
    }
    auto max_x = 0;
    auto max_c = 0;
    for (const auto [x, c] : map) {
        if (c > max_c) {
            max_c = c;
            max_x = x;
        }
    }
    return max_c >= len / 2 + 1 ? XMB[max_x] : -1;
}

inline int count(const std::vector<int>& pc, int a, int b) {
    return upper_bound(pc.begin(), pc.end(), b) - lower_bound(pc.begin(), pc.end(), a);
}

int solve(int a, int b) {
    const auto req = (b - a + 1) / 2 + 1;
    std::uniform_int_distribution<int> dist(a, b);
    for (auto i = 0; i < 32; ++i) {
        const auto x = X[dist(mt)];
        if (count(F[x], a, b) >= req) {
            return XMB[x];
        }
    }
    return -1;
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(0);
    int n, q;
    std::cin >> n >> q;
    std::unordered_map<int, int> XM;
    XM.reserve(n);
    for (int i = 0, mi = 0, x; i < n; ++i) {
        std::cin >> x;
        if (const auto it = XM.find(x); it == XM.end()) {
            X[i] = mi;
            XMB[mi] = x;
            F[mi].push_back(i);
            XM[x] = mi++;
        } else {
            X[i] = it->second;
            F[it->second].push_back(i);
        }
    }
    for (int i = 0; i < q; ++i) {
        int a, b;
        std::cin >> a >> b;
        if (b - a <= 32) {
            std::cout << brute(a - 1, b - 1) << '\n';
        } else {
            std::cout << solve(a - 1, b - 1) << '\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