oj.uz

Submission #850928

# Submission time Handle Problem Language Result Execution time Memory
850928 2023-09-17T19:54:55 Z tvladm2009 Growing Trees (BOI11_grow) C++17
100 / 100
 229 ms 5204 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
const int N = (int) 1e5 + 7;
const int INF = (int) 2e9;
int a[N], tree[4 * N], lazy[4 * N];
int n, q;
 
int main() {
  ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
 
/// freopen("input.txt", "r", stdin);
 
  cin >> n >> q;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  sort(a + 1, a + n + 1);
  a[n + 1] = INF;
  n++;
  function<void(int, int, int)> build = [&](int v, int tl, int tr) {
    if (tl == tr) {
      tree[v] = a[tl];
      return;
    }
    int tm = (tl + tr) / 2;
    build(2 * v, tl, tm);
    build(2 * v + 1, tm + 1, tr);
    tree[v] = max(tree[2 * v], tree[2 * v + 1]);
  };
  build(1, 1, n);
  function<void(int, int, int)> push = [&](int v, int tl, int tr) {
    if (tl < tr) {
      lazy[2 * v] += lazy[v];
      lazy[2 * v + 1] += lazy[v];
    }
    tree[v] += lazy[v];
    lazy[v] = 0;
  };
  function<void(int, int, int, int, int)> apply = [&](int v, int tl, int tr, int l, int r) {
    push(v, tl, tr);
    if (l <= tl && tr <= r) {
      lazy[v]++;
      push(v, tl, tr);
      return;
    }
    int tm = (tl + tr) / 2;
    if (l <= tm) {
      apply(2 * v, tl, tm, l, min(tm, r));
    }
    if (tm + 1 <= r) {
      apply(2 * v + 1, tm + 1, tr, max(l, tm + 1), r);
    }
    push(2 * v, tl, tm);
    push(2 * v + 1, tm + 1, tr);
    tree[v] = max(tree[2 * v], tree[2 * v + 1]);
  };
  function<int(int, int, int, int)> smaller = [&](int v, int tl, int tr, int val) {
    if (tl == tr) {
      return tl;
    }
    int tm = (tl + tr) / 2;
    push(2 * v, tl, tm);
    push(2 * v + 1, tm + 1, tr);
    if (tree[2 * v] >= val) {
      return smaller(2 * v, tl, tm, val);
    }
    return smaller(2 * v + 1, tm + 1, tr, val);
  };
  function<int(int, int, int, int)> bigger = [&](int v, int tl, int tr, int val) {
    if (tl == tr) {
      return tl;
    }
    int tm = (tl + tr) / 2;
    push(2 * v, tl, tm);
    push(2 * v + 1, tm + 1, tr);
    if (tree[2 * v] > val) {
      return bigger(2 * v, tl, tm, val);
    }
    return bigger(2 * v + 1, tm + 1, tr, val);
  };
  function<int(int, int, int, int)> get_val = [&](int v, int tl, int tr, int pos) {
    push(v, tl, tr);
    if (tl == tr) {
      return tree[v];
    }
    int tm = (tl + tr) / 2;
    if (pos <= tm) {
      return get_val(2 * v, tl, tm, pos);
    }
    return get_val(2 * v + 1, tm + 1, tr, pos);
  };
  for (int iq = 1; iq <= q; iq++) {
    char type;
    int x, y;
    cin >> type >> x >> y;
    if (type == 'F') {
      int first = smaller(1, 1, n, y);
      if (first == n) {
        continue;
      }
      int last = first + x - 1;
      if (last >= n) {
        apply(1, 1, n, first, n - 1);
        continue;
      }
      int val = get_val(1, 1, n, last);
      int last_to_update = smaller(1, 1, n, val) - 1;
      if (first <= last_to_update) {
        apply(1, 1, n, first, last_to_update);
      }
      int rem = last - last_to_update;
      if (rem == 0) {
        continue;
      }
      last_to_update = bigger(1, 1, n, val) - 1;
      apply(1, 1, n, last_to_update - rem + 1, last_to_update);
    } else {
      cout << bigger(1, 1, n, y) - smaller(1, 1, n, x) << "\n";
    }
  }
  return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 4180 KB Output is correct
2 Correct 149 ms 4948 KB Output is correct
3 Correct 154 ms 5000 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 2 ms 2396 KB Output is correct
3 Correct 3 ms 2396 KB Output is correct
4 Correct 2 ms 2396 KB Output is correct
5 Correct 51 ms 3416 KB Output is correct
6 Correct 65 ms 3864 KB Output is correct
7 Correct 6 ms 2648 KB Output is correct
8 Correct 44 ms 3412 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 3444 KB Output is correct
2 Correct 63 ms 3924 KB Output is correct
3 Correct 2 ms 2392 KB Output is correct
4 Correct 44 ms 3420 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 3932 KB Output is correct
2 Correct 67 ms 3812 KB Output is correct
3 Correct 13 ms 2648 KB Output is correct
4 Correct 62 ms 3876 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 3596 KB Output is correct
2 Correct 130 ms 4496 KB Output is correct
3 Correct 16 ms 3092 KB Output is correct
4 Correct 125 ms 4652 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 3924 KB Output is correct
2 Correct 135 ms 4672 KB Output is correct
3 Correct 155 ms 4828 KB Output is correct
4 Correct 16 ms 3160 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 4176 KB Output is correct
2 Correct 98 ms 4636 KB Output is correct
3 Correct 163 ms 4880 KB Output is correct
4 Correct 15 ms 3164 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 3416 KB Output is correct
2 Correct 152 ms 4664 KB Output is correct
3 Correct 29 ms 3932 KB Output is correct
4 Correct 104 ms 4436 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 4432 KB Output is correct
2 Correct 141 ms 5200 KB Output is correct
3 Correct 229 ms 5204 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 3924 KB Output is correct