#include "squad.h"
#include <bits/stdc++.h>
using namespace std;
const int nmax=100005;
typedef double ldouble;
struct line
{
int a,b,ind;
long long ev(long long X,long long Y)
{
return (1LL*this->a*X+1LL*this->b*Y);
}
}atac[nmax],apar[nmax];
bool operator <(line unu,line doi)
{
if(unu.a==doi.a) return unu.b<doi.b;
return unu.a<doi.a;
}
ldouble a1,a2,b1,b2;
int lg[nmax];
ldouble in(line unu,line doi)
{
a1=unu.a,a2=doi.a,b1=unu.b,b2=doi.b;
return (b2-b1)/(a1-a2);
}
struct CHT
{
int u;
vector<line> st;
vector<ldouble> ints;
void ini(int sz)
{
st.resize(sz+2);
ints.resize(sz+2);
ints[0]=-(1<<30);
}
void ins(line dr)
{
while(u>=1&&st[u].a==dr.a&&st[u].b<dr.b)
u--;
while(u>=2&&in(st[u-1],st[u])>in(st[u-1],dr))
u--;
if(u)ints[u]=in(st[u],dr);
u++;
st[u]=dr;
}
};
long long mx;
int wh;
mt19937 gen(chrono::high_resolution_clock::now().time_since_epoch().count());
int n,i;
line wants[nmax];
struct aint
{
CHT arb[4*nmax];
vector<line> drepte[nmax];
vector<ldouble> all[4*nmax];
vector<int> pica_st[4*nmax],pica_dr[4*nmax],pica_in[4*nmax];
vector<ldouble> k1,k2,k3,k4;
int cb(ldouble x)
{
int ret=0;
for(int p=17; p>=0; p--)
if(ret+(1<<p)<all[1].size()&&all[1][ret+(1<<p)]<x)
ret+=(1<<p);
return ret;
}
void build(int nod,int l,int r)
{
if(l==r)
{
arb[nod].ini(1);
drepte[nod].push_back(wants[l]);
arb[nod].ins(wants[l]);
all[nod].push_back(-(1<<30));
pica_in[nod].push_back(0);
return;
}
int m=(l+r)/2;
build(2*nod,l,m);
build(2*nod+1,m+1,r);
drepte[nod].resize(r-l+1);
merge(drepte[2*nod].begin(),drepte[2*nod].end(),drepte[2*nod+1].begin(),drepte[2*nod+1].end(),drepte[nod].begin());
arb[nod].ini(r-l+1);
for(i=0; i<drepte[nod].size(); i++)
arb[nod].ins(drepte[nod][i]);
k1.resize((all[2*nod].size()+1)/2);
int cv1=0,cv2=0;
for(i=0;i<all[2*nod].size();i+=2)
k1[cv1++]=(all[2*nod][i]);
k2.resize((all[2*nod+1].size()+1)/2);
for(i=0;i<all[2*nod+1].size();i+=2)
k2[cv2++]=(all[2*nod+1][i]);
k3.resize(arb[nod].u);
for(i=0;i<arb[nod].u;i++)
k3[i]=(arb[nod].ints[i]);
k4.resize(k1.size()+k2.size());
merge(k1.begin(),k1.end(),k2.begin(),k2.end(),k4.begin());
all[nod].resize(k3.size()+k4.size());
merge(k3.begin(),k3.end(),k4.begin(),k4.end(),all[nod].begin());
int p;
ldouble act;
int sz=all[nod].size();
pica_in[nod].resize(sz);pica_st[nod].resize(sz);pica_dr[nod].resize(sz);
for(i=0;i<all[nod].size();i++)
{
act=all[nod][i];
if(i>0) p=max(pica_in[nod][i-1],0);
else p=0;
while(p<arb[nod].u&&arb[nod].ints[p]<=act)
p++;
p--;
pica_in[nod][i]=p;
if(i>0) p=max(pica_st[nod][i-1],0);
else p=0;
while(p<all[2*nod].size()&&all[2*nod][p]<=act)
p++;
p--;
pica_st[nod][i]=p;
if(i>0) p=max(pica_dr[nod][i-1],0);
else p=0;
while(p<all[2*nod+1].size()&&all[2*nod+1][p]<=act)
p++;
p--;
pica_dr[nod][i]=p;
}
}
void query(int nod,int l,int r,int st,int dr,int unde,long long X,long long Y)
{
ldouble val=(ldouble)(X)/(ldouble)(Y);
if(l==1&&r==n)
{
unde=cb(val);
}
while(unde+1<all[nod].size()&&all[nod][unde+1]<val)
unde++;
if(st<=l&&r<=dr)
{
int poz=pica_in[nod][unde]+1;
line D=arb[nod].st[poz];
if(D.ev(X,Y)>mx)
{
mx=D.ev(X,Y);
wh=D.ind;
}
return;
}
int m=(l+r)/2;
if(st<=m) query(2*nod,l,m,st,dr,pica_st[nod][unde],X,Y);
if(m<dr) query(2*nod+1,m+1,r,st,dr,pica_dr[nod][unde],X,Y);
}
}A[2];
void Init(std::vector<int> Aa, std::vector<int> D, std::vector<int> P){
int N = Aa.size();
n=N;
for(i=2;i<=n;i++)
lg[i]=lg[i/2]+1;
for(i=0;i<n;i++)
{
atac[i+1].a=Aa[i],atac[i+1].b=P[i],atac[i+1].ind=i+1;
apar[i+1].a=D[i],apar[i+1].b=P[i],apar[i+1].ind=i+1;
}
for(i=1;i<=n;i++)
wants[i]=atac[i];
A[0].build(1,1,n);
for(i=1;i<=n;i++)
wants[i]=apar[i];
A[1].build(1,1,n);
}
long long BestSquad(int X, int Y){
long long ret=0,act=0;
for(int it=0;it<2;it++)
{
mx=0;act=0;
A[it].query(1,1,n,1,n,0,X,Y);
act+=mx;
int spl=wh;
mx=0;
if(spl>1) A[1-it].query(1,1,n,1,spl-1,0,X,Y);
if(spl<n) A[1-it].query(1,1,n,spl+1,n,0,X,Y);
act+=mx;
if(act>ret)
ret=act;
}
return ret;
}
Compilation message
squad.cpp: In member function 'int aint::cb(ldouble)':
squad.cpp:65:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(ret+(1<<p)<all[1].size()&&all[1][ret+(1<<p)]<x)
~~~~~~~~~~^~~~~~~~~~~~~~
squad.cpp: In member function 'void aint::build(int, int, int)':
squad.cpp:86:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=0; i<drepte[nod].size(); i++)
~^~~~~~~~~~~~~~~~~~~
squad.cpp:90:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=0;i<all[2*nod].size();i+=2)
~^~~~~~~~~~~~~~~~~~
squad.cpp:93:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=0;i<all[2*nod+1].size();i+=2)
~^~~~~~~~~~~~~~~~~~~~
squad.cpp:106:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=0;i<all[nod].size();i++)
~^~~~~~~~~~~~~~~~
squad.cpp:117:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(p<all[2*nod].size()&&all[2*nod][p]<=act)
~^~~~~~~~~~~~~~~~~~
squad.cpp:123:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(p<all[2*nod+1].size()&&all[2*nod+1][p]<=act)
~^~~~~~~~~~~~~~~~~~~~
squad.cpp: In member function 'void aint::query(int, int, int, int, int, int, long long int, long long int)':
squad.cpp:136:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(unde+1<all[nod].size()&&all[nod][unde+1]<val)
~~~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
78 ms |
124028 KB |
Output is correct |
| 2 |
Correct |
79 ms |
125688 KB |
Output is correct |
| 3 |
Runtime error |
238 ms |
133880 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
80 ms |
124152 KB |
Output is correct |
| 2 |
Correct |
90 ms |
127856 KB |
Output is correct |
| 3 |
Runtime error |
209 ms |
133880 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
78 ms |
124028 KB |
Output is correct |
| 2 |
Correct |
79 ms |
125688 KB |
Output is correct |
| 3 |
Runtime error |
238 ms |
133880 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 4 |
Halted |
0 ms |
0 KB |
- |
