oj.uz

Submission #447699

# Submission time Handle Problem Language Result Execution time Memory
447699 2021-07-27T11:09:56 Z Sneha_codes Balloons (CEOI11_bal) C++14
100 / 100
 750 ms 8516 KB 
#include <bits/stdc++.h>
#define f first
#define s second
#define N 200005
#define int long long
using namespace std;
double pos[N],rad[N];
stack<pair<double,double>> st;
double inflate(double x,double r) {
    while (!st.empty()) {
        double x1 = st.top().f, r1 = st.top().s;
        r = min(r, ((x1 - x) * (x1 - x)) / (4 * r1));
        if (r >= r1)
            st.pop();
        else
            break;
    }
    st.push({x, r});
    return r;
}
signed main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> pos[i] >> rad[i];
    for (int i = 0; i < n; i++)
        cout << fixed<<setprecision(3)<<inflate(pos[i], rad[i])  << endl;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 720 KB 20000 numbers

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 182 ms 1616 KB 50000 numbers
2 Correct 188 ms 2300 KB 49912 numbers

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 372 ms 2808 KB 100000 numbers

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 439 ms 3240 KB 115362 numbers
2 Correct 441 ms 5208 KB 119971 numbers

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 559 ms 4100 KB 154271 numbers
2 Correct 750 ms 8448 KB 200000 numbers

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 745 ms 4896 KB 200000 numbers
2 Correct 723 ms 8516 KB 199945 numbers