oj.uz

Submission #148772

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

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){
		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 = 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;
}

Compilation message

squad.cpp: In function 'll get(const std::vector<std::pair<int, int> >&, int, int)':
squad.cpp:58: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:71: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 43 ms 49656 KB Output is correct
2 Correct 52 ms 49912 KB Output is correct
3 Correct 1505 ms 143632 KB Output is correct
4 Correct 1457 ms 143608 KB Output is correct
5 Correct 95 ms 60784 KB Output is correct
6 Correct 1397 ms 218572 KB Output is correct
7 Correct 1378 ms 218584 KB Output is correct
8 Correct 1347 ms 218576 KB Output is correct

Subtask #2
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 49528 KB Output is correct
2 Correct 56 ms 50304 KB Output is correct
3 Correct 1862 ms 142392 KB Output is correct
4 Correct 1859 ms 142260 KB Output is correct
5 Correct 121 ms 55032 KB Output is correct
6 Execution timed out 3108 ms 178576 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 49656 KB Output is correct
2 Correct 52 ms 49912 KB Output is correct
3 Correct 1505 ms 143632 KB Output is correct
4 Correct 1457 ms 143608 KB Output is correct
5 Correct 95 ms 60784 KB Output is correct
6 Correct 1397 ms 218572 KB Output is correct
7 Correct 1378 ms 218584 KB Output is correct
8 Correct 1347 ms 218576 KB Output is correct
9 Correct 48 ms 49528 KB Output is correct
10 Correct 56 ms 50304 KB Output is correct
11 Correct 1862 ms 142392 KB Output is correct
12 Correct 1859 ms 142260 KB Output is correct
13 Correct 121 ms 55032 KB Output is correct
14 Execution timed out 3108 ms 178576 KB Time limit exceeded
15 Halted 0 ms 0 KB -