oj.uz

답안 #397300

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
397300 2021-05-01T20:46:35 Z ritul_kr_singh 원숭이와 사과 나무 (IZhO12_apple) C++17
0 / 100
 140 ms 48800 KB 
#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

# 결과 실행 시간 메모리 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 -