oj.uz

Submission #916379

# Submission time Handle Problem Language Result Execution time Memory
916379 2024-01-25T19:00:45 Z jlass Balloons (CEOI11_bal) C++17
100 / 100
 635 ms 5716 KB 
#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
using namespace std;
const ll MOD = 1e9 + 7;
ld eps = 1e-8;
/*
Notes for stack:
store dimensions of balloon, as well as for what distance it is significant for
From bottom to top of the stack, the distance it's significant should be increasing 

Find insert size
Because the significant distance is increasing in size, we pop elements in the stack until the distance is less than the insertion distance
Then, take min of balloon size and stack thing

Use Geometries to find balloon sizing and distances ft. Marvin

*/

ld calc_r(ld dx, ld r1) {
    return dx * dx / 4 / r1;
}

//given that r1 > r2, otherwise we do not care
ld calc_x(ld x1, ld r1, ld x2, ld r2) {
    ld l = x2, r = 1e9 + 1;
    while(r - l > eps) {
        ld m = l + (r - l) / 2;
        ld d1 = calc_r(m - x1, r1);
        ld d2 = calc_r(m - x2, r2);
        if(d1 > d2) {
            l = m;
        } else {
            r = m;
        }
    }
    return l + (r - l) / 2;
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout << fixed << setprecision(3);
    int n; cin >> n;
    stack<pair<ld, pair<ld,ld>>> s; //stored as {significant distance, {x, r}}
    for(int i = 0; i < n; i++) {
        ld x, maxr; cin >> x >> maxr;
        while(s.size() && x > s.top().first) {
            s.pop();
        }
        ld r = min(maxr, s.empty() ? maxr : calc_r(x - s.top().second.first, s.top().second.second));
        //current balloon will always be significant for some portion of graph
        while(s.size() && (r > s.top().second.second || calc_x(s.top().second.first, s.top().second.second, x, r) > s.top().first)) {
            s.pop();
        }
        ld dist = (s.empty() ? 1e9 + 5 : calc_x(s.top().second.first, s.top().second.second, x, r));
        s.push({dist, {x,r}});
        cout << r << '\n';
    }

    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 1 ms 344 KB 2 numbers

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 496 KB 2000 numbers

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 764 KB 20000 numbers

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 160 ms 1360 KB 50000 numbers
2 Correct 107 ms 1748 KB 49912 numbers

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 351 ms 2552 KB 100000 numbers

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 386 ms 3080 KB 115362 numbers
2 Correct 254 ms 3396 KB 119971 numbers

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 532 ms 4144 KB 154271 numbers
2 Correct 433 ms 5716 KB 200000 numbers

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 635 ms 4868 KB 200000 numbers
2 Correct 424 ms 5576 KB 199945 numbers