oj.uz

Submission #151532

# Submission time Handle Problem Language Result Execution time Memory
151532 2019-09-03T13:52:59 Z edenooo Organizing the Best Squad (FXCUP4_squad) C++17
100 / 100
 984 ms 56832 KB 
#include "squad.h"
#include<vector>
#include<algorithm>
using namespace std;

#define INF 9'000'000'000'000'000'000LL
#define ll long long

struct Fraction {
	ll a, b; // a/b
	bool operator< (Fraction &n)
	{
		if (a == -INF) return true; //틀린 이유
		if (n.a == -INF) return false;
		ll ta, tb, tc, td;
		ta = a; tb = b; tc = n.a; td = n.b;
		if (tb < 0) { ta *= -1; tb *= -1; }
		if (td < 0) { tc *= -1; td *= -1; }
		return ta * td < tb * tc;
	}
	bool operator<= (Fraction &n)
	{
		if (a == -INF) return true;
		if (n.a == -INF) return false;
		ll ta, tb, tc, td;
		ta = a; tb = b; tc = n.a; td = n.b;
		if (tb < 0) { ta *= -1; tb *= -1; }
		if (td < 0) { tc *= -1; td *= -1; }
		return ta * td <= tb * tc;
	}
};

struct Line {
	ll a, b;
	Fraction s;
	int idx;

	bool operator< (const Line &n) const
	{
		if (a != n.a) return a < n.a;
		return b > n.b;
	}
};

int N;
vector<Line> v, re;

Fraction Cross(Line &A, Line &B)
{
	return { (B.b - A.b),(A.a - B.a) };
}

struct CHT {
	vector<Line> cht;
	void insert(Line n)
	{
		while (!cht.empty())
		{
			if (cht.back().a == n.a)
			{
				if (cht.back().b <= n.b)
				{
					re.push_back(cht.back());
					cht.pop_back();
				}
				else
				{
					re.push_back(n); //틀린 이유
					return;
				}
			}
			else
			{
				Fraction c = Cross(cht.back(), n);
				n.s.a = c.a; n.s.b = c.b;
				if (n.s <= cht.back().s) //틀린 이유
				{
					re.push_back(cht.back());
					cht.pop_back();
				}
				else break;
			}
		}
		cht.push_back(n);
	}
	int query(Fraction x)
	{
		if (cht.empty()) return -1;

		int lo = 0, hi = (int)cht.size();
		for (int i = 0; i < 20; i++)
		{
			int mid = lo + hi >> 1;
			if (x < cht[mid].s) hi = mid;
			else lo = mid;
		}
		return lo;
	}
} x, xx, y, yy;

void Init(std::vector<int> A, std::vector<int> D, std::vector<int> P){
	v.reserve(300301); re.reserve(300301);
	x.cht.reserve(300301); xx.cht.reserve(300301); y.cht.reserve(300301); yy.cht.reserve(300301);
	N = A.size();
	for (int i = 0; i < N; i++)
	{
		Line n = { (ll)A[i], (ll)P[i], {-INF, 1LL}, i }; //-INF : 틀린 이유
		v.push_back(n);
	}
	sort(v.begin(), v.end());
	for (int i = 0; i < v.size(); i++)
		x.insert(v[i]);

	sort(re.begin(), re.end());
	int M = (int)re.size();
	for (int i = 0; i < M; i++) //틀린 이유
		re[i].s = { -INF, 1LL };
	for (int i = 0; i < M; i++)
		xx.insert(re[i]);
	v.clear(); re.clear();

	for (int i = 0; i < N; i++)
	{
		Line n = { (ll)D[i], (ll)P[i], {-INF, 1LL}, i };
		v.push_back(n);
	}
	sort(v.begin(), v.end());
	for (int i = 0; i < v.size(); i++)
		y.insert(v[i]);
	sort(re.begin(), re.end());
	M = (int)re.size();
	for (int i = 0; i < M; i++)
		re[i].s = { -INF, 1LL };
	for (int i = 0; i < M; i++)
		yy.insert(re[i]);
	v.clear(); re.clear();
}

long long BestSquad(int X, int Y) {
	Fraction pos = { (ll)X, (ll)Y };
	int i = x.query(pos);
	int j = y.query(pos);

	if (x.cht[i].idx != y.cht[j].idx)
		return x.cht[i].a*X + x.cht[i].b*Y + y.cht[j].a*X + y.cht[j].b*Y;
	else
	{
		ll res = 0;
		int ii = xx.query(pos);
		if (ii != -1)
			res = max(res, xx.cht[ii].a*X + xx.cht[ii].b*Y + y.cht[j].a*X + y.cht[j].b*Y);

		int jj = yy.query(pos);
		if (jj != -1)
			res = max(res, x.cht[i].a*X + x.cht[i].b*Y + yy.cht[jj].a*X + yy.cht[jj].b*Y);

		if (i - 1 >= 0)
			res = max(res, x.cht[i - 1].a*X + x.cht[i - 1].b*Y + y.cht[j].a*X + y.cht[j].b*Y);
		if (i + 1 < (int)x.cht.size())
			res = max(res, x.cht[i + 1].a*X + x.cht[i + 1].b*Y + y.cht[j].a*X + y.cht[j].b*Y);
		if (j - 1 >= 0)
			res = max(res, x.cht[i].a*X + x.cht[i].b*Y + y.cht[j - 1].a*X + y.cht[j - 1].b*Y);
		if (j + 1 < (int)y.cht.size())
			res = max(res, x.cht[i].a*X + x.cht[i].b*Y + y.cht[j + 1].a*X + y.cht[j + 1].b*Y);

		if (res == 0) while (1);
		return res;
	}
	return -1;
}

Compilation message

squad.cpp: In member function 'int CHT::query(Fraction)':
squad.cpp:93:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    int mid = lo + hi >> 1;
              ~~~^~~~
squad.cpp: In function 'void Init(std::vector<int>, std::vector<int>, std::vector<int>)':
squad.cpp:111:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < v.size(); i++)
                  ~~^~~~~~~~~~
squad.cpp:128:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < v.size(); i++)
                  ~~^~~~~~~~~~

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 504 KB Output is correct
3 Correct 347 ms 42744 KB Output is correct
4 Correct 351 ms 42636 KB Output is correct
5 Correct 18 ms 3064 KB Output is correct
6 Correct 276 ms 42716 KB Output is correct
7 Correct 277 ms 42616 KB Output is correct
8 Correct 278 ms 42568 KB Output is correct

Subtask #2
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 6 ms 760 KB Output is correct
3 Correct 538 ms 44980 KB Output is correct
4 Correct 520 ms 45088 KB Output is correct
5 Correct 22 ms 2792 KB Output is correct
6 Correct 709 ms 56716 KB Output is correct
7 Correct 675 ms 56752 KB Output is correct
8 Correct 686 ms 56832 KB Output is correct

Subtask #3
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 504 KB Output is correct
3 Correct 347 ms 42744 KB Output is correct
4 Correct 351 ms 42636 KB Output is correct
5 Correct 18 ms 3064 KB Output is correct
6 Correct 276 ms 42716 KB Output is correct
7 Correct 277 ms 42616 KB Output is correct
8 Correct 278 ms 42568 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 6 ms 760 KB Output is correct
11 Correct 538 ms 44980 KB Output is correct
12 Correct 520 ms 45088 KB Output is correct
13 Correct 22 ms 2792 KB Output is correct
14 Correct 709 ms 56716 KB Output is correct
15 Correct 675 ms 56752 KB Output is correct
16 Correct 686 ms 56832 KB Output is correct
17 Correct 106 ms 2856 KB Output is correct
18 Correct 8 ms 760 KB Output is correct
19 Correct 596 ms 45164 KB Output is correct
20 Correct 593 ms 45056 KB Output is correct
21 Correct 33 ms 2528 KB Output is correct
22 Correct 970 ms 44976 KB Output is correct
23 Correct 940 ms 45188 KB Output is correct
24 Correct 984 ms 45040 KB Output is correct