Submission #836327

#	Time	Username	Problem	Language	Result	Execution time	Memory
836327		mat_jur	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	472 ms	209448 KiB

apple

#include <bits/stdc++.h>
using namespace std;
#ifdef DEBUG
auto&operator<<(auto &o, pair<auto, auto> p) {o << "(" << p.first << ", " << p.second << ")"; return o;}
auto operator<<(auto &o, auto x)->decltype(x.end(), o) {o<<"{"; for(auto e : x) o<<e<<", "; return o<<"}";}
#define debug(X) cerr << "["#X"]: " << X << '\n';
#else 
#define debug(X) ;
#endif
#define ll long long
#define all(v) (v).begin(), (v).end()
#define FOR(i,l,r) for(int i=(l);i<=(r);++i)
#define REP(i,n) FOR(i,0,(n)-1)
#define ssize(x) int(x.size())
#define fi first
#define se second

int main () {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int m;
	cin >> m;
	int C = 0;
	struct Node {
		int val, lazy, start, end;
		Node *left, *right;
		Node() {
			val = 0;
			lazy = -1; 
			start = 0, end = (1<<30)-1; 
			left = right = nullptr;
		}
		Node(int l, int r) {
			val = 0;
			lazy = -1; 
			start = l; end = r; 
			left = right = nullptr;
		}
	};
	Node root;
	auto push_to_sons = [&](Node &v) {
		int x = v.lazy;
		int mid = (v.start+v.end)/2;
		int d = (v.end-v.start+1)/2;
		if (v.left == nullptr) v.left = new Node(v.start, mid);
		if (v.right == nullptr) v.right = new Node(mid+1, v.end);
		if (x == -1) return;
		(v.right)->val = x*d;
		(v.left)->val = x*d;
		(v.right)->lazy = x;
		(v.left)->lazy = x;
		v.lazy = -1;
	};
	function<void(int, int, int, Node &)> update = [&](int l, int r, int x, Node &v) {
		int a = v.start, b = v.end;	
		if (r < a || b < l) return;
		if (l <= a && b <= r) {
			v.val = (b-a+1)*x;
			v.lazy = x;
			return;
		}
		push_to_sons(v);
		update(l, r, x, *v.left); update(l, r, x, *v.right);
		v.val = (v.left)->val+(v.right)->val;
	};
	function<int(int, int, Node&)> query = [&](int l, int r, Node &v) {
		int a = v.start, b = v.end;	
		if (r < a || b < l) return 0;
		if (l <= a && b <= r) {
			return v.val;
		}
		push_to_sons(v);
		return query(l, r, *v.left) + query(l, r, *v.right);
	};
	while (m--) {
		int x, l, r;
		cin >> x >> l >> r;
		l += C; r += C;
		if (x == 2) {
			update(l, r, 1, root);	
		}
		else {
			cout << (C=query(l, r, root)) << '\n';
		}
	}
	function<void(Node &)> clean = [&](Node &v) {
		if (v.left == nullptr) {
			return;
		}
		clean(*v.left); clean(*v.right);
		delete v.left; delete v.right;
	};
	clean(root);

	return 0;
}

• Subtask 1: 100 / 100