Submission #1098427

#	Time	Username	Problem	Language	Result	Execution time	Memory
1098427		dark_369	Balloons (CEOI11_bal)	C++14	10 / 100	155 ms	4636 KiB

bal

#include<bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>

#pragma comment(linker, "/stack:256000000")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#define ll long long int
#define ld long double
#define mp make_pair
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define sz(x) ((ll)x.size())
#define endl "\n"
#define pi 3.1415926535897932384626
#define lp(n,v) for(ll i=0;i<n;i++){ll x; cin >> x; v.emplace_back(x);}
#define YES cout << "YES" << endl
#define NO cout << "NO" << endl
#define Yes cout << "Yes" << endl
#define No cout << "No" << endl
using namespace std;
// using namespace __gnu_pbds;

const ll N = 1e5 + 10;
const ll M = 1e9 + 7;

const ll inf = 1e18 + 10;
const ld eps = 1e-9;

ll dx[] = {1,0,-1,0};
ll dy[] = {0,1,0,-1};

// template<class T>
// using ordered_set = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
// find_by_order() order_of_key()

ll binexp(ll a,ll b){
    ll res = 1;
    while(b){
        if(b&1){
            res = (res * a)%M;
        }
        a = (a*a)%M;
        b >>= 1;
    }
    return res;
}

double calc(pair<double,double> p1,pair<double,double> p2){
     double sq = (p1.first - p2.first)*(p1.first - p2.first);
     double divi = 4.0 * p1.second;
     sq /= divi;
     return sq;
}

bool func(pair<double,double> p1,pair<double,double> p2){
     double r1 = calc(p1,p2);
     r1 = min(r1,p2.second);
     return r1 >= p1.second; 
}

void Solve(){
    ll n;
    cin >> n;
    stack<pair<double,double>> st;
    for(ll i = 0 ; i < n ; i ++){
        pair<double,double> p;
        cin >> p.first >> p.second;
        while(!st.empty() && func(st.top(),p)) st.pop();
        if(!st.empty()){
            p.second = min(p.second,calc(st.top(),p));
        }
        cout << fixed << setprecision(3) << p.second << endl;
        st.push(p);
    }
}

int main() {
    // auto begin = std::chrono::high_resolution_clock::now();

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    ll t = 1;
    // cin >> t;

    // freopen("in.txt",  "r", stdin);
    // freopen("out.txt", "w", stdout);

    for (ll i = 1; i <= t; i++) {
        // cout << "Case #" << i << ": ";
        Solve();
    }

    // auto end = std::chrono::high_resolution_clock::now();
    // auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    // cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n";

    return 0;
}

Compilation message (stderr)

bal.cpp:4: warning: ignoring '#pragma comment ' [-Wunknown-pragmas]
    4 | #pragma comment(linker, "/stack:256000000")
      |

• Subtask 1: 10 / 10
• Subtask 2: 0 / 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