oj.uz

Submission #800445

# Submission time Handle Problem Language Result Execution time Memory
800445 2023-08-01T15:01:03 Z tch1cherin Growing Trees (BOI11_grow) C++17
100 / 100
 97 ms 5068 KB 
#include <bits/stdc++.h>
using namespace std;

struct segment_tree {
  struct node {
    int max_value;
    int tag;
  };

  node merge(node a, node b) {
    return {max(a.max_value, b.max_value), 0};
  }

  int size;
  int N;
  vector<node> tree;

  segment_tree(vector<int> H) {
    N = (int)H.size();
    size = 2 << __lg(N);
    tree.assign(2 * size, {0, 0});
    for (int i = 0; i < N; i++) {
      tree[size + i] = {H[i], 0}; 
    }
    for (int i = size - 1; i > 0; i--) {
      tree[i] = merge(tree[i * 2], tree[i * 2 + 1]);
    }
  }

  void apply(int x, int value) {
    tree[x].max_value += value;
    tree[x].tag += value;  
  }

  void propagate(int x) {
    apply(x * 2, tree[x].tag);
    apply(x * 2 + 1, tree[x].tag);
    tree[x].tag = 0;
  }

  void update(int l, int r, int value) {
    update(l, r, value, 1, 0, size);
  }

  void update(int l, int r, int value, int x, int lx, int rx) {
    if (lx >= r || rx <= l) {
      return;
    } else if (lx >= l && rx <= r) {
      apply(x, value);
    } else {
      propagate(x);
      int mid = (lx + rx) / 2;
      update(l, r, value, x * 2, lx, mid);
      update(l, r, value, x * 2 + 1, mid, rx);
      tree[x] = merge(tree[x * 2], tree[x * 2 + 1]);
    }
  }

  int lower_bound(int value) {
    return lower_bound(value, 1, 0, size);
  }

  int lower_bound(int value, int x, int lx, int rx) {
    if (tree[x].max_value < value) {
      return N;
    } else if (rx - lx == 1) {
      return x - size;
    } else {
      propagate(x);
      int mid = (lx + rx) / 2;
      if (tree[x * 2].max_value >= value) {
        return lower_bound(value, x * 2, lx, mid); 
      } else {
        return lower_bound(value, x * 2 + 1, mid, rx);
      }
    }
  }

  int get(int i) {
    return get(i, 1, 0, size);
  }

  int get(int i, int x, int lx, int rx) {
    if (rx - lx == 1) {
      return tree[x].max_value;
    } else {
      propagate(x);
      int mid = (lx + rx) / 2;
      if (i < mid) {
        return get(i, x * 2, lx, mid);
      } else {
        return get(i, x * 2 + 1, mid, rx);
      }
    }
  }
};

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int N, M;
  cin >> N >> M;
  vector<int> H(N);
  for (int &v : H) {
    cin >> v;
  }
  sort(H.begin(), H.end());
  segment_tree tree(H);
  while (M--) {
    char type;
    cin >> type;
    if (type == 'F') {
      int c, h;
      cin >> c >> h;
      int start = tree.lower_bound(h);
      int end = start + c;
      int next_value = tree.get(end);
      if (end < N && tree.get(end - 1) == next_value) {
        int start_block = tree.lower_bound(next_value);
        int end_block = tree.lower_bound(next_value + 1);
        tree.update(start, start_block, +1);
        int num = end - start_block;
        tree.update(end_block - num, end_block, +1);
      } else {
        tree.update(start, end, +1);
      }
    } else {
      int l, r;
      cin >> l >> r;
      cout << tree.lower_bound(r + 1) - tree.lower_bound(l) << "\n";
    }
  }
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 4056 KB Output is correct
2 Correct 77 ms 4468 KB Output is correct
3 Correct 48 ms 4360 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 1 ms 388 KB Output is correct
5 Correct 30 ms 1500 KB Output is correct
6 Correct 33 ms 1728 KB Output is correct
7 Correct 4 ms 468 KB Output is correct
8 Correct 17 ms 1236 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 1712 KB Output is correct
2 Correct 34 ms 1888 KB Output is correct
3 Correct 1 ms 508 KB Output is correct
4 Correct 21 ms 1364 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 1976 KB Output is correct
2 Correct 35 ms 1796 KB Output is correct
3 Correct 6 ms 596 KB Output is correct
4 Correct 33 ms 1900 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 2696 KB Output is correct
2 Correct 84 ms 3988 KB Output is correct
3 Correct 10 ms 1364 KB Output is correct
4 Correct 45 ms 4040 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 3716 KB Output is correct
2 Correct 75 ms 4024 KB Output is correct
3 Correct 56 ms 4408 KB Output is correct
4 Correct 10 ms 1364 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 3844 KB Output is correct
2 Correct 54 ms 4012 KB Output is correct
3 Correct 57 ms 4392 KB Output is correct
4 Correct 10 ms 1364 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 4476 KB Output is correct
2 Correct 77 ms 3948 KB Output is correct
3 Correct 20 ms 3796 KB Output is correct
4 Correct 51 ms 3816 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 4152 KB Output is correct
2 Correct 69 ms 4356 KB Output is correct
3 Correct 97 ms 4532 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 5068 KB Output is correct