답안 #397305

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
397305 2021-05-01T21:01:05 Z ritul_kr_singh 원숭이와 사과 나무 (IZhO12_apple) C++17
100 / 100
523 ms 237940 KB
#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);
	}
}
# 결과 실행 시간 메모리 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