oj.uz

Submission #956907

# Submission time Handle Problem Language Result Execution time Memory
956907 2024-04-02T16:18:05 Z dzzz Balloons (CEOI11_bal) C++17
100 / 100
 157 ms 14420 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 2e5 + 10;
struct ball{
    long double x, r;
};
int n;
ball a[maxn];
long double ra[maxn];

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    for(int i = 1; i <= n; ++i) {
        cin >> a[i].x >> a[i].r;
        ra[i] = a[i].r;
    }
    deque <ball> d;
    for(int i = 1; i <= n; ++i) {
        while(!d.empty()) {
            ball tmp = d.back();
            ra[i] = min(ra[i], (a[i].x - tmp.x)*(a[i].x-tmp.x) / (4.0*tmp.r));
            if(ra[i] >= tmp.r) {
                d.pop_back();
            }
            else break;
        }
        d.push_back({a[i].x, ra[i]});
    }
    for(int i = 1; i <= n; ++i) {
        cout << fixed << setprecision(3)<< ra[i] << '\n';
    }
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 4696 KB 20000 numbers

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 7476 KB 50000 numbers
2 Correct 46 ms 8016 KB 49912 numbers

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 7824 KB 100000 numbers

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 10396 KB 115362 numbers
2 Correct 84 ms 11860 KB 119971 numbers

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 10320 KB 154271 numbers
2 Correct 146 ms 14396 KB 200000 numbers

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 11372 KB 200000 numbers
2 Correct 154 ms 14420 KB 199945 numbers