oj.uz

Submission #151434

# Submission time Handle Problem Language Result Execution time Memory
151434 2019-09-03T00:31:48 Z kuroni Organizing the Best Squad (FXCUP4_squad) C++17
100 / 100
 1684 ms 43500 KB 
#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.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 4 ms 376 KB Output is correct
3 Correct 646 ms 16248 KB Output is correct
4 Correct 646 ms 16252 KB Output is correct
5 Correct 81 ms 3204 KB Output is correct
6 Correct 1436 ms 43016 KB Output is correct
7 Correct 1412 ms 43168 KB Output is correct
8 Correct 1426 ms 43132 KB Output is correct

Subtask #2
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 8 ms 504 KB Output is correct
3 Correct 714 ms 22012 KB Output is correct
4 Correct 715 ms 21896 KB Output is correct
5 Correct 48 ms 1884 KB Output is correct
6 Correct 1304 ms 34572 KB Output is correct
7 Correct 1319 ms 33548 KB Output is correct
8 Correct 1316 ms 34520 KB Output is correct

Subtask #3
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 4 ms 376 KB Output is correct
3 Correct 646 ms 16248 KB Output is correct
4 Correct 646 ms 16252 KB Output is correct
5 Correct 81 ms 3204 KB Output is correct
6 Correct 1436 ms 43016 KB Output is correct
7 Correct 1412 ms 43168 KB Output is correct
8 Correct 1426 ms 43132 KB Output is correct
9 Correct 2 ms 256 KB Output is correct
10 Correct 8 ms 504 KB Output is correct
11 Correct 714 ms 22012 KB Output is correct
12 Correct 715 ms 21896 KB Output is correct
13 Correct 48 ms 1884 KB Output is correct
14 Correct 1304 ms 34572 KB Output is correct
15 Correct 1319 ms 33548 KB Output is correct
16 Correct 1316 ms 34520 KB Output is correct
17 Correct 75 ms 5396 KB Output is correct
18 Correct 11 ms 632 KB Output is correct
19 Correct 826 ms 24404 KB Output is correct
20 Correct 820 ms 24368 KB Output is correct
21 Correct 64 ms 2348 KB Output is correct
22 Correct 1684 ms 43296 KB Output is correct
23 Correct 1670 ms 43288 KB Output is correct
24 Correct 1682 ms 43500 KB Output is correct