Submission #1104136

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1104136	2024-10-23T02:39:34 Z	eysbutno	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	483 ms	139592 KB

apple

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = array<int, 2>;
#define all(x) begin(x), end(x)
#define sz(x) (int) (x).size()

class SparseSegtree {
  private:
	const int n;
	struct Node {
		int freq = 0;
        int lazy = 0;
		Node *left = nullptr;
		Node *right = nullptr;
	};
	Node *root = new Node;

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

	void apply(Node *cur, int len, int val) {
		if (val == 1) {
            (cur -> lazy) = 1;
            (cur -> freq) = len;
        }
	}

	void push_down(Node *cur, int l, int r) {
		if ((cur->left) == nullptr) { (cur->left) = new Node; }
		if ((cur->right) == nullptr) { (cur->right) = new Node; }
        int m = (l + r) / 2;
        apply(cur->left, m - l + 1, cur->lazy);
        apply(cur->right, r - m, cur->lazy);
	}

	void range_set(Node *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(cur->left, l, m, ql, qr, val);
			range_set(cur->right, m + 1, r, ql, qr, val);
			(cur->freq) = comb((cur->left)->freq, (cur->right)->freq);
		}
	}

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

  public:
	SparseSegtree(int n) : n(n) {}

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

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

int main() {
    int n;
    cin >> n;
    SparseSegtree st((int) (1e9 + 1));
    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	3376 KB	Output is correct
5	Correct	21 ms	4192 KB	Output is correct
6	Correct	23 ms	3912 KB	Output is correct
7	Correct	21 ms	4168 KB	Output is correct
8	Correct	131 ms	30024 KB	Output is correct
9	Correct	273 ms	52328 KB	Output is correct
10	Correct	277 ms	57672 KB	Output is correct
11	Correct	319 ms	62024 KB	Output is correct
12	Correct	330 ms	63780 KB	Output is correct
13	Correct	305 ms	74312 KB	Output is correct
14	Correct	303 ms	75036 KB	Output is correct
15	Correct	434 ms	135496 KB	Output is correct
16	Correct	440 ms	136520 KB	Output is correct
17	Correct	326 ms	77604 KB	Output is correct
18	Correct	336 ms	77640 KB	Output is correct
19	Correct	471 ms	139456 KB	Output is correct
20	Correct	483 ms	139592 KB	Output is correct