Submission #988907

#	Time	Username	Problem	Language	Result	Execution time	Memory
988907		holagola	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	261 ms	188756 KiB

apple

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

struct Node {
	int sum, lazy, tl, tr, l, r;
	Node() : sum(0), lazy(0), l(-1), r(-1) {}
};

// [1,1e9] - indexed 1
struct SegTree {
	vector<Node> st;
	int cnt = 2;

	void build(int n) {
		st.assign(64 * 123456, Node());
		st[1].sum = 0;
		st[1].lazy = 0;
		st[1].tl = 1;
		st[1].tr = n;
	}

	void push_left(int node){
		if (st[node].l == -1) {
			st[node].l = cnt++;
			st[st[node].l].tl = st[node].tl;
			st[st[node].l].tr = (st[node].tl + st[node].tr) / 2;
		}
	}

	void push_right(int node){
		if (st[node].r == -1) {
			st[node].r = cnt++;
			st[st[node].r].tl = (st[node].tl + st[node].tr) / 2 + 1;
			st[st[node].r].tr = st[node].tr;
		}
	}

	void push_lazy(int node) {
		if (st[node].lazy) {
			st[node].sum = st[node].tr - st[node].tl + 1;
			push_left(node);
			push_right(node);
			st[st[node].l].lazy = st[st[node].r].lazy = 1;
			st[node].lazy = 0;
		}
	}

	void update(int l, int r, int node=1) {
		push_lazy(node);
		if (l == st[node].tl && r == st[node].tr) {
			st[node].lazy = 1;
			push_lazy(node);
		} else {
			int mid = (st[node].tl + st[node].tr) / 2;
			push_left(node);
			push_right(node);

			if (l > mid) update(l, r,st[node].r);
			else if (r <= mid) update(l, r,st[node].l);
			else {
				update(l, mid, st[node].l);
				update(mid + 1, r, st[node].r);
			}

			push_lazy(st[node].l);
			push_lazy(st[node].r);
			st[node].sum = st[st[node].l].sum + st[st[node].r].sum;
		}
	}

	int query(int l, int r, int node=1) {
		push_lazy(node);
		if (l == st[node].tl && r == st[node].tr) return st[node].sum;
		int mid = (st[node].tl + st[node].tr) / 2;
		push_left(node);
		push_right(node);

		if (l > mid) return query(l, r, st[node].r);
		else if (r <= mid) return query(l, r, st[node].l);
		else return query(l, mid, st[node].l) + query(mid + 1, r, st[node].r);
	}
};

int main() {
	iostream::sync_with_stdio(false);cin.tie(nullptr);
	int q;cin>>q;
	int op,l,r,c=0;
	SegTree st;
	st.build(1e9);
	while(q--){
		cin>>op>>l>>r;
		if(op==1){
			c=st.query(l+c,r+c);
			cout<<c<<"\n";
		}else{
			st.update(l+c,r+c);
		}
	}
	return 0;
}

• Subtask 1: 100 / 100