oj.uz

답안 #50892

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
50892 2018-06-14T05:57:12 Z faishol27 Sterilizing Spray (JOI15_sterilizing) C++14
10 / 100
 1174 ms 274068 KB 
////////////////////////////////////////////////
//                                            //
//  Author: Muhammad Faishol Amirul Mukminin  //
//                                            //
////////////////////////////////////////////////
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define PUB push_back
#define POF pop_front

const int MAXE = 4e5+5;

struct child{
	deque<ll>sum;
	int pending;
};

int N, Q, K;
int plate[100005];
child segtree[MAXE];
ll ans;
bool isValid[MAXE];

void push_pending(int ind, int l, int r){
	if(segtree[ind].pending != 0){
		if(l != r){
			segtree[2*ind].pending += segtree[ind].pending;
			segtree[2*ind+1].pending += segtree[ind].pending;
		}

		while(segtree[ind].pending > 0 && !segtree[ind].sum.empty() && K > 1){
			segtree[ind].sum.POF();
			segtree[ind].pending--;
		}
		segtree[ind].pending = 0;
	}

}

void update_me(int ind, int l, int r){
	if(l != r){
		int mid = (l+r)/2;
		if(segtree[2*ind].pending > 0) push_pending(2*ind, l, mid);
		if(segtree[2*ind+1].pending > 0) push_pending(2*ind+1, mid+1, r);

		int sz_left = segtree[2*ind].sum.size(),
			sz_right = segtree[2*ind+1].sum.size();
		
		segtree[ind].sum.clear();

		for(int i=0; i < min(sz_left, sz_right); i++){
			segtree[ind].sum.PUB(segtree[2*ind].sum[i]+segtree[2*ind+1].sum[i]);
		}
		for(int i = min(sz_left, sz_right); i < max(sz_left, sz_right); i++){
			if(i < sz_left) segtree[ind].sum.PUB(segtree[2*ind].sum[i]);
			if(i < sz_right) segtree[ind].sum.PUB(segtree[2*ind+1].sum[i]);
		}
		segtree[ind].pending = 0;
	}
}

void query1(int ind, int l, int r, int i_src, ll val){
	push_pending(ind, l, r);
	
	if(l == r){
		segtree[ind].sum.clear();
		while(val > 0){
			segtree[ind].sum.PUB(val);
			val /= K;
	
			if(K==1) break;
		}
	
		segtree[ind].pending = 0;
		return;
	}
	
	int mid = (l+r)/2;
	if(i_src <= mid) query1(2*ind, l, mid, i_src, val);
	else query1(2*ind+1, mid+1, r, i_src, val);
	
	update_me(ind, l, r);
}

void query2(int ind, int l, int r, int l_src, int r_src){
	push_pending(ind, l, r);
	
	if(r < l_src || l > r_src) return;

	if(l_src <= l && r <= r_src){
		segtree[ind].pending += 1;
		return;
	}
	
	int mid = (l+r)/2;
	query2(2*ind, l, mid, l_src, r_src);
	query2(2*ind+1, mid+1, r, l_src, r_src);
	
	update_me(ind, l, r);
}

void query3(int ind, int l, int r, int l_src, int r_src){
	push_pending(ind, l, r);

	if(r < l_src || l > r_src) return;

	if(l_src <= l && r <= r_src){
		if(!segtree[ind].sum.empty()) ans += segtree[ind].sum.front();
		return;
	}

	int mid = (l+r)/2;
	query3(2*ind, l, mid, l_src, r_src);
	query3(2*ind+1, mid+1, r, l_src, r_src);

	update_me(ind, l, r);
}

void build_segtree(int ind, int l, int r){
	if(l == r){
		ll tmp = plate[l];
		while(tmp > 0){
			segtree[ind].sum.PUB(tmp);
			tmp /= K;

			if(K == 1) break;
		}

		segtree[ind].pending = 0;
		return;
	}

	int mid = (l+r)/2;

	build_segtree(2*ind, l, mid);
	build_segtree(2*ind+1, mid+1, r);
	
	int sz_left = min(segtree[2*ind].sum.size(), segtree[2*ind+1].sum.size()),
		sz_right = max(segtree[2*ind].sum.size(), segtree[2*ind+1].sum.size());
	
	for(int i=0; i < min(sz_left, sz_right); i++){
		segtree[ind].sum.PUB(segtree[2*ind].sum[i]+segtree[2*ind+1].sum[i]);
	}
	for(int i = min(sz_left, sz_right); i < max(sz_left, sz_right); i++){
		if(i < sz_left) segtree[ind].sum.PUB(segtree[2*ind].sum[i]);
		if(i < sz_right) segtree[ind].sum.PUB(segtree[2*ind+1].sum[i]);
	}

	segtree[ind].pending = 0;
	
}

void print_segtree(){
	cout << "========\n";
	// for(int i=1;i<=maksi;i++){
	// 	cout << i << " -> " << segtree[i].pending << " -> ";
	// 	//cout << segtree[i].sum.size() << endl;
	// 	for(auto elm:segtree[i].sum) cout << " " << elm;
	// 	cout << endl;
	// }

	for(int i=1;i<=N;i++){
		ans = 0;
		query3(1,1,N,i,i);
		cout << i << " -> " << ans << endl;
	}
	cout << "========\n";
}

int main(){
	cin >> N >> Q >> K;
	for(int i=1;i<=N;i++)
		cin >> plate[i];

	build_segtree(1, 1, N);
	// print_segtree();
	// cout << maksi << endl;
	while(Q--){
		int id;
		ll a, b;
		cin >> id >> a >> b;
		
		if(id == 1){
			assert(1 <= a && a <= N);
			assert(0 <= b && b <= 1000000000);
			
			query1(1, 1, N, a, b);
		}else if(id == 2){
			assert(1 <= a && a <= b && b <= N);

			query2(1, 1, N, a, b);
		}else{
			assert(1 <= a && a <= b && b <= N);
			
			ans = 0;
			query3(1, 1, N, a, b);
			cout << ans << endl;
		}

		//debug_segtree();
	}

	return 0;
}

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 261 ms 272760 KB Output is correct
2 Correct 272 ms 272960 KB Output is correct
3 Incorrect 265 ms 272960 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 871 ms 273616 KB Output is correct
2 Correct 755 ms 273652 KB Output is correct
3 Correct 711 ms 273652 KB Output is correct
4 Correct 829 ms 273924 KB Output is correct
5 Correct 1174 ms 274044 KB Output is correct
6 Correct 1020 ms 274044 KB Output is correct
7 Correct 978 ms 274044 KB Output is correct
8 Correct 1082 ms 274068 KB Output is correct
9 Correct 740 ms 274068 KB Output is correct
10 Correct 842 ms 274068 KB Output is correct
11 Correct 756 ms 274068 KB Output is correct
12 Correct 743 ms 274068 KB Output is correct

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 391 ms 274068 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 811 ms 274068 KB Output isn't correct
2 Halted 0 ms 0 KB -