제출 #148992

#제출 시각아이디문제언어결과실행 시간메모리
148992강력한 한방 필살기 (#200)최적의 팀 구성 (FXCUP4_squad)C++17
0 / 100
25 ms29056 KiB
#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; }

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

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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...