oj.uz

Submission #1098435

# Submission time Handle Problem Language Result Execution time Memory
1098435 2024-10-09T11:40:47 Z dark_369 Balloons (CEOI11_bal) C++14
100 / 100
 133 ms 5392 KB 
#include<bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>

#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;
}

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()){
             double r1 = calc(st.top(),p);
             p.second = min(r1,p.second);
             if(p.second >= st.top().second){
                st.pop();
                continue;
             }
             else break;
        }     
        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;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 856 KB 20000 numbers

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 1576 KB 50000 numbers
2 Correct 32 ms 1600 KB 49912 numbers

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 2748 KB 100000 numbers

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 3148 KB 115362 numbers
2 Correct 76 ms 3408 KB 119971 numbers

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 4176 KB 154271 numbers
2 Correct 133 ms 5332 KB 200000 numbers

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 4692 KB 200000 numbers
2 Correct 126 ms 5392 KB 199945 numbers