oj.uz

Submission #149855

# Submission time Handle Problem Language Result Execution time Memory
149855 2019-09-01T07:17:30 Z Torat(#3726, Osama_Alkhodairy, mohammedehab2002, mahmoudbadawy) Organizing the Best Squad (FXCUP4_squad) C++17
0 / 100
 3000 ms 524288 KB 
#include "squad.h"
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define F first
#define S second

using namespace std;

const int N=3e5+5;

bool qu;
struct line
{
	long 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(long double m,long 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<long double,int> eval(long 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)>>1;
	build(id,node<<1,l,mid);
	build(id,(node<<1)|1,mid+1,r);
	for(int i=l;i<=r;i++)
		tr[id][node].add(p[i],a[id][i],i);
}

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

# Verdict Execution time Memory Grader output
1 Correct 61 ms 113144 KB Output is correct
2 Correct 75 ms 114040 KB Output is correct
3 Correct 1837 ms 415992 KB Output is correct
4 Correct 1937 ms 415992 KB Output is correct
5 Correct 304 ms 189688 KB Output is correct
6 Execution timed out 3047 ms 524288 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #2
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 112888 KB Output is correct
2 Correct 84 ms 115064 KB Output is correct
3 Correct 1983 ms 384696 KB Output is correct
4 Correct 1887 ms 384700 KB Output is correct
5 Correct 175 ms 140920 KB Output is correct
6 Execution timed out 3062 ms 524288 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 113144 KB Output is correct
2 Correct 75 ms 114040 KB Output is correct
3 Correct 1837 ms 415992 KB Output is correct
4 Correct 1937 ms 415992 KB Output is correct
5 Correct 304 ms 189688 KB Output is correct
6 Execution timed out 3047 ms 524288 KB Time limit exceeded
7 Halted 0 ms 0 KB -