oj.uz

Submission #149749

# Submission time Handle Problem Language Result Execution time Memory
149749 2019-09-01T07:05:24 Z =SUM(D1:D9)(#3629, ydk1104, stet_stet, Hyperbolic) Organizing the Best Squad (FXCUP4_squad) C++17
19 / 100
 445 ms 29144 KB 
#include "squad.h"
#include <algorithm>
#include <map>

struct str{
	int x0;
	int y0;
	int z0;
	int index;
}x[300010];
std::vector<str> St1,St2;

bool cmp1(str A, str B)
{
	if(A.z0==B.z0) return A.x0>B.x0;
	return A.z0<B.z0;
}
bool cmp2(str A, str B)
{
	if(A.z0==B.z0) return A.y0>B.y0;
	return A.z0<B.z0;
}

double xCoor(str A, str B)
{
	return (double)(B.y0-A.y0)/(A.x0-B.x0);
}

std::map<int, std::pair<int,int> > M1,M2;
std::vector<str> save1,save2;

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++) x[i]={A[i],D[i],P[i],i};
	std::sort(x,x+N,cmp1);
	
	int n;
	str B,C;
	St1.push_back({x[0].z0,x[0].x0,x[0].index});
	for(int i=1;i<N;i++)
	{
		if(St1[St1.size()-1].x0==x[i].z0)
		{
			if(M1[x[i].z0].first==0) M1[x[i].z0] = std::make_pair(x[i].x0,x[i].index);
			continue;
		}
		
		while(St1.size()>=2)
		{
			n = St1.size();
			B = St1[n-1];
			C = St1[n-2];
			
			if(xCoor(B,C)<=xCoor({x[i].z0,x[i].x0,x[i].index},B)) break;
			else St1.pop_back();
		}
		St1.push_back({x[i].z0,x[i].x0,x[i].index});
		u:;
	}
	
	std::sort(x,x+N,cmp2);
	
	St2.push_back({x[0].z0,x[0].y0,x[0].index});
	for(int i=1;i<N;i++)
	{
		if(St2[St2.size()-1].x0==x[i].z0)
		{
			if(M2[x[i].z0].first==0) M2[x[i].z0] = std::make_pair(x[i].y0,x[i].index);
			continue;
		}
		
		while(St2.size()>=2)
		{
			n = St2.size();
			B = St2[n-1];
			C = St2[n-2];
			
			if(xCoor(B,C)<=xCoor({x[i].z0,x[i].y0,x[i].index},B)) break;
			else St2.pop_back();
		}
		St2.push_back({x[i].z0,x[i].y0,x[i].index});
		v:;
	}
}

int getIndex1(double k)
{
	int min = 1, max = St1.size()-1, ans = 0;
	while(min<=max)
	{
		int h = (min+max)/2;
		if(xCoor(St1[h-1],St1[h])<=k)
		{
			ans = h;
			min = h+1;
		}
		else max = h-1;
	}
	return ans;
}

int getIndex2(double k)
{
	int min = 1, max = St2.size()-1, ans = 0;
	while(min<=max)
	{
		int h = (min+max)/2;
		if(xCoor(St2[h-1],St2[h])<=k)
		{
			ans = h;
			min = h+1;
		}
		else max = h-1;
	}
	return ans;
}

long long BestSquad(int X, int Y){
	int n1 = getIndex1((double)Y/X);
	int n2 = getIndex2((double)Y/X);
	long long int ans = 0;
	
	save1.clear(),save2.clear();
	for(int i=n1-1;i<=n1+1;i++) if(0<=i&&i<St1.size()) save1.push_back(St1[i]);
	if(M1[St1[n1].x0].first!=0) save1.push_back({St1[n1].x0,M1[St1[n1].x0].first,M1[St1[n1].x0].second});
	for(int i=n2-1;i<=n2+1;i++) if(0<=i&&i<St2.size()) save2.push_back(St2[i]);
	if(M2[St2[n2].x0].first!=0) save2.push_back({St2[n2].x0,M2[St2[n2].x0].first,M2[St2[n2].x0].second});
	
	for(int i=0;i<save1.size();i++)
	{
		for(int j=0;j<save2.size();j++)
		{
			if(save1[i].z0!=save2[j].z0)
			{
				long long int S = (long long int)X*(save1[i].y0+save2[j].y0)+(long long int)Y*(save1[i].x0+save2[j].x0);
				ans = ans>S?ans:S;
			}
		}
	}
	
	return ans;
}

Compilation message

squad.cpp: In function 'void Init(std::vector<int>, std::vector<int>, std::vector<int>)':
squad.cpp:58:3: warning: label 'u' defined but not used [-Wunused-label]
   u:;
   ^
squad.cpp:82:3: warning: label 'v' defined but not used [-Wunused-label]
   v:;
   ^
squad.cpp: In function 'long long int BestSquad(int, int)':
squad.cpp:124:40: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=n1-1;i<=n1+1;i++) if(0<=i&&i<St1.size()) save1.push_back(St1[i]);
                                       ~^~~~~~~~~~~
squad.cpp:126:40: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=n2-1;i<=n2+1;i++) if(0<=i&&i<St2.size()) save2.push_back(St2[i]);
                                       ~^~~~~~~~~~~
squad.cpp:129:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<save1.size();i++)
              ~^~~~~~~~~~~~~
squad.cpp:131:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0;j<save2.size();j++)
               ~^~~~~~~~~~~~~

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 432 KB Output is correct
2 Correct 6 ms 384 KB Output is correct
3 Correct 254 ms 12152 KB Output is correct
4 Correct 251 ms 12152 KB Output is correct
5 Correct 23 ms 2296 KB Output is correct
6 Correct 254 ms 29144 KB Output is correct
7 Correct 257 ms 29140 KB Output is correct
8 Correct 254 ms 29140 KB Output is correct

Subtask #2
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 9 ms 384 KB Output is correct
3 Correct 440 ms 20452 KB Output is correct
4 Incorrect 445 ms 20452 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 432 KB Output is correct
2 Correct 6 ms 384 KB Output is correct
3 Correct 254 ms 12152 KB Output is correct
4 Correct 251 ms 12152 KB Output is correct
5 Correct 23 ms 2296 KB Output is correct
6 Correct 254 ms 29144 KB Output is correct
7 Correct 257 ms 29140 KB Output is correct
8 Correct 254 ms 29140 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 9 ms 384 KB Output is correct
11 Correct 440 ms 20452 KB Output is correct
12 Incorrect 445 ms 20452 KB Output isn't correct
13 Halted 0 ms 0 KB -