제출 #150515

#제출 시각아이디문제언어결과실행 시간메모리
150515Seishun Buta Yarou wa Yumemiru Shoujo no Yume wo Minai (#200)최적의 팀 구성 (FXCUP4_squad)C++17
19 / 100
3115 ms524288 KiB
#include "squad.h" #include <bits/stdc++.h> using namespace std; #define ll long long #define ar array bool cmp(int a0, int a1, int b0, int b1) { return (ll)a0*b1<(ll)b0*a1; } struct cht { int a[1<<18], b[1<<18], qt; ar<int, 2> l[1<<18]; vector<ar<int, 4>> m; void al(int c, int d) { while(qt&&c==a[qt-1]||qt>1&&(ll)(b[qt-1]-b[qt-2])*(a[qt-1]-c)>=(ll)(d-b[qt-1])*(a[qt-2]-a[qt-1])) --qt; a[qt]=c; b[qt]=d; ++qt; } void cl() { for(int i=0; i+1<qt; ++i) l[i]={b[i]-b[i+1], a[i+1]-a[i]}; l[qt-1]={1<<30, 1}; } void cm(vector<ar<int, 4>> &v) { for(int i=0, j=0; i<qt||j<v.size(); ) { if(j>=v.size()||i<qt&&cmp(l[i][0], l[i][1], v[j][0], v[j][1])) { m.push_back({l[i][0], l[i][1], i, 2*j+1}); ++i; } else { m.push_back({v[j][0], v[j][1], i, 2*j+1}); ++j; } } //for(ar<int, 4> mi : m) //cout << "{" << mi[0] << " " << mi[1] << " " << mi[2] << " " << mi[3] << "} "; //cout << endl; } } c[76]; int n, k, q[300000]; void Init(vector<int> a, vector<int> d, vector<int> p) { n=a.size(); while(1<<k<n) ++k; iota(q, q+n, 0); sort(q, q+n, [&](const int &i, const int &j) { return ar<int, 2>{a[i], p[i]}<ar<int, 2>{a[j], p[j]}; }); for(int i=0; i<n; ++i) for(int j=0; j<k; ++j) c[j*4+(q[i]>>j&1)].al(a[q[i]], p[q[i]]); sort(q, q+n, [&](const int &i, const int &j) { return ar<int, 2>{d[i], p[i]}<ar<int, 2>{d[j], p[j]}; }); for(int i=0; i<n; ++i) for(int j=0; j<k; ++j) c[j*4+2+(q[i]>>j&1)].al(d[q[i]], p[q[i]]); //cout << "hi0" << endl; for(int i=0; i<k*4; ++i) { c[i].cl(); } //cout << "hi1" << endl; for(int i=k*4-1; ~i; --i) { vector<ar<int, 4>> v; if(i+1<k*4) for(int j=1; j<c[i+1].m.size(); j+=2) v.push_back(c[i+1].m[j]); c[i].cm(v); } //cout << "hi2" << endl; } ll BestSquad(int x, int y) { //cout << "bs " << x << " " << y << endl; ll ans=0, d[k*4]; //for(int i=0; i<k*4; ++i) //d[i]=c[i].qry(x, y); //frucktional cascading int lb=1, rb=c[0].m.size()-1; while(lb<rb) { int mb=(lb+rb)/2; if(!cmp(c[0].m[mb][0], c[0].m[mb][1], x, y)) rb=mb; else lb=mb+1; } //cout << "hi3 " << lb << endl; for(int i=0; i<k*4; ++i) { if(!cmp(c[i].m[lb-1][0], c[i].m[lb-1][1], x, y)) --lb; //cout << i << " " << lb << endl; int j=c[i].m[lb][2]; //cout << j << endl; lb=c[i].m[lb][3]; d[i]=(ll)x*c[i].a[j]+(ll)y*c[i].b[j]; } for(int i=0; i<k; ++i) { //ans=max(ans, ca[i][0].qry(x, y)+cd[i][1].qry(x, y)); //ans=max(ans, cd[i][0].qry(x, y)+ca[i][1].qry(x, y)); ans=max(ans, d[i*4]+d[i*4+3]); ans=max(ans, d[i*4+1]+d[i*4+2]); } return ans; }

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

squad.cpp: In member function 'void cht::al(int, int)':
squad.cpp:17:11: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   while(qt&&c==a[qt-1]||qt>1&&(ll)(b[qt-1]-b[qt-2])*(a[qt-1]-c)>=(ll)(d-b[qt-1])*(a[qt-2]-a[qt-1]))
         ~~^~~~~~~~~~~~
squad.cpp: In member function 'void cht::cm(std::vector<std::array<int, 4> >&)':
squad.cpp:29:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0, j=0; i<qt||j<v.size(); ) {
                           ~^~~~~~~~~
squad.cpp:30:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(j>=v.size()||i<qt&&cmp(l[i][0], l[i][1], v[j][0], v[j][1])) {
       ~^~~~~~~~~~
squad.cpp:30:24: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
    if(j>=v.size()||i<qt&&cmp(l[i][0], l[i][1], v[j][0], v[j][1])) {
                    ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
squad.cpp: In function 'void Init(std::vector<int>, std::vector<int>, std::vector<int>)':
squad.cpp:71:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j=1; j<c[i+1].m.size(); j+=2)
                 ~^~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...