Submission #397300

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
397300	2021-05-01T20:46:35 Z	ritul_kr_singh	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	140 ms	48800 KB

apple

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define sp << ' ' <<
#define nl << endl

struct SparseSegmentTree{
	vector<int> val, sum, c;
	int sz = 1, curr = 1; const int ID = 1e18;
	SparseSegmentTree(int n, int lim){
		while(sz < n) sz += sz;
		sum.resize(lim);
		val.resize(lim);
		c.assign(lim, -1);
	}

	void push(int x, int lx, int rx){
		if(rx-lx==1) return;
		int mx = (lx + rx) / 2;
		if(c[x] < 0) c[x] = curr, curr += 2;

		if(val[x]){
			val[c[x]] = val[c[x]+1] = 1;
			sum[c[x]] = sum[c[x]+1] = (rx - mx);
			val[x] = 0;
		}
		sum[x] = sum[c[x]] + sum[c[x]+1];
	}

	void rangeAssign(int l, int r, int x, int lx, int rx){
		push(x, lx, rx);
		if(r<=lx || rx<=l) return;
		if(l<=lx && rx<=r){
			val[x] = 1;
			sum[x] = rx - lx;
			return;
		}
		int mx = (lx + rx) / 2;
		rangeAssign(l, r, c[x], lx, mx);
		rangeAssign(l, r, c[x]+1, mx, rx);
		sum[x] = sum[c[x]] + sum[c[x]+1];
	}
	void rangeAssign(int l, int r){ rangeAssign(l, r+1, 0, 0, sz); }
	int rangeSum(int l, int r, int x, int lx, int rx){
		push(x, lx, rx);
		if(r<=lx || rx<=l) return 0;
		if(l<=lx && rx<=r) return sum[x];
		int mx = (lx + rx) / 2;
		return rangeSum(l, r, c[x], lx, mx) + rangeSum(l, r, c[x]+1, mx, rx);
	}
	int rangeSum(int l, int r){ return rangeSum(l, r+1, 0, 0, sz); }
};

signed main(){
	cin.tie(0)->sync_with_stdio(0);
	int m, c = 0, t, l, r; cin >> m;

	SparseSegmentTree st((int)1e9+1, (int)1e6);

	while(m--){
		cin >> t >> l >> r; --l, --r;
		l += c, r += c;
		if(t==1) cout << (c = st.rangeSum(l, r)) nl;
		else st.rangeAssign(l, r);
	}
}

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	14 ms	23756 KB	Output is correct
2	Correct	14 ms	23744 KB	Output is correct
3	Correct	14 ms	23744 KB	Output is correct
4	Correct	37 ms	23972 KB	Output is correct
5	Correct	42 ms	23976 KB	Output is correct
6	Correct	42 ms	23884 KB	Output is correct
7	Correct	41 ms	23940 KB	Output is correct
8	Runtime error	140 ms	48800 KB	Execution killed with signal 11
9	Halted	0 ms	0 KB	-