Submission #893085

#TimeUsernameProblemLanguageResultExecution timeMemory
893085fanwenWeirdtree (RMI21_weirdtree)C++17
0 / 100
6 ms4444 KiB
#include <bits/stdc++.h> using namespace std; #define fi first #define se second const int MAX = 2e5 + 5; const int BLOCK = sqrt(MAX); const int INF = 1e9 + 1; struct node { long long sum; int ma1, ma2, fr, lazy; node(long long sum = 0, int ma1 = 0, int ma2 = 0, int fr = 0, int lazy = INF) : sum(sum), ma1(ma1), ma2(ma2), fr(fr), lazy(lazy) {} } infor[BLOCK + 5] ; int n, h[MAX]; int id_block(int pos) { return (pos - 1) / BLOCK; } int begin_block(int id) { return id * BLOCK; } int end_block(int id) { return min((id + 1) * BLOCK, n) - 1; } void build_block(int id) { int l = begin_block(id), r = end_block(id); infor[id].ma1 = infor[id].ma2 = infor[id].fr = infor[id].sum = 0; for (int i = l; i <= r; ++i) { h[i] = min(h[i], infor[id].lazy); infor[id].sum += h[i]; if(infor[id].ma1 < h[i]) { infor[id].ma2 = infor[id].ma1; infor[id].ma1 = h[i]; infor[id].fr = 1; } else { if(h[i] == infor[id].ma1) infor[id].fr++; infor[id].ma2 = max(infor[id].ma2, h[i]); } } infor[id].lazy = INF; } void initialise(int _n, int q, int _h[]) { n = _n; for (int i = 0; i < n; ++i) h[i] = _h[i + 1]; for (int i = 0; i < n; i += BLOCK) { build_block(i / BLOCK); } } node get(int l, int r) { node res; for (int i = l; i <= min(r, end_block(id_block(l))); ++i) { if(res.ma1 < h[i]) { res.ma2 = res.ma1; res.ma1 = h[i]; res.fr = 1; } else { if(res.ma1 == h[i]) res.fr++; else res.ma2 = max(res.ma2, h[i]); } res.sum += h[i]; } if(id_block(l) != id_block(r)) { for (int i = begin_block(id_block(r)); i <= r; ++i) { if(res.ma1 < h[i]) { res.ma2 = res.ma1; res.ma1 = h[i]; res.fr = 1; } else { if(res.ma1 == h[i]) res.fr++; else res.ma2 = max(res.ma2, h[i]); } res.sum += h[i]; } } for (int i = id_block(l); ++i < id_block(r);) { if(res.ma1 < infor[i].ma1) { res.ma2 = res.ma1; res.ma1 = infor[i].ma1; res.fr = infor[i].fr; } else { if(res.ma1 == infor[i].ma1) res.fr += infor[i].fr; else res.ma2 = max(res.ma2, infor[i].ma1); } res.sum += infor[i].sum; } return res; } void cut(int l, int r, int k) { l--, r--; while(k > 0) { node res = get(l, r); if(res.ma1 == 0) break; long long tmp = 1LL * res.fr * (res.ma1 - res.ma2); if(k >= tmp) { k -= tmp; for (int i = l; i <= min(r, end_block(id_block(l))); ++i) { h[i] = min(h[i], res.ma2); } build_block(id_block(l)); if(id_block(l) != id_block(r)) { for (int i = begin_block(id_block(r)); i <= r; ++i) { h[i] = min(h[i], res.ma2); } build_block(id_block(r)); } for (int i = id_block(l); ++i < id_block(r);) { if(infor[i].ma1 == res.ma1) { infor[i].lazy = res.ma2; infor[i].ma1 = res.ma2; infor[i].sum -= 1LL * infor[i].fr * (res.ma1 - res.ma2); } if(infor[i].ma1 == infor[i].ma2) build_block(i); } } else { int rem = k / res.fr; for (int i = l; i <= min(r, end_block(id_block(l))); ++i) { if(h[i] == res.ma1) h[i] -= rem; } build_block(id_block(l)); for (int i = id_block(l); ++i < id_block(r);) { if(infor[i].ma1 == res.ma1) { infor[i].ma1 -= rem; infor[i].lazy = infor[i].ma1; infor[i].sum -= 1LL * infor[i].fr * rem; } } if(id_block(l) != id_block(r)) { for (int i = begin_block(id_block(r)); i <= r; ++i) { if(h[i] == res.ma1) h[i] -= rem; } build_block(id_block(r)); } k = k % res.fr; res.ma1 -= rem; for (int i = l; i <= end_block(id_block(l)) && k > 0; ++i) { if(h[i] == res.ma1) { h[i]--; k--; } } build_block(id_block(l)); for (int i = id_block(l); ++i < id_block(r);) { if(infor[i].ma1 != res.ma1) continue; if(infor[i].fr <= k) { k -= infor[i].fr; infor[i].lazy = --infor[i].ma1; infor[i].sum -= infor[i].fr; if(infor[i].ma1 == infor[i].ma2) build_block(i); } else { build_block(i); for (int j = begin_block(i); j <= end_block(i) && k > 0; ++j) { if(h[j] == res.ma1) h[j]--, k--; } build_block(i); break; } } assert(k <= 0); } } } void magic(int i, int x) { i--; build_block(id_block(i)); h[i] = x; build_block(id_block(i)); } long long inspect(int l, int r) { return get(l - 1, r - 1).sum; } #ifdef LOCAL #include <iostream> using namespace std; int main() { freopen("TASK.inp", "r", stdin); freopen("TASK.out", "w", stdout); int N, Q; cin >> N >> Q; int h[N + 1]; for (int i = 1; i <= N; ++i) cin >> h[i]; initialise(N, Q, h); for (int i = 1; i <= Q; ++i) { int t; cin >> t; if (t == 1) { int l, r, k; cin >> l >> r >> k; cut(l, r, k); } else if (t == 2) { int i, x; cin >> i >> x; magic(i, x); } else { int l, r; cin >> l >> r; cout << inspect(l, r) << '\n'; } } return 0; } #endif // LOCAL // Dream it. Wish it. Do it.
#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...