Submission #409343

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
409343	2021-05-20T15:27:18 Z	danielliu04	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	592 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 left, right;
    int sum, lazy;
    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;
}

Compilation message

apple.cpp: In constructor 'Node::Node()':
apple.cpp:15:14: warning: 'Node::lazy' will be initialized after [-Wreorder]
   15 |     int sum, lazy;
      |              ^~~~
apple.cpp:14:9: warning:   'int Node::left' [-Wreorder]
   14 |     int left, right;
      |         ^~~~
apple.cpp:18:5: warning:   when initialized here [-Wreorder]
   18 |     Node() : sum(0), lazy(0), left(-1), right(-1){}
      |     ^~~~

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	27 ms	8376 KB	Output is correct
5	Correct	46 ms	10136 KB	Output is correct
6	Correct	32 ms	9816 KB	Output is correct
7	Correct	33 ms	10092 KB	Output is correct
8	Correct	256 ms	77524 KB	Output is correct
9	Correct	519 ms	135184 KB	Output is correct
10	Correct	518 ms	149124 KB	Output is correct
11	Correct	592 ms	160216 KB	Output is correct
12	Correct	572 ms	164976 KB	Output is correct
13	Correct	533 ms	190600 KB	Output is correct
14	Correct	515 ms	192900 KB	Output is correct
15	Runtime error	564 ms	262148 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-