#include "squad.h"
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef long double db;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<db,db> pdb;
typedef tuple<int,int,int,int> TP;
typedef vector<vector<ll>> mat;
const int N=3e5+5;
const ll mod=1e9+7;
int n;
ll a[N],d[N],p[N];
struct Lichao{
pii tree[2*N]; int cn=1,le[2*N]={0},re[2*N]={0};
pll func[N];
void ins(int nd,db L,db R,int x)
{
if(!tree[nd].fi){
tree[nd].fi=x;
return;
}
db M=(L+R)/2.;
if(!tree[nd].se){
db r1=(db)func[tree[nd].fi].fi*M+(db)func[tree[nd].fi].se;
db r2=(db)func[x].fi*M+(db)func[x].se;
tree[nd].se=x;
if(r1<r2) swap(tree[nd].fi,tree[nd].se);
return;
}
db m1=(db)func[tree[nd].fi].fi*M+(db)func[tree[nd].fi].se;
db m2=(db)func[tree[nd].se].fi*M+(db)func[tree[nd].se].se;
db m3=(db)func[x].fi*M+(db)func[x].se;
db l1=(db)func[tree[nd].fi].fi*L+(db)func[tree[nd].fi].se;
db l2=(db)func[tree[nd].se].fi*L+(db)func[tree[nd].se].se;
db l3=(db)func[x].fi*L+(db)func[x].se;
db r1=(db)func[tree[nd].fi].fi*R+(db)func[tree[nd].fi].se;
db r2=(db)func[tree[nd].se].fi*R+(db)func[tree[nd].se].se;
db r3=(db)func[x].fi*R+(db)func[x].se;
if(m3>m1){
swap(tree[nd].fi,tree[nd].se);
swap(tree[nd].fi,x);
if(min(l1,l3)>=l2&&min(r1,r3)>=r2) return;
if(l2>=min(l1,l3)){
if(!le[nd]) le[nd]=++cn;
ins(le[nd],L,M,x);
}
if(r2>=min(r1,r3)){
if(re[nd]) re[nd]=++cn;
ins(re[nd],M,R,x);
}
}
else if(m3>m2){
swap(tree[nd].se,x);
if(min(l1,l3)>=l2&&min(r1,r3)>=r2) return;
if(l2>=min(l1,l3)){
if(!le[nd]) le[nd]=++cn;
ins(le[nd],L,M,x);
}
if(r2>=min(r1,r3)){
if(re[nd]) re[nd]=++cn;
ins(re[nd],M,R,x);
}
}
else{
if(min(l1,l2)>=l3&&min(r1,r2)>=r3) return;
if(l3>=min(l1,l2)){
if(!le[nd]) le[nd]=++cn;
ins(le[nd],L,M,x);
}
if(r3>=min(r1,r2)){
if(re[nd]) re[nd]=++cn;
ins(re[nd],M,R,x);
}
}
}
void init(){
for(int i=0;i<2*N;i++) tree[i]=pii(0,0);
for(int i=1;i<=n;i++) ins(1,0,1e9,i);
}
pair<pll,pll> query(int nd,db L,db R,db x,ll rx,ll ry)
{
pll r1=pll(-1e9,-1e9),r2=pll(-1e9,-1e9);
if(!nd) return {r1,r2};
if(tree[nd].fi){
ll f1=rx*func[tree[nd].fi].fi+ry*func[tree[nd].fi].se;
r1=pll(f1,tree[nd].fi);
}
if(tree[nd].se){
ll f2=rx*func[tree[nd].se].fi+ry*func[tree[nd].se].se;
r2=pll(f2,tree[nd].se);
}
db M=(L+R)/2.;
pair<pll,pll> it;
pll n1,n2;
if(x<=M) it=query(le[nd],L,M,x,rx,ry);
else it=query(re[nd],M,R,x,rx,ry);
n1=it.fi;
n2=it.se;
vector<pll> v={r1,r2,n1,n2};
sort(v.begin(),v.end());
return {v[3],v[2]};
}
pair<pll,pll> query(db x,ll rx,ll ry){
return query(1,0,1e9,x,rx,ry);
}
}t1,t2;
void Init(std::vector<int> A, std::vector<int> D, std::vector<int> P){
n=A.size();
for(int i=1;i<=n;i++){
a[i]=A[i-1];
d[i]=D[i-1];
p[i]=P[i-1];
t1.func[i]=pll(a[i],p[i]);
t2.func[i]=pll(d[i],p[i]);
}
t1.init(); t2.init();
}
long long BestSquad(int X, int Y){
ll V=__gcd(X,Y);
auto p1=t1.query((db)X/(db)Y,X,Y),p2=t2.query((db)X/(db)Y,X,Y);
if(p1.fi.se==p2.fi.se) return max(p1.fi.fi+p2.se.fi,p1.se.fi+p2.fi.fi);
return p1.fi.fi+p2.fi.fi;
}
Compilation message
squad.cpp: In function 'long long int BestSquad(int, int)':
squad.cpp:124:5: warning: unused variable 'V' [-Wunused-variable]
ll V=__gcd(X,Y);
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
9856 KB |
Output is correct |
| 2 |
Correct |
13 ms |
9856 KB |
Output is correct |
| 3 |
Correct |
277 ms |
33276 KB |
Output is correct |
| 4 |
Correct |
250 ms |
33272 KB |
Output is correct |
| 5 |
Incorrect |
115 ms |
11384 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
9856 KB |
Output is correct |
| 2 |
Correct |
27 ms |
10104 KB |
Output is correct |
| 3 |
Correct |
1045 ms |
35508 KB |
Output is correct |
| 4 |
Correct |
1006 ms |
35508 KB |
Output is correct |
| 5 |
Incorrect |
85 ms |
10984 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
9856 KB |
Output is correct |
| 2 |
Correct |
13 ms |
9856 KB |
Output is correct |
| 3 |
Correct |
277 ms |
33276 KB |
Output is correct |
| 4 |
Correct |
250 ms |
33272 KB |
Output is correct |
| 5 |
Incorrect |
115 ms |
11384 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
