제출 #31831

#제출 시각아이디문제언어결과실행 시간메모리
31831Dat160601Sterilizing Spray (JOI15_sterilizing)C++14
80 / 100
5000 ms12332 KiB
#include <bits/stdc++.h> using namespace std; #define int long long int n,q,k,x,y; long long a[100007],it[400007],mx[400007],lazy[400007]; void init(int p,int l,int r){ if(l==r){ it[p]=a[l]; mx[p]=a[l]; return; } int mid=(l+r)/2; init(p*2,l,mid); init(p*2+1,mid+1,r); it[p]=it[p*2]+it[p*2+1]; mx[p]=max(mx[p*2],mx[p*2+1]); } void dolazy(int p,int l,int r){ if(lazy[p]==0) return; it[p]=0; mx[p]=0; if(l!=r){ lazy[p*2]=1; lazy[p*2+1]=1; } lazy[p]=0; } void upd(int p,int l,int r,int pos,int val){ dolazy(p,l,r); if(l>pos || r<pos) return; if(l==pos && l==r){ it[p]=val; mx[p]=val; return; } int mid=(l+r)/2; upd(p*2,l,mid,pos,val); upd(p*2+1,mid+1,r,pos,val); it[p]=it[p*2]+it[p*2+1]; mx[p]=max(mx[p*2],mx[p*2+1]); } void div(int p,int l,int r,int L,int R){ dolazy(p,l,r); if(l>R || r<L || l>r) return; if(l>=L && r<=R && mx[p]<k){ it[p]=0; mx[p]=0; if(l!=r){ lazy[p*2]=1; lazy[p*2+1]=1; } return; } if(l==r){ it[p]/=k; mx[p]/=k; return; } int mid=(l+r)/2; div(p*2,l,mid,L,R); div(p*2+1,mid+1,r,L,R); it[p]=it[p*2]+it[p*2+1]; mx[p]=max(mx[p*2],mx[p*2+1]); } long long get(int p,int l,int r,int L,int R){ dolazy(p,l,r); if(l>R || r<L || l>r) return 0; if(l>=L && r<=R){ //cout<<l<<" "<<r<<" "<<it[p]<<endl; return it[p]; } int mid=(l+r)/2; return get(p*2,l,mid,L,R)+get(p*2+1,mid+1,r,L,R); } signed main(){ ios_base::sync_with_stdio(0); cin>>n>>q>>k; for(int i=1;i<=n;i++){ cin>>a[i]; } init(1,1,n); int type; while(q--){ cin>>type>>x>>y; if(type==1){ upd(1,1,n,x,y); } else if(type==2){ div(1,1,n,x,y); } else{ cout<<get(1,1,n,x,y)<<"\n"; } } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...