oj.uz

Submission #891239

# Submission time Handle Problem Language Result Execution time Memory
891239 2023-12-22T14:45:28 Z fragadmsc Balloons (CEOI11_bal) C++14
100 / 100
 393 ms 15452 KB 
#include <bits/stdc++.h>
using namespace std;
 
typedef pair<long long, long long> pii;
typedef long long ll;
typedef long double ld;
 
const long long MAXLOG = 23;
const long long MAXN = 1e3+5; // use com cuidado
const long long MOD = 998244353;
const long long inf = 1e9 + 10;
const long long TWO_MOD_INV = 500000004;
 
#define pb push_back
#define mp make_pair
#define f first
#define s second
#define KAMEKAMEHA ios_base::sync_with_stdio(0); ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define sz(x) (int)x.size()

int main() {
    KAMEKAMEHA
    #ifdef FRAGA     
        //freopen("output.out", "w", stdout);
        freopen("err.er", "w", stderr);
    #endif 
    #ifndef FRAGA
        //freopen("cbarn2.in", "r", stdin);
        //freopen("cbarn2.out", "w", stdout);
    #endif
    ll n;
    cin>>n;
    vector<pair<ld, ld>> vet(n+2);
    for(ll i=1;i<=n;i++) {
        cin>>vet[i].f>>vet[i].s;
    }
    vet[0]={-1e10, 2*1e9};
    stack<ll> st;
    st.push(0);
    vector<ld> rad(n+5);
    ll ult;
    for(ll i=1;i<=n;i++) {
        ult=0;
        while(true) {
            //n bateu
            if(vet[i].s<(vet[i].f-vet[st.top()].f)*(vet[i].f-vet[st.top()].f)/(4.0*vet[st.top()].s)) {
                if(vet[i].s<vet[st.top()].s) {// n bateu e eh menor, ja pode encerrar
                    rad[i]=vet[i].s;
                    if(ult!=0) st.push(ult);
                    st.push(i);
                    break;
                } else { //n bateu mas e maior, elimina o ult e continua
                    st.pop();
                }
            } else { //bateu
                //muda pra um raio menor e ve se vai ter um pra deixar o raio menor ainda 
                vet[i].s=(vet[i].f-vet[st.top()].f)*(vet[i].f-vet[st.top()].f)/(4.0*vet[st.top()].s);
                ult=st.top();
                st.pop();
            }
        }
        
    }
    for(ll i=1;i<=n;i++) {
        cout<<fixed<<setprecision(6)<<rad[i]<<endl;
    }
    cout<<endl;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 500 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 4 ms 348 KB 2000 numbers

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 1372 KB 20000 numbers

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 3288 KB 50000 numbers
2 Correct 112 ms 4360 KB 49912 numbers

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 216 ms 6256 KB 100000 numbers

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 244 ms 7148 KB 115362 numbers
2 Correct 228 ms 9328 KB 119971 numbers

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 321 ms 9592 KB 154271 numbers
2 Correct 382 ms 15444 KB 200000 numbers

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 393 ms 11856 KB 200000 numbers
2 Correct 389 ms 15452 KB 199945 numbers