#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 80100, maxblock = sqrt(maxn) + 10, inf = 1e9 + 10;
ll n, q, h[maxn], block;
ll lazy[maxblock], sum[maxblock];
ll mx1[maxblock], fr[maxblock], mx2[maxblock];
void initialise(int N, int Q, int H[])
{
n = N;
q = Q;
block = max((ll)sqrt(n), (ll)(1));
for (int i = 1; i <= n; i ++)
{
h[i] = H[i];
lazy[i / block] = inf;
sum[i / block] += h[i];
if (h[i] > mx1[i / block])
{
mx2[i / block] = mx1[i / block];
mx1[i / block] = h[i];
fr[i / block] = 0;
}
if (h[i] == mx1[i / block])
{
fr[i / block] ++;
}
else if (h[i] > mx2[i / block])
{
mx2[i / block] = h[i];
}
}
}
void update_block(int bl)
{
mx1[bl] = mx2[bl] = 0;
fr[bl] = 0;
sum[bl] = 0;
for (int i = bl * block; i < (bl + 1) * block; i ++)
{
h[i] = min(h[i], lazy[bl]);
sum[bl] += h[i];
if (h[i] > mx1[bl])
{
mx2[bl] = mx1[bl];
mx1[bl] = h[i];
fr[bl] = 0;
}
if (h[i] == mx1[bl])
{
fr[bl] ++;
}
else if (h[i] > mx2[bl])
{
mx2[bl] = h[i];
}
}
lazy[bl] = inf;
}
void magic(int i, int x)
{
update_block(i / block);
h[i] = (ll)x;
update_block(i / block);
}
void cut(int l, int r, int k)
{
///cout << l << " : " << r << " : " << k << endl;;
while(k > 0)
{
ll max1 = 0, max2 = 0, freq = 0;
///update_block(l / block);
///update_block(r / block);
for (int i = l; i < min((ll)r + 1, (l / block + 1) * block); i ++)
{
h[i] = min(h[i], lazy[i / block]);
if (h[i] > max1)
{
max2 = max1;
max1 = h[i];
freq = 0;
}
if (h[i] == max1)
freq ++;
else if (h[i] > max2)
max2 = h[i];
}
for (int bl = l / block + 1; bl < r / block; bl ++)
{
if (mx1[bl] > max1)
{
max2 = max1;
max1 = mx1[bl];
freq = 0;
}
if (mx1[bl] == max1)
freq += fr[bl];
else if (mx1[bl] > max2)
max2 = mx1[bl];
if (mx2[bl] > max2)
max2 = mx2[bl];
}
if (l / block != r / block)
{
for (int i = (r / block) * block; i <= r; i ++)
{
h[i] = min(h[i], lazy[i / block]);
if (h[i] > max1)
{
max2 = max1;
max1 = h[i];
freq = 0;
}
if (h[i] == max1)
freq ++;
else if (h[i] > max2)
max2 = h[i];
}
}
if (max1 == 0)
break;
///cout << "heree " << max1 << " " << max2 << " " << freq << endl;
if (freq * (max1 - max2) <= k)
{
k = k - freq * (max1 - max2);
for (int i = l; i < min((ll)r + 1, (l / block + 1) * block); i ++)
{
if (h[i] > max2)
h[i] = max2;
}
update_block(l / block);
if (l / block != r / block)
{
for (int i = (r / block) * block; i <= r; i ++)
{
if (h[i] > max2)
h[i] = max2;
}
update_block(r / block);
}
for (int bl = l / block + 1; bl < r / block; bl ++)
{
if (mx1[bl] == max1)
{
lazy[bl] = max2;
sum[bl] -= fr[bl] * (mx1[bl] - max2);
mx1[bl] = max2;
}
if (mx1[bl] == mx2[bl])
update_block(bl);
}
}
else
{
ll dec = k / freq;
for (int i = l; i < min((ll)(r + 1), (l / block + 1) * block); i ++)
{
if (h[i] == max1)
h[i] -= dec;
}
update_block(l / block);
if (l / block != r / block)
{
for (int i = (r / block) * block; i <= r; i ++)
{
if (h[i] == max1)
h[i] -= dec;
}
update_block(r / block);
}
for (int bl = l / block + 1; bl < r / block; bl ++)
{
if (mx1[bl] == max1)
{
lazy[bl] = mx1[bl] - dec;
sum[bl] -= fr[bl] * dec;
mx1[bl] -= dec;
}
}
k = k - dec * freq;
max1 -= dec;
for (int i = l; i < min((ll)(r + 1), (l / block + 1) * block) && k > 0; i ++)
{
if (h[i] == max1)
h[i] --, k --;
}
update_block(l / block);
for (int bl = l / block + 1; bl < r / block; bl ++)
{
if (mx1[bl] == max1)
{
if (fr[bl] <= k)
{
k -= fr[bl];
lazy[bl] = mx1[bl] - 1;
sum[bl] -= fr[bl];
mx1[bl] --;
if (mx1[bl] == mx2[bl])
update_block(bl);
}
else
{
update_block(bl);
for (int i = bl * block; i < (bl + 1) * block && k > 0; i ++)
if (h[i] == max1)
h[i] --, k --;
update_block(bl);
break;
}
}
}
if (l / block != r / block)
{
for (int i = (r / block) * block; i <= r && k > 0; i ++)
{
if (h[i] == max1)
h[i] --, k --;
}
update_block(r / block);
}
break;
}
}
}
ll inspect(int l, int r)
{
/**for (int i = 1; i <= n; i ++)
update_block(i / block);
for (int i = 1; i <= n; i ++)
cout << h[i] << " ";
cout << endl;*/
///cout << l << " " << r << endl;
ll ans = 0;
update_block(l / block);
for (int i = l; i < min((ll)(r + 1), (l / block + 1) * block); i ++)
{
ans = ans + h[i];
}
if (l / block != r / block)
{
update_block(r / block);
for (int i = (r / block) * block; i <= r; i ++)
{
ans = ans + h[i];
}
}
for (int bl = l / block + 1; bl < r / block; bl ++)
{
ans = ans + sum[bl];
}
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
185 ms |
1612 KB |
Output is correct |
| 4 |
Correct |
202 ms |
1636 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
340 KB |
Output is correct |
| 2 |
Correct |
2 ms |
340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
340 KB |
Output is correct |
| 2 |
Correct |
2 ms |
340 KB |
Output is correct |
| 3 |
Runtime error |
9 ms |
7264 KB |
Execution killed with signal 11 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
7 ms |
4172 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
185 ms |
1612 KB |
Output is correct |
| 4 |
Correct |
202 ms |
1636 KB |
Output is correct |
| 5 |
Correct |
3 ms |
340 KB |
Output is correct |
| 6 |
Correct |
2 ms |
340 KB |
Output is correct |
| 7 |
Correct |
190 ms |
3616 KB |
Output is correct |
| 8 |
Correct |
206 ms |
3556 KB |
Output is correct |
| 9 |
Correct |
176 ms |
3564 KB |
Output is correct |
| 10 |
Correct |
203 ms |
3752 KB |
Output is correct |
| 11 |
Correct |
178 ms |
3752 KB |
Output is correct |
| 12 |
Correct |
600 ms |
3372 KB |
Output is correct |
| 13 |
Correct |
694 ms |
3236 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
185 ms |
1612 KB |
Output is correct |
| 4 |
Correct |
202 ms |
1636 KB |
Output is correct |
| 5 |
Correct |
3 ms |
340 KB |
Output is correct |
| 6 |
Correct |
2 ms |
340 KB |
Output is correct |
| 7 |
Runtime error |
9 ms |
7264 KB |
Execution killed with signal 11 |
| 8 |
Halted |
0 ms |
0 KB |
- |
