Submission #150893

#	Time	Username	Problem	Language	Result	Execution time	Memory
150893		dragoon	Organizing the Best Squad (FXCUP4_squad)	C++17	100 / 100	1034 ms	55460 KiB

squad

#include "squad.h"
#include<vector>
#include<algorithm>
#include<assert.h>
#include<utility>
using namespace std;

typedef long long LL;

//StaticCHT<LL> cht;
//cht.InsertLine({ id, m, c });
//auto ret = cht.SlidingEval(x);
template<class T = LL>
struct Line {
	int id;
	// y = mx + c
	T m, c;
	// The line starts from start_x.
	static const LL MIN_START_X = 0;
	long double start_x;
	LL Eval(LL x) { return m * x + c; }
	long double Eval(long double x) { return m * x + c; }
	long double Intersect(const Line& other) {
		// mx + c = other.m * x + other.c
		long double num = other.c - c;
		long double den = m - other.m;
		assert(m != other.m);
		return num / den;
	}
};

template<class T = LL>
struct StaticCHT {
	static const int MIN_TYPE = 0;
	static const int MAX_TYPE = 1;
	int type = MAX_TYPE;

	// Stores convex hull lines.
	vector<Line<T>> ch;
	// Used if the query x is increasing.
	// id of the current segment.
	int id = 0;

	void InsertLine(Line<T> cur) {
		int sz = ch.size();
		//if (sz) assert(type == MAX_TYPE || (ch[sz - 1].m > cur.m || (ch[sz - 1].m == cur.m && ch[sz - 1].c >= cur.c)));
		//if (sz) assert(type == MIN_TYPE || (ch[sz - 1].m < cur.m || (ch[sz - 1].m == cur.m && ch[sz - 1].c <= cur.c)));
		if (sz) {
			if (ch[sz - 1].m == cur.m) return;
		}
		while (sz > 1) {
			double left_side = (LL(ch[sz - 1].c - ch[sz - 2].c)) * (ch[sz - 2].m - cur.m);
			double right_side = (LL(ch[sz - 2].m - ch[sz - 1].m)) * (cur.c - ch[sz - 2].c);
			if ((left_side >= right_side)) {
				ch.pop_back();
				sz--;
			}
			else break;
		}
		if (!sz) cur.start_x = Line<T>::MIN_START_X;
		else cur.start_x = ch[sz - 1].Intersect(cur);
		ch.push_back(cur);
	}

	pair<int, T> SlidingEval(T x) {
		// There should be at least one element.
		assert(SZ(ch) > 0);
		// May be ch was updated by the time?
		id = MIN(id, SZ(ch));
		while (id + 1 < SZ(ch) && ((type == MIN_TYPE && ch[id].Eval(x) > ch[id + 1].Eval(x)) ||
			(type == MAX_TYPE && ch[id].Eval(x) < ch[id + 1].Eval(x)))) {
			id++;
		}
		return { ch[id].id, ch[id].Eval(x) };
	}

	vector<int> Eval(double x, int qmode) {
		if (ch.size() == 0) return {};
		int lo = 0, hi = (int)(ch.size()) - 1;
		while (lo < hi) {
			int mid = (lo + hi + 1) / 2;
			if (ch[mid].start_x > x) hi = mid - 1;
			else lo = mid;
		}
		vector<int> V;
		if (qmode && lo) V.push_back(ch[lo - 1].id);
		V.push_back(ch[lo].id);
		if (qmode && lo + 1 < ch.size()) V.push_back(ch[lo + 1].id);
		return V;
	}
};

StaticCHT<LL> Atree1, Atree2;
StaticCHT<LL> Dtree1, Dtree2;
int Amark[300005], Dmark[300005];
vector<int> A, D, P;
struct Person {
	int id, p, z;
};
bool operator< (Person A, Person B) {
	if (A.p != B.p) return A.p < B.p;
	return A.z > B.z;
}
vector<Person> Attack, Defence;

void Init(std::vector<int> A, std::vector<int> D, std::vector<int> P){
	int n = A.size();
	::A = A;
	::D = D;
	::P = P;
	for (int i = 0; i < n; i++) {
		Attack.push_back({ i, P[i], A[i] });
		Defence.push_back({ i, P[i], D[i] });
	}
	sort(Attack.begin(), Attack.end());
	sort(Defence.begin(), Defence.end());
	for (int i = 0; i < n; i++) {
		Atree1.InsertLine({ Attack[i].id, Attack[i].p, Attack[i].z });
		Dtree1.InsertLine({ Defence[i].id, Defence[i].p, Defence[i].z });
	}
	for (auto& p : Atree1.ch) {
		Amark[p.id] = 1;
	}
	for (auto& p : Dtree1.ch) {
		Dmark[p.id] = 1;
	}
	for (int i = 0; i < n; i++) {
		if (!Amark[Attack[i].id]) Atree2.InsertLine({ Attack[i].id, Attack[i].p, Attack[i].z });
		if (!Dmark[Defence[i].id]) Dtree2.InsertLine({ Defence[i].id, Defence[i].p, Defence[i].z });
	}
}

#define MAX(A, B) ((A) > (B) ? (A) : (B))

long long BestSquad(int X, int Y){
	vector<int> AX = Atree1.Eval((1. * Y)/X, 1); vector<int> tx = Atree2.Eval((1. * Y) / X, 0);
	if (tx.size()) AX.push_back(tx[0]);
	vector<int> AY = Dtree1.Eval((1. * Y) / X, 1); vector<int> ty = Dtree2.Eval((1. * Y) / X, 0);
	if (ty.size()) AY.push_back(ty[0]);
	LL ret = 0;
	for (int a : AX) for (int b : AY) {
		if (a != b) {
			ret = MAX(ret, (1LL * X) * (A[a] + D[b]) + (1LL * Y) * (P[a] + P[b]));
		}
	}
	return ret;
}

Compilation message (stderr)

squad.cpp: In instantiation of 'std::vector<int> StaticCHT<T>::Eval(double, int) [with T = long long int]':
squad.cpp:136:44:   required from here
squad.cpp:88:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (qmode && lo + 1 < ch.size()) V.push_back(ch[lo + 1].id);

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