Submission #412849

#TimeUsernameProblemLanguageResultExecution timeMemory
412849iliccmarkoSterilizing Spray (JOI15_sterilizing)C++14
100 / 100
843 ms10836 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define endl "\n" #define INF 1000000000 #define LINF 1000000000000000LL #define pb push_back #define all(x) x.begin(), x.end() #define len(s) (int)s.size() #define test_case { int t; cin>>t; while(t--)solve(); } #define input(n, v) {for(int i = 0;i<n;i++) cin>>v[i];} #define output(n, v) {for(int i = 0;i<n;i++) cout<<v[i]<<" "; cout<<endl;} #define single_case solve(); #define line cout<<"------------"<<endl; #define ios { ios_base::sync_with_stdio(false); cin.tie(NULL); } using namespace std; int n, q, k; const int N = 1e5 + 5; ll sum[4*N]; vector<ll> a(N); ll get_sum(int node, int l, int r, int i, int j) { if(i>r||j<l) return 0; if(i>=l&&j<=r) return sum[node]; int mid = (i+j)/2; return get_sum(node*2+1, l, r, i, mid) + get_sum(node*2+2, l, r, mid+1, j); } void update(int node, int l, int r, int pos, int x) { if(l==r) { sum[node] = x; return; } int mid = (l+r)/2; if(pos>mid) update(node*2+2, mid+1, r, pos, x); else update(node*2+1, l, mid, pos, x); sum[node] = sum[node*2+1] + sum[node*2+2]; } ll build_sum(int node, int l, int r) { if(l==r) { return sum[node] = a[l]; } int mid = (l+r)/2; return sum[node] = build_sum(node*2+1, l, mid) + build_sum(node*2+2, mid+1, r); } int main() { ios cin>>n>>q>>k; for(int i = 0;i<n;i++) cin>>a[i]; //cout<<11111<<endl; set<ll> alive; for(ll i = 0;i<n;i++) if(a[i]) alive.insert(i); build_sum(0, 0, n-1); //cout<<2222<<endl; while(q--) { ll s, t, u; cin>>s>>t>>u; t--; u--; if(s==1) { // a-ti tanjir na b u++; //cout<<a[t]<<" "<<u<<endl; if(!a[t]&&u) alive.insert(t); if(a[t]&&!u) alive.erase(t); a[t] = u; update(0, 0, n-1, t, u); } else if(s==2) { // sprej if(k==1) continue; vector<int> s; auto w = alive.lower_bound(t); while(w!=alive.end()) { if((*w)>u) break; int e = *w; a[e]/=k; if(!a[e]) s.pb(e); update(0, 0, n-1, e, a[e]); w++; } for(int x : s) alive.erase(x); //cout<<endl; //cout<<endl; } else{ // ispisi sumu od l do r //cout<<u<<" "<<t<<endl; cout<<get_sum(0, t, u, 0, n-1); cout<<endl; } } 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...