Kyselyt

#include <bits/stdc++.h>
using namespace std;
#define N (1 << 18)
typedef vector<int> VI;

unordered_map<int, int> cnts[2 * N + 1];
vector<pair<int, int>> cms[2 * N + 1];

void put(int i, int x) {
  i += N;
  cnts[i][x]++;
  i /= 2;
  while (i >= 1) {
    cnts[i][x]++;
    i /= 2;
  }
}
void init(int n, VI &x) {
  for (int i = 1; i <= n; i++) {
    put(i, x[i]);
  }
  for (int i = N; i >= 1; i--) {
    map<int, int> mp;
    for (auto u : cnts[i / 2]) {
      mp[u.first] += u.second;
    }
    for (auto u : cnts[i / 2 + 1]) {
      mp[u.first] += u.second;
    }
    for (auto u : mp)
      cms[i].push_back({u.second, u.first});
    sort(cms[i].rbegin(), cms[i].rend());
  }
  for (int i = N + 1; i <= N + n; i++)
    cms[i].push_back({1, x[i - N]});
  // for (auto u : cms[1])
  //   cout << u.first << " - " << u.second << endl;
}

int cq(int a, int b, int x, VI &xs) {
  int ret = 0;
  a += N;
  b += N;
  while (a <= b) {
    // cout<<a << " ja " << b <<endl;
    if (a % 2 == 1) {
      if (a > N)
        ret += xs[a - N] == x;
      else
        ret += cnts[a][x];
      a++;
    }
    if (b % 2 == 0) {
      if (b > N)
        ret += xs[b - N] == x;
      else
        ret += cnts[b][x];
      b--;
    }
    a /= 2;
    b /= 2;
  }
  return ret;
}

int sq(int A, int B, VI &x) {
  int a = A + N;
  int b = B + N;
  set<int> mc;
  int Q = 2;
  while (a <= b) {
    if (a % 2 == 1) {
      for (int i = 0; i < min(Q, (int)cms[a].size()); i++)
        mc.insert(cms[a][i].second);
      a++;
    }
    if (b % 2 == 0) {
      for (int i = 0; i < min(Q, (int)cms[b].size()); i++)
        mc.insert(cms[b][i].second);
      b--;
    }
    a /= 2;
    b /= 2;
  }
  for (auto u : mc) {
    int c = cq(A, B, u, x);
    if (c > (B - A + 1) / 2)
      return u;
  }
  return -1;
}

int query(int a, int b, VI &x) { return sq(a, b, x); }

int main() {
  cin.tie(0);
  ios_base::sync_with_stdio(0);
  int n, q;
  cin >> n >> q;
  vector<int> x(n + 1);
  for (int i = 1; i <= n; i++)
    cin >> x[i];
  init(n, x);
  int a, b;
  for (int i = 0; i < q; i++) {
    cin >> a >> b;
    cout << query(a, b, x) << "\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: TIME LIMIT EXCEEDED

Test 7

Group: 3, 4

Verdict: TIME LIMIT EXCEEDED

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

Test 12

Group: 4

Verdict: TIME LIMIT EXCEEDED

Test 13

Group: 3, 4

Verdict: WRONG ANSWER

Test 14

Group: 4

Verdict: WRONG ANSWER

Test 15

Group: 4

Verdict: WRONG ANSWER

Test 16

Group: 4

Verdict: ACCEPTED