#include "squad.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ar array
bool cmp(ar<int, 2> a, ar<int, 2> b) {
return (ll)a[0]*b[1]<(ll)b[0]*a[1];
}
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], {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;
}
Compilation message
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], {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], {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 time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
1024 KB |
Output is correct |
| 2 |
Correct |
9 ms |
1536 KB |
Output is correct |
| 3 |
Correct |
786 ms |
10128 KB |
Output is correct |
| 4 |
Correct |
758 ms |
10104 KB |
Output is correct |
| 5 |
Correct |
68 ms |
30612 KB |
Output is correct |
| 6 |
Correct |
1275 ms |
524288 KB |
Output is correct |
| 7 |
Correct |
1309 ms |
524288 KB |
Output is correct |
| 8 |
Correct |
1308 ms |
524288 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
1152 KB |
Output is correct |
| 2 |
Correct |
13 ms |
1664 KB |
Output is correct |
| 3 |
Correct |
1364 ms |
12468 KB |
Output is correct |
| 4 |
Correct |
1343 ms |
12464 KB |
Output is correct |
| 5 |
Correct |
118 ms |
11700 KB |
Output is correct |
| 6 |
Execution timed out |
3115 ms |
302420 KB |
Time limit exceeded |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
1024 KB |
Output is correct |
| 2 |
Correct |
9 ms |
1536 KB |
Output is correct |
| 3 |
Correct |
786 ms |
10128 KB |
Output is correct |
| 4 |
Correct |
758 ms |
10104 KB |
Output is correct |
| 5 |
Correct |
68 ms |
30612 KB |
Output is correct |
| 6 |
Correct |
1275 ms |
524288 KB |
Output is correct |
| 7 |
Correct |
1309 ms |
524288 KB |
Output is correct |
| 8 |
Correct |
1308 ms |
524288 KB |
Output is correct |
| 9 |
Correct |
6 ms |
1152 KB |
Output is correct |
| 10 |
Correct |
13 ms |
1664 KB |
Output is correct |
| 11 |
Correct |
1364 ms |
12468 KB |
Output is correct |
| 12 |
Correct |
1343 ms |
12464 KB |
Output is correct |
| 13 |
Correct |
118 ms |
11700 KB |
Output is correct |
| 14 |
Execution timed out |
3115 ms |
302420 KB |
Time limit exceeded |
| 15 |
Halted |
0 ms |
0 KB |
- |
