답안 #149894

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
149894	2019-09-01T07:21:43 Z	Dopatii(#3751, bogdan10bos, Gioto, Bodo171)	최적의 팀 구성 (FXCUP4_squad)	C++17	컴파일 오류	0 ms	0 KB

squad

#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;
}

Compilation message

squad.cpp: In member function 'int aint::cb(ldouble)':
squad.cpp:62: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:81:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(i=0; i<drepte[nod].size(); i++)
                  ~^~~~~~~~~~~~~~~~~~~
squad.cpp:83:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(i=0;i<all[2*nod].size();i+=2)
                 ~^~~~~~~~~~~~~~~~~~
squad.cpp:85:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(i=0;i<all[2*nod+1].size();i+=2)
                 ~^~~~~~~~~~~~~~~~~~~~
squad.cpp:97:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(i=0;i<all[nod].size();i++)
                 ~^~~~~~~~~~~~~~~~
squad.cpp:108:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             while(p<all[2*nod].size()&&all[2*nod][p]<=act)
                   ~^~~~~~~~~~~~~~~~~~
squad.cpp:114:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             while(p<all[2*nod].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:127:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(unde+1<all[nod].size()&&all[nod][unde+1]<val)
            ~~~~~~^~~~~~~~~~~~~~~~
squad.cpp: In function 'void Init(std::vector<int>, std::vector<int>, std::vector<int>)':
squad.cpp:157:14: error: request for member 'want' in 'A.std::vector<int>::operator[](0)', which is of non-class type '__gnu_cxx::__alloc_traits<std::allocator<int> >::value_type {aka int}'
         A[0].want[i]=atac[i];
              ^~~~
squad.cpp:158:14: error: request for member 'want' in 'A.std::vector<int>::operator[](1)', which is of non-class type '__gnu_cxx::__alloc_traits<std::allocator<int> >::value_type {aka int}'
         A[1].want[i]=apar[i];
              ^~~~
squad.cpp:160:10: error: request for member 'build' in 'A.std::vector<int>::operator[](0)', which is of non-class type '__gnu_cxx::__alloc_traits<std::allocator<int> >::value_type {aka int}'
     A[0].build(1,1,n);
          ^~~~~
squad.cpp:161:10: error: request for member 'build' in 'A.std::vector<int>::operator[](1)', which is of non-class type '__gnu_cxx::__alloc_traits<std::allocator<int> >::value_type {aka int}'
     A[1].build(1,1,n);
          ^~~~~
squad.cpp: In function 'long long int BestSquad(int, int)':
squad.cpp:167:14: error: 'act' was not declared in this scope
         mx=0;act=0;
              ^~~
squad.cpp:168:34: error: no matching function for call to 'aint::query(int, int, int&, int, int&, int&, int&)'
         A[it].query(1,1,n,1,n,X,Y);
                                  ^
squad.cpp:120:10: note: candidate: void aint::query(int, int, int, int, int, int, long long int, long long int)
     void query(int nod,int l,int r,int st,int dr,int unde,long long X,long long Y)
          ^~~~~
squad.cpp:120:10: note:   candidate expects 8 arguments, 7 provided
squad.cpp:172:50: error: no matching function for call to 'aint::query(int, int, int&, int, int, int&, int&)'
         if(spl>1) A[1-it].query(1,1,n,1,spl-1,X,Y);
                                                  ^
squad.cpp:120:10: note: candidate: void aint::query(int, int, int, int, int, int, long long int, long long int)
     void query(int nod,int l,int r,int st,int dr,int unde,long long X,long long Y)
          ^~~~~
squad.cpp:120:10: note:   candidate expects 8 arguments, 7 provided
squad.cpp:173:50: error: no matching function for call to 'aint::query(int, int, int&, int, int&, int&, int&)'
         if(spl<n) A[1-it].query(1,1,n,spl+1,n,X,Y);
                                                  ^
squad.cpp:120:10: note: candidate: void aint::query(int, int, int, int, int, int, long long int, long long int)
     void query(int nod,int l,int r,int st,int dr,int unde,long long X,long long Y)
          ^~~~~
squad.cpp:120:10: note:   candidate expects 8 arguments, 7 provided