Kyselyt

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

map<int,int> merge(map<int,int> M, const map<int,int>& m) {
    for (auto [k,v]:m) M[k]+=v;
    return M;
}

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

struct Node {
    int boss = 0;
    int delta = 0;
    map<int,int> M;

    int cnt(int x) const {
        auto it = M.find(x);
        return it==M.end() ? 0 : it->second;
    }

    void init(int x) {
        boss = x;
        delta = 1;
        M[x] = 1;
    }

    void init(const Node& a, const Node& b) {
        M = a.M.size()>=b.M.size() ? merge(a.M,b.M) : merge(b.M,a.M);
        tie(boss, delta) = pii(a.boss, a.delta) + pii(b.boss, b.delta);
    }
};

Node 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].init(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 getcnt(int t, int ql, int qr, int x, int tl=0, int tr=N-1) {
    if (ql<=tl && qr>=tr) return T[t].cnt(x);
    if (qr<tl || ql>tr) return 0;
    int tm = (tl+tr)/2;
    return getcnt(2*t, ql, qr, x, tl, tm) +
           getcnt(2*t+1, ql, qr, x, tm+1, tr);
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int n,q; cin>>n>>q;
    for (int i=0; i<n; i++) {
        int x; cin>>x;
        T[N+i].init(x);
    }
    init();
    for (int a,b; cin>>a>>b;) {
        a--, b--;
        auto [boss,_] = getboss(1,a,b);
        if (boss && 2*getcnt(1,a,b,boss)>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: TIME LIMIT EXCEEDED

Test 11

Group: 3, 4

Verdict: ACCEPTED

Test 12

Group: 4

Verdict: TIME LIMIT EXCEEDED

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