oj.uz

Submission #923212

# Submission time Handle Problem Language Result Execution time Memory
923212 2024-02-06T21:00:32 Z myst6 Growing Trees (BOI11_grow) C++17
100 / 100
 236 ms 9984 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 7492 KB Output is correct
2 Correct 148 ms 9080 KB Output is correct
3 Correct 172 ms 8396 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 2 ms 472 KB Output is correct
3 Correct 2 ms 600 KB Output is correct
4 Correct 2 ms 604 KB Output is correct
5 Correct 55 ms 1840 KB Output is correct
6 Correct 68 ms 2128 KB Output is correct
7 Correct 6 ms 856 KB Output is correct
8 Correct 46 ms 1424 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 1328 KB Output is correct
2 Correct 68 ms 2376 KB Output is correct
3 Correct 2 ms 856 KB Output is correct
4 Correct 53 ms 1924 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 1280 KB Output is correct
2 Correct 72 ms 2188 KB Output is correct
3 Correct 11 ms 1112 KB Output is correct
4 Correct 74 ms 2360 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 5664 KB Output is correct
2 Correct 137 ms 7712 KB Output is correct
3 Correct 18 ms 2124 KB Output is correct
4 Correct 126 ms 7312 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 7212 KB Output is correct
2 Correct 133 ms 7904 KB Output is correct
3 Correct 152 ms 7456 KB Output is correct
4 Correct 18 ms 2140 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 6804 KB Output is correct
2 Correct 96 ms 8496 KB Output is correct
3 Correct 157 ms 8424 KB Output is correct
4 Correct 18 ms 2208 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 7236 KB Output is correct
2 Correct 144 ms 7736 KB Output is correct
3 Correct 33 ms 9008 KB Output is correct
4 Correct 106 ms 8440 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 7472 KB Output is correct
2 Correct 131 ms 8764 KB Output is correct
3 Correct 236 ms 9984 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 8608 KB Output is correct