oj.uz

Submission #151027

# Submission time Handle Problem Language Result Execution time Memory
151027 2019-09-01T15:10:31 Z bogdan10bos Organizing the Best Squad (FXCUP4_squad) C++17
19 / 100
 2094 ms 47512 KB 
#include "squad.h"
#include <bits/stdc++.h>

typedef long double LD;

using namespace std;

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

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 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 191 ms 11000 KB Output is correct
4 Correct 180 ms 11000 KB Output is correct
5 Correct 84 ms 3816 KB Output is correct
6 Correct 1583 ms 47384 KB Output is correct
7 Correct 1596 ms 47512 KB Output is correct
8 Correct 1631 ms 47408 KB Output is correct

Subtask #2
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 252 KB Output is correct
2 Correct 7 ms 376 KB Output is correct
3 Correct 679 ms 13396 KB Output is correct
4 Correct 606 ms 13312 KB Output is correct
5 Correct 69 ms 1784 KB Output is correct
6 Incorrect 2094 ms 31480 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
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 191 ms 11000 KB Output is correct
4 Correct 180 ms 11000 KB Output is correct
5 Correct 84 ms 3816 KB Output is correct
6 Correct 1583 ms 47384 KB Output is correct
7 Correct 1596 ms 47512 KB Output is correct
8 Correct 1631 ms 47408 KB Output is correct
9 Correct 2 ms 252 KB Output is correct
10 Correct 7 ms 376 KB Output is correct
11 Correct 679 ms 13396 KB Output is correct
12 Correct 606 ms 13312 KB Output is correct
13 Correct 69 ms 1784 KB Output is correct
14 Incorrect 2094 ms 31480 KB Output isn't correct
15 Halted 0 ms 0 KB -