Submission #397305

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
397305	2021-05-01T21:01:05 Z	ritul_kr_singh	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	523 ms	237940 KB

apple

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

const int LIM = 2e7;

struct SparseSegmentTree{
	vector<int> val, sum, c;
	int sz = 1, curr = 1;
	SparseSegmentTree(int n){
		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){
		if(r<=lx || rx<=l) return;
		push(x, lx, rx);
		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){
		if(r<=lx || rx<=l) return 0;
		if(l<=lx && rx<=r) return sum[x];
		push(x, lx, rx);
		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);

	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

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	127 ms	235072 KB	Output is correct
2	Correct	126 ms	235204 KB	Output is correct
3	Correct	124 ms	235076 KB	Output is correct
4	Correct	144 ms	235264 KB	Output is correct
5	Correct	148 ms	235292 KB	Output is correct
6	Correct	147 ms	235332 KB	Output is correct
7	Correct	151 ms	235236 KB	Output is correct
8	Correct	271 ms	235884 KB	Output is correct
9	Correct	449 ms	237264 KB	Output is correct
10	Correct	450 ms	237228 KB	Output is correct
11	Correct	451 ms	237204 KB	Output is correct
12	Correct	456 ms	237384 KB	Output is correct
13	Correct	439 ms	237636 KB	Output is correct
14	Correct	445 ms	237744 KB	Output is correct
15	Correct	523 ms	237940 KB	Output is correct
16	Correct	517 ms	237804 KB	Output is correct
17	Correct	439 ms	237660 KB	Output is correct
18	Correct	443 ms	237716 KB	Output is correct
19	Correct	519 ms	237764 KB	Output is correct
20	Correct	522 ms	237764 KB	Output is correct