Kyselyt

#include <bits/stdc++.h>

constexpr auto N = 200000;
constexpr auto BS = 512;

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 : b > other.b);
    }
};

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) {
    const auto pfv = f[v]++;
    --fc[pfv];
    ++fc[pfv + 1];
    fr[pfv + 1] = v;
    bc += (pfv == bc);
}

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

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

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

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

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

    std::vector<int> res(q);
    for (int i = 0, ma = 0, mb = -1; i < q; ++i) {
        const auto [a, b, idx] = Q[i];
        if (mb < a || ma > b) {
            del_range(ma, mb);
            add_range(a, b);
        } else {
            del_range(ma, a - 1);
            del_range(b + 1, mb);
            add_range(a, ma - 1);
            add_range(mb + 1, b);
        }
        ma = a;
        mb = b;
        res[idx] = mode(ma, mb);
    }

    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