Submission #1046958

#	Time	Username	Problem	Language	Result	Execution time	Memory
1046958		vjudge1	Index (COCI21_index)	C++17	110 / 110	1937 ms	36352 KiB

index

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

#define all(a) a.begin(), a.end()

struct segtr {
  vector<vector<int>> tree;
  int n;
  segtr(vector<int> const &a)
      : n(a.size()), tree(a.size() << 1, vector<int>()) {
    for (int i = 0; i < n; i++)
      tree[i + n].push_back(a[i]);
    for (int i = n - 1; i > 0; i--) {
      merge(all(tree[i << 1]), all(tree[i << 1 | 1]), back_inserter(tree[i]));
    }
  }
  int query(int l, int r, int h) {
    int res = 0;
    for (l += n, r += n + 1; l < r; l >>= 1, r >>= 1) {
      if (l & 1) {
        res += tree[l].end() - lower_bound(all(tree[l]), h);
        l++;
      }
      if (r & 1) {
        r--;
        res += tree[r].end() - lower_bound(all(tree[r]), h);
      }
    }
    return res;
  }
  int query(int l, int r) {
    int ll = 0, rr = r - l + 1;
    int ans = INT_MIN;
    while (rr - ll >= 0) {
      int m = (rr + ll) >> 1;
      if (query(l, r, m) >= m) {
        ans = max(ans, m);
        ll = m + 1;
      } else
        rr = m - 1;
    }
    return ans;
  }
};

int main() {
  cin.tie(0)->sync_with_stdio(0);
  int n, q;
  cin >> n >> q;
  vector<int> a(n);
  for (auto &x : a)
    cin >> x;
  segtr tr(a);
  while (q--) {
    int l, r;
    cin >> l >> r;
    l--;
    r--;
    cout << tr.query(l, r) << '\n';
  }
}

Compilation message (stderr)

index.cpp: In constructor 'segtr::segtr(const std::vector<int>&)':
index.cpp:8:7: warning: 'segtr::n' will be initialized after [-Wreorder]
    8 |   int n;
      |       ^
index.cpp:7:23: warning:   'std::vector<std::vector<int> > segtr::tree' [-Wreorder]
    7 |   vector<vector<int>> tree;
      |                       ^~~~
index.cpp:9:3: warning:   when initialized here [-Wreorder]
    9 |   segtr(vector<int> const &a)
      |   ^~~~~

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