oj.uz

Submission #151033

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

typedef long double LD;

using namespace std;

const LD eps = 1e-6;
const int LVL = 45;
const int OPS = 60;

class LiChao
{
public:
	int ops;
	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);
		ops = 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;
		}

		ops++;
		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(ops > OPS)	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)
	{
		ops = 0;
		insert(root, 0, 1e9, Line(a, b, id), 0);
	}

	pair<Line, Line> query(Node *nod, LD st, LD dr, LD x)
	{
		if(nod == 0)	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);
		else	nxt = query(nod->r, mij, dr, x);

		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);
	}
};
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 198 ms 10932 KB Output is correct
4 Correct 187 ms 10932 KB Output is correct
5 Correct 81 ms 3832 KB Output is correct
6 Correct 1550 ms 53604 KB Output is correct
7 Correct 1534 ms 53784 KB Output is correct
8 Correct 1539 ms 53832 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 504 KB Output is correct
3 Correct 661 ms 13440 KB Output is correct
4 Correct 597 ms 13448 KB Output is correct
5 Correct 65 ms 1916 KB Output is correct
6 Correct 2027 ms 34588 KB Output is correct
7 Correct 2025 ms 34740 KB Output is correct
8 Correct 2032 ms 34696 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 198 ms 10932 KB Output is correct
4 Correct 187 ms 10932 KB Output is correct
5 Correct 81 ms 3832 KB Output is correct
6 Correct 1550 ms 53604 KB Output is correct
7 Correct 1534 ms 53784 KB Output is correct
8 Correct 1539 ms 53832 KB Output is correct
9 Correct 2 ms 256 KB Output is correct
10 Correct 7 ms 504 KB Output is correct
11 Correct 661 ms 13440 KB Output is correct
12 Correct 597 ms 13448 KB Output is correct
13 Correct 65 ms 1916 KB Output is correct
14 Correct 2027 ms 34588 KB Output is correct
15 Correct 2025 ms 34740 KB Output is correct
16 Correct 2032 ms 34696 KB Output is correct
17 Correct 118 ms 2816 KB Output is correct
18 Correct 10 ms 504 KB Output is correct
19 Correct 885 ms 13316 KB Output is correct
20 Correct 833 ms 13408 KB Output is correct
21 Correct 140 ms 3128 KB Output is correct
22 Execution timed out 3032 ms 54332 KB Time limit exceeded
23 Halted 0 ms 0 KB -