Submission #409424

#	Time	Username	Problem	Language	Result	Execution time	Memory
409424		danielliu04	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	596 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;

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(){
        if(!lc){
            int mid = (left + right) / 2;
            lc = new Node(left, mid);
        }
    }
    void addRight(){
        if(!rc){
            int mid = (left + right) / 2;
            rc = new Node(mid+1, right);
        }
    }
    void propagate(){
        if(lazy){
            sum = right - left + 1;
            addLeft();
            addRight();
            lc->lazy = rc->lazy = 1;
            lazy = 0;
        }
    }
    void update(int x, int y){
        // cout << left << " " << right << endl;
        if(x <= left && right <= y){
            lazy = 1; // set the lazy value if completely in range
            // cout << left << " " << right << endl;
        }
        else{
            propagate();
            int mid = (left + right) / 2;
            if(x <= mid){
                addLeft();
                lc->update(x, y);
            }
            if(y >= mid+1){
                addRight();
                rc->update(x, y);
            }
            if(lc){
                lc->propagate();
            }
            if(rc){
                rc->propagate();
            }
            sum = (lc ? lc->sum : 0) + (rc ? rc->sum : 0);
        }
    }
    int query(int x, int y){
        propagate();
        if(x <= left && right <= y){
            return sum;
        }
        else{
            int mid = (left + right) / 2;
            int sum = 0;
            if(x <= mid && lc){
                sum += lc->query(x, y);
            }
            if(y >= mid+1 && rc){
                sum += rc->query(x, y);
            }
            return sum;
        }
    }
};

Node *root;

int main(){

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> q;

    // cout << q << endl;

    root = new Node(1, MAX);
    // cout << root->sum << " " << root->lazy << endl;
    // cout << root->left << " " << root->right << endl;
    
    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);
            // cout << "finished" << endl;
        }
    }
    return 0;
}

• Subtask 1: 0 / 100