Submission #883261

#	Time	Username	Problem	Language	Result	Execution time	Memory
883261		Wobert	Balloons (CEOI11_bal)	C++17	100 / 100	204 ms	6740 KiB

bal

#include "bits/stdc++.h"
#ifdef LOCAL
#include "dbg.h"
#else
#define dbg(...) 0
#endif

#define fox(i, n) for (int i = 0; i < (n); ++i)
#define rep(i, a, b) for (int i = (a); i < (b); ++i)
#define rrep(i, a, b) for (int i = (a); i >= (b); --i)
#define fore(x, v) for (auto &&x : v)
#define forp(a, b, v) for (auto &&[a, b] : v)
#define pb push_back
#define eb emplace_back
#define tomax(a, b) ((a) = max((a), (b)))
#define tomin(a, b) ((a) = min((a), (b)))
#define F first
#define S second
#define all(x) begin(x), end(x)
#define EL "\n"

using namespace std;

using vi = vector<int>;
using ll = long long;
using vll = vector<ll>;
using pii = pair<int, int>;
using vpii = vector<pii>;
using db = long double;

template<class T>
int sz(T& container) {
    return (int) container.size();
}

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
ll urand(ll a, ll b) { return rng() % (b-a+1) + a; }

db maxdist(pair<db, db> pr, db x2) {
    auto [x1, r] = pr;
    return pow(x1-x2, 2) / r / 4;
}

void solve() {
    int n; cin >> n;
    stack<pair<db, db>> s;

    cout << fixed << setprecision(9);
    fox(_, n) {
        db x, r;
        cin >> x >> r;
        db ans = r;

        // drop everything with radius < ans
        // find something we touch
        while (!s.empty() && s.top().S <= ans) {
            tomin(ans, maxdist(s.top(), x));
            if (s.top().S <= ans) s.pop();
        }
        if (!s.empty()) tomin(ans, maxdist(s.top(), x));

        s.emplace(x, ans);
        cout << ans << EL;
    }
}

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

//    int t; cin >> t;
//    while (t--)
        solve();
    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