#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 505050;
int n, a[N], d[N], yes[N];
struct seg {
ll sum[8 * N]; int tree[8 * N], lazy[8 * N];
void push(int l, int r, int x) {
if (lazy[x]) {
tree[x] = lazy[x];
sum[x] = 1ll * (r - l + 1) * lazy[x];
if (l != r) {
lazy[2 * x] = lazy[x];
lazy[2 * x + 1] = lazy[x];
}
lazy[x] = 0;
}
}
void update(int a, int b, int v, int l, int r, int x) {
push(l, r, x);
if (b < l || a > r)
return;
if (a <= l && r <= b) {
lazy[x] = v; push(l, r, x);
return;
}
int m = (l + r) / 2;
update(a, b, v, l, m, 2 * x);
update(a, b, v, m + 1, r, 2 * x + 1);
tree[x] = max(tree[2 * x], tree[2 * x + 1]);
sum[x] = sum[2 * x] + sum[2 * x + 1];
}
int query(int k, int l, int r, int x) {
push(l, r, x);
if (l == r)
return l;
int m = (l + r) / 2;
push(l, m, 2 * x);
if (tree[2 * x] > k)
return query(k, l, m, 2 * x);
else
return query(k, m + 1, r, 2 * x + 1);
}
ll get_sum(int a, int b, int l, int r, int x) {
push(l, r, x);
if (b < l || a > r)
return 0ll;
if (a <= l && r <= b)
return sum[x];
int m = (l + r) / 2;
return get_sum(a, b, l, m, 2 * x) + get_sum(a, b, m + 1, r, 2 * x + 1);
}
} t1;
int main() {
cin.tie(0); ios_base::sync_with_stdio(0);
cin >> n;
ll ans = 0;
for (int i = 1; i <= n; i++) {
cin >> a[i];
if (a[i] != -1)
ans += a[i];
d[i] = 1e9;
}
int p = -1, q = -1;
for (int i = 1; i <= n; i++) {
if (a[i] == -1)
p = i;
else {
if (p != -1)
d[i] = i - p;
}
}
p = -1;
for (int i = n; i >= 1; i--) {
if (a[i] == -1)
p = i;
else {
if (p != -1)
d[i] = min(d[i], p - i);
if (p != -1 && p < q)
yes[i] = 1;
if (q == -1)
yes[i] = 2;
if (a[i] != 0)
q = i;
}
}
t1.update(n, 2 * n, 1e9, 1, 2 * n, 1);
int l = n, x = -1, offset = 0;
for (int i = 1; i <= n; i++) {
if (a[i] <= 0) {
offset++;
continue;
}
int p = t1.query(2 * d[i], 1, 2 * n, 1);
ll s = t1.get_sum(1, p - 1, 1, 2 * n, 1) + offset;
if (s <= 2 * (i - 1)) {
int r = (2 * (i - 1) - s) / (2 * d[i]);
if (yes[i])
r = min(r, a[i] - 2);
else
r = min(r, a[i] - 1);
if (r != -1)
t1.update(p, p + r, 2 * d[i], 1, 2 * n, 1);
}
if (yes[i] == 1)
--l;
if (yes[i] == 2) {
x = i;
break;
}
++offset;
}
p = t1.query((int)1e9 - 1, 1, 2 * n, 1);
if (a[x] && offset + t1.get_sum(l, p - 1, 1, 2 * n, 1) <= 2 * (x - 1))
--l;
cout << ans - (p - l);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
