oj.uz

Submission #682627

# Submission time Handle Problem Language Result Execution time Memory
682627 2023-01-16T15:55:24 Z vjudge1 Index (COCI21_index) C++17
110 / 110
 2141 ms 132872 KB 
#include <bits/stdc++.h>

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 st = 2, dr = r - l + 1, 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 16 ms 13412 KB Output is correct
2 Correct 17 ms 13452 KB Output is correct
3 Correct 17 ms 13348 KB Output is correct
4 Correct 18 ms 13420 KB Output is correct
5 Correct 17 ms 13376 KB Output is correct
6 Correct 17 ms 13332 KB Output is correct
7 Correct 18 ms 13396 KB Output is correct
8 Correct 17 ms 13396 KB Output is correct
9 Correct 18 ms 13404 KB Output is correct
10 Correct 19 ms 13368 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 13412 KB Output is correct
2 Correct 17 ms 13452 KB Output is correct
3 Correct 17 ms 13348 KB Output is correct
4 Correct 18 ms 13420 KB Output is correct
5 Correct 17 ms 13376 KB Output is correct
6 Correct 17 ms 13332 KB Output is correct
7 Correct 18 ms 13396 KB Output is correct
8 Correct 17 ms 13396 KB Output is correct
9 Correct 18 ms 13404 KB Output is correct
10 Correct 19 ms 13368 KB Output is correct
11 Correct 328 ms 42748 KB Output is correct
12 Correct 313 ms 42776 KB Output is correct
13 Correct 316 ms 42732 KB Output is correct
14 Correct 307 ms 42756 KB Output is correct
15 Correct 319 ms 42912 KB Output is correct
16 Correct 289 ms 42696 KB Output is correct
17 Correct 301 ms 42668 KB Output is correct
18 Correct 307 ms 42736 KB Output is correct
19 Correct 291 ms 42684 KB Output is correct
20 Correct 294 ms 42812 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 13412 KB Output is correct
2 Correct 17 ms 13452 KB Output is correct
3 Correct 17 ms 13348 KB Output is correct
4 Correct 18 ms 13420 KB Output is correct
5 Correct 17 ms 13376 KB Output is correct
6 Correct 17 ms 13332 KB Output is correct
7 Correct 18 ms 13396 KB Output is correct
8 Correct 17 ms 13396 KB Output is correct
9 Correct 18 ms 13404 KB Output is correct
10 Correct 19 ms 13368 KB Output is correct
11 Correct 328 ms 42748 KB Output is correct
12 Correct 313 ms 42776 KB Output is correct
13 Correct 316 ms 42732 KB Output is correct
14 Correct 307 ms 42756 KB Output is correct
15 Correct 319 ms 42912 KB Output is correct
16 Correct 289 ms 42696 KB Output is correct
17 Correct 301 ms 42668 KB Output is correct
18 Correct 307 ms 42736 KB Output is correct
19 Correct 291 ms 42684 KB Output is correct
20 Correct 294 ms 42812 KB Output is correct
21 Correct 2087 ms 132640 KB Output is correct
22 Correct 2117 ms 132688 KB Output is correct
23 Correct 1994 ms 132588 KB Output is correct
24 Correct 2103 ms 132752 KB Output is correct
25 Correct 2105 ms 132872 KB Output is correct
26 Correct 2141 ms 132604 KB Output is correct
27 Correct 2051 ms 132732 KB Output is correct
28 Correct 2005 ms 132716 KB Output is correct
29 Correct 1961 ms 132680 KB Output is correct
30 Correct 2081 ms 132660 KB Output is correct