Kyselyt

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

map<int, int> cnts[2 * N + 10];
int lz[2 * N + 10];
int cms[2 * N + 10];

void put(int i, int x) {
  i += N;
  cnts[i][x]++;
  lz[i]++;
  i /= 2;
  while (i >= 1) {
    lz[i]++;
    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;
    if (i * 2 > N) {
      if (i * 2 - N <= n)
        mp[x[i * 2 - N]]++;
    } else {
      for (auto u : cnts[i * 2]) {
        mp[u.first] += u.second;
      }
    }
    for (auto u : cnts[i * 2 + 1]) {
      mp[u.first] += u.second;
    }
    cnts[i] = mp;
    for (auto u : mp)
      if (u.second > lz[i] / 2)
        cms[i] = u.first;
  }
  for (int i = N + 1; i <= N + n; i++)
    cms[i] = x[i - N];
}

int cq(int a, int b, int x, VI &xs) {
  int ret = 0;
  a += N;
  b += N;
  while (a <= b) {
    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;
  vector<int> mc;
  while (a <= b) {
    if (a % 2 == 1) {
      if (cms[a] && find(mc.begin(), mc.end(), cms[a]) == mc.end())
        mc.push_back(cms[a]);
      a++;
    }
    if (b % 2 == 0) {
      if (cms[b] && find(mc.begin(), mc.end(), cms[b]) == mc.end())
        mc.push_back(cms[b]);
      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: ACCEPTED

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