#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[600 + 5] ;
int n, h[MAX], BLOCK;
int id_block(int pos) {
return (pos) / 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++;
else infor[id].ma2 = max(infor[id].ma2, h[i]);
}
}
infor[id].lazy = INF;
}
void initialise(int _n, int q, int _h[]) {
n = _n;
BLOCK = sqrt(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 * rem;
res.ma1 -= rem;
assert(k < res.fr);
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;
}
}
if(id_block(l) != id_block(r)) {
for (int i = begin_block(id_block(r)); i <= r && k > 0; ++i) {
if(h[i] == res.ma1) h[i]--, k--;
}
build_block(id_block(r));
}
// 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 time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
215 ms |
1364 KB |
Output is correct |
| 4 |
Incorrect |
206 ms |
1360 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
8 ms |
4440 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
215 ms |
1364 KB |
Output is correct |
| 4 |
Incorrect |
206 ms |
1360 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
215 ms |
1364 KB |
Output is correct |
| 4 |
Incorrect |
206 ms |
1360 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
