#include<bits/stdc++.h>
#include<chrono>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
using namespace chrono;
#define ll long long
#define vl vector<long long>
#define endl '\n'
const int MOD = 1e9 + 7;
void inputv(vl &v) {for(int i = 0; i < (ll)v.size(); i++) cin>>v[i];}
void printv(vl v) {for(auto i : v) cout<<i<<" ";cout<<endl;}
#define ONLINE_JUDGE
#ifndef ONLINE_JUDGE
#include "template.cpp"
#else
#define debug(...)
#define debugArr(...)
#endif
#define int long long
#define ld long double
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ost;
int n;
vector<int>arr;
vector<int>maxRad;
vector<ld>ans;
int check(int x1, int x2, ld rad1, ld rad2) {
ld temp = rad1/rad2;
int high = 1e16;
int ans = -1;
int low = x2+1;
while(low<=high) {
int mid = (low+high)/2;
ld t = (1 + (((ld)x2 - x1)/((ld)mid - x2)));
t *= t;
if(t>temp) {
ans = mid;
low = mid+1;
}
else high = mid-1;
}
return ans;
}
signed main() {
#ifndef ONLINE_JUDGE
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
freopen("error.txt","w",stderr);
#endif
ios::sync_with_stdio(false); cin.tie(NULL);
int ts = 1;
#ifndef ONLINE_JUDGE
auto start = duration_cast<milliseconds>(system_clock::now().time_since_epoch()).count();
#endif
while(ts--) {
cin>>n;
arr = maxRad = vector<int>(n);
for(int i = 0; i < n; i++) cin>>arr[i]>>maxRad[i];
stack<pair<int,int>>st;
ans = vector<ld>(n);
ans[0] = maxRad[0];
st.push({0,-1});
for(int i = 1; i < n; i++) {
while(st.top().second != -1 && st.top().second < arr[i]) st.pop();
int prev = st.top().first;
ld rad = min((ld)maxRad[i], ((ld)arr[i]-(ld)arr[prev])*((ld)arr[i]-(ld)arr[prev])/((ld)4.0*ans[prev]));
ans[i] = rad;
while(!st.empty() && ans[st.top().first] <= rad) st.pop();
if(!st.empty()) {
prev= st.top().first;
int temp = check(arr[prev], arr[i], ans[prev], ans[i]);
if(temp!=-1) st.push({i,temp});
}
else {
st.push({i, -1});
}
}
cout<<fixed<<setprecision(3);
for(int i = 0; i < n; i++) cout<<ans[i]<<endl;
}
#ifndef ONLINE_JUDGE
auto stop = duration_cast<milliseconds>(system_clock::now().time_since_epoch()).count();
cerr << "Took " << stop - start << "ms" << endl;
#endif
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
336 KB |
10 numbers |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
336 KB |
2 numbers |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
2 ms |
336 KB |
53rd numbers differ - expected: '213.0000000000', found: '235.0000000000', error = '22.0000000000' |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
336 KB |
2000 numbers |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
19 ms |
1104 KB |
4165th numbers differ - expected: '463.3780000000', found: '468.0000000000', error = '4.6220000000' |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
52 ms |
2632 KB |
26317th numbers differ - expected: '1.1140000000', found: '16.4820000000', error = '15.3680000000' |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
95 ms |
4460 KB |
7458th numbers differ - expected: '1.9040000000', found: '8.0000000000', error = '6.0960000000' |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
126 ms |
5020 KB |
4889th numbers differ - expected: '0.7110000000', found: '8.0000000000', error = '7.2890000000' |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
165 ms |
6740 KB |
40692nd numbers differ - expected: '5543.6460000000', found: '5559.0000000000', error = '15.3540000000' |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
206 ms |
8292 KB |
4263rd numbers differ - expected: '0.6980000000', found: '4.0000000000', error = '3.3020000000' |
2 |
Halted |
0 ms |
0 KB |
- |