Submission #870650

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
870650	2023-11-08T17:27:03 Z	Irate	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	249 ms	145280 KB

apple

#include<bits/stdc++.h>
using namespace std;
const int mxN = 6e6;
struct SegmentTree{
	vector<int>sTree, L, R;
	vector<bool>lazy;
	int nxt = 1;
	SegmentTree(){
		sTree.resize(mxN);
		L.resize(mxN);
		R.resize(mxN);
		lazy.resize(mxN);
	}
	void Propagate(int node, int l, int r){
		if(!lazy[node])return;
		sTree[node] = r - l + 1;
		if(l != r){
			if(!L[node])L[node] = ++nxt;
			if(!R[node])R[node] = ++nxt;
			lazy[L[node]] = 1;
			lazy[R[node]] = 1;
		}
		lazy[node] = 0;
	}
	void Update(int node, int l, int r, int ql, int qr){
		Propagate(node, l, r);
		if(ql <= l && r <= qr){
			lazy[node] = 1;
			Propagate(node, l, r);
			return;
		}
		if(ql > r || l > qr)return;
		int mid = (l + r) >> 1;
		if(!L[node])L[node] = ++nxt;
		if(!R[node])R[node] = ++nxt;
		Update(L[node], l, mid, ql, qr);
		Update(R[node], mid + 1, r, ql, qr);
		sTree[node] = sTree[L[node]] + sTree[R[node]]; 
	}
	int Query(int node, int l, int r, int ql, int qr){
		Propagate(node, l, r);
		if(ql <= l && r <= qr)return sTree[node];
		if(ql > r || l > qr)return 0;
		int mid = (l + r) >> 1;
		int lc = 0, rc = 0;
		if(L[node])lc = Query(L[node], l, mid, ql, qr);
		if(R[node])rc = Query(R[node], mid + 1, r, ql, qr);
		return lc + rc;
	}
};
int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int q, C = 0;
	cin >> q;
	SegmentTree tree;
	while(q--){
		int d, x, y;
		cin >> d >> x >> y;
		x += C;
		y += C;
		if(d == 1){
			int sum = tree.Query(1, 1, 1e9, x, y);
			cout << sum << "\n";
			C = sum;
		}
		else{
			tree.Update(1, 1, 1e9, x, y);	
		}
	}
}

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	13 ms	71512 KB	Output is correct
2	Correct	13 ms	71516 KB	Output is correct
3	Correct	10 ms	71516 KB	Output is correct
4	Correct	20 ms	71516 KB	Output is correct
5	Correct	22 ms	71516 KB	Output is correct
6	Correct	24 ms	71904 KB	Output is correct
7	Correct	23 ms	71516 KB	Output is correct
8	Correct	98 ms	71764 KB	Output is correct
9	Correct	194 ms	71932 KB	Output is correct
10	Correct	198 ms	71948 KB	Output is correct
11	Correct	202 ms	71804 KB	Output is correct
12	Correct	241 ms	72012 KB	Output is correct
13	Correct	226 ms	72368 KB	Output is correct
14	Correct	182 ms	72016 KB	Output is correct
15	Runtime error	249 ms	145280 KB	Execution killed with signal 11
16	Halted	0 ms	0 KB	-