# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
409355 | danielliu04 | Monkey and Apple-trees (IZhO12_apple) | C++17 | 575 ms | 262148 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define INF 1e18
// #define lc 2*node+1
// #define rc 2*node+2
int q;
int MAX = 1e9+1;
struct Node{
int sum, lazy, left, right;
Node *lc = nullptr, *rc = nullptr;
Node() : sum(0), lazy(0), left(-1), right(-1){}
Node(int l, int r) : sum(0), lazy(0){
left = l; right = r;
}
void addLeft(){
int mid = (left + right) / 2;
if(!lc){
lc = new Node(left, mid);
}
}
void addRight(){
int mid = (left + right) / 2;
if(!rc){
rc = new Node(mid+1, right);
}
}
void propagate(){
if(lazy){
sum = right - left + 1;
addLeft();
addRight();
lc->lazy = rc->lazy = 1; // set the lazy value for later
lazy = 0;
}
}
void update(int x, int y){
propagate(); // I need to add the children later regardless
if(x <= left && right <= y){
lazy = 1;
}
else{
int mid = (left + right) / 2;
addLeft();
addRight();
if(x <= mid) lc->update(x, y);
if(y >= mid+1) rc->update(x, y);
lc->propagate(); rc->propagate(); // update the values
sum = lc->sum + rc->sum;
}
}
int query(int x, int y){
propagate(); // always updates the lazy value to children
if(x <= left && right <= y){
return sum;
}
else{
int mid = (left + right) / 2;
int ans = 0;
// if lazy value is 0 and there are no children, this means we don't need to go any further
if(lc && x <= mid){
ans += lc->query(x, y);
}
if(rc && y >= mid+1){
ans += rc->query(x, y);
}
return ans;
}
}
};
Node *root;
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> q;
root = new Node(0, MAX);
int c = 0;
int t, a, b;
while(q --){
cin >> t >> a >> b;
a += c; b += c;
if(t == 1){ // query
c = root->query(a, b);
cout << c << endl;
}
else{ // update
root->update(a, b);
}
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |