Submission #853327

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
853327	2023-09-24T06:49:06 Z	serifefedartar	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	244 ms	214404 KB

apple

#include <bits/stdc++.h>
using namespace std;
 
#define fast ios::sync_with_stdio(0);cin.tie(0);
#define s second
#define f first
typedef long long ll;
const ll MOD = 1e9 + 7;
const ll LOGN = 20;
const ll MAXN = 1e5 + 5;

struct Node {
	int l, r, sum;
	bool lazy;
	int left, right;
	Node(int a, int b) : l(a), r(b), sum(0), lazy(0), left(-1), right(-1) { }
	Node() : l(-1), r(-1), sum(0), lazy(0), left(-1), right(-1) { }
};
Node sg[90*MAXN];
int no = 2;

void add(int x) {
	if (sg[x].left == -1 && sg[x].l != sg[x].r) {
		int mid = (sg[x].l + sg[x].r) / 2;
		sg[x].left = no;
		sg[x].right = no+1;
		sg[no++] = Node(sg[x].l, mid);
		sg[no++] = Node(mid+1, sg[x].r);
	}
}

void push(int x) {
	if (sg[x].lazy) {
		sg[x].sum = sg[x].r - sg[x].l + 1;
		if (sg[x].l != sg[x].r) {
			add(x);
			sg[sg[x].left].lazy = 1;
			sg[sg[x].left].sum = sg[sg[x].left].r - sg[sg[x].left].l + 1;
			sg[sg[x].right].lazy = 1;
			sg[sg[x].right].sum = sg[sg[x].right].r - sg[sg[x].right].l + 1;
		}
		sg[x].lazy = 0;
	}
}

void update(int x, int a, int b) {
	if (sg[x].l > b || a > sg[x].r)
		return ;
	if (a <= sg[x].l && sg[x].r <= b) {
		sg[x].lazy = 1;
		push(x);
		return ;
	}
	add(x);
	push(x);
	update(sg[x].left, a, b);
	update(sg[x].right, a, b);
	sg[x].sum = sg[sg[x].left].sum + sg[sg[x].right].sum; 
}

int query(int x, int a, int b) {
	if (sg[x].l > b || a > sg[x].r)
		return 0;
	push(x);
	if (a <= sg[x].l && sg[x].r <= b)
		return sg[x].sum;
	add(x);
	return query(sg[x].left, a, b) + query(sg[x].right, a, b);
}

int M, D, X, Y, C = 0;
int main() {
	fast
	cin >> M;

	sg[1] = Node(1, 1e9); 
	while (M--) {
		cin >> D >> X >> Y;
		if (D == 1) {
			C = query(1, X + C, Y + C);
			cout << C << "\n";
		} else
			update(1, X + C, Y + C);
	}
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	44 ms	211792 KB	Output is correct
2	Correct	38 ms	211536 KB	Output is correct
3	Correct	40 ms	212140 KB	Output is correct
4	Correct	46 ms	211788 KB	Output is correct
5	Correct	47 ms	211816 KB	Output is correct
6	Correct	48 ms	211796 KB	Output is correct
7	Correct	48 ms	211796 KB	Output is correct
8	Correct	105 ms	211788 KB	Output is correct
9	Correct	199 ms	212304 KB	Output is correct
10	Correct	202 ms	212052 KB	Output is correct
11	Correct	205 ms	212304 KB	Output is correct
12	Correct	201 ms	212048 KB	Output is correct
13	Correct	180 ms	212048 KB	Output is correct
14	Correct	176 ms	212048 KB	Output is correct
15	Correct	243 ms	214352 KB	Output is correct
16	Correct	244 ms	214364 KB	Output is correct
17	Correct	206 ms	214352 KB	Output is correct
18	Correct	188 ms	214352 KB	Output is correct
19	Correct	242 ms	214404 KB	Output is correct
20	Correct	242 ms	214216 KB	Output is correct