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());

bool check[N];
int numm[N];

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 (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;

    vector<int> c;
    for (int i = 0; i < 80; ++i) {
      int j = a + (rng() % (b - a + 1));
      ++numm[v[j]];
      if (!check[v[j]]) {
        c.push_back(v[j]);
        check[v[j]] = 1;
      }
    }

    vector<pair<int, int>> c2;
    for (int x : c) {
      if (numm[x] > 10) c2.push_back({numm[x], x});
      numm[x] = 0;
      check[x] = 0;
    }
    sort(c2.rbegin(), c2.rend());
    while (c2.size() > 2) c2.pop_back();

    bool found = 0;
    for (auto p : c2) {
      int x = p.second;
      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;

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

Test 6

Group: 2, 3, 4

Verdict: ACCEPTED

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

Test 16

Group: 4

Verdict: ACCEPTED