oj.uz

Submission #1030143

# Submission time Handle Problem Language Result Execution time Memory
1030143 2024-07-21T21:22:12 Z ArthuroWich Balloons (CEOI11_bal) C++17
100 / 100
 306 ms 11860 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long int
struct bal {
    int x, r;
};
void solve() {
    int n;
    cin >> n;
    vector<long double> ans(n);
    vector<bal> p(n);
    for (int i = 0; i < n; i++) {
        cin >> p[i].x >> p[i].r;
        ans[i] = p[i].r;
    }
    vector<pair<long double, int>> st;
    for (int i = 0; i < n; i++) {
        while(!st.empty()) {
            long double delta = abs(p[i].x-p[st.back().second].x);
            ans[i] = min(ans[i], (long double) delta*delta/((long double)4.0L*st.back().first));
            if (ans[i] >= st.back().first) {
                st.pop_back();
            } else {
                break;
            }
        }
        st.push_back({ans[i], i});
    }
    for (int i = 0; i < n; i++) {
        cout << fixed << setprecision(3) << ans[i] << endl;
    }
}
int32_t main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t;
    t = 1;
    while(t--) {
        solve();
    }
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 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 36 ms 1484 KB 20000 numbers

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 3540 KB 50000 numbers
2 Correct 86 ms 3192 KB 49912 numbers

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 6088 KB 100000 numbers

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 186 ms 7124 KB 115362 numbers
2 Correct 192 ms 7248 KB 119971 numbers

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 251 ms 9108 KB 154271 numbers
2 Correct 306 ms 11768 KB 200000 numbers

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 302 ms 11184 KB 200000 numbers
2 Correct 302 ms 11860 KB 199945 numbers