oj.uz

Submission #149020

# Submission time Handle Problem Language Result Execution time Memory
149020 2019-09-01T05:35:19 Z 강력한 한방 필살기(#3595, gs14004, kriii, OnionPringles) Organizing the Best Squad (FXCUP4_squad) C++17
19 / 100
 3000 ms 169616 KB 
#include "squad.h"
#include <algorithm>
#include <map>
using namespace std;
using pii=pair<int,int>;
using ll=long long;
const int N=301010;
vector<pii> tr[2][2][N],stk,tot[2];
//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++){
		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};
		tot[0].push_back(q);
		q={D[i],P[i]};
		//if(cnt[1].count(q))cnt[1][q]=-1;
		//else cnt[1][q]=i;
		ind[1][i]={q,i};
		tot[1].push_back(q);
	}
	sort(ind[0],ind[0]+n);
	sort(ind[1],ind[1]+n);
	sort(tot[0].begin(),tot[0].end());
	sort(tot[1].begin(),tot[1].end());
	for(int k=0;k<2;k++){
		for(int i=0;i<n;i++){
			for(int j=ind[k][i].second+1;j<=n;j+=j&(-j)){
				tr[k][0][j].push_back(ind[k][i].first);
			}
			for(int j=n-ind[k][i].second;j<=n;j+=j&(-j)){
				tr[k][1][j].push_back(ind[k][i].first);
			}
		}
		for(int t=0;t<2;t++)for(int i=1;i<=n;i++){	
			stk.clear();
			for(auto &x:tr[k][t][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][t][i]=stk;
		}
	}
	for(int k=0;k<2;k++){
		stk.clear();
		for(auto &x:tot[k]){
			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);
		}
		tot[k]=stk;
	}
	/*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(int X,int Y, int k){
	vector<pii>& V=tot[k];
	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(X,Y,0);
	//printf("A0: %lld %d\n",A.first,A.second);
	if(A.second==-1){
		return A.first+get(tot[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));
		}
	}*/
	
	for(int j=i;j;j-=j&(-j))Max=max(Max,get(tr[1][0][j],X,Y));
	for(int j=n-1-i;j;j-=j&(-j))Max=max(Max,get(tr[1][1][j],X,Y));
	
	
//	printf("tree1 max %lld\n",Max);
	ans=max(ans,A.first+Max);
	
	A=get2(X,Y,1);
	if(A.second==-1){
		return A.first+get(tot[0],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));
		}
	}*/
	
	for(int j=i;j;j-=j&(-j))Max=max(Max,get(tr[0][0][j],X,Y));
	for(int j=n-1-i;j;j-=j&(-j))Max=max(Max,get(tr[0][1][j],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:107:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid=low+high>>1;
           ~~~^~~~~
squad.cpp: In function 'std::pair<long long int, int> get2(int, int, int)':
squad.cpp:120: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 23 ms 28672 KB Output is correct
2 Correct 26 ms 28928 KB Output is correct
3 Correct 1804 ms 163024 KB Output is correct
4 Correct 1553 ms 163016 KB Output is correct
5 Correct 70 ms 36516 KB Output is correct
6 Correct 1745 ms 167248 KB Output is correct
7 Correct 1415 ms 167380 KB Output is correct
8 Correct 1724 ms 167496 KB Output is correct

Subtask #2
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 28672 KB Output is correct
2 Correct 33 ms 29440 KB Output is correct
3 Correct 2094 ms 165260 KB Output is correct
4 Correct 2073 ms 165268 KB Output is correct
5 Correct 91 ms 33528 KB Output is correct
6 Execution timed out 3108 ms 169616 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 28672 KB Output is correct
2 Correct 26 ms 28928 KB Output is correct
3 Correct 1804 ms 163024 KB Output is correct
4 Correct 1553 ms 163016 KB Output is correct
5 Correct 70 ms 36516 KB Output is correct
6 Correct 1745 ms 167248 KB Output is correct
7 Correct 1415 ms 167380 KB Output is correct
8 Correct 1724 ms 167496 KB Output is correct
9 Correct 25 ms 28672 KB Output is correct
10 Correct 33 ms 29440 KB Output is correct
11 Correct 2094 ms 165260 KB Output is correct
12 Correct 2073 ms 165268 KB Output is correct
13 Correct 91 ms 33528 KB Output is correct
14 Execution timed out 3108 ms 169616 KB Time limit exceeded
15 Halted 0 ms 0 KB -