#include "squad.h"
#include <bits/stdc++.h>
#define g(tp, x) get<x>(tp)
#define eb emplace_back
#define all(v) (v).begin(), (v).end()
using namespace std;
typedef long long ll;
typedef tuple <ll, ll, int> tp3;
vector <tp3> p1, p2, ch1, chs1, ch2, chs2, temp;
bool chk1[303030], chk2[303030];
bool ccw(tp3 a, tp3 b, tp3 c) {
return (g(b, 0) - g(a, 0)) * (g(c, 1) - g(a, 1)) -
(g(c, 0) - g(a, 0)) * (g(b, 1) - g(a, 1)) >= 0;
}
void Init(vector<int> A, vector<int> D, vector<int> P){
int n = A.size();
for(int i = 0; i < n; i++) {
p1.eb((ll)A[i], (ll)P[i], i);
p2.eb((ll)D[i], (ll)P[i], i);
}
sort(all(p1), [](tp3 a, tp3 b) {
if(g(a, 0) == g(b, 0)) return g(a, 1) > g(b, 1);
else return a < b;
});
for(int i = 0; i < n; i++) {
while(!temp.empty() && g(temp[temp.size()-1], 1) < g(p1[i], 1)) {
temp.pop_back();
}
temp.eb(p1[i]);
}
for(int i = 0; i < temp.size(); i++) {
while(ch1.size() >= 2 && ccw(ch1[ch1.size()-2], ch1[ch1.size()-1], temp[i])) {
ch1.pop_back();
}
ch1.eb(temp[i]);
}
for(int i = 0; i < ch1.size(); i++) chk1[g(ch1[i], 2)] = true;
temp.clear();
for(int i = 0; i < n; i++) {
if(chk1[g(p1[i], 2)]) continue;
while(!temp.empty() && g(temp[temp.size()-1], 1) < g(p1[i], 1)) {
temp.pop_back();
}
temp.eb(p1[i]);
}
for(int i = 0; i < temp.size(); i++) {
while(chs1.size() >= 2 && ccw(chs1[chs1.size()-2], chs1[chs1.size()-1], temp[i])) {
chs1.pop_back();
}
chs1.eb(temp[i]);
}
temp.clear();
sort(all(p2), [](tp3 a, tp3 b) {
if(g(a, 0) == g(b, 0)) return g(a, 1) > g(b, 1);
else return a < b;
});
for(int i = 0; i < n; i++) {
while(!temp.empty() && g(temp[temp.size()-1], 1) < g(p2[i], 1)) {
temp.pop_back();
}
temp.eb(p2[i]);
}
for(int i = 0; i < temp.size(); i++) {
while(ch2.size() >= 2 && ccw(ch2[ch2.size()-2], ch2[ch2.size()-1], temp[i])) {
ch2.pop_back();
}
ch2.eb(temp[i]);
}
for(int i = 0; i < ch2.size(); i++) chk2[g(ch2[i], 2)] = true;
temp.clear();
for(int i = 0; i < n; i++) {
if(chk2[g(p2[i], 2)]) continue;
while(!temp.empty() && g(temp[temp.size()-1], 1) < g(p2[i], 1)) {
temp.pop_back();
}
temp.eb(p2[i]);
}
for(int i = 0; i < temp.size(); i++) {
while(chs2.size() >= 2 && ccw(chs2[chs2.size()-2], chs2[chs2.size()-1], temp[i])) {
chs2.pop_back();
}
chs2.eb(temp[i]);
}
}
long long BestSquad(int X, int Y){
ll ma1 = 0, ma2 = 0, md1 = 0, md2 = 0;
int ia = 0, id = 0;
int lb, ub;
lb = 0, ub = ch1.size()-2;
while(lb < ub) {
int m = (lb + ub + 1) >> 1;
if((g(ch1[m+1], 1) - g(ch1[m], 1)) * Y >
-X * (g(ch1[m+1], 0) - g(ch1[m], 0))) lb = m;
else ub = m - 1;
}
ia = lb;
ma1 = max(ma1, X * g(ch1[ia], 0) + Y * g(ch1[ia], 1));
if(ia > 0) ma2 = max(ma2, X * g(ch1[ia-1], 0) + Y * g(ch1[ia-1], 1));
if(ia+1 < ch1.size()) {
ma2 = max(ma2, X * g(ch1[ia+1], 0) + Y * g(ch1[ia+1], 1));
if(ma2 > ma1) swap(ma1, ma2), ia++;
}
if(!chs1.empty()) {
lb = 0, ub = chs1.size()-2;
while(lb < ub) {
int m = (lb + ub + 1) >> 1;
if((g(chs1[m+1], 1) - g(chs1[m], 1)) * Y >
-X * (g(chs1[m+1], 0) - g(chs1[m], 0))) lb = m;
else ub = m - 1;
}
ma2 = max(ma2, X * g(chs1[lb], 0) + Y * g(chs1[lb], 1));
if(lb+1 < chs1.size()) ma2 = max(ma2, X * g(chs1[lb+1], 0) + Y * g(chs1[lb+1], 1));
}
lb = 0, ub = ch2.size()-2;
while(lb < ub) {
int m = (lb + ub + 1) >> 1;
if((g(ch2[m+1], 1) - g(ch2[m], 1)) * Y >
-X * (g(ch2[m+1], 0) - g(ch2[m], 0))) lb = m;
else ub = m - 1;
}
id = min(lb, (int)ch2.size()-1);
md1 = max(md1, X * g(ch2[id], 0) + Y * g(ch2[id], 1));
if(id > 0) md2 = max(md2, X * g(ch2[id-1], 0) + Y * g(ch2[id-1], 1));
if(id+1 < ch2.size()){
md2 = max(md2, X * g(ch2[id+1], 0) + Y * g(ch2[id+1], 1));
if(md2 > md1) swap(md1, md2), id++;
}
if(!chs2.empty()) {
lb = 0, ub = chs2.size()-2;
while(lb < ub) {
int m = (lb + ub + 1) >> 1;
if((g(chs2[m+1], 1) - g(chs2[m], 1)) * Y >
-X * (g(chs2[m+1], 0) - g(chs2[m], 0))) lb = m;
else ub = m - 1;
}
lb = min(lb, (int)chs2.size()-1);
md2 = max(md2, X * g(chs2[lb], 0) + Y * g(chs2[lb], 1));
if(lb+1 < chs2.size()) ma2 = max(ma2, X * g(chs2[lb+1], 0) + Y * g(chs2[lb+1], 1));
}
if(g(ch1[ia], 2) != g(ch2[id], 2)) return ma1 + md1;
else return max(ma1 + md2, ma2 + md1);
}
Compilation message
squad.cpp: In function 'void Init(std::vector<int>, std::vector<int>, std::vector<int>)':
squad.cpp:37:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < temp.size(); i++) {
~~^~~~~~~~~~~~~
squad.cpp:44:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < ch1.size(); i++) chk1[g(ch1[i], 2)] = true;
~~^~~~~~~~~~~~
squad.cpp:54:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < temp.size(); i++) {
~~^~~~~~~~~~~~~
squad.cpp:75:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < temp.size(); i++) {
~~^~~~~~~~~~~~~
squad.cpp:82:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < ch2.size(); i++) chk2[g(ch2[i], 2)] = true;
~~^~~~~~~~~~~~
squad.cpp:92:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < temp.size(); i++) {
~~^~~~~~~~~~~~~
squad.cpp: In function 'long long int BestSquad(int, int)':
squad.cpp:115:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(ia+1 < ch1.size()) {
~~~~~^~~~~~~~~~~~
squad.cpp:128:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(lb+1 < chs1.size()) ma2 = max(ma2, X * g(chs1[lb+1], 0) + Y * g(chs1[lb+1], 1));
~~~~~^~~~~~~~~~~~~
squad.cpp:141:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(id+1 < ch2.size()){
~~~~~^~~~~~~~~~~~
squad.cpp:155:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(lb+1 < chs2.size()) ma2 = max(ma2, X * g(chs2[lb+1], 0) + Y * g(chs2[lb+1], 1));
~~~~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
256 KB |
Output is correct |
| 2 |
Correct |
3 ms |
504 KB |
Output is correct |
| 3 |
Correct |
287 ms |
28144 KB |
Output is correct |
| 4 |
Correct |
287 ms |
27840 KB |
Output is correct |
| 5 |
Correct |
20 ms |
4384 KB |
Output is correct |
| 6 |
Incorrect |
320 ms |
56320 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
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 |
449 ms |
39984 KB |
Output is correct |
| 4 |
Correct |
454 ms |
39964 KB |
Output is correct |
| 5 |
Correct |
21 ms |
2228 KB |
Output is correct |
| 6 |
Correct |
560 ms |
48460 KB |
Output is correct |
| 7 |
Correct |
597 ms |
48208 KB |
Output is correct |
| 8 |
Correct |
563 ms |
48176 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
256 KB |
Output is correct |
| 2 |
Correct |
3 ms |
504 KB |
Output is correct |
| 3 |
Correct |
287 ms |
28144 KB |
Output is correct |
| 4 |
Correct |
287 ms |
27840 KB |
Output is correct |
| 5 |
Correct |
20 ms |
4384 KB |
Output is correct |
| 6 |
Incorrect |
320 ms |
56320 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
