Submission #197284

#	Time	Username	Problem	Language	Result	Execution time	Memory
197284		TAISA_	Sterilizing Spray (JOI15_sterilizing)	C++14	100 / 100	470 ms	11060 KiB

sterilizing

#include<bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
using namespace std;
using ll=long long;
using P=pair<ll,ll>;
const ll LINF=(1LL<<60)-1LL;
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
struct Segtree{
	int n;
	vector<ll> dat;
	Segtree(int n_){
		n=1;
		while(n<n_){
			n<<=1;
		}
		dat.resize(2*n);
	}
	void upd(int k,ll x){
		k+=n;
		dat[k]=x;
		k>>=1;
		while(k>0){
			dat[k]=dat[k<<1]+dat[k<<1|1];
			k>>=1;
		}
	}
	ll get(int a,int b,int k,int l,int r){
		if(b<=l||r<=a){
			return 0;
		}
		if(a<=l&&r<=b){
			return dat[k];
		}
		return get(a,b,k<<1,l,(l+r)/2)+get(a,b,k<<1|1,(l+r)/2,r);
	}
	inline ll get(int a,int b){
		return get(a,b,1,0,n);
	}
};
int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n,q,k;cin>>n>>q>>k;
	vector<ll> c(n);
	set<int> st;
	Segtree seg(n);
	for(int i=0;i<n;i++){
		cin>>c[i];
		if(c[i]>0){
			st.insert(i);
		}
		seg.upd(i,c[i]);
	}
	for(int i=0;i<q;i++){
		int t,a,b;cin>>t>>a>>b;
		if(t==1){
			--a;
			if(k==1){
				seg.upd(a,b);
				continue;
			}
			if(c[a]>0){
				st.erase(a);
			}
			c[a]=b;
			if(b>0){
				st.insert(a);
			}
			seg.upd(a,b);
		}else if(t==2){
			--a;--b;
			if(k==1){
				continue;
			}
			auto it=st.lower_bound(a);
			vector<int> v;
			for(;it!=st.end();it++){
				if((*it)>b){
					break;
				}
				c[*it]/=k;
				if(c[*it]==0){
					v.emplace_back(*it);
				}
				seg.upd((*it),c[*it]);
			}
			for(auto &e:v){
				st.erase(e);
			}
		}else{
			--a;--b;
			cout<<seg.get(a,b+1)<<endl;
		}
	}
	return 0;
}	

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