Submission #781332

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
781332	2023-07-13T03:42:47 Z	michy	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	370 ms	262144 KB

apple

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

struct Node {
  int tl, tr;
  int sum = 0, lazy = 0;
  Node *left = nullptr, *right = nullptr;
  Node(int l, int r) : tl(l), tr(r) {}
};
  
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;
    v->lazy = 0;
  }
}

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, int val) {
  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, val);
  update(v->right, l, r, val);
  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, 1);
    }
  }
  return 0;
}

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	324 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	21 ms	8664 KB	Output is correct
5	Correct	24 ms	10536 KB	Output is correct
6	Correct	22 ms	10148 KB	Output is correct
7	Correct	23 ms	10460 KB	Output is correct
8	Correct	166 ms	77904 KB	Output is correct
9	Correct	349 ms	132596 KB	Output is correct
10	Correct	370 ms	148628 KB	Output is correct
11	Correct	368 ms	161048 KB	Output is correct
12	Correct	366 ms	166600 KB	Output is correct
13	Correct	357 ms	207216 KB	Output is correct
14	Correct	349 ms	209136 KB	Output is correct
15	Runtime error	367 ms	262144 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-