Kyselyt

#include <bits/stdc++.h>

constexpr auto N = 2e5;
constexpr auto BS = 450;

struct Query {
    int a;
    int b;
    int idx;
    bool operator<(const Query& other) const {
        return a / BS != other.a / BS ? a < other.a : ((a / BS) & 1)^(b > other.b);
    }
};

std::vector<Query> Q = [](){
    std::vector<Query> Q(N);
    for (auto i = 0; i < N; ++i) {
        Q[i].idx = i;
    }
    return Q;
}();

std::unordered_map<int, int> XM;
std::vector<int> X(N);
std::vector<int> XMB(N);
std::vector<int> f(N);
std::vector<int> fc(N + 1);
std::vector<int> fr(N + 1);
int bc = 0;

inline int mode_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_v = 0;
    auto max_c = 0;
    for (const auto [v, c] : map) {
        if (c > max_c) {
            max_c = c;
            max_v = v;
        }
    }
    return max_c >= len / 2 + 1 ? XMB[max_v] : -1;
}

inline int mode(int a, int b) {
    const auto len = (b - a + 1);
    if (bc >= len / 2 + 1) {
        return f[fr[bc]] != bc ? mode_brute(a, b) : XMB[fr[bc]];
    }
    return -1;
}

inline void add(int v) {
    auto& fv = f[v];
    --fc[fv];
    ++fv;
    ++fc[fv];
    fr[fv] = v;
    bc += fv > bc;
}

inline void del(int v) {
    auto& fv = f[v];
    bc -= (fv == bc && fc[fv] == 1);
    --fc[fv];
    --fv;
    ++fc[fv];
}

inline void add_range(int a, int b) {
    for (; a <= b; ++a) {
        add(X[a]);
    }
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(0);
    int n, q;
    std::cin >> n >> q;

    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;
            XM[x] = mi++;
        } else {
            X[i] = it->second;
        }
    }

    for (int i = 0; i < q; ++i) {
        std::cin >> Q[i].a >> Q[i].b;
        --Q[i].a;
        --Q[i].b;
    }
    std::sort(Q.begin(), Q.begin() + q);

    std::vector<int> res(q, -1);
    auto ma = Q[0].a;
    auto mb = Q[0].b;
    add_range(ma, mb);
    const auto v = mode(ma, mb);
    if (v >= 0) {
        res[Q[0].idx] = v;
    }

    for (int i = 1; i < q; ++i) {
        const auto [a, b, idx] = Q[i];
        for (; ma < a && ma <= mb; ++ma) {
            del(X[ma]);
        }
        for (; mb > b && mb >= ma; --mb) {
            del(X[mb]);
        }
        if (mb < ma) {
            ma = a;
            mb = b;
            add_range(ma, mb);
        }
        while (ma > a) {
            --ma;
            add(X[ma]);
        }
        while (mb < b) {
            ++mb;
            add(X[mb]);
        }
        const auto v = mode(a, b);
        if (v >= 0) {
            res[idx] = v;
        }
    }
    for (const auto r : res) {
        std::cout << r << '\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: TIME LIMIT EXCEEDED

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

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