Submission #649921

#	Time	Username	Problem	Language	Result	Execution time	Memory
649921		ymm	Balloons (CEOI11_bal)	C++17	40 / 100	203 ms	1964 KiB

bal

#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

typedef pair<double, double> pdd;

struct obj {
	double st;
	pdd f;
};

struct cmp_slope {
	bool operator()(const obj &x, const obj &y) const {
		return x.f.first > y.f.first;
	}
};
struct cmp_st {
	bool operator()(const obj &x, const obj &y) const {
		return x.st < y.st;
	}
};



set<obj, cmp_st> daaard;
set<obj, cmp_slope> *by_slope = (set<obj, cmp_slope> *)&daaard;
set<obj, cmp_st> *by_st = &daaard;

double inter(pdd f, pdd g)
{
	return (f.second - g.second) / (g.first - f.first);
}
double eval(pdd f, double x)
{
	return f.first * x + f.second;
}

double get(double x)
{
	if (by_st->empty())
		return 1e100;
	auto it = by_st->upper_bound({x, {}});
	return eval((--it)->f, x);
}

bool should_remove(pdd l, pdd m, pdd r)
{
	double x = inter(l, r);
	double y0 = eval(m, x);
	double y1 = eval(l, x);
	return y0 >= y1;
}

void insert(pdd f)
{
	auto it1 = by_slope->lower_bound({0, f});
	if (it1 != by_slope->end() && it1->f.first == f.first) {
		if (it1->f.second <= f.second)
			return;
		else
			by_slope->erase(it1++);
	}
	auto it0 = it1; if (it1 != by_slope->begin()) { --it0; }
	if (it1 != by_slope->begin() && it1 != by_slope->end() && should_remove(it0->f, f, it1->f))
		return;
	if (it1 != by_slope->begin()) for (;;) {
		if (it0 == by_slope->begin())
			break;
		auto it00 = it0; --it00;
		if (!should_remove(it00->f, it0->f, f))
			break;
		by_slope->erase(it0);
		it0 = it00;
	}
	if (it1 != by_slope->end()) for (;;) {
		auto it11 = it1; ++it11;
		if (it11 == by_slope->end())
			break;
		if (!should_remove(f, it1->f, it11->f))
			break;
		by_slope->erase(it1);
		it1 = it11;
	}
	if (it1 != by_slope->end()) {
		double st1 = inter(f, it1->f);
		obj o1 = {st1, it1->f};
		by_slope->erase(it1);
		by_slope->insert(o1);
	}
	double st0 = it1 == by_slope->begin()? -1e100: inter(it0->f, f);
	obj o0 = {st0, f};
	by_slope->insert(o0);
}

pdd in()
{
	ll x, y;
	cin >> x >> y;
	return {x, y};
}

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	cout << fixed << setprecision(3);
	int n;
	cin >> n;
	Loop (i,0,n) {
		auto [x, r] = in();
		r = sqrt(r);
		r = min(r, get(x));
		cout << r*r << '\n';
		insert({0.5/r, -x*0.5/r});
	}
}

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