Submission #124839

#	Time	Username	Problem	Language	Result	Execution time	Memory
124839		DMCS	Sterilizing Spray (JOI15_sterilizing)	C++14	100 / 100	264 ms	6136 KiB

sterilizing

#include <bits/stdc++.h>

using namespace std;

#define int int64_t
const int N = 1e5+1;

int n, q, k;
int it[4*N], a[N];

void build(int id, int l, int r) {
	if(l == r) {
		it[id] = a[l]; 
		return;
	}
	
	int m = (l+r)/2;
	build(id*2, l, m);
	build(id*2+1, m+1, r);
	it[id] = it[id*2] + it[id*2+1];
}

void update(int id, int l, int r, int p, int val) {
	if(l > p || r < p) return; 
	if(l == r) {
		it[id] = val;
		return;
	}
	
	int m = (l+r)/2;
	update(id*2, l, m, p, val);
	update(id*2+1, m+1, r, p, val);
	it[id] = it[id*2] + it[id*2+1];
}

void dec(int id, int l, int r, int x, int y) {
	if(it[id] == 0 || k == 1) return; 
	if(l > y || r < x) return; 
	if(l == r) {
		it[id] /= k;
		return;
	}
	
	int m = (l+r)/2;
	dec(id*2, l, m, x, y);
	dec(id*2+1, m+1, r, x, y);
	it[id] = it[id*2] + it[id*2+1];
}

int get(int id, int l, int r, int x, int y) {
	if(l > y || r < x) return 0;
	if(l >= x && r <= y) return it[id];
	
	int m = (l+r)/2;
	return get(id*2, l, m, x, y) + get(id*2+1, m+1, r, x, y);
}

signed main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	cin >> n >> q >> k;
	for(int i = 1; i <= n; i++) cin >> a[i];
	
	build(1, 1, n); 
	while(q--) {
		int t;
		cin >> t;
		if(t == 1) {
			int p, val;
			cin >> p >> val;
			update(1, 1, n, p, val);
		}
		if(t == 2) {
			int l, r;
			cin >> l >> r;		
			dec(1, 1, n, l, r);
		}
		if(t == 3) {
			int l, r;
			cin >> l >> r;
			cout << get(1, 1, n, l, r) << "\n";
		}
	}  
}	

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