This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
double calc_r(array<double, 2> a, double bx) {
return (a[0] - bx) * (a[0] - bx) / (4 * a[1]);
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
vector<double> ans(n);
stack<array<double, 2>> s;
for(int i = 0; i < n; i++) {
double x, r;
cin >> x >> r;
double mx_r = r;
while(!s.empty()) {
array<double, 2> last = s.top();
double ro_last_r = calc_r(last, x);
mx_r = min(mx_r, ro_last_r);
if(mx_r >= last[1]) {
s.pop();
continue;
}
else break;
}
s.push({x, mx_r});
ans[i] = mx_r;
}
cout << fixed << setprecision(5);
for(auto it : ans) cout << it << ' ';
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |