Submission #409365

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
409365	2021-05-20T15:41:13 Z	danielliu04	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	538 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
            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.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	8212 KB	Output is correct
5	Correct	33 ms	9988 KB	Output is correct
6	Correct	33 ms	9724 KB	Output is correct
7	Correct	33 ms	10024 KB	Output is correct
8	Correct	250 ms	76704 KB	Output is correct
9	Correct	487 ms	133180 KB	Output is correct
10	Correct	514 ms	147452 KB	Output is correct
11	Correct	528 ms	158560 KB	Output is correct
12	Correct	529 ms	163140 KB	Output is correct
13	Correct	477 ms	188964 KB	Output is correct
14	Correct	506 ms	191000 KB	Output is correct
15	Runtime error	538 ms	262148 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-