# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
762665 |
2023-06-21T16:13:59 Z |
Sig0001 |
Balloons (CEOI11_bal) |
C++17 |
|
128 ms |
8524 KB |
#include <bits/stdc++.h>
using namespace std;
double maxRadius(int x1, int x2, double r1) {
/**
* (x2 - x1)^2 + (r2 - r1)^2 = (r2 + r1)^2
* (x2 - x1)^2 = 4 r1 r2
*/
return 1LL * (x2 - x1) * (x2 - x1) / (4 * r1);
}
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
int n; cin >> n;
vector<pair<int, double>> a(n); // [x, maxRadius]
for (auto &[x, r]: a) cin >> x >> r;
stack<pair<int, double>> st; // [position, radius]
cout << fixed << setprecision(3);
for (int i = 0; i < n; i++) {
auto [x2, maxR2] = a[i];
double r2 = maxR2;
while (not st.empty()) {
auto [x1, r1] = st.top();
r2 = min(r2, maxRadius(x1, x2, r1));
if (r2 < r1) break;
st.pop();
}
st.emplace(x2, r2);
cout << r2 << '\n';
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
212 KB |
10 numbers |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
2 numbers |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
320 KB |
505 numbers |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
468 KB |
2000 numbers |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
1032 KB |
20000 numbers |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
34 ms |
2428 KB |
50000 numbers |
2 |
Correct |
31 ms |
2376 KB |
49912 numbers |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
68 ms |
4244 KB |
100000 numbers |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
78 ms |
4940 KB |
115362 numbers |
2 |
Correct |
77 ms |
5264 KB |
119971 numbers |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
103 ms |
6424 KB |
154271 numbers |
2 |
Correct |
128 ms |
8524 KB |
200000 numbers |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
128 ms |
7784 KB |
200000 numbers |
2 |
Correct |
128 ms |
8524 KB |
199945 numbers |