Submission #736808

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
736808	2023-05-06T08:50:31 Z	MODDI	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	406 ms	188596 KB

apple

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<long long, long long> pll;
typedef pair<int,int> pii;
typedef vector<long long> vl;
typedef vector<int> vi;
struct Node{
	int sum, lazy, tl, tr, l, r;
	Node() : sum(0), lazy(0), l(-1), r(-1){}
};
Node tree[64 * 123456];
int cnt = 2;
void push_lazy(int node){
	if(tree[node].lazy){
		tree[node].sum= tree[node].tr - tree[node].tl + 1;
		int mid = (tree[node].tl + tree[node].tr) / 2;
		if(tree[node].l == -1){
			tree[node].l = cnt++;
			tree[tree[node].l].tl = tree[node].tl;
			tree[tree[node].l].tr = mid;
		}
		if(tree[node].r == -1){
			tree[node].r = cnt++;
			tree[tree[node].r].tl = mid+1;
			tree[tree[node].r].tr = tree[node].tr;
		}
		tree[tree[node].l].lazy = tree[tree[node].r].lazy = 1;
		tree[node].lazy = 0;
	}
}
void update(int node, int l, int r){
	push_lazy(node);
	if(l == tree[node].tl && tree[node].tr == r){
		tree[node].lazy = 1;
		push_lazy(node);
	}
	else{
		int mid = (tree[node].tl + tree[node].tr) / 2;
		if(tree[node].l == -1){
			tree[node].l = cnt++;
			tree[tree[node].l].tl = tree[node].tl;
			tree[tree[node].l].tr = mid;
		}
		if(tree[node].r == -1){
			tree[node].r = cnt++;
			tree[tree[node].r].tl = mid+1;
			tree[tree[node].r].tr = tree[node].tr;
		}
		if(l > mid)	update(tree[node].r, l, r);
		else if(r <= mid)	update(tree[node].l, l, r);
		else{
			update(tree[node].l, l, mid);
			update(tree[node].r, mid+1, r);
		}
		push_lazy(tree[node].l);
		push_lazy(tree[node].r);
		tree[node].sum = tree[tree[node].l].sum + tree[tree[node].r].sum;
	}
}
int query(int node, int l, int r){
	push_lazy(node);
	if(l == tree[node].tl && r == tree[node].tr){
		return tree[node].sum;	
	}
	else{
		int mid = (tree[node].tl + tree[node].tr )/2;
		if(tree[node].l == -1){
			tree[node].l = cnt++;
			tree[tree[node].l].tl = tree[node].tl;
			tree[tree[node].l].tr = mid;
		}
		if(tree[node].r == -1){
			tree[node].r = cnt++;
			tree[tree[node].r].tl = mid+1;
			tree[tree[node].r].tr = tree[node].tr;
		}
		if(l > mid)	return query(tree[node].r, l, r);
		else if(r <= mid)	return query(tree[node].l, l, r);
		else{
			return query(tree[node].l, l, mid) + query(tree[node].r, mid+1, r);
		}
	}
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin>>n;
	tree[1].sum = 0;
	tree[1].lazy = 0;
	tree[1].tl = 1;
	tree[1].tr = 1e9;
	int c = 0;
	while(n--){
		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	83 ms	185804 KB	Output is correct
2	Correct	79 ms	185800 KB	Output is correct
3	Correct	79 ms	185768 KB	Output is correct
4	Correct	95 ms	185932 KB	Output is correct
5	Correct	93 ms	186020 KB	Output is correct
6	Correct	93 ms	186004 KB	Output is correct
7	Correct	96 ms	186008 KB	Output is correct
8	Correct	202 ms	186892 KB	Output is correct
9	Correct	309 ms	187968 KB	Output is correct
10	Correct	333 ms	187956 KB	Output is correct
11	Correct	334 ms	187900 KB	Output is correct
12	Correct	334 ms	187952 KB	Output is correct
13	Correct	298 ms	188380 KB	Output is correct
14	Correct	305 ms	188320 KB	Output is correct
15	Correct	398 ms	188488 KB	Output is correct
16	Correct	387 ms	188596 KB	Output is correct
17	Correct	312 ms	188436 KB	Output is correct
18	Correct	289 ms	188420 KB	Output is correct
19	Correct	406 ms	188544 KB	Output is correct
20	Correct	398 ms	188424 KB	Output is correct