# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
836582 | azatega | 원숭이와 사과 나무 (IZhO12_apple) | C++11 | 1 ms | 212 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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 time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |