답안 #706877

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
706877	2023-03-08T02:33:05 Z	nhuang685	원숭이와 사과 나무 (IZhO12_apple)	C++17	100 / 100	433 ms	248188 KB

apple

/**
 * @author nhuang685
 * @date 2023-03-05 19:26:54
 */
#include <bits/stdc++.h>

using namespace std;

using ll = long long;

template <class OP>
class LazySegmentTree {
 private:
  using T = typename decay<decltype(OP::ID)>::type;
  using st2 = int;

  st2 sz;
  struct Node {
    T val, ls = OP::ID2;
    // st2 ind;
    int l = -1, r = -1;
    Node() : val(OP::ID) {}
    Node(T _val) : val(_val) {}
  };
  vector<Node> data;

  void push(int ind, st2 l, st2 r) {
    assert(ind != -1);
    if (l != r) {
      if (data[ind].l == -1) {
        data.push_back(Node());
        data[ind].l = (int)data.size() - 1;
      }
      if (data[ind].r == -1) {
        data.push_back(Node());
        data[ind].r = (int)data.size() - 1;
      }
    }
    if (data[ind].ls == OP::ID2) return;
    data[ind].val = OP::all(l, r, data[ind].ls);
    if (l != r) {
      data[data[ind].l].ls = data[ind].ls;
      data[data[ind].r].ls = data[ind].ls;
    }
    data[ind].ls = OP::ID2;
  }
  void pull(int i) {
    data[i].val = OP::comb((data[i].l == -1) ? OP::ID : data[data[i].l].val,
                           (data[i].r == -1) ? OP::ID : data[data[i].r].val);
  }

  void modify(st2 a, st2 b, T v, int ind, st2 l, st2 r) {
    assert(ind != -1);
    push(ind, l, r);
    if (a <= l && r <= b) {
      data[ind].ls = v;
      push(ind, l, r);
      return;
    } else if (r < a || b < l)
      return;

    st2 mid = (l + r) / 2;
    modify(a, b, v, data[ind].l, l, mid);
    modify(a, b, v, data[ind].r, mid + 1, r);
    pull(ind);
  }
  T query(st2 a, st2 b, int ind, st2 l, st2 r) {
    assert(ind != -1);
    push(ind, l, r);
    if (a <= l && r <= b)
      return data[ind].val;
    else if (r < a || b < l)
      return OP::ID;

    st2 mid = (l + r) / 2;
    return OP::comb(query(a, b, data[ind].l, l, mid),
                    query(a, b, data[ind].r, mid + 1, r));
  }

 public:
  LazySegmentTree() {}
  LazySegmentTree(st2 _sz) {
    sz = 1;
    while (sz < _sz) sz *= 2;
    data.reserve(64 * 123456);
    data.push_back(Node());
  }
  LazySegmentTree(const vector<T> &arr) {
    sz = 1;
    while (sz < (st2)arr.size()) sz *= 2;

    auto build = [&](auto &self, st2 l, st2 r) -> int {
      if (l == r) {
        data.push_back(Node(arr[l]));
        return (int)data.size() - 1;
      }

      data.push_back(Node());
      int ind = (int)data.size() - 1;

      st2 mid = (l + r) / 2;
      auto tmp = self(self, l, mid);
      data[ind].l = tmp;
      if ((st2)arr.size() - 1 >= mid + 1) {
        tmp = self(self, mid + 1, r);
        data[ind].r = tmp;
      }
      pull(ind);
      return ind;
    };
    build(build, 0, sz - 1);
  }

  void set(st2 a, st2 b, T v) { modify(a, b, v, 0, 0, sz - 1); }
  void set(st2 i, T v) { modify(i, i, v, 0, 0, sz - 1); }
  T query(st2 a, st2 b) { return query(a, b, 0, 0, sz - 1); }
};
template <class T>
struct Add {
  static constexpr T ID = 0, ID2 = -1;  // change ID2 as needed
  static T comb(T a, T b) { return a + b; }
  template <class U>
  static T all([[maybe_unused]] U l, [[maybe_unused]] U r, T v) {
    return (r - l + 1) * v;
  }
};
template <class T>
using Seg = LazySegmentTree<Add<T>>;

int main() {
  ios::sync_with_stdio(false);

#ifdef LOCAL
  // freopen("input.txt", "r", stdin);
  freopen("output.txt", "w", stdout);
  freopen("log.txt", "w", stderr);
#else
  cin.tie(nullptr);
#endif

  Seg<int> seg((ll)1e9 + 1);

  int M;
  cin >> M;
  ll C = 0;
  while (M--) {
    int D;
    ll X, Y;
    cin >> D >> X >> Y;
    if (D == 1)
      cout << (C = seg.query(X + C, Y + C)) << '\n';
    else
      seg.set(X + C, Y + C, 1);
  }
}

Subtask #1

100.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	14 ms	3156 KB	Output is correct
5	Correct	18 ms	3796 KB	Output is correct
6	Correct	18 ms	3608 KB	Output is correct
7	Correct	17 ms	3720 KB	Output is correct
8	Correct	134 ms	26584 KB	Output is correct
9	Correct	268 ms	44148 KB	Output is correct
10	Correct	267 ms	50680 KB	Output is correct
11	Correct	300 ms	54960 KB	Output is correct
12	Correct	263 ms	56776 KB	Output is correct
13	Correct	243 ms	69644 KB	Output is correct
14	Correct	276 ms	70440 KB	Output is correct
15	Correct	404 ms	248100 KB	Output is correct
16	Correct	433 ms	248188 KB	Output is correct
17	Correct	248 ms	72788 KB	Output is correct
18	Correct	258 ms	72920 KB	Output is correct
19	Correct	413 ms	248092 KB	Output is correct
20	Correct	424 ms	248140 KB	Output is correct