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];

pair<int,int> get_ancs(int a, int b) {
    int lono=N+a;
    int hino=N+b-1;
    int aa = lono;
    int bb = hino;
    while (aa/2 < bb/2) {
        if (aa%2==0) lono=aa/2;
        if (bb%2==1) hino=bb/2;
        aa /=2;
        bb /=2;
    }
    return {lono,hino};
}

int get_am(int ancl, int ancr, int val) {
    return ( counts[ancl][val]) + (counts[ancr][val]);
}

void make_trees() {
    for (int d=17;d>=0;d--) {
        int thres=(1<<(17-d))+1;
        for (int i = (1<<(d+1))-1;i>=(1<<d);--i) {
            if (dom[2*i] > 0 && 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] >0 && 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];
            }
            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][v];
            ++aa;
        }
        if (bb%2 == 0) {
            su += counts[bb][v];
            --bb;
        }
        aa/=2;
        bb/=2;
    }
    return su;
}


int answer(int a, int b) {
    pair<int,int> anc = get_ancs(a,b);
    int aa = a+N;
    int bb = b-1+N;
//    unordered_set<int> tried;
    while (aa<=bb) {
        if (aa%2 == 1) {
            int tar = dom[aa++];
            if (tar > 0 && get_am(anc.F,anc.S,tar) >= (b-a)/2 + 1 /*&& !tried.count(tar)*/) {
//                tried.insert(tar);
                if (get_count(a,b,tar) >= ((b-a)/2) + 1) return tar;
            }
        }
        if (bb%2 == 0) {
            int tar = dom[bb--];
            if (tar > 0 && get_am(anc.F,anc.S,tar) >= (b-a)/2 + 1 /*&& !tried.count(tar)*/) {
//                tried.insert(tar);
                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: 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