Submission #1285713

#	Time	Username	Problem	Language	Result	Execution time	Memory
1285713		thanhliem40	Balloons (CEOI11_bal)	C++20	10 / 100	89 ms	9972 KiB

bal

#include <bits/stdc++.h>
#define ll long long
using namespace std;

// Struct lưu thông tin quả bóng đã bơm (Vị trí X, Bán kính R)
struct Balloon {
    ll X;
    double R;
};

// Hàm tính R_i^max khi tiếp xúc với bóng 'prev' (j)
double cal(double R_j, ll X_j, ll X_i) {
    if (R_j < 1e-9) return 1e18; // Rất lớn nếu R_j = 0
    double delta_X = (double)(X_i - X_j);
    return (delta_X * delta_X) / (4.0 * R_j);
}

void sol() {
    ll n;
    cin >> n;
    vector<pair<ll, double>> v(n + 1); // v[i] = {X_i, M_i}
    for (ll i = 1; i <= n; i++) {
        cin >> v[i].first >> v[i].second;
    }

    vector<double> ans(n + 1);
    // Stack lưu các quả bóng đã bơm tạo thành bao lồi dưới
    stack<Balloon> mono_stack;

    for (ll i = 1; i <= n; i++) {
        ll X_i = v[i].first;
        double M_i = v[i].second;

        double R_i = M_i;

        // BƯỚC 1 & 2: Tính R_i và Duy trì Stack
        while (!mono_stack.empty()) {
            Balloon t = mono_stack.top();
            
            // Tính bán kính tối đa R_i khi tiếp xúc với bóng t (j)
            double r_max_t = cal(t.R, t.X, X_i);
            
            // Cập nhật R_i: R_i = min(R_i, r_max_t)
            R_i = min(R_i, r_max_t);
            
            // Nếu r_max_t <= R_i (tức là bóng t GIỚI HẠN R_i)
            if (abs(R_i - r_max_t) < 1e-9 || R_i < r_max_t) {
                // T đã giới hạn R_i, nên không cần kiểm tra bóng dưới T
                break; 
            }
            // Nếu R_i đã được giới hạn bởi M_i hoặc bóng khác (R_i < r_max_t)
            // và r_max_t > R_i: nghĩa là bóng t không phải là giới hạn gần nhất, 
            // ta loại bỏ t để kiểm tra bóng tiếp theo.
            else { 
                mono_stack.pop();
            }
        }
        
        // BƯỚC 3: Thêm bóng i vào Stack
        // Chỉ cần thêm nếu R_i > 0 để tránh R_j = 0
        if (R_i > 1e-9) { 
            mono_stack.push({X_i, R_i});
        }
        ans[i] = R_i;
    }

    // Ghi kết quả
    for (ll i = 1; i <= n; i++) {
        cout << fixed << setprecision(3) << ans[i] << '\n';
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    // freopen("BALLOONS.INP","r",stdin);
    // freopen("BALLOONS.OUT","w",stdout);

    sol();
    return 0;
}

• Subtask 1: 0 / 10
• Subtask 2: 10 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10