/* cerberus97 - Hanit Banga */
#include "squad.h"
#include <iostream>
#include <iomanip>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <algorithm>
using namespace std;
#define pb push_back
#define fast_cin() ios_base::sync_with_stdio(false); cin.tie(NULL)
typedef long long ll;
typedef long double ld;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
const int N = 3e5 + 10;
// Attribution - t3nsor codebook
struct ConvexHullTrick {
typedef long long LL;
vector<int> M;
vector<int> B;
vector<int> ids;
vector<double> left;
ConvexHullTrick() {}
bool bad(LL m1, LL b1, LL m2, LL b2, LL m3, LL b3) {
// Careful, this may overflow
return (b3-b1)*(m1-m2) < (b2-b1)*(m1-m3);
}
// Add a new line to the structure, y = mx + b.
// Lines must be added in decreasing order of slope.
void add(LL m, LL b, int id) {
while (M.size() >= 2 && bad(M[M.size()-2], B[B.size()-2], M.back(), B.back(), m, b)) {
M.pop_back(); B.pop_back(); ids.pop_back(); left.pop_back();
}
if (M.size() && M.back() == m) {
if (B.back() > b) {
M.pop_back(); B.pop_back(); ids.pop_back(); left.pop_back();
} else {
return;
}
}
if (M.size() == 0) {
left.push_back(-numeric_limits<double>::infinity());
} else {
left.push_back((double)(b - B.back())/(M.back() - m));
}
M.push_back(m);
B.push_back(b);
ids.push_back(id);
}
// Get the minimum value of mx + b among all lines in the structure.
// There must be at least one line.
pll query(LL x, LL y) {
int i = upper_bound(left.begin(), left.end(), double(y) / x) - left.begin();
return {-(M[i-1]*y + B[i-1]*x), ids[i - 1]};
}
};
struct player_t {
int a, d, p;
bool operator<(const player_t &o) const {
return p < o.p;
}
};
int n;
player_t player[N];
ConvexHullTrick atree[4 * N], dtree[4 * N];
void build(int i, int l, int r);
pll query(ConvexHullTrick* tree, int i, int l, int r, int ql, int qr, int x, int y);
void Init(std::vector<int> A, std::vector<int> D, std::vector<int> P){
n = A.size();
for (int i = 1; i <= n; ++i) {
player[i] = {A[i - 1], D[i - 1], P[i - 1]};
}
sort(player + 1, player + n + 1);
build(1, 1, n);
}
ll BestSquad(int x, int y) {
auto ba = query(atree, 1, 1, n, 1, n, x, y);
int id = ba.second;
auto bd = max(query(dtree, 1, 1, n, 1, id - 1, x, y), query(dtree, 1, 1, n, id + 1, n, x, y));
ll ans = ba.first + bd.first;
// cout << ba.second << ' ' << bd.second << endl;
// cout << ba.first << ' ' << bd.first << endl;
bd = query(dtree, 1, 1, n, 1, n, x, y);
if (bd.second != id) {
return ans;
}
id = bd.second;
ba = max(query(atree, 1, 1, n, 1, id - 1, x, y), query(atree, 1, 1, n, id + 1, n, x, y));
ans = max(ans, ba.first + bd.first);
// cout << ba.second << ' ' << bd.second << endl;
// cout << ba.first << ' ' << bd.first << endl;
return ans;
}
void build(int i, int l, int r) {
if (l < r) {
int mid = (l + r) / 2, lc = 2 * i, rc = lc + 1;
build(lc, l, mid);
build(rc, mid + 1, r);
atree[i] = atree[lc];
dtree[i] = dtree[lc];
int s = (l == mid ? l : mid + 1);
for (int j = s; j <= r; ++j) {
dtree[i].add(-player[j].p, -player[j].d, j);
atree[i].add(-player[j].p, -player[j].a, j);
}
}
}
pll query(ConvexHullTrick* tree, int i, int l, int r, int ql, int qr, int x, int y) {
if (l > qr or ql > r) {
return {-1, -1};
} else if (l == r) {
if (tree == atree) {
return {ll(x) * player[l].a + ll(y) * player[l].p, l};
} else {
return {ll(x) * player[l].d + ll(y) * player[l].p, l};
}
} else if (ql <= l and r <= qr) {
return tree[i].query(x, y);
} else {
int mid = (l + r) / 2, lc = 2 * i, rc = lc + 1;
auto a1 = query(tree, lc, l, mid, ql, qr, x, y);
auto a2 = query(tree, rc, mid + 1, r, ql, qr, x, y);
if (a1.first > a2.first) {
return a1;
} else {
return a2;
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
140 ms |
225808 KB |
Output is correct |
| 2 |
Correct |
135 ms |
226168 KB |
Output is correct |
| 3 |
Correct |
1030 ms |
323452 KB |
Output is correct |
| 4 |
Correct |
983 ms |
323320 KB |
Output is correct |
| 5 |
Correct |
173 ms |
240632 KB |
Output is correct |
| 6 |
Correct |
1229 ms |
497364 KB |
Output is correct |
| 7 |
Correct |
1056 ms |
497348 KB |
Output is correct |
| 8 |
Correct |
1182 ms |
497344 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
136 ms |
225656 KB |
Output is correct |
| 2 |
Correct |
149 ms |
226960 KB |
Output is correct |
| 3 |
Correct |
1589 ms |
415388 KB |
Output is correct |
| 4 |
Correct |
1675 ms |
418544 KB |
Output is correct |
| 5 |
Correct |
204 ms |
235000 KB |
Output is correct |
| 6 |
Correct |
2378 ms |
499456 KB |
Output is correct |
| 7 |
Correct |
2405 ms |
499460 KB |
Output is correct |
| 8 |
Execution timed out |
3053 ms |
499456 KB |
Time limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
140 ms |
225808 KB |
Output is correct |
| 2 |
Correct |
135 ms |
226168 KB |
Output is correct |
| 3 |
Correct |
1030 ms |
323452 KB |
Output is correct |
| 4 |
Correct |
983 ms |
323320 KB |
Output is correct |
| 5 |
Correct |
173 ms |
240632 KB |
Output is correct |
| 6 |
Correct |
1229 ms |
497364 KB |
Output is correct |
| 7 |
Correct |
1056 ms |
497348 KB |
Output is correct |
| 8 |
Correct |
1182 ms |
497344 KB |
Output is correct |
| 9 |
Correct |
136 ms |
225656 KB |
Output is correct |
| 10 |
Correct |
149 ms |
226960 KB |
Output is correct |
| 11 |
Correct |
1589 ms |
415388 KB |
Output is correct |
| 12 |
Correct |
1675 ms |
418544 KB |
Output is correct |
| 13 |
Correct |
204 ms |
235000 KB |
Output is correct |
| 14 |
Correct |
2378 ms |
499456 KB |
Output is correct |
| 15 |
Correct |
2405 ms |
499460 KB |
Output is correct |
| 16 |
Execution timed out |
3053 ms |
499456 KB |
Time limit exceeded |
