#include <bits/stdc++.h>
#define IO_OP std::ios::sync_with_stdio(0); std::cin.tie(0);
#define F first
#define S second
#define V vector
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(v) int((v).size())
#define ALL(v) (v).begin(), (v).end()
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;
string _reset = "\u001b[0m", _yellow = "\u001b[33m", _bold = "\u001b[1m";
void DBG() { cerr << "]" << _reset << endl; }
template<class H, class...T> void DBG(H h, T ...t) {
cerr << to_string(h);
if(sizeof ...(t)) cerr << ", ";
DBG(t...);
}
#ifdef CHEISSMART
#define debug(...) cerr << _yellow << _bold << "Line(" << __LINE__ << ") -> [" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__)
#else
#define debug(...)
#endif
const int INF = 1e9 + 7;
struct DS {
V<pair<ll, ll>> tt;
void insert(ll m, ll b) {
tt.EB(m, b);
}
ll qry(ll x) {
ll mx = 0;
for(auto[m, b]:tt) {
mx = max(mx, m * x + b);
}
return mx;
}
};
void claim(bool b) {
if(!b) while(1);
}
signed main()
{
IO_OP;
int n, q;
cin >> n >> q;
V<pair<pair<pi, pi>, int>> ev;
vi xs, ys;
for(int i = 0; i < n; i++) {
int t, x, y, c, d;
cin >> t >> x >> y >> c, d = abs(x - y);
claim(c % 2 == 0);
c /= 2;
pi a = {t + x, t - x};
pi b = {t + d + y, t + d - y};
ev.EB(MP(a, b), c);
xs.PB(a.F), ys.PB(a.S);
xs.PB(b.F), ys.PB(b.S);
assert((a.F == b.F || a.S == b.S) && a != b);
if(a.F == b.F) {
assert(a.S < b.S);
} else {
assert(a.F < b.F);
}
}
sort(ALL(xs)), xs.resize(unique(ALL(xs)) - xs.begin());
sort(ALL(ys)), ys.resize(unique(ALL(ys)) - ys.begin());
V<vi> dx, dy;
dx = dy = V<vi>(SZ(xs), vi(SZ(ys)));
V<V<ll>> dp = V<V<ll>>(SZ(xs), V<ll>(SZ(ys)));
for(auto[pab, c]:ev) {
auto[a, b] = pab;
a.F = lower_bound(ALL(xs), a.F) - xs.begin();
a.S = lower_bound(ALL(ys), a.S) - ys.begin();
b.F = lower_bound(ALL(xs), b.F) - xs.begin();
b.S = lower_bound(ALL(ys), b.S) - ys.begin();
claim((a.F == b.F || a.S == b.S) && a != b);
if(a.F == b.F) {
claim(a.S < b.S);
for(int i = a.S; i < b.S; i++)
dy[a.F][i] = max(dy[a.F][i], c);
} else {
claim(a.F < b.F);
for(int i = a.F; i < b.F; i++)
dx[i][a.S] = max(dx[i][a.S], c);
}
}
for(int i = SZ(xs) - 1; i >= 0; i--) {
for(int j = SZ(ys) - 1; j >= 0; j--) {
if(i + 1 < SZ(xs)) dp[i][j] = max(dp[i][j], dp[i + 1][j] + 1LL * dx[i][j] * (xs[i + 1] - xs[i]));
if(j + 1 < SZ(ys)) dp[i][j] = max(dp[i][j], dp[i][j + 1] + 1LL * dy[i][j] * (ys[j + 1] - ys[j]));
}
}
V<V<V<pair<pi, int>>>> qq(SZ(xs), V<V<pair<pi, int>>>(SZ(ys)));
V<ll> ans(q);
for(int i = 0; i < q; i++) {
int t, x;
cin >> t >> x;
pi a = {t + x, t - x};
int he = lower_bound(ALL(xs), a.F) - xs.begin();
int be = lower_bound(ALL(ys), a.S) - ys.begin();
if(he < SZ(xs) && be < SZ(ys)) {
qq[he][be].EB(a, i);
}
}
for(int j = 0; j < SZ(ys); j++) {
DS ds;
for(int i = SZ(xs) - 1; i >= 0; i--) {
int c = j ? dy[i][j - 1] : 0;
ds.insert(c, dp[i][j]);
for(auto[a, qi]:qq[i][j])
ans[qi] = max(ans[qi], ds.qry(ys[j] - a.S));
}
}
for(int i = 0; i < SZ(xs); i++) {
DS ds;
for(int j = SZ(ys) - 1; j >= 0; j--) {
int c = i ? dx[i - 1][j] : 0;
ds.insert(c, dp[i][j]);
for(auto[a, qi]:qq[i][j])
ans[qi] = max(ans[qi], ds.qry(xs[i] - a.F));
}
}
for(int i = 0; i < q; i++)
cout << ans[i] << '\n';
}
Compilation message
bodyguard.cpp: In member function 'll DS::qry(ll)':
bodyguard.cpp:40:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
40 | for(auto[m, b]:tt) {
| ^
bodyguard.cpp: In function 'int main()':
bodyguard.cpp:84:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
84 | for(auto[pab, c]:ev) {
| ^
bodyguard.cpp:85:7: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
85 | auto[a, b] = pab;
| ^
bodyguard.cpp:126:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
126 | for(auto[a, qi]:qq[i][j])
| ^
bodyguard.cpp:135:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
135 | for(auto[a, qi]:qq[i][j])
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14952 ms |
474228 KB |
Output is correct |
| 2 |
Correct |
15049 ms |
477392 KB |
Output is correct |
| 3 |
Correct |
4645 ms |
189940 KB |
Output is correct |
| 4 |
Correct |
3411 ms |
74876 KB |
Output is correct |
| 5 |
Execution timed out |
25109 ms |
764496 KB |
Time limit exceeded |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14952 ms |
474228 KB |
Output is correct |
| 2 |
Correct |
15049 ms |
477392 KB |
Output is correct |
| 3 |
Correct |
4645 ms |
189940 KB |
Output is correct |
| 4 |
Correct |
3411 ms |
74876 KB |
Output is correct |
| 5 |
Execution timed out |
25109 ms |
764496 KB |
Time limit exceeded |
| 6 |
Halted |
0 ms |
0 KB |
- |
