Submission #952334

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
952334	2024-03-23T14:31:51 Z	ind1v	Monkey and Apple-trees (IZhO12_apple)	C++11	100 / 100	191 ms	189012 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[120 * 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;
    t[id].lz = false;
  }
  
  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	95 ms	188244 KB	Output is correct
2	Correct	37 ms	188240 KB	Output is correct
3	Correct	35 ms	188212 KB	Output is correct
4	Correct	44 ms	188244 KB	Output is correct
5	Correct	42 ms	188312 KB	Output is correct
6	Correct	42 ms	188280 KB	Output is correct
7	Correct	41 ms	188348 KB	Output is correct
8	Correct	74 ms	188500 KB	Output is correct
9	Correct	121 ms	188596 KB	Output is correct
10	Correct	132 ms	188496 KB	Output is correct
11	Correct	127 ms	188568 KB	Output is correct
12	Correct	169 ms	188500 KB	Output is correct
13	Correct	119 ms	188752 KB	Output is correct
14	Correct	126 ms	188576 KB	Output is correct
15	Correct	165 ms	189012 KB	Output is correct
16	Correct	156 ms	188756 KB	Output is correct
17	Correct	146 ms	188732 KB	Output is correct
18	Correct	119 ms	188612 KB	Output is correct
19	Correct	191 ms	188720 KB	Output is correct
20	Correct	151 ms	188568 KB	Output is correct