oj.uz

Submission #151015

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

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 190 ms 10972 KB Output is correct
4 Correct 180 ms 10872 KB Output is correct
5 Correct 86 ms 3868 KB Output is correct
6 Correct 1607 ms 62308 KB Output is correct
7 Correct 1603 ms 62244 KB Output is correct
8 Correct 1614 ms 62532 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 659 ms 14456 KB Output is correct
4 Correct 592 ms 13448 KB Output is correct
5 Correct 71 ms 2312 KB Output is correct
6 Correct 2029 ms 46768 KB Output is correct
7 Correct 2058 ms 46828 KB Output is correct
8 Correct 2041 ms 46812 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 190 ms 10972 KB Output is correct
4 Correct 180 ms 10872 KB Output is correct
5 Correct 86 ms 3868 KB Output is correct
6 Correct 1607 ms 62308 KB Output is correct
7 Correct 1603 ms 62244 KB Output is correct
8 Correct 1614 ms 62532 KB Output is correct
9 Correct 2 ms 256 KB Output is correct
10 Correct 7 ms 504 KB Output is correct
11 Correct 659 ms 14456 KB Output is correct
12 Correct 592 ms 13448 KB Output is correct
13 Correct 71 ms 2312 KB Output is correct
14 Correct 2029 ms 46768 KB Output is correct
15 Correct 2058 ms 46828 KB Output is correct
16 Correct 2041 ms 46812 KB Output is correct
17 Correct 117 ms 5280 KB Output is correct
18 Correct 10 ms 760 KB Output is correct
19 Correct 856 ms 27836 KB Output is correct
20 Correct 836 ms 27820 KB Output is correct
21 Correct 139 ms 3752 KB Output is correct
22 Execution timed out 3065 ms 67472 KB Time limit exceeded
23 Halted 0 ms 0 KB -