Kyselyt

input/code.cpp: In function 'void solveRange(int, int, PersistentSegtree&)':
input/code.cpp:108:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |     if (i == freq.size()) return void(cout << "-1\n");
      |         ~~^~~~~~~~~~~~~~

#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];
map<int, int> rev;

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 {
    ll 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++;
  }

  ll range_sum(int v, int ql, int qr, int tl, int tr) {
    if (qr < tl || tr < ql) { return 0ll; }
    if (ql <= tl && tr <= qr) { return tree[v].sum; }
    int mid = (tl + tr) / 2;
    return range_sum(tree[v].l, ql, qr, tl, mid) + range_sum(tree[v].r, ql, qr, 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); }
  ll range_sum(int root, int l, int r) { return range_sum(root, l, r, 0, n - 1); }
  int add_copy(int root) {
    tree[timer] = tree[root];
    return timer++;
  }
};

int roots[N];

void solveRange(int a, int b, PersistentSegtree& seg) {
  // find 3 best candidates between [a..b] that could be dominant
  // max iter? maybe 50-100 or something
  int max_iter = 20;
  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";
    int val = p.second;
    int cnt = seg.range_sum(roots[b], val, val) - seg.range_sum(roots[a-1], val, 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, 36 * 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: 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: ACCEPTED

Test 10

Group: 4

Verdict: TIME LIMIT EXCEEDED

Test 11

Group: 3, 4

Verdict: WRONG ANSWER

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