#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
using namespace std;
const int MX = 2e5 + 5;
ll x[MX], radius[MX];
ld ans[MX];
int main()
{
int N;
cin >> N;
for (int i = 0; i < N; i++)
cin >> x[i] >> radius[i];
stack<pair<ll, ld>> st;
for (int i = 0; i < N; i++)
{
ld r = radius[i];
while (!st.empty())
{
auto curr = st.top();
r = min(r, ((curr.first - x[i]) * (curr.first - x[i])) / (4 * curr.second));
if (r > curr.second)
st.pop();
else
break;
}
ans[i] = r;
st.push({x[i], r});
}
cout << fixed << setprecision(3);
for (int i = 0; i < N; i++)
cout << ans[i] << "\n";
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
204 KB |
10 numbers |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
204 KB |
2 numbers |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
204 KB |
505 numbers |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
416 KB |
2000 numbers |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
27 ms |
1220 KB |
20000 numbers |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
70 ms |
2908 KB |
50000 numbers |
2 |
Correct |
72 ms |
3384 KB |
49912 numbers |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
147 ms |
4912 KB |
100000 numbers |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
166 ms |
5548 KB |
115362 numbers |
2 |
Correct |
183 ms |
7060 KB |
119971 numbers |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
224 ms |
6996 KB |
154271 numbers |
2 |
Correct |
301 ms |
11332 KB |
200000 numbers |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
301 ms |
8536 KB |
200000 numbers |
2 |
Correct |
286 ms |
11480 KB |
199945 numbers |