Submission #871874

#	Time	Username	Problem	Language	Result	Execution time	Memory
871874		andrei_c1	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	72 ms	3112 KiB

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 / 100