oj.uz

Submission #883262

# Submission time Handle Problem Language Result Execution time Memory
883262 2023-12-05T01:26:26 Z Wobert Balloons (CEOI11_bal) C++17
100 / 100
 182 ms 3300 KB 
#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()) {
            tomin(ans, maxdist(s.top(), x));
            if (s.top().S <= ans) s.pop();
            else break;
        }

        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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB 10 numbers

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB 2 numbers

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 452 KB 505 numbers

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 344 KB 2000 numbers

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 732 KB 20000 numbers

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 1604 KB 50000 numbers
2 Correct 42 ms 1104 KB 49912 numbers

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 2144 KB 100000 numbers

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 2380 KB 115362 numbers
2 Correct 105 ms 1760 KB 119971 numbers

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 148 ms 2816 KB 154271 numbers
2 Correct 182 ms 2900 KB 200000 numbers

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 180 ms 3300 KB 200000 numbers
2 Correct 169 ms 2772 KB 199945 numbers