Submission #1262920

#	Time	Username	Problem	Language	Result	Execution time	Memory
1262920		dnx04	Index (COCI21_index)	C++20	110 / 110	851 ms	43512 KiB

index

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

struct WaveletTree {
  int lo, hi;
  WaveletTree *L = nullptr, *R = nullptr;
  vector<int> leftCnt;

  template <class It>
  WaveletTree(It l, It r, int mn, int mx) : lo(mn), hi(mx) {
    if (lo == hi || l >= r) return;
    int mid = lo + (hi - lo) / 2;
    leftCnt.reserve(r - l + 1);
    leftCnt.push_back(0);
    for (auto it = l; it != r; ++it)
      leftCnt.push_back(leftCnt.back() + (*it <= mid));
    auto pivot = stable_partition(l, r, [&](int x) { return x <= mid; });
    L = new WaveletTree(l, pivot, lo, mid);
    R = new WaveletTree(pivot, r, mid + 1, hi);
  }

  inline pair<int, int> mapLeft(int l, int r) const {
    return {leftCnt[l - 1] + 1, leftCnt[r]};
  }
  inline pair<int, int> mapRight(int l, int r) const {
    return {(l - 1) - leftCnt[l - 1] + 1, r - leftCnt[r]};
  }

  int range(int l, int r, int x, int y) const {
    if (l > r || y < lo || x > hi) return 0;
    if (x <= lo && hi <= y) return r - l + 1;
    int res = 0;
    if (L) {
      auto [nl, nr] = mapLeft(l, r);
      res += L->range(nl, nr, x, y);
    }
    if (R) {
      auto [nl, nr] = mapRight(l, r);
      res += R->range(nl, nr, x, y);
    }
    return res;
  }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n, q;
  cin >> n >> q;
  vector<int> c(n);
  for (int &x : c) cin >> x;

  int mn = *min_element(c.begin(), c.end());
  int mx = *max_element(c.begin(), c.end());
  WaveletTree wt(c.begin(), c.end(), mn, mx);

  while (q--) {
    int l, r;
    cin >> l >> r;  // 1-based input in your example
    l--, r--;
    int len = r - l + 1;
    int low = 0, high = len, ans = 0;
    while (low <= high) {
      int mid = (low + high) / 2;
      // count of ≥ mid = len - count(≤ mid-1)
      int cnt = len - wt.range(l + 1, r + 1, mn, mid - 1);
      if (cnt >= mid) {
        ans = mid;
        low = mid + 1;
      } else
        high = mid - 1;
    }
    cout << ans << "\n";
  }
}

• Subtask 1: 20 / 20
• Subtask 2: 40 / 40
• Subtask 3: 50 / 50