#include<bits/stdc++.h>
using ll = long long;
using namespace std;
#define pll pair <ll,ll>
#define fi first
#define se second
#define MP make_pair
#define sz(a) (ll((a).size()))
#define BIT(mask,i) (((mask) >> (i))&1)
#define MASK(i) (1LL << (i))
ll n,q;
const ll MAXN = 2827;
const ll MAX_Q = 3e6+100;
const ll INF = 1e18;
ll V[MAXN],A[MAXN],B[MAXN],C[MAXN],D[MAXN];
ll P[MAX_Q],X[MAX_Q];
ll ans[MAX_Q];
struct query{
ll r,c,id;
};
query all[MAX_Q];
ll inter(pll x1,pll x2){
swap(x1,x2);
if (x1.fi==x2.fi)return (x1.se < x2.se ? -INF : INF);
return (x2.se-x1.se)/(x1.fi-x2.fi);
}
int main(){
ios_base::sync_with_stdio(0);cin.tie(nullptr);
cin>>n>>q;
for (ll i = 1;i <= n;i ++){
cin>>C[i]>>A[i]>>B[i]>>V[i];
D[i] = C[i] + abs(A[i]-B[i]);
}
for (ll i = 1;i <= q;i ++){
cin>>P[i]>>X[i];
}
vector <ll> row,col;
for (ll i = 1;i <= n;i ++){
row.push_back(C[i]+A[i]);
row.push_back(D[i]+B[i]);
col.push_back(C[i]-A[i]);
col.push_back(D[i]-B[i]);
}
sort(row.begin(),row.end());
row.resize(unique(row.begin(),row.end())-row.begin());
sort(col.begin(),col.end());
col.resize(unique(col.begin(),col.end())-col.begin());
vector <vector <ll> > ar,ac,dp;
dp=ar=ac=vector<vector <ll> > (sz(row),vector <ll>(sz(col)));
for (ll i = 1;i <= n;i ++){
if (A[i] > B[i]){
ll x = lower_bound(row.begin(),row.end(),C[i]+A[i])-row.begin();
for (ll j = 0;j < sz(col);j ++){
if (C[i] - A[i] < col[j] && D[i] - B[i] >= col[j]){
ar[x][j] = max(V[i],ar[x][j]);
}
}
}
else{
ll y = lower_bound(col.begin(),col.end(),C[i]-A[i])-col.begin();
for (ll j = 0;j < sz(row);j ++){
if (C[i] + A[i] < row[j] && row[j] <= D[i] + B[i]){
ac[j][y] = max(ac[j][y],V[i]);
}
}
}
}
for (ll i = sz(row)-1; i >= 0; i --){
for (ll j = sz(col)-1; j >= 0; j --){
if (i)dp[i-1][j] = max(dp[i-1][j],dp[i][j] + ac[i][j] * (row[i] - row[i-1]));
if (j)dp[i][j-1] = max(dp[i][j-1],dp[i][j] + ar[i][j] * (col[j] - col[j-1]));
}
}
// for (ll i = 0;i < sz(row);i ++){
// for (ll j = 0;j < sz(col);j ++){
// cout<<"DP "<<row[i]<<' '<<col[j]<<" : "<<dp[i][j]<<endl;
// }
// }
for (ll i = 1;i <= q;i ++){
all[i] = {P[i]+X[i],P[i]-X[i],i};
// cout<<P[i]+X[i]<<' '<<P[i]-X[i]<<endl;
}
// cout<<row[5]<<' '<<col[3]<<' '<<ar[5][3]<<' '<<ac[5][3]<<endl;
sort(all+1,all+1+q,[](query a1,query a2){return MP(a1.r,-a1.c) < MP(a2.r,-a2.c);});
for (ll i = 0,ptr = 0;i < sz(row);i ++){
while (ptr <= q && all[ptr].r <= row[i] && all[ptr].c > col.back())ptr++;
vector <pll> hull;
for (ll j = sz(col)-1;j >= 0;j --){
ll tmp = j?col[j-1]:-INF;
while (sz(hull) && hull.back().fi <= ac[i][j] && hull.back().se <= dp[i][j])hull.pop_back();
while (sz(hull) >= 2 && inter(hull[sz(hull)-2],hull[sz(hull)-1]) <= inter(hull[sz(hull)-1],MP(ac[i][j],dp[i][j])))hull.pop_back();
hull.push_back(MP(ac[i][j],dp[i][j]));
while (ptr <= q && all[ptr].r <= row[i] && all[ptr].c > tmp && all[ptr].c <= col[j]){
// if (all[ptr].id == 1){cout<<row[i]<<' '<<col[j]<<endl;for (auto x:hull)cout<<x.fi<<' '<<x.se<<endl;}
ll x = row[i] - all[ptr].r;
ll l = 0,r = sz(hull) - 1;
while (l <= r){
ll mid = (l + r) >> 1;
if (mid == 0 || hull[mid].fi * x + hull[mid].se > hull[mid-1].fi * x + hull[mid-1].se) l = mid + 1;
else r = mid - 1;
}
ans[all[ptr].id] = max(ans[all[ptr].id],hull[r].fi * x + hull[r].se);
ptr++;
}
}
}
sort(all+1,all+1+q,[](query a1,query a2){return MP(a1.c,-a1.r) < MP(a2.c,-a2.r);});
for (ll i = 0,ptr = 0;i < sz(col);i ++){
while (ptr <= q && all[ptr].c <= col[i] && all[ptr].r > row.back())ptr++;
vector <pll> hull;
for (ll j = sz(row)-1;j >= 0;j --){
ll tmp = j?row[j-1]:-INF;
while (sz(hull) && hull.back().fi <= ar[j][i] && hull.back().se <= dp[j][i])hull.pop_back();
while (sz(hull) >= 2 && inter(hull[sz(hull)-2],hull[sz(hull)-1]) <= inter(hull[sz(hull)-1],MP(ar[j][i],dp[j][i])))hull.pop_back();
hull.push_back(MP(ar[j][i],dp[j][i]));
while (ptr <= q && all[ptr].c <= col[i] && all[ptr].r > tmp && all[ptr].r <= row[j]){
ll x = col[i] - all[ptr].c;
ll l = 0,r = sz(hull) - 1;
while (l <= r){
ll mid = (l + r) >> 1;
if (mid == 0 || hull[mid].fi * x + hull[mid].se > hull[mid-1].fi * x + hull[mid-1].se) l = mid + 1;
else r = mid - 1;
}
ans[all[ptr].id] = max(ans[all[ptr].id],hull[r].fi * x + hull[r].se);
ptr++;
}
}
}
for (ll i = 1;i <= q;i ++)cout<<ans[i]/2<<'\n';
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1524 ms |
398676 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
742 ms |
415564 KB |
Output is correct |
| 2 |
Correct |
751 ms |
415316 KB |
Output is correct |
| 3 |
Correct |
771 ms |
409680 KB |
Output is correct |
| 4 |
Incorrect |
2 ms |
860 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
742 ms |
415564 KB |
Output is correct |
| 2 |
Correct |
751 ms |
415316 KB |
Output is correct |
| 3 |
Correct |
771 ms |
409680 KB |
Output is correct |
| 4 |
Incorrect |
2 ms |
860 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
742 ms |
415564 KB |
Output is correct |
| 2 |
Correct |
751 ms |
415316 KB |
Output is correct |
| 3 |
Correct |
771 ms |
409680 KB |
Output is correct |
| 4 |
Incorrect |
2 ms |
860 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1524 ms |
398676 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
