oj.uz

Submission #148850

# Submission time Handle Problem Language Result Execution time Memory
148850 2019-09-01T05:15:23 Z 강력한 한방 필살기(#3595, gs14004, kriii, OnionPringles) Organizing the Best Squad (FXCUP4_squad) C++17
47 / 100
 3000 ms 189016 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,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++){
		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;){
			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(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:69: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:82: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 87 ms 49664 KB Output is correct
2 Correct 91 ms 49580 KB Output is correct
3 Correct 452 ms 108024 KB Output is correct
4 Correct 477 ms 108024 KB Output is correct
5 Correct 133 ms 58868 KB Output is correct
6 Correct 654 ms 189012 KB Output is correct
7 Correct 686 ms 189016 KB Output is correct
8 Correct 657 ms 188988 KB Output is correct

Subtask #2
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 49656 KB Output is correct
2 Correct 93 ms 50040 KB Output is correct
3 Correct 843 ms 106932 KB Output is correct
4 Correct 834 ms 106932 KB Output is correct
5 Correct 144 ms 53624 KB Output is correct
6 Correct 2254 ms 143700 KB Output is correct
7 Correct 2474 ms 143740 KB Output is correct
8 Correct 2312 ms 143740 KB Output is correct

Subtask #3
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 49664 KB Output is correct
2 Correct 91 ms 49580 KB Output is correct
3 Correct 452 ms 108024 KB Output is correct
4 Correct 477 ms 108024 KB Output is correct
5 Correct 133 ms 58868 KB Output is correct
6 Correct 654 ms 189012 KB Output is correct
7 Correct 686 ms 189016 KB Output is correct
8 Correct 657 ms 188988 KB Output is correct
9 Correct 92 ms 49656 KB Output is correct
10 Correct 93 ms 50040 KB Output is correct
11 Correct 843 ms 106932 KB Output is correct
12 Correct 834 ms 106932 KB Output is correct
13 Correct 144 ms 53624 KB Output is correct
14 Correct 2254 ms 143700 KB Output is correct
15 Correct 2474 ms 143740 KB Output is correct
16 Correct 2312 ms 143740 KB Output is correct
17 Correct 214 ms 52088 KB Output is correct
18 Correct 97 ms 50296 KB Output is correct
19 Correct 916 ms 110136 KB Output is correct
20 Correct 912 ms 110388 KB Output is correct
21 Correct 206 ms 56056 KB Output is correct
22 Execution timed out 3109 ms 188860 KB Time limit exceeded
23 Halted 0 ms 0 KB -