Submission #952294

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
952294	2024-03-23T13:48:15 Z	ind1v	Monkey and Apple-trees (IZhO12_apple)	C++11	0 / 100	153 ms	262144 KB

apple

#include <bits/stdc++.h>

using namespace std;

const int M = 1e4 + 5;
const int L = 20;
const int X = 1e6;

struct dynamic_segment_tree {
  struct node {
    bool lz;
    int l, r, cnt;
    
    node() : l(-1), r(-1), cnt(0), lz(false) {}
    
    node(int _l, int _r, int _cnt, bool _lz) : l(_l), r(_r), cnt(_cnt), lz(_lz) {}
  } t[4 * M * L];
  int nd = 0, root;
  
  int new_node() {
    nd++;
    return nd;
  }
  
  dynamic_segment_tree() {
    root = new_node();
  }
  
  void push(int id, int tl, int tr) {
    int tm = (tl + tr) >> 1;
    if (t[id].l == -1) {
      t[id].l = new_node();
      t[t[id].l].cnt = (t[id].lz ? tm - tl + 1 : 0);
      t[t[id].l].lz = t[id].lz;
    }
    if (t[id].r == -1) {
      t[id].r = new_node();
      t[t[id].r].cnt = (t[id].lz ? tr - tm : 0);
      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;
    }
    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;
    }
    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) {
      assert(y <= X);
      c = dst.get(dst.root, 1, X, x, y);
      cout << c << '\n';
    } else if (d == 2) {
      assert(y <= X);
      dst.upd(dst.root, 1, X, x, y);
    }
  }
  return 0;
}

Compilation message

apple.cpp: In constructor 'dynamic_segment_tree::node::node()':
apple.cpp:12:15: warning: 'dynamic_segment_tree::node::cnt' will be initialized after [-Wreorder]
   12 |     int l, r, cnt;
      |               ^~~
apple.cpp:11:10: warning:   'bool dynamic_segment_tree::node::lz' [-Wreorder]
   11 |     bool lz;
      |          ^~
apple.cpp:14:5: warning:   when initialized here [-Wreorder]
   14 |     node() : l(-1), r(-1), cnt(0), lz(false) {}
      |     ^~~~
apple.cpp: In constructor 'dynamic_segment_tree::node::node(int, int, int, bool)':
apple.cpp:12:15: warning: 'dynamic_segment_tree::node::cnt' will be initialized after [-Wreorder]
   12 |     int l, r, cnt;
      |               ^~~
apple.cpp:11:10: warning:   'bool dynamic_segment_tree::node::lz' [-Wreorder]
   11 |     bool lz;
      |          ^~
apple.cpp:16:5: warning:   when initialized here [-Wreorder]
   16 |     node(int _l, int _r, int _cnt, bool _lz) : l(_l), r(_r), cnt(_cnt), lz(_lz) {}
      |     ^~~~

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	12892 KB	Output is correct
2	Correct	3 ms	12892 KB	Output is correct
3	Runtime error	153 ms	262144 KB	Execution killed with signal 9
4	Halted	0 ms	0 KB	-