oj.uz

Submission #149443

# Submission time Handle Problem Language Result Execution time Memory
149443 2019-09-01T06:29:44 Z =SUM(D1:D9)(#3629, ydk1104, stet_stet, Hyperbolic) Organizing the Best Squad (FXCUP4_squad) C++17
19 / 100
 432 ms 23780 KB 
#include "squad.h"
#include <algorithm>

struct str{
	int x0;
	int y0;
	int z0;
}x[300010];
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 if(St1[n-1].y0==x[i].x0)
				{
					St1.push_back({x[i].z0,x[i].x0,i});
					goto u;
				}
				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 if(St2[n-1].y0==x[i].x0)
				{
					St2.push_back({x[i].z0,x[i].y0,i});
					goto v;
				}
				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:130:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(0<=i&&i<St1.size()&&0<=j&&j<St2.size())
             ~^~~~~~~~~~~
squad.cpp:130:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(0<=i&&i<St1.size()&&0<=j&&j<St2.size())
                                 ~^~~~~~~~~~~

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 384 KB Output is correct
2 Correct 6 ms 384 KB Output is correct
3 Correct 245 ms 10872 KB Output is correct
4 Correct 226 ms 10872 KB Output is correct
5 Correct 19 ms 1916 KB Output is correct
6 Correct 230 ms 23676 KB Output is correct
7 Correct 227 ms 23652 KB Output is correct
8 Correct 227 ms 23780 KB Output is correct

Subtask #2
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 9 ms 640 KB Output is correct
3 Correct 420 ms 17256 KB Output is correct
4 Incorrect 432 ms 17256 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 384 KB Output is correct
2 Correct 6 ms 384 KB Output is correct
3 Correct 245 ms 10872 KB Output is correct
4 Correct 226 ms 10872 KB Output is correct
5 Correct 19 ms 1916 KB Output is correct
6 Correct 230 ms 23676 KB Output is correct
7 Correct 227 ms 23652 KB Output is correct
8 Correct 227 ms 23780 KB Output is correct
9 Correct 5 ms 256 KB Output is correct
10 Correct 9 ms 640 KB Output is correct
11 Correct 420 ms 17256 KB Output is correct
12 Incorrect 432 ms 17256 KB Output isn't correct
13 Halted 0 ms 0 KB -