oj.uz

Submission #151019

# Submission time Handle Problem Language Result Execution time Memory
151019 2019-09-01T15:03:22 Z bogdan10bos Organizing the Best Squad (FXCUP4_squad) C++17
47 / 100
 3000 ms 53772 KB 
#include "squad.h"
#include <bits/stdc++.h>
#pragma GCC optimize ("Ofast")

typedef long double LD;

using namespace std;

const LD eps = 1e-6;

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)
	{
		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(l(st) > max(nod->unu(st), nod->doi(st)))
			insert(nod->l, st, mij, l);
		if(l(dr) > max(nod->unu(dr), nod->doi(dr)))
			insert(nod->r, mij, dr, l);
	}

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

	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 221 ms 11172 KB Output is correct
4 Correct 203 ms 10924 KB Output is correct
5 Correct 135 ms 3844 KB Output is correct
6 Correct 2504 ms 53652 KB Output is correct
7 Correct 2482 ms 53728 KB Output is correct
8 Correct 2494 ms 53772 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 658 ms 13360 KB Output is correct
4 Correct 589 ms 13392 KB Output is correct
5 Correct 94 ms 2048 KB Output is correct
6 Correct 2858 ms 34632 KB Output is correct
7 Correct 2840 ms 34616 KB Output is correct
8 Correct 2876 ms 34600 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 221 ms 11172 KB Output is correct
4 Correct 203 ms 10924 KB Output is correct
5 Correct 135 ms 3844 KB Output is correct
6 Correct 2504 ms 53652 KB Output is correct
7 Correct 2482 ms 53728 KB Output is correct
8 Correct 2494 ms 53772 KB Output is correct
9 Correct 2 ms 256 KB Output is correct
10 Correct 7 ms 504 KB Output is correct
11 Correct 658 ms 13360 KB Output is correct
12 Correct 589 ms 13392 KB Output is correct
13 Correct 94 ms 2048 KB Output is correct
14 Correct 2858 ms 34632 KB Output is correct
15 Correct 2840 ms 34616 KB Output is correct
16 Correct 2876 ms 34600 KB Output is correct
17 Correct 108 ms 2928 KB Output is correct
18 Correct 10 ms 504 KB Output is correct
19 Correct 858 ms 13376 KB Output is correct
20 Correct 862 ms 13344 KB Output is correct
21 Correct 213 ms 2948 KB Output is correct
22 Execution timed out 3014 ms 53680 KB Time limit exceeded
23 Halted 0 ms 0 KB -