Submission #982624

#	Time	Username	Problem	Language	Result	Execution time	Memory
982624		IdanRosen	Balloons (CEOI11_bal)	C++98	100 / 100	1722 ms	12116 KiB

bal

#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 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10