/*
Keep track of prefix maximum and minimum as these things tell us the highest and the lowest points we reached so far with the snowballs
For each pair of two adjacent snowballs, we should binary search the point x at which maxq[x] + abs(minq[x]) >= v[i+1] - v[i] and then add accordingly
to each end based on where the last update came from
We should deal separately with the two extremes too
*/
#include <bits/stdc++.h>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n, q;
cin >> n >> q;
vector<long long> v(n+1);
for(int i = 1; i <= n; i++)
cin >> v[i];
vector<long long> minq(q+1), maxq(q+1);
long long sum = 0;
for(int i = 1; i <= q; i++)
{
long long x;
cin >> x;
sum += x;
minq[i] = min(minq[i-1], sum);
maxq[i] = max(maxq[i-1], sum);
}
vector<long long> ans(n+1);
for(int i = 1; i < n; i++)
{
int st = 1;
int dr = q;
int poz = 0;
while(st <= dr)
{
int mid = (st + dr) / 2;
if(abs(minq[mid]) + abs(maxq[mid]) < v[i+1] - v[i])
{
poz = mid;
st = mid + 1;
}
else
dr = mid - 1;
}
ans[i] += maxq[poz];
ans[i+1] += abs(minq[poz]);
if(poz != q && maxq[poz+1] > maxq[poz])
ans[i] += (v[i+1] - v[i]) - (abs(minq[poz]) + abs(maxq[poz]));
if(poz != q && minq[poz+1] < minq[poz])
ans[i+1] += (v[i+1] - v[i]) - (abs(minq[poz]) + abs(maxq[poz]));
}
ans[1] += abs(minq[q]);
ans[n] += abs(maxq[q]);
for(int i = 1; i <= n; i++)
cout << ans[i] << '\n';
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
516 KB |
Output is correct |
| 4 |
Correct |
1 ms |
348 KB |
Output is correct |
| 5 |
Correct |
1 ms |
348 KB |
Output is correct |
| 6 |
Correct |
1 ms |
348 KB |
Output is correct |
| 7 |
Correct |
2 ms |
508 KB |
Output is correct |
| 8 |
Correct |
1 ms |
348 KB |
Output is correct |
| 9 |
Correct |
1 ms |
348 KB |
Output is correct |
| 10 |
Correct |
1 ms |
348 KB |
Output is correct |
| 11 |
Correct |
1 ms |
348 KB |
Output is correct |
| 12 |
Correct |
1 ms |
348 KB |
Output is correct |
| 13 |
Correct |
0 ms |
348 KB |
Output is correct |
| 14 |
Correct |
1 ms |
348 KB |
Output is correct |
| 15 |
Correct |
1 ms |
348 KB |
Output is correct |
| 16 |
Correct |
1 ms |
348 KB |
Output is correct |
| 17 |
Correct |
1 ms |
348 KB |
Output is correct |
| 18 |
Correct |
0 ms |
348 KB |
Output is correct |
| 19 |
Correct |
1 ms |
464 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
516 KB |
Output is correct |
| 4 |
Correct |
1 ms |
348 KB |
Output is correct |
| 5 |
Correct |
1 ms |
348 KB |
Output is correct |
| 6 |
Correct |
1 ms |
348 KB |
Output is correct |
| 7 |
Correct |
2 ms |
508 KB |
Output is correct |
| 8 |
Correct |
1 ms |
348 KB |
Output is correct |
| 9 |
Correct |
1 ms |
348 KB |
Output is correct |
| 10 |
Correct |
1 ms |
348 KB |
Output is correct |
| 11 |
Correct |
1 ms |
348 KB |
Output is correct |
| 12 |
Correct |
1 ms |
348 KB |
Output is correct |
| 13 |
Correct |
0 ms |
348 KB |
Output is correct |
| 14 |
Correct |
1 ms |
348 KB |
Output is correct |
| 15 |
Correct |
1 ms |
348 KB |
Output is correct |
| 16 |
Correct |
1 ms |
348 KB |
Output is correct |
| 17 |
Correct |
1 ms |
348 KB |
Output is correct |
| 18 |
Correct |
0 ms |
348 KB |
Output is correct |
| 19 |
Correct |
1 ms |
464 KB |
Output is correct |
| 20 |
Correct |
29 ms |
5488 KB |
Output is correct |
| 21 |
Correct |
18 ms |
5468 KB |
Output is correct |
| 22 |
Correct |
16 ms |
5244 KB |
Output is correct |
| 23 |
Correct |
31 ms |
5212 KB |
Output is correct |
| 24 |
Correct |
21 ms |
5576 KB |
Output is correct |
| 25 |
Correct |
115 ms |
11836 KB |
Output is correct |
| 26 |
Correct |
77 ms |
11864 KB |
Output is correct |
| 27 |
Correct |
83 ms |
11600 KB |
Output is correct |
| 28 |
Correct |
79 ms |
11608 KB |
Output is correct |
| 29 |
Correct |
83 ms |
11088 KB |
Output is correct |
| 30 |
Correct |
64 ms |
10584 KB |
Output is correct |
| 31 |
Correct |
73 ms |
10076 KB |
Output is correct |
| 32 |
Correct |
43 ms |
10260 KB |
Output is correct |
| 33 |
Correct |
7 ms |
1628 KB |
Output is correct |
| 34 |
Correct |
81 ms |
12328 KB |
Output is correct |
| 35 |
Correct |
80 ms |
11600 KB |
Output is correct |
| 36 |
Correct |
75 ms |
11856 KB |
Output is correct |
| 37 |
Correct |
80 ms |
11612 KB |
Output is correct |
| 38 |
Correct |
77 ms |
11484 KB |
Output is correct |
| 39 |
Correct |
69 ms |
11672 KB |
Output is correct |
| 40 |
Correct |
50 ms |
11608 KB |
Output is correct |
| 41 |
Correct |
18 ms |
6224 KB |
Output is correct |
| 42 |
Correct |
41 ms |
10072 KB |
Output is correct |
| 43 |
Correct |
53 ms |
13392 KB |
Output is correct |
| 44 |
Correct |
24 ms |
6080 KB |
Output is correct |
| 45 |
Correct |
90 ms |
11532 KB |
Output is correct |
| 46 |
Correct |
58 ms |
13528 KB |
Output is correct |
| 47 |
Correct |
58 ms |
13664 KB |
Output is correct |
| 48 |
Correct |
66 ms |
13896 KB |
Output is correct |
