Submission #912550

#TimeUsernameProblemLanguageResultExecution timeMemory
912550anarch_yMonkey and Apple-trees (IZhO12_apple)C++17
100 / 100
390 ms202632 KiB
#include <bits/stdc++.h> using namespace std; #define all(x) begin(x), end(x) #define sz(x) (int)x.size() #define pb push_back #define int long long const int maxn = 1e9; struct Node{ int value, lzSet; Node *left, *right; Node(int v){ value = v; lzSet = -1; left = right = nullptr; } }; struct DynamicTree{ int len; Node *root; DynamicTree(int N){ int p = ceil(log2(N)); len = (1<<p); root = new Node(0); } void pushup(Node *k){ int sum = 0; if(k->left != nullptr) sum += k->left->value; if(k->right != nullptr) sum += k->right->value; k->value = sum; } void pushdown(Node *k, int x, int y){ int v = k->lzSet; if(v != -1){ if(k->left == nullptr) k->left = new Node(0); if(k->right == nullptr) k->right = new Node(0); k->left->lzSet = v; k->right->lzSet = v; int d = (x+y)/2; k->left->value = (d-x+1)*v; k->right->value = (y-d)*v; k->lzSet = -1; } } Node* update(int a, int b, int v, Node *k, int x, int y){ if(b < x or a > y) return k; if(k == nullptr) k = new Node(0); if(a <= x and y <= b){ k->value = (y-x+1)*v; k->lzSet = v; return k; } pushdown(k, x, y); int d = (x+y)/2; k->left = update(a, b, v, k->left, x, d); k->right = update(a, b, v, k->right, d+1, y); pushup(k); return k; } void update(int a, int b, int v){ root = update(a, b, v, root, 0, len-1); } int query(int a, int b, Node *k, int x, int y){ if(b < x or a > y) return 0LL; if(k == nullptr) return 0LL; if(a <= x and y <= b) return k->value; pushdown(k, x, y); int d = (x+y)/2; int s1 = query(a, b, k->left, x, d); int s2 = query(a, b, k->right, d+1, y); return s1+s2; } int query(int a, int b){ return query(a, b, root, 0, len-1); } }; signed main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int M; cin >> M; DynamicTree dseg(maxn); int C = 0; while(M--){ int op; cin >> op; if(op == 2){ int a, b; cin >> a >> b; a--; b--; dseg.update(a+C, b+C, 1); } else{ int a, b; cin >> a >> b; a--; b--; int ans = dseg.query(a+C, b+C); C = ans; cout << ans << "\n"; } } }
#Verdict Execution timeMemoryGrader output
Fetching results...