Submission #895053

#	Time	Username	Problem	Language	Result	Execution time	Memory
895053		Jerseys	Balloons (CEOI11_bal)	C++17	10 / 100	32 ms	13140 KiB

bal

#ifdef LOCAL
#include "include/include.h"
#else
#include <ext/pb_ds/assoc_container.hpp>
#include <bits/stdc++.h>
#endif
using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> o_set;
// order_of_key (val): returns the no. of values less than val
// find_by_order (k): returns the kth largest element.(0-based)
template<typename T> using minHeap = priority_queue<T, vector<T>, greater<T>>;
template<typename T> using maxHeap = priority_queue<T>;
#define int long long
#define all(s) s.begin(), s.end()
#define sz(s) (int) s.size()
#define testcases \
    cin >> tt;    \
    for (i = 1; i <= tt; i++)
#define fast                      \
    ios_base::sync_with_stdio(0); \
    cin.tie(NULL);                \
    cout.tie(NULL)
#define deb(a) cerr << #a << " = " << (a) << endl;
#define deb1(a)                                                        \
    cerr << #a << " = [ ";                                             \
    for (auto it = a.begin(); it != a.end(); it++) cerr << *it << " "; \
    cerr << "]" << endl;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef pair<int, int> pii;
typedef vector<pair<int, int>> vpii;
typedef vector<bool> vb;
const int INF = LONG_LONG_MAX;
const int M = 1e9 + 7;

void solve(int tt) {
    int n; cin >> n;
    vi pos(n), rad(n);
    for (int i = 0; i < n; i++) {
        cin >> pos[i] >> rad[i];
    }

    using ldbl = long double;
    using vldbl = vector<ldbl>;

    vi stk; // just indices lol
    vi range; // also a part of the stack
    vldbl ans(n, -1);
    auto push = [&] (int i) {
        while (not empty(stk) and (ans[stk.back()] < ans[i] or pos[i] > range[stk.back()])) {
            stk.pop_back();
            range.pop_back();
        }

        if (empty(stk)) {
            stk.push_back(i);
            range.push_back(1'000'000'000);
            return;
        }


        int j = stk.back();
        int L = pos[i], R = range[j];
        int ret = L;
        while (L <= R) {
            auto ok = [&] (int x) { // is x 'closer' to this circle or stk.back()
                return (ans[j] * (x - pos[i]) * (x - pos[i])) <= (ans[i] * (x - pos[j]) * (x - pos[j]));
            };
            int mid = L + (R - L) / 2;
            if (ok(mid)) {
                ret = mid;
                L = mid + 1;
            } else {
                R = mid - 1;
            }
        }
        stk.push_back(i);
        range.push_back(ret);
    };

    auto getAns = [&] (int x) {
        if (empty(stk)) return (ldbl) INF;

        // deb1(stk);
        // deb1(range);
        int L = 0, R = sz(stk) - 1;
        int ret = L;
        while (L <= R) {
            int mid = L + (R - L) / 2;
            if (range[mid] >= x) {
                ret = mid;
                L = mid + 1;
            } else {
                R = mid - 1;
            }
        }
        
        // deb(ret);
        // cout << "\n";
        int i = stk[ret];
        ldbl l = ((x - pos[i]) * (x - pos[i])) / (4.0L * ans[ret]);
        ldbl t = INF;
        for (int j = 0; j < sz(stk); j++) {
            t = min(t, ((x - pos[stk[j]]) * (x - pos[stk[j]])) / (4.0L * ans[stk[j]]));
        }
        #define EPS 1e-8
        assert(abs(t - l) < EPS);
        return l;
    };

    for (int i = 0; i < n; i++) {
        ans[i] = min(getAns(pos[i]), (ldbl) rad[i]);
        push(i);
    }

    for (int i = 0; i < n; i++) {
        cout << fixed << setprecision(3) << ans[i] << " ";
    }
    cout << "\n";
    
}

int32_t main() {
    fast;
    int tt = 1;
    int i = 1;
    // testcases
        solve(i);
}

Compilation message (stderr)

bal.cpp: In function 'int32_t main()':
bal.cpp:126:9: warning: unused variable 'tt' [-Wunused-variable]
  126 |     int tt = 1;
      |         ^~

• 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