Submission #1104138

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1104138	2024-10-23T03:04:47 Z	eysbutno	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	307 ms	70512 KB

apple

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

class SparseSegtree {
  private:
	struct Node {
		int freq = 0;
        int lazy = 0;
		int left = -1;
        int right = -1;
	};
	vector<Node> tree;
    const int n;
    int timer = 0;

	int comb(int a, int b) {
        return a + b;
    }

	void apply(int cur, int len, int val) {
		if (val == 1) {
            tree[cur].lazy = 1;
            tree[cur].freq = len;
        }
	}

	void push_down(int cur, int l, int r) {
		if (tree[cur].left == -1) {
            tree[cur].left = ++timer;
            tree.push_back(Node());
        }
        if (tree[cur].right == -1) {
            tree[cur].right = ++timer;
            tree.push_back(Node());
        }
        int m = (l + r) / 2;
        apply(tree[cur].left, m - l + 1, tree[cur].lazy);
        apply(tree[cur].right, r - m, tree[cur].lazy);
		tree[cur].lazy = 0;  // Reset lazy after pushing down
	}

	void range_set(int cur, int l, int r, int ql, int qr, int val) {
		if (qr < l || ql > r) { return; }
		if (ql <= l && r <= qr) {
			apply(cur, r - l + 1, val);
		} else {
			push_down(cur, l, r);
			int m = (l + r) / 2;
			range_set(tree[cur].left, l, m, ql, qr, val);
			range_set(tree[cur].right, m + 1, r, ql, qr, val);
			tree[cur].freq = comb(tree[tree[cur].left].freq, tree[tree[cur].right].freq);
		}
	}

	int range_sum(int cur, int l, int r, int ql, int qr) {
        if (qr < l || ql > r) { return 0; }
        if (ql <= l && r <= qr) { return tree[cur].freq; }
        push_down(cur, l, r);
        int m = (l + r) / 2;
        return comb(range_sum(tree[cur].left, l, m, ql, qr), 
                    range_sum(tree[cur].right, m + 1, r, ql, qr));
    }

  public:
	SparseSegtree(int n, int q) : n(n) {
        tree.reserve(2 * q * __lg(n));
		tree.push_back(Node());
	}

	void range_set(int ql, int qr, int val) { 
		range_set(0, 0, n - 1, ql, qr, val);  
	}

    int range_sum(int ql, int qr) { 
		return range_sum(0, 0, n - 1, ql, qr); 
	}
};


int main() {
    int n;
    cin >> n;
    SparseSegtree st((int) (1e9 + 1), n);
    int c = 0;
    for (int i = 0; i < n; i++) {
        int type, x, y;
        cin >> type >> x >> y;
        if (type == 1) {
            c = st.range_sum(x + c, y + c);
            cout << c << '\n';
        } else if (type == 2) {
            st.range_set(x + c, y + c, 1);
        }
    }
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	336 KB	Output is correct
2	Correct	1 ms	336 KB	Output is correct
3	Correct	1 ms	336 KB	Output is correct
4	Correct	17 ms	2640 KB	Output is correct
5	Correct	20 ms	2556 KB	Output is correct
6	Correct	20 ms	2640 KB	Output is correct
7	Correct	19 ms	2384 KB	Output is correct
8	Correct	116 ms	17736 KB	Output is correct
9	Correct	237 ms	27332 KB	Output is correct
10	Correct	247 ms	29512 KB	Output is correct
11	Correct	237 ms	31476 KB	Output is correct
12	Correct	256 ms	31492 KB	Output is correct
13	Correct	250 ms	37644 KB	Output is correct
14	Correct	243 ms	38988 KB	Output is correct
15	Correct	290 ms	68484 KB	Output is correct
16	Correct	307 ms	68424 KB	Output is correct
17	Correct	234 ms	39752 KB	Output is correct
18	Correct	259 ms	39752 KB	Output is correct
19	Correct	289 ms	70472 KB	Output is correct
20	Correct	293 ms	70512 KB	Output is correct