Submission #344431

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
344431	2021-01-05T19:24:00 Z	Tosic	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	358 ms	159468 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]){
		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.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	14 ms	3564 KB	Output is correct
5	Correct	17 ms	4204 KB	Output is correct
6	Correct	17 ms	4076 KB	Output is correct
7	Correct	17 ms	4204 KB	Output is correct
8	Correct	146 ms	29952 KB	Output is correct
9	Correct	321 ms	51128 KB	Output is correct
10	Correct	322 ms	56556 KB	Output is correct
11	Correct	329 ms	60524 KB	Output is correct
12	Correct	358 ms	62444 KB	Output is correct
13	Correct	287 ms	72684 KB	Output is correct
14	Correct	274 ms	73196 KB	Output is correct
15	Runtime error	319 ms	159468 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
16	Halted	0 ms	0 KB	-