oj.uz

Submission #148655

# Submission time Handle Problem Language Result Execution time Memory
148655 2019-09-01T04:52:40 Z 강력한 한방 필살기(#3595, gs14004, kriii, OnionPringles) Organizing the Best Squad (FXCUP4_squad) C++17
19 / 100
 3000 ms 218572 KB 
#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;){
			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("");
	}*/
}

pair<long long,int> get(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){
		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;
	auto A = get(tr[0][1], X,Y,0);
	//printf("A0: %lld %d\n",A.first,A.second);
	if(A.second==-1){
//		puts("multiple");
		auto B = get(tr[1][1],X,Y,1);
//		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;
	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,1);
			Max=max(Max,C.first);
		}
		if(r&1){
			auto C=get(tr[1][r-1],X,Y,1);
			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,1);
			Max=max(Max,C.first);
		}
		if(r&1){
			auto C=get(tr[1][r-1],X,Y,1);
			Max=max(Max,C.first);
		}
	}
//	printf("tree1 max %lld\n",Max);
	ans=max(ans,A.first+Max);
	
	A=get(tr[1][1],X,Y,1);
	if(A.second==-1){
		auto B=get(tr[0][1],X,Y,0);
		return A.first+B.first;
	}
	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)){
			auto C=get(tr[0][l+1],X,Y,0);
			Max=max(Max,C.first);
		}
		if(r&1){
			auto C=get(tr[0][r-1],X,Y,0);
			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,0);
			Max=max(Max,C.first);
		}
		if(r&1){
			auto C=get(tr[0][r-1],X,Y,0);
			Max=max(Max,C.first);
		}
	}
	ans=max(ans,A.first+Max);
	
	return ans;
}

Compilation message

squad.cpp: In function 'std::pair<long long int, int> get(const std::vector<std::pair<int, int> >&, int, int, int)':
squad.cpp:58:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid=low+high>>1;
           ~~~^~~~~

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 49664 KB Output is correct
2 Correct 50 ms 49920 KB Output is correct
3 Correct 1455 ms 143608 KB Output is correct
4 Correct 1533 ms 143608 KB Output is correct
5 Correct 98 ms 60784 KB Output is correct
6 Correct 1396 ms 218572 KB Output is correct
7 Correct 1391 ms 218572 KB Output is correct
8 Correct 1379 ms 218500 KB Output is correct

Subtask #2
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 49664 KB Output is correct
2 Correct 56 ms 50424 KB Output is correct
3 Execution timed out 3104 ms 141260 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 49664 KB Output is correct
2 Correct 50 ms 49920 KB Output is correct
3 Correct 1455 ms 143608 KB Output is correct
4 Correct 1533 ms 143608 KB Output is correct
5 Correct 98 ms 60784 KB Output is correct
6 Correct 1396 ms 218572 KB Output is correct
7 Correct 1391 ms 218572 KB Output is correct
8 Correct 1379 ms 218500 KB Output is correct
9 Correct 43 ms 49664 KB Output is correct
10 Correct 56 ms 50424 KB Output is correct
11 Execution timed out 3104 ms 141260 KB Time limit exceeded
12 Halted 0 ms 0 KB -