#include "squad.h"
#include <algorithm>
#include <map>
using namespace std;
using pii=pair<int,int>;
using ll=long long;
const int B=1<<19;
vector<pii > tr[2][B<<1],stk;
map<pii,int> cnt[2];
ll cr(const pii& a,const pii& b){
return 1LL*a.first*b.second-1LL*a.second*b.first;
}
ll ccw(const pii& a,const pii& b,const pii& 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){
int n=A.size();
for(int i=0;i<n;i++){
tr[0][B+i].emplace_back(A[i],P[i]);
pii q={A[i],P[i]};
if(cnt[0].count(q))cnt[0][q]=-1;
else cnt[0][q]=i;
tr[1][B+i].emplace_back(D[i],P[i]);
q={D[i],P[i]};
if(cnt[1].count(q))cnt[1][q]=-1;
else cnt[1][q]=i;
}
for(int k=0;k<2;k++){
for(int i=B;--i;){
stk.clear();
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(stk));
for(auto &x:stk){
while((int)tr[k][i].size()>1){
int sz=tr[k][i].size();
auto t=tr[k][i][sz-1],tt=tr[k][i][sz-2];
if(ccw(tt,x,t)>0)break;
else stk.pop_back();
}
tr[k][i].push_back(x);
}
}
}
/* 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("");
}*/
}
int K;
pair<long long,int> get(const vector<pii>& V, int X,int Y){
if(V.empty())return {-9012345678912345678LL,0};
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){
if(1LL*X*V[low].first+1LL*Y*V[low].second == 1LL*X*V[low+1].first+1LL*Y*V[low+1].second)bad=true;
}
if(cnt[K][V[low]]==-1)bad=true;
return make_pair(1LL*X*V[low].first+1LL*Y*V[low].second,bad?-1:cnt[K][V[low]]);
}
long long BestSquad(int X, int Y){
//printf("Call %d %d\n",X,Y);
long long ans=-9012345678912345678LL;
K=0;
auto A = get(tr[0][1], X,Y);
//printf("A0: %lld %d\n",A.first,A.second);
if(A.second==-1){
// puts("multiple");
K=1;
auto B = get(tr[1][1],X,Y);
// printf("B1: %lld %d\n",B.first,B.second);
return A.first+B.first;
}
int i=A.second;
// printf("i0 is %d\n",i);
long long Max=-9012345678912345678LL;
K=1;
for(int l=0+B-1,r=i+B;l/2!=r/2;l/=2,r/=2){
if(!(l&1)){
auto C=get(tr[1][l+1],X,Y);
Max=max(Max,C.first);
}
if(r&1){
auto C=get(tr[1][r-1],X,Y);
Max=max(Max,C.first);
}
}
for(int l=i+B,r=B+B;l/2!=r/2;l/=2,r/=2){
if(!(l&1)){
auto C=get(tr[1][l+1],X,Y);
Max=max(Max,C.first);
}
if(r&1){
auto C=get(tr[1][r-1],X,Y);
Max=max(Max,C.first);
}
}
// printf("tree1 max %lld\n",Max);
ans=max(ans,A.first+Max);
A=get(tr[1][1],X,Y);
if(A.second==-1){
K=0;
auto B=get(tr[0][1],X,Y);
return A.first+B.first;
}
i=A.second;
Max=-9012345678912345678LL;
K=0;
for(int l=0+B-1,r=i+B;l/2!=r/2;l/=2,r/=2){
if(!(l&1)){
auto C=get(tr[0][l+1],X,Y);
Max=max(Max,C.first);
}
if(r&1){
auto C=get(tr[0][r-1],X,Y);
Max=max(Max,C.first);
}
}
for(int l=i+B,r=B+B;l/2!=r/2;l/=2,r/=2){
if(!(l&1)){
auto C=get(tr[0][l+1],X,Y);
Max=max(Max,C.first);
}
if(r&1){
auto C=get(tr[0][r-1],X,Y);
Max=max(Max,C.first);
}
}
ans=max(ans,A.first+Max);
return ans;
}
Compilation message
squad.cpp: In function 'std::pair<long long int, int> get(const std::vector<std::pair<int, int> >&, int, int)':
squad.cpp:59:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid=low+high>>1;
~~~^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
37 ms |
49664 KB |
Output is correct |
| 2 |
Execution timed out |
3100 ms |
49784 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3099 ms |
49664 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
37 ms |
49664 KB |
Output is correct |
| 2 |
Execution timed out |
3100 ms |
49784 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
