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
#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;
}
# 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