Submission #736808

#	Time	Username	Problem	Language	Result	Execution time	Memory
736808		MODDI	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	406 ms	188596 KiB

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 / 100