제출 #149894

#제출 시각아이디문제언어결과실행 시간메모리
149894Dopatii (#200)최적의 팀 구성 (FXCUP4_squad)C++17
컴파일 에러
0 ms0 KiB
#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; }

컴파일 시 표준 에러 (stderr) 메시지

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