Submission #79038

#	Time	Username	Problem	Language	Result	Execution time	Memory
79038		KLPP	Sterilizing Spray (JOI15_sterilizing)	C++14	0 / 100	5078 ms	1372 KiB

sterilizing

#include<iostream>

using namespace std;
typedef long long int lld;
const int blocksz=316;
lld arr[100000];
int n,q,k;
lld blockresults[blocksz+100][40];
int updatecounter[blocksz+100];
void prepareUpdate(int id){
	while(updatecounter[id]>0){
		for(int i=blocksz*id;i<blocksz*(id+1) && i<n;i++)arr[i]/=k;
		updatecounter[id]--;
	}
}
void updateblock(int id){//O(sqrt(N*log(MAX/K)))
	for(int i=0;i<40;i++)blockresults[id][i]=0;
	for(int i=blocksz*id;i<blocksz*(id+1) && i<n;i++){
		lld x=arr[i];
		int step=0;
		while(step<40){
			blockresults[id][step]+=x;
			x/=k;
			step++;
		}
	}
	updatecounter[id]=0;
}

lld getSum(int id){
	return blockresults[id][updatecounter[id]];
}
lld getSum2(int id, int x, int y){
	updateblock(id);
	lld ans=0;
	for(int i=x;i<=y && i<n;i++){
		ans+=arr[i];
	}return ans;
}
void spray(int id){
	if(updatecounter[id]<39)updatecounter[id]++;
}

int main(){
	cin>>n>>q>>k;
	for(int i=0;i<n;i++)cin>>arr[i];
	if(k>1){
		for(int i=0;i<=n/blocksz+10;i++){
			updateblock(i);
		}
		while(q--){
			int x,y,z;
			cin>>x>>y>>z;
			if(x==1){y--;
				prepareUpdate(y/blocksz);
				arr[y]=z;
				updateblock(y/blocksz);
			}
			if(x==2){
				y--;z--;
				if(y/blocksz==z/blocksz){
					prepareUpdate(y/blocksz);
					for(int i=y;i<=z;i++)arr[i]/=k;
					updateblock(y/blocksz);	
				}else{
					prepareUpdate(y/blocksz);
					int blocky=y/blocksz;
					for(int i=y;i<(blocky+1)*blocksz;i++)arr[i]/=k;
					updateblock(y/blocksz);
					prepareUpdate(z/blocksz);
					int blockz=z/blocksz;
					for(int i=blockz*blocksz;i<=z;i++)arr[i]/=k;
					updateblock(z/blocksz);
					for(int i=blocky+1;i<blockz;i++){
						spray(i);
					}
				}
			}
			if(x==3){
				y--;z--;
				lld sum=0;
				if(y/blocksz==z/blocksz){
					prepareUpdate(y/blocksz);
					for(int i=y;i<=z;i++)sum+=arr[i];
					updateblock(y/blocksz);	
				}else{
					prepareUpdate(y/blocksz);
					int blocky=y/blocksz;
					for(int i=y;i<(blocky+1)*blocksz;i++)sum+=arr[i];
					updateblock(y/blocksz);
					prepareUpdate(z/blocksz);
					int blockz=z/blocksz;
					for(int i=blockz*blocksz;i<=z;i++)sum+=arr[i];
					updateblock(z/blocksz);
					for(int i=blocky+1;i<blockz;i++){
						sum+=getSum(i);
					}
				}cout<<sum<<endl;
			}
		}
	}

	return 0;
}

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