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

Submission Time
Task F - Contest with Drinks Hard
User The_Unbeatable
Language C++14 (GCC 5.4.1)
Score 0
Code Size 2559 Byte
Status WA
Exec Time 248 ms
Memory 21376 KB

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
AC × 2
AC × 6
WA × 48
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