Submission #707222

#	Time	Username	Problem	Language	Result	Execution time	Memory
707222		therealpain	Balloons (CEOI11_bal)	C++17	100 / 100	201 ms	10136 KiB

bal

#include <bits/stdc++.h> 
#define fi first 
#define se second
#define mp make_pair
#define getbit(x, i) (((x) >> (i)) & 1)
#define all(x) x.begin(), x.end()
#define SQR(x) (x) * (x)
#define TASK ""
 
using namespace std;
 
template <typename T1, typename T2> bool mini(T1 &a, T2 b) {
	if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maxi(T1 &a, T2 b) {
	if (a < b) {a = b; return true;} return false;
}
 
const long long inf = 1e18;
const int mod = 1e9 + 7;
const int N = 2e5 + 7;

stack <pair <double, double>> st;
double x[N], r[N], ans[N];
int n;

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;

	auto calc_r = [&](const pair <double, double> &a, const double &bx) {
		return SQR(a.first - bx) / (4 * a.second);
	};

	for (int i = 1; i <= n; ++i) {
		cin >> x[i] >> r[i];
		double max_r = r[i];
		while (st.size()) {
			pair <double, double> last = st.top();
			double cur = calc_r(st.top(), x[i]);

			max_r = min(max_r, cur);

			if (max_r >= last.second) {
				st.pop();
				continue;
			} else break;

		}
		st.emplace(x[i], max_r);
		ans[i] = max_r;
	}
	cout << fixed << setprecision(3);
	for (int i = 1; i <= n; ++i) cout << ans[i] << "\n";
}

• 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