#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 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 };
vector<pair<ll, int> > L, R;
int i = x.query(pos);
L.push_back({ x.cht[i].a*X + x.cht[i].b*Y, x.cht[i].idx });
int ii = xx.query(pos);
if (ii != -1)
L.push_back({ xx.cht[ii].a*X + xx.cht[ii].b*Y, xx.cht[ii].idx });
if (i - 1 >= 0)
L.push_back({ x.cht[i - 1].a*X + x.cht[i - 1].b*Y, x.cht[i - 1].idx });
if (i + 1 < (int)x.cht.size())
L.push_back({ x.cht[i + 1].a*X + x.cht[i + 1].b*Y, x.cht[i + 1].idx });
int j = y.query(pos);
R.push_back({ y.cht[j].a*X + y.cht[j].b*Y, y.cht[j].idx });
int jj = yy.query(pos);
if (jj != -1)
R.push_back({ yy.cht[jj].a*X + yy.cht[jj].b*Y, yy.cht[jj].idx });
if (j - 1 >= 0)
R.push_back({ y.cht[j - 1].a*X + y.cht[j - 1].b*Y, y.cht[j - 1].idx });
if (j + 1 < (int)y.cht.size())
R.push_back({ y.cht[j + 1].a*X + y.cht[j + 1].b*Y, y.cht[j + 1].idx });
ll res = 0;
for (int i = 0; i < L.size(); i++)
for (int j = 0; j < R.size(); j++)
if (L[i].second != R[j].second)
res = max(res, L[i].first + R[j].first);
return res;
}
Compilation message
squad.cpp: In member function 'int CHT::query(Fraction)':
squad.cpp:89: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:107:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < v.size(); i++)
~~^~~~~~~~~~
squad.cpp:124:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < v.size(); i++)
~~^~~~~~~~~~
squad.cpp: In function 'long long int BestSquad(int, int)':
squad.cpp:160:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < L.size(); i++)
~~^~~~~~~~~~
squad.cpp:161:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 0; j < R.size(); j++)
~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
3 ms |
508 KB |
Output is correct |
| 3 |
Correct |
350 ms |
42744 KB |
Output is correct |
| 4 |
Correct |
351 ms |
42756 KB |
Output is correct |
| 5 |
Correct |
19 ms |
3064 KB |
Output is correct |
| 6 |
Correct |
295 ms |
42608 KB |
Output is correct |
| 7 |
Correct |
296 ms |
42532 KB |
Output is correct |
| 8 |
Correct |
277 ms |
42696 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
3 ms |
508 KB |
Output is correct |
| 3 |
Correct |
350 ms |
42744 KB |
Output is correct |
| 4 |
Correct |
351 ms |
42756 KB |
Output is correct |
| 5 |
Correct |
19 ms |
3064 KB |
Output is correct |
| 6 |
Correct |
295 ms |
42608 KB |
Output is correct |
| 7 |
Correct |
296 ms |
42532 KB |
Output is correct |
| 8 |
Correct |
277 ms |
42696 KB |
Output is correct |
| 9 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 10 |
Halted |
0 ms |
0 KB |
- |
