Submission #397301

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
397301	2021-05-01T20:47:52 Z	ritul_kr_singh	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	319 ms	97180 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)2e9, (int)2e6);

	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	24 ms	47180 KB	Output is correct
2	Correct	24 ms	47172 KB	Output is correct
3	Correct	25 ms	47200 KB	Output is correct
4	Correct	46 ms	47300 KB	Output is correct
5	Correct	52 ms	47424 KB	Output is correct
6	Correct	56 ms	47360 KB	Output is correct
7	Correct	51 ms	47308 KB	Output is correct
8	Correct	218 ms	47688 KB	Output is correct
9	Runtime error	319 ms	97180 KB	Execution killed with signal 11
10	Halted	0 ms	0 KB	-