#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n, i, cur = 0;
cin >> n;
vector<int> h(n), ans(n);
for (i = 0; i < n; i++) cin >> h[i];
vector<int> hull = {0};
for (i = 1; i < n; i++) {
if (h[i] > h[hull.back()]) hull.push_back(i);
}
for (i = 0; i < n; i++) {
while (cur < hull.size() - 1 and hull[cur] < i and h[hull[cur]] + sqrt(i - hull[cur]) < h[hull[cur + 1]] + sqrt(i - hull[cur + 1])) cur++;
ans[i] = max(ans[i], (int) ceil(h[hull[cur]] + sqrt(i - hull[cur])));
}
reverse(h.begin(), h.end());
reverse(ans.begin(), ans.end());
hull = {0};
for (i = 1; i < n; i++) {
if (h[i] > h[hull.back()]) hull.push_back(i);
}
cur = 0;
for (i = 0; i < n; i++) {
while (cur < hull.size() - 1 and hull[cur] < i and h[hull[cur]] + sqrt(i - hull[cur]) < h[hull[cur + 1]] + sqrt(i - hull[cur + 1])) cur++;
ans[i] = max(ans[i], (int) ceil(h[hull[cur]] + sqrt(i - hull[cur])));
}
reverse(ans.begin(), ans.end());
reverse(h.begin(), h.end());
for (i = 0; i < n; i++) cout << max(0, ans[i] - h[i]) << endl;
return 0;
}
Compilation message
pio.cpp: In function 'int main()':
pio.cpp:18:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
18 | while (cur < hull.size() - 1 and hull[cur] < i and h[hull[cur]] + sqrt(i - hull[cur]) < h[hull[cur + 1]] + sqrt(i - hull[cur + 1])) cur++;
| ~~~~^~~~~~~~~~~~~~~~~
pio.cpp:30:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
30 | while (cur < hull.size() - 1 and hull[cur] < i and h[hull[cur]] + sqrt(i - hull[cur]) < h[hull[cur + 1]] + sqrt(i - hull[cur + 1])) cur++;
| ~~~~^~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
43 ms |
1540 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
64 ms |
1664 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
77 ms |
1732 KB |
Output is correct |
2 |
Correct |
74 ms |
1116 KB |
Output is correct |
3 |
Incorrect |
77 ms |
1836 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
118 ms |
2456 KB |
Output is correct |
2 |
Correct |
118 ms |
2388 KB |
Output is correct |
3 |
Incorrect |
118 ms |
2572 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
274 ms |
5460 KB |
Output is correct |
2 |
Correct |
269 ms |
5064 KB |
Output is correct |
3 |
Incorrect |
280 ms |
5164 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
422 ms |
10068 KB |
Output is correct |
2 |
Correct |
430 ms |
8056 KB |
Output is correct |
3 |
Incorrect |
437 ms |
8744 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
604 ms |
14048 KB |
Output is correct |
2 |
Correct |
586 ms |
11236 KB |
Output is correct |
3 |
Incorrect |
595 ms |
12160 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
620 ms |
11556 KB |
Output is correct |
2 |
Correct |
601 ms |
11348 KB |
Output is correct |
3 |
Incorrect |
605 ms |
12496 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |