oj.uz

Submission #149284

# Submission time Handle Problem Language Result Execution time Memory
149284 2019-09-01T06:08:03 Z =SUM(D1:D9)(#3629, ydk1104, stet_stet, Hyperbolic) Organizing the Best Squad (FXCUP4_squad) C++17
0 / 100
 167 ms 8700 KB 
#include "squad.h"
#include <algorithm>

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

bool cmp(str A, str B)
{
	return A.z0<B.z0;
}

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

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]};
	std::sort(x,x+N,cmp);
	
	int n;
	str B,C;
	for(int i=0;i<N;i++)
	{
		while(St1.size()>=1)
		{
			n = St1.size();
			if(St1[n-1].x0==x[i].z0)
			{
				if(St1[n-1].y0<=x[i].x0) St1.pop_back();
				else goto u;
			}
			else break;
		}
		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,i},B)) break;
			else St1.pop_back();
		}
		St1.push_back({x[i].z0,x[i].x0,i});
		u:;
	}
	
	for(int i=0;i<N;i++)
	{
		while(St2.size()>=1)
		{
			n = St2.size();
			if(St2[n-1].x0==x[i].z0)
			{
				if(St2[n-1].y0<=x[i].y0) St2.pop_back();
				else goto v;
			}
			else break;
		}
		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,i},B)) break;
			else St2.pop_back();
		}
		St2.push_back({x[i].z0,x[i].y0,i});
		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;
	for(int i=n1-1;i<=n1+1;i++)
	{
		for(int j=n2-1;j<=n2+1;j++)
		{
			if(0<=i&&i<St1.size()&&0<=j&&j<St2.size())
			{
				if(St1[i].z0!=St2[j].z0)
				{
					long long int S = (long long int)X*(St1[i].y0+St2[j].y0)+(long long int)Y*(St1[i].x0+St2[j].x0);
					ans = ans>S?ans:S;
				}
			}
		}
	}
	return ans;
}

Compilation message

squad.cpp: In function 'long long int BestSquad(int, int)':
squad.cpp:120:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(0<=i&&i<St1.size()&&0<=j&&j<St2.size())
             ~^~~~~~~~~~~
squad.cpp:120:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(0<=i&&i<St1.size()&&0<=j&&j<St2.size())
                                 ~^~~~~~~~~~~

Subtask #1
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 7 ms 256 KB Output is correct
3 Runtime error 167 ms 8696 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #2
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 9 ms 640 KB Output is correct
3 Runtime error 146 ms 8700 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #3
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 7 ms 256 KB Output is correct
3 Runtime error 167 ms 8696 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -