Submission #409421

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
409421	2021-05-20T17:34:09 Z	danielliu04	Monkey and Apple-trees (IZhO12_apple)	C++11	0 / 100	584 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 = 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;
}

Compilation message

apple.cpp: In member function 'void Node::update(int, int)':
apple.cpp:60:13: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   60 |             if(lc) lc->propagate(); if(rc) rc->propagate();
      |             ^~
apple.cpp:60:37: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   60 |             if(lc) lc->propagate(); if(rc) rc->propagate();
      |                                     ^~

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	312 KB	Output is correct
4	Correct	27 ms	8332 KB	Output is correct
5	Correct	35 ms	10132 KB	Output is correct
6	Correct	33 ms	9892 KB	Output is correct
7	Correct	32 ms	10096 KB	Output is correct
8	Correct	238 ms	77572 KB	Output is correct
9	Correct	490 ms	134980 KB	Output is correct
10	Correct	519 ms	149276 KB	Output is correct
11	Correct	520 ms	160248 KB	Output is correct
12	Correct	548 ms	165060 KB	Output is correct
13	Correct	495 ms	190744 KB	Output is correct
14	Correct	505 ms	193220 KB	Output is correct
15	Runtime error	584 ms	262148 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-