답안 #197284

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
197284 2020-01-20T06:24:30 Z TAISA_ Sterilizing Spray (JOI15_sterilizing) C++14
100 / 100
470 ms 11060 KB
#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;
}	
# 결과 실행 시간 메모리 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
# 결과 실행 시간 메모리 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
# 결과 실행 시간 메모리 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
# 결과 실행 시간 메모리 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