Submission #528345

#	Time	Username	Problem	Language	Result	Execution time	Memory
528345		Falcon	Balloons (CEOI11_bal)	C++17	100 / 100	183 ms	9404 KiB

bal

#include <bits/stdc++.h>

#ifdef DEBUG
    #include "debug.hpp"
#endif

using namespace std;

#define all(c)        (c).begin(), (c).end()
#define rall(c)       (c).rbegin(), (c).rend()
#define rep(i, N)     for (int i = 0; i < (N); ++i)
#define rrep(i, N)    for (int i = (N)-1; i >= 0; --i)
#define rep1(i, N)    for (int i = 1; i <= (N); ++i)
#define rep2(i, s, e) for (int i = (s); i <= (e); ++i)

#ifdef DEBUG
    #define debug(x...)                                                        \
        do {                                                                   \
            ++dbg::depth;                                                      \
            string dbg_vals = dbg::to_string(x);                               \
            --dbg::depth;                                                      \
            dbg::fprint(__func__, __LINE__, #x, dbg_vals);                     \
        } while (false)
#else
    #define debug(...) 42
#endif

template<typename T> inline T& ckmin(T& a, T b) { return a = a > b ? b : a; }
template<typename T> inline T& ckmax(T& a, T b) { return a = a < b ? b : a; }

#define double long double

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

    int n;
    cin >> n;
    vector<int> x(n);
    vector<double> r(n);

    deque<int> s;

    auto f = [&](int i, int X) -> double {
        return (double)(X - x[i]) * (X - x[i]) / (4 * r[i]);
    };

    rep(i, n) {
        cin >> x[i] >> r[i];
        while (!s.empty()) {
            ckmin(r[i], f(s.front(), x[i]));
            if (r[s.front()] > r[i])
                break;
            else
                s.pop_front();
        }
        s.push_front(i);
        cout << fixed << setprecision(3) << r[i] << '\n';
    }

    return 0;
}

• 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