#include "squad.h"
#include <algorithm>
struct str{
int x0;
int y0;
int z0;
}x[100010];
std::vector<str> St1,St2;
bool cmp(str A, str B)
{
return A.z0<B.z0;
}
double xCoor(str A, str B)
{
return (double)(B.y0-A.y0)/(A.x0-B.x0);
}
void Init(std::vector<int> A, std::vector<int> D, std::vector<int> P){
int N = A.size();
for(int i=0;i<N;i++) x[i]={A[i],D[i],P[i]};
std::sort(x,x+N,cmp);
int n;
str B,C;
for(int i=0;i<N;i++)
{
while(St1.size()>=1)
{
n = St1.size();
if(St1[n-1].x0==x[i].z0)
{
if(St1[n-1].y0<=x[i].x0) St1.pop_back();
else goto u;
}
else break;
}
while(St1.size()>=2)
{
n = St1.size();
B = St1[n-1];
C = St1[n-2];
if(xCoor(B,C)<=xCoor({x[i].z0,x[i].x0,i},B)) break;
else St1.pop_back();
}
St1.push_back({x[i].z0,x[i].x0,i});
u:;
}
for(int i=0;i<N;i++)
{
while(St2.size()>=1)
{
n = St2.size();
if(St2[n-1].x0==x[i].z0)
{
if(St2[n-1].y0<=x[i].y0) St2.pop_back();
else goto v;
}
else break;
}
while(St2.size()>=2)
{
n = St2.size();
B = St2[n-1];
C = St2[n-2];
if(xCoor(B,C)<=xCoor({x[i].z0,x[i].y0,i},B)) break;
else St2.pop_back();
}
St2.push_back({x[i].z0,x[i].y0,i});
v:;
}
}
int getIndex1(double k)
{
int min = 1, max = St1.size()-1, ans = 0;
while(min<=max)
{
int h = (min+max)/2;
if(xCoor(St1[h-1],St1[h])<=k)
{
ans = h;
min = h+1;
}
else max = h-1;
}
return ans;
}
int getIndex2(double k)
{
int min = 1, max = St2.size()-1, ans = 0;
while(min<=max)
{
int h = (min+max)/2;
if(xCoor(St2[h-1],St2[h])<=k)
{
ans = h;
min = h+1;
}
else max = h-1;
}
return ans;
}
long long BestSquad(int X, int Y){
int n1 = getIndex1((double)Y/X);
int n2 = getIndex2((double)Y/X);
printf("%d %d??\n",n1,n2);
long long int ans = 0;
for(int i=n1-1;i<=n1+1;i++)
{
for(int j=n2-1;j<=n2+1;j++)
{
if(0<=i&&i<St1.size()&&0<=j&&j<St2.size())
{
if(St1[i].z0!=St2[j].z0)
{
long long int S = (long long int)X*(St1[i].y0+St2[j].y0)+(long long int)Y*(St1[i].x0+St2[j].x0);
ans = ans>S?ans:S;
}
}
}
}
return ans;
}
Compilation message
squad.cpp: In function 'long long int BestSquad(int, int)':
squad.cpp:115:2: error: 'printf' was not declared in this scope
printf("%d %d??\n",n1,n2);
^~~~~~
squad.cpp:115:2: note: suggested alternative: 'uint'
printf("%d %d??\n",n1,n2);
^~~~~~
uint
squad.cpp:121:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(0<=i&&i<St1.size()&&0<=j&&j<St2.size())
~^~~~~~~~~~~
squad.cpp:121:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(0<=i&&i<St1.size()&&0<=j&&j<St2.size())
~^~~~~~~~~~~
