oj.uz

Submission #982624

# Submission time Handle Problem Language Result Execution time Memory
982624 2024-05-14T14:06:18 Z IdanRosen Balloons (CEOI11_bal) C++
100 / 100
 1722 ms 12116 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pld;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    ll n;
    cin >> n;

    vector<pll> balloons(n);
    for (auto &ref: balloons) cin >> ref.first >> ref.second;

    vector<ld> final_inflate(n);

    vector<ll> mono_stck;
    for (int i = 0; i < n; i++) {
        ll curr_x = balloons[i].first;
        ll max_r = balloons[i].second;

        if (mono_stck.empty()) {
            final_inflate[i] = max_r;

        } else {
//            ll start = 0;
//            ll end = mono_stck.size();
//            while (start < end) {
//                ll third = start + (end - start) / 3;
//                ll third2 = start + 2 * (end - start) / 3;
//
//
//            }
            ld max_radius = max_r;
            for (int j = mono_stck.size() - 1; j >= 0; j--) {
                max_radius = min(max_radius,
                                 (ld) ((curr_x - balloons[mono_stck[j]].first) *
                                       (curr_x - balloons[mono_stck[j]].first)) /
                                 (ld) (4 * final_inflate[mono_stck[j]])
                );
            }

            final_inflate[i] = max_radius;
        }

        while (!mono_stck.empty() && final_inflate[mono_stck.back()] <= final_inflate[i])
            mono_stck.pop_back();
        mono_stck.push_back(i);
    }

    for (auto final_r: final_inflate) {
        cout << fixed << setprecision(4) << final_r << endl;
    }
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 1688 KB 20000 numbers

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 679 ms 3444 KB 50000 numbers
2 Correct 355 ms 3272 KB 49912 numbers

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1157 ms 5936 KB 100000 numbers

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1572 ms 7000 KB 115362 numbers
2 Correct 868 ms 7328 KB 119971 numbers

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1722 ms 9124 KB 154271 numbers
2 Correct 1439 ms 11932 KB 200000 numbers

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 803 ms 11280 KB 200000 numbers
2 Correct 1431 ms 12116 KB 199945 numbers