Submission #649926

#	Time	Username	Problem	Language	Result	Execution time	Memory
649926		ymm	Balloons (CEOI11_bal)	C++17	20 / 100	225 ms	5096 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;

#define double long double

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);
}

const double eps = 1e-7;

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 + eps >= y1;
}

void insert(pdd f)
{
	auto it1 = by_slope->lower_bound({0, {f.first - eps, 0}});
	if (it1 != by_slope->end() && abs(it1->f.first - f.first) < eps) {
		if (it1->f.second <= f.second + eps)
			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);
}

vector<pll> vec;

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) {
		vec.emplace_back(rand()%10+1, rand()%10+1);
		int len = vec.size();
		if (len > 1)
			vec[len-1].first += vec[len-2].first;
	}
	reverse(vec.begin(), vec.end());
	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: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10