#include <bits/stdc++.h>
#define pii pair<int, int>
#define pll pair<long long, long long>
#define piii pair<int, pii>
#define tiii tuple<int, int, int>
#define tiiii tuple<int, int, int, int>
#define ff first
#define ss second
#define ee ss.ff
#define rr ss.ss
using namespace std;
const long long INF = (long long)1e9 + 7;
struct line
{
long long a, b;
line(void) : a(0), b(0) {}
long long eval(long long x) { return a * x + b; }
};
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
// freopen("in.txt", "r", stdin);
int n, T; cin >> n >> T;
tiiii A[n];
for(auto &[a, b, c, d] : A) cin >> a >> b >> c >> d;
vector<long long> prX, prY;
for(auto &[a, b, c, d] : A)
{
if(b < c)
{
prX.push_back(1ll * a + b);
prX.push_back(1ll * a - b + 2 * c);
prY.push_back(1ll * a - b + INF);
}
else
{
prX.push_back(1ll * a + b);
prY.push_back(1ll * a - b + INF);
prY.push_back(1ll * a + b - 2 * c + INF);
}
}
prX.push_back(INF * 3);
prX.push_back(-1);
prY.push_back(INF * 3);
prY.push_back(-1);
sort(prX.begin(), prX.end());
sort(prY.begin(), prY.end());
prX.resize(unique(prX.begin(), prX.end()) - prX.begin());
prY.resize(unique(prY.begin(), prY.end()) - prY.begin());
int N = prX.size(), M = prY.size();
int CX[N + 1][M + 1]{}, CY[N + 1][M + 1]{};
for(auto &[a, b, c, d] : A)
{
if(b < c)
{
int x1 = lower_bound(prX.begin(), prX.end(), 1ll * a + b) - prX.begin();
int x2 = lower_bound(prX.begin(), prX.end(), 1ll * a - b + 2 * c) - prX.begin();
int y = lower_bound(prY.begin(), prY.end(), 1ll * a - b + INF) - prY.begin();
for(int j = x1; j < x2; ++j) CX[j][y] = max(CX[j][y], d / 2);
}
else
{
int x = lower_bound(prX.begin(), prX.end(), 1ll * a + b) - prX.begin();
int y1 = lower_bound(prY.begin(), prY.end(), 1ll * a - b + INF) - prY.begin();
int y2 = lower_bound(prY.begin(), prY.end(), 1ll * a + b - 2 * c + INF) - prY.begin();
for(int j = y1; j < y2; ++j) CY[x][j] = max(CY[x][j], d / 2);
}
}
long long dp[N + 1][M + 1]{};
for(int i = N; i >= 0; --i)
{
for(int j = M; j >= 0; --j)
{
if(i < N) dp[i][j] = max(dp[i][j], dp[i + 1][j] + 1ll * CX[i][j] * (prX[i + 1] - prX[i]));
if(j < M) dp[i][j] = max(dp[i][j], dp[i][j + 1] + 1ll * CY[i][j] * (prY[j + 1] - prY[j]));
}
}
// for(int i = 0; i <= N; ++i)
// {
// for(int j = 0; j <= M; ++j)
// cout << dp[i][j] << ' ';
// cout << endl;
// }
vector<pll> lsX[N + 1][M + 1], lsY[N + 1][M + 1];
for(int i = 0; i < T; ++i)
{
int x, y; cin >> x >> y;
int xi = lower_bound(prX.begin(), prX.end(), x + y) - prX.begin();
int yi = lower_bound(prY.begin(), prY.end(), x - y + INF) - prY.begin();
lsX[xi][yi].push_back({prX[xi] - x - y, i});
lsY[xi][yi].push_back({prY[yi] - x + y - INF, i});
}
vector<line> S;
long long ans[T]{};
for(int i = 1; i <= N; ++i)
{
S.clear();
S.emplace_back();
for(int j = M; j >= 0; --j)
{
line tmp;
tmp.a = CX[i - 1][j];
tmp.b = dp[i][j];
while(S.size() >= 2)
{
long long x = S[S.size() - 1].b - S[S.size() - 2].b;
long long y = S[S.size() - 2].a - S[S.size() - 1].a;
long long z = tmp.b - S[S.size() - 1].b;
long long w = S[S.size() - 1].a - tmp.a;
if(w <= 0 || x * w > y * z) S.pop_back();
else break;
}
if(S.back().b == tmp.b) S.back().a = max(S.back().a, tmp.a);
else if(S.back().a <= tmp.a) S.back() = tmp;
else S.push_back(tmp);
for(auto [x, q] : lsX[i][j])
{
int s = 0, e = S.size();
while(s + 1 < e)
{
int mid = s + e >> 1;
long long y = S[mid].b - S[mid - 1].b;
long long z = S[mid - 1].a - S[mid].a;
if(x * z < y) s = mid;
else e = mid;
}
ans[q] = max(ans[q], S[s].eval(x));
}
}
}
for(int j = 1; j <= M; ++j)
{
S.clear();
S.emplace_back();
for(int i = N; i >= 0; --i)
{
line tmp;
tmp.a = CY[i][j - 1];
tmp.b = dp[i][j];
while(S.size() >= 2)
{
long long x = S[S.size() - 1].b - S[S.size() - 2].b;
long long y = S[S.size() - 2].a - S[S.size() - 1].a;
long long z = tmp.b - S[S.size() - 1].b;
long long w = S[S.size() - 1].a - tmp.a;
if(w <= 0 || x * w > y * z) S.pop_back();
else break;
}
if(S.back().b == tmp.b) S.back().a = max(S.back().a, tmp.a);
else if(S.back().a <= tmp.a) S.back() = tmp;
else S.push_back(tmp);
for(auto [x, q] : lsY[i][j])
{
int s = 0, e = S.size();
while(s + 1 < e)
{
int mid = s + e >> 1;
long long y = S[mid].b - S[mid - 1].b;
long long z = S[mid - 1].a - S[mid].a;
if(x * z < y) s = mid;
else e = mid;
}
ans[q] = max(ans[q], S[s].eval(x));
}
}
}
for(auto i : ans) cout << i << '\n';
}
Compilation message
bodyguard.cpp: In function 'int main()':
bodyguard.cpp:137:33: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
137 | int mid = s + e >> 1;
| ~~^~~
bodyguard.cpp:175:33: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
175 | int mid = s + e >> 1;
| ~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7183 ms |
769748 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1893 ms |
1106964 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1893 ms |
1106964 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1893 ms |
1106964 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7183 ms |
769748 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
