Submission #1104140

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1104140	2024-10-23T03:11:17 Z	eysbutno	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	169 ms	70472 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;
    int mnc = -1;
    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 > 0) {
            tree[cur].lazy = val;
            tree[cur].freq = len * val;
        }
	}

	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());
        }
        assert(tree.size() < mnc);
        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;
	}

	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(mnc = 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() {
    cin.tie(0) -> sync_with_stdio(0);
    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);
        }
    }
}

Compilation message

In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from apple.cpp:1:
apple.cpp: In member function 'void SparseSegtree::push_down(int, int, int)':
apple.cpp:37:28: warning: comparison of integer expressions of different signedness: 'std::vector<SparseSegtree::Node>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   37 |         assert(tree.size() < mnc);
      |                ~~~~~~~~~~~~^~~~~

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	8 ms	2384 KB	Output is correct
5	Correct	9 ms	2384 KB	Output is correct
6	Correct	9 ms	2384 KB	Output is correct
7	Correct	9 ms	2512 KB	Output is correct
8	Correct	57 ms	16968 KB	Output is correct
9	Correct	118 ms	27468 KB	Output is correct
10	Correct	109 ms	29512 KB	Output is correct
11	Correct	110 ms	31560 KB	Output is correct
12	Correct	111 ms	31560 KB	Output is correct
13	Correct	100 ms	37712 KB	Output is correct
14	Correct	103 ms	37704 KB	Output is correct
15	Correct	131 ms	68424 KB	Output is correct
16	Correct	130 ms	68424 KB	Output is correct
17	Correct	114 ms	39752 KB	Output is correct
18	Correct	118 ms	39752 KB	Output is correct
19	Correct	155 ms	70472 KB	Output is correct
20	Correct	169 ms	70464 KB	Output is correct