제출 #89623

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
89623		KLPP	Sterilizing Spray (JOI15_sterilizing)	C++14	100 / 100	1597 ms	421960 KiB

sterilizing

#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 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 75 / 75