Kyselyt

#include <algorithm>
#include <iostream>
#include <map>
#include <utility>
#include <vector>
using namespace std;
using pii = pair<int,int>;
const int N=1<<18;

#define boss first
#define delta second

pii operator+(pii a, pii b) {
    if (a.boss == b.boss) {
        return pii(a.boss, a.delta + b.delta);
    }
    return a.delta >= b.delta ?
           pii(a.boss, a.delta - b.delta) :
           pii(b.boss, b.delta - a.delta);
}

pii T[4*N];

void init(int t=1, int tl=0, int tr=N-1) {
    if (tl>=tr) return;
    int tm = (tl+tr)/2;
    init(2*t, tl, tm);
    init(2*t+1, tm+1, tr);
    T[t] = T[2*t] + T[2*t+1];
}

pii getboss(int t, int ql, int qr, int tl=0, int tr=N-1) {
    if (ql<=tl && qr>=tr) return pii(T[t].boss, T[t].delta);
    if (qr<tl || ql>tr) return pii(0, 0);
    int tm = (tl+tr)/2;
    return getboss(2*t, ql, qr, tl, tm) +
           getboss(2*t+1, ql, qr, tm+1, tr);
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    map<int, vector<int>> occ;
    int n,q; cin>>n>>q;
    for (int i=0; i<n; i++) {
        int x; cin>>x;
        T[N+i] = pii(x,1);
        occ[x].push_back(i);
    }
    for (auto& [_,v] : occ) v.push_back(-1), v.push_back(N);
    for (auto& [_,v] : occ) sort(v.begin(), v.end());
    init();
    for (int a,b; cin>>a>>b;) {
        a--, b--;
        auto [boss,_] = getboss(1,a,b);
        auto L = lower_bound(occ[boss].begin(), occ[boss].end(), a);
        auto R = upper_bound(occ[boss].begin(), occ[boss].end(), b) - 1;
        if (2*(R-L+1)>b-a+1) {
            cout << boss << '\n';
        }
        else {
            cout << "-1\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