oj.uz

Submission #682626

# Submission time Handle Problem Language Result Execution time Memory
682626 2023-01-16T15:53:29 Z vjudge1 Index (COCI21_index) C++17
110 / 110
 2273 ms 136432 KB 
#include <bits/stdc++.h>
// Sample problem: https://oj.uz/problem/view/COCI21_index?locale=en

using namespace std;

const int N = 2e5;

struct node {
  node *l;
  node *r;
  int sum;

  node() : sum(0) {
    l = nullptr;
    r = nullptr;
  }
} *roots[1 + N];

void build(node *root, int lx, int rx) {
  if (lx == rx) {
    return;
  }

  int mid = (lx + rx) / 2;

  root->l = new node;
  build(root->l, lx, mid);

  root->r = new node;
  build(root->r, mid + 1, rx);
}

void update(node *prevRoot, node *root, int lx, int rx, int pos, int val) {
  if (lx == rx) {
    root->sum = prevRoot->sum + val;
    return;
  }

  int mid = (lx + rx) / 2;

  if (pos <= mid) {
    root->l = new node;

    root->r = prevRoot->r;

    update(prevRoot->l, root->l, lx, mid, pos, val);
  } else {
    root->l = prevRoot->l;

    root->r = new node;

    update(prevRoot->r, root->r, mid + 1, rx, pos, val);
  }

  root->sum = root->l->sum + root->r->sum;
}

int query(node *root, int lx, int rx, int st, int dr) {
  if (st <= lx && rx <= dr) {
    return root->sum;
  }

  int mid = (lx + rx) / 2;

  int sum = 0;

  if (st <= mid) {
    sum += query(root->l, lx, mid, st, dr);
  }

  if (mid < dr) {
    sum += query(root->r, mid + 1, rx, st, dr);
  }

  return sum;
}

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

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

  roots[0] = new node;
  build(roots[0], 1, N);

  for (int i = 1; i <= n; ++i) {
    int x;
    cin >> x;

    roots[i] = new node;
    update(roots[i - 1], roots[i], 1, N, x, 1);
  }

  for (int i = 0; i < q; ++i) {
    int l, r;
    cin >> l >> r;

    int len = r - l + 1;

    int st = 2, dr = len, res = 1;

    while (st <= dr) {
      int mid = (st + dr) / 2;

      if (query(roots[r], 1, N, mid, N) - query(roots[l - 1], 1, N, mid, N) >= mid) {
        res = mid;
        st = mid + 1;
      } else {
        dr = mid - 1;
      }
    }

    cout << res << '\n';
  }

  return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 13356 KB Output is correct
2 Correct 18 ms 13440 KB Output is correct
3 Correct 17 ms 13424 KB Output is correct
4 Correct 17 ms 13396 KB Output is correct
5 Correct 16 ms 13396 KB Output is correct
6 Correct 17 ms 13456 KB Output is correct
7 Correct 17 ms 13396 KB Output is correct
8 Correct 17 ms 13396 KB Output is correct
9 Correct 20 ms 13396 KB Output is correct
10 Correct 18 ms 13428 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 13356 KB Output is correct
2 Correct 18 ms 13440 KB Output is correct
3 Correct 17 ms 13424 KB Output is correct
4 Correct 17 ms 13396 KB Output is correct
5 Correct 16 ms 13396 KB Output is correct
6 Correct 17 ms 13456 KB Output is correct
7 Correct 17 ms 13396 KB Output is correct
8 Correct 17 ms 13396 KB Output is correct
9 Correct 20 ms 13396 KB Output is correct
10 Correct 18 ms 13428 KB Output is correct
11 Correct 309 ms 42772 KB Output is correct
12 Correct 302 ms 42716 KB Output is correct
13 Correct 311 ms 42680 KB Output is correct
14 Correct 286 ms 42864 KB Output is correct
15 Correct 313 ms 42704 KB Output is correct
16 Correct 304 ms 42764 KB Output is correct
17 Correct 339 ms 42760 KB Output is correct
18 Correct 346 ms 42888 KB Output is correct
19 Correct 291 ms 42740 KB Output is correct
20 Correct 308 ms 42792 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 13356 KB Output is correct
2 Correct 18 ms 13440 KB Output is correct
3 Correct 17 ms 13424 KB Output is correct
4 Correct 17 ms 13396 KB Output is correct
5 Correct 16 ms 13396 KB Output is correct
6 Correct 17 ms 13456 KB Output is correct
7 Correct 17 ms 13396 KB Output is correct
8 Correct 17 ms 13396 KB Output is correct
9 Correct 20 ms 13396 KB Output is correct
10 Correct 18 ms 13428 KB Output is correct
11 Correct 309 ms 42772 KB Output is correct
12 Correct 302 ms 42716 KB Output is correct
13 Correct 311 ms 42680 KB Output is correct
14 Correct 286 ms 42864 KB Output is correct
15 Correct 313 ms 42704 KB Output is correct
16 Correct 304 ms 42764 KB Output is correct
17 Correct 339 ms 42760 KB Output is correct
18 Correct 346 ms 42888 KB Output is correct
19 Correct 291 ms 42740 KB Output is correct
20 Correct 308 ms 42792 KB Output is correct
21 Correct 2174 ms 132968 KB Output is correct
22 Correct 2080 ms 136320 KB Output is correct
23 Correct 2041 ms 136376 KB Output is correct
24 Correct 2273 ms 136432 KB Output is correct
25 Correct 2170 ms 136316 KB Output is correct
26 Correct 2209 ms 136280 KB Output is correct
27 Correct 2000 ms 136300 KB Output is correct
28 Correct 2143 ms 136336 KB Output is correct
29 Correct 2182 ms 136308 KB Output is correct
30 Correct 2207 ms 136276 KB Output is correct