Submission #923212

#	Time	Username	Problem	Language	Result	Execution time	Memory
923212		myst6	Growing Trees (BOI11_grow)	C++17	100 / 100	236 ms	9984 KiB

grow

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

struct Tag {
  ll add;
  Tag(ll _add) : add(_add) {}
  Tag() : add(0) {}
  void apply(Tag &tag) { add += tag.add; }
};

struct Info {
  ll m;
  Info(ll _m) : m(_m) {}
  Info() : m(0) {}
  void apply(Tag &tag) { m += tag.add; }
  Info combine(Info &other) { return {max(m, other.m)}; }
};

struct Tree {
  vector<Tag> tag;
  vector<Info> info;
  Tree(int size) {
    tag.resize(size*4);
    info.resize(size*4);
  }
  void build(vector<Info> &base, int x, int xl, int xr) {
    if (xl == xr) {
      info[x] = base[xl];
    } else {
      int xm = (xl + xr) / 2;
      build(base, x*2, xl, xm);
      build(base, x*2+1, xm+1, xr);
      info[x] = info[x*2].combine(info[x*2+1]);
    }
  }
  void pushdown(int x) {
    info[x].apply(tag[x]);
    if (x*2 < tag.size()) tag[x*2].apply(tag[x]);
    if (x*2+1 < tag.size()) tag[x*2+1].apply(tag[x]);
    tag[x] = {};
  }
  void update(int l, int r, int x, int xl, int xr, Tag delta) {
    if (l > r) return;
    if (l == xl && r == xr) {
      tag[x].apply(delta);
    } else {
      int xm = (xl + xr) / 2;
      update(l, min(r, xm), x*2, xl, xm, delta);
      update(max(l, xm+1), r, x*2+1, xm+1, xr, delta);
      pushdown(x); pushdown(x*2); pushdown(x*2+1);
      info[x] = info[x*2].combine(info[x*2+1]);
    }
  }
  Info query(int l, int r, int x, int xl, int xr) {
    if (l > r) return {};
    pushdown(x);
    if (l == xl && r == xr) {
      return info[x];
    } else {
      int xm = (xl + xr) / 2;
      Info left = query(l, min(r, xm), x*2, xl, xm);
      Info right = query(max(l, xm+1), r, x*2+1, xm+1, xr);
      return left.combine(right);
    }
  }
  int find_first(function<bool(Info&)> pred, int x, int xl, int xr) {
    pushdown(x);
    if (xl == xr) {
      if (pred(info[x])) return xl;
      else return -1;
    } else {
      int xm = (xl + xr) / 2;
      pushdown(x*2);
      if (pred(info[x*2])) return find_first(pred, x*2, xl, xm);
      else return find_first(pred, x*2+1, xm+1, xr);
    }
  }
};

int main() {
  cin.tie(0)->sync_with_stdio(0);
  int N, M;
  cin >> N >> M;
  vector<ll> H(N);
  for (int i=0; i<N; i++) cin >> H[i];
  sort(H.begin(), H.end());
  vector<Info> base(N);
  for (int i=0; i<N; i++) base[i] = {H[i]};
  Tree tree(N);
  tree.build(base, 1, 0, N-1);
  function<int(ll)> lower_bound = [&](ll val) {
    int idx = tree.find_first([&](Info &info) -> bool {
      return info.m >= val;
    }, 1, 0, N-1);
    if (idx == -1) return N;
    else return idx;
  };
  for (int i=0; i<M; i++) {
    char t;
    cin >> t;
    if (t == 'F') {
      int c; ll h;
      cin >> c >> h;
      int l = lower_bound(h);
      if (l == N) continue;
      int r = min(N-1, l+c-1);
      ll v = tree.query(r, r, 1, 0, N-1).m;
      int vl = lower_bound(v);
      int vr = lower_bound(v+1)-1;
      int vc = (r-vl+1);
      int l2 = vr-vc+1;
      tree.update(l, vl-1, 1, 0, N-1, {+1});
      tree.update(l2, vr, 1, 0, N-1, {+1});
    } else {
      ll lo, hi;
      cin >> lo >> hi;
      int loL = lower_bound(lo);
      int hiR = lower_bound(hi+1)-1;
      cout << hiR-loL+1 << "\n";
    }
  }
  return 0;
}

Compilation message (stderr)

grow.cpp: In member function 'void Tree::pushdown(int)':
grow.cpp:40:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Tag>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |     if (x*2 < tag.size()) tag[x*2].apply(tag[x]);
      |         ~~~~^~~~~~~~~~~~
grow.cpp:41:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Tag>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |     if (x*2+1 < tag.size()) tag[x*2+1].apply(tag[x]);
      |         ~~~~~~^~~~~~~~~~~~

• 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