Kyselyt

input/code.cpp: In function 'int main()':
input/code.cpp:39: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]
   39 |         for (int j=0; j<v_temp.size(); ++j){
      |                       ~^~~~~~~~~~~~~~
input/code.cpp:41:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |             if (j+1 < v_temp.size()){
      |                 ~~~~^~~~~~~~~~~~~~~
input/code.cpp:97:19: warning: unused variable 'u' [-Wunused-variable]
   97 |         for (auto u:interval_ind[i]){
      |                   ^
input/code.cpp:108:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |             while (ind < ntk[i].size() && ntk[i][ind] < u.f) i...

#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){
        vector<pair<int, int>> v_temp;
        for (auto u:v[2*i]) v_temp.PB(u);
        for (auto u:v[2*i+1]) v_temp.PB(u);
        sort(v_temp.begin(), v_temp.end());
        int ma_cnt = 0, ma_ind = 0;
        for (int j=0; j<v_temp.size(); ++j){
            int f1 = v_temp[j].f, s1 = v_temp[j].s;
            if (j+1 < v_temp.size()){
                int f2 = v_temp[j+1].f, s2 = v_temp[j+1].s;
                if (f1 == f2){
                    v[i].PB({f1, s1 + s2});
                    if (s1 + s2 > ma_cnt){
                        ma_cnt = s1 + s2;
                        ma_ind = f1;
                        
                    }
                    j++;
                }
                else v[i].PB({v_temp[j].f, v_temp[j].s});
            }
            else v[i].PB({v_temp[j].f, v_temp[j].s});
        }
        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 (auto u:v[i]) m[i][u.f] = u.s;
    }
    /*
    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[i].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: ACCEPTED

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: ACCEPTED

Test 16

Group: 4

Verdict: ACCEPTED