Submission #781349

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
781349	2023-07-13T04:01:50 Z	michy	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	463 ms	262144 KB

apple

#include <bits/stdc++.h>
using namespace std;

struct Node {
  int tl, tr, sum, lazy;
  Node *left = nullptr, *right = nullptr;
  Node(int l, int r) : tl(l), tr(r), sum(0), lazy(0) {}
};
  
void push(Node *v) {
  if (v->tl == v->tr) return;
  int tm = (v->tl + v->tr) / 2;
  if (!v->left) v->left = new Node(v->tl, tm);
  if (!v->right) v->right = new Node(tm+1, v->tr);
  if (v->lazy == 1) {
    v->left->sum = (tm - v->tl + 1);
    v->right->sum = (v->tr - tm);
    v->left->lazy = 1;
    v->right->lazy = 1;
  }
}

int query(Node *v, int l, int r) {
  push(v);
  if (l > v->tr || r < v->tl)
    return 0;
  if (l <= v->tl && v->tr <= r)
    return v->sum;
  return (v->left ? query(v->left, l, r) : 0) + (v->right ? query(v->right, l, r) : 0);
}

void update(Node *v, int l, int r) {
  push(v);
  if (l > v->tr || r < v->tl)
    return;
  if (l <= v->tl && v->tr <= r) {
    v->lazy = 1;
    v->sum = (v->tr - v->tl + 1);
    return;
  }
  update(v->left, l, r);
  update(v->right, l, r);
  v->sum = (v->left ? v->left->sum : 0) + (v->right ? v->right->sum : 0);
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int q;
  cin >> q;
  Node *root = new Node(1, 1e9);
  int ans = 0;
  while (q--) {
    int op, l, r;
    cin >> op >> l >> r;
    l += ans; r += ans;
    if (op == 1) {
      ans = query(root, l, r);
      cout << ans << endl;
    } else {
      update(root, l, r);
    }
  }
  return 0;
}

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	316 KB	Output is correct
2	Correct	1 ms	324 KB	Output is correct
3	Correct	1 ms	316 KB	Output is correct
4	Correct	19 ms	8736 KB	Output is correct
5	Correct	23 ms	10452 KB	Output is correct
6	Correct	24 ms	10072 KB	Output is correct
7	Correct	29 ms	10412 KB	Output is correct
8	Correct	164 ms	77068 KB	Output is correct
9	Correct	339 ms	130940 KB	Output is correct
10	Correct	352 ms	147012 KB	Output is correct
11	Correct	463 ms	159500 KB	Output is correct
12	Correct	371 ms	164964 KB	Output is correct
13	Correct	375 ms	205080 KB	Output is correct
14	Correct	377 ms	207132 KB	Output is correct
15	Runtime error	362 ms	262144 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-