Submission #148713

#	Time	Username	Problem	Language	Result	Execution time	Memory
148713		강력한 한방 필살기 (#200)	Organizing the Best Squad (FXCUP4_squad)	C++17	0 / 100	3100 ms	49784 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];

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 (stderr)

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

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