oj.uz

Submission #150893

# Submission time Handle Problem Language Result Execution time Memory
150893 2019-09-01T10:12:14 Z dragoon Organizing the Best Squad (FXCUP4_squad) C++17
100 / 100
 1034 ms 55460 KB 
#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

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.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 280 ms 20944 KB Output is correct
4 Correct 278 ms 20688 KB Output is correct
5 Correct 20 ms 4460 KB Output is correct
6 Correct 329 ms 55460 KB Output is correct
7 Correct 326 ms 55384 KB Output is correct
8 Correct 324 ms 55312 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 7 ms 636 KB Output is correct
3 Correct 579 ms 21200 KB Output is correct
4 Correct 567 ms 21200 KB Output is correct
5 Correct 27 ms 2548 KB Output is correct
6 Correct 764 ms 43116 KB Output is correct
7 Correct 758 ms 43060 KB Output is correct
8 Correct 773 ms 42932 KB Output is correct

Subtask #3
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 280 ms 20944 KB Output is correct
4 Correct 278 ms 20688 KB Output is correct
5 Correct 20 ms 4460 KB Output is correct
6 Correct 329 ms 55460 KB Output is correct
7 Correct 326 ms 55384 KB Output is correct
8 Correct 324 ms 55312 KB Output is correct
9 Correct 2 ms 256 KB Output is correct
10 Correct 7 ms 636 KB Output is correct
11 Correct 579 ms 21200 KB Output is correct
12 Correct 567 ms 21200 KB Output is correct
13 Correct 27 ms 2548 KB Output is correct
14 Correct 764 ms 43116 KB Output is correct
15 Correct 758 ms 43060 KB Output is correct
16 Correct 773 ms 42932 KB Output is correct
17 Correct 108 ms 3316 KB Output is correct
18 Correct 9 ms 760 KB Output is correct
19 Correct 625 ms 21252 KB Output is correct
20 Correct 620 ms 21224 KB Output is correct
21 Correct 38 ms 3748 KB Output is correct
22 Correct 1027 ms 55452 KB Output is correct
23 Correct 1034 ms 55444 KB Output is correct
24 Correct 1029 ms 55432 KB Output is correct