Submission #472078

#	Time	Username	Problem	Language	Result	Execution time	Memory
472078		disastah	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	477 ms	134392 KiB

apple

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define ar array
using namespace std;
typedef long double ld;
typedef long long ll;
const int inf=1e9+9;
const ll linf=4e18+18;
const int N=1e9;

struct segtr {
	struct node {
		int x=0, l=-1, r=-1;
		bool lz=0;
		node() {}
	};
	vector<node> t;
	int N;
	segtr(int n): N(n) {
		t={{}};
	}
	void push(int v, int l, int r) {
		if (l+1<r) {
			if (t[v].l==-1) {
				t[v].l=t.size();
				t.push_back({});
			}
			if (t[v].r==-1) {
				t[v].r=t.size();
				t.push_back({});
			}
		}
		if (!t[v].lz) return;
		t[v].x=r-l;
		if (l+1<r) t[t[v].l].lz=t[t[v].r].lz=1;
		t[v].lz=0;
	}
	void upd(int v, int tl, int tr, int l, int r) {
		push(v,tl,tr);
		if (l>=r) return;
		if (tl==l&&tr==r) {
			t[v].lz=1, push(v,l,r);
		}
		else {
			int tm=(tl+tr)/2;
			upd(t[v].l,tl,tm,l,min(r,tm));
			upd(t[v].r,tm,tr,max(l,tm),r);
			t[v].x=t[t[v].l].x+t[t[v].r].x;
		}
	} void upd(int l, int r) {upd(0,0,N,l,r);}
	int sum(int v, int tl, int tr, int l, int r) {
		push(v,tl,tr);
		if (l>=r) return 0;
		if (tl==l&&tr==r) return t[v].x;
		int tm=(tl+tr)/2;
		return sum(t[v].l,tl,tm,l,min(r,tm))+sum(t[v].r,tm,tr,max(l,tm),r);
	} int sum(int l, int r) {return sum(0,0,N,l,r);}
};

int q;

void solve() {
	cin >> q;
	int C=0;
	segtr tr(N);
	while(q--) {
		int t, l, r; cin >> t >> l >> r; --l;
		if (t==1) {
			C=tr.sum(l+C,r+C);
			cout << C << "\n";
		}
		else tr.upd(l+C,r+C);
	}
}

signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
#ifdef disastah
	cout << "Output\n\n";
#endif
/*#ifndef disastah
	freopen("snowcow.in","r",stdin);
	freopen("snowcow.out","w",stdout);
#endif*/
	int tt=1;
//	cin >> tt;
	while (tt--) {
		solve();
	}
}

• Subtask 1: 100 / 100