Submission #409424

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
409424	2021-05-20T17:40:47 Z	danielliu04	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	596 ms	262148 KB

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.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	26 ms	8248 KB	Output is correct
5	Correct	32 ms	10016 KB	Output is correct
6	Correct	32 ms	9760 KB	Output is correct
7	Correct	32 ms	10052 KB	Output is correct
8	Correct	234 ms	76692 KB	Output is correct
9	Correct	482 ms	133312 KB	Output is correct
10	Correct	505 ms	147524 KB	Output is correct
11	Correct	530 ms	158480 KB	Output is correct
12	Correct	528 ms	163396 KB	Output is correct
13	Correct	513 ms	188728 KB	Output is correct
14	Correct	489 ms	191048 KB	Output is correct
15	Runtime error	596 ms	262148 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-