Submission #344426

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
344426	2021-01-05T19:22:03 Z	Tosic	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	263 ms	77292 KB

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] == (r-l+1) ){
		return min(qr-ql+1,min(qr-l+1, r-ql+1));
	}
	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

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	10 ms	2284 KB	Output is correct
5	Correct	12 ms	2636 KB	Output is correct
6	Correct	13 ms	2668 KB	Output is correct
7	Correct	14 ms	2796 KB	Output is correct
8	Correct	85 ms	18668 KB	Output is correct
9	Correct	210 ms	33260 KB	Output is correct
10	Correct	201 ms	36172 KB	Output is correct
11	Correct	192 ms	38380 KB	Output is correct
12	Correct	197 ms	39276 KB	Output is correct
13	Correct	180 ms	41452 KB	Output is correct
14	Correct	180 ms	42348 KB	Output is correct
15	Correct	242 ms	75776 KB	Output is correct
16	Correct	250 ms	76012 KB	Output is correct
17	Correct	179 ms	43628 KB	Output is correct
18	Correct	222 ms	43632 KB	Output is correct
19	Correct	263 ms	77292 KB	Output is correct
20	Correct	247 ms	77292 KB	Output is correct