Kyselyt

input/code.cpp: In constructor 'Node::Node(int)':
input/code.cpp:27:9: warning: 'Node::r' will be initialized after [-Wreorder]
   27 |   Node* r;
      |         ^
input/code.cpp:25:7: warning:   'int Node::val' [-Wreorder]
   25 |   int val;
      |       ^~~
input/code.cpp:28:3: warning:   when initialized here [-Wreorder]
   28 |   Node(int v) : l(nullptr), r(nullptr), val(v) {}
      |   ^~~~
input/code.cpp: In constructor 'Node::Node(Node*, Node*)':
input/code.cpp:27:9: warning: 'Node::r' will be initialized after [-Wreorder]
   27 |   Node* r;
      |         ^
input/code.cpp:25:7: warning:   'int Node::val' [-Wreorder]
   25 |   int val;
      |       ^~~
input/code.cpp:29:3: warning:   when initialized here [-Wreorder]
   29 |   Node(Node* a, Node* b) : l(a), r(b), val(0) {
      |   ^~~~
input/code.cpp: In function 'void solveRange(int, int)':
input/code.cpp:91:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >...

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

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

#define N 202020
#define M (1<<18)
#define INF 2147483600

random_device rd;
mt19937 gen(rd());

int arr[N];
unordered_map<int, int> rev;

int n, q;

struct Node {
  int val;
  Node* l;
  Node* r;
  Node(int v) : l(nullptr), r(nullptr), val(v) {}
  Node(Node* a, Node* b) : l(a), r(b), val(0) {
    if (l) val += l->val;
    if (r) val += r->val;
  }
};

Node* roots[202020];

// add 1 to number: cnt
Node* update(Node* cur, int pos, int tl, int tr) {
  if (tl == tr) return new Node((cur ? cur->val : 0) + 1);
  int tm = (tl + tr) / 2;

  Node* left_tree = cur ? cur->l : nullptr;
  Node* right_tree = cur ? cur->r : nullptr;

  if (pos <= tm) return new Node(update(left_tree, pos, tl, tm), right_tree);
  else return new Node(left_tree, update(right_tree, pos, tm+1, tr));
}

pair<int, int> query(Node* a, Node* b, int pos, int tl, int tr) {
  if (tl == tr) {
    int bv = b ? b->val : 0;
    int av = a ? a->val : 0;
    return make_pair(bv - av, tl);
  }
  int tm = (tl + tr) / 2;

  Node* a_left = a ? a->l : nullptr;
  Node* b_left = b ? b->l : nullptr;

  if (pos <= tm) return query(a_left, b_left, pos, tl, tm);

  Node* a_right = a ? a->r : nullptr;
  Node* b_right = b ? b->r : nullptr;

  return query(a_right, b_right, pos, tm+1, tr);
}

void solveRange(int a, int b) {
  // find 3 best candidates between [a..b] that could be dominant
  // max iter? maybe 50-100 or something
  int max_iter = 15;
  uniform_int_distribution<> dst(a, b);
  unordered_map<int, int> cnts;

  for (int i = 0; i < max_iter; i++) {
    int idxbetween = dst(gen);
    int x = arr[idxbetween];
    cnts[x]++;
  }

  vector<pair<int, int>> freq;
  for (const auto& p : cnts) {
    freq.push_back({p.second, p.first});
  }

  sort(freq.begin(), freq.end(), [](const auto& l, const auto& r) { return l.first > r.first; });

  // try 3 best
  int TRYDIFF = 2;
  for (int i = 0; i < TRYDIFF; i++) {
    if (i == freq.size()) return void(cout << "-1\n");
    pair<int, int> p = freq[i];
    // cout << "for range "<<a<<" "<<b<<" one candidate is element "<<p.second<<" which was sampled "<<p.first<<" times\n";
    pair<int, int> resFromPersistent = query(roots[a-1], roots[b], p.second, 0, M-1);
    // cout << resFromPersistent.first << " " << resFromPersistent.second << "\n";
    if (resFromPersistent.first > (b-a+1)/2) {
      return void(cout << rev[resFromPersistent.second] << "\n");
    }
  }

  cout << "-1\n";
}

int main() {
  ios_base::sync_with_stdio(0); cin.tie(0);
  cin>>n>>q;
  

  roots[0] = new Node(0);

  unordered_map<int, int> z;

  for (int i = 1; i <= n; i++) {
    int x; cin>>x;
    arr[i] = x;
    z[arr[i]] = 1;
  }

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

  for (int i = 1; i <= n; i++) {
    arr[i] = z[arr[i]];
  }
  
  for (int i = 1; i <= n; i++) {
    roots[i] = update(roots[i-1], arr[i], 0, M-1);
  }

  for (int i = 0; i < q; i++) {
    int a, b; cin>>a>>b;
    solveRange(a, b);
  }
}

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

Test 9

Group: 4

Verdict: WRONG ANSWER

Test 10

Group: 4

Verdict: TIME LIMIT EXCEEDED

Test 11

Group: 3, 4

Verdict: WRONG ANSWER

Test 12

Group: 4

Verdict: WRONG ANSWER

Test 13

Group: 3, 4

Verdict: WRONG ANSWER

Test 14

Group: 4

Verdict: ACCEPTED

Test 15

Group: 4

Verdict: ACCEPTED

Test 16

Group: 4

Verdict: WRONG ANSWER