제출 #329211

#제출 시각아이디문제언어결과실행 시간메모리
329211iliccmarkoSterilizing Spray (JOI15_sterilizing)C++14
10 / 100
857 ms69344 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; set<int> seg[4*N]; int sum[4*N]; vector<int> a(N); int 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]; } void build(int node, int l, int r) { if(l==r) { if(a[l]) seg[node].insert(l); return; } for(int s = l;s<=r;s++) if(a[s]) seg[node].insert(s); int mid = (l+r)/2; build(node*2+1, l, mid); build(node*2+2, mid+1, r); } int 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); } void _erase(int node, int l, int r, int pos, int x) { seg[node].erase(pos); if(l==r) return; int mid = (l+r)/2; if(pos>mid) _erase(node*2+2, mid+1, r, pos, x); else _erase(node*2+1, l, mid, pos, x); } void _insert(int node, int l, int r, int pos, int x) { seg[node].insert(pos); if(l==r) return; int mid = (l+r)/2; if(pos>mid) _insert(node*2+2, mid+1, r, pos, x); else _insert(node*2+1, l, mid, pos, x); } set<int> get_alive(int node, int l, int r, int i, int j) { if(i>r||j<l) { set<int> q; return q; } if(i>=l&&j<=r) return seg[node]; int mid = (i+j)/2; set<int> levo = get_alive(node*2+1, l, r, i, mid); set<int> desno = get_alive(node*2+2, l, r, mid+1, j); set<int> ans; for(int x : levo) ans.insert(x); for(int x : desno) ans.insert(x); return ans; } int main() { //ios cin>>n>>q>>k; for(int i = 0;i<n;i++) cin>>a[i]; build(0, 0, n-1); //cout<<11111<<endl; build_sum(0, 0, n-1); //cout<<2222<<endl; int ss = q; int cnt = 0; vector<pair<int, pair<int, int> > > sss; while(ss--) { int s, t, u; cin>>s>>t>>u; if(s==3) cnt++; sss.pb({s, {t, u}}); } int i = 0; while(q--) { int s, t, u; s = sss[i].first; t = sss[i].second.first; u = sss[i].second.second; i++; //line //cin>>s>>t>>u; t--; u--; if(s==1) { // a-ti tanjir na b u++; if(!a[t]&&u) _insert(0, 0, n-1, t, t); if(a[t]&&!u) _erase(0, 0, n-1, t, t); a[t] = u; update(0, 0, n-1, t, u); } else if(s==2) { // sprej if(k==1) continue; set<int> qq = get_alive(0, t, u, 0, n-1); for(int x : qq) { //cout<<x<<" "; //cout<<x<<" "; a[x] /= k; if(!a[x]) _erase(0, 0, n-1, x, x); update(0, 0, n-1, x, a[x]); } //cout<<endl; //cout<<endl; } else{ // ispisi sumu od l do r //cout<<u<<" "<<t<<endl; cnt--; cout<<get_sum(0, t, u, 0, n-1); if(cnt) 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...