| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 620816 | 2022-08-03T09:29:54 Z | patrikpavic2 | Snowball (JOI21_ho_t2) | C++17 | 138 ms | 15308 KB |
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 2e5 + 500;
typedef long long ll;
int n, q;
ll A[N], w[N];
ll dpL[N], dpR[N], ans[N];
int main(){
scanf("%d%d", &n, &q);
for(int i = 0;i < n;i++)
scanf("%lld", A + i);
for(int i = 1;i <= q;i++)
scanf("%lld", w + i);
ll cur = 0;
for(int i = 1;i <= q;i++){
cur += w[i];
dpL[i] = min(dpL[i - 1], cur);
dpR[i] = max(dpR[i - 1], cur);
}
ans[0] -= dpL[q]; ans[n - 1] += dpR[q];
for(int i = 0;i + 1 < n;i++){
ll raz = A[i + 1] - A[i];
int j = 0;
for(int k = 17;k >= 0;k--){
if(j + (1 << k) > q) continue;
if(-dpL[j + (1 << k)] + dpR[j + (1 << k)] <= raz)
j += (1 << k);
}
ans[i] += dpR[j];
ans[i + 1] -= dpL[j];
if(j < q){
if(w[j + 1] > 0)
ans[i] += raz + dpL[j] - dpR[j];
else
ans[i + 1] += raz + dpL[j] - dpR[j];
}
}
for(int i = 0;i < n;i++)
printf("%lld\n", ans[i]);
return 0;
}
Compilation message
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 1 ms | 472 KB | Output is correct |
| 2 | Correct | 2 ms | 340 KB | Output is correct |
| 3 | Correct | 1 ms | 340 KB | Output is correct |
| 4 | Correct | 2 ms | 348 KB | Output is correct |
| 5 | Correct | 2 ms | 340 KB | Output is correct |
| 6 | Correct | 1 ms | 440 KB | Output is correct |
| 7 | Correct | 1 ms | 340 KB | Output is correct |
| 8 | Correct | 1 ms | 340 KB | Output is correct |
| 9 | Correct | 2 ms | 340 KB | Output is correct |
| 10 | Correct | 1 ms | 436 KB | Output is correct |
| 11 | Correct | 1 ms | 436 KB | Output is correct |
| 12 | Correct | 0 ms | 212 KB | Output is correct |
| 13 | Correct | 0 ms | 212 KB | Output is correct |
| 14 | Correct | 1 ms | 212 KB | Output is correct |
| 15 | Correct | 2 ms | 468 KB | Output is correct |
| 16 | Correct | 2 ms | 356 KB | Output is correct |
| 17 | Correct | 2 ms | 340 KB | Output is correct |
| 18 | Correct | 0 ms | 212 KB | Output is correct |
| 19 | Correct | 2 ms | 384 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 1 ms | 472 KB | Output is correct |
| 2 | Correct | 2 ms | 340 KB | Output is correct |
| 3 | Correct | 1 ms | 340 KB | Output is correct |
| 4 | Correct | 2 ms | 348 KB | Output is correct |
| 5 | Correct | 2 ms | 340 KB | Output is correct |
| 6 | Correct | 1 ms | 440 KB | Output is correct |
| 7 | Correct | 1 ms | 340 KB | Output is correct |
| 8 | Correct | 1 ms | 340 KB | Output is correct |
| 9 | Correct | 2 ms | 340 KB | Output is correct |
| 10 | Correct | 1 ms | 436 KB | Output is correct |
| 11 | Correct | 1 ms | 436 KB | Output is correct |
| 12 | Correct | 0 ms | 212 KB | Output is correct |
| 13 | Correct | 0 ms | 212 KB | Output is correct |
| 14 | Correct | 1 ms | 212 KB | Output is correct |
| 15 | Correct | 2 ms | 468 KB | Output is correct |
| 16 | Correct | 2 ms | 356 KB | Output is correct |
| 17 | Correct | 2 ms | 340 KB | Output is correct |
| 18 | Correct | 0 ms | 212 KB | Output is correct |
| 19 | Correct | 2 ms | 384 KB | Output is correct |
| 20 | Correct | 35 ms | 7116 KB | Output is correct |
| 21 | Correct | 40 ms | 6904 KB | Output is correct |
| 22 | Correct | 30 ms | 6660 KB | Output is correct |
| 23 | Correct | 33 ms | 6560 KB | Output is correct |
| 24 | Correct | 41 ms | 7088 KB | Output is correct |
| 25 | Correct | 126 ms | 13388 KB | Output is correct |
| 26 | Correct | 113 ms | 13460 KB | Output is correct |
| 27 | Correct | 126 ms | 12956 KB | Output is correct |
| 28 | Correct | 111 ms | 13128 KB | Output is correct |
| 29 | Correct | 107 ms | 12700 KB | Output is correct |
| 30 | Correct | 107 ms | 11984 KB | Output is correct |
| 31 | Correct | 88 ms | 11584 KB | Output is correct |
| 32 | Correct | 99 ms | 11552 KB | Output is correct |
| 33 | Correct | 11 ms | 1652 KB | Output is correct |
| 34 | Correct | 117 ms | 13776 KB | Output is correct |
| 35 | Correct | 116 ms | 13096 KB | Output is correct |
| 36 | Correct | 127 ms | 13504 KB | Output is correct |
| 37 | Correct | 138 ms | 13164 KB | Output is correct |
| 38 | Correct | 107 ms | 13004 KB | Output is correct |
| 39 | Correct | 117 ms | 13316 KB | Output is correct |
| 40 | Correct | 93 ms | 13220 KB | Output is correct |
| 41 | Correct | 36 ms | 7652 KB | Output is correct |
| 42 | Correct | 84 ms | 11612 KB | Output is correct |
| 43 | Correct | 114 ms | 14864 KB | Output is correct |
| 44 | Correct | 43 ms | 7532 KB | Output is correct |
| 45 | Correct | 76 ms | 13076 KB | Output is correct |
| 46 | Correct | 124 ms | 15024 KB | Output is correct |
| 47 | Correct | 109 ms | 15308 KB | Output is correct |
| 48 | Correct | 111 ms | 15308 KB | Output is correct |