Submission #1264070

#	Time	Username	Problem	Language	Result	Execution time	Memory
1264070		EntityPlantt	Monkey and Apple-trees (IZhO12_apple)	C++20	100 / 100	421 ms	205548 KiB

apple

#include <bits/stdc++.h>
using namespace std;

struct sgtnode {
	int il, ir;
	bool v = false;
	int cnt = 0;
	sgtnode *l, *r;
	inline void expand() {
		if (il == ir || l) return;
		const int m = il + ir >> 1;
		l = new sgtnode{il, m};
		r = new sgtnode{m + 1, ir};
		updlz();
	}
	inline void build() {
		if (!l) return;
		l->updlz();
		r->updlz();
		cnt = l->cnt + r->cnt;
	}
	inline void updlz() {
		if (!v) return;
		cnt = ir - il + 1;
		if (l) l->v = r->v = true;
	}
	int get(int tl, int tr) {
		if (ir < tl || tr < il) return 0;
		updlz();
		if (tl <= il && ir <= tr) return cnt;
		expand();
		return l->get(tl, tr) + r->get(tl, tr);
	}
	void set(int tl, int tr) {
		if (ir < tl || tr < il) return;
		if (tl <= il && ir <= tr) return v = true, updlz();
		expand();
		l->set(tl, tr);
		r->set(tl, tr);
		build();
	}
} sgt{1, 1000000000, false};
int c;

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int q;
	cin >> q;
	while (q--) {
		char o;
		int l, r;
		cin >> o >> l >> r;
		if (o == '1') cout << (c = sgt.get(l + c, r + c)) << '\n';
		else sgt.set(l + c, r + c);
	}
}

• Subtask 1: 100 / 100