#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXQ = 3000005;
const ll inf = 1e18;
ll ans[MAXQ];
vector<ll> xdisc, ydisc;
struct line{
ll m, c;
ll eval(ll x){
return m * x + c;
}
};
struct node{
ll s, e, m; line ln;
node *l = nullptr, *r = nullptr;
node(ll _s, ll _e) {
s = _s, e = _e, m = (s + e) >> 1, ln = { 0, -inf };
}
void makechild() {
if (l == nullptr) {
l = new node(s, m); r = new node(m, e);
}
}
void update(line x) {
if (x.eval(m) > ln.eval(m)) swap(ln, x);
if (s + 1 == e || x.c == -inf) return;
if (x.eval(s) > ln.eval(s)) {
makechild(); l->update(x);
}
else if (x.eval(e) > ln.eval(e)) {
makechild(); r->update(x);
}
}
ll query(ll x) {
if (l == nullptr || s + 1 == e) return ln.eval(x);
if (x < m) return max(ln.eval(x), l->query(x));
else return max(ln.eval(x), r->query(x));
}
};
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int nums, queries; cin >> nums >> queries;
vector<tuple<ll, ll, ll, ll>> pv[2];
for (int i = 0; i < nums; i++){
ll t, a, b, c, s, e, o; cin >> t >> a >> b >> c;
c >>= 1;
if (a < b){
s = t + a, e = s + 2 * (b - a), o = t - a;
xdisc.push_back(s); xdisc.push_back(e); ydisc.push_back(o);
pv[0].push_back({s, e, o, c});
}
else{
s = t - a, e = s + 2 * (a - b), o = t + a;
ydisc.push_back(s); ydisc.push_back(e); xdisc.push_back(o);
pv[1].push_back({s, e, o, c});
}
}
sort(xdisc.begin(), xdisc.end());
xdisc.resize(distance(xdisc.begin(), unique(xdisc.begin(), xdisc.end())));
sort(ydisc.begin(), ydisc.end());
ydisc.resize(distance(ydisc.begin(), unique(ydisc.begin(), ydisc.end())));
int xsz = xdisc.size(), ysz = ydisc.size();
vector<vector<ll>> hpay(ysz, vector<ll>(xsz));
vector<vector<vector<pair<bool, ll>>>> hpv(ysz, vector<vector<pair<bool, ll>>>(xsz + 1));
for (auto [s, e, o, c] : pv[0]){
s = lower_bound(xdisc.begin(), xdisc.end(), s) - xdisc.begin();
e = lower_bound(xdisc.begin(), xdisc.end(), e) - xdisc.begin();
o = lower_bound(ydisc.begin(), ydisc.end(), o) - ydisc.begin();
hpv[o][s + 1].push_back({0, c}); hpv[o][e + 1].push_back({1, c});
}
for (int o = 0; o < ysz; o++){
multiset<ll> s; s.insert(0);
for (int i = 0; i < xsz; i++){
for (auto [typ, c] : hpv[o][i]){
if (typ) s.erase(s.find(c));
else s.insert(c);
}
hpay[o][i] = *s.rbegin();
}
}
vector<vector<ll>> vpay(xsz, vector<ll>(xsz));
vector<vector<vector<pair<bool, ll>>>> vpv(xsz, vector<vector<pair<bool, ll>>>(ysz + 1));
for (auto [s, e, o, c] : pv[1]){
s = lower_bound(ydisc.begin(), ydisc.end(), s) - ydisc.begin();
e = lower_bound(ydisc.begin(), ydisc.end(), e) - ydisc.begin();
o = lower_bound(xdisc.begin(), xdisc.end(), o) - xdisc.begin();
vpv[o][s + 1].push_back({0, c}); vpv[o][e + 1].push_back({1, c});
}
for (int o = 0; o < xsz; o++){
multiset<ll> s; s.insert(0);
for (int i = 0; i < ysz; i++){
for (auto [typ, c] : vpv[o][i]){
if (typ) s.erase(s.find(c));
else s.insert(c);
}
vpay[o][i] = *s.rbegin();
}
}
vector<vector<ll>> dp(xsz, vector<ll>(ysz));
for (int x = xsz - 1; x >= 0; x--)
for (int y = ysz - 1; y >= 0; y--){
dp[x][y] = 0;
if (x != xsz - 1) dp[x][y] = max(dp[x][y], dp[x + 1][y] + hpay[y][x + 1] * (xdisc[x + 1] - xdisc[x]));
if (y != ysz - 1) dp[x][y] = max(dp[x][y], dp[x][y + 1] + vpay[x][y + 1] * (ydisc[y + 1] - ydisc[y]));
}
vector<vector<tuple<int, ll, int>>> hqv(ysz), vqv(xsz);
for (int q = 0; q < queries; q++){
ll t, p; cin >> t >> p;
ll x = t + p, y = t - p;
int xid = lower_bound(xdisc.begin(), xdisc.end(), x) - xdisc.begin();
int yid = lower_bound(ydisc.begin(), ydisc.end(), y) - ydisc.begin();
if (xid != xsz && yid != ysz){
hqv[yid].push_back({xid, y, q}); vqv[xid].push_back({yid, x, q});
}
}
for (int i = 0; i < ysz; i++){
sort(hqv[i].begin(), hqv[i].end(), greater<tuple<int, ll, int>>());
int curr = xsz;
if (i != 0){
node *root = new node(0, ydisc[i] - ydisc[i - 1]);
for (auto [id, y, q] : hqv[i]){
while (curr > id){
curr--; root->update({vpay[curr][i], dp[curr][i]});
}
ans[q] = max(ans[q], root->query(ydisc[i] - y));
}
}
else{
ll maxv = 0;
for (auto [id, y, q] : hqv[i]){
while (curr > id){
curr--; maxv = max(maxv, dp[curr][i]);
}
ans[q] = max(ans[q], maxv);
}
}
}
for (int i = 0; i < xsz; i++){
sort(vqv[i].begin(), vqv[i].end(), greater<tuple<int, ll, int>>());
int curr = ysz;
if (i != 0){
node *root = new node(0, xdisc[i] - xdisc[i - 1]);
for (auto [id, x, q] : vqv[i]){
while (curr > id){
curr--; root->update({hpay[curr][i], dp[i][curr]});
}
ans[q] = max(ans[q], root->query(xdisc[i] - x));
}
}
else{
ll maxv = 0;
for (auto [id, x, q] : vqv[i]){
while (curr > id){
curr--; maxv = max(maxv, dp[i][curr]);
}
ans[q] = max(ans[q], maxv);
}
}
}
for (int q = 0; q < queries; q++) cout << ans[q] << '\n';
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |