#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 2e5+10;
ll n, m, x[N], maxp[N], minp[N];
int main() {
ios::sync_with_stdio(0); cin.tie(0);
cin >> n >> m;
for(int i = 1; i <= n; ++i) {
cin >> x[i];
}
ll p = 0;
for(int i = 1; i <= m; ++i) {
ll offset; cin >> offset;
p += offset;
maxp[i] = max(maxp[i - 1], p);
minp[i] = min(minp[i - 1], p);
}
const ll oo = 1e18;
x[0] = -oo;
x[n+1] = oo;
auto crit_point = [&](ll dist) {
ll l = 0, r = m, ans = m;
while(r >= l) {
ll middle = l + r >> 1;
if(maxp[middle] >= dist + minp[middle]) {
r = middle-1;
ans = middle;
} else {
l = middle+1;
}
}
return ans;
};
auto maximum = [&](ll a, ll b) {
return max(a, b);
};
auto minimum = [&](ll a, ll b) {
return min(a, b);
};
auto f = [&](ll id, ll A, ll B, function<ll(ll, ll)> fun) {
id = max(id, 0LL);
id = min(id, m);
return fun(maxp[id] + A, minp[id] + B);
};
for(int i = 1; i <= n; ++i) {
ll point_lft = crit_point(x[i] - x[i-1]);
ll point_rgh = crit_point(x[i+1] - x[i]);
ll lft = oo, rgh = -oo;
for(int off = -1; off <= 1; ++off) {
lft = min(lft, f(point_lft+off, x[i-1], x[i], maximum));
rgh = max(rgh, f(point_rgh+off, x[i], x[i+1], minimum));
}
cout << rgh - lft << ' ';
}
}
Compilation message
Main.cpp: In lambda function:
Main.cpp:25:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
25 | ll middle = l + r >> 1;
| ~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| 3 |
Correct |
2 ms |
364 KB |
Output is correct |
| 4 |
Correct |
2 ms |
364 KB |
Output is correct |
| 5 |
Correct |
2 ms |
364 KB |
Output is correct |
| 6 |
Correct |
2 ms |
364 KB |
Output is correct |
| 7 |
Correct |
2 ms |
364 KB |
Output is correct |
| 8 |
Correct |
2 ms |
364 KB |
Output is correct |
| 9 |
Correct |
2 ms |
364 KB |
Output is correct |
| 10 |
Correct |
2 ms |
364 KB |
Output is correct |
| 11 |
Correct |
3 ms |
364 KB |
Output is correct |
| 12 |
Correct |
1 ms |
364 KB |
Output is correct |
| 13 |
Correct |
1 ms |
364 KB |
Output is correct |
| 14 |
Correct |
1 ms |
364 KB |
Output is correct |
| 15 |
Correct |
2 ms |
512 KB |
Output is correct |
| 16 |
Correct |
2 ms |
364 KB |
Output is correct |
| 17 |
Correct |
2 ms |
364 KB |
Output is correct |
| 18 |
Correct |
1 ms |
364 KB |
Output is correct |
| 19 |
Correct |
2 ms |
364 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| 3 |
Correct |
2 ms |
364 KB |
Output is correct |
| 4 |
Correct |
2 ms |
364 KB |
Output is correct |
| 5 |
Correct |
2 ms |
364 KB |
Output is correct |
| 6 |
Correct |
2 ms |
364 KB |
Output is correct |
| 7 |
Correct |
2 ms |
364 KB |
Output is correct |
| 8 |
Correct |
2 ms |
364 KB |
Output is correct |
| 9 |
Correct |
2 ms |
364 KB |
Output is correct |
| 10 |
Correct |
2 ms |
364 KB |
Output is correct |
| 11 |
Correct |
3 ms |
364 KB |
Output is correct |
| 12 |
Correct |
1 ms |
364 KB |
Output is correct |
| 13 |
Correct |
1 ms |
364 KB |
Output is correct |
| 14 |
Correct |
1 ms |
364 KB |
Output is correct |
| 15 |
Correct |
2 ms |
512 KB |
Output is correct |
| 16 |
Correct |
2 ms |
364 KB |
Output is correct |
| 17 |
Correct |
2 ms |
364 KB |
Output is correct |
| 18 |
Correct |
1 ms |
364 KB |
Output is correct |
| 19 |
Correct |
2 ms |
364 KB |
Output is correct |
| 20 |
Correct |
31 ms |
3436 KB |
Output is correct |
| 21 |
Correct |
28 ms |
3436 KB |
Output is correct |
| 22 |
Correct |
35 ms |
3436 KB |
Output is correct |
| 23 |
Correct |
26 ms |
3564 KB |
Output is correct |
| 24 |
Correct |
36 ms |
3820 KB |
Output is correct |
| 25 |
Correct |
148 ms |
6636 KB |
Output is correct |
| 26 |
Correct |
146 ms |
6636 KB |
Output is correct |
| 27 |
Correct |
143 ms |
6508 KB |
Output is correct |
| 28 |
Correct |
144 ms |
6380 KB |
Output is correct |
| 29 |
Correct |
141 ms |
6252 KB |
Output is correct |
| 30 |
Correct |
135 ms |
5996 KB |
Output is correct |
| 31 |
Correct |
88 ms |
5484 KB |
Output is correct |
| 32 |
Correct |
82 ms |
5612 KB |
Output is correct |
| 33 |
Correct |
16 ms |
1004 KB |
Output is correct |
| 34 |
Correct |
147 ms |
6636 KB |
Output is correct |
| 35 |
Correct |
150 ms |
6508 KB |
Output is correct |
| 36 |
Correct |
144 ms |
6636 KB |
Output is correct |
| 37 |
Correct |
146 ms |
6508 KB |
Output is correct |
| 38 |
Correct |
152 ms |
6544 KB |
Output is correct |
| 39 |
Correct |
179 ms |
6508 KB |
Output is correct |
| 40 |
Correct |
109 ms |
6380 KB |
Output is correct |
| 41 |
Correct |
34 ms |
3436 KB |
Output is correct |
| 42 |
Correct |
80 ms |
8556 KB |
Output is correct |
| 43 |
Correct |
102 ms |
11936 KB |
Output is correct |
| 44 |
Correct |
35 ms |
6124 KB |
Output is correct |
| 45 |
Correct |
89 ms |
10092 KB |
Output is correct |
| 46 |
Correct |
116 ms |
12012 KB |
Output is correct |
| 47 |
Correct |
107 ms |
12268 KB |
Output is correct |
| 48 |
Correct |
105 ms |
12268 KB |
Output is correct |
