Submission #781358

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
781358	2023-07-13T04:12:07 Z	michy	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	380 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->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 (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 (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	316 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	16 ms	11476 KB	Output is correct
5	Correct	20 ms	13796 KB	Output is correct
6	Correct	20 ms	13404 KB	Output is correct
7	Correct	22 ms	13784 KB	Output is correct
8	Correct	151 ms	102908 KB	Output is correct
9	Correct	328 ms	174568 KB	Output is correct
10	Correct	354 ms	195836 KB	Output is correct
11	Correct	346 ms	212392 KB	Output is correct
12	Correct	380 ms	219744 KB	Output is correct
13	Runtime error	330 ms	262144 KB	Execution killed with signal 9
14	Halted	0 ms	0 KB	-