Submission #1124258

#TimeUsernameProblemLanguageResultExecution timeMemory
1124258njoopGrowing Trees (BOI11_grow)C++17
0 / 100
931 ms11092 KiB
#include <bits/stdc++.h> #define int long long using namespace std; int n, m, arr[100010], in, h, mn, mx, c; struct lzt { vector<int> seg, lazy; void init() { seg.assign(600010, 0); lazy.assign(600010, 0); } void push(int l, int r, int node) { if(lazy[node] != 0) { seg[node] += (r-l+1)*lazy[node]; if(l != r) { lazy[node*2] += lazy[node]; lazy[node*2+1] += lazy[node]; } lazy[node] = 0; } } void update(int l, int r, int idl, int idr, int val, int node) { push(l, r, node); if(l > idr || r < idl) return; if(l >= idl && r <= idr) { seg[node] += (r-l+1)*val; if(l != r) { lazy[node*2] += val; lazy[node*2+1] += val; } return; } int mid = l + (r-l)/2; update(l, mid, idl, idr, val, node*2); update(mid+1, r, idl, idr, val, node*2+1); seg[node] = seg[node*2] + seg[node*2+1]; } int query(int l, int r, int ql, int qr, int node) { push(l, r, node); if(l > qr || r < ql) return 0; if(l >= ql && r <= qr) return seg[node]; int mid = l+(r-l)/2; return query(l, mid, ql, qr, node*2) + query(mid+1, r, ql, qr, node*2+1); } void upd(int l, int r, int val) { update(1, n, l, r, val, 1); } int qry(int l, int r) { return query(1, n, l, r, 1); } bool is_found(int val) { int l=1, r=n; while(l < r) { int mid = (l+r)/2; if(qry(mid, mid) >= val) { r = mid; } else { l = mid+1; } } if(l >= 1 && l <= n && qry(l, l) == val) return true; return false; } int lb_idx(int val) { int l=0, r=n+1; while(l < r) { int mid = (l+r)/2; if(qry(mid, mid) >= val) { r = mid; } else { l = mid+1; } } return l; } int ub_idx(int val) { int l=0, r=n+1; while(l < r) { int mid = (l+r)/2; if(qry(mid, mid) > val) { r = mid; } else { l = mid+1; } } return l; } }; signed main() { lzt seg; char co; cin >> n >> m; seg.init(); for(int i=1; i<=n; i++) { cin >> arr[i]; } sort(arr+1, arr+n+1); seg.upd(0, 0, -1); for(int i=1; i<=n; i++) { seg.upd(i, i, arr[i]); } seg.upd(n+1, n+1, 1e10); while(m--) { cin >> co; if(co == 'C') { cin >> mn >> mx; if(seg.ub_idx(mx)-seg.lb_idx(mn) <= 0) cout << 0 << "\n"; else cout << seg.ub_idx(mx)-seg.lb_idx(mn) << "\n"; } else { cin >> c >> h; int lb = seg.lb_idx(h); int rbv = seg.qry(lb+c-1, lb+c-1); int rb = seg.ub_idx(rbv)-1; int mb = seg.lb_idx(rbv); int ov = lb+c-1 - mb; if(mb-lb >= 1) { seg.upd(lb, mb-1, 1); } seg.upd(rb-ov, rb, 1); } } 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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...