Submission #50777

#	Time	Username	Problem	Language	Result	Execution time	Memory
50777		faishol27	Sterilizing Spray (JOI15_sterilizing)	C++14	0 / 100	38 ms	7324 KiB

sterilizing

////////////////////////////////////////////////
//                                            //
//  Author: Muhammad Faishol Amirul Mukminin  //
//                                            //
////////////////////////////////////////////////
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define BTW(x,a,b) a <= x && x <= b

const int MAXE = 4e5+5;

struct child{
	ll sum, minus;
	bool pending;
};

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

void build_segtree(int ind, int l, int r){
	if(l == r){
		segtree[ind].sum = plate[l];
		segtree[ind].minus = plate[l]%K;
		segtree[ind].pending = 0;
		return;
	}

	int mid = (l+r)/2;

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

	segtree[ind].sum = segtree[2*ind].sum + segtree[2*ind+1].sum;
	segtree[ind].minus = segtree[2*ind].minus + segtree[2*ind+1].minus;
	segtree[ind].pending = 0;
}

void push_pending(int ind){
	segtree[ind].pending = 0;
	segtree[ind].sum = (segtree[ind].sum-segtree[ind].minus)/K;
	segtree[ind].minus = 0;

	if(segtree[2*ind].pending == 1 && 2*ind < MAXE) push_pending(2*ind);
	if(segtree[2*ind+1].pending == 1 && 2*ind+1 < MAXE) push_pending(2*ind+1);

	segtree[2*ind].pending = 1;
	segtree[2*ind+1].pending = 1;
}

void update_me(int ind){
	segtree[ind].sum = 0;
	segtree[ind].minus = 0;
	segtree[ind].pending = 0;

	if(segtree[2*ind].pending == 1){
		segtree[ind].sum += (segtree[2*ind].sum-segtree[2*ind].minus)/K;
	}else{
		segtree[ind].sum += segtree[2*ind].sum;
		segtree[ind].minus += segtree[2*ind].minus;
	}

	if(segtree[2*ind+1].pending == 1){
		segtree[ind].sum += (segtree[2*ind+1].sum-segtree[2*ind+1].minus)/K;
	}else{
		segtree[ind].sum += segtree[2*ind+1].sum;
		segtree[ind].minus += segtree[2*ind+1].minus;
	}
}

void query1(int ind, int l, int r, int i_src, ll val){
	if(segtree[ind].pending == 1){
		push_pending(ind);
	}

	if(l == r){
		segtree[ind].sum = val;
		segtree[ind].minus = val%K;
		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);
}

void query2(int ind, int l, int r, int l_src, int r_src){
	if(segtree[ind].pending == 1){
		push_pending(ind);
	}

	// if(BTW(l, l_src, r_src) && BTW(r, l_src, r_src)){
	// 	segtree[ind].pending = 1;
	// 	return;
	// }

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

	update_me(ind);
}

void query3(int ind, int l, int r, int l_src, int r_src){
	if(segtree[ind].pending == 1){
		push_pending(ind);
	}

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

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

void print_segtree(){
	for(int i=1;i<=2*N+2;i++){
		cout << i << " -> " << segtree[i].sum << " " << segtree[i].minus << " " << segtree[i].pending << endl;
	}
}

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

		// cout << "=== " << Q << " ===" << endl;
		// print_segtree();
	}

	return 0;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 75