oj.uz

Submission #50891

# Submission time Handle Problem Language Result Execution time Memory
50891 2018-06-14T05:44:24 Z faishol27 Sterilizing Spray (JOI15_sterilizing) C++14
10 / 100
 814 ms 274520 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, maksi;
int plate[100005];
child segtree[MAXE];
ll ans;

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);
}

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";
}

void build_segtree(int ind, int l, int r){
	maksi = max(ind, maksi);

	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;
	
}

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;
		}

		//print_segtree();
	}

	return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 268 ms 273016 KB Output is correct
2 Correct 254 ms 273016 KB Output is correct
3 Incorrect 253 ms 273016 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 704 ms 273592 KB Output is correct
2 Correct 651 ms 273764 KB Output is correct
3 Correct 582 ms 273820 KB Output is correct
4 Correct 698 ms 273928 KB Output is correct
5 Correct 794 ms 273928 KB Output is correct
6 Correct 798 ms 274180 KB Output is correct
7 Correct 814 ms 274180 KB Output is correct
8 Correct 789 ms 274180 KB Output is correct
9 Correct 652 ms 274180 KB Output is correct
10 Correct 704 ms 274180 KB Output is correct
11 Correct 730 ms 274180 KB Output is correct
12 Correct 644 ms 274180 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 377 ms 274180 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Incorrect 716 ms 274520 KB Output isn't correct
2 Halted 0 ms 0 KB -