답안 #869302

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
869302	2023-11-04T01:54:40 Z	nima_aryan	원숭이와 사과 나무 (IZhO12_apple)	C++17	100 / 100	251 ms	182540 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;
  int n;

  struct Node {
    int left = -1, right = -1;
  };
  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;
    }
  }

  SparseLazySegmentTree(int n, int q) : n(n) {
    int m = 4 * __lg(n) * q;
    info.resize(m), tag.resize(m);
    nodes.resize(m);
  }

  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 = 1E7;

  int M;
  cin >> M;
  SparseLazySegmentTree<Info, Tag> seg(N + 1, 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;
}

Compilation message

apple.cpp: In function 'int main()':
apple.cpp:139:26: warning: unused variable 'A' [-Wunused-variable]
  139 |   constexpr int N = 1E9, A = 1E7;
      |                          ^

Subtask #1

100.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	1 ms	604 KB	Output is correct
4	Correct	13 ms	14792 KB	Output is correct
5	Correct	16 ms	18568 KB	Output is correct
6	Correct	16 ms	18524 KB	Output is correct
7	Correct	15 ms	18520 KB	Output is correct
8	Correct	91 ms	91588 KB	Output is correct
9	Correct	221 ms	182340 KB	Output is correct
10	Correct	197 ms	182356 KB	Output is correct
11	Correct	211 ms	182256 KB	Output is correct
12	Correct	208 ms	182392 KB	Output is correct
13	Correct	180 ms	182356 KB	Output is correct
14	Correct	178 ms	182344 KB	Output is correct
15	Correct	238 ms	182360 KB	Output is correct
16	Correct	240 ms	182360 KB	Output is correct
17	Correct	177 ms	182356 KB	Output is correct
18	Correct	180 ms	182356 KB	Output is correct
19	Correct	244 ms	182356 KB	Output is correct
20	Correct	251 ms	182540 KB	Output is correct