Submission #1233819

#	Time	Username	Problem	Language	Result	Execution time	Memory
1233819		goppamach	Balloons (CEOI11_bal)	C++20	10 / 100	103 ms	4932 KiB

bal

#include <bits/stdc++.h>

using namespace std;

template<class T> bool chmax(T &a, T const &b) {
    return (a < b ? (a = b, true) : false);
}

template<class T> bool chmin(T &a, T const &b) {
    return (a > b ? (a = b, true) : false);
}

#define el "\n"
#define pii pair<int, int>
#define pll pair<ll, ll>
#define fi first
#define se second
#define FOR(i, l, r) for (int i = l; i <= r; i++)
#define FOD(i, l, r) for (int i = l; i >= r; i--)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) (int)(x).size()
#define by(x) [](auto const &a, auto const &b) { return a.x < b.x; }
#define fast_io ios_base::sync_with_stdio(false); cin.tie(nullptr);
#define PROBLEM "bal"

using db = long double;
using ll = long long;
using vi = vector<int>;
using vll = vector<ll>;
using vpii = vector<pii>;
using vpll = vector<pll>;

#define LOCAL
#ifdef LOCAL
template<typename T> void _print(const char* name, T&& x) {
    cerr << name << " = " << x << el;
}
#define debug(x) _print(#x, x)
#else
#define debug(x)
#endif

mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());

const int MAXN = 2E5 + 5;
const int INF = 1E9 + 7;
const ll MOD = 1E9 + 7, INFLL = 1E18 + 7;
const double EPS = 1E-9;
const int PRECISION = 3;

struct Circle {
    int x, r;

    Circle(int x, int r): x(x), r(r) {}
};

int a[MAXN];
db res[MAXN];
int n;

void solve() {
    cin >> n;

    stack<Circle> inflated;
    FOR(i, 1, n) {
        int x; db max_r;
        cin >> x >> max_r;

        while (!inflated.empty()) {
            auto const &prev = inflated.top();
            chmin(max_r, (db)(x - prev.x) * (x - prev.x) / (4.0 * prev.r));
            if (max_r >= prev.r) {
                inflated.pop();
                continue;
            } else {
                break;
            }
        }

        inflated.emplace(x, max_r);
        res[i] = max_r;
    }

    cout << fixed << setprecision(PRECISION);
    FOR(i, 1, n) {
        cout << res[i] << el;
    }
}

int main() {
    fast_io
    #ifndef LOCAL
    freopen(PROBLEM ".INP", "r", stdin);
    freopen(PROBLEM ".OUT", "w", stdout);
    #endif

    int t = 1;
    // cin >> t;
    while (t--) solve();
}

• 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