Submission #113615

#	Time	Username	Problem	Language	Result	Execution time	Memory
113615		Diuven	Sterilizing Spray (JOI15_sterilizing)	C++14	100 / 100	725 ms	10488 KiB

sterilizing

#include <bits/stdc++.h>
using namespace std;

typedef long long lint;
typedef pair<int, int> pii;

const int INF = 2e9;
const int MOD = 1e9+7;
const int MAX = 1e5+10;
const lint LNF = 2e18;

int n, q, k, A[MAX];
set<int> S;

class Seg_t{
	lint T[1<<18];
	void upt(int v, int s, int e, int p, int x){
		if(p<s || e<p) return;
		if(s==e){ T[v]=x; return; }
		upt(v*2,s,(s+e)/2,p,x); upt(v*2+1,(s+e)/2+1,e,p,x);
		T[v]=T[v*2]+T[v*2+1];
	}
	lint sum(int v, int s, int e, int l, int r){
		if(e<l || r<s) return 0;
		if(l<=s && e<=r) return T[v];
		return sum(v*2,s,(s+e)/2,l,r) + sum(v*2+1,(s+e)/2+1,e,l,r);
	}
  public:
    void upt(int p, int x){ upt(1,1,n,p,x); }
	lint sum(int l, int r){ return sum(1,1,n,l,r); }
} Seg;

int main(){
	ios::sync_with_stdio(0); cin.tie(0);

	cin>>n>>q>>k;
	for(int i=1; i<=n; i++){
		cin>>A[i]; Seg.upt(i, A[i]);
		if(A[i]!=0) S.insert(i);
	}

	for(int i=1; i<=q; i++){
		int o,x,y; cin>>o>>x>>y;
		if(o==1){
			A[x]=y, Seg.upt(x, A[x]);
			if(A[x]!=0) S.insert(x);
		}
		else if(o==2){
			if(k==1) continue;
			auto lit=S.lower_bound(x), rit=S.upper_bound(y);
			vector<int> V;
			while(lit!=rit){
				int p=*lit; lit++;
				A[p]/=k, Seg.upt(p, A[p]);
				if(A[p]==0) V.push_back(p);
			}
			for(int p:V) S.erase(p);
		}
		else if(o==3){
			cout<<Seg.sum(x,y)<<'\n';
		}
	}

	return 0;
}

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