oj.uz

Submission #79038

# Submission time Handle Problem Language Result Execution time Memory
79038 2018-10-10T18:32:58 Z KLPP Sterilizing Spray (JOI15_sterilizing) C++14
0 / 100
 5000 ms 1372 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 209 ms 376 KB Output is correct
2 Incorrect 2 ms 376 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 26 ms 832 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5005 ms 832 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5078 ms 1372 KB Time limit exceeded
2 Halted 0 ms 0 KB -