Submission #635266

#TimeUsernameProblemLanguageResultExecution timeMemory
635266tamajitbubaBalloons (CEOI11_bal)C++14
20 / 100
226 ms10872 KiB
// g++ -std=c++17 -O3 __.cpp -o test #include <bits/stdc++.h> using namespace std; //defs using ll = long long; #define rep(i,x,y) for(int i=x;i<int(y);i++) #define per(i,x,y) for(int i=int(y)-1;i>=x;i--) #define all(c) c.begin(),c.end() #define sz(x) int(x.size()) #define pb emplace_back #define F first #define S second #define fio cin.tie(nullptr)->sync_with_stdio(false) //helper template<class T> using V = vector<T>; template<class T> using VV = vector<vector<T>>; template<class T, class S> using P = pair<T,S>; template<class T,class U> void chmax(T& x, U y){if(x<y) x=y;} template<class T,class U> void chmin(T& x, U y){if(y<x) x=y;} template<class T> void mkuni(V<T>& v){sort(all(v));v.erase(unique(all(v)),v.end());} //debug print template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){ return o<<"("<<p.fs<<","<<p.sc<<")"; } template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){ o<<"{"; for(const T& v:vc) o<<v<<","; o<<"}\n"; return o; } template<class T> ostream& operator<<(ostream& o,const vector<vector<T> > &vc){ o<<"{"; for(const vector<T>& v:vc) o<<v; o<<"}\n"; return o; } template<class T> T gcd (T a, T b) { return b ? gcd (b, a % b) : a; } template<class T> T binpow(T a, T b, T m) { a %= m; T res = 1; while (b > 0) { if (b & 1) res = res * a % m; a = a * a % m; b >>= 1; } return res; } //global vars const long long inf = 1LL<<62; const int MAXN = 2e5+1; const ll mod = 1e9+7; void pre(){ } double get_r(int x1, int x2, double r1) { return ((x2-x1)*(x2-x1))/(4*r1); } void solve(){ int n; cin >> n; int x[n], r[n]; for (int i = 0; i < n; i++) cin >> x[i] >> r[i]; stack<pair<int, double>> st; // idx, radius vector<double> ans(n); for (int i = 0; i < n; i++) { double max_r = r[i]; while (!st.empty()) { auto last = st.top(); double new_r = get_r(last.F, x[i], last.S); max_r = min(max_r, new_r); if (max_r > last.S) st.pop(); else break; } ans[i] = max_r; st.push({x[i], max_r}); } for (auto i : ans) cout << i << "\n"; } signed main(){ cout<<fixed<<setprecision(9); fio; int test = 1; // cin>>test; pre(); for(int t=1; t<=test; t++){ // cout<<"Case #"<<t<<": "; solve(); } 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...