제출 #916793

#제출 시각아이디문제언어결과실행 시간메모리
916793Dec0DeddSterilizing Spray (JOI15_sterilizing)C++14
100 / 100
100 ms9040 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<ll, ll> pii; struct fenwick { vector<ll> bit; int n; void init(int sz) { n=sz+10; bit.assign(n, 0); } ll sum(int r) { ll res=0; for (;r>=0; r=(r&(r+1))-1) res+=bit[r]; return res; } ll que(int l, int r) { return sum(r)-sum(l-1); } void upd(int x, ll d) { for (; x<n; x=x|(x+1)) bit[x]+=d; } void st(int x, ll d) { ll vl=que(x, x); upd(x, d-vl); } }; const int N = 1e5+10; int n, q, k, c[N]; void solve() { cin>>n>>q>>k; for (int i=1; i<=n; ++i) cin>>c[i]; fenwick f; f.init(n+10); set<int> st; for (int i=1; i<=n; ++i) { f.st(i, c[i]); if (c[i] > 0) st.insert(i); } while (q--) { int s, t, u; cin>>s>>t>>u; if (s == 1) { f.upd(t, u-c[t]); c[t]=u; if (u > 0) st.insert(t); } else if (s == 2) { auto ptr=st.lower_bound(t); if (k == 1) continue; while (ptr != st.end()) { if ((*ptr) > u) break; int nvl=c[*ptr]/k; f.upd(*ptr, nvl-c[*ptr]); c[*ptr]=nvl; if (nvl == 0) { st.erase(ptr++); continue; } ++ptr; } } else cout<<f.que(t, u)<<"\n"; } } int main() { ios_base::sync_with_stdio(0); cin.tie(NULL); int t=1; //cin>>t; while (t--) solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...