Submission #432143

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
432143	2021-06-17T21:40:41 Z	danielliu04	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	636 ms	262148 KB

apple

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define INF 1e9+7
#define lc 2*node+1
#define rc 2*node+2

#define done 0
#define add 1
#define del 2


const int MAX = 1e9 + 1;
int m;


struct Node {
    Node* left_child; Node* right_child;
    int left, right, mid, total;
    bool lazy;

    Node() {
        total = lazy = left = right = mid = 0;
        left_child = right_child = NULL;
    }

    Node(int val, int l, int r) {
        left = l; right = r;
        mid = (left + right) / 2;
        total = val; lazy = 0;
        left_child = right_child = NULL;
    }

    void extend() {
        left_child = new Node(0, left, mid);
        right_child = new Node(0, mid + 1, right);
    }

    void propagate() {
        if (left != right && left_child == NULL) extend();
        if (lazy) {
            total = right - left + 1;
            if (left != right) left_child->lazy = right_child->lazy = 1;
            lazy = 0;
        }
    }

    void update(int x, int y) {
        if (x <= left && right <= y) lazy = 1;
        else {
            propagate(); // make sure that the children are there and the current value is extended

            if (x <= mid) left_child->update(x, y);
            if (y >= mid + 1) right_child->update(x, y);

            left_child->propagate(); right_child->propagate();
            total = left_child->total + right_child->total;
        }
    }

    int query(int x, int y) {
        propagate();
        if (x <= left && right <= y) return total;
        else {
            int ans = 0;
            if (x <= mid) ans += left_child->query(x, y);
            if (y >= mid + 1) ans += right_child->query(x, y);
            return ans;
        }
    }
};


Node* root;


int main() {

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    // freopen("input.in", "r", stdin);
    // freopen("input.out", "w", stdout);

    cin >> m;

    root = new Node(0, 0, MAX);

    int t, l, r;
    int c = 0;

    while (m --) {
        cin >> t >> l >> r;
        l --; r --;

        l += c; r += c;

        if (t == 1) { // query
            c = root->query(l, r);
            cout << c << endl;
        }
        else if (t == 2) { // ripening
            root->update(l, r);
        }
    }

    return 0;

}

Compilation message

apple.cpp: In constructor 'Node::Node()':
apple.cpp:24:29: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   24 |         total = lazy = left = right = mid = 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	7748 KB	Output is correct
5	Correct	33 ms	9384 KB	Output is correct
6	Correct	33 ms	9064 KB	Output is correct
7	Correct	34 ms	9440 KB	Output is correct
8	Correct	288 ms	70168 KB	Output is correct
9	Correct	524 ms	120100 KB	Output is correct
10	Correct	567 ms	134304 KB	Output is correct
11	Correct	592 ms	145252 KB	Output is correct
12	Correct	582 ms	150080 KB	Output is correct
13	Correct	532 ms	183376 KB	Output is correct
14	Correct	521 ms	185536 KB	Output is correct
15	Runtime error	636 ms	262148 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-