| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 149894 | Dopatii (#200) | 최적의 팀 구성 (FXCUP4_squad) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "squad.h"
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
const int nmax=300005;
const int magic=39;
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;
void ini(int sz)
{
st.resize(sz+1);
}
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--;
u++;
st[u]=dr;
}
};
long long mx;
int wh;
mt19937 gen(chrono::high_resolution_clock::now().time_since_epoch().count());
int n,i;
struct aint
{
CHT arb[4*nmax];
vector<line> drepte[nmax];
vector<ldouble> all[4*nmax];
vector<ldouble> k1,k2,k3,k4;
vector<int> pica_st[4*nmax],pica_dr[4*nmax],pica_in[4*nmax];
line want[nmax];
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(want[l]);
arb[nod].ins(want[l]);
return;
}
int m=(l+r)/2;
build(2*nod,l,m);
build(2*nod+1,m+1,r);
//drepte.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]);
for(i=0;i<all[2*nod].size();i+=2)
k1.push_back(all[2*nod][i]);
for(i=0;i<all[2*nod+1].size();i+=2)
k2.push_back(all[2*nod+1][i]);
k3.clear();
k3.push_back(0);
for(i=1;i<arb[nod].u;i++)
k3.push_back(in(arb[nod].st[i],arb[nod].st[i+1]));
merge(k1.begin(),k1.end(),k2.begin(),k2.end(),k4.begin());
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&&in(arb[nod].st[p],arb[nod].st[p+1])<=act)//vezi aici
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].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);
}
if(unde+1<all[nod].size()&&all[nod][unde+1]<val)
unde+=1;
if(st<=l&&r<=dr)
{
int poz=pica_in[nod][unde];
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> A, std::vector<int> D, std::vector<int> P){
int N = A.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=A[i],atac[i].b=P[i],atac[i].ind=i+1;
apar[i+1].a=D[i],apar[i].b=P[i],apar[i].ind=i+1;
}
for(i=1;i<=n;i++)
{
A[0].want[i]=atac[i];
A[1].want[i]=apar[i];
}
A[0].build(1,1,n);
A[1].build(1,1,n);
}
long long BestSquad(int X, int Y){
long long ret=0;
for(int it=0;it<2;it++)
{
mx=0;act=0;
A[it].query(1,1,n,1,n,X,Y);
act+=mx;
int spl=wh;
mx=0;
if(spl>1) A[1-it].query(1,1,n,1,spl-1,X,Y);
if(spl<n) A[1-it].query(1,1,n,spl+1,n,X,Y);
act+=mx;
if(act>ret)
return act;
}
return ret;
}