Submission #492103

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
492103	2021-12-05T13:07:05 Z	ronnith	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	1 ms	460 KB

apple

#include <bits/stdc++.h>

using namespace std;

struct sparse_segment_tree {
	struct Node {
		int64_t val;
        Node* left;
        Node* right;
        bool upd;
		Node() : val(0), left(nullptr), right(nullptr), upd(false) {}
		Node(int64_t v) : val(v), left(nullptr), right(nullptr), upd(false) {}
	};

	int size;
    Node* root;

	sparse_segment_tree() {}

	sparse_segment_tree(int _) : size(_), root(new Node()) {
	}

    void propogate(Node* curr, int lx, int rx) {
        if (!curr->upd) {
            return;
        }
        curr->upd = false;
        curr->val = rx - lx + 1;
        if (lx != rx) {
             if (curr->left == nullptr) {
                 curr->left = new Node();
             }
             if (curr->right == nullptr) {
                 curr->right = new Node();
             }
             curr->left->upd = true;
             curr->right->upd = true;
        }
    }

	void update(Node* curr, int l, int r, int lx, int rx) {
        propogate(curr, lx, rx);
        if (rx < l || r < lx) {
            return;
        }
		if (l <= lx && rx <= r) {
            curr->upd = true;
            propogate(curr, lx, rx);
            return;
        }

		int mid = lx + (rx - lx) / 2;

        if (curr->left == nullptr) {
            curr->left = new Node();
        }
		update(curr->left, l, r, lx, mid);
        if (curr->right == nullptr) {
            curr->right = new Node();
        }
		update(curr->right, l, r, mid + 1, rx);
        curr->val = curr->left->val + curr->right->val;
	}

	void update(int l, int r) {
		update(root, l, r, 1, size);
	}

	int64_t query(Node* curr, int l, int r, int lx, int rx) {
		if (r < lx || rx < l) return 0;
        propogate(curr, lx, rx);
		if (l <= lx && rx <= r) return curr->val;
		int mid = lx + (rx - lx) / 2;
		return query(curr->left, l, r, lx, mid) + query(curr->right, l, r, mid + 1, rx);
	}

	int64_t query(int l, int r) {
		return query(root, l, r, 1, size);
	}
};

// have to implement LAZY PROPOGATION

const int M = (int)1e5;
int m;

void solve() {
    cin >> m;
    int C = 0;
    sparse_segment_tree seg((int)1e9);
    for (int i = 0; i < m; i ++) {
        int d, x, y;
        cin >> d >> x >> y;
        x += C;
        y += C;
        if (d == 1) {
            int ans = seg.query(x, y);
            C = ans;
            cout << ans << '\n';
        } else {
            seg.update(x, y);
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    t = 1;
    for (int i = 0; i < t; i ++) {
        solve();
    }
    return 0;
}

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Runtime error	1 ms	460 KB	Execution killed with signal 11
3	Halted	0 ms	0 KB	-