#include "squad.h"
#include <bits/stdc++.h>
using namespace std;
struct Point{
long long x, y;
int ind;
bool operator <(const Point A) const{
if(x==A.x) return y<A.y;
return x<A.x;
}
};
vector<Point> pa,pb,ca,cb,cca,ccb;
int n;
bool in[300010];
bool chk(Point a, Point b, Point c){
long long x=b.x-a.x, y=b.y-a.y, xx=c.x-b.x, yy=c.y-b.y;
return x*yy-y*xx>=0;
}
vector<Point> f(vector<Point> feed){
vector<Point> ret;
for(auto i:feed){
while(!ret.empty()&&ret[ret.size()-1].x==i.x&&ret[ret.size()-1].y<=i.y){
in[ret[ret.size()-1].ind]=false;
ret.pop_back();
}
while(ret.size()>1&&chk(ret[ret.size()-2],ret[ret.size()-1],i)) ret.pop_back();
ret.push_back(i);
in[i.ind]=true;
}
return ret;
}
void Init(std::vector<int> A, std::vector<int> D, std::vector<int> P){
n = A.size();
for(int i=0;i<n;i++){
pa.push_back({A[i],P[i],i});
pb.push_back({D[i],P[i],i});
}
sort(pa.begin(), pa.end());
sort(pb.begin(), pb.end());
for(int i=0;i<n;i++) in[i]=false;
ca = f(pa);
for(auto i:pa){
if(in[i.ind]==false) cca.push_back(i);
in[i.ind]=false;
}
cca = f(cca);
for(int i=0;i<n;i++) in[i]=false;
cb = f(pb);
for(auto i:pb) if(in[i.ind]==false) ccb.push_back(i);
ccb = f(ccb);
/*
cout<<"ca --------------\n";
for(auto i:ca){
cout<<i.x<<" "<<i.y<<" "<<i.ind<<"\n";
}
cout<<"cb --------------\n";
for(auto i:cb){
cout<<i.x<<" "<<i.y<<" "<<i.ind<<"\n";
}
cout<<"cca --------------\n";
for(auto i:cca){
cout<<i.x<<" "<<i.y<<" "<<i.ind<<"\n";
}
cout<<"ccb --------------\n";
for(auto i:ccb){
cout<<i.x<<" "<<i.y<<" "<<i.ind<<"\n";
}
cout<<"end of debug-----\n";
*/
}
int get(vector<Point> &v,long long X, long long Y){
int l=0,r=v.size()-2,ret=v.size()-2;
while(l<r){
int mid = (l+r)/2;
long long y=pa[mid+1].y-pa[mid].y, x=pa[mid+1].x-pa[mid].x;
if(y*X<(-Y)*x){
ret = min(ret, mid);
r=mid-1;
}
else l=mid+1;
}
return ret;
}
long long BestSquad(int X, int Y){
int ica = get(ca,X,Y),icb=get(cb,X,Y),icca=get(cca,X,Y),iccb=get(ccb,X,Y);
vector<Point> at,df;
for(int i=-1;i<=1;i++) if(0<=ica+i&&ica+i<ca.size()) at.push_back(ca[ica+i]);
for(int i=-1;i<=1;i++) if(0<=icca+i&&icca+i<cca.size()) at.push_back(cca[icca+i]);
for(int i=-1;i<=1;i++) if(0<=icb+i&&icb+i<cb.size()) df.push_back(cb[ica+i]);
for(int i=-1;i<=1;i++) if(0<=iccb+i&&iccb+i<ccb.size()) df.push_back(ccb[icca+i]);
long long ret=0;
for(auto i:at){
for(auto j:df){
if(i.ind!=j.ind){
long long t = (i.x+j.x)*X+(i.y+j.y)*Y;
//cout<<"check "<<aa<<" "<<bb<<" "<<t<<"\n";
if(ret<t) ret=t;
}
}
}
return ret;
}
Compilation message
squad.cpp: In function 'long long int BestSquad(int, int)':
squad.cpp:91:43: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=-1;i<=1;i++) if(0<=ica+i&&ica+i<ca.size()) at.push_back(ca[ica+i]);
~~~~~^~~~~~~~~~
squad.cpp:92:45: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=-1;i<=1;i++) if(0<=icca+i&&icca+i<cca.size()) at.push_back(cca[icca+i]);
~~~~~~^~~~~~~~~~~
squad.cpp:93:43: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=-1;i<=1;i++) if(0<=icb+i&&icb+i<cb.size()) df.push_back(cb[ica+i]);
~~~~~^~~~~~~~~~
squad.cpp:94:45: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=-1;i<=1;i++) if(0<=iccb+i&&iccb+i<ccb.size()) df.push_back(ccb[icca+i]);
~~~~~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Incorrect |
6 ms |
512 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Incorrect |
6 ms |
512 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
