Submission #151434

#	Time	Username	Problem	Language	Result	Execution time	Memory
151434		kuroni	Organizing the Best Squad (FXCUP4_squad)	C++17	100 / 100	1684 ms	43500 KiB

squad

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

struct SPoint
{
	int x, y;

	SPoint(int _x = 0, int _y = 0) : x(_x), y(_y) {}

	inline bool operator<(const SPoint &oth) const
	{
		return x < oth.x || (x == oth.x && y < oth.y);
	}

	inline SPoint operator+(const SPoint &oth) const
	{
		return SPoint(x + oth.x, y + oth.y);
	}
};

struct SVector
{
	int x, y;

	SVector(SPoint _st, SPoint _en) : x(_en.x - _st.x), y(_en.y - _st.y) {}

	inline long long operator*(const SVector &oth) const
	{
		return 1LL * x * oth.y - 1LL * y * oth.x;
	}
};

struct SConvex
{
	vector<SPoint> ve;

	void add(const SPoint &u)
	{
		while (ve.size() >= 2 && SVector(ve[ve.size() - 2], ve[ve.size() - 1]) * SVector(ve[ve.size() - 2], u) >= 0)
			ve.pop_back();
		ve.push_back(u);
	}

	inline SConvex operator+(const SConvex &oth) const
	{
		SConvex ans;
		int l = 0, r = 0;
		while (l < (int)ve.size() || r < (int)oth.ve.size())
		{
			if (l < (int)ve.size() && (r == (int)oth.ve.size() || ve[l] < oth.ve[r]))
				ans.add(ve[l++]);
			else
				ans.add(oth.ve[r++]);
		}
		return ans;
	}

	inline SConvex operator*(const SConvex &oth) const // Minkowski addition
	{
		SConvex ans;
		int l = 0, r = 0;
		ans.add(ve[l] + oth.ve[r]);
		while (l < (int)ve.size() - 1 || r < (int)oth.ve.size() - 1)
		{
			if (l < (int)ve.size() - 1 && (r == (int)oth.ve.size() - 1 || SVector(ve[l], ve[l + 1]) * SVector(oth.ve[r], oth.ve[r + 1]) < 0))
				l++;
			else
				r++;
			ans.add(ve[l] + oth.ve[r]);
		}
		return ans;
	}
} con;

tuple<SConvex, SConvex, SConvex> build(int l, int r, vector<int> &a, vector<int> &d, vector<int> &p)
{
	SConvex ap, dp, pp;
	if (l == r)
	{
		ap.add(SPoint(a[l], p[l]));
		dp.add(SPoint(d[l], p[l]));
	}
	else
	{
		int m = (l + r) / 2;
		SConvex la, ld, lp, ra, rd, rp;
		tie(la, ld, lp) = build(l, m, a, d, p);
		tie(ra, rd, rp) = build(m + 1, r, a, d, p);
		ap = la + ra;
		dp = ld + rd;
		pp = lp + rp + la * rd + ld * ra;
	}
	return make_tuple(ap, dp, pp);
}

void Init(vector<int> a, vector<int> d, vector<int> p)
{
	int n = a.size();
	con = get<2>(build(0, n - 1, a, d, p));
}

long long BestSquad(int x, int y)
{
	int le = 0, ri = con.ve.size() - 2;
	while (le <= ri)
	{
		int mi = (le + ri) / 2;
		long long lv = 1LL * con.ve[mi].x * x + 1LL * con.ve[mi].y * y;
		long long rv = 1LL * con.ve[mi + 1].x * x + 1LL * con.ve[mi + 1].y * y;
		if (lv < rv)
			le = mi + 1;
		else
			ri = mi - 1;
	}
	return 1LL * con.ve[le].x * x + 1LL * con.ve[le].y * y;
}

• Subtask 1: 19 / 19
• Subtask 2: 28 / 28
• Subtask 3: 53 / 53