Submission #1014959

#TimeUsernameProblemLanguageResultExecution timeMemory
1014959lambd47Sterilizing Spray (JOI15_sterilizing)C++14
10 / 100
64 ms9448 KiB
#pragma GCC optimize ("O3") #pragma GCC target ("sse4") #include <bits/stdc++.h> using namespace std; #define int long long const int MOD = 1000000007; const char nl = '\n'; const int MX = 100001; int arr[MX]; struct node{ int soma=0, mx=0; node operator+(node aux){ return {soma+aux.soma,max(mx,aux.mx)}; } }; node seg[4*MX]; int potencias[30]; int k; void build(int pos, int ini, int fim){ if(ini==fim){ seg[pos]={arr[ini],arr[ini]}; return; } int m=(ini+fim)/2; int e=2*pos,d=2*pos+1; build(e,ini,m); build(d,m+1,fim); seg[pos]=seg[e]+seg[d]; } void updt1(int pos, int ini, int fim, int id, int val){ if(ini>id || fim<id)return; if(ini==fim){ seg[pos]={val,val}; return; } int m=(ini+fim)/2; int e=2*pos,d=2*pos+1; updt1(e,ini,m,id,val); updt1(d,m+1,fim,id,val); seg[pos]=seg[e]+seg[d]; } void spray(int pos,int ini, int fim, int l, int r){ if(ini>r || fim<l)return; if(l<=ini && fim<=r){ seg[pos].mx/=k; if(seg[pos].mx==0){ seg[pos].soma=0; return; } else if(ini==fim){ seg[pos].soma=seg[pos].mx; return; } } int m=(ini+fim)/2; int e=2*pos,d=2*pos+1; spray(e,ini,m,l,r); spray(d,m+1,fim,l,r); seg[pos]=seg[e]+seg[d]; } int query(int pos, int ini, int fim, int l, int r){ if(ini>r || fim<l)return 0; if(l<=ini && fim<=r){ return seg[pos].soma; } int m=(ini+fim)/2; int e=2*pos,d=2*pos+1; return query(e,ini,m,l,r)+query(d,m+1,fim,l,r); } void solve() { int n,q; cin>>n>>q>>k; for(int i=1;i<=n;i++){ cin>>arr[i]; } build(1,1,n); while(q--){ int tipo,a,b; cin>>tipo>>a>>b; if(tipo==1){ updt1(1,1,n,a,b); } else if(tipo==2){ if(k!=1) spray(1,1,n,a,b); } else{ cout<<query(1,1,n,a,b)<<"\n"; } } } int32_t main() { cin.tie(0)->sync_with_stdio(0); cin.exceptions(cin.failbit); int T = 1; // cin >> T; while(T--) { solve(); } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...