제출 #236161

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
236161		kshitij_sodani	Sterilizing Spray (JOI15_sterilizing)	C++17	100 / 100	1416 ms	11256 KiB

sterilizing

#include <bits/stdc++.h>
using namespace std;
typedef int64_t llo;
#define mp make_pair
#define pb push_back
#define a first
#define b second
llo n,q,k;
llo aa,bb,cc;
llo it[100001];
llo tree[100001];
void u(llo i,llo j){
	while(i<=100000){
		tree[i]+=j;
		i+=(i&-i);
	}
}
llo s(llo i){
	llo su=0;
	while(i>0){
		su+=tree[i];
		i-=(i&-i);
	}
	return su;
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>n>>q>>k;
	set<pair<llo,llo>> ss;
	for(llo i=0;i<n;i++){
		cin>>it[i];
		u(i+1,it[i]);
		ss.insert({i,it[i]});
	}

	for(llo i=0;i<q;i++){
		cin>>aa>>bb>>cc;
		if(aa==1){
			if(it[bb-1]>0){
				ss.erase({bb-1,it[bb-1]});
			}
			u(bb,-it[bb-1]);
			it[bb-1]=cc;

			u(bb,cc);
			if(cc>0){
				ss.insert({bb-1,it[bb-1]});
			}
		}
		else if(aa==2){
			if(k>1){
				auto j=ss.lower_bound({bb-1,0});
				while((*j).a<cc and j!=ss.end()){
					llo ind=(*j).a;
					u(ind+1,-it[ind]);
					pair<llo,llo> kk=*j;
					ss.erase(j);
					it[ind]=it[ind]/k;
					if(it[ind]>0){
						u(ind+1,it[ind]);
						ss.insert({ind,it[ind]});
					}
					j=ss.upper_bound(kk);
				}
			}
		}
		else{
			cout<<s(cc)-s(bb-1)<<endl;

		}
	}
	return 0;
}

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