oj.uz

Submission #870652

# Submission time Handle Problem Language Result Execution time Memory
870652 2023-11-08T17:29:46 Z Irate Monkey and Apple-trees (IZhO12_apple) C++14
0 / 100
 142 ms 48816 KB 
#include<bits/stdc++.h>
using namespace std;
const int mxN = 2e6;
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 6 ms 24152 KB Output is correct
2 Correct 5 ms 24152 KB Output is correct
3 Correct 6 ms 24188 KB Output is correct
4 Correct 14 ms 24152 KB Output is correct
5 Correct 16 ms 24492 KB Output is correct
6 Correct 16 ms 24216 KB Output is correct
7 Correct 16 ms 24156 KB Output is correct
8 Correct 86 ms 24268 KB Output is correct
9 Runtime error 142 ms 48816 KB Execution killed with signal 11
10 Halted 0 ms 0 KB -