Submission #409355

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
409355	2021-05-20T15:32:17 Z	danielliu04	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	575 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+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;
}

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	28 ms	8372 KB	Output is correct
5	Correct	38 ms	10164 KB	Output is correct
6	Correct	33 ms	9812 KB	Output is correct
7	Correct	34 ms	10124 KB	Output is correct
8	Correct	243 ms	77160 KB	Output is correct
9	Correct	486 ms	134016 KB	Output is correct
10	Correct	513 ms	147908 KB	Output is correct
11	Correct	521 ms	158968 KB	Output is correct
12	Correct	538 ms	163804 KB	Output is correct
13	Correct	505 ms	189272 KB	Output is correct
14	Correct	495 ms	191656 KB	Output is correct
15	Runtime error	575 ms	262148 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-