Kyselyt

input/code.cpp: In function 'int main()':
input/code.cpp:57:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |             if (j0==v[2*i].size()){
      |                 ~~^~~~~~~~~~~~~~~
input/code.cpp:58:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |                 if (j1==v[2*i+1].size()) break;
      |                     ~~^~~~~~~~~~~~~~~~~
input/code.cpp:64:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |             else if (j1==v[2*i+1].size()){
      |                      ~~^~~~~~~~~~~~~~~~~
input/code.cpp:54:13: warning: unused variable 'ma_cnt' [-Wunused-variable]
   54 |         int ma...

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;

#define f first
#define s second
#define PB push_back

vector<pair<int, int>> v[606060];
int num_cnt[606060];
vector<pair<int, int>> max_cnt[606060];
map<int, int> to_small;
vector<int> candidates[606060], interval_ind[606060];
int int_len[606060];
int rev_map[202020];
int temp[202020];
int qa[202020], qb[202020];
set<pair<int, int>> s[202020];

void push(int i, pair<int, int> pu){
    v[i].PB(pu);
    if (pu.second*4 > num_cnt[i]){
        max_cnt[i].PB({pu.s, pu.f});
    }
}
 
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, q;
    cin >> n >> q;
    int M=1;
    while (M <= n) M*=2;
    int e = 1;
    for (int i=0; i<n; ++i) {
        int x;
        cin >> x;
        if (to_small[x]==0){
            to_small[x]=e;
            rev_map[e] = x;
            e++;
        }
        x = to_small[x];
        v[M+i].push_back({x,1});
        max_cnt[M+i].PB({1, x});
        num_cnt[M+i] = 1;
        
        s[x].insert({i+1, temp[x]+1});
        temp[x]++;
    }
    for (int i=M-1; i>=1; --i){
        int j0=0, j1=0;
        int ma_cnt = 0, ma_ind = 0;
        num_cnt[i] = num_cnt[2*i] + num_cnt[2*i+1];
        while (true){
            if (j0==v[2*i].size()){
                if (j1==v[2*i+1].size()) break;
                else {
                    push(i, v[2*i+1][j1]);
                    j1++;
                }
            }
            else if (j1==v[2*i+1].size()){
                push(i, v[2*i][j0]);
                j0++;
            }
            else {
                int f1 = v[2*i][j0].f, f2 = v[2*i+1][j1].f;
                if (f1 < f2 ){
                    push(i, v[2*i][j0]);
                    j0++;
                }
                else if (f1 > f2){
                    push(i, v[2*i+1][j1]);
                    j1++;
                }
                else {
                    int s1 = v[2*i][j0].s, s2 = v[2*i+1][j1].s;
                    push(i, {f1, s1+s2});
                    j0++;
                    j1++;
                }
            }
        }
        // cout << "hmm, here " << i << "\n";
    }
    /*
    for (int i=1; i<=2*M-1; ++i){
        cout << "here " << i << " " << max_cnt[i] << " " << max_ind[i] << " " << num_cnt[i] << "\n";
        for (auto u:v[i]) cout << u.f << " " << u.s << " " << m[i][u.f] << "  ";
        cout << "\n";
    } */
    for (int i=1; i<=q; ++i){
        int a, b;
        cin >> a >> b;
        qa[i]=a;
        qb[i]=b;
        // In this version, we only use segment tree to find candidate answers.
        int_len[i] = b-a+1;
        a+=M-1;
        b+=M-1;
        while (b >= a){
            if (a%2==1){
                interval_ind[i].PB(a);
                a++;
            }
            if (b%2==0){
                interval_ind[i].PB(b);
                b--;
            }
            a/=2;
            b/=2;
        }
        reverse(interval_ind[i].begin(), interval_ind[i].end());
        int int_len_sum=0;
        set<int> candi;
        for (auto u:interval_ind[i]){
            for (auto ite:max_cnt[u]){
                candi.insert(ite.s);
            }
            int_len_sum+=num_cnt[u];
            if (int_len_sum*4 > 3*int_len[i]) break;
        }
        for (auto u:candi) candidates[i].PB(u);
    }
    
    for (int i=1; i<=q; ++i){
        bool found = false;
        for (auto u:candidates[i]){
            int num = 0;
            auto it = s[u].lower_bound({qa[i], 0});
            auto ite = s[u].lower_bound({qb[i],0});
            int a_ind = it->s;
            int b_ind =0;
            if (ite==s[u].end()){
                b_ind=s[u].size();
            }
            else {
                if (ite->f == qb[i]) b_ind = ite->s;
                else b_ind = ite->s-1;
            }
            //cout << i << " " << u << " " << rev_map[u] << " " << a_ind << " " << b_ind << "\n";
            if (2*(b_ind-a_ind+1) > int_len[i]){
                cout << rev_map[u] << "\n";
                found = true;
                break;
            }
        }
        if (found == false) 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: ACCEPTED

Test 11

Group: 3, 4

Verdict: ACCEPTED

Test 12

Group: 4

Verdict: ACCEPTED

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