Submission #149771

#	Time	Username	Problem	Language	Result	Execution time	Memory
149771		Torat (#200)	Organizing the Best Squad (FXCUP4_squad)	C++17	0 / 100	70 ms	113144 KiB

squad

#include "squad.h"
#include <bits/stdc++.h>
#define F first
#define S second

using namespace std;

const int N=3e5+5;

bool qu;
struct line
{
	double m,b;
	int id;
	mutable function<const line*()> succ;
	bool operator<(const line &rhs) const
	{
		if (!qu)
		return (m<rhs.m);
		const line *s=succ();
		if (!s)
		return 0;
		return b-s->b<rhs.m*(s->m-m);
	}
};
struct hull:public multiset<line>
{
	bool bad(iterator y)
	{
		auto z=next(y);
		if (y==begin())
		{
			if (z==end())
			return 0;
			return (y->m==z->m && y->b<=z->b);
		}
		auto x=prev(y);
		if (z==end())
		return (y->m==x->m && y->b<=x->b);
		return 1.0*(x->b-y->b)*(z->m-y->m)>=1.0*(y->b-z->b)*(y->m-x->m);
	}
	void add(double m,double b,int id)
	{
		auto it=insert({m,b,id});
		it->succ=[=] { return (next(it)==end())? 0:&*next(it); };
		if (bad(it))
		{
			erase(it);
			return;
		}
		while (next(it)!=end() && bad(next(it)))
		erase(next(it));
		while (it!=begin() && bad(prev(it)))
		erase(prev(it));
	}
	pair<double,int> eval(double x)
	{
		qu=1;
		line l=*lower_bound((line){x,0});
		qu=0;
		return {l.m*x+l.b,l.id};
	}
};

hull tr[2][4*N];
vector<int> a[2],p;
int n;

void build(int id,int node,int l,int r)
{
	if(l==r)
	{
		// a[id]*x+p*y
		// x*(a[id]+p*y/x)
		tr[id][node].add(p[l],a[id][l],l);
		return;
	}
	int mid=(l+r)/2;
	build(id,node*2,l,mid);
	build(id,node*2+1,mid+1,r);
	for(int i=l;i<=r;i++)
		tr[id][node].add(p[i],a[id][i],i);
}

pair<double,int> query(int id,int node,int l,int r,double x,long long y)
{
	if(l==r) {/*cout << l << endl;*/ return {-1,-1};}
	pair<double,int> ll=tr[id][node*2].eval(x),rr=tr[id][node*2+1].eval(x);
	int mid=(l+r)/2;
	if(ll.F+1e-9>rr.F)
		return max({round(rr.F*y),rr.S},query(id,node*2,l,mid,x,y));
	return max({round(ll.F*y),ll.S},query(id,node*2+1,mid+1,r,x,y));
}

void Init(std::vector<int> A, std::vector<int> D, std::vector<int> P){
	n = A.size();
	a[0]=A; a[1]=D; p=P;
	build(0,1,0,n-1);
	build(1,1,0,n-1);
}

long long BestSquad(int X, int Y){
	pair<double,int> x=tr[0][1].eval((double)Y/X),
		y=tr[1][1].eval((double)Y/X);
	if(x.S!=y.S)
	{
		//cout << x.S << " " << y.S << endl;
		return round(x.F*X)+round(y.F*X);
	}
	pair<long long,int> x2=query(0,1,0,n-1,(double)Y/X,X),
		y2=query(1,1,0,n-1,(double)Y/X,X);
	//cout << x.S << " " << y.S << " " << x2.S << " " << y2.S << endl;
	return max(round(x.F*X)+y2.F,x2.F+round(y.F*X));
}

• Subtask 1: 0 / 19
• Subtask 2: 0 / 28
• Subtask 3: 0 / 53