#include <bits/stdc++.h>
using namespace std;
using lint = long long;
const lint INF = 1e12;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int N, Q;
cin >> N >> Q;
vector<lint> T(N), A(N), B(N), C(N);
for (int i = 0; i < N; i++) {
cin >> T[i] >> A[i] >> B[i] >> C[i];
T[i] *= 2; A[i] *= 2; B[i] *= 2;
}
vector<lint> P(Q), X(Q);
for (int i = 0; i < Q; i++) {
cin >> P[i] >> X[i];
P[i] *= 2; X[i] *= 2;
}
// Solution:
// In the 2D graph of position and time, the VIPs
// are diagonal lines. We must move (diagonally)
// s.t. maximize the sum of costs of overlapping lines.
//
// Rotate the lines by 45 degrees using (x + y, x - y).
// Then, we can do coordinate compression. Since there
// are O(N) distinct x coordinates and y coordinates,
// we can make the DP table in O(N^2).
//
// For each query, assume we go rightwards (downwards is
// symnetric). Then there are O(N) distinct y coordinates
// we can start on, so this runs in O(Q N). We can optimize
// getting the answer for a query with the Convex Hull Trick.
//
// Time complexity: O(N^2 + Q log N).
vector<lint> ans(Q);
vector<lint> coords = {-INF, INF};
vector<array<lint, 3>> query;
vector<array<lint, 5>> lines;
for (int i = 0; i < N; i++) {
pair<lint, lint> st = {T[i], A[i]};
pair<lint, lint> et = {T[i] + abs(A[i] - B[i]), B[i]};
st = pair(st.first + st.second, st.first - st.second);
et = pair(et.first + et.second, et.first - et.second);
lines.push_back({st.first, st.second, et.first, et.second, C[i]});
assert(st < et && (st.first == et.first || st.second == et.second));
coords.emplace_back(st.first);
coords.emplace_back(st.second);
coords.emplace_back(et.first);
coords.emplace_back(et.second);
}
for (int i = 0; i < Q; i++) {
pair<lint, lint> st = {P[i], X[i]};
st = pair(st.first + st.second, st.first - st.second);
query.push_back({st.first, st.second, i});
}
sort(begin(coords), end(coords));
coords.resize(unique(begin(coords), end(coords)) - begin(coords));
const auto Coord = [&](lint x) {
return lower_bound(begin(coords), end(coords), x) - begin(coords);
};
for (auto &l : lines) {
for (int i = 0; i < 4; i++) {
l[i] = Coord(l[i]);
}
}
for (int rep = 0; rep < 2; rep++) {
sort(begin(lines), end(lines));
int query_ptr = 0;
sort(begin(query), end(query));
reverse(begin(query), end(query));
vector<lint> dp(coords.size());
for (int x = int(coords.size()) - 1; x >= 1; x--) {
vector<lint> cost_horz(coords.size());
vector<lint> cost_vert(coords.size());
vector<lint> last = dp;
for (int lid = 0; lid < int(lines.size()); lid++) {
auto l = lines[lid];
if (l[0] == l[2] && l[0] == x) { // horizontal line
for (int y = l[1]; y < l[3]; y++) {
cost_horz[y] = max(cost_horz[y], l[4]);
}
}
if (l[1] == l[3] && l[0] <= x && x < l[2]) { // vertical line
dp[l[1]] = max(dp[l[1]], last[l[1]] + (coords[x + 1] - coords[x]) * l[4]);
}
if (l[1] == l[3] && l[0] < x && x <= l[2]) {
cost_vert[l[1]] = max(cost_vert[l[1]], l[4]);
}
}
for (int y = int(coords.size()) - 2; y >= 0; y--) {
dp[y] = max(dp[y], cost_horz[y] * (coords[y + 1] - coords[y]) + dp[y + 1]);
}
// Convex Hull Trick
vector<pair<lint, lint>> hull;
const auto Check = [&](pair<lint, lint> a, pair<lint, lint> b, pair<lint, lint> c) -> bool {
return double(b.second - a.second) / double(a.first - b.first) <
double(c.second - b.second) / double(b.first - c.first);
};
const auto Insert = [&](lint a, lint b) -> void {
while (!hull.empty() && hull.back().first <= a) {
assert(hull.back().second <= b);
hull.pop_back(); // all line (a, b) and query (x) are non-negative integers
}
while (hull.size() > 1 && !Check({a, b}, hull.back(), end(hull)[-2])) {
hull.pop_back();
}
hull.emplace_back(a, b);
};
const auto Query = [&](lint x) -> lint {
int lo = 0, hi = int(hull.size()) - 1;
while (lo < hi) {
int md = (lo + hi) / 2;
if (hull[md].first * x + hull[md].second > hull[md + 1].first * x + hull[md + 1].second) {
hi = md;
} else {
lo = md + 1;
}
}
return hull[lo].first * x + hull[lo].second;
};
vector<array<lint, 4>> query_list;
while (query_ptr < int(query.size()) && coords[x - 1] < query[query_ptr][0]) {
auto q = query[query_ptr++];
int yinit = lower_bound(begin(coords), end(coords), q[1]) - begin(coords);
if (coords[x] == q[0]) {
ans[q[2]] = max(ans[q[2]], dp[yinit] + (coords[yinit] - q[1]) * cost_horz[yinit - 1]);
} else {
query_list.push_back({yinit, q[0], q[1], q[2]});
}
}
int inserted_y = int(coords.size());
sort(begin(query_list), end(query_list));
reverse(begin(query_list), end(query_list));
for (auto q : query_list) {
int yinit = q[0];
// for (int y = yinit; y < int(coords.size()); y++) {
// ans[q[3]] = max(ans[q[3]], dp[y] + (coords[x] - q[1]) * cost_vert[y]);
// }
// Note that dp[y] >= dp[y + 1]
// Thus, while slope[y] >= CHT.back().slope, pop CHT.back(). Afterwards, the slope is
// still sorted when we add line y. This works since for all input f(x), x >= 0 holds,
// thus a greater slope is always optimal if the dp[y] is also greater.
// This allows us to do CHT insert in O(1).
while (yinit < inserted_y) {
Insert(cost_vert[inserted_y - 1], dp[inserted_y - 1]);
inserted_y -= 1;
}
ans[q[3]] = max(ans[q[3]], Query(coords[x] - q[1]));
}
}
for (int i = 0; i < N; i++) {
swap(lines[i][0], lines[i][1]);
swap(lines[i][2], lines[i][3]);
}
for (int i = 0; i < Q; i++) {
swap(query[i][0], query[i][1]);
}
}
for (int i = 0; i < Q; i++) {
assert(ans[i] % 4 == 0);
cout << (ans[i] / 4) << '\n';
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3952 ms |
186596 KB |
Output is correct |
| 2 |
Correct |
3962 ms |
186472 KB |
Output is correct |
| 3 |
Correct |
3672 ms |
307860 KB |
Output is correct |
| 4 |
Correct |
3349 ms |
242252 KB |
Output is correct |
| 5 |
Correct |
4333 ms |
308032 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1382 ms |
1048 KB |
Output is correct |
| 2 |
Correct |
1348 ms |
1044 KB |
Output is correct |
| 3 |
Incorrect |
1316 ms |
1128 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1382 ms |
1048 KB |
Output is correct |
| 2 |
Correct |
1348 ms |
1044 KB |
Output is correct |
| 3 |
Incorrect |
1316 ms |
1128 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1382 ms |
1048 KB |
Output is correct |
| 2 |
Correct |
1348 ms |
1044 KB |
Output is correct |
| 3 |
Incorrect |
1316 ms |
1128 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3952 ms |
186596 KB |
Output is correct |
| 2 |
Correct |
3962 ms |
186472 KB |
Output is correct |
| 3 |
Correct |
3672 ms |
307860 KB |
Output is correct |
| 4 |
Correct |
3349 ms |
242252 KB |
Output is correct |
| 5 |
Correct |
4333 ms |
308032 KB |
Output is correct |
| 6 |
Correct |
1382 ms |
1048 KB |
Output is correct |
| 7 |
Correct |
1348 ms |
1044 KB |
Output is correct |
| 8 |
Incorrect |
1316 ms |
1128 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
