Submission #853326

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
853326	2023-09-24T06:47:50 Z	serifefedartar	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	1081 ms	262144 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[60*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

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	32 ms	141148 KB	Output is correct
2	Correct	25 ms	141148 KB	Output is correct
3	Correct	25 ms	141140 KB	Output is correct
4	Correct	33 ms	141404 KB	Output is correct
5	Correct	35 ms	141400 KB	Output is correct
6	Correct	34 ms	141404 KB	Output is correct
7	Correct	35 ms	141496 KB	Output is correct
8	Correct	96 ms	142164 KB	Output is correct
9	Correct	179 ms	143308 KB	Output is correct
10	Correct	195 ms	143412 KB	Output is correct
11	Correct	190 ms	143396 KB	Output is correct
12	Correct	187 ms	143516 KB	Output is correct
13	Correct	169 ms	143652 KB	Output is correct
14	Correct	167 ms	141760 KB	Output is correct
15	Runtime error	1081 ms	262144 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-