oj.uz

Submission #151026

# Submission time Handle Problem Language Result Execution time Memory
151026 2019-09-01T15:09:28 Z bogdan10bos Organizing the Best Squad (FXCUP4_squad) C++17
47 / 100
 3000 ms 53824 KB 
#include "squad.h"
#include <bits/stdc++.h>

typedef long double LD;

using namespace std;

const LD eps = 1e-6;
const int LVL = 50;

class LiChao
{
public:
	struct Line
	{
		LD a = 0, b = 0;
		int id = 0;

		Line() { ; }
		Line(LD _a, LD _b, int _id) { a = _a, b = _b, id = _id; }

		LD operator()(LD x)
		{
			return a * x + b;
		}

		const bool operator== (const Line &l) const
		{
			return (id == l.id);
		}
	};

	struct Node
	{
		Line unu, doi;
		Node *l, *r;

		Node(Line a, Line b, Node *_l, Node *_r)
		{
			unu = a, doi = b, l = _l, r = _r;
		}
	};

	Line df;
	Node *root;

	LiChao()
	{
		df = Line(0, 0, -1);
		root = new Node(df, df, 0, 0);
	}

	void insert(Node *&nod, LD st, LD dr, Line l, int lvl)
	{
		if(l == df)	return;
		if(nod == 0)
		{
			nod = new Node(l, df, 0, 0);
			return;
		}

		LD mij = (st + dr) / 2.0;
		if(nod->unu(mij) < l(mij))
		{
			swap(nod->unu, l);
			swap(nod->doi, l);
		}
		else if(nod->doi(mij) < l(mij))
			swap(nod->doi, l);

		if(l == df)	return;
		if(lvl >= LVL)	return;

		if(l(st) > max(nod->unu(st), nod->doi(st)))
			insert(nod->l, st, mij, l, lvl + 1);
		if(l(dr) > max(nod->unu(dr), nod->doi(dr)))
			insert(nod->r, mij, dr, l, lvl + 1);
	}

	void insert(LD a, LD b, int id)
	{
		insert(root, 0, 1e9, Line(a, b, id), 0);
	}

	pair<Line, Line> query(Node *nod, LD st, LD dr, LD x, int lvl)
	{
		if(nod == 0 || lvl > LVL)	return {df, df};

		Line unu = nod->unu, doi = nod->doi;
		if(unu(x) < doi(x))	swap(unu, doi);
		pair<Line, Line> nxt = {df, df};

		LD mij = st + (dr - st) / 2;
		if(x < mij)	nxt = query(nod->l, st, mij, x, lvl + 1);
		else	nxt = query(nod->r, mij, dr, x, lvl + 1);

		if(nxt.first(x) > unu(x))
		{
			swap(doi, nxt.first);
			swap(unu, doi);
		}
		else if(nxt.first(x) > doi(x))
			swap(doi, nxt.first);

		if(nxt.second(x) > unu(x))
		{
			swap(doi, nxt.second);
			swap(unu, doi);
		}
		else if(nxt.second(x) > doi(x))
			swap(doi, nxt.second);

		return {unu, doi};
	}

	pair<Line, Line> query(LD x)
	{
		return query(root, 0, 1e9, x, 0);
	}
};
LiChao att, def;

vector<int> AA, DD, PP;
void Init(vector<int> A, vector<int> D, vector<int> P)
{
	AA = A, DD = D, PP = P;
	int N = A.size();
	for(int i = 0; i < N; i++)
	{
		att.insert(A[i], P[i], i);
		def.insert(D[i], P[i], i);
	}
}

long long calc(int a, int d, int X, int Y)
{
	if(a == d)	return -1;
	long long ans = 1LL * X * (AA[a] + DD[d]) + 1LL * Y * (PP[a] + PP[d]);
	return ans;
}

long long BestSquad(int X, int Y)
{
	LD frac = LD(X) / LD(Y);
	auto at = att.query(frac);
	auto df = def.query(frac);

	vector<int> ids;
	ids.push_back(at.first.id);
	ids.push_back(at.second.id);
	ids.push_back(df.first.id);
	ids.push_back(df.second.id);

	long long ans = -1;
	ans = max(ans, calc(ids[0], ids[2], X, Y));
	ans = max(ans, calc(ids[1], ids[2], X, Y));
	ans = max(ans, calc(ids[0], ids[3], X, Y));
	return ans;
}

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 191 ms 10868 KB Output is correct
4 Correct 180 ms 10928 KB Output is correct
5 Correct 86 ms 3840 KB Output is correct
6 Correct 1616 ms 53652 KB Output is correct
7 Correct 1665 ms 53824 KB Output is correct
8 Correct 1601 ms 53748 KB Output is correct

Subtask #2
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 7 ms 376 KB Output is correct
3 Correct 675 ms 13272 KB Output is correct
4 Correct 604 ms 13288 KB Output is correct
5 Correct 69 ms 1784 KB Output is correct
6 Correct 2155 ms 34668 KB Output is correct
7 Correct 2188 ms 34680 KB Output is correct
8 Correct 2188 ms 34552 KB Output is correct

Subtask #3
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 191 ms 10868 KB Output is correct
4 Correct 180 ms 10928 KB Output is correct
5 Correct 86 ms 3840 KB Output is correct
6 Correct 1616 ms 53652 KB Output is correct
7 Correct 1665 ms 53824 KB Output is correct
8 Correct 1601 ms 53748 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 7 ms 376 KB Output is correct
11 Correct 675 ms 13272 KB Output is correct
12 Correct 604 ms 13288 KB Output is correct
13 Correct 69 ms 1784 KB Output is correct
14 Correct 2155 ms 34668 KB Output is correct
15 Correct 2188 ms 34680 KB Output is correct
16 Correct 2188 ms 34552 KB Output is correct
17 Correct 116 ms 2808 KB Output is correct
18 Correct 10 ms 504 KB Output is correct
19 Correct 887 ms 13324 KB Output is correct
20 Correct 859 ms 13360 KB Output is correct
21 Correct 161 ms 2892 KB Output is correct
22 Execution timed out 3015 ms 53796 KB Time limit exceeded
23 Halted 0 ms 0 KB -