oj.uz

Submission #1117785

# Submission time Handle Problem Language Result Execution time Memory
1117785 2024-11-24T08:22:25 Z Icelast Balloons (CEOI11_bal) C++17
100 / 100
 136 ms 14932 KB 
#include <iostream>
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn = 2*1e5+5, INF = 4e18+9;
struct balloon{
    long double x, r;
};
void solve(){
    int n;
    cin >> n;
    vector<balloon> a(n+1);
    for(int i = 1; i <= n; i++){
        cin >> a[i].x >> a[i].r;
    }
    cout << fixed << setprecision(3);
    auto sqr = [&](long double x) -> long double{
        return x*x;
    };
    stack<int> st;
    vector<long double> ans(n+1);
    for(int i = 1; i <= n; i++){
        long double r = a[i].r;
        while(!st.empty()){
            int id = st.top();
            r = min(r, sqr(a[i].x-a[id].x)/(ans[id]*4));
            if(r >= ans[id]){
                st.pop();
            }else{
                break;
            }
        }
        ans[i] = r;
        cout << r << "\n";
        st.push(i);
    }
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 1616 KB 20000 numbers

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 3928 KB 50000 numbers
2 Correct 39 ms 4052 KB 49912 numbers

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 7296 KB 100000 numbers

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 8404 KB 115362 numbers
2 Correct 75 ms 9072 KB 119971 numbers

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 11164 KB 154271 numbers
2 Correct 124 ms 14772 KB 200000 numbers

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 14144 KB 200000 numbers
2 Correct 119 ms 14932 KB 199945 numbers