Submission #781364

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

apple

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

struct Node {
  int tl, tr, sum, lazy;
  Node *left, *right;
  Node(int l, int r) : tl(l), tr(r), sum(0), lazy(0), left(nullptr), right(nullptr) {}
};
  
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 != 0) {
    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;
  }
  if (v->left) update(v->left, l, r);
  if (v->right) 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 << "\n";
    } 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	16 ms	8660 KB	Output is correct
5	Correct	21 ms	10452 KB	Output is correct
6	Correct	18 ms	10040 KB	Output is correct
7	Correct	24 ms	10476 KB	Output is correct
8	Correct	149 ms	77188 KB	Output is correct
9	Correct	308 ms	131116 KB	Output is correct
10	Correct	335 ms	147276 KB	Output is correct
11	Correct	341 ms	159400 KB	Output is correct
12	Correct	324 ms	164948 KB	Output is correct
13	Correct	323 ms	205644 KB	Output is correct
14	Correct	314 ms	207932 KB	Output is correct
15	Runtime error	352 ms	262144 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-