제출 #836582

#제출 시각아이디문제언어결과실행 시간메모리
836582azatega원숭이와 사과 나무 (IZhO12_apple)C++11
0 / 100
1 ms212 KiB
#include <iostream> using namespace std; #define ll long long struct Node{ ll val; ll lazy = 0; // 0 if no set, 1 if set ll l; ll r; Node* left = nullptr; Node* right = nullptr; Node(){} Node(ll _val){ val = _val; } Node(ll _val, ll _l, ll _r){ val = _val; l = _l; r = _r; } }; void pushdown(Node *node){ if(node->l == node->r) return; ll mid = (node->l + node->r) / 2; if(node->left == nullptr) node->left = new Node(0, node->l, mid); if(node->right == nullptr) node->right = new Node(0, mid+1, node->r); if(node->lazy == 1){ node->left->val += (node->left->r - node->left->l + 1); node->left->lazy = 1; node->right->val += (node->right->r - node->right->l + 1); node->right->lazy = 1; node->lazy = 0; } } void pushup(Node *node){ ll val = 0; if(node->left != nullptr) val += node->left->val; if(node->right != nullptr) val += node->right->val; node->val = val; } void update(Node *node, ll ql, ll qr){ if(node->l > qr || node->r < ql) return; if(node->l >= ql && node->r <= qr){ node->val += (node->r - node->l + 1); node->lazy = 1; return; } pushdown(node); update(node->left, ql, qr); update(node->right, ql, qr); pushup(node); } ll query(Node *node, ll ql, ll qr){ if(node->l > qr || node->r < ql) return 0; if(node->l >= ql && node->r <= qr) return node->val; pushdown(node); return query(node->left, ql, qr) + query(node->right, ql, qr); } Node *root = new Node(0, 0, 1e16 + 5); int main() { int T; cin >> T; ll C = 0; while(T--){ ll t, l, r; cin >> t >> l >> r; l += C; r += C; if(t == 1){ ll x = query(root, l, r); C = x; cout << x << endl; }else{ update(root, l, r); } } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...