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;

int x[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].count(val) ? counts[ancl][val] : 0) + (counts[ancr].count(val) ? counts[ancr][val] : 0);
}

void make_trees() {
    int L = N;
    int lo = 0;
    int hi = N;
    for (int i=1;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) {
            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 tries = 15;

int answer(int a, int b) {
    pair<int,int> anc = get_ancs(a,b);
    int aa = a+N;
    int bb = b-1+N;
    for (int r = 0; r < tries; r++) {
        int ind = a + rand() % (b-a);
        int val = dom[ind+N];
        if (get_count(a,b,val) > (b-a)/2) return val;
    }
    return -1;
    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>>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: WRONG ANSWER

Test 6

Group: 2, 3, 4

Verdict: ACCEPTED

Test 7

Group: 3, 4

Verdict: TIME LIMIT EXCEEDED

Test 8

Group: 4

Verdict: ACCEPTED

Test 9

Group: 4

Verdict: WRONG ANSWER

Test 10

Group: 4

Verdict: TIME LIMIT EXCEEDED

Test 11

Group: 3, 4

Verdict: TIME LIMIT EXCEEDED

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: WRONG ANSWER

Test 16

Group: 4

Verdict: WRONG ANSWER