oj.uz

Submission #622488

# Submission time Handle Problem Language Result Execution time Memory
622488 2022-08-04T10:21:26 Z bLIC Balloons (CEOI11_bal) C++17
100 / 100
 153 ms 10480 KB 
#include <bits/stdc++.h>
using namespace std;

#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define sz(x) (int)(x).size()
#define ft first
#define sd second
#define pb push_back
#define endl '\n'

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vii;
typedef vector<ll> vl;
typedef pair<ll, ll> pll;
typedef vector<pll> vll;
typedef vector<vi> vvi;

#define dbg if(1)

void printbit(int x) {string s="\n";while(x){s=((x%2)?'1':'0')+s;x/=2;} cout<<s;}

const ll MOD = 1e9+7;
const int INF = 1e9;
const int N = 200001;

#define sq(x) ((x)*(x))

void solve(){
    int n;
    cin>>n;
    vll a(n);
    for (pll &x:a) cin>>x.ft>>x.sd;

    stack<int> s;
    double ans[n];
    for (int i = 0;i<n;i++){
        ans[i] = a[i].sd;

        while(!s.empty()){
            int tp = s.top();
            ans[i] = min(ans[i], sq(a[i].ft-a[tp].ft)/(4*ans[tp]));
            if (ans[tp] < ans[i]) s.pop();
            else break;
        }
        s.push(i);
    }
    for (int i = 0;i<n;i++) cout<<fixed<<setprecision(3)<<ans[i]<<'\n';

}


int main() {
     ios_base::sync_with_stdio(false);
     cin.tie(NULL);
     cout.tie(NULL);

    int t = 1;
    // cin>>t;

    while(t--){

        solve();
        cout<<endl;
    }
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB 2000 numbers

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 1116 KB 20000 numbers

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 2684 KB 50000 numbers
2 Correct 33 ms 2816 KB 49912 numbers

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 5016 KB 100000 numbers

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 5744 KB 115362 numbers
2 Correct 92 ms 6416 KB 119971 numbers

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 7564 KB 154271 numbers
2 Correct 136 ms 10444 KB 200000 numbers

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 9352 KB 200000 numbers
2 Correct 125 ms 10480 KB 199945 numbers