Submission #150713

#	Time	Username	Problem	Language	Result	Execution time	Memory
150713		Dopatii (#200)	Organizing the Best Squad (FXCUP4_squad)	C++17	0 / 100	401 ms	409720 KiB

squad

#include "squad.h"
#include <bits/stdc++.h>

using namespace std;
const int nmax=300005;
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);
        }
        if(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 (stderr)

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:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(unde+1<all[nod].size()&&all[nod][unde+1]<val)
            ~~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 0 / 19
• Subtask 2: 0 / 28
• Subtask 3: 0 / 53