oj.uz

Submission #151018

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

typedef 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 183 ms 11232 KB Output is correct
4 Correct 177 ms 11232 KB Output is correct
5 Correct 48 ms 3320 KB Output is correct
6 Correct 910 ms 38044 KB Output is correct
7 Correct 917 ms 37976 KB Output is correct
8 Correct 957 ms 38248 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 6 ms 504 KB Output is correct
3 Correct 478 ms 14212 KB Output is correct
4 Correct 450 ms 13748 KB Output is correct
5 Correct 45 ms 2040 KB Output is correct
6 Correct 1447 ms 26748 KB Output is correct
7 Correct 1477 ms 26740 KB Output is correct
8 Correct 1431 ms 26936 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 183 ms 11232 KB Output is correct
4 Correct 177 ms 11232 KB Output is correct
5 Correct 48 ms 3320 KB Output is correct
6 Correct 910 ms 38044 KB Output is correct
7 Correct 917 ms 37976 KB Output is correct
8 Correct 957 ms 38248 KB Output is correct
9 Correct 2 ms 256 KB Output is correct
10 Correct 6 ms 504 KB Output is correct
11 Correct 478 ms 14212 KB Output is correct
12 Correct 450 ms 13748 KB Output is correct
13 Correct 45 ms 2040 KB Output is correct
14 Correct 1447 ms 26748 KB Output is correct
15 Correct 1477 ms 26740 KB Output is correct
16 Correct 1431 ms 26936 KB Output is correct
17 Correct 104 ms 3192 KB Output is correct
18 Correct 8 ms 632 KB Output is correct
19 Correct 563 ms 13608 KB Output is correct
20 Correct 568 ms 13740 KB Output is correct
21 Correct 94 ms 2936 KB Output is correct
22 Incorrect 2445 ms 41844 KB Output isn't correct
23 Halted 0 ms 0 KB -