| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1097537 |
2024-10-07T14:42:07 Z |
Alihan_8 |
Snowball (JOI21_ho_t2) |
C++17 |
|
2500 ms |
7252 KB |
#include <bits/stdc++.h>
using namespace std;
#define ar array
using i64 = long long;
const i64 inf = 1e18;
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n, q; cin >> n >> q;
vector <i64> X(n + 2);
for ( int i = 1; i <= n; i++ ){
cin >> X[i];
}
X[0] = -inf, X[n + 1] = inf;
vector <i64> Q(q);
for ( auto &x: Q ) cin >> x;
vector <ar<i64,2>> f(q);
i64 cnt = 0;
for ( int i = 0; i < q; i++ ){
if ( i > 0 ) f[i] = f[i - 1];
else f[i] = {inf, -inf};
cnt += Q[i];
f[i][0] = min(f[i][0], cnt);
f[i][1] = max(f[i][1], cnt);
}
vector <i64> ans(n + 1);
for ( int i = 1; i <= n; i++ ){
i64 l = X[i], r = X[i];
for ( int j = 0; j < q; j++ ){
l = min(l, max(f[j][0] + X[i], f[j][1] + X[i - 1]));
r = max(r, min(f[j][1] + X[i], f[j][0] + X[i + 1]));
}
l = max(l, X[i - 1]), r = min(r, X[i + 1]);
ans[i] = r - l;
}
for ( int i = 1; i <= n; i++ ){
cout << ans[i] << endl;
}
cout << '\n';
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
468 KB |
Output is correct |
| 3 |
Correct |
2 ms |
476 KB |
Output is correct |
| 4 |
Correct |
8 ms |
348 KB |
Output is correct |
| 5 |
Correct |
8 ms |
576 KB |
Output is correct |
| 6 |
Correct |
9 ms |
348 KB |
Output is correct |
| 7 |
Correct |
8 ms |
348 KB |
Output is correct |
| 8 |
Correct |
8 ms |
568 KB |
Output is correct |
| 9 |
Correct |
8 ms |
348 KB |
Output is correct |
| 10 |
Correct |
8 ms |
348 KB |
Output is correct |
| 11 |
Correct |
8 ms |
348 KB |
Output is correct |
| 12 |
Correct |
0 ms |
456 KB |
Output is correct |
| 13 |
Correct |
0 ms |
348 KB |
Output is correct |
| 14 |
Correct |
1 ms |
348 KB |
Output is correct |
| 15 |
Correct |
8 ms |
348 KB |
Output is correct |
| 16 |
Correct |
8 ms |
584 KB |
Output is correct |
| 17 |
Correct |
8 ms |
348 KB |
Output is correct |
| 18 |
Correct |
1 ms |
344 KB |
Output is correct |
| 19 |
Correct |
8 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
468 KB |
Output is correct |
| 3 |
Correct |
2 ms |
476 KB |
Output is correct |
| 4 |
Correct |
8 ms |
348 KB |
Output is correct |
| 5 |
Correct |
8 ms |
576 KB |
Output is correct |
| 6 |
Correct |
9 ms |
348 KB |
Output is correct |
| 7 |
Correct |
8 ms |
348 KB |
Output is correct |
| 8 |
Correct |
8 ms |
568 KB |
Output is correct |
| 9 |
Correct |
8 ms |
348 KB |
Output is correct |
| 10 |
Correct |
8 ms |
348 KB |
Output is correct |
| 11 |
Correct |
8 ms |
348 KB |
Output is correct |
| 12 |
Correct |
0 ms |
456 KB |
Output is correct |
| 13 |
Correct |
0 ms |
348 KB |
Output is correct |
| 14 |
Correct |
1 ms |
348 KB |
Output is correct |
| 15 |
Correct |
8 ms |
348 KB |
Output is correct |
| 16 |
Correct |
8 ms |
584 KB |
Output is correct |
| 17 |
Correct |
8 ms |
348 KB |
Output is correct |
| 18 |
Correct |
1 ms |
344 KB |
Output is correct |
| 19 |
Correct |
8 ms |
348 KB |
Output is correct |
| 20 |
Correct |
28 ms |
7252 KB |
Output is correct |
| 21 |
Correct |
25 ms |
7004 KB |
Output is correct |
| 22 |
Correct |
78 ms |
6896 KB |
Output is correct |
| 23 |
Correct |
559 ms |
6836 KB |
Output is correct |
| 24 |
Execution timed out |
2573 ms |
7000 KB |
Time limit exceeded |
| 25 |
Halted |
0 ms |
0 KB |
- |
