Submission #432143

#TimeUsernameProblemLanguageResultExecution timeMemory
432143danielliu04Monkey and Apple-trees (IZhO12_apple)C++17
0 / 100
636 ms262148 KiB
#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 (stderr)

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;
      |                        ~~~~~^~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...