Submission #781386

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
781386	2023-07-13T05:06:51 Z	michy	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	449 ms	262144 KB

apple

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

struct Node {
  int sum, lazy;
  Node *left, *right;
  Node() : sum(0), lazy(0), left(nullptr), right(nullptr) {}
};
  
void push(Node *v, int tl, int tr) {
  if (tl == tr) return;
  int tm = (tl + tr) / 2;
  if (!v->left) v->left = new Node();
  if (!v->right) v->right = new Node();
  if (v->lazy == 1) {
    v->left->sum = tm - tl + 1;
    v->right->sum = tr - tm;
    v->left->lazy = 1;
    v->right->lazy = 1;
    v->lazy = 0;
  }
}

int query(Node *v, int tl, int tr, int l, int r) {
  push(v, tl, tr);
  if (l > tr || r < tl)
    return 0;
  if (l <= tl && tr <= r)
    return v->sum;
  int tm = (tl + tr) / 2;
  return (v->left ? query(v->left, tl, tm, l, r) : 0) + (v->right ? query(v->right, tm+1, tr, l, r) : 0);
}

void update(Node *v, int tl, int tr, int l, int r) {
  push(v, tl, tr);
  if (l > tr || r < tl)
    return;
  if (l <= tl && tr <= r) {
    v->lazy = 1;
    v->sum = tr - tl + 1;
    return;
  }
  int tm = (tl + tr) / 2;
  if (v->left) update(v->left, tl, tm, l, r);
  if (v->right) update(v->right, tm+1, tr, 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();
  int ans = 0;
  while (q--) {
    int op, l, r;
    cin >> op >> l >> r;
    l += ans; r += ans;
    if (op == 1) {
      ans = query(root, 1, 1e9, l, r);
      cout << ans << "\n";
    } else {
      update(root, 1, 1e9, l, r);
    }
  }
  return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	13 ms	5844 KB	Output is correct
5	Correct	16 ms	6980 KB	Output is correct
6	Correct	20 ms	6808 KB	Output is correct
7	Correct	16 ms	7024 KB	Output is correct
8	Correct	119 ms	51468 KB	Output is correct
9	Correct	254 ms	87452 KB	Output is correct
10	Correct	256 ms	98104 KB	Output is correct
11	Correct	280 ms	106396 KB	Output is correct
12	Correct	271 ms	110124 KB	Output is correct
13	Correct	268 ms	136936 KB	Output is correct
14	Correct	269 ms	138444 KB	Output is correct
15	Correct	431 ms	254508 KB	Output is correct
16	Correct	434 ms	256556 KB	Output is correct
17	Correct	273 ms	145312 KB	Output is correct
18	Correct	274 ms	145640 KB	Output is correct
19	Correct	434 ms	262144 KB	Output is correct
20	Correct	449 ms	262144 KB	Output is correct