Submission #800445

#	Time	Username	Problem	Language	Result	Execution time	Memory
800445		tch1cherin	Growing Trees (BOI11_grow)	C++17	100 / 100	97 ms	5068 KiB

grow

#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 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10