Submission #312573

#TimeUsernameProblemLanguageResultExecution timeMemory
312573fatemetmhrBalloons (CEOI11_bal)C++17
100 / 100
235 ms10748 KiB
#include<bits/stdc++.h> #define sanastd using namespace std sanastd; const int MAXN = 1000 * 1000 + 10; const long long INF = 1LL * 1000 * 1000 * 1000 * 1000 * 1000 * 1000 + 10; long long n, r[MAXN], x[MAXN]; long double ans[MAXN]; stack <int> balloon; int main () { cout<<fixed<<setprecision(15); ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); cin >> n >> x[0] >> r[0]; balloon.push(0); ans[0] = r[0]; cout << r[0] << endl; for(int i = 1; i < n; i++){ cin >> x[i] >> r[i]; ans[i] = r[i]; while(!balloon.empty() and ans[balloon.top()] <= ans[i]){ long double d = (x[i] - x[balloon.top()]) * (x[i] - x[balloon.top()]) / ( ans[balloon.top()] * 4.0); ans[i] = min(ans[i], d); if(ans[i] >= ans[balloon.top()]) balloon.pop(); } if(!balloon.empty()){ long double d = (x[i] - x[balloon.top()]) * (x[i] - x[balloon.top()]) / (ans[balloon.top()] * 4.0); ans[i] = min(ans[i], d); } balloon.push(i); cout << ans[i] << '\n'; } 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...