Submission #402572

#	Time	Username	Problem	Language	Result	Execution time	Memory
402572		Talha_Taki	Index (COCI21_index)	C++17	110 / 110	1244 ms	137276 KiB

index

#include <bits/stdc++.h>

using namespace std;


const int MAXN = 2e5;

struct Vertex {
  Vertex *l, *r;
  int cnt;

  Vertex(int val) : l(nullptr), r(nullptr), cnt(val) {}
  Vertex(Vertex* l, Vertex* r) : l(l), r(r), cnt(0) {
    if (l) cnt += l->cnt;
    if (r) cnt += r->cnt;
  }
};

struct persistenSegmentTree {

  Vertex* build(int l, int r) {
    if (l == r) return new Vertex(0);

    int mid = (l+r)>>1;
    return new Vertex(build(l, mid), build(mid+1, r));
  }

  Vertex* update(Vertex* v, int l, int r, const int val) {
    if (l == r) return new Vertex(v->cnt+1);

    int mid = (l+r)>>1;
    if (val <= mid) return new Vertex(update(v->l, l, mid, val), v->r);
    return new Vertex(v->l, update(v->r, mid+1, r, val));
  }

  int query(Vertex* v1, Vertex* v2, int l, int r, const int k) {
    if (l == r) return (k <= l? v2->cnt - v1->cnt:0);

    int mid = (l+r)>>1;
    if (k <= mid) return (v2->r->cnt - v1->r->cnt) + query(v1->l, v2->l, l, mid, k);
    return query(v1->r, v2->r, mid+1, r, k);
  }
};


int main(int argc, const char* argv[]) {

  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  int n, q;
  cin >> n >> q;

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

  persistenSegmentTree tree;
  vector <Vertex*> version(n+1);

  version[0] = tree.build(1, MAXN);

  for(int i = 1; i <= n; ++i) {
    version[i] = tree.update(version[i-1], 1, MAXN, arr[i]);
  }

  while (q--) {
    int left, right;
    cin >> left >> right;

    int l = 1, r = MAXN;
    int best = 0;

    while (l <= r) {
      int mid = (l+r)>>1;

      int cnt = tree.query(version[left-1], version[right], 1, MAXN, mid);
      if (cnt >= mid) {
        best = mid;
        l = mid+1;
      }
      else r = mid-1;
    }

    cout << best << '\n';
  }

  arr.clear();


  return 0;
}

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