제출 #148835

#제출 시각아이디문제언어결과실행 시간메모리
148835강력한 한방 필살기 (#200)최적의 팀 구성 (FXCUP4_squad)C++17
47 / 100
3109 ms187984 KiB
#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]; 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,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){ 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; ind[0][i]={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; ind[1][i]={q,i}; } sort(ind[0],ind[0]+n); sort(ind[1],ind[1]+n); for(int k=0;k<2;k++){ for(int i=B;--i;){ 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]=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(const vector<pii>& V, int X,int Y, int k){ 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){ 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(tr[0][1], X,Y,0); //printf("A0: %lld %d\n",A.first,A.second); if(A.second==-1){ return A.first+get(tr[1][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)); } } // printf("tree1 max %lld\n",Max); ans=max(ans,A.first+Max); A=get2(tr[1][1],X,Y,1); if(A.second==-1){ return A.first+get(tr[0][1],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)); } } ans=max(ans,A.first+Max); return ans; }

컴파일 시 표준 에러 (stderr) 메시지

squad.cpp: In function 'll get(const std::vector<std::pair<int, int> >&, int, int)':
squad.cpp:63:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid=low+high>>1;
           ~~~^~~~~
squad.cpp: In function 'std::pair<long long int, int> get2(const std::vector<std::pair<int, int> >&, int, int, int)':
squad.cpp:76:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid=low+high>>1;
           ~~~^~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...