oj.uz

Submission #737090

# Submission time Handle Problem Language Result Execution time Memory
737090 2023-05-06T15:35:09 Z study Balloons (CEOI11_bal) C++17
100 / 100
 166 ms 10220 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;

struct Bal{
    int x;
    double max_r;
};

const int N = 2e5, inf = 1e18;

Bal bals[N];

double calc_rayon(Bal a, Bal b){
    double dist = a.x-b.x;
    return dist*dist/4.0/a.max_r;
}

int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
    cout.precision(3);
    cout << fixed;
    int n;
    cin >> n;
    for (int i=0; i<n; ++i){
        cin >> bals[i].x >> bals[i].max_r;
    }
    stack<Bal> st;
    for (int i=0; i<n; ++i){
        double crt_ans = bals[i].max_r;
        while (!st.empty()){
            Bal f = st.top();
            crt_ans = min(crt_ans,calc_rayon(f,bals[i]));
            if (crt_ans > f.max_r) st.pop();
            else break;
        }
        st.push({bals[i].x,crt_ans});
        cout << crt_ans << '\n';
    }
	return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 324 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 18 ms 1032 KB 20000 numbers

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 2344 KB 50000 numbers
2 Correct 52 ms 2792 KB 49912 numbers

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 4424 KB 100000 numbers

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 5004 KB 115362 numbers
2 Correct 100 ms 6172 KB 119971 numbers

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 6476 KB 154271 numbers
2 Correct 162 ms 10220 KB 200000 numbers

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 166 ms 7740 KB 200000 numbers
2 Correct 154 ms 10188 KB 199945 numbers