Submission #781341

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
781341	2023-07-13T03:50:53 Z	michy	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	417 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) {
  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	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	19 ms	8580 KB	Output is correct
5	Correct	25 ms	10384 KB	Output is correct
6	Correct	22 ms	10024 KB	Output is correct
7	Correct	23 ms	10268 KB	Output is correct
8	Correct	163 ms	76952 KB	Output is correct
9	Correct	337 ms	130856 KB	Output is correct
10	Correct	346 ms	146888 KB	Output is correct
11	Correct	366 ms	159364 KB	Output is correct
12	Correct	372 ms	164896 KB	Output is correct
13	Correct	415 ms	205196 KB	Output is correct
14	Correct	417 ms	207132 KB	Output is correct
15	Runtime error	389 ms	262144 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-