| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1095723 |
2024-10-03T03:41:34 Z |
zaza |
Snowball (JOI21_ho_t2) |
C++14 |
|
1 ms |
600 KB |
#include <bits/stdc++.h>
using namespace std;
long long a[200005], w[200005];
long long mini[200005], maxi[200005];
main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n, q;
cin >> n >> q;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
}
w[0] = 0;
mini[0] = 2e18;
maxi[0] = -2e18;
for (int i = 1; i <= q; ++i) {
cin >> w[i];
w[i] += w[i - 1];
mini[i] = min(mini[i - 1], w[i]);
maxi[i] = max(maxi[i - 1], w[i]);
}
for (int i = 1; i <= n; ++i) {
long long L, R;
if (i == 1) {
L = min(a[i], a[i] + mini[q]);
} else {
int l = 1, r = q;
while (l <= r) {
int mid = (l + r) / 2;
if (min(a[i], a[i] + mini[mid]) <= max(a[i - 1], a[i - 1] + maxi[mid])) {
r = mid - 1;
} else {
l = mid + 1;
}
}
if (l > q) {
L = min(a[i], a[i] + mini[q]);
} else {
L = max(a[i - 1], a[i - 1] + maxi[l]);
if (l > 1) {
L = min(L, min(a[i], a[i] + mini[l - 1]));
}
}
//cout << "i = " << i << " i_l = " << l << '\n';
}
if (i == n) {
R = max(a[i], a[i] + maxi[q]);
} else {
int l = 1, r = q;
while (l <= r) {
int mid = (l + r) / 2;
if (max(a[i], a[i] + maxi[mid]) >= min(a[i + 1], a[i + 1] + mini[mid])) {
r = mid - 1;
} else {
l = mid + 1;
}
}
if (l > q) {
R = max(a[i], a[i] + maxi[q]);
} else {
R = min(a[i + 1], a[i + 1] + mini[l]);
if (l > 1) {
R = max(R, max(a[i], a[i] + maxi[l - 1]));
}
}
//cout << "i = " << i << " i_r = " << l << '\n';
}
// cout <<"L = " << L<<" R = "<<R<<'\n';
cout << R - L << '\n';
}
}
Compilation message
Main.cpp:9:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
9 | main() {
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
344 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 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 |
1 ms |
348 KB |
Output is correct |
| 8 |
Correct |
1 ms |
600 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 |
344 KB |
Output is correct |
| 12 |
Correct |
0 ms |
348 KB |
Output is correct |
| 13 |
Correct |
1 ms |
348 KB |
Output is correct |
| 14 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 15 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
344 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 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 |
1 ms |
348 KB |
Output is correct |
| 8 |
Correct |
1 ms |
600 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 |
344 KB |
Output is correct |
| 12 |
Correct |
0 ms |
348 KB |
Output is correct |
| 13 |
Correct |
1 ms |
348 KB |
Output is correct |
| 14 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 15 |
Halted |
0 ms |
0 KB |
- |
