제출 #1286579

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1286579		duyanhchupapi	Sterilizing Spray (JOI15_sterilizing)	C++20	75 / 100	138 ms	3828 KiB

sterilizing

#include <bits/stdc++.h>
using namespace std; 
using ll = long long; 
const int N = 1e5 + 5;
int n, q, k, MAX[4*N];
ll SUM[4*N];

void up1(int x, int l, int r, int id, int w) {
	if(l == r) {
		SUM[x] = w;
		MAX[x] = w;
		return;
	}
	int mid = (l + r)/2;
	if(id <= mid) up1(2*x,l,mid,id,w);
	else up1(2*x+1,mid+1,r,id,w);
	SUM[x] = SUM[2*x] + SUM[2*x+1];
	MAX[x] = max(MAX[2*x], MAX[2*x+1]);
}

void up2(int x, int l, int r, int i, int j) {
	if(l > j || r < i || MAX[x] == 0) return;
	if(l == r) {
		SUM[x] /= k;
		MAX[x] /= k;
		return;
	}
	int mid = (l + r)/2;
	up2(2*x,l,mid,i,j);
	up2(2*x+1,mid+1,r,i,j);
	SUM[x] = SUM[2*x] + SUM[2*x+1];
	MAX[x] = max(MAX[2*x], MAX[2*x+1]);
}

ll get(int x, int l, int r, int i, int j) {
	if(l > j || r < i || MAX[x] == 0) return 0;
	if(l >= i && r <= j) return SUM[x];
	int mid = (l + r)/2;
	return get(2*x,l,mid,i,j) + get(2*x+1,mid+1,r,i,j);
}

int main() { 
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n >> q >> k;
	for(int i=1;i<=n;++i) {
		int c;
		cin >> c;
		up1(1,1,n,i,c);
	}
	
	while(q--) {
		int s,t,u;
		cin >> s >> t >> u;
		if(s == 1) up1(1,1,n,t,u);
		else if(s == 2 && k != 1) up2(1,1,n,t,u);
		else cout << get(1,1,n,t,u) << '\n';
	}
 	return 0;
}

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