oj.uz

Submission #89622

# Submission time Handle Problem Language Result Execution time Memory
89622 2018-12-17T16:02:31 Z KLPP Sterilizing Spray (JOI15_sterilizing) C++14
20 / 100
 634 ms 131352 KB 
#include<iostream>

using namespace std;
typedef long long int lld;
#define max 10
class ST{
	lld sum[1000000][max];
	lld lazy[1000000];
	lld k;
	int n;
	public:
	void build(int a, int b, int node){
		for(int i=0;i<max;i++){
			sum[node][i]=0;
		}
		lazy[node]=0;
		if(a==b)return;
		int mid=(a+b)/2;
		build(a,mid,2*node);
		build(mid+1,b,2*node+1);
	}
	void init(int N, int K){
		n=N;
		k=K;
		build(0,n-1,1);
	}
	void propagate(int a,int b, int node){
		if(lazy[node]==0)return;
		if(a!=b){
			lazy[2*node]+=lazy[node];
			lazy[2*node+1]+=lazy[node];
		}
		if(k>1){
			for(int i=0;i<max;i++){
				if(i+lazy[node]<max)sum[node][i]=sum[node][i+lazy[node]];
				else sum[node][i]=0;
			}
		}lazy[node]=0;
	}
	void update(int a, int b, int node, int pos,lld val){
		//cout<<a<<" "<<b<<" "<<node<<endl;
		propagate(a,b,node);
		if(pos<a || b<pos)return;
		if(a==b){//cout<<a<<endl;
			lld Q=val;
			for(int i=0;i<max;i++){
				//cout<<Q<<endl;
				sum[node][i]=Q;
				Q/=k;
			}return;
		}
		int mid=(a+b)/2;
		update(a,mid,2*node,pos,val);
		update(mid+1,b,2*node+1,pos,val);
		for(int i=0;i<max;i++){
			sum[node][i]=sum[2*node][i]+sum[2*node+1][i];
		}
	}
	void upd(int pos,lld val){
		update(0,n-1,1,pos,val);
	}
	void spray(int a, int b, int node, int x, int y){
		propagate(a,b,node);
		if(y<a || b<x)return;
		if(x<=a && b<=y){
			lazy[node]++;
			propagate(a,b,node);
			return;
		}
		int mid=(a+b)/2;
		spray(a,mid,2*node,x,y);
		spray(mid+1,b,2*node+1,x,y);
		for(int i=0;i<max;i++){
			sum[node][i]=sum[2*node][i]+sum[2*node+1][i];
		}
	}
	void Spray(int x, int y){
		spray(0,n-1,1,x,y);
	}
	void print(int a, int b, int node){
		cout<<a<<" "<<b<<" : "<<endl;
		for(int i=0;i<max;i++)cout<<sum[node][i]<<" ";
		cout<<lazy[node]<<endl;
		if(a!=b){
			int mid=(a+b)/2;
			print(a,mid,2*node);
			print(mid+1,b,2*node+1);
		}
	}
	lld query(int a, int b, int node, int x, int y){
		propagate(a,b,node);
		if(y<a || b<x)return 0;
		if(x<=a && b<=y)return sum[node][0];
		int mid=(a+b)/2;
		return query(a,mid,2*node,x,y)+query(mid+1,b,2*node+1,x,y);
	}
	lld Q(int x, int y){
		return query(0,n-1,1,x,y);
	}
};
int main(){
	int n,q,k;
	cin>>n>>q>>k;
	int arr[n];
	for(int i=0;i<n;i++)cin>>arr[i];
	ST *S=new ST();
	S->init(n,k);
	for(int i=0;i<n;i++)S->upd(i,arr[i]);
	//S->print(0,n-1,1);
	/*S->Spray(0,2);
	S->print(0,n-1,1);*/
	for(int i=0;i<q;i++){
		int op;
		cin>>op;
		if(op==1){
			int x;
			cin>>x;
			x--;
			lld v;
			cin>>v;
			S->upd(x,v);
		}else if(op==2){
			int x,y;
			cin>>x>>y;
			x--;y--;
			S->Spray(x,y);
		}else{
			int x,y;
			cin>>x>>y;
			x--;y--;
			cout<<S->Q(x,y)<<endl;
			//S->print(0,n-1,1);
		}
		//S->print(0,n-1,1);
	}
	return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 86524 KB Output is correct
2 Correct 80 ms 86692 KB Output is correct
3 Correct 80 ms 86780 KB Output is correct
4 Incorrect 87 ms 86816 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 376 ms 89668 KB Output is correct
2 Correct 317 ms 91244 KB Output is correct
3 Correct 318 ms 92872 KB Output is correct
4 Correct 430 ms 95116 KB Output is correct
5 Correct 499 ms 97948 KB Output is correct
6 Correct 519 ms 100180 KB Output is correct
7 Correct 495 ms 102728 KB Output is correct
8 Correct 500 ms 105244 KB Output is correct
9 Correct 441 ms 107484 KB Output is correct
10 Correct 438 ms 109820 KB Output is correct
11 Correct 419 ms 112028 KB Output is correct
12 Correct 439 ms 114316 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 192 ms 114316 KB Output is correct
2 Correct 173 ms 114536 KB Output is correct
3 Correct 211 ms 114784 KB Output is correct
4 Correct 441 ms 115944 KB Output is correct
5 Correct 622 ms 117928 KB Output is correct
6 Correct 590 ms 119180 KB Output is correct
7 Correct 422 ms 120664 KB Output is correct
8 Correct 634 ms 121988 KB Output is correct
9 Correct 474 ms 123252 KB Output is correct
10 Correct 463 ms 124552 KB Output is correct
11 Correct 474 ms 125948 KB Output is correct
12 Correct 453 ms 127304 KB Output is correct

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 426 ms 128520 KB Output is correct
2 Correct 487 ms 130404 KB Output is correct
3 Incorrect 337 ms 131352 KB Output isn't correct
4 Halted 0 ms 0 KB -