oj.uz

Submission #485121

# Submission time Handle Problem Language Result Execution time Memory
485121 2021-11-06T08:40:32 Z dz001 Balloons (CEOI11_bal) C++11
100 / 100
 216 ms 6624 KB 
#include <bits/stdc++.h>
using namespace std;

#define sqr(x) (x)*(x)

const double eps=1e-3;
const int N=2e5+10;
stack<int> st;
double ans[N],x[N],R[N];
int n;

signed main()
{
    ios::sync_with_stdio(NULL);
    cin.tie(nullptr);
    cout.precision(3);
    cout<<fixed;

    cin>>n;
    for(int i=0;i<n;++i)cin>>x[i]>>R[i],ans[i]=R[i];
    
    st.push(0);
    for(int i=1;i<n;++i){
        while(!st.empty()){
            ans[i]=min(ans[i],sqr(x[i]-x[st.top()])/(4.*ans[st.top()]));
            if(ans[i]-ans[st.top()]>=eps)st.pop();
            else break;
        }
        st.push(i);
    }

    for(int i=0;i<n;++i)cout<<ans[i]<<'\n';
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 972 KB 20000 numbers

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 1940 KB 50000 numbers
2 Correct 47 ms 1888 KB 49912 numbers

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 3456 KB 100000 numbers

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 4008 KB 115362 numbers
2 Correct 109 ms 4104 KB 119971 numbers

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 175 ms 5320 KB 154271 numbers
2 Correct 182 ms 6580 KB 200000 numbers

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 201 ms 6624 KB 200000 numbers
2 Correct 216 ms 6596 KB 199945 numbers