Submission #1873269
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; 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);
memset(A, - 0x3f, sizeof (LL) * (n + 2));
memset(B, - 0x3f, sizeof (LL) * (n + 2));
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:59: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:79:18: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &m);
^
./Main.cpp:81: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 |
1400 / 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 |
14592 KB |
sample_02.txt |
AC |
4 ms |
14592 KB |
subtask_1_high_equaly_01.txt |
AC |
98 ms |
18176 KB |
subtask_1_high_equaly_02.txt |
AC |
71 ms |
17792 KB |
subtask_1_high_equaly_03.txt |
AC |
22 ms |
14720 KB |
subtask_1_high_equaly_04.txt |
AC |
155 ms |
18560 KB |
subtask_1_high_rand_01.txt |
AC |
98 ms |
18176 KB |
subtask_1_high_rand_02.txt |
AC |
71 ms |
17792 KB |
subtask_1_high_rand_03.txt |
AC |
104 ms |
18176 KB |
subtask_1_high_rand_04.txt |
AC |
134 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 |
AC |
160 ms |
19840 KB |
subtask_1_low_equaly_02.txt |
AC |
99 ms |
18688 KB |
subtask_1_low_equaly_03.txt |
AC |
114 ms |
19200 KB |
subtask_1_low_equaly_04.txt |
AC |
54 ms |
17664 KB |
subtask_1_low_rand_01.txt |
AC |
126 ms |
19200 KB |
subtask_1_low_rand_02.txt |
AC |
94 ms |
18432 KB |
subtask_1_low_rand_03.txt |
AC |
81 ms |
18304 KB |
subtask_1_low_rand_04.txt |
AC |
167 ms |
19840 KB |
subtask_1_max_high_equaly_01.txt |
AC |
238 ms |
20096 KB |
subtask_1_max_high_equaly_02.txt |
AC |
238 ms |
20480 KB |
subtask_1_max_high_equaly_03.txt |
AC |
242 ms |
20736 KB |
subtask_1_max_high_equaly_04.txt |
AC |
233 ms |
19840 KB |
subtask_1_max_high_rand_01.txt |
AC |
241 ms |
20736 KB |
subtask_1_max_high_rand_02.txt |
AC |
240 ms |
20224 KB |
subtask_1_max_high_rand_03.txt |
AC |
241 ms |
20224 KB |
subtask_1_max_high_rand_04.txt |
AC |
242 ms |
20480 KB |
subtask_1_max_low_equaly_01.txt |
AC |
219 ms |
20992 KB |
subtask_1_max_low_equaly_02.txt |
AC |
216 ms |
21376 KB |
subtask_1_max_low_equaly_03.txt |
AC |
222 ms |
20992 KB |
subtask_1_max_low_equaly_04.txt |
AC |
218 ms |
21376 KB |
subtask_1_max_low_rand_01.txt |
AC |
211 ms |
21376 KB |
subtask_1_max_low_rand_02.txt |
AC |
224 ms |
20992 KB |
subtask_1_max_low_rand_03.txt |
AC |
216 ms |
21376 KB |
subtask_1_max_low_rand_04.txt |
AC |
212 ms |
21376 KB |
subtask_1_max_rand_equaly_01.txt |
AC |
238 ms |
19584 KB |
subtask_1_max_rand_equaly_02.txt |
AC |
233 ms |
19584 KB |
subtask_1_max_rand_equaly_03.txt |
AC |
240 ms |
19584 KB |
subtask_1_max_rand_equaly_04.txt |
AC |
237 ms |
19584 KB |
subtask_1_max_rand_rand_01.txt |
AC |
242 ms |
19584 KB |
subtask_1_max_rand_rand_02.txt |
AC |
237 ms |
19584 KB |
subtask_1_max_rand_rand_03.txt |
AC |
237 ms |
19584 KB |
subtask_1_max_rand_rand_04.txt |
AC |
233 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 |
AC |
13 ms |
14720 KB |
subtask_1_rand_equaly_02.txt |
AC |
141 ms |
18432 KB |
subtask_1_rand_equaly_03.txt |
AC |
68 ms |
17408 KB |
subtask_1_rand_equaly_04.txt |
AC |
110 ms |
18048 KB |
subtask_1_rand_rand_01.txt |
AC |
160 ms |
19072 KB |
subtask_1_rand_rand_02.txt |
AC |
98 ms |
17792 KB |
subtask_1_rand_rand_03.txt |
AC |
142 ms |
18816 KB |
subtask_1_rand_rand_04.txt |
AC |
72 ms |
17280 KB |