제출 #148992

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

squad

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

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