답안 #869299

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
869299	2023-11-04T01:50:34 Z	nima_aryan	원숭이와 사과 나무 (IZhO12_apple)	C++17	0 / 100	112 ms	64204 KB

apple

/**
 *    author:  NimaAryan
 *    created: 2023-11-04 02:46:41  
**/
#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "algo/debug.h"
#endif

using i64 = long long;

template <class Info, class Tag>
class SparseLazySegmentTree {
 public:
  vector<Info> info;
  vector<Tag> tag;

  struct Node {
    int left = -1, right = -1;

    void init() {
      left = ++num;
      right = ++num;
    }
  };
  vector<Node> nodes;
  
  int num = 0;
  void make_childs(int p) {
    if (nodes[p].left == -1) {
      nodes[p].left = ++num;
    }
    if (nodes[p].right == -1) {
      nodes[p].right = ++num;
    }
  }

  int n;

  SparseLazySegmentTree(int n, int alpha) : n(n) {
    info.resize(alpha), tag.resize(alpha);
    nodes.resize(alpha);
  }

  void pull(int p) {
    info[p] = info[nodes[p].left] + info[nodes[p].right];
  }
  void apply(int p, int l, int r, const Tag& v) {
    make_childs(p);
    info[p].apply(l, r, v);
    tag[p].apply(v);
  }
  void push(int p, int l, int r) {
    make_childs(p);
    int m = (l + r) / 2;
    apply(nodes[p].left, l, m, tag[p]);
    apply(nodes[p].right, m, r, tag[p]);
    tag[p] = Tag();
  }

  void modify(int p, int l, int r, int x, const Info& v) {
    make_childs(p);
    if (r - l == 1) {
      info[p] = v;
      return;
    }
    push(p, l, r);
    int m = (l + r) / 2;
    if (x < m) {
      modify(2 * p, l, m, x, v);
    } else {
      modify(2 * p + 1, m, r, x, v);
    }
    pull(p);
  }
  void modify(int x, const Info& v) {
    modify(0, 0, n, x, v);
  }

  void RangeApply(int p, int l, int r, int lx, int rx, const Tag& v) {
    make_childs(p);
    if (l >= rx || r <= lx) {
      return;
    }
    if (l >= lx && r <= rx) {
      apply(p, l, r, v);
      return;
    }
    push(p, l, r);
    int m = (l + r) / 2;
    RangeApply(nodes[p].left, l, m, lx, rx, v);
    RangeApply(nodes[p].right, m, r, lx, rx, v);
    pull(p);
  }
  void RangeApply(int lx, int rx, const Tag& v) {
    RangeApply(0, 0, n, lx, rx, v);
  }

  Info RangeQuery(int p, int l, int r, int lx, int rx) {
    make_childs(p);
    if (l >= rx || r <= lx) {
      return Info();
    }
    if (l >= lx && r <= rx) {
      return info[p];
    }
    push(p, l, r);
    int m = (l + r) / 2;
    return RangeQuery(nodes[p].left, l, m, lx, rx) +
           RangeQuery(nodes[p].right, m, r, lx, rx);
  }
  Info RangeQuery(int lx, int rx) {
    return RangeQuery(0, 0, n, lx, rx);
  }
};

struct Tag {
  int ripen = 0;

  void apply(const Tag& v) {
    ripen |= v.ripen;
  }
};
struct Info {
  int sum = 0;

  void apply(int l, int r, const Tag& v) {
    if (v.ripen) {
      sum = r - l;
    }
  }
};
Info operator+(const Info& a, const Info& b) {
  return Info{a.sum + b.sum};
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  constexpr int N = 1E9, A = 2E6;
  SparseLazySegmentTree<Info, Tag> seg(N + 1, A);

  int M;
  cin >> M;

  int C = 0;
  while (M--) {
    int D, X, Y;
    cin >> D >> X >> Y;
    X += C, Y += C;

    if (D == 1) {
      int res = seg.RangeQuery(X, Y + 1).sum;
      cout << (C = res) << "\n";
    } else {
      seg.RangeApply(X, Y + 1, Tag{1});
    }
  }

  return 0;
}

Subtask #1

0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	8 ms	31576 KB	Output is correct
2	Correct	7 ms	31580 KB	Output is correct
3	Correct	6 ms	31580 KB	Output is correct
4	Correct	16 ms	31816 KB	Output is correct
5	Correct	17 ms	31580 KB	Output is correct
6	Correct	18 ms	31580 KB	Output is correct
7	Correct	17 ms	31632 KB	Output is correct
8	Correct	87 ms	32316 KB	Output is correct
9	Runtime error	112 ms	64204 KB	Execution killed with signal 11
10	Halted	0 ms	0 KB	-