oj.uz

Submission #415307

# Submission time Handle Problem Language Result Execution time Memory
415307 2021-05-31T21:07:27 Z ba_hah Balloons (CEOI11_bal) C++14
100 / 100
 630 ms 9104 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
#define FAST   ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define int long long 
 
 
 
void init(){

 
}

const int N = (int) 2e5 + 8;
const int mod = (int)1e9+7;
double x[N] , r[N];
int n ; 
stack<pair<double,double>> st;
int inflate( double xx , double rr ) {
     // for touching circle 
    //  max radius will be r = ( x1 - x) ^2 / 4*r1
    //  also observation 
    //  x2 > x1  for any x > x2  we have (x1-x)^2 > (x2-x)^2 
    //  along with r1<=r2 then only r2 will require for calculation of answer for x 
    
    
    while( !st.empty() ){
        double x1 = st.top().first , r1 = st.top().second;
         rr  = min ( rr , (double)(x1-xx)*1.0*(x1-xx)/(4.0*r1));
        if( rr  >= r1 ) {
            st.pop();
        }else break;
    }
    st.push({xx,rr});
    cout<<fixed<<rr<<endl;
    return 0;
}
void solve(){
    cin>>n;
    for( int i = 0 ; i< n ;i ++) {
        cin>>x[i]>>r[i];
    }

    for( int i =0  ;i < n ; i ++) {
        inflate( x[i] , r[i] ) ;
    }
    

}

int32_t main(){

    FAST;
    init();
    int t=1;
    /* cin>>t; */ 
 
    while(t--){
        solve();
    }
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB 10 numbers

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB 2 numbers

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 332 KB 505 numbers

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 332 KB 2000 numbers

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 784 KB 20000 numbers

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 188 ms 1860 KB 50000 numbers
2 Correct 145 ms 2524 KB 49912 numbers

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 327 ms 3196 KB 100000 numbers

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 353 ms 3604 KB 115362 numbers
2 Correct 352 ms 5636 KB 119971 numbers

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 555 ms 4720 KB 154271 numbers
2 Correct 576 ms 9104 KB 200000 numbers

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 630 ms 5560 KB 200000 numbers
2 Correct 622 ms 9104 KB 199945 numbers