#include <stdio.h>
#include <string.h>
#define N 400000
#define INF 0x3f3f3f3f3f3f3f3fLL
long long min(long long a, long long b) { return a < b ? a : b; }
long long max(long long a, long long b) { return a > b ? a : b; }
int n, k;
int ww[N]; long long ss[N + 1];
int xx[N], yy[N], dd[N], pp[N], qq[N], hh[N], tt[N], ii[N]; long long dp[N];
int cross(int i, int j) {
int lower = -1, upper = k - yy[j] + 1;
while (upper - lower > 1) {
int d = (lower + upper) / 2;
if (dp[i] - ss[yy[i] + d] > dp[j] - ss[yy[j] + d])
upper = d;
else
lower = d;
}
return lower;
}
void merge(int i, int j) {
int u, v, d;
u = tt[i], v = hh[j];
while (1) {
d = cross(u, v);
if (u != hh[i] && cross(pp[u], u) <= d)
u = pp[u];
else if (v != tt[j] && cross(v, qq[v]) >= d)
v = qq[v];
else {
qq[u] = v, pp[v] = u;
break;
}
}
hh[j] = hh[i];
}
long long query(int i, int d) {
while (hh[i] != tt[i] && cross(hh[i], qq[hh[i]]) >= d)
hh[i] = qq[hh[i]];
return dp[hh[i]] - ss[yy[hh[i]] + d];
}
void dc(int il, int ir, int jl, int jr) {
int i, i_, j, d;
long long z, z_;
if (jl > jr)
return;
j = (jl + jr) / 2;
d = k - yy[j];
z_ = -INF, i_ = -1;
for (i = max(il, ii[j] + 1); i <= ir && i <= j; i++)
if (dp[i] != -INF) {
z = dp[i] - ss[yy[i] + d];
if (z_ < z)
z_ = z, i_ = i;
}
if (ii[j] >= 0)
z_ = max(z_, dp[ii[j]] - ss[xx[ii[j]]]);
else
z_ = max(z_, -ss[d]);
z_ += ss[k];
dc(il, i_, jl, j - 1), printf("%lld ", z_), dc(i_, ir, j + 1, jr);
}
int main() {
static int aa[N], qu[N];
int cnt, h, i, i_, j, a, y;
scanf("%d", &n);
memset(ii, -1, n * sizeof *ii);
for (i = 0; i < n; i++) {
scanf("%d", &aa[i]), aa[i]--;
if (aa[i] >= 0)
ii[aa[i]] = i;
}
for (a = 0; a < n; a++)
scanf("%d", &ww[a]);
k = 0;
for (a = 0; a < n; a++)
if ((i = ii[a]) != -1)
xx[i] = k;
else
ss[k + 1] = ss[k] + ww[a], k++;
for (i = 0; i < n; i++)
pp[i] = qq[i] = -1, hh[i] = tt[i] = i;
y = 0, a = -1, cnt = 0, h = 0;
for (j = 0; j < n; j++) {
if (aa[j] < 0)
y++;
yy[j] = y, dd[j] = xx[j] - yy[j];
a = max(a, aa[j]);
if (aa[j] == a && dd[j] >= 0) {
i_ = -1;
while (cnt && dd[i = qu[cnt - 1]] < dd[j]) {
if (i_ == -1)
i_ = i;
else
merge(i, i_);
cnt--;
}
dp[j] = cnt ? dp[i] - ss[xx[i]] : -ss[dd[j]];
if (i_ != -1)
dp[j] = max(dp[j], query(i_, dd[j]));
dp[j] += ss[xx[j]] + ww[aa[j]];
if (i_ != -1)
merge(i_, j);
qu[cnt++] = j;
} else
dp[i] = -INF;
h = min(h, cnt);
while (h < cnt && dd[qu[h]] >= k - y)
h++;
ii[j] = h == 0 ? -1 : qu[h - 1];
}
dc(0, n - 1, 0, n - 1), printf("\n");
return 0;
}
Compilation message
Main.c: In function 'main':
Main.c:79:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
79 | scanf("%d", &n);
| ^~~~~~~~~~~~~~~
Main.c:82:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
82 | scanf("%d", &aa[i]), aa[i]--;
| ^~~~~~~~~~~~~~~~~~~
Main.c:87:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
87 | scanf("%d", &ww[a]);
| ^~~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
468 KB |
Output is correct |
| 3 |
Correct |
6 ms |
1364 KB |
Output is correct |
| 4 |
Correct |
71 ms |
11600 KB |
Output is correct |
| 5 |
Correct |
113 ms |
22912 KB |
Output is correct |
| 6 |
Correct |
0 ms |
340 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
116 ms |
21196 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
