Kyselyt

#include <bits/stdc++.h>

#define N (1<<18)

using namespace std;

int v[N];
int comp[N];
vector<int> mp[N];
map<int, int> enc;
map<int, int> de;
int pot[N];
int tried[N];

int main() {
    cin.sync_with_stdio(false);
    cin.tie(0);
    srand(time(0));
    int n, q;
    cin>>n>>q;
    vector<int> vals;
    for (int i = 1; i <= n; i++) {
        cin>>v[i];
        vals.push_back(v[i]);
    }
    int g = 1;
    for (int i = 1; i < N; i++) {
        if (2 * g <= i) g *= 2;
        pot[i] = g;
    }
    vals.push_back(-1);
    sort(vals.begin(), vals.end());
    int cnt = 0;
    for (int i = 1; i <= n; i++) {
        if (vals[i] != vals[i - 1]) cnt++;
        enc[vals[i]] = cnt;
        de[cnt] = vals[i];
    }
    for (int i = 1; i <= n; i++) {
        comp[i] = enc[v[i]];
        mp[comp[i]].push_back(i);
    }
    
    for (int i = 1; i <= n; i++) {
        if (mp[comp[i]].back() != n + 1) mp[comp[i]].push_back(n + 1);
    }
    while (q --> 0) {
        int l, r;
        cin>>l>>r;
        vector<int> att;
        for (int t = 0; t < 21; t++) {
            int len = r - l + 1;
            int i = l + (rand() % len);
            int x = comp[i];
            if (tried[x]) continue;
            tried[x] = 1;
            att.push_back(x);
            int li = -1;
            int ri = -1;
            int wl = mp[x].size();
            for (int inc = 2 * pot[wl]; inc >= 1; inc /= 2) {
                if (li + inc < wl && mp[x][li + inc] < l) li += inc;
            }
            ri = li;
            for (int inc = 2 * pot[wl - li]; inc >= 1; inc /= 2) {
                if (ri + inc < wl && mp[x][ri + inc] <= r) ri += inc;
            }
            if (2 * (ri - li) > len) {
                cout<<de[x]<<endl;
                goto end;
            }
        }
        cout<<-1<<endl;
        end:;
        for (int i : att) {
            tried[i] = 0;
        }
    }
}

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

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