Submission #472078

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
472078	2021-09-12T19:41:42 Z	disastah	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	477 ms	134392 KB

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	1 ms	308 KB	Output is correct
4	Correct	22 ms	4640 KB	Output is correct
5	Correct	20 ms	4676 KB	Output is correct
6	Correct	21 ms	4648 KB	Output is correct
7	Correct	20 ms	4656 KB	Output is correct
8	Correct	150 ms	33920 KB	Output is correct
9	Correct	302 ms	67868 KB	Output is correct
10	Correct	338 ms	67452 KB	Output is correct
11	Correct	323 ms	67452 KB	Output is correct
12	Correct	326 ms	67416 KB	Output is correct
13	Correct	343 ms	134392 KB	Output is correct
14	Correct	350 ms	134224 KB	Output is correct
15	Correct	455 ms	133224 KB	Output is correct
16	Correct	459 ms	133204 KB	Output is correct
17	Correct	338 ms	134216 KB	Output is correct
18	Correct	375 ms	134260 KB	Output is correct
19	Correct	477 ms	133036 KB	Output is correct
20	Correct	466 ms	133028 KB	Output is correct