Submission #952332

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
952332	2024-03-23T14:31:04 Z	ind1v	Monkey and Apple-trees (IZhO12_apple)	C++11	100 / 100	165 ms	128336 KB

apple

#include <bits/stdc++.h>

using namespace std;

const int M = 1e5 + 5;
const int X = 1e9;

struct dynamic_segment_tree {
  struct node {
    int l, r, cnt;
    bool lz;
    
    node() : l(-1), r(-1), cnt(0), lz(false) {}
  } t[80 * M];
  int nd = 0, root;
  
  dynamic_segment_tree() {
    root = ++nd;
  }
  
  void create(int id) {
    if (t[id].l == -1) {
      t[id].l = ++nd;
    }
    if (t[id].r == -1) {
      t[id].r = ++nd;
    }
  }
  
  void push(int id, int tl, int tr) {
    int tm = (tl + tr) >> 1;
    t[t[id].l].cnt = tm - tl + 1;
    t[t[id].l].lz = t[id].lz;
    t[t[id].r].cnt = tr - tm;
    t[t[id].r].lz = t[id].lz;
  }
  
  int get(int id, int tl, int tr, int l, int r) {
    if (l <= tl && tr <= r) {
      return t[id].cnt;
    }
    create(id);
    if (t[id].lz) {
      push(id, tl, tr);
    }
    int tm = (tl + tr) >> 1;
    if (r <= tm) {
      return get(t[id].l, tl, tm, l, r);
    } else if (tm + 1 <= l) {
      return get(t[id].r, tm + 1, tr, l, r);
    } else {
      return get(t[id].l, tl, tm, l, r) + get(t[id].r, tm + 1, tr, l, r);
    }
  }
  
  void upd(int id, int tl, int tr, int l, int r) {
    if (l <= tl && tr <= r) {
      t[id].cnt = tr - tl + 1;
      t[id].lz = true;
      return;
    }
    create(id);
    if (t[id].lz) {
      push(id, tl, tr);
    }
    int tm = (tl + tr) >> 1;
    if (r <= tm) {
      upd(t[id].l, tl, tm, l, r);
    } else if (tm + 1 <= l) {
      upd(t[id].r, tm + 1, tr, l, r);
    } else {
      upd(t[id].l, tl, tm, l, r);
      upd(t[id].r, tm + 1, tr, l, r);
    }
    t[id].cnt = t[t[id].l].cnt + t[t[id].r].cnt;
  }
} dst;

int m, c;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> m;
  while (m--) {
    int d, x, y;
    cin >> d >> x >> y;
    x += c; y += c;
    if (d == 1) {
      c = dst.get(1, 1, X, x, y);
      cout << c << '\n';
    } else if (d == 2) {
      dst.upd(1, 1, X, x, y);
    }
  }
  return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	58 ms	125520 KB	Output is correct
2	Correct	25 ms	125468 KB	Output is correct
3	Correct	25 ms	125532 KB	Output is correct
4	Correct	31 ms	125784 KB	Output is correct
5	Correct	34 ms	125792 KB	Output is correct
6	Correct	30 ms	125784 KB	Output is correct
7	Correct	31 ms	125700 KB	Output is correct
8	Correct	63 ms	126548 KB	Output is correct
9	Correct	121 ms	127768 KB	Output is correct
10	Correct	113 ms	127824 KB	Output is correct
11	Correct	115 ms	127684 KB	Output is correct
12	Correct	118 ms	127704 KB	Output is correct
13	Correct	113 ms	128108 KB	Output is correct
14	Correct	112 ms	128036 KB	Output is correct
15	Correct	137 ms	128336 KB	Output is correct
16	Correct	137 ms	128308 KB	Output is correct
17	Correct	114 ms	128156 KB	Output is correct
18	Correct	109 ms	128008 KB	Output is correct
19	Correct	137 ms	128336 KB	Output is correct
20	Correct	165 ms	128144 KB	Output is correct