Submission #1873068
Source Code Expand
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#define ri register int
#define int long long
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; 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;
}
}
signed main() {
scanf("%lld", &n);
for (ri i = 1; i <= n; i ++) scanf("%lld", &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("%lld", &m);
for (; m; m --) {
scanf("%lld%lld", &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:57:20: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld", &n);
^
./Main.cpp:58:52: 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("%lld", &a[i]);
^
./Main.cpp:78:20: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld", &m);
^
./Main.cpp:80:30: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld%lld", &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 |
4 ms |
16640 KB |
sample_02.txt |
AC |
4 ms |
16640 KB |
subtask_1_high_equaly_01.txt |
WA |
88 ms |
20224 KB |
subtask_1_high_equaly_02.txt |
WA |
64 ms |
19840 KB |
subtask_1_high_equaly_03.txt |
WA |
23 ms |
17024 KB |
subtask_1_high_equaly_04.txt |
WA |
142 ms |
20608 KB |
subtask_1_high_rand_01.txt |
WA |
89 ms |
20224 KB |
subtask_1_high_rand_02.txt |
WA |
65 ms |
19840 KB |
subtask_1_high_rand_03.txt |
WA |
95 ms |
20224 KB |
subtask_1_high_rand_04.txt |
WA |
126 ms |
20480 KB |
subtask_1_killer_01.txt |
AC |
4 ms |
16640 KB |
subtask_1_killer_02.txt |
AC |
4 ms |
16640 KB |
subtask_1_low_equaly_01.txt |
WA |
153 ms |
21888 KB |
subtask_1_low_equaly_02.txt |
WA |
87 ms |
20736 KB |
subtask_1_low_equaly_03.txt |
WA |
102 ms |
21376 KB |
subtask_1_low_equaly_04.txt |
WA |
49 ms |
19712 KB |
subtask_1_low_rand_01.txt |
WA |
123 ms |
21376 KB |
subtask_1_low_rand_02.txt |
WA |
87 ms |
20480 KB |
subtask_1_low_rand_03.txt |
WA |
78 ms |
20352 KB |
subtask_1_low_rand_04.txt |
WA |
146 ms |
21888 KB |
subtask_1_max_high_equaly_01.txt |
WA |
221 ms |
22528 KB |
subtask_1_max_high_equaly_02.txt |
WA |
232 ms |
22784 KB |
subtask_1_max_high_equaly_03.txt |
WA |
228 ms |
23040 KB |
subtask_1_max_high_equaly_04.txt |
WA |
222 ms |
22272 KB |
subtask_1_max_high_rand_01.txt |
WA |
230 ms |
23168 KB |
subtask_1_max_high_rand_02.txt |
WA |
225 ms |
22528 KB |
subtask_1_max_high_rand_03.txt |
WA |
217 ms |
22528 KB |
subtask_1_max_high_rand_04.txt |
WA |
219 ms |
22784 KB |
subtask_1_max_low_equaly_01.txt |
WA |
204 ms |
23424 KB |
subtask_1_max_low_equaly_02.txt |
WA |
195 ms |
23680 KB |
subtask_1_max_low_equaly_03.txt |
WA |
213 ms |
23424 KB |
subtask_1_max_low_equaly_04.txt |
WA |
206 ms |
23680 KB |
subtask_1_max_low_rand_01.txt |
WA |
194 ms |
23680 KB |
subtask_1_max_low_rand_02.txt |
WA |
208 ms |
23424 KB |
subtask_1_max_low_rand_03.txt |
WA |
201 ms |
23680 KB |
subtask_1_max_low_rand_04.txt |
WA |
201 ms |
23680 KB |
subtask_1_max_rand_equaly_01.txt |
WA |
217 ms |
21888 KB |
subtask_1_max_rand_equaly_02.txt |
WA |
222 ms |
21888 KB |
subtask_1_max_rand_equaly_03.txt |
WA |
216 ms |
21888 KB |
subtask_1_max_rand_equaly_04.txt |
WA |
215 ms |
21888 KB |
subtask_1_max_rand_rand_01.txt |
WA |
229 ms |
21888 KB |
subtask_1_max_rand_rand_02.txt |
WA |
222 ms |
21888 KB |
subtask_1_max_rand_rand_03.txt |
WA |
228 ms |
21888 KB |
subtask_1_max_rand_rand_04.txt |
WA |
224 ms |
22016 KB |
subtask_1_min_rand_rand_01.txt |
AC |
4 ms |
16640 KB |
subtask_1_min_rand_rand_02.txt |
AC |
4 ms |
16640 KB |
subtask_1_rand_equaly_01.txt |
WA |
13 ms |
16768 KB |
subtask_1_rand_equaly_02.txt |
WA |
132 ms |
20480 KB |
subtask_1_rand_equaly_03.txt |
WA |
63 ms |
19456 KB |
subtask_1_rand_equaly_04.txt |
WA |
101 ms |
20096 KB |
subtask_1_rand_rand_01.txt |
WA |
146 ms |
21248 KB |
subtask_1_rand_rand_02.txt |
WA |
95 ms |
19840 KB |
subtask_1_rand_rand_03.txt |
WA |
130 ms |
20864 KB |
subtask_1_rand_rand_04.txt |
WA |
70 ms |
19328 KB |