Kyselyt

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

#ifdef LOCAL
#include "debug.hpp"
#else
#define debug(...) 0xffff
#endif

#define N 202020

// https://codeforces.com/blog/entry/61203    (Hilbert curve sort for Mo)

inline int64_t gilbertOrder(int x, int y, int pow, int rotate) {
	if (pow == 0) {
		return 0;
	}
	int hpow = 1 << (pow-1);
	int seg = (x < hpow) ? (
		(y < hpow) ? 0 : 3
	) : (
		(y < hpow) ? 1 : 2
	);
	seg = (seg + rotate) & 3;
	const int rotateDelta[4] = {3, 0, 0, 1};
	int nx = x & (x ^ hpow), ny = y & (y ^ hpow);
	int nrot = (rotate + rotateDelta[seg]) & 3;
	int64_t subSquareSize = int64_t(1) << (2*pow - 2);
	int64_t ans = seg * subSquareSize;
	int64_t add = gilbertOrder(nx, ny, pow-1, nrot);
	ans += (seg == 1 || seg == 2) ? add : (subSquareSize - add - 1);
	return ans;
}
 

struct Query {
  int l, r, idx;
  int64_t ord;

  inline void calcOrder() {
    ord = gilbertOrder(l, r, 21, 0);
  }
};

inline bool operator<(const Query &a, const Query &b) {
  return a.ord < b.ord;
}

vector<Query> qr;
int arr[N];
int res[N];
int cnt[202020];
int n, q, S;
int curr = 0;
set<pair<int, int>> curset;
 
bool cmp(const Query& A, const Query& B) {
  int a = A.l / S, b = B.l / S;
  if (a != b) return a < b;
  else return A.r < B.r;
}
 
void add(int x) {
  if (cnt[x] != 0) {
    auto p = curset.find({cnt[x], x});
    curset.erase(p);
  }
  curset.insert({++cnt[x], x});
}
 
void del(int x) {
  auto p = curset.find({cnt[x], x});
  curset.erase(p);
  cnt[x]--;
  if (cnt[x] > 0) {
    curset.insert({cnt[x], x});
  }
}
 
int main() {
  ios_base::sync_with_stdio(0); cin.tie(0);
  cin >> n >> q;
  S = floor(sqrt(n));

  map<int, int> z;
  map<int, int> rev;
  
  for (int i = 0; i < n; i++) {
    cin>>arr[i];
    z[arr[i]] = 1;
  }

  int idx = 0;
  for (auto &p : z) {
    z[p.first] = ++idx;
    rev[idx] = p.first;
  }

  for (int i = 0; i < n; i++) {
    arr[i] = z[arr[i]];
  }

  for (int i = 0; i < q; i++) {
    int a, b; cin >> a >> b; a--; b--;
    Query q; q.l = a; q.r = b; q.idx = i;
    q.calcOrder();
    qr.push_back(q);
  }
  
  sort(qr.begin(), qr.end());
  
  int l = 0, r = -1;
  for (int i = 0; i < q; i++) {
    int a = qr[i].l, b = qr[i].r;
    while (r < b) add(arr[++r]);
    while (r > b) del(arr[r--]);
    while (l < a) del(arr[l++]);
    while (l > a) add(arr[--l]);

    int rangelen = b - a + 1;
    auto p = *curset.rbegin();
    if (p.first > (rangelen / 2)) {
      res[qr[i].idx] = rev[p.second];
    } else res[qr[i].idx] = -1;
  }

  for (int i = 0; i < q; i++) {
    cout << res[i] << "\n";
  }
}

Test 1

Group: 1, 2, 3, 4

Verdict: ACCEPTED

Test 2

Group: 1, 2, 3, 4

Verdict: TIME LIMIT EXCEEDED

Test 3

Group: 1, 3, 4

Verdict: TIME LIMIT EXCEEDED

Test 4

Group: 2, 3, 4

Verdict: TIME LIMIT EXCEEDED

Test 5

Group: 2, 3, 4

Verdict: TIME LIMIT EXCEEDED

Test 6

Group: 2, 3, 4

Verdict: TIME LIMIT EXCEEDED

Test 7

Group: 3, 4

Verdict: TIME LIMIT EXCEEDED

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

Test 12

Group: 4

Verdict: TIME LIMIT EXCEEDED

Test 13

Group: 3, 4

Verdict: TIME LIMIT EXCEEDED

Test 14

Group: 4

Verdict: TIME LIMIT EXCEEDED

Test 15

Group: 4

Verdict: TIME LIMIT EXCEEDED

Test 16

Group: 4

Verdict: ACCEPTED