Submission #781361

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

apple

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

typedef long long ll;

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

ll query(Node *v, ll l, ll r) {
  push(v);
  if (!v || 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, ll l, ll r) {
  push(v);
  if (!v || 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);
  ll ans = 0;
  while (q--) {
    ll 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	0 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	11356 KB	Output is correct
5	Correct	20 ms	13676 KB	Output is correct
6	Correct	19 ms	13140 KB	Output is correct
7	Correct	22 ms	13652 KB	Output is correct
8	Correct	156 ms	102556 KB	Output is correct
9	Correct	318 ms	174196 KB	Output is correct
10	Correct	499 ms	195608 KB	Output is correct
11	Correct	405 ms	212584 KB	Output is correct
12	Correct	375 ms	219964 KB	Output is correct
13	Runtime error	328 ms	262144 KB	Execution killed with signal 9
14	Halted	0 ms	0 KB	-