Submission #31766

#TimeUsernameProblemLanguageResultExecution timeMemory
31766trathMonkey and Apple-trees (IZhO12_apple)C++98
100 / 100
186 ms2176 KiB
#include <bits/stdc++.h> using namespace std; struct node { int sum; struct node *left, *right; node(){ sum = 0; left = NULL; right = NULL; } }; void combine(node *root, node *a, node *b){ root->sum= 0; if(a != NULL) root->sum += a->sum; if(b != NULL) root->sum += b->sum; } void update(node *root, int l, int r, int a, int b){ if(root->sum == r-l+1) return; if(l == a && r == b){ root->sum=(r-l+1); return; } int m = (l+r) >> 1; if(b <= m){ if(!root->left) root->left = new node(); update(root->left, l, m, a, b); } else if(m < a){ if(!root->right) root->right = new node(); update(root->right, m+1, r, a, b); } else { if(!root->left) root->left = new node(); if(!root->right) root->right = new node(); update(root->left, l, m, a, m); update(root->right, m+1, r, m+1, b); } combine(root, root->left, root->right); } int query(node *root, int l, int r, int a, int b){ if(root->sum == r-l+1) return b-a+1; if(l == a && r == b) return root->sum; int m = (l+r) >> 1; if(b <= m){ if(root->left) return query(root->left, l, m, a, b); else return 0; } else if(m < a){ if(root->right) return query(root->right, m+1, r, a, b); else return 0; } else { int sum = 0; if(root->left) sum += query(root->left, l, m, a, m); if(root->right) sum += query(root->right, m+1, r, m+1, b); return sum; } } int c = 0; node *tree = new node(); int main(){ ios_base::sync_with_stdio(false); int q; cin >> q; while(q--){ int op,a,b; cin >> op >> a >> b; if(op == 1){ c = query(tree, 1, (int)1e9, a+c, b+c); cout << c << endl; } else update(tree, 1, (int)1e9, a+c, b+c); } }
#Verdict Execution timeMemoryGrader output
Fetching results...