Submission #871874

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
871874	2023-11-11T18:40:59 Z	andrei_c1	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	72 ms	3112 KB

apple

#include <algorithm>
#include <iostream>
#include <vector>
#include <set>
 
using namespace std;
using ll = long long;
 
struct Chtholly {
	struct Node {
		int l, r;
		mutable ll v;
		Node() {}
		Node(int l, int r = -1, ll v = 0): l(l), r(r), v(v) {}
		bool operator < (const Node &oth) const {
			return l < oth.l;
		}
	};
 
	int n;
	set<Node> tree;
	Chtholly() {}
	Chtholly(int n): n(n) {
		tree.emplace(0, n - 1);
	}
	set<Node>::iterator split(int x) {
		auto it = tree.lower_bound(Node(x));
		if(it != tree.end() && it->l == x) {
			return it;
		}
		// assert(it != tree.begin());
		it = prev(it);
		if(it->r < x) {
			return tree.end();
		}
		int l = it->l, r = it-> r;
		ll v = it->v;
		tree.erase(it);
		tree.emplace(l, x - 1, v);
		return tree.emplace(x, r, v).first;
	}
	void flatten(int l, int r, int v) {
		auto R = split(r + 1), L = split(l);
		tree.erase(L, R);
		tree.emplace(l, r, v);
	}
	int query(int l, int r) {
		auto R = split(r + 1), L = split(l);
		int res = 0;
		while(L != R) {
			res += L->v * (L->r - L->l + 1);
			L = next(L);
		}
		return res;
	}
};
 
int main() {
#ifndef EVAL
	freopen("f.in", "r", stdin);
	freopen("f.out", "w", stdout);
#endif
	cin.tie(nullptr)->sync_with_stdio(false);
	int n;
	cin >> n;
	Chtholly ds(1e9);
	int c = 0;
	for(int i = 0; i < n; i++) {
		int t, l, r;
		cin >> t >> l >> r;
 
		l += c;
		r += c;
 
		l--;
		r--;
 
		if(t == 2) {
			ds.flatten(l, r, 1);
		} else {
			c = ds.query(l, r);
			cout << c << '\n';
		}
	}
	return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	6 ms	468 KB	Output is correct
5	Correct	6 ms	604 KB	Output is correct
6	Correct	7 ms	604 KB	Output is correct
7	Correct	6 ms	576 KB	Output is correct
8	Correct	34 ms	1372 KB	Output is correct
9	Correct	67 ms	2384 KB	Output is correct
10	Correct	67 ms	2552 KB	Output is correct
11	Correct	66 ms	2568 KB	Output is correct
12	Correct	66 ms	2524 KB	Output is correct
13	Correct	72 ms	2896 KB	Output is correct
14	Correct	63 ms	2896 KB	Output is correct
15	Correct	71 ms	2900 KB	Output is correct
16	Correct	68 ms	3112 KB	Output is correct
17	Correct	63 ms	3008 KB	Output is correct
18	Correct	66 ms	2896 KB	Output is correct
19	Correct	69 ms	3072 KB	Output is correct
20	Correct	68 ms	3104 KB	Output is correct