#include <cstdio>
#include <cstring>
#include <cassert>
#include <string>
#include <deque>
#include <vector>
#include <map>
#include <queue>
#include <algorithm>
#include <iostream>
#include <utility>
using namespace std;
using ll = long long;
using ld = long double;
#define ShinLena cin.tie(nullptr)->sync_with_stdio(false)
#define N 200005
#define ALL(x) x.begin(), x.end()
ll n, q, x[N], w[N], hi[N], lo[N];
int main()
{
ShinLena;
cin >> n >> q;
for (int i = 1; i <= n; ++i) cin >> x[i];
for (int i = 1; i <= q; ++i) cin >> w[i], w[i] += w[i-1], hi[i] = max(hi[i-1], w[i]), lo[i] = min(lo[i-1], w[i]);
for (int i = 1; i <= n; ++i)
{
ll lft= 1e14, rgt=-1e14;
{
int l = 1, r = q;
while (l <= r)
{
int y = (l+r)/2;
if (hi[y] + x[i] > lo[y] + x[i+1]) r = y - 1, rgt = max(rgt, lo[y] + x[i+1]);
else
{
l = y + 1, rgt = max(rgt, x[i] + hi[y]);
//if (y < q) rgt = max(rgt, lo[y+1] + x[i+1]);
}
}
if (i == n) rgt = x[i] + hi[q];
l = 1, r = q;
while (l <= r)
{
int y = (l+r)/2;
if (lo[y] + x[i] < hi[y] + x[i-1]) r = y - 1, lft = min(lft, hi[y] + x[i-1]);
else
{
l = y + 1, lft = min(lft, x[i] + lo[y]);
//if (y < q) lft = min(lft, hi[y+1] + x[i-1]);
}
}
if (i == 1) lft = x[i] + lo[q];
}
cout << rgt - lft << '\n';
}
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
2396 KB |
Output is correct |
2 |
Correct |
1 ms |
2396 KB |
Output is correct |
3 |
Correct |
1 ms |
2396 KB |
Output is correct |
4 |
Correct |
1 ms |
2396 KB |
Output is correct |
5 |
Correct |
1 ms |
2396 KB |
Output is correct |
6 |
Correct |
1 ms |
2396 KB |
Output is correct |
7 |
Correct |
1 ms |
2396 KB |
Output is correct |
8 |
Correct |
2 ms |
2396 KB |
Output is correct |
9 |
Correct |
1 ms |
2396 KB |
Output is correct |
10 |
Correct |
1 ms |
2396 KB |
Output is correct |
11 |
Correct |
1 ms |
2396 KB |
Output is correct |
12 |
Correct |
1 ms |
2396 KB |
Output is correct |
13 |
Correct |
1 ms |
2396 KB |
Output is correct |
14 |
Incorrect |
0 ms |
2396 KB |
Output isn't correct |
15 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
2396 KB |
Output is correct |
2 |
Correct |
1 ms |
2396 KB |
Output is correct |
3 |
Correct |
1 ms |
2396 KB |
Output is correct |
4 |
Correct |
1 ms |
2396 KB |
Output is correct |
5 |
Correct |
1 ms |
2396 KB |
Output is correct |
6 |
Correct |
1 ms |
2396 KB |
Output is correct |
7 |
Correct |
1 ms |
2396 KB |
Output is correct |
8 |
Correct |
2 ms |
2396 KB |
Output is correct |
9 |
Correct |
1 ms |
2396 KB |
Output is correct |
10 |
Correct |
1 ms |
2396 KB |
Output is correct |
11 |
Correct |
1 ms |
2396 KB |
Output is correct |
12 |
Correct |
1 ms |
2396 KB |
Output is correct |
13 |
Correct |
1 ms |
2396 KB |
Output is correct |
14 |
Incorrect |
0 ms |
2396 KB |
Output isn't correct |
15 |
Halted |
0 ms |
0 KB |
- |