Submission #492104

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
492104	2021-12-05T13:09:58 Z	ronnith	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	444 ms	262148 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 (curr == nullptr) return 0;
		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	0 ms	204 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	14 ms	7756 KB	Output is correct
5	Correct	19 ms	9468 KB	Output is correct
6	Correct	20 ms	9056 KB	Output is correct
7	Correct	22 ms	9320 KB	Output is correct
8	Correct	153 ms	70172 KB	Output is correct
9	Correct	312 ms	120172 KB	Output is correct
10	Correct	394 ms	134332 KB	Output is correct
11	Correct	345 ms	145300 KB	Output is correct
12	Correct	358 ms	150012 KB	Output is correct
13	Correct	341 ms	183288 KB	Output is correct
14	Correct	324 ms	185460 KB	Output is correct
15	Runtime error	444 ms	262148 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-