oj.uz

Submission #883261

# Submission time Handle Problem Language Result Execution time Memory
883261 2023-12-05T01:24:24 Z Wobert Balloons (CEOI11_bal) C++17
100 / 100
 204 ms 6740 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() && 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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 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 600 KB 505 numbers

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 468 KB 2000 numbers

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 944 KB 20000 numbers

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 2244 KB 50000 numbers
2 Correct 44 ms 2096 KB 49912 numbers

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 3592 KB 100000 numbers

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 4180 KB 115362 numbers
2 Correct 108 ms 4300 KB 119971 numbers

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 5068 KB 154271 numbers
2 Correct 176 ms 6720 KB 200000 numbers

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 204 ms 6168 KB 200000 numbers
2 Correct 173 ms 6740 KB 199945 numbers