Kyselyt

input/code.cpp: In function 'int main()':
input/code.cpp:27:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |     for (int i = 0; i < v.size(); i++) {
      |                     ~~^~~~~~~~~~

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


int N = 700;
int x[200002];
map<int,int> m;
int mrev[200002]; 
int cnts[200002];
vector<int> commons;
int pref[200002][580];


int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n,q;
    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> x[i];
    vector<int> v;
    for (int i = 1; i <= n; i++) v.push_back(x[i]);
    sort(v.begin(), v.end());
    int k = 0;
    for (int i = 0; i < v.size(); i++) {
        if (i == 0 || v[i] != v[i-1]) {
            k++;
            mrev[k] = v[i];
            m[v[i]] = k;
        }
    }
    for (int i = 1; i <= n; i++) x[i] = m[x[i]];
    for (int i = 1; i <= n; i++)  cnts[x[i]]++;
    for (int i = 1; i <= 200000; i++) {
        if (cnts[i] >= N/2) commons.push_back(i);
    }

    for (int a : commons) {
        for (int i = 1; i <= n; i++) {
            pref[i][a] = pref[i-1][a];
            if (x[i] == a) pref[i][a]++;
        }
    }

    for (int i = 0; i < q; i++) {
        int a, b;
        cin >> a >> b;
        int cmn = 0;
        int cmncnt = 0;
        if (b-a+1 <= N) {
            for (int j = a; j <= b; j++) cnts[x[j]] = 0;
            for (int j = a; j <= b; j++) {
                cnts[x[j]]++;
                if (cnts[x[j]] > cmncnt) {
                    cmncnt = cnts[x[j]];
                    cmn = x[j];
                }
            }
        } else {
            for (int z : commons) {
                int cntt = pref[b][z] - pref[a-1][z];
                if (cntt > cmncnt) {
                    cmncnt = cntt;
                    cmn = z;
                }
            }
        }
        if (2*cmncnt > b-a+1) {
            cout << mrev[cmn] << "\n";
        } else {
            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: WRONG ANSWER

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