Kyselyt

input/code.cpp: In function 'int main()':
input/code.cpp:37: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]
   37 |             if (j0==v[2*i].size()){
      |                 ~~^~~~~~~~~~~~~~~
input/code.cpp:38: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]
   38 |                 if (j1==v[2*i+1].size()) break;
      |                     ~~^~~~~~~~~~~~~~~~~
input/code.cpp:44: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]
   44 |             else if (j1==v[2*i+1].size()){
      |                      ~~^~~~~~~~~~~~~~~~~
input/code.cpp:122:24: warning: comparison of integer expressions of different signedness: 'int' a...

#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 max_cnt[606060], max_ind[606060], num_cnt[606060];
map<int, int> m[606060];
vector<int> ntk[606060]; // ntk: need to know
vector<int> candidates[606060], interval_ind[606060];
int int_len[606060];
 
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, q;
    cin >> n >> q;
    int M=1;
    while (M <= n) M*=2;
    for (int i=0; i<n; ++i) {
        int x;
        cin >> x;
        v[M+i].push_back({x,1});
        max_cnt[M+i] = 1;
        max_ind[M+i] = x;
        num_cnt[M+i] = 1;
        m[M+i][x] = 1;
    }
    for (int i=M-1; i>=1; --i){
        int j0=0, j1=0;
        int ma_cnt = 0, ma_ind = 0;
        while (true){
            if (j0==v[2*i].size()){
                if (j1==v[2*i+1].size()) break;
                else {
                    v[i].PB(v[2*i+1][j1]);
                    j1++;
                }
            }
            else if (j1==v[2*i+1].size()){
                v[i].PB(v[2*i][j0]);
                j0++;
            }
            else {
                int f1 = v[2*i][j0].f, f2 = v[2*i+1][j1].f;
                if (f1 < f2 ){
                    v[i].PB(v[2*i][j0]);
                    j0++;
                }
                else if (f1 > f2){
                    v[i].PB(v[2*i+1][j1]);
                    j1++;
                }
                else {
                    int s1 = v[2*i][j0].s, s2 = v[2*i+1][j1].s;
                    v[i].PB({f1, s1 + s2});
                    if (s1 + s2 > ma_cnt){
                        ma_cnt = s1 + s2;
                        ma_ind = f1;
                    }
                    j0++;
                    j1++;
                }
            }
        }
        // cout << "hmm, here " << i << "\n";
        if (max_cnt[2*i] > ma_cnt){
            // To control the interval, number must appear in both subintervals (above)
            // or interval is partly empty on the right side (this case).
            ma_cnt = max_cnt[2*i];
            ma_ind = max_ind[2*i];
        }
        num_cnt[i] = num_cnt[2*i] + num_cnt[2*i+1];
        if (ma_cnt*2 > num_cnt[i]){
            max_cnt[i] = ma_cnt;
            max_ind[i] = ma_ind;
        }
    }
    /*
    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;
        int_len[i] = b-a+1;
        a+=M-1;
        b+=M-1;
        set<int> candi;
        while (b >= a){
            if (a%2==1){
                if (max_cnt[a]) candi.insert(max_ind[a]);
                // We only add number to candidates if it controls at least one subinterval.
                interval_ind[i].PB(a);
                a++;
            }
            if (b%2==0){
                if (max_cnt[b]) candi.insert(max_ind[b]);
                interval_ind[i].PB(b);
                b--;
            }
            a/=2;
            b/=2;
        }
        for (auto u:interval_ind[i]){
            for (auto ite:candi){
                ntk[u].PB(ite);
            }
        }
        for (auto u:candi) candidates[i].PB(u);
    }
    for (int i=1; i<=M+n; ++i){
        sort(ntk[i].begin(), ntk[i].end());
        int ind = 0;
        for (auto u:v[i]){
            while (ind < ntk[i].size() && ntk[i][ind] < u.f) ind++;
            if (ind < ntk[i].size() && ntk[i][ind] == u.f){
                m[i][u.f] = u.s;
            }
            if (ind == ntk[i].size()) break;
        }
    }
    for (int i=1; i<=q; ++i){
        bool found = false;
        for (auto u:candidates[i]){
            int num = 0;
            for (auto ite:interval_ind[i]) num+=m[ite][u];
            if (2*num > int_len[i]){
                cout << 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: TIME LIMIT EXCEEDED

Test 8

Group: 4

Verdict: ACCEPTED

Test 9

Group: 4

Verdict: TIME LIMIT EXCEEDED

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