Kyselyt

input/code.cpp: In function 'void solveRange(int, int)':
input/code.cpp:58:11: 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 (i == freq.size()) return void(cout << "-1\n");
      |         ~~^~~~~~~~~~~~~~

#include <bits/stdc++.h>
#include <random>

using namespace std;
using ll = long long;
 
#ifdef LOCAL
#include "debug.hpp"
#include "pbds.h"
#else
#define debug(...) 0xffff
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#endif
 
#define N 202020
#define M (1<<18)
#define INF 2147483600
 
random_device rd;
mt19937 gen(rd());
unordered_map<int, ordered_set<int>> h;
 
int arr[N], usedInQuery[N], cnts[N];
 
int n, q, queryIndex = 0;
 
void solveRange(int a, int b) {
  // find 2 best candidates between [a..b] that could be dominant
  // max iter? maybe 50-100 or something
  int max_iter = 25;
  unordered_map<int, int> cnts;
  cnts.reserve(64);
  cnts.max_load_factor(0.7f);
  queryIndex++;
 
  for (int i = 0; i < max_iter; i++) {
    int idxbetween = a + (int)(gen() % (b-a+1));
    if (usedInQuery[idxbetween] == queryIndex) continue;
    usedInQuery[idxbetween] = queryIndex;
    int x = arr[idxbetween];
    cnts[x]++;
  }
 
  vector<pair<int, int>> freq;
  for (const auto& p : cnts) {
    freq.push_back({p.second, p.first});
  }
 
  sort(freq.begin(), freq.end(), [](const auto& l, const auto& r) { return l.first > r.first; });
 
  // try 2 best
  int TRYDIFF = 2;
  for (int i = 0; i < TRYDIFF; i++) {
    if (i == freq.size()) return void(cout << "-1\n");
    pair<int, int> p = freq[i];
    int val = p.second;

    int cnt = h[val].order_of_key(b+1) - h[val].order_of_key(a);

    if (cnt > (b-a+1)/2) {
      return void(cout << val << "\n");
    }
  }
 
  cout << "-1\n";
}
 
int main() {
  ios_base::sync_with_stdio(0); cin.tie(0);
  cin>>n>>q;
 
  for (int i = 1; i <= n; i++) {
    cin>>arr[i];
    h[arr[i]].insert(i);
  }
 
  for (int i = 0; i < q; i++) {
    int a, b; cin>>a>>b;
    solveRange(a, b);
  }
}

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