제출 #148835

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
148835		강력한 한방 필살기 (#200)	최적의 팀 구성 (FXCUP4_squad)	C++17	47 / 100	3109 ms	187984 KiB

squad

#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;
           ~~~^~~~~

• Subtask 1: 19 / 19
• Subtask 2: 28 / 28
• Subtask 3: 0 / 53