Submission #409365

#	Time	Username	Problem	Language	Result	Execution time	Memory
409365		danielliu04	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	538 ms	262148 KiB

apple

#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
            addLeft();
            addRight();

            if(x <= mid) ans += lc->query(x, y);
            if(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(1, 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;
}

• Subtask 1: 0 / 100