oj.uz

Submission #151024

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

typedef long double LD;

using namespace std;

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

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 10844 KB Output is correct
4 Correct 182 ms 11000 KB Output is correct
5 Correct 84 ms 3832 KB Output is correct
6 Correct 1618 ms 53848 KB Output is correct
7 Correct 1604 ms 53752 KB Output is correct
8 Correct 1607 ms 53724 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 376 KB Output is correct
3 Correct 683 ms 13336 KB Output is correct
4 Correct 602 ms 13372 KB Output is correct
5 Correct 68 ms 1784 KB Output is correct
6 Correct 2129 ms 34712 KB Output is correct
7 Correct 2185 ms 34608 KB Output is correct
8 Correct 2143 ms 34632 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 10844 KB Output is correct
4 Correct 182 ms 11000 KB Output is correct
5 Correct 84 ms 3832 KB Output is correct
6 Correct 1618 ms 53848 KB Output is correct
7 Correct 1604 ms 53752 KB Output is correct
8 Correct 1607 ms 53724 KB Output is correct
9 Correct 2 ms 256 KB Output is correct
10 Correct 7 ms 376 KB Output is correct
11 Correct 683 ms 13336 KB Output is correct
12 Correct 602 ms 13372 KB Output is correct
13 Correct 68 ms 1784 KB Output is correct
14 Correct 2129 ms 34712 KB Output is correct
15 Correct 2185 ms 34608 KB Output is correct
16 Correct 2143 ms 34632 KB Output is correct
17 Correct 117 ms 2864 KB Output is correct
18 Correct 10 ms 504 KB Output is correct
19 Correct 882 ms 13468 KB Output is correct
20 Correct 858 ms 13420 KB Output is correct
21 Correct 145 ms 2928 KB Output is correct
22 Execution timed out 3050 ms 54124 KB Time limit exceeded
23 Halted 0 ms 0 KB -