Submission #831269

#	Time	Username	Problem	Language	Result	Execution time	Memory
831269		tranxuanbach	Balloons (CEOI11_bal)	C++17	100 / 100	174 ms	7876 KiB

bal

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define fi first
#define se second
#define For(i, l, r) for (auto i = (l); i < (r); i++)
#define ForE(i, l, r) for (auto i = (l); i <= (r); i++)
#define FordE(i, l, r) for (auto i = (l); i >= (r); i--)
#define Fora(v, a) for (auto v: (a))
#define bend(a) (a).begin(), (a).end()
#define isz(a) ((signed)(a).size())

using ll = long long;
using ld = long double;
using pii = pair <int, int>;
using vi = vector <int>;
using vpii = vector <pii>;
using vvi = vector <vi>;

const int N = 2e5 + 5;

int n;
vector <pair <int, double>> a;

signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	// freopen("KEK.inp", "r", stdin);
	// freopen("KEK.out", "w", stdout);
	cout << fixed << setprecision(15);
	cin >> n;
	while (n--){
		int x, max_r;
		cin >> x >> max_r;
		double r = max_r;
		while (not a.empty()){
			auto [tx, tr] = a.back();
			r = min(r, (ll)(x - tx) * (x - tx) / (4ll * tr));
			if (r < tr){
				break;
			}
			a.pop_back();
		}
		a.emplace_back(x, r);
		cout << r << endl;
	}
}

/*
==================================================+
INPUT                                             |
--------------------------------------------------|

--------------------------------------------------|
==================================================+
OUTPUT                                            |
--------------------------------------------------|

--------------------------------------------------|
==================================================+
*/

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10