#include<bits/stdc++.h>
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("trapv")
#define st first
#define nd second
#define pb push_back
#define pp pop_back
#define eb emplace_back
#define mp(a, b) make_pair(a, b)
#define all(x) (x).begin(), (x).end()
#define rev(x) reverse(all(x))
#define sor(x) sort(all(x))
#define sz(x) (int)(x).size()
#define rsz(x) resize(x)
using namespace std;
///~~~~~~~~~~~~~~~~~~~~~~~~~~
template <typename H, typename T>
ostream& operator<<(ostream& os, pair<H, T> m){
return os <<"("<< m.st<<", "<<m.nd<<")";
}
template <typename H>
ostream& operator<<(ostream& os, vector<H> V){
os<<"{";
for(int i=0; i<V.size(); i++){
if(i)os<<" ";
os<<V[i];
}
os<<"}";
return os;
}
void debug(){cerr<<"\n";}
template <typename H, typename... T>
void debug(H h, T... t) {cerr<<h; if (sizeof...(t)) cerr << ", "; debug(t...);}
#define deb(x...) cerr<<#x<<" = ";debug(x);
///~~~~~~~~~~~~~~~~~~~~~~~~~
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<pii > vii;
typedef vector<ll> vl;
typedef vector<pll> vll;
typedef string str;
#define BOOST ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
const int N=1<<18, mod=1e9+7, INF=(1<<30);
const ld EPS=1e-9;
struct line{
ld a, b;
line(): a(0), b(INF){}
line(ld a, ld b): a(a), b(b){}
ld isect(line L){
return (b-L.b)/(L.a-a);
}
ld val(ld x){return a*x+b;}
};
int L[N+N], R[N+N];
line lin[N+N];
void insert(int v, line li2, int l1, int r1){
//deb(l, r, li.a, li.b);
//deb(v, L[v], l1, R[v], r1, li2.a, li2.b);
assert(l1>=L[v] && r1<=R[v]);
if(li2.val(L[v])>lin[v].val(L[v]) && li2.val(R[v])>lin[v].val(R[v]))return;
//deb("a");
if(l1==L[v] && r1==R[v] && li2.val(L[v])<lin[v].val(L[v]) && li2.val(R[v])<lin[v].val(R[v])){
//deb(v, li2.a, li2.b);
lin[v]=li2;
return;
}
assert((v>=N)==(L[v]==R[v]));
if(v>=N)return;
if(l1<=R[v+v])insert(v+v,li2, l1, min(r1, R[v+v]));
//deb("a");
if(r1>=L[v+v+1]){
insert(v+v+1, li2, max(l1, L[v+v+1]), r1);
}
return;
}
ld val(int v, int x){
//deb(v, x, L[v], R[v], lin[v].a, lin[v].b);
ld ans=lin[v].val(x);
if(v<N && x<=R[v+v])ans=min(ans, val(v+v, x));
else{
if(v<N)ans=min(ans, val(v+v+1, x));
}
return ans;
}
int main(){
BOOST;
int n;
cin>>n;
vii quer;
for(int i=0; i<n; i++){
int x, rr;
cin>>x>>rr;
quer.pb(mp(x, rr));
L[N+i]=x;
}
for(int i=n; i<N; i++)L[N+i]=INF+i;
sort(L+N, L+N+N);
for(int i=N+N-1;i>0; i--){
if(i>=N)R[i]=L[i];
else R[i]=R[i+i+1], L[i]=L[i+i];
}
for(int i=0; i<n; i++){
ld r2=val(1, quer[i].st);
r2=min(r2*r2, ld(quer[i].nd));
cout<<fixed<<setprecision(3)<<r2<<"\n";
if(r2>EPS){
insert(1, line(-1/ld(2*sqrt(r2)), quer[i].st/ld(2*sqrt(r2))), L[N], quer[i].st);
insert(1, line(1/ld(2*sqrt(r2)), -quer[i].st/ld(2*sqrt(r2))), quer[i].st, L[N+N-1]);
}
}
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
17 ms |
20820 KB |
10 numbers |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
16 ms |
20720 KB |
2 numbers |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
18 ms |
20848 KB |
505 numbers |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
22 ms |
20948 KB |
2000 numbers |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
57 ms |
21264 KB |
20000 numbers |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
115 ms |
21700 KB |
50000 numbers |
| 2 |
Correct |
145 ms |
21660 KB |
49912 numbers |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
209 ms |
22576 KB |
100000 numbers |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
248 ms |
22832 KB |
115362 numbers |
| 2 |
Correct |
217 ms |
22584 KB |
119971 numbers |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
317 ms |
23524 KB |
154271 numbers |
| 2 |
Correct |
353 ms |
23780 KB |
200000 numbers |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
388 ms |
24108 KB |
200000 numbers |
| 2 |
Correct |
375 ms |
23748 KB |
199945 numbers |
