#include "squad.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const double eps = 1e-8;
#ifndef DEBUGGGG
#define DEBUGGGG 1
#endif
vector<int> __a, __d, __p;
void initbf(std::vector<int> A, std::vector<int> D, std::vector<int> P) {
__a = A;
__d = D;
__p = P;
}
ll bfbfb(int X, int Y) {
ll ans = 0;
int n = __a.size();
for (int i = 0; i < n; i++){
for (int j = 0; j < n; j++)
if (i != j) {
ans = max(ans, 1ll * X * (__a[i] + __d[j]) + 1ll * Y * (__p[i] + __p[j]));
}
}
return ans;
}
struct Pt{
long long x, y;
int idx;
};
bool operator < (const Pt & a, const Pt & b){
if (a.x == b.x)
return a.y < b.y;
else
return a.x < b.x;
}
bool operator == (const Pt & a, const Pt & b){
return a.x == b.x && a.y == b.y;
}
inline long long operator * (const Pt & a, const Pt & b){
return a.x * b.y - a.y * b.x;
}
inline long long operator % (const Pt & a, const Pt & b){
return a.x * b.x + a.y * b.y;
}
inline Pt operator - (const Pt & a, const Pt & b){
return (Pt){a.x - b.x, a.y - b.y, 0};
}
inline Pt operator + (const Pt & a, const Pt & b){
return (Pt){a.x + b.x, a.y + b.y, 0};
}
long long sqr(long long x){
return x * x;
}
inline double len(const Pt & a){
return sqrt(sqr(a.x) + sqr(a.y));
}
long long absll(long long x){
return x < 0 ? -x : x;
}
vector<Pt> convex_hull(vector<Pt> u){
sort(u.begin(), u.end());
u.erase(unique(u.begin(), u.end()), u.end());
if (u.size() < 3)
return u;
vector<Pt> c;
for(int i=0, o=1, m=1; ~i; i += o){
while(c.size() > m){
Pt a = c.back() - c[c.size() - 2];
Pt b = c.back() - u[i];
if (a * b <= 0)
break;
c.pop_back();
}
c.push_back(u[i]);
if(i + 1 == u.size())
m = c.size(), o = -1;
}
c.pop_back();
return c;
}
vector<Pt> a1, a2, b1, b2;
void fuck(vector<Pt> &a) {
// cout << "fuck" << endl;
a = convex_hull(a);
// for (auto &pt : a) cout << pt.x << ' ' << pt.y << endl;
// cout << "===" << endl;
if (a.size() < 4) return ;
int u = 0, v = 0;
vector<Pt> b;
for (int i = 1; i < a.size(); i++) {
if (a[i].x > a[u].x || (a[i].x == a[u].x && a[i].y < a[u].y))
u = i;
if (a[i].y > a[v].y || (a[i].y == a[v].y && a[i].x < a[v].x))
v = i;
}
for (int i = u; i != v; i = (i + 1) % a.size()) {
b.push_back(a[i]);
}
b.push_back(a[v]);
a.swap(b);
// for (auto &pt : a) cout << pt.x << ' ' << pt.y << endl;
// cout << "QAQ" << endl;
}
void deal(const vector<int>& A, const vector<int>& P,
vector<Pt>& a, vector<Pt>& b) {
int n = A.size();
a.resize(n);
for (int i = 0; i < n; i++) {
a[i].x = A[i];
a[i].y = P[i];
a[i].idx = i;
}
fuck(a);
vector<int> vis;
for (auto &x : a) {
vis.push_back(x.idx);
}
sort(vis.begin(), vis.end());
vis.push_back(n + 1);
b.clear();
for (int i = 0, j = 0; i < n; i++) {
if (vis[j] == i) j++;
else {
b.push_back((Pt){A[i], P[i], i});
}
}
fuck(b);
}
std::vector<Pt> query1(ll X, ll Y, const vector<Pt>& a) {
int L = 0, R = a.size() - 1;
while (L + 5 < R) {
int M = (L + R) / 2;
int M2 = (L + M) / 2;
ll ans1 = a[M].x * X + a[M].y * Y;
ll ans2 = a[M2].x * X + a[M2].y * Y;
if (ans1 > ans2) {
L = M2;
}
else {
R = M;
}
}
L = max(0, L - 1);
R = min(R + 1, int(a.size()) - 1);
Pt u({0, 0, 0});
Pt v({0, 0, 0});
for (int i = L; i <= R; i++) {
ll ans = a[i].x * X + a[i].y * Y;
if (ans > u.x) {
v = u;
u.idx = a[i].idx;
u.x = ans;
}
else if (ans > v.x) {
v.idx = a[i].idx;
v.x = ans;
}
}
vector<Pt> ans;
ans.push_back(u);
ans.push_back(v);
return ans;
}
std::vector<Pt> query(ll X, ll Y, const vector<Pt>& a, const vector<Pt>& b) {
auto u = query1(X, Y, a);
auto v = query1(X, Y, b);
for (auto & pt : v) u.push_back(pt);
return u;
}
void Init(std::vector<int> A, std::vector<int> D, std::vector<int> P){
if (DEBUGGGG)
initbf(A,D,P);
int n = A.size();
deal(A, P, a1, a2);
deal(D, P, b1, b2);
// for (auto &x : a1) cout << x.x << ' ' << x.y << ' ' << x.idx << endl; cout << endl;
// for (auto &x : a2) cout << x.x << ' ' << x.y << ' ' << x.idx << endl; cout << endl;
// for (auto &x : b1) cout << x.x << ' ' << x.y << ' ' << x.idx << endl; cout << endl;
// for (auto &x : b2) cout << x.x << ' ' << x.y << ' ' << x.idx << endl; cout << endl;
}
long long BestSquad(int X, int Y){
if (DEBUGGGG)
return bfbfb(X, Y);
auto u = query(X, Y, a1, a2);
auto v = query(X, Y, b1, b2);
ll ans = 0;
for (auto &p : u) {
for (auto &q : v) {
if (p.idx != q.idx) {
ans = max(ans, p.x + q.x);
}
}
}
return ans;
}
Compilation message
squad.cpp: In function 'std::vector<Pt> convex_hull(std::vector<Pt>)':
squad.cpp:83:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(c.size() > m){
~~~~~~~~~^~~
squad.cpp:91:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(i + 1 == u.size())
~~~~~~^~~~~~~~~~~
squad.cpp: In function 'void fuck(std::vector<Pt>&)':
squad.cpp:108:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 1; i < a.size(); i++) {
~~^~~~~~~~~~
squad.cpp: In function 'void Init(std::vector<int>, std::vector<int>, std::vector<int>)':
squad.cpp:195:6: warning: unused variable 'n' [-Wunused-variable]
int n = A.size();
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
384 KB |
Output is correct |
| 2 |
Correct |
9 ms |
512 KB |
Output is correct |
| 3 |
Execution timed out |
3099 ms |
30368 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
384 KB |
Output is correct |
| 2 |
Execution timed out |
3098 ms |
892 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
384 KB |
Output is correct |
| 2 |
Correct |
9 ms |
512 KB |
Output is correct |
| 3 |
Execution timed out |
3099 ms |
30368 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
