#include "squad.h"
#include <algorithm>
#include <map>
using namespace std;
using pii=pair<int,int>;
using ll=long long;
const int N=301010;
vector<pii> tr[2][2][N],stk,tot[2];
//map<pii,int> cnt[2];
pair<pii,int> ind[2][301010];
int n;
ll cr(const pii& a,const pii& b){
return 1LL*a.first*b.second-1LL*a.second*b.first;
}
ll ccw(const pii& a,pii b,pii c){
c.first -= a.first;
c.second -= a.second;
b.first -= a.first;
b.second -= a.second;
return cr(b, c);
//return cr(a,b)+cr(b,c)+cr(c,a);
}
void Init(std::vector<int> A, std::vector<int> D, std::vector<int> P){
n=A.size();
for(int i=0;i<n;i++){
pii q={A[i],P[i]};
//if(cnt[0].count(q))cnt[0][q]=-1;
//else cnt[0][q]=i;
ind[0][i]={q,i};
tot[0].push_back(q);
q={D[i],P[i]};
//if(cnt[1].count(q))cnt[1][q]=-1;
//else cnt[1][q]=i;
ind[1][i]={q,i};
tot[1].push_back(q);
}
sort(ind[0],ind[0]+n);
sort(ind[1],ind[1]+n);
for(int k=0;k<2;k++){
for(int i=0;i<n;i++){
for(int j=ind[k][i].second+1;j<=n;j+=j&(-j)){
tr[k][0][j].push_back(ind[k][i].first);
}
for(int j=n-ind[k][i].second;j<=n;j+=j&(-j)){
tr[k][1][j].push_back(ind[k][i].first);
}
}
for(int t=0;t<2;t++)for(int i=1;i<=n;i++){
stk.clear();
for(auto &x:tr[k][t][i]){
while((int)stk.size()>1){
int sz=stk.size();
auto t=stk[sz-1],tt=stk[sz-2];
if(ccw(tt,x,t)>0)break;
else stk.pop_back();
}
stk.push_back(x);
}
swap(stk,tr[k][t][i]);
}
}
for(int k=0;k<2;k++){
stk.clear();
for(auto &x:tot[k]){
while((int)stk.size()>1){
int sz=stk.size();
auto t=stk[sz-1],tt=stk[sz-2];
if(ccw(tt,x,t)>0)break;
else stk.pop_back();
}
stk.push_back(x);
}
swap(stk,tot[k]);
}
/*for(int k=0;k<2;k++){
for(int i=B;--i;){
tr[k][i].reserve(tr[k][i<<1].size()+tr[k][i<<1|1].size()+1);
merge(tr[k][i<<1].begin(),tr[k][i<<1].end(),tr[k][i<<1|1].begin(),tr[k][i<<1|1].end(),back_inserter(tr[k][i]));
stk.clear();
for(auto &x:tr[k][i]){
while((int)stk.size()>1){
int sz=stk.size();
auto t=stk[sz-1],tt=stk[sz-2];
if(ccw(tt,x,t)>0)break;
else stk.pop_back();
}
stk.push_back(x);
}
tr[k][i]=move(stk);
}
}*/
/* puts("Init");
for(int i=0;i<2;i++){
printf("tree %d: ",i);
for(auto &x:tr[i][1])printf("(%d %d) ",x.first,x.second);
puts("");
}*/
}
ll get(const vector<pii>& V, int X,int Y){
if(V.empty())return -9012345678912345678LL;
int low=0,high=V.size()-1;
while(low!=high){
int mid=low+high>>1;
int dx=V[mid].first-V[mid+1].first;
int dy=V[mid].second-V[mid+1].second;
if(1LL*X*dx+1LL*Y*dy>=0)high=mid;
else low=mid+1;
}
return 1LL*X*V[low].first+1LL*Y*V[low].second;
}
pair<long long,int> get2(int X,int Y, int k){
vector<pii>& V=tot[k];
int low=0,high=V.size()-1;
while(low!=high){
int mid=low+high>>1;
int dx=V[mid].first-V[mid+1].first;
int dy=V[mid].second-V[mid+1].second;
if(1LL*X*dx+1LL*Y*dy>=0)high=mid;
else low=mid+1;
}
bool bad=false;
if(low < (int)V.size() - 1){
int dx=V[low].first-V[low+1].first;
int dy=V[low].second-V[low+1].second;
if(1LL*X*dx+1LL*Y*dy==0)bad=true;
}
//if(cnt[k][V[low]]==-1)bad=true;
int j=lower_bound(ind[k],ind[k]+n,make_pair(V[low],-1))-ind[k];
if(j<n-1&&V[low]==ind[k][j+1].first)bad=true;
return make_pair(1LL*X*V[low].first+1LL*Y*V[low].second,bad?-1:ind[k][j].second);
}
long long BestSquad(int X, int Y){
//printf("Call %d %d\n",X,Y);
long long ans=-9012345678912345678LL;
auto A = get2(X,Y,0);
//printf("A0: %lld %d\n",A.first,A.second);
if(A.second==-1){
return A.first+get(tot[1],X,Y);
}
int i=A.second;
// printf("i0 is %d\n",i);
long long Max=-9012345678912345678LL;
/*for(int l=0+B-1,r=i+B;l/2!=r/2;l/=2,r/=2){
if(!(l&1)){
Max=max(Max,get(tr[1][l+1],X,Y));
}
if(r&1){
Max=max(Max,get(tr[1][r-1],X,Y));
}
}
for(int l=i+B,r=B+B;l/2!=r/2;l/=2,r/=2){
if(!(l&1)){
Max=max(Max,get(tr[1][l+1],X,Y));
}
if(r&1){
Max=max(Max,get(tr[1][r-1],X,Y));
}
}*/
for(int j=i;j;j-=j&(-j))Max=max(Max,get(tr[1][0][j],X,Y));
for(int j=n-1-i;j;j-=j&(-j))Max=max(Max,get(tr[1][1][j],X,Y));
// printf("tree1 max %lld\n",Max);
ans=max(ans,A.first+Max);
A=get2(X,Y,1);
if(A.second==-1){
return A.first+get(tot[0],X,Y);
}
i=A.second;
Max=-9012345678912345678LL;
/*for(int l=0+B-1,r=i+B;l/2!=r/2;l/=2,r/=2){
if(!(l&1)){
Max=max(Max,get(tr[0][l+1],X,Y));
}
if(r&1){
Max=max(Max,get(tr[0][r-1],X,Y));
}
}
for(int l=i+B,r=B+B;l/2!=r/2;l/=2,r/=2){
if(!(l&1)){
Max=max(Max,get(tr[0][l+1],X,Y));
}
if(r&1){
Max=max(Max,get(tr[0][r-1],X,Y));
}
}*/
for(int j=i;j;j-=j&(-j))Max=max(Max,get(tr[0][0][j],X,Y));
for(int j=n-1-i;j;j-=j&(-j))Max=max(Max,get(tr[0][1][j],X,Y));
ans=max(ans,A.first+Max);
return ans;
}
Compilation message
squad.cpp: In function 'll get(const std::vector<std::pair<int, int> >&, int, int)':
squad.cpp:105:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid=low+high>>1;
~~~^~~~~
squad.cpp: In function 'std::pair<long long int, int> get2(int, int, int)':
squad.cpp:118:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid=low+high>>1;
~~~^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
28716 KB |
Output is correct |
| 2 |
Incorrect |
25 ms |
29056 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
23 ms |
28672 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
28716 KB |
Output is correct |
| 2 |
Incorrect |
25 ms |
29056 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
