Submission #1873077
Source Code Expand
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#define ri register int
using namespace std;
typedef long long LL;
const int N = 3e5 + 5;
int a[N], n, id[N];
LL L[N], R[N], A[N], B[N], g[N], sum[N], suf[N];
inline void DivideAndConquer(int l, int r, LL *L, LL *R, LL *dp) {
if (l == r) {
dp[l] = max(dp[l], L[l - 1] + R[l + 1] - a[l] + 1);
return;
}
int mid = (l + r) >> 1;
int top = 0;
for (int i = l - 1; i <= mid; i ++) {
g[i] = L[i] + sum[i] + 1LL * i * (i - 1) / 2;
while (top > 1 && (g[i] - g[id[top]]) * (id[top] - id[top - 1]) >= (g[id[top]] - g[id[top - 1]]) * (i - id[top])) top --;
id[++ top] = i;
}
for (int i = mid + 1; i <= r; i ++) {
while (top > 1 && g[id[top]] - g[id[top - 1]] <= 1LL * i * (id[top] - id[top - 1])) top --;
suf[i] = g[id[top]] - sum[i] + 1LL * i * (i + 1) / 2 - 1LL * id[top] * i + R[i + 1];
}
LL t = suf[r];
dp[r] = max(dp[r], t);
for (int i = r - 1; i >= mid; i --) {
t = max(t, suf[i]);
dp[i] = max(dp[i], t);
}
DivideAndConquer(l, mid, L, R, dp);
DivideAndConquer(mid + 1, r, L, R, dp);
}
inline void DP(LL *dp) {
int top = 1;
LL S = 0;
id[1] = 0;
for (int i = 1; i <= n; i ++) {
S += a[i];
while (top > 1 && g[id[top]] - g[id[top - 1]] <= 1LL * i * (id[top] - id[top - 1])) top --;
dp[i] = g[id[top]] - S + 1LL * i * (i + 1) / 2 - 1LL * id[top] * i;
dp[i] = max(dp[i], dp[i - 1]);
g[i] = dp[i] + S + 1LL * i * (i - 1) / 2;
while (top > 1 && (g[i] - g[id[top]]) * (id[top] - id[top - 1]) >= (g[id[top]] - g[id[top - 1]]) * (i - id[top])) top --;
id[++ top] = i;
}
}
int main() {
scanf("%d", &n);
for (ri i = 1; i <= n; i ++) scanf("%d", &a[i]);
DP(L); reverse(a + 1, a + n + 1);
DP(R); reverse(R + 1, R + n + 1);
reverse(a + 1, a + n + 1);
for (ri i = 1; i <= n; i ++) sum[i] = sum[i - 1] + a[i];
DivideAndConquer(1, n, L, R, A);
for (ri i = (n >> 1); i; i --) {
swap(L[i], L[n - i + 1]);
swap(R[i], R[n - i + 1]);
swap(a[i], a[n - i + 1]);
}
for (ri i = 1; i <= n; i ++) sum[i] = sum[i - 1] + a[i];
DivideAndConquer(1, n, R, L, B);
for (ri i = (n >> 1); i; i --) {
swap(L[i], L[n - i + 1]);
swap(R[i], R[n - i + 1]);
swap(a[i], a[n - i + 1]);
swap(B[i], B[n - i + 1]);
}
int m, p, v;
scanf("%d", &m);
for (; m; m --) {
scanf("%d%d", &p, &v);
printf("%lld\n", max(L[p - 1] + R[p + 1], max(A[p], B[p]) - v + a[p]));
}
return 0;
}
Submission Info
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:56:18: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
^
./Main.cpp:57:50: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
for (ri i = 1; i <= n; i ++) scanf("%d", &a[i]);
^
./Main.cpp:77:18: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &m);
^
./Main.cpp:79:26: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &p, &v);
^
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
0 / 1400 |
Status |
|
|
Set Name |
Test Cases |
Sample |
sample_01.txt, sample_02.txt |
All |
sample_01.txt, sample_02.txt, subtask_1_high_equaly_01.txt, subtask_1_high_equaly_02.txt, subtask_1_high_equaly_03.txt, subtask_1_high_equaly_04.txt, subtask_1_high_rand_01.txt, subtask_1_high_rand_02.txt, subtask_1_high_rand_03.txt, subtask_1_high_rand_04.txt, subtask_1_killer_01.txt, subtask_1_killer_02.txt, subtask_1_low_equaly_01.txt, subtask_1_low_equaly_02.txt, subtask_1_low_equaly_03.txt, subtask_1_low_equaly_04.txt, subtask_1_low_rand_01.txt, subtask_1_low_rand_02.txt, subtask_1_low_rand_03.txt, subtask_1_low_rand_04.txt, subtask_1_max_high_equaly_01.txt, subtask_1_max_high_equaly_02.txt, subtask_1_max_high_equaly_03.txt, subtask_1_max_high_equaly_04.txt, subtask_1_max_high_rand_01.txt, subtask_1_max_high_rand_02.txt, subtask_1_max_high_rand_03.txt, subtask_1_max_high_rand_04.txt, subtask_1_max_low_equaly_01.txt, subtask_1_max_low_equaly_02.txt, subtask_1_max_low_equaly_03.txt, subtask_1_max_low_equaly_04.txt, subtask_1_max_low_rand_01.txt, subtask_1_max_low_rand_02.txt, subtask_1_max_low_rand_03.txt, subtask_1_max_low_rand_04.txt, subtask_1_max_rand_equaly_01.txt, subtask_1_max_rand_equaly_02.txt, subtask_1_max_rand_equaly_03.txt, subtask_1_max_rand_equaly_04.txt, subtask_1_max_rand_rand_01.txt, subtask_1_max_rand_rand_02.txt, subtask_1_max_rand_rand_03.txt, subtask_1_max_rand_rand_04.txt, subtask_1_min_rand_rand_01.txt, subtask_1_min_rand_rand_02.txt, subtask_1_rand_equaly_01.txt, subtask_1_rand_equaly_02.txt, subtask_1_rand_equaly_03.txt, subtask_1_rand_equaly_04.txt, subtask_1_rand_rand_01.txt, subtask_1_rand_rand_02.txt, subtask_1_rand_rand_03.txt, subtask_1_rand_rand_04.txt |
Case Name |
Status |
Exec Time |
Memory |
sample_01.txt |
AC |
5 ms |
14588 KB |
sample_02.txt |
AC |
4 ms |
14592 KB |
subtask_1_high_equaly_01.txt |
WA |
103 ms |
18176 KB |
subtask_1_high_equaly_02.txt |
WA |
72 ms |
17792 KB |
subtask_1_high_equaly_03.txt |
WA |
23 ms |
14976 KB |
subtask_1_high_equaly_04.txt |
WA |
156 ms |
18560 KB |
subtask_1_high_rand_01.txt |
WA |
99 ms |
18176 KB |
subtask_1_high_rand_02.txt |
WA |
74 ms |
17792 KB |
subtask_1_high_rand_03.txt |
WA |
104 ms |
18176 KB |
subtask_1_high_rand_04.txt |
WA |
140 ms |
18432 KB |
subtask_1_killer_01.txt |
AC |
4 ms |
14592 KB |
subtask_1_killer_02.txt |
AC |
4 ms |
14592 KB |
subtask_1_low_equaly_01.txt |
WA |
165 ms |
19840 KB |
subtask_1_low_equaly_02.txt |
WA |
99 ms |
18688 KB |
subtask_1_low_equaly_03.txt |
WA |
115 ms |
19200 KB |
subtask_1_low_equaly_04.txt |
WA |
55 ms |
17664 KB |
subtask_1_low_rand_01.txt |
WA |
130 ms |
19328 KB |
subtask_1_low_rand_02.txt |
WA |
95 ms |
18432 KB |
subtask_1_low_rand_03.txt |
WA |
82 ms |
18304 KB |
subtask_1_low_rand_04.txt |
WA |
163 ms |
19840 KB |
subtask_1_max_high_equaly_01.txt |
WA |
238 ms |
20224 KB |
subtask_1_max_high_equaly_02.txt |
WA |
241 ms |
20480 KB |
subtask_1_max_high_equaly_03.txt |
WA |
246 ms |
20736 KB |
subtask_1_max_high_equaly_04.txt |
WA |
245 ms |
19840 KB |
subtask_1_max_high_rand_01.txt |
WA |
248 ms |
20736 KB |
subtask_1_max_high_rand_02.txt |
WA |
243 ms |
20224 KB |
subtask_1_max_high_rand_03.txt |
WA |
245 ms |
20224 KB |
subtask_1_max_high_rand_04.txt |
WA |
240 ms |
20480 KB |
subtask_1_max_low_equaly_01.txt |
WA |
223 ms |
20992 KB |
subtask_1_max_low_equaly_02.txt |
WA |
211 ms |
21376 KB |
subtask_1_max_low_equaly_03.txt |
WA |
227 ms |
20992 KB |
subtask_1_max_low_equaly_04.txt |
WA |
222 ms |
21376 KB |
subtask_1_max_low_rand_01.txt |
WA |
210 ms |
21376 KB |
subtask_1_max_low_rand_02.txt |
WA |
223 ms |
20992 KB |
subtask_1_max_low_rand_03.txt |
WA |
224 ms |
21376 KB |
subtask_1_max_low_rand_04.txt |
WA |
220 ms |
21376 KB |
subtask_1_max_rand_equaly_01.txt |
WA |
243 ms |
19584 KB |
subtask_1_max_rand_equaly_02.txt |
WA |
243 ms |
19584 KB |
subtask_1_max_rand_equaly_03.txt |
WA |
236 ms |
19584 KB |
subtask_1_max_rand_equaly_04.txt |
WA |
247 ms |
19584 KB |
subtask_1_max_rand_rand_01.txt |
WA |
235 ms |
19584 KB |
subtask_1_max_rand_rand_02.txt |
WA |
241 ms |
19584 KB |
subtask_1_max_rand_rand_03.txt |
WA |
238 ms |
19584 KB |
subtask_1_max_rand_rand_04.txt |
WA |
234 ms |
19584 KB |
subtask_1_min_rand_rand_01.txt |
AC |
4 ms |
14592 KB |
subtask_1_min_rand_rand_02.txt |
AC |
4 ms |
14592 KB |
subtask_1_rand_equaly_01.txt |
WA |
13 ms |
14720 KB |
subtask_1_rand_equaly_02.txt |
WA |
149 ms |
18432 KB |
subtask_1_rand_equaly_03.txt |
WA |
67 ms |
17408 KB |
subtask_1_rand_equaly_04.txt |
WA |
112 ms |
18048 KB |
subtask_1_rand_rand_01.txt |
WA |
164 ms |
19072 KB |
subtask_1_rand_rand_02.txt |
WA |
98 ms |
17792 KB |
subtask_1_rand_rand_03.txt |
WA |
144 ms |
18816 KB |
subtask_1_rand_rand_04.txt |
WA |
76 ms |
17280 KB |