Kyselyt

input/code.cpp: In function 'int main()':
input/code.cpp:26:24: warning: comparison of integer expressions of different signedness: 'std::multiset<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   26 |         if (s.count(u) >= sq) s1.insert(u);
      |             ~~~~~~~~~~~^~~~~

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


int t[202020][500];
int x[202020];
int rev_map1[500];
map<int, int> m;
 
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, q;
    cin >> n >> q;
    int sq = 1;
    while (sq*sq < n) sq++;
    multiset<int> s;
    for (int i=1; i<=n; ++i){
        cin >> x[i];
        s.insert(x[i]);
    }
    set<int> s1;
    for (auto u:s){
        if (s.count(u) >= sq) s1.insert(u);
    }
    int c =1;
    for (auto u:s1){
        m[u] = c;
        rev_map1[c]= u;
        c++;
    }
    for (int i=1; i<=n; ++i){
        int d = m[x[i]];
        for (int j=1; j<=c; ++j){
            t[i][j] = t[i-1][j];
            if (d == j) t[i][j]++;
        }
    }
    for (int i=1; i<=q; ++i){
        int a, b;
        cin >> a >> b;
        if (b-a <= sq){
            vector<int> v;
            for (int j=a; j<=b; ++j){
                v.push_back(x[j]);
            }
            sort(v.begin(), v.end());
            int prev =0, cnt = 0, ma = 0, ma_ind = 0;
            for (int j=0; j<=b-a; ++j){
                if (v[j] != prev){
                    cnt = 1;
                    prev = v[j];
                }
                else {
                    cnt++;
                }
                if (cnt > ma){
                    ma = cnt;
                    ma_ind = v[j];
                }
            }
            if (ma*2 > b-a+1){
                cout << ma_ind << "\n";
            }
            else cout << "-1\n";
        }
        else {
            bool found = false;
            for (int j=1; j<=c; ++j){
                if ((t[b][j] - t[a-1][j])*2 > b-a+1 ){
                    cout << rev_map1[j] << "\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: TIME LIMIT EXCEEDED

Test 5

Group: 2, 3, 4

Verdict: TIME LIMIT EXCEEDED

Test 6

Group: 2, 3, 4

Verdict: TIME LIMIT EXCEEDED

Test 7

Group: 3, 4

Verdict: ACCEPTED

Test 8

Group: 4

Verdict: TIME LIMIT EXCEEDED

Test 9

Group: 4

Verdict: TIME LIMIT EXCEEDED

Test 10

Group: 4

Verdict: ACCEPTED

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: TIME LIMIT EXCEEDED

Test 16

Group: 4

Verdict: TIME LIMIT EXCEEDED