oj.uz

Submission #89623

# Submission time Handle Problem Language Result Execution time Memory
89623 2018-12-17T16:03:02 Z KLPP Sterilizing Spray (JOI15_sterilizing) C++14
100 / 100
 1597 ms 421960 KB 
#include<iostream>

using namespace std;
typedef long long int lld;
#define max 50
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
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 340 ms 399544 KB Output is correct
2 Correct 305 ms 399624 KB Output is correct
3 Correct 302 ms 399740 KB Output is correct
4 Correct 313 ms 399740 KB Output is correct
5 Correct 347 ms 399888 KB Output is correct
6 Correct 322 ms 400128 KB Output is correct
7 Correct 369 ms 400128 KB Output is correct
8 Correct 374 ms 400280 KB Output is correct
9 Correct 366 ms 400340 KB Output is correct
10 Correct 347 ms 400340 KB Output is correct
11 Correct 318 ms 400376 KB Output is correct
12 Correct 370 ms 400572 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 938 ms 401368 KB Output is correct
2 Correct 841 ms 401368 KB Output is correct
3 Correct 868 ms 401368 KB Output is correct
4 Correct 1048 ms 401368 KB Output is correct
5 Correct 1223 ms 401476 KB Output is correct
6 Correct 1188 ms 401476 KB Output is correct
7 Correct 1179 ms 401604 KB Output is correct
8 Correct 1193 ms 401604 KB Output is correct
9 Correct 1054 ms 401604 KB Output is correct
10 Correct 1041 ms 401604 KB Output is correct
11 Correct 1008 ms 401604 KB Output is correct
12 Correct 1035 ms 401604 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 574 ms 401604 KB Output is correct
2 Correct 573 ms 401604 KB Output is correct
3 Correct 643 ms 401604 KB Output is correct
4 Correct 1102 ms 401604 KB Output is correct
5 Correct 1540 ms 401604 KB Output is correct
6 Correct 1523 ms 401604 KB Output is correct
7 Correct 1106 ms 401604 KB Output is correct
8 Correct 1507 ms 401604 KB Output is correct
9 Correct 1173 ms 401604 KB Output is correct
10 Correct 1172 ms 401604 KB Output is correct
11 Correct 1170 ms 401604 KB Output is correct
12 Correct 1180 ms 401604 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 1066 ms 401604 KB Output is correct
2 Correct 1097 ms 401604 KB Output is correct
3 Correct 866 ms 401604 KB Output is correct
4 Correct 1132 ms 402844 KB Output is correct
5 Correct 1561 ms 405424 KB Output is correct
6 Correct 1580 ms 408012 KB Output is correct
7 Correct 1572 ms 410248 KB Output is correct
8 Correct 1597 ms 412836 KB Output is correct
9 Correct 1198 ms 415236 KB Output is correct
10 Correct 1206 ms 417384 KB Output is correct
11 Correct 1179 ms 419800 KB Output is correct
12 Correct 1218 ms 421960 KB Output is correct