Submission #197284

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
197284	2020-01-20T06:24:30 Z	TAISA_	Sterilizing Spray (JOI15_sterilizing)	C++14	100 / 100	470 ms	11060 KB

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.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	376 KB	Output is correct
2	Correct	4 ms	376 KB	Output is correct
3	Correct	4 ms	504 KB	Output is correct
4	Correct	10 ms	504 KB	Output is correct
5	Correct	11 ms	504 KB	Output is correct
6	Correct	10 ms	632 KB	Output is correct
7	Correct	11 ms	632 KB	Output is correct
8	Correct	10 ms	504 KB	Output is correct
9	Correct	12 ms	612 KB	Output is correct
10	Correct	10 ms	632 KB	Output is correct
11	Correct	10 ms	504 KB	Output is correct
12	Correct	10 ms	636 KB	Output is correct

Subtask #2

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	163 ms	5492 KB	Output is correct
2	Correct	144 ms	5352 KB	Output is correct
3	Correct	132 ms	8568 KB	Output is correct
4	Correct	166 ms	10360 KB	Output is correct
5	Correct	200 ms	11060 KB	Output is correct
6	Correct	199 ms	10872 KB	Output is correct
7	Correct	198 ms	10856 KB	Output is correct
8	Correct	198 ms	10792 KB	Output is correct
9	Correct	189 ms	10872 KB	Output is correct
10	Correct	190 ms	10744 KB	Output is correct
11	Correct	191 ms	10744 KB	Output is correct
12	Correct	188 ms	10744 KB	Output is correct

Subtask #3

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	60 ms	732 KB	Output is correct
2	Correct	38 ms	2808 KB	Output is correct
3	Correct	53 ms	2900 KB	Output is correct
4	Correct	148 ms	1784 KB	Output is correct
5	Correct	184 ms	5752 KB	Output is correct
6	Correct	188 ms	5752 KB	Output is correct
7	Correct	170 ms	6520 KB	Output is correct
8	Correct	186 ms	7040 KB	Output is correct
9	Correct	175 ms	7228 KB	Output is correct
10	Correct	178 ms	7172 KB	Output is correct
11	Correct	178 ms	7216 KB	Output is correct
12	Correct	172 ms	6960 KB	Output is correct

Subtask #4

75.0 / 75.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	185 ms	4488 KB	Output is correct
2	Correct	200 ms	4416 KB	Output is correct
3	Correct	208 ms	4104 KB	Output is correct
4	Correct	222 ms	2936 KB	Output is correct
5	Correct	305 ms	8332 KB	Output is correct
6	Correct	327 ms	8256 KB	Output is correct
7	Correct	300 ms	8332 KB	Output is correct
8	Correct	387 ms	8312 KB	Output is correct
9	Correct	359 ms	8616 KB	Output is correct
10	Correct	367 ms	8436 KB	Output is correct
11	Correct	302 ms	8472 KB	Output is correct
12	Correct	470 ms	8544 KB	Output is correct