#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));
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
69 ms |
113144 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
70 ms |
113144 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
69 ms |
113144 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
