oj.uz

Submission #148835

# Submission time Handle Problem Language Result Execution time Memory
148835 2019-09-01T05:12:59 Z 강력한 한방 필살기(#3595, gs14004, kriii, OnionPringles) Organizing the Best Squad (FXCUP4_squad) C++17
47 / 100
 3000 ms 187984 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];
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;
}

Compilation message

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.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 49536 KB Output is correct
2 Correct 45 ms 49784 KB Output is correct
3 Correct 462 ms 113144 KB Output is correct
4 Correct 473 ms 113144 KB Output is correct
5 Correct 79 ms 58736 KB Output is correct
6 Correct 641 ms 187984 KB Output is correct
7 Correct 641 ms 187980 KB Output is correct
8 Correct 632 ms 187952 KB Output is correct

Subtask #2
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 49656 KB Output is correct
2 Correct 48 ms 50168 KB Output is correct
3 Correct 839 ms 111668 KB Output is correct
4 Correct 848 ms 111796 KB Output is correct
5 Correct 97 ms 53752 KB Output is correct
6 Correct 2207 ms 148240 KB Output is correct
7 Correct 2128 ms 148236 KB Output is correct
8 Correct 2231 ms 148336 KB Output is correct

Subtask #3
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 49536 KB Output is correct
2 Correct 45 ms 49784 KB Output is correct
3 Correct 462 ms 113144 KB Output is correct
4 Correct 473 ms 113144 KB Output is correct
5 Correct 79 ms 58736 KB Output is correct
6 Correct 641 ms 187984 KB Output is correct
7 Correct 641 ms 187980 KB Output is correct
8 Correct 632 ms 187952 KB Output is correct
9 Correct 50 ms 49656 KB Output is correct
10 Correct 48 ms 50168 KB Output is correct
11 Correct 839 ms 111668 KB Output is correct
12 Correct 848 ms 111796 KB Output is correct
13 Correct 97 ms 53752 KB Output is correct
14 Correct 2207 ms 148240 KB Output is correct
15 Correct 2128 ms 148236 KB Output is correct
16 Correct 2231 ms 148336 KB Output is correct
17 Correct 180 ms 52088 KB Output is correct
18 Correct 54 ms 50304 KB Output is correct
19 Correct 949 ms 115380 KB Output is correct
20 Correct 929 ms 115380 KB Output is correct
21 Correct 168 ms 55928 KB Output is correct
22 Execution timed out 3109 ms 187980 KB Time limit exceeded
23 Halted 0 ms 0 KB -