#pragma GCC optimize("-Ofast","-funroll-all-loops","-ffast-math")
#include "squad.h"
#include <iostream>
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <time.h>
#include <stdlib.h>
#include <string>
#include <bitset>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <algorithm>
#include <sstream>
#include <stack>
#include <iomanip>
#include <assert.h>
using namespace std;
#define pb push_back
#define mp make_pair
typedef pair<int,int> pii;
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
#define fi first
#define se second
#define fe first
#define FO(x) {freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);}
#define Edg int M=0,fst[SZ],vb[SZ],nxt[SZ];void ad_de(int a,int b){++M;nxt[M]=fst[a];fst[a]=M;vb[M]=b;}void adde(int a,int b){ad_de(a,b);ad_de(b,a);}
#define Edgc int M=0,fst[SZ],vb[SZ],nxt[SZ],vc[SZ];void ad_de(int a,int b,int c){++M;nxt[M]=fst[a];fst[a]=M;vb[M]=b;vc[M]=c;}void adde(int a,int b,int c){ad_de(a,b,c);ad_de(b,a,c);}
#define es(x,e) (int e=fst[x];e;e=nxt[e])
#define esb(x,e,b) (int e=fst[x],b=vb[e];e;e=nxt[e],b=vb[e])
#define SZ 1111111
typedef pair<ll,ll> pll;
ll operator * (pll a,pll b)
{
return a.fi*(ll)b.se-(ll)a.se*b.fi;
}
pll operator - (pll a,pll b)
{
return pll(a.fi-b.fi,a.se-b.se);
}
pll operator + (pll a,pll b)
{
return pll(a.fi+b.fi,a.se+b.se);
}
void convex_hull(vector<pll>& p)
{
stable_sort(p.begin(),p.end());
p.erase(unique(p.begin(),p.end()),p.end());
if(p.size()<=2) return;
vector<pll> h;
for(int r=0;r<2;++r)
{
int l=h.size();
for(auto x:p)
{
while((int)h.size()>l+1&&
(h[h.size()-1]-h[h.size()-2])
*(x-h[h.size()-2])<=0) h.pop_back();
h.pb(x);
}
h.pop_back();
reverse(p.begin(),p.end());
}
p=h;
}
vector<pll> su(const vector<pll>& aa,const vector<pll>& bb)
{
// vector<pll> g;
// for(auto x:aa)
// for(auto y:bb) g.pb(y+x);
// g=convex_hull(g);
// return g;
static pll ans[SZ],a[SZ],b[SZ];
int top,top1=aa.size(),top2=bb.size();
for(int i=1;i<top1;++i) a[i]=aa[i]-aa[i-1];
for(int i=1;i<top2;++i) b[i]=bb[i]-bb[i-1];
a[top1]=aa[0]-aa[top1-1];
b[top2]=bb[0]-bb[top2-1];
//for(int i=1;i<=top1;i++)a[i]=stack1[i+1]-stack1[i];
//for(int i=1;i<=top2;i++)b[i]=stack2[i+1]-stack2[i];
ans[top=1]=aa[0]+bb[0];
int now1=1,now2=1;
while(now1<=top1&&now2<=top2)
top++,ans[top]=ans[top-1]+
((a[now1]*b[now2])>=0?a[now1++]:b[now2++]);
while(now1<=top1)top++,ans[top]=ans[top-1]+a[now1++];
while(now2<=top2)top++,ans[top]=ans[top-1]+b[now2++];
top--;
vector<pll> oo(top);
for(int i=0;i<top;++i) oo[i]=(ans[i+1]);
return oo;
}
int n,a[SZ],d[SZ],p[SZ];
vector<pll> op;
vector<pll> oa[SZ],ob[SZ];
void go(int l,int r,int i=1)
{
if(l>=r)
{
for(int t=l;t<=r;++t)
oa[i].pb(pll(a[t],p[t])),
ob[i].pb(pll(d[t],p[t]));
return;
}
int m=(l+r)>>1;
go(l,m,i*2); go(m+1,r,i*2+1);
vector<pll> &A=oa[i*2],&B=ob[i*2],&C=oa[i*2+1],&D=ob[i*2+1];
// vector<pll> A(m-l+1),B(m-l+1),C(r-m),D(r-m);
// for(int i=l;i<=m;++i)
// A[i-l]=(pll(a[i],p[i])),
// B[i-l]=(pll(d[i],p[i]));
// for(int i=m+1;i<=r;++i)
// C[i-m-1]=(pll(a[i],p[i])),
// D[i-m-1]=(pll(d[i],p[i]));
#define CH(w) convex_hull(w)
CH(A);CH(B);CH(C);CH(D);
// cout<<A.size()<<"w"<<B.size()<<"w"<<C.size()<<"w"<<D.size()<<"\n";
for(auto t:su(A,D)) op.pb(t);
for(auto t:su(B,C)) op.pb(t);
for(auto t:C) A.pb(t);
for(auto t:D) B.pb(t);
swap(A,oa[i]);
swap(B,ob[i]);
}
struct fs
{
ll a,b;
fs() {}
fs(ll p,ll q)
{
if(q==0) a=-4e9,b=1;
else
{
if(q<0) q=-q,p=-p;
a=p,b=q;
}
}
};
bool operator < (fs a,fs b)
{
return a.a*b.b<b.a*a.b;
}
vector<pair<fs,pll>> sb;
void Init(std::vector<int> A, std::vector<int> D, std::vector<int> P){
n=A.size();
for(int i=0;i<n;++i) a[i]=A[i],d[i]=D[i],p[i]=P[i];
go(0,n-1);
// for(auto u:op) cout<<u.fi<<","<<u.se<<"!";
// cout<<"\n";
convex_hull(op);
// for(auto w:op)
// cout<<w.fi<<","<<w.se<<" ";
// cout<<"\n";
for(int j=0;j<op.size();++j)
{
pll P=op[j],Q=op[(j+1)%op.size()];
pll t=P;
if(t.fi<=Q.fi&&t.se<=Q.se) t=Q;
sb.pb(mp(fs(Q.se-P.se,Q.fi-P.fi),t));
}
sort(sb.begin(),sb.end());
}
long long BestSquad(int X, int Y){
auto w=lower_bound(sb.begin(),sb.end(),mp(fs(-X,Y),pll(0,0)));
for(int j=1;j<=8&&w!=sb.begin();++j)
--w;
ll mx=0;
for(int j=0;j<6&&j<sb.size();++j)
mx=max(mx,sb[j].se.fi*(ll)X+sb[j].se.se*(ll)Y);
// for(int w=0,j=sb.size()-1;w<5&&w<sb.size();++w,--j)
// mx=max(mx,sb[j].se.fi*(ll)X+sb[j].se.se*(ll)Y);
for(int j=1;j<=16&&w!=sb.end();++j)
{
mx=max(mx,X*(ll)w->se.fi+Y*(ll)w->se.se);
++w;
}
return mx;
}
#ifdef LOCAL
#include "grader.cpp"
#endif
Compilation message
squad.cpp: In function 'void Init(std::vector<int>, std::vector<int>, std::vector<int>)':
squad.cpp:158:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=0;j<op.size();++j)
~^~~~~~~~~~
squad.cpp: In function 'long long int BestSquad(int, int)':
squad.cpp:173:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=0;j<6&&j<sb.size();++j)
~^~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
37 ms |
52608 KB |
Output is correct |
| 2 |
Correct |
44 ms |
53116 KB |
Output is correct |
| 3 |
Correct |
1398 ms |
193112 KB |
Output is correct |
| 4 |
Correct |
1360 ms |
193112 KB |
Output is correct |
| 5 |
Correct |
185 ms |
79820 KB |
Output is correct |
| 6 |
Correct |
2953 ms |
524288 KB |
Output is correct |
| 7 |
Correct |
2804 ms |
524288 KB |
Output is correct |
| 8 |
Execution timed out |
3045 ms |
524288 KB |
Time limit exceeded |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
41 ms |
52608 KB |
Output is correct |
| 2 |
Correct |
52 ms |
53492 KB |
Output is correct |
| 3 |
Correct |
1251 ms |
169944 KB |
Output is correct |
| 4 |
Correct |
1215 ms |
169944 KB |
Output is correct |
| 5 |
Correct |
118 ms |
62556 KB |
Output is correct |
| 6 |
Correct |
2215 ms |
356824 KB |
Output is correct |
| 7 |
Correct |
2086 ms |
356820 KB |
Output is correct |
| 8 |
Correct |
2149 ms |
356820 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
37 ms |
52608 KB |
Output is correct |
| 2 |
Correct |
44 ms |
53116 KB |
Output is correct |
| 3 |
Correct |
1398 ms |
193112 KB |
Output is correct |
| 4 |
Correct |
1360 ms |
193112 KB |
Output is correct |
| 5 |
Correct |
185 ms |
79820 KB |
Output is correct |
| 6 |
Correct |
2953 ms |
524288 KB |
Output is correct |
| 7 |
Correct |
2804 ms |
524288 KB |
Output is correct |
| 8 |
Execution timed out |
3045 ms |
524288 KB |
Time limit exceeded |
