#include <bits/stdc++.h>
#define vi vector<int>
#define ve vector
#define ll long long
#define vf vector<float>
#define vll vector<pair<ll,ll>>
#define ii pair<int,int>
#define vvi vector<vi>
#define vii vector<ii>
#define gii greater<ii>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define INF 1e16
#define eps 1e-7
#define eps1 1e-25
#define optimise ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define MAX_A 1e5+5
#define V 450
using namespace std;
const int MOD = 1e9+7;
const int nax = 2e5+5;
ve<pair<long double,long double>> s;
long double r[nax];
int main(){
optimise;
int n;
cin >> n;
for (int i = 0; i < n; ++i)
{
long double x,mr;
cin >> x >> mr;
s.pb({x,mr});
}
stack<int> st;
for (int i = 0; i < n; ++i)
{
long double mx = s[i].se;
while (!st.empty())
{
pair<long double,long double> a = s[st.top()];
long double b = (long double)((s[i].fi-a.fi)*(s[i].fi-a.fi))/(long double) (4*r[st.top()]);
mx = min(b,mx);
if(mx >= r[st.top()]){
st.pop();
} else {
break;
}
}
st.push(i);
r[i] = mx;
cout <<fixed << setprecision(3) << mx << endl;
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
204 KB |
10 numbers |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
332 KB |
2 numbers |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
332 KB |
505 numbers |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
460 KB |
2000 numbers |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
46 ms |
1500 KB |
20000 numbers |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
112 ms |
3124 KB |
50000 numbers |
2 |
Correct |
109 ms |
4060 KB |
49912 numbers |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
228 ms |
6004 KB |
100000 numbers |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
290 ms |
6864 KB |
115362 numbers |
2 |
Correct |
254 ms |
9120 KB |
119971 numbers |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
359 ms |
9052 KB |
154271 numbers |
2 |
Correct |
426 ms |
14912 KB |
200000 numbers |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
437 ms |
11316 KB |
200000 numbers |
2 |
Correct |
420 ms |
14852 KB |
199945 numbers |