oj.uz

Submission #402572

# Submission time Handle Problem Language Result Execution time Memory
402572 2021-05-12T00:56:53 Z Talha_Taki Index (COCI21_index) C++17
110 / 110
 1244 ms 137276 KB 
#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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 13388 KB Output is correct
2 Correct 19 ms 13440 KB Output is correct
3 Correct 19 ms 13348 KB Output is correct
4 Correct 19 ms 13420 KB Output is correct
5 Correct 25 ms 13456 KB Output is correct
6 Correct 19 ms 13444 KB Output is correct
7 Correct 19 ms 13412 KB Output is correct
8 Correct 19 ms 13416 KB Output is correct
9 Correct 19 ms 13388 KB Output is correct
10 Correct 20 ms 13408 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 13388 KB Output is correct
2 Correct 19 ms 13440 KB Output is correct
3 Correct 19 ms 13348 KB Output is correct
4 Correct 19 ms 13420 KB Output is correct
5 Correct 25 ms 13456 KB Output is correct
6 Correct 19 ms 13444 KB Output is correct
7 Correct 19 ms 13412 KB Output is correct
8 Correct 19 ms 13416 KB Output is correct
9 Correct 19 ms 13388 KB Output is correct
10 Correct 20 ms 13408 KB Output is correct
11 Correct 196 ms 43760 KB Output is correct
12 Correct 202 ms 43764 KB Output is correct
13 Correct 206 ms 43804 KB Output is correct
14 Correct 206 ms 43788 KB Output is correct
15 Correct 206 ms 43800 KB Output is correct
16 Correct 203 ms 43716 KB Output is correct
17 Correct 197 ms 43700 KB Output is correct
18 Correct 200 ms 43716 KB Output is correct
19 Correct 215 ms 43724 KB Output is correct
20 Correct 203 ms 43724 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 13388 KB Output is correct
2 Correct 19 ms 13440 KB Output is correct
3 Correct 19 ms 13348 KB Output is correct
4 Correct 19 ms 13420 KB Output is correct
5 Correct 25 ms 13456 KB Output is correct
6 Correct 19 ms 13444 KB Output is correct
7 Correct 19 ms 13412 KB Output is correct
8 Correct 19 ms 13416 KB Output is correct
9 Correct 19 ms 13388 KB Output is correct
10 Correct 20 ms 13408 KB Output is correct
11 Correct 196 ms 43760 KB Output is correct
12 Correct 202 ms 43764 KB Output is correct
13 Correct 206 ms 43804 KB Output is correct
14 Correct 206 ms 43788 KB Output is correct
15 Correct 206 ms 43800 KB Output is correct
16 Correct 203 ms 43716 KB Output is correct
17 Correct 197 ms 43700 KB Output is correct
18 Correct 200 ms 43716 KB Output is correct
19 Correct 215 ms 43724 KB Output is correct
20 Correct 203 ms 43724 KB Output is correct
21 Correct 1118 ms 137112 KB Output is correct
22 Correct 1150 ms 137068 KB Output is correct
23 Correct 1127 ms 137188 KB Output is correct
24 Correct 1244 ms 137116 KB Output is correct
25 Correct 1140 ms 137276 KB Output is correct
26 Correct 1181 ms 137108 KB Output is correct
27 Correct 1204 ms 137104 KB Output is correct
28 Correct 1131 ms 137020 KB Output is correct
29 Correct 1135 ms 137104 KB Output is correct
30 Correct 1191 ms 137240 KB Output is correct