Submission #344432

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
344432	2021-01-05T19:24:54 Z	Tosic	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	249 ms	75756 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(min(qr-l+1, r-ql+1), qr-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	11 ms	2156 KB	Output is correct
5	Correct	12 ms	2540 KB	Output is correct
6	Correct	12 ms	2540 KB	Output is correct
7	Correct	13 ms	2540 KB	Output is correct
8	Correct	88 ms	17900 KB	Output is correct
9	Correct	182 ms	31724 KB	Output is correct
10	Correct	190 ms	34540 KB	Output is correct
11	Correct	191 ms	36716 KB	Output is correct
12	Correct	191 ms	37612 KB	Output is correct
13	Correct	175 ms	39532 KB	Output is correct
14	Correct	184 ms	40300 KB	Output is correct
15	Correct	242 ms	74092 KB	Output is correct
16	Correct	249 ms	74252 KB	Output is correct
17	Correct	185 ms	42016 KB	Output is correct
18	Correct	175 ms	42080 KB	Output is correct
19	Correct	246 ms	75732 KB	Output is correct
20	Correct	243 ms	75756 KB	Output is correct