Kyselyt

#include <bits/stdc++.h>
 
#define pii pair<int, int>
#define pdd pair<double, double>
#define ull unsigned long long
#define uint unsigned int
#define ll long long
#define INF 999999999
#define LINF 999999999999999999
#define M 1000000007
#define E 0.0000001
#define N (1<<19)
 
using namespace std;
 
map<int, vector<int>> m;
 
int v[N + 2][19];
int a[N + 2][19];
 
pii ans (int l, int r, int x, int y, int i, int j) {
    if (y < l || x > r) return {0, 0};
    //cout<<l<<" "<<r<<" "<<x<<" "<<y<<" "<<i<<" "<<j<<endl;
    if (l == x && r == y) return {v[i][j], a[i][j]};
    int d = r - l + 1;
    d /= 2;
    pii n = ans(l, r - d, x, min(y, r - d), 2 * i, j - 1);
    pii m = ans(l + d, r, max(x, l + d), y, 2 * i + 1, j - 1);
    //cout<<"DEBUG "<<m.first<<" "<<m.second<<endl;
    if (n.first == m.first) return {n.first, n.second + m.second};
    if (n.second == m.second) return {0, 0};
    if (n.second > m.second) return {n.first, n.second - m.second};
    return {m.first, m.second - n.second};
}
 
int main () {
    cin.sync_with_stdio(false);
    cin.tie(0);
    int n, k;
    cin>>n>>k;
    
    for (int i = 0; i < N; i++) v[i][0] = -1 - i, a[i][0] = 0;
 
    for (int i = 0; i < n; i++) {
        ll k;
        cin>>k;
        v[i][0] = k;
        a[i][0] = 1;
        m[k].push_back(i);
    }
 
    int l = N;
    for (int i = 1; i < 19; i++) {
        l /= 2;
        for (int j = 0; j < l; j++) {
            if (v[2 * j][i - 1] == v[2 * j + 1][i - 1]) {
                v[j][i] = v[2 * j][i - 1];
                a[j][i] = a[2 * j][i - 1] + a[2 * j + 1][i - 1];
            } else if (a[2 * j][i - 1] == a[2 * j + 1][i - 1]) {
                v[j][i] = 0;
                a[j][i] = 0;
            } else if (a[2 * j][i - 1] > a[2 * j + 1][i - 1]) {
                v[j][i] = v[2 * j][i - 1];
                a[j][i] = a[2 * j][i - 1] - a[2 * j + 1][i - 1];
            } else {
                v[j][i] = v[2 * j + 1][i - 1];
                a[j][i] = a[2 * j + 1][i - 1] - a[2 * j][i - 1];
            }
        }
    }
 
    //for (int i = 0; i < 4; i++) {
    //  for (int j = 0; j < 8; j++) cout<<v[j][i]<<" ";
    //  cout<<endl;
    //}
 
    for (int i = 0; i < k; i++) {
        int a, b;
        cin>>a>>b;
        a--;
        b--;
        int c = ans(0, N - 1, a, b, 0, 19).first;
        if (c == 0) cout<<-1<<endl;
        else {
            auto x = lower_bound(m[c].begin(), m[c].end(), a);
            auto y = upper_bound(m[c].begin(), m[c].end(), b);
            if (2 * (int)(y - x) > b - a + 1) cout<<c<<endl;
            else cout<<-1<<endl;
        }
    }
}

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