Submission #656848

#	Time	Username	Problem	Language	Result	Execution time	Memory
656848		Nafeeszx	Balloons (CEOI11_bal)	C++14	40 / 100	195 ms	7308 KiB

bal

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define trav(a, x) for(auto& a : x)
#define FOR(i, a, b) for (int i=(a); i<=(signed)(b); i++)
#define ROF(i, a, b) for (int i=(a); i>=(signed)(b); i--)
#define F0R(i, a) for (int i=0; i<(signed)(a); i++)
#define vi vector<int>
#define all(v) (v).begin(), (v).end()
#define f first
#define s second
typedef long long ll;

const int mod = 1e9 + 7, MOD = 998244353;

int main()
{	
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n; cin >> n;
    vector<pair<double, double>> v(n);
    deque<pair<double, double>> rad;
    vector<double> res(n, 1e18);
    F0R(i, n) {
        cin >> v[i].first >> v[i].second;
    }
    F0R(i, n) {
        
        if(i == 0) {
            rad.push_back({v[i].first, v[i].second});
            res[i] = v[i].second;
            continue;
        }

        /*if(i == 43) {
            F0R(i, rad.size()) cout << rad[i].first << " " << rad[i].second << "\n";
        }*/

        while(rad.size() > 1) {
            auto s = rad[rad.size()-1];
            auto t = rad[rad.size()-2];

            /*double a, b, ra, rb;
            tie(a, ra) = s;
            tie(b, rb) = t;*/

            double opp1 = ((v[i].first - s.first) * (v[i].first - s.first)) / (4 * s.second);
            double opp2 = ((v[i].first - t.first) * (v[i].first - t.first)) / (4 * t.second);
            if(opp1 < opp2) break;
            rad.pop_back();
            //while(rad.size() > 1 && pp < v[i].first) rad.pop_back();

        }

        /*if(i == 43) {
            F0R(i, rad.size()) cout << rad[i].second << " ";
        }*/

        double opp = ((v[i].first - rad.back().first) * (v[i].first - rad.back().first)) / (4 * rad.back().second);
        res[i] = min(v[i].second, opp);
        while(!rad.empty() && rad[rad.size()-1].second <= res[i]) rad.pop_back();
        while(rad.size() > 1) {
            auto s = rad[rad.size()-1];
            auto t = rad[rad.size()-2];
 
            double a, b, ra, rb, x, rx;
            tie(a, ra) = s;
            tie(b, rb) = t;
            x = v[i].first;
            rx = res[i];
            double k = sqrt(ra/rx);
            double p1 = (a - k * x) / (1 - k);
            double pp1 = ((p1 - a)*(p1 - a)) / (4 * rx);
            k = sqrt(rb/rx);
            double p2 = (b - k * x) / (1 - k);
            double pp2 = ((p2 - b)*(p2 - b)) / (4 * rx);
            if(pp1 < pp2) break;
            rad.pop_back();
            //while(rad.size() > 1 && pp < v[i].first) rad.pop_back();

        }
        
        rad.push_back({v[i].first, res[i]});

    }

    F0R(i, n) {
        cout << fixed << setprecision(3) << res[i] << "\n";
    }

    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 0 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10