Submission #433511

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
433511	2021-06-20T02:01:01 Z	john256	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	542 ms	188528 KB

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) {}
};

const int MAXN = 123456;
Node segtree[64 * MAXN];
int cnt = 2;

void push_lazy(int node) {
	if(segtree[node].lazy) {
		segtree[node].sum = segtree[node].tr - segtree[node].tl + 1;
		int mid = (segtree[node].tl + segtree[node].tr) / 2;
		if(segtree[node].l == -1) {
			segtree[node].l = cnt++;
			segtree[segtree[node].l].tl = segtree[node].tl;
			segtree[segtree[node].l].tr = mid;
		}
		if(segtree[node].r == -1) {
			segtree[node].r = cnt++;
			segtree[segtree[node].r].tl = mid + 1;
			segtree[segtree[node].r].tr = segtree[node].tr;
		}
		segtree[segtree[node].l].lazy = segtree[segtree[node].r].lazy = 1;
		segtree[node].lazy = 0;
	}
}

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

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

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

int query(int node, int l, int r) {
	push_lazy(node);
	if(l == segtree[node].tl && r == segtree[node].tr) 
		return segtree[node].sum;
	else {
		int mid = (segtree[node].tl + segtree[node].tr) / 2;
		if(segtree[node].l == -1) {
			segtree[node].l = cnt++;
			segtree[segtree[node].l].tl = segtree[node].tl;
			segtree[segtree[node].l].tr = mid;
		}
		if(segtree[node].r == -1) {
			segtree[node].r = cnt++;
			segtree[segtree[node].r].tl = mid + 1;
			segtree[segtree[node].r].tr = segtree[node].tr;
		}

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

int main() {
	iostream::sync_with_stdio(false); cin.tie(0);
	int m;
	cin >> m;

	segtree[1].sum = 0; segtree[1].lazy = 0;
	segtree[1].tl = 1; segtree[1].tr = 1e9;

	int c = 0;
	for(int j=0; j<m; j++) {
		int d, x, y;
		cin >> d >> x >> y;
		if(d == 1) {
			c = query(1, x + c, y + c);
			cout << c << '\n';
		} 
		else 
			update(1, x + c, y + c);
	}
	return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	106 ms	185812 KB	Output is correct
2	Correct	117 ms	185760 KB	Output is correct
3	Correct	104 ms	185844 KB	Output is correct
4	Correct	124 ms	185924 KB	Output is correct
5	Correct	139 ms	186012 KB	Output is correct
6	Correct	124 ms	186000 KB	Output is correct
7	Correct	126 ms	186064 KB	Output is correct
8	Correct	292 ms	186896 KB	Output is correct
9	Correct	429 ms	187932 KB	Output is correct
10	Correct	421 ms	187948 KB	Output is correct
11	Correct	416 ms	188116 KB	Output is correct
12	Correct	485 ms	188032 KB	Output is correct
13	Correct	396 ms	188416 KB	Output is correct
14	Correct	400 ms	188376 KB	Output is correct
15	Correct	512 ms	188408 KB	Output is correct
16	Correct	522 ms	188424 KB	Output is correct
17	Correct	410 ms	188416 KB	Output is correct
18	Correct	392 ms	188388 KB	Output is correct
19	Correct	542 ms	188492 KB	Output is correct
20	Correct	513 ms	188528 KB	Output is correct