#include "squad.h"
#include <cstdio>
#include <algorithm>
using namespace std;
typedef pair<int, int> p;
typedef pair<p, int> pp;
pp a[300003];
vector<pp> AA, DD;
vector<p> AAA[300003], DDD[300003];
inline long long ccw(p &u, p &v, p &w) {
return (long long)(w.first - u.first) * (v.second - u.second) - (long long)(w.second - u.second) * (v.first - u.first);
}
inline long long ccw(pp &u, pp &v, pp &w) {
return ccw(u.first, v.first, w.first);
}
inline void create(int N, vector<int> &A, vector<int> &P, vector<pp> &r, vector<p> *s) {
int i, j;
for (i = 0; i < N; i++) {
a[i].first.first = A[i];
a[i].first.second = P[i];
a[i].second = i;
}
sort(a, a + N);
for (i = 0; i < N; i++) {
while (!r.empty() && r[r.size() - 1].first.first <= a[i].first.first && r[r.size() - 1].first.second <= a[i].first.second || r.size() > 1 && ccw(r[r.size() - 2], r[r.size() - 1], a[i]) <= 0) r.pop_back();
r.push_back(a[i]);
}
for (i = 0; i < r.size(); i++) {
auto L = i ? lower_bound(a, a + N, r[i - 1]) : a, R = i + 1 < r.size() ? upper_bound(a, a + N, r[i + 1]) : a + N;
auto &t = s[r[i].second];
for (; L < R; L++) {
if (*L == r[i]) continue;
while (!t.empty() && t[t.size() - 1].first <= L->first.first && t[t.size() - 1].second <= L->first.second || t.size() > 1 && ccw(t[t.size() - 2], t[t.size() - 1], L->first) <= 0) t.pop_back();
t.push_back(L->first);
}
}
}
void Init(std::vector<int> A, std::vector<int> D, std::vector<int> P){
int N = A.size();
create(N, A, P, AA, AAA);
create(N, D, P, DD, DDD);
//for (auto t : AA) printf("%d %d %d\n", t.first.first, t.first.second, t.second); puts("");
//for (auto t : DD) printf("%d %d %d\n", t.first.first, t.first.second, t.second); puts("");
//for (int i = 0; i < N; i++) if (!AAA[i].empty()) { printf("%d : ", i); for (auto t : AAA[i]) printf("(%d %d) ", t.first, t.second); puts(""); }
//for (int i = 0; i < N; i++) if (!DDD[i].empty()) { printf("%d : ", i); for (auto t : DDD[i]) printf("(%d %d) ", t.first, t.second); puts(""); }
}
inline pp bs(vector<pp> &AA, long long X, long long Y) {
int L = 0, R = AA.size();
while (R - L > 1) {
int M = (L + R >> 1) - 1;
if (X * AA[M].first.first + Y * AA[M].first.second < X * AA[M + 1].first.first + Y * AA[M + 1].first.second) L = M + 1;
else R = M;
}
return AA[L];
}
inline p bs(vector<p> &AAA, long long X, long long Y) {
int L = 0, R = AAA.size() - 1;
while (L < R) {
int M = L + R >> 1;
if (X * AAA[M].first + Y * AAA[M].second < X * AAA[M + 1].first + Y * AAA[M + 1].second) L = M + 1;
else R = M;
}
return AAA[L];
}
long long BestSquad(int X, int Y){
auto A = bs(AA, X, Y), D = bs(DD, X, Y);
//printf("%d %d %d, %d %d %d\n", A.first.first, A.first.second, A.second, D.first.first, D.first.second, D.second);
if (A.second != D.second) return 1ll * X * (A.first.first + D.first.first) + 1ll * Y * (A.first.second + D.first.second);
auto A2 = bs(AAA[A.second], X, Y), D2 = bs(DDD[D.second], X, Y);
return max(
1ll * X * (A.first.first + D2.first) + 1ll * Y * (A.first.second + D2.second),
1ll * X * (D.first.first + A2.first) + 1ll * Y * (D.first.second + A2.second)
);
}
Compilation message
squad.cpp: In function 'void create(int, std::vector<int>&, std::vector<int>&, std::vector<std::pair<std::pair<int, int>, int> >&, std::vector<std::pair<int, int> >*)':
squad.cpp:31:72: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
while (!r.empty() && r[r.size() - 1].first.first <= a[i].first.first && r[r.size() - 1].first.second <= a[i].first.second || r.size() > 1 && ccw(r[r.size() - 2], r[r.size() - 1], a[i]) <= 0) r.pop_back();
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
squad.cpp:34:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (i = 0; i < r.size(); i++) {
~~^~~~~~~~~~
squad.cpp:35:63: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
auto L = i ? lower_bound(a, a + N, r[i - 1]) : a, R = i + 1 < r.size() ? upper_bound(a, a + N, r[i + 1]) : a + N;
~~~~~~^~~~~~~~~~
squad.cpp:39:65: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
while (!t.empty() && t[t.size() - 1].first <= L->first.first && t[t.size() - 1].second <= L->first.second || t.size() > 1 && ccw(t[t.size() - 2], t[t.size() - 1], L->first) <= 0) t.pop_back();
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
squad.cpp:23:9: warning: unused variable 'j' [-Wunused-variable]
int i, j;
^
squad.cpp: In function 'pp bs(std::vector<std::pair<std::pair<int, int>, int> >&, long long int, long long int)':
squad.cpp:58:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int M = (L + R >> 1) - 1;
~~^~~
squad.cpp: In function 'p bs(std::vector<std::pair<int, int> >&, long long int, long long int)':
squad.cpp:68:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int M = L + R >> 1;
~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
14464 KB |
Output is correct |
| 2 |
Correct |
15 ms |
14464 KB |
Output is correct |
| 3 |
Correct |
271 ms |
24952 KB |
Output is correct |
| 4 |
Incorrect |
269 ms |
25080 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
14464 KB |
Output is correct |
| 2 |
Incorrect |
20 ms |
14592 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
14464 KB |
Output is correct |
| 2 |
Correct |
15 ms |
14464 KB |
Output is correct |
| 3 |
Correct |
271 ms |
24952 KB |
Output is correct |
| 4 |
Incorrect |
269 ms |
25080 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
