Kyselyt

#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], rev[N];
 
int n, q;
 
// index version of persistent taken from usaco guide, because my pointer based is too slow
// https://usaco.guide/adv/persistent
class PersistentSegtree {
  private:
  struct Node {
    int sum = 0;
    int l = 0, r = 0;
  };
 
  const int n;
  vector<Node> tree;
  int timer = 1;
  
  Node join(int l, int r) { return Node{tree[l].sum + tree[r].sum, l, r}; }
  
  int build(int tl, int tr) {
    if (tl == tr) {
      tree[timer] = {0, 0, 0};
      return timer++;
    }
    
    int mid = (tl + tr) / 2;
    tree[timer] = join(build(tl, mid), build(mid + 1, tr));
    
    return timer++;
  }
  
  int set(int v, int pos, int val, int tl, int tr) {
    if (tl == tr) {
      tree[timer] = {tree[v].sum + val, 0, 0};
      return timer++;
    }
    int mid = (tl + tr) / 2;
    if (pos <= mid) {
      tree[timer] = join(set(tree[v].l, pos, val, tl, mid), tree[v].r);
    } else {
      tree[timer] = join(tree[v].l, set(tree[v].r, pos, val, mid + 1, tr));
    }
    return timer++;
  }
 
  int pointsum(int v, int v2, int pos, int tl, int tr) {
    if (tl == tr) return tree[v2].sum - tree[v].sum;
    int mid = (tl + tr) / 2;
    if (pos <= mid) return pointsum(tree[v].l, tree[v2].l, pos, tl, mid);
    else return pointsum(tree[v].r, tree[v2].r, pos, mid+1, tr);
  }
 
  public:
  PersistentSegtree(int n, int MX_NODES) : n(n), tree(MX_NODES) {}
  int build() { return build(0, n - 1); }
  int set(int root, int pos, int val) { return set(root, pos, val, 0, n - 1); }
  int pointsum(int root, int root2, int pos) { return pointsum(root, root2, pos, 0, n - 1); }
  int add_copy(int root) {
    tree[timer] = tree[root];
    return timer++;
  }
};
 
int roots[N];
int queryIndex = 0;
int usedInQuery[N];
int usedValueInQuery[N];
int valueCntInQuery[N];
 
void solveRange(int a, int b, PersistentSegtree& seg) {
  // find 2 best candidates between [a..b] that could be dominant
  // max iter? maybe 50-100 or something
  int max_iter = 20;
  queryIndex++;

  int best1 = -1, best2 = -1;
  int cnt1 = 0, cnt2 = 0;
 
  for (int i = 0; i < max_iter; i++) {
    int idxbetween = a + (int)(gen() % (b-a+1));
    if (usedInQuery[idxbetween] == queryIndex) continue;
    usedInQuery[idxbetween] = queryIndex;
    int x = arr[idxbetween];

    if (usedValueInQuery[x] != queryIndex) {
      usedValueInQuery[x] = queryIndex;
      valueCntInQuery[x] = 0;
    }
    valueCntInQuery[x]++;

    if (best1 == -1 || valueCntInQuery[x] > cnt1) {
      best2 = best1;
      cnt2 = cnt1;
      best1 = x;
      cnt1 = valueCntInQuery[x];
    } else if (x != best1 && (best2 == -1 || valueCntInQuery[x] > cnt2)) {
      best2 = x;
      cnt2 = valueCntInQuery[x];
    }
  }
 
  // try 2 best
  for (int i = 0; i < 2; i++) {
    int val = (i == 0) ? best1 : best2;
    if (val == -1) continue;
    int cnt = seg.pointsum(roots[a-1], roots[b], val);
    // cout << resFromPersistent.first << " " << resFromPersistent.second << "\n";
    if (cnt > (b-a+1)/2) {
      return void(cout << rev[val] << "\n");
    }
  }
 
  cout << "-1\n";
}
 
int main() {
  ios_base::sync_with_stdio(0); cin.tie(0);
  cin>>n>>q;
 
  PersistentSegtree seg(n, 33 * n);
 
  roots[0] = seg.build();
 
  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] = seg.set(roots[i-1], arr[i], 1);
  }
 
  for (int i = 0; i < q; i++) {
    int a, b; cin>>a>>b;
    solveRange(a, b, seg);
  }
}

Test 1

Group: 1, 2, 3, 4

Verdict: ACCEPTED

Test 2

Group: 1, 2, 3, 4

Verdict: WRONG ANSWER

Test 3

Group: 1, 3, 4

Verdict: ACCEPTED

Test 4

Group: 2, 3, 4

Verdict: ACCEPTED

Test 5

Group: 2, 3, 4

Verdict: WRONG ANSWER

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

Test 12

Group: 4

Verdict: WRONG ANSWER

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