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
 
struct Query {
	int l, r, idx;
};
 
Query qr[N];
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) * 4);
 
  unordered_map<int, int> z;
  unordered_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;
		qr[i] = q;
	}
 
	sort(qr, qr + q, cmp);
 
	
	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: ACCEPTED

Test 3

Group: 1, 3, 4

Verdict: ACCEPTED

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

Test 14

Group: 4

Verdict: ACCEPTED

Test 15

Group: 4

Verdict: ACCEPTED

Test 16

Group: 4

Verdict: ACCEPTED