#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair < int, int > pii;
typedef pair < ll, ll > pll;
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define SZ(x) (int)x.size()
#define Mp make_pair
#define endl "\n"
#define fast_io ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define int ll
const int M = 3e3 + 10;
const int N = 4e4 + 10;
const int N2 = 3e6 + 10;
const int LOG = 20;
const ll mod = 1e9 + 7;
const ll inf = 4e9;
int n, q, T[M], T2[M], fir[M], sec[M], Qa[N2], Qb[N2], C[M], dp[N][N], R[N][N], U[N][N];
vector < int > cmx, cmy;
void Add(int a, int b)
{
cmx.push_back(a);
cmy.push_back(b);
}
inline int lwrx(int a) { return lower_bound(all(cmx), a) - cmx.begin(); }
inline int lwry(int a) { return lower_bound(all(cmy), a) - cmy.begin(); }
signed main()
{
fast_io;
cin >> n >> q;
for(int i = 1; i <= n; i ++)
{
cin >> T[i] >> fir[i] >> sec[i] >> C[i];
T2[i] = T[i] + abs(fir[i] - sec[i]);
C[i] /= 2;
Add(T[i] + fir[i], T[i] - fir[i]);
Add(T2[i] + sec[i], T2[i] - sec[i]);
}
for(int i = 1; i <= q; i ++)
{
cin >> Qa[i] >> Qb[i];
Add(Qa[i] + Qb[i], Qa[i] - Qb[i]);
}
Add(inf, inf);
sort(all(cmx));
sort(all(cmy));
cmx.resize(unique(all(cmx)) - cmx.begin());
cmy.resize(unique(all(cmy)) - cmy.begin());
assert(SZ(cmx) < N);
assert(SZ(cmy) < N);
int sz1 = SZ(cmx), sz2 = SZ(cmy);
for(int i = 1; i <= n; i ++)
{
if(fir[i] < sec[i]) /// going up
{
int y = lwry(T[i] - fir[i]);
int l = lwrx(T[i] + fir[i]), r = lwrx(T2[i] + sec[i]);
for(int j = l; j < r; j ++)
{
U[j][y] = max(U[j][y], C[i]);
}
}
else /// going right
{
int x = lwrx(T[i] + fir[i]);
int l = lwry(T[i] - fir[i]), r = lwry(T2[i] - sec[i]);
for(int j = l; j < r; j ++)
{
R[x][j] = max(R[x][j], C[i]);
}
}
}
for(int i = sz1 - 1; ~i; i --)
{
for(int j = sz2 - 1; ~j; j --)
{
if(i + 1 < sz1)
{
dp[i][j] = max(dp[i][j], dp[i + 1][j] + U[i][j] * (cmx[i + 1] - cmx[i]));
}
if(j + 1 < sz2)
{
dp[i][j] = max(dp[i][j], dp[i][j + 1] + R[i][j] * (cmy[j + 1] - cmy[j]));
}
}
}
for(int i = 1; i <= q; i ++)
{
cout << dp[lwrx(Qa[i] + Qb[i])][lwry(Qa[i] - Qb[i])] << endl;
}
return 0;
}
Compilation message
/usr/bin/ld: failed to convert GOTPCREL relocation; relink with --no-relax
collect2: error: ld returned 1 exit status
