Kyselyt

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

const int N = 202020;
set<pair<int, int>> s[N];

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

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

  int n, q;
  cin >> n >> q;

  vector<int> v(n);
  for (int i = 0; i < n; ++i) cin >> v[i];

  map<int, int> m;
  map<int, int> rm;
  {
    int x = 1;
    for (int i = 0; i < n; ++i) {
      if (m[v[i]] == 0) {
        rm[x] = v[i];
        m[v[i]] = x++;
      }
      v[i] = m[v[i]];
    }
  }

  // for (auto x : v) cout << x << " ";
  // cout << endl << endl;

  for (int i = 0; i < n; ++i) s[v[i]].insert({i, s[v[i]].size()});

  while (q--) {
    int a, b;
    cin >> a >> b;

    --a;
    --b;

    set<int> c;
    for (int i = 0; i < 20; ++i) {
      int j = a + (rng() % (b - a + 1));
      c.insert(v[j]);
    }

    bool found = 0;
    for (int x : c) {
      auto it = s[x].lower_bound({a, 0});
      auto it2 = s[x].lower_bound({b + 1, 0});
      --it2;
      int num = it2->second - it->second + 1;

      // cout << "{" << a << " -> " << b << "} == " << x << " count=" << num << endl;
      if (num >= (b - a + 1) / 2 + 1) {
        cout << rm[x] << endl;
        found = 1;
      }
    }
    if (!found) cout << "-1" << endl;
  }
}

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: WRONG ANSWER

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