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
#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);
        }
    }
}
# 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