Submission #344431

#	Time	Username	Problem	Language	Result	Execution time	Memory
344431		Tosic	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	358 ms	159468 KiB

apple

#include <bits/stdc++.h>
#define maxn 5000010
using namespace std;

int n, ans;
int tree[maxn], lChild[maxn], rChild[maxn], lazy[maxn], treeSize;

void makeL(int idx){
	if(!lChild[idx]){
			lChild[idx] = treeSize;
			++treeSize;
		}
}
void makeR(int idx){
	if(!rChild[idx]){
			rChild[idx] = treeSize;
			++treeSize;
		}
}

void prop(int idx, int l, int r){
	if(lazy[idx]){
		tree[idx] = r-l+1;
		lazy[idx] = 0;
		makeR(idx);
		makeL(idx);
		lazy[lChild[idx]] = 1;
		lazy[rChild[idx]] = 1;
	}

}

void upd(int idx, int l, int r, int ql, int qr){
	prop(idx, l, r);
	if(l >= ql and r<=qr){
		lazy[idx] = 1;
		prop(idx, l, r);
		return;
	}
	if(l > qr or r< ql){
		return;
	}
	makeL(idx);
	makeR(idx);
	int mid = (l+r)/2;
	upd(lChild[idx], l, mid, ql, qr);
	upd(rChild[idx], mid+1, r, ql, qr);
	tree[idx] = tree[rChild[idx]]+tree[lChild[idx]];
}

int cnt(int idx, int l, int r, int ql, int qr){
	prop(idx, l, r);
	if(l >= ql and r<= qr){
		return tree[idx];
	}
	if(r < ql or l > qr){
		return 0;
	}
	if(!tree[idx]){
		return 0;
	}
	int mid=(l+r)/2, res = 0;
	if(rChild[idx]){
		res += cnt(rChild[idx], mid+1, r, ql, qr);
	}
	if(lChild[idx]){
		res += cnt(lChild[idx], l, mid, ql, qr);
	}
	return res;
}

int main(){
	ios_base::sync_with_stdio(0);
	cout.tie(0);
	cin.tie(0);
	cin >> n;
	treeSize=1;
	for(int i = 0; i < n; ++i){
		int k,x,y;
		cin>>k;
		if(k == 1){
			cin>>x >>y;
			ans=cnt(0, 0, 1e9+1, x+ans, y+ans);
			cout << ans << '\n';
		} else {
			cin>> x>>y;
			upd(0, 0, 1e9+1, x+ans, y+ans);
		}
	}
}

• Subtask 1: 0 / 100