oj.uz

Submission #50893

# Submission time Handle Problem Language Result Execution time Memory
50893 2018-06-14T08:11:52 Z faishol27 Sterilizing Spray (JOI15_sterilizing) C++14
100 / 100
 1527 ms 307412 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;

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;
		
		push_pending(2*ind, l, mid);
		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++){
			ll tmp = segtree[2*ind].sum[i]+segtree[2*ind+1].sum[i];
			if(tmp > 0) segtree[ind].sum.PUB(tmp);
		}
		for(int i = min(sz_left, sz_right); i < max(sz_left, sz_right); i++){
			
			if(i < sz_left && segtree[2*ind].sum[i] > 0) segtree[ind].sum.PUB(segtree[2*ind].sum[i]);
			if(i < sz_right && segtree[2*ind+1].sum[i] > 0) 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){
	if(r < l_src || l > r_src) return;
	
	push_pending(ind, l, r);
	
	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 = segtree[2*ind].sum.size(),
		sz_right = 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(int ind){
	cerr << ind << " ->";
	for(auto elm:segtree[ind].sum) cerr << " " << elm ;
	cerr << endl;
}

ll BF(int id, ll a, ll b){
	ll ret = 0;
	if(id == 1) plate[a] = b;
	else if(id == 2){
		for(int i=a;i<=b;i++) plate[i] /= K;	
	}else{
		for(int i=a;i<=b;i++) ret += plate[i];
	}

	return ret;
}

void debug_segtree(int ind, int l, int r){
	print_segtree(ind);
	push_pending(ind, l, r);
	print_segtree(ind);

	ll hr = 0,
		st = -1;
	
	for(int i=l;i<=r;i++) hr += plate[i];
	if(!segtree[ind].sum.empty()) st = segtree[ind].sum.front();

	if(hr != st) cout << "B " << ind << " " << l << "-" << r << " -> " << hr << " " << st << " " << segtree[ind].pending << endl;
	else if(hr == st) cout <<l << "-" << r << " -> " << hr << endl;

	if(l == r) return;

	int mid = (l+r)/2;

	debug_segtree(2*ind, l, mid);
	debug_segtree(2*ind+1, mid+1, r);

	update_me(ind, l, r);
}

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

	build_segtree(1, 1, N);

	while(Q--){
		int id;
		ll a, b;
		cin >> id >> a >> b;
		
		if(id == 1){
			query1(1, 1, N, a, b);
		}else if(id == 2){
			query2(1, 1, N, a, b);
		}else{
			ans = 0;
			query3(1, 1, N, a, b);
			cout << ans << endl;
		}
	}

	return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 269 ms 272760 KB Output is correct
2 Correct 260 ms 272760 KB Output is correct
3 Correct 267 ms 272820 KB Output is correct
4 Correct 353 ms 273124 KB Output is correct
5 Correct 370 ms 273288 KB Output is correct
6 Correct 325 ms 273368 KB Output is correct
7 Correct 336 ms 273384 KB Output is correct
8 Correct 349 ms 273480 KB Output is correct
9 Correct 340 ms 273480 KB Output is correct
10 Correct 323 ms 273620 KB Output is correct
11 Correct 308 ms 273620 KB Output is correct
12 Correct 315 ms 273620 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 826 ms 274104 KB Output is correct
2 Correct 729 ms 274104 KB Output is correct
3 Correct 678 ms 274104 KB Output is correct
4 Correct 938 ms 274252 KB Output is correct
5 Correct 1006 ms 274504 KB Output is correct
6 Correct 961 ms 274504 KB Output is correct
7 Correct 1032 ms 274504 KB Output is correct
8 Correct 988 ms 274504 KB Output is correct
9 Correct 776 ms 274504 KB Output is correct
10 Correct 709 ms 274504 KB Output is correct
11 Correct 686 ms 274504 KB Output is correct
12 Correct 726 ms 274504 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 399 ms 274504 KB Output is correct
2 Correct 330 ms 274504 KB Output is correct
3 Correct 371 ms 274504 KB Output is correct
4 Correct 584 ms 274504 KB Output is correct
5 Correct 748 ms 274504 KB Output is correct
6 Correct 734 ms 274504 KB Output is correct
7 Correct 830 ms 274504 KB Output is correct
8 Correct 787 ms 274504 KB Output is correct
9 Correct 643 ms 274504 KB Output is correct
10 Correct 666 ms 274504 KB Output is correct
11 Correct 633 ms 274504 KB Output is correct
12 Correct 681 ms 274504 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 749 ms 274504 KB Output is correct
2 Correct 843 ms 275932 KB Output is correct
3 Correct 856 ms 279160 KB Output is correct
4 Correct 1135 ms 279436 KB Output is correct
5 Correct 1124 ms 281748 KB Output is correct
6 Correct 1341 ms 284412 KB Output is correct
7 Correct 1062 ms 286652 KB Output is correct
8 Correct 1258 ms 290256 KB Output is correct
9 Correct 1173 ms 293216 KB Output is correct
10 Correct 1221 ms 297416 KB Output is correct
11 Correct 1008 ms 297416 KB Output is correct
12 Correct 1527 ms 307412 KB Output is correct