제출 #409355

#제출 시각아이디문제언어결과실행 시간메모리
409355danielliu04Monkey and Apple-trees (IZhO12_apple)C++17
0 / 100
575 ms262148 KiB
#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 timeMemoryGrader output
Fetching results...