oj.uz

Submission #492885

# Submission time Handle Problem Language Result Execution time Memory
492885 2021-12-09T14:09:15 Z sberens Balloons (CEOI11_bal) C++17
100 / 100
 230 ms 11716 KB 
#include <bits/stdc++.h>

#include <ext/pb_ds/assoc_container.hpp>

using namespace __gnu_pbds;
template<typename K> using hset = gp_hash_table<K, null_type>;
template<typename K, typename V> using hmap = gp_hash_table<K, V>;


using namespace std;

#define all(x) (x).begin(), (x).end()
#define pb push_back
#define eb emplace_back
#define smax(x, y) (x = max(x, y))
#define smin(x, y) (x = min(x, y))

#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define F0R(i, a) FOR(i,0,a)
#define ROF(i, a, b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i, a) ROF(i,0,a)


using ll = long long;
using ld = long double;

template<typename T>
using vv = vector<vector<T>>;

using vi = vector<int>;
using ii = array<int, 2>;
using vii = vector<ii>;
using vvi = vv<int>;

using vll = vector<ll>;
using l2 = array<ll, 2>;
using vl2 = vector<l2>;
using vvll = vv<ll>;

template<typename T>
using minq = priority_queue<T, vector<T>, greater<T>>;
template<typename T>
using maxq = priority_queue<T>;

const ll M = 1000000007;
const ll infll = M * M;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    vector<array<ld, 2>> b(n);
    F0R(i, n) cin >> b[i][0] >> b[i][1];
    // if the current circle is taller than some circles before it, then a new circle cannot intersect them
    // so use a stack somehow to keep track of the circles that we can intersect
    // obviously? monotonically decreasing

    // now say we have this stack of circles with (x, r) in decreasing r (r is how much they were actually filled)
    // and we want to insert a new circle (x', r')
    // for each circle c in the stack, the radius of the new circle if it is to touch c, r' will be ((x - x')^2 + r^2) / (2 * r)
    // now we go down the stack and while r' > c.r
        // smin(r', min(r_for_tangent, max_r))
    stack<int> s;
    F0R(i, n) {
        auto &[xx, rr] = b[i];
        while (!s.empty()) {
            auto [x, r] = b[s.top()];
            ld tanr = pow(xx - x, 2)/ (4.l * r);
            smin(rr, tanr);
            if (rr >= r) s.pop();
            else break;
        }
        s.push(i);
    }
    cout << fixed << setprecision(3);
    for (auto [x, r] : b) {
        cout << r << '\n';
    }
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 1272 KB 20000 numbers

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 3032 KB 50000 numbers
2 Correct 55 ms 3068 KB 49912 numbers

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 5804 KB 100000 numbers

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 6672 KB 115362 numbers
2 Correct 125 ms 7152 KB 119971 numbers

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 174 ms 8720 KB 154271 numbers
2 Correct 204 ms 11680 KB 200000 numbers

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 224 ms 10844 KB 200000 numbers
2 Correct 230 ms 11716 KB 199945 numbers