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;

struct hashp {
    size_t operator()(const pair<int,int>& p) const
    {
        return p.F ^ (p.S + 2376487 + ((p.F) << 6) + ((p.F) >> 2));
    }
};

int x[N];
unordered_map<pair<int,int>,int, hashp> counts(18*N+1);
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) {
    int su=0;
    auto xx = counts.find({ancl,val});
    if ( xx != counts.end()) {
        su += xx->S;
    }
    xx = counts.find({ancr,val});
    if (xx != counts.end()) {
        su += xx->S;
    }
    return su;
}

void make_trees() {
    int L = N/2;
    int lo = 0;
    int hi = N/2;
    for (int i=2;i<2*N;i++) {
        for (int j=lo; j<min(n,hi); j++) {
            int r = ++counts[{i,x[j]}];
            if (r>L/2) dom[i] = x[j];
        }
        lo+=L;
        hi+=L;
        if (lo==N) {
            L/=2;
            lo=0;
            hi=L;
        }
    }
}

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) {
            auto xx = counts.find({aa,v});
            if (xx != counts.end()) su += xx->S;
            ++aa;
        }
        if (bb%2 == 0) {
            auto xx = counts.find({bb,v});
            if (xx != counts.end()) su += xx->S;
            --bb;
        }
        aa/=2;
        bb/=2;
    }
    return su;
}

set<int> tried;

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

    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