Submission #870653

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
870653	2023-11-08T17:31:54 Z	Irate	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	304 ms	119968 KB

apple

#include<bits/stdc++.h>
using namespace std;
const int mxN = 1e7;
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

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	22 ms	118868 KB	Output is correct
2	Correct	16 ms	118872 KB	Output is correct
3	Correct	17 ms	118996 KB	Output is correct
4	Correct	26 ms	118892 KB	Output is correct
5	Correct	27 ms	119128 KB	Output is correct
6	Correct	28 ms	119124 KB	Output is correct
7	Correct	27 ms	119128 KB	Output is correct
8	Correct	104 ms	119132 KB	Output is correct
9	Correct	202 ms	119468 KB	Output is correct
10	Correct	200 ms	119376 KB	Output is correct
11	Correct	205 ms	119616 KB	Output is correct
12	Correct	213 ms	119332 KB	Output is correct
13	Correct	202 ms	119476 KB	Output is correct
14	Correct	191 ms	119968 KB	Output is correct
15	Correct	272 ms	119544 KB	Output is correct
16	Correct	279 ms	119404 KB	Output is correct
17	Correct	192 ms	119380 KB	Output is correct
18	Correct	195 ms	119512 KB	Output is correct
19	Correct	304 ms	119632 KB	Output is correct
20	Correct	292 ms	119348 KB	Output is correct