제출 #634301

#제출 시각아이디문제언어결과실행 시간메모리
634301SharpEdgedBalloons (CEOI11_bal)C++17
10 / 100
286 ms7652 KiB
#include <bits/stdc++.h> template<class T> bool ckmin(T& a, T b) { return b < a ? a = b, 1 : 0; } template<class T> bool ckmax(T& a, T b) { return a < b ? a = b, 1 : 0; } typedef long long ll; const char nl = '\n'; using namespace std; int main() { int n; cin >> n; vector<double> ans(n); deque<pair<int, double>> mono; int sz = 0; auto eval = [&](pair<int, double> a, int b){ return a.second * (b - a.first); }; for (int i = 0; i < n; i++){ int x; double r; cin >> x >> r; while (sz >= 2 && eval(mono[sz-1], x) > eval(mono[sz-2], x)){ sz--; mono.pop_back(); } ans[i] = sqrt(r); if (!mono.empty()) ckmin(ans[i], eval(mono[sz], x)); double rate = 0.5 * (1 / ans[i]); ans[i] *= ans[i]; while (!mono.empty() && mono.back().second >= rate) mono.pop_back(); mono.push_back({x, rate}); } cout << fixed << setprecision(10); for (int i = 0; i < n; i++) cout << ans[i] << nl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...