Kyselyt

#include <bits/stdc++.h>

#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()

using namespace std;
using ll = long long;

const int inf = 1e9;
const ll LLInf = 1e18;
const int SQR = 300;



int main() {
    cin.tie(0)->sync_with_stdio(0);
    int n, q;
    cin >> n >> q;
    vector<int> a(n);
    vector<int> vals;
    for (int&x : a) {
        cin >> x;
        vals.push_back(x);
    }

    sort(all(vals));
    vals.erase(unique(all(vals)), vals.end());

    auto comp = [&](int x) {
        return lower_bound(all(vals), x) - begin(vals);
    };
    map<int, int> inv;

    for (int& x : a) {
        int c = comp(x);
        inv[c] = x;
        x = c;
    }

    map<int, int> cnt;
    vector<int> high;

    for (int x : a) {
        cnt[x]++;
        if (cnt[x] == SQR) {
            high.push_back(x);
        }
    }

    vector<vector<int>> pfx(sz(high), vector<int> (n));
    for (int j = 0; j < sz(high); ++j) {
        int x = high[j];
        for (int i = 0; i < n; ++i) {
            if (x == a[i]) pfx[j][i] = 1;
            if (i) pfx[j][i] += pfx[j][i - 1];
        }
    }

    auto get_pfx = [&](int j, int l, int r) {
        return pfx[j][r] - (l == 0 ? 0 : pfx[j][l - 1]);
    };

    auto solve = [&](int l, int r) {
        int len = r - l + 1;
        // for (int i = l; i <= r; ++i) {
        //     // cerr << a[i] << " ";
        // }
        // cerr << "\n";
        if (len >= 2 * SQR) {
            // must be in high

            for (int j = 0; j < sz(high); ++j) {
                // cerr << "j and pfx: " << j << " " << get_pfx(j, l, r) << "\n";
                // cerr << "high[j]: " << high[j] << "\n";
                if (get_pfx(j, l, r) > len / 2) {
                    return high[j];
                } 
            }
            return -1;
        } else {
            vector<int> f(sz(vals));
            for (int i = l; i <= r; ++i) {
                f[a[i]]++;
                if (f[a[i]] > len / 2) {
                    return a[i];
                }
            }
            return -1;
        }
    };

    while (q--) {
        int l, r;
        cin >> l >> r;
        l--; r--;
        int ans = solve(l, r);
        if (ans == -1) cout << ans << "\n";
        else cout << inv[ans] << "\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