oj.uz

Submission #148883

# Submission time Handle Problem Language Result Execution time Memory
148883 2019-09-01T05:18:47 Z 강력한 한방 필살기(#3595, gs14004, kriii, OnionPringles) Organizing the Best Squad (FXCUP4_squad) C++17
47 / 100
 3000 ms 188988 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=n+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=n+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 92 ms 49664 KB Output is correct
2 Correct 90 ms 49792 KB Output is correct
3 Correct 479 ms 108024 KB Output is correct
4 Correct 477 ms 108024 KB Output is correct
5 Correct 121 ms 58868 KB Output is correct
6 Correct 638 ms 188988 KB Output is correct
7 Correct 624 ms 188908 KB Output is correct
8 Correct 618 ms 188732 KB Output is correct

Subtask #2
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 49392 KB Output is correct
2 Correct 88 ms 50040 KB Output is correct
3 Correct 881 ms 106932 KB Output is correct
4 Correct 891 ms 106932 KB Output is correct
5 Correct 141 ms 53624 KB Output is correct
6 Correct 2735 ms 143660 KB Output is correct
7 Correct 2481 ms 143612 KB Output is correct
8 Correct 2658 ms 143612 KB Output is correct

Subtask #3
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 49664 KB Output is correct
2 Correct 90 ms 49792 KB Output is correct
3 Correct 479 ms 108024 KB Output is correct
4 Correct 477 ms 108024 KB Output is correct
5 Correct 121 ms 58868 KB Output is correct
6 Correct 638 ms 188988 KB Output is correct
7 Correct 624 ms 188908 KB Output is correct
8 Correct 618 ms 188732 KB Output is correct
9 Correct 90 ms 49392 KB Output is correct
10 Correct 88 ms 50040 KB Output is correct
11 Correct 881 ms 106932 KB Output is correct
12 Correct 891 ms 106932 KB Output is correct
13 Correct 141 ms 53624 KB Output is correct
14 Correct 2735 ms 143660 KB Output is correct
15 Correct 2481 ms 143612 KB Output is correct
16 Correct 2658 ms 143612 KB Output is correct
17 Correct 175 ms 51908 KB Output is correct
18 Correct 105 ms 50296 KB Output is correct
19 Correct 1033 ms 110388 KB Output is correct
20 Correct 994 ms 110388 KB Output is correct
21 Correct 212 ms 55928 KB Output is correct
22 Execution timed out 3108 ms 188988 KB Time limit exceeded
23 Halted 0 ms 0 KB -