Submission #156568

#	Time	Username	Problem	Language	Result	Execution time	Memory
156568		Saboon	Sterilizing Spray (JOI15_sterilizing)	C++14	100 / 100	444 ms	7436 KiB

sterilizing

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int mod = 1e9 + 7;
const int maxn = 1e5 + 10;

ll sum[4 * maxn], mxm[4 * maxn];

ll get(int id, int L, int R, int l, int r){
	if (r <= L or R <= l)
		return 0;
	if (l <= L and R <= r)
		return sum[id];
	int mid = (L + R) >> 1;
	return get(2 * id + 0, L, mid, l, r) + get(2 * id + 1, mid, R, l, r);
}

void change(int id, int L, int R, int l, int r, int k){
	if (r <= L or R <= l or mxm[id] == 0)
		return;
	if (L + 1 == R){
		int x = mxm[id] / k;
		sum[id] = mxm[id] = x;
		return;
	}
	int mid = (L + R) >> 1;
	change(2 * id + 0, L, mid, l, r, k);
	change(2 * id + 1, mid, R, l, r, k);
	sum[id] = sum[2 * id + 0] + sum[2 * id + 1];
	mxm[id] = max(mxm[2 * id + 0], mxm[2 * id + 1]);
}

void apply(int id, int L, int R, int idx, int val){
	if (idx < L or R <= idx)
		return;
	if (L + 1 == R){
		sum[id] = mxm[id] = val;
		return;
	}
	int mid = (L + R) >> 1;
	apply(2 * id + 0, L, mid, idx, val);
	apply(2 * id + 1, mid, R, idx, val);
	sum[id] = sum[2 * id + 0] + sum[2 * id + 1];
	mxm[id] = max(mxm[2 * id + 0], mxm[2 * id + 1]);
}

int main(){
	ios_base::sync_with_stdio (false);
	int n, q, k;
	cin >> n >> q >> k;
	for (int i = 0; i < n; i++){
		int a;
		cin >> a;
		apply(1, 0, n, i, a);
	}
	for (int i = 0; i < q; i++){
		int type, a, b;
		cin >> type >> a >> b;
		if (type == 1){
			a --;
			apply(1, 0, n, a, b);
		}
		else if (type == 2){
			a --;
			if (k > 1)
				change(1, 0, n, a, b, k);
		}
		else{
			a --;
			cout << get(1, 0, n, a, b) << '\n';
		}
	}
}

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