Submission #525596

#	Time	Username	Problem	Language	Result	Execution time	Memory
525596		Tam_theguide	Balloons (CEOI11_bal)	C++14	100 / 100	343 ms	14908 KiB

bal

//dung stack de tim voi tat ca cac phan tu trong mang:
//phan tu gan nhat ve phia ben trai nho hon a[i]/lon hon a[i];
//stack chi tim duoc gan nhat
//tinh chat monotone:
//gia su khi them vao phan tu a[i] ta pop stack den phan tu a[j] thi cac phan tu a[t] sao cho j<t<i la mot day don dieu (MONOTONE)
//do ta pop tu a[i] den a[j] va pop het cac phan tu a[t] suy ra cac phan tu a[t] phai cung thoa man mot tinh chat nao neu khong thi khi them vao mot phan tu trong doan a[t] thi ta buoc phai pop mot so phan tu khac do mau thuan ve tinh chat

#include <bits/stdc++.h>
using namespace std;
stack<pair<long double, long double>>potential;
long double process(long double x, long double r){
    while (!potential.empty()){
        r=min(r, ((x-potential.top().first)*(x-potential.top().first))/(4*potential.top().second));
        if (r>potential.top().second) potential.pop();
        else break;
    }
    potential.push({x, r});
    return r;
}


int n;
long double x[300005];
long double r[300005];
int main(){
    cin>>n;
    for (int i=1;i <=n; i++){
        cin>>x[i]>>r[i];
    }
    for (int i=1;i <=n; i++){
        cout<<fixed<<setprecision(3)<<process(x[i], r[i])<<'\n';
    }
}

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