Kyselyt

#include <bits/stdc++.h>
#define F first
#define S second
#define X real()
#define Y imag()
using namespace std;
typedef long long ll;
typedef long double ld;

const int N = 1<<18;
int n;

unordered_map<int,int> counts[2*N];
int dom[2*N];

int get_anc(int a, int b) {
    int lono=N+a;
    int hino=N+b-1;
    while (lono < hino) {
        lono /=2;
        hino /=2;
    }
    return lono;
}

void make_trees() {
    for (int i=N+n;i<2*N;i++) dom[i]=-1;
    for (int d=17;d>=0;d--) {
        int thres=(1<<(17-d))+1;
        for (int i = (1<<d);i<(1<<(d+1));i++) {
            if (dom[2*i] !=-1 && counts[2*i+1].count(dom[2*i]) && counts[2*i+1][dom[2*i]]+counts[2*i][dom[2*i]] >= thres) {
                dom[i] = dom[2*i];
            } else if (dom[2*i+1] !=-1 && counts[2*i].count(dom[2*i+1]) && counts[2*i][dom[2*i+1]]+counts[2*i+1][dom[2*i+1]] >= thres) {
                dom[i] = dom[2*i+1];
            } else dom[i] = -1;
            for (auto x : counts[2*i]) counts[i][x.F] = x.S;
            for (auto x : counts[2*i+1]) counts[i][x.F] += x.S;
        }
    }
}

int get_count(int a, int b, int v) {
    int aa = a+N;
    int bb = b-1+N;
    int su = 0;
    while (aa <=bb) {
        if (aa%2 == 1) {
            su += counts[aa].count(v) ? counts[aa][v] : 0;
            ++aa;
        }
        if (bb%2 == 0) {
            su += counts[bb].count(v) ? counts[bb][v] : 0;
            --bb;
        }
        aa/=2;
        bb/=2;
    }
    return su;
}


int answer(int a, int b) {
    int anc = get_anc(a,b);
    int aa = a+N;
    int bb = b-1+N;
    while (aa<=bb) {
        if (aa%2 == 1) {
            int tar = dom[aa++];
            if (tar != -1 && counts[anc][tar] >= (b-a)/2 + 1) {
                if (get_count(a,b,tar) >= ((b-a)/2) + 1) return tar;
            }
        }
        if (bb%2 == 0) {
            int tar = dom[bb--];
            if (tar != -1 && counts[anc][tar] >= (b-a)/2 + 1) {
                if (get_count(a,b,tar) >= ((b-a)/2) + 1) return tar;
            }
        }
        aa/=2;
        bb/=2;
    }
    return -1;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    int q;
    cin>>n>>q;
    for (int i=0;i<n;i++) {
        cin>>dom[N+i];
        counts[N+i][dom[N+i]]=1;
    }

    make_trees();

    for (int qu=0;qu<q;qu++) {
        int a, b;
        cin>>a>>b;
        cout << answer(a-1,b)<<"\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: 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