제출 #40640

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
40640		IvanC	Sterilizing Spray (JOI15_sterilizing)	C++14	100 / 100	350 ms	40528 KiB

sterilizing

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 1e5 + 10;
ll seg[4*MAXN],qtd[4*MAXN],vetor[MAXN],N,Q,K;
void build(int pos,int left,int right){
	if(left == right){
		seg[pos] = vetor[left];
		qtd[pos] = (seg[pos] == 0);
		return;
	}
	int mid = (left+right)/2;
	build(2*pos,left,mid);
	build(2*pos+1,mid+1,right);
	seg[pos] = seg[2*pos] + seg[2*pos+1];
	qtd[pos] = qtd[2*pos] + qtd[2*pos+1];
}
void update_division(int pos,int left,int right,int i,int j){
	if(qtd[pos] == right - left + 1) return;
	if(left == right){
		seg[pos] = seg[pos]/K;
		qtd[pos] = (seg[pos] == 0);
		return;
	}
	int mid = (left+right)/2;
	if(j <= mid){
		update_division(2*pos,left,mid,i,j);
	}
	else if(i >= mid+1){
		update_division(2*pos+1,mid+1,right,i,j);
	}
	else{
		update_division(2*pos,left,mid,i,mid);
		update_division(2*pos+1,mid+1,right,mid+1,j);
	}
	seg[pos] = seg[2*pos] + seg[2*pos+1];
	qtd[pos] = qtd[2*pos] + qtd[2*pos+1];
}
void update_value(int pos,int left,int right,int x,ll val){
	if(left == right){
		seg[pos] = val;
		qtd[pos] = (seg[pos] == 0);
		return;
	}
	int mid = (left+right)/2;
	if(x <= mid) update_value(2*pos,left,mid,x,val);
	else update_value(2*pos+1,mid+1,right,x,val);
	seg[pos] = seg[2*pos] + seg[2*pos+1];
	qtd[pos] = qtd[2*pos] + qtd[2*pos+1];
}
ll query(int pos,int left,int right,int i,int j){
	if(left >= i && right <= j) return seg[pos];
	int mid = (left+right)/2;
	if(j <= mid) return query(2*pos,left,mid,i,j);
	else if(i >= mid + 1) return query(2*pos+1,mid+1,right,i,j);
	else return query(2*pos,left,mid,i,j) + query(2*pos+1,mid+1,right,i,j);
}
int main(){
	cin.tie(0);cout.tie(0);ios_base::sync_with_stdio(0);
	cin >> N >> Q >> K;
	for(int i = 1;i<=N;i++) cin >> vetor[i];
	build(1,1,N);
	for(int q = 1;q<=Q;q++){
		ll op,u,v;
		cin >> op >> u >> v;
		if(op == 1){
			update_value(1,1,N,u,v);
		}
		else if(op == 2){
			if(K != 1) update_division(1,1,N,u,v);
		}
		else{
			cout << query(1,1,N,u,v) << endl;
		}
	}
	return 0;
}

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