Submission #397305

#	Time	Username	Problem	Language	Result	Execution time	Memory
397305		ritul_kr_singh	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	523 ms	237940 KiB

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 / 100