#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int>pii;
int32_t main(){
ios::sync_with_stdio(0);
cin.tie(0);
int n,q;
cin >> n >> q;
int arr[n+5];
arr[0]=-1e18;
arr[n+1]=1e18;
for(int x=1;x<=n;x++){
cin >> arr[x];
}
int wind[q+2];
int left[q+2];
int right[q+2];
left[0]=0;
right[0]=0;
wind[0]=0;
for(int x=1;x<=q;x++){
cin >> wind[x];
wind[x]+=wind[x-1];
left[x]=min(wind[x],left[x-1]);
right[x]=max(wind[x],right[x-1]);
}
wind[q+1]=wind[q];
// for(auto it:wind) cout << it << " ";
// cout << " wind\n";
// for(auto it:left) cout << it << " ";
// cout << " left\n";
// for(auto it:right) cout << it << " ";
// cout << " right\n";
int counter=0;
for(int x=1;x<=n;x++){
int hold=0;
//left
int l=0;
int r=q;
int mid;
int best=0;
while(l<=r){
mid=(l+r)/2;
if(arr[x]+left[mid]>=arr[x-1]+right[mid]){
best=mid;
l=mid+1;
}
else{
r=mid-1;
}
}
// cout << best << " best\n";
hold+=(-left[best]);
int hold2=wind[best+1]-wind[best];
if(hold2<0){
hold+=min(-hold2,(arr[x]+left[best]-arr[x-1]-right[best]));
}
// cout << hold << " hold\n";
//right
l=0;
r=q;
best=0;
while(l<=r){
mid=(l+r)/2;
if(arr[x]+right[mid]<=arr[x+1]+left[mid]){
best=mid;
l=mid+1;
}
else{
r=mid-1;
}
}
// cout << best << " best2\n";
hold+=right[best];
hold2=wind[best+1]-wind[best];
if(hold2>0){
// cout << hold2 << " " << (arr[x+1]+left[best]-arr[x]-right[best]) << " *\n";
hold+=min(hold2,(arr[x+1]+left[best]-arr[x]-right[best]));
}
// cout << hold << " hold\n";
counter+=hold;
// cout << hold << " " << x << "\n";
cout << hold << "\n";
}
// cout << counter;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
2 ms |
340 KB |
Output is correct |
| 5 |
Correct |
2 ms |
340 KB |
Output is correct |
| 6 |
Correct |
1 ms |
468 KB |
Output is correct |
| 7 |
Correct |
1 ms |
340 KB |
Output is correct |
| 8 |
Correct |
2 ms |
360 KB |
Output is correct |
| 9 |
Correct |
1 ms |
340 KB |
Output is correct |
| 10 |
Correct |
1 ms |
364 KB |
Output is correct |
| 11 |
Correct |
1 ms |
340 KB |
Output is correct |
| 12 |
Correct |
1 ms |
320 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 |
340 KB |
Output is correct |
| 16 |
Correct |
1 ms |
340 KB |
Output is correct |
| 17 |
Correct |
1 ms |
340 KB |
Output is correct |
| 18 |
Correct |
1 ms |
248 KB |
Output is correct |
| 19 |
Correct |
1 ms |
340 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
2 ms |
340 KB |
Output is correct |
| 5 |
Correct |
2 ms |
340 KB |
Output is correct |
| 6 |
Correct |
1 ms |
468 KB |
Output is correct |
| 7 |
Correct |
1 ms |
340 KB |
Output is correct |
| 8 |
Correct |
2 ms |
360 KB |
Output is correct |
| 9 |
Correct |
1 ms |
340 KB |
Output is correct |
| 10 |
Correct |
1 ms |
364 KB |
Output is correct |
| 11 |
Correct |
1 ms |
340 KB |
Output is correct |
| 12 |
Correct |
1 ms |
320 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 |
340 KB |
Output is correct |
| 16 |
Correct |
1 ms |
340 KB |
Output is correct |
| 17 |
Correct |
1 ms |
340 KB |
Output is correct |
| 18 |
Correct |
1 ms |
248 KB |
Output is correct |
| 19 |
Correct |
1 ms |
340 KB |
Output is correct |
| 20 |
Correct |
25 ms |
7116 KB |
Output is correct |
| 21 |
Correct |
27 ms |
6912 KB |
Output is correct |
| 22 |
Correct |
25 ms |
6644 KB |
Output is correct |
| 23 |
Correct |
22 ms |
6528 KB |
Output is correct |
| 24 |
Correct |
31 ms |
6924 KB |
Output is correct |
| 25 |
Correct |
140 ms |
11844 KB |
Output is correct |
| 26 |
Correct |
135 ms |
11804 KB |
Output is correct |
| 27 |
Correct |
118 ms |
11464 KB |
Output is correct |
| 28 |
Correct |
118 ms |
11528 KB |
Output is correct |
| 29 |
Correct |
146 ms |
11112 KB |
Output is correct |
| 30 |
Correct |
108 ms |
10516 KB |
Output is correct |
| 31 |
Correct |
70 ms |
9932 KB |
Output is correct |
| 32 |
Correct |
61 ms |
10048 KB |
Output is correct |
| 33 |
Correct |
10 ms |
1488 KB |
Output is correct |
| 34 |
Correct |
129 ms |
12196 KB |
Output is correct |
| 35 |
Correct |
128 ms |
11580 KB |
Output is correct |
| 36 |
Correct |
130 ms |
11848 KB |
Output is correct |
| 37 |
Correct |
121 ms |
11572 KB |
Output is correct |
| 38 |
Correct |
115 ms |
11472 KB |
Output is correct |
| 39 |
Correct |
110 ms |
11668 KB |
Output is correct |
| 40 |
Correct |
74 ms |
11560 KB |
Output is correct |
| 41 |
Correct |
31 ms |
7680 KB |
Output is correct |
| 42 |
Correct |
74 ms |
10052 KB |
Output is correct |
| 43 |
Correct |
102 ms |
13380 KB |
Output is correct |
| 44 |
Correct |
36 ms |
7492 KB |
Output is correct |
| 45 |
Correct |
82 ms |
11636 KB |
Output is correct |
| 46 |
Correct |
81 ms |
13508 KB |
Output is correct |
| 47 |
Correct |
79 ms |
13720 KB |
Output is correct |
| 48 |
Correct |
84 ms |
13772 KB |
Output is correct |
