#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll
#define y1 zck_is_king
#define pii pair<int, int>
#define ull unsigned ll
#define f first
#define s second
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
#define SQ(x) (x)*(x)
#define MN(a,b) a = min(a,(__typeof__(a))(b))
#define MX(a,b) a = max(a,(__typeof__(a))(b))
#define pb push_back
#define REP(i,n) for (int i = 0; i<n; ++i)
#define RREP(i,n) for (int i = n-1; i>=0; --i)
#define REP1(i,n) for (int i = 1; i<=n; ++i)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#ifdef BALBIT
#define IOS()
#define bug(...) fprintf(stderr,"#%d (%s) = ",__LINE__,#__VA_ARGS__),_do(__VA_ARGS__);
template<typename T> void _do(T &&x){cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T &&x, S &&...y){cerr<<x<<", ";_do(y...);}
#else
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);
#define endl '\n'
#define bug(...)
#endif
const int iinf = 1e9+10;
const ll inf = 1ll<<60;
const ll mod = 1e9+7 ;
void GG(){cout<<"0\n"; exit(0);}
ll mpow(ll a, ll n, ll mo = mod){ // a^n % mod
ll re=1;
while (n>0){
if (n&1) re = re*a %mo;
a = a*a %mo;
n>>=1;
}
return re;
}
ll inv (ll b, ll mo = mod){
if (b==1) return b;
return (mo-mo/b) * inv(mo%b,mo) % mo;
}
const int maxn = 2800*2+5;
//ll xat[maxn], yat[maxn];
ll rt[maxn][maxn], dw[maxn][maxn]; // right (m++), down (n++)
ll dp[maxn][maxn];
struct seg{
signed l,r,h,c;
};
vector<seg> dseg, rseg;
vector<ll> dax, rax; // axis lines
ll ans[maxn];
struct ask{
int df, i;
};
vector<ask> dask[maxn][maxn], rask[maxn][maxn];
bool QTYPE=0;
struct Line {
mutable ll m, b, p;
bool operator<(const Line& o) const {
if (QTYPE) return p<o.p;
return m < o.m;
}
};
struct LineContainer : multiset<Line > {
const ll INF = LLONG_MAX;
ll div(ll A, ll B) {
return A / B - ((A ^ B) < 0 && A % B); }
bool isect(iterator x, iterator y) {
if (y == end()) { x->p = INF; return false; }
if (x->m == y->m) x->p = x->b > y->b ? INF : -INF;
else x->p = div(y->b - x->b, x->m - y->m);
return x->p >= y->p;}
void add(ll m, ll b) {
auto z = insert({m, b, 0}), y = z++, x = y;
while (isect(y, z)) z = erase(z);
if (x != begin() && isect(--x, y)) isect(x, y = erase(y));
while ((y = x) != begin() && (--x)->p >= y->p)
isect(x, erase(y));}
ll query(ll x) {
assert(!empty());
QTYPE=1; auto l = *lower_bound({0,0,x}); QTYPE = 0;
return l.m * x + l.b; }
};
signed main(){
IOS();
int n,q; cin>>n>>q;
REP(i,n) {
int t,a,b,c; cin>>t>>a>>b>>c;
if (a < b) {
// down segment
dseg.pb({t+a, t+b-a+b, t-a, c});
bug("down", t-a, t+a, t+b-a+b);
bug(c);
}else{
// right seg
rseg.pb({t-a, t+(a-b)-b, t+a, c});
bug("right", t+a, t-a, t+(a-b)-b);
bug(c);
}
}
for (auto s : dseg) {
dax.pb(s.h);
rax.pb(s.l);
rax.pb(s.r);
}
for (auto s : rseg) {
rax.pb(s.h);
dax.pb(s.l);
dax.pb(s.r);
}
SORT_UNIQUE(rax);
SORT_UNIQUE(dax);
auto getr = [&](ll x) {return lower_bound(ALL(rax), x) - rax.begin();};
auto getd = [&](ll x) {return lower_bound(ALL(dax), x) - dax.begin();};
for (auto s : dseg) {
// work on dw array
int L = getr(s.l), R = getr(s.r);
int H = getd(s.h);
for (int i = L; i<R; ++i) {
MX(dw[i][H], s.c);
}
}
for (auto s : rseg) {
// work on rt array
int L = getd(s.l), R = getd(s.r);
int H = getr(s.h);
for (int i = L; i<R; ++i) {
MX(rt[H][i], s.c);
}
}
int N = SZ(rax), M = SZ(dax);
for (int i = N-1; i>=0; --i) for (int j = M-1; j>=0; --j) {
if (i + 1 < N) {
MX(dp[i][j], dp[i+1][j] + (rax[i+1] - rax[i])*dw[i][j]);
}
if (j + 1 < M) {
MX(dp[i][j], dp[i][j+1] + (dax[j+1] - dax[j])*rt[i][j]);
}
bug(i,j,rax[i],dax[j],dp[i][j]);
}
REP(i, q) {
int t,x; cin>>t>>x;
int r = t+x, c = t-x;
int dpos = getd(c), rpos = getr(r);
bug(r,c,dpos,rpos);
dask[rpos][dpos].pb({dax[dpos] - c, i});
rask[rpos][dpos].pb({rax[rpos] - r, i});
}
REP(i,N) {
LineContainer hull;
for (int j = M-1; j>=0; --j) {
hull.add(i?dw[i-1][j]:0, dp[i][j]);
if (i) bug(i,j,dw[i-1][j], dp[i][j]);
for (ask aa : rask[i][j]) {
bug(aa.i, aa.df, hull.query(aa.df));
MX(ans[aa.i], hull.query(aa.df));
}
}
}
REP(j,M) {
LineContainer hull;
for (int i = N-1; i>=0; --i) {
hull.add(j?rt[i][j-1]:0, dp[i][j]);
for (ask aa : dask[i][j]) {
bug(aa.i, aa.df, hull.query(aa.df));
MX(ans[aa.i], hull.query(aa.df));
}
}
}
REP(i,q) {
cout<<ans[i]/2<<endl;
}
}
Compilation message
bodyguard.cpp: In function 'int main()':
bodyguard.cpp:112:23: warning: narrowing conversion of '(t + a)' from 'long long int' to 'int' [-Wnarrowing]
112 | dseg.pb({t+a, t+b-a+b, t-a, c});
| ~^~
bodyguard.cpp:112:32: warning: narrowing conversion of '(((t + b) - a) + b)' from 'long long int' to 'int' [-Wnarrowing]
112 | dseg.pb({t+a, t+b-a+b, t-a, c});
| ~~~~~^~
bodyguard.cpp:112:37: warning: narrowing conversion of '(t - a)' from 'long long int' to 'int' [-Wnarrowing]
112 | dseg.pb({t+a, t+b-a+b, t-a, c});
| ~^~
bodyguard.cpp:112:41: warning: narrowing conversion of 'c' from 'long long int' to 'int' [-Wnarrowing]
112 | dseg.pb({t+a, t+b-a+b, t-a, c});
| ^
bodyguard.cpp:117:23: warning: narrowing conversion of '(t - a)' from 'long long int' to 'int' [-Wnarrowing]
117 | rseg.pb({t-a, t+(a-b)-b, t+a, c});
| ~^~
bodyguard.cpp:117:34: warning: narrowing conversion of '((t + (a - b)) - b)' from 'long long int' to 'int' [-Wnarrowing]
117 | rseg.pb({t-a, t+(a-b)-b, t+a, c});
| ~~~~~~~^~
bodyguard.cpp:117:39: warning: narrowing conversion of '(t + a)' from 'long long int' to 'int' [-Wnarrowing]
117 | rseg.pb({t-a, t+(a-b)-b, t+a, c});
| ~^~
bodyguard.cpp:117:43: warning: narrowing conversion of 'c' from 'long long int' to 'int' [-Wnarrowing]
117 | rseg.pb({t-a, t+(a-b)-b, t+a, c});
| ^
/tmp/cclrNV7j.o: in function `GG()':
bodyguard.cpp:(.text+0x779): relocation truncated to fit: R_X86_64_PC32 against symbol `std::cout' defined in .bss._ZSt4cout section in /usr/lib/gcc/x86_64-linux-gnu/10/libstdc++.a(globals_io.o)
/tmp/cclrNV7j.o: in function `main':
bodyguard.cpp:(.text.startup+0x37): relocation truncated to fit: R_X86_64_PC32 against symbol `std::cin' defined in .bss._ZSt3cin section in /usr/lib/gcc/x86_64-linux-gnu/10/libstdc++.a(globals_io.o)
bodyguard.cpp:(.text.startup+0x3e): relocation truncated to fit: R_X86_64_PC32 against symbol `std::cin' defined in .bss._ZSt3cin section in /usr/lib/gcc/x86_64-linux-gnu/10/libstdc++.a(globals_io.o)
bodyguard.cpp:(.text.startup+0xf7): relocation truncated to fit: R_X86_64_PC32 against symbol `std::cin' defined in .bss._ZSt3cin section in /usr/lib/gcc/x86_64-linux-gnu/10/libstdc++.a(globals_io.o)
bodyguard.cpp:(.text.startup+0x7d2): relocation truncated to fit: R_X86_64_PC32 against symbol `std::cin' defined in .bss._ZSt3cin section in /usr/lib/gcc/x86_64-linux-gnu/10/libstdc++.a(globals_io.o)
bodyguard.cpp:(.text.startup+0xcd1): relocation truncated to fit: R_X86_64_PC32 against symbol `std::cout' defined in .bss._ZSt4cout section in /usr/lib/gcc/x86_64-linux-gnu/10/libstdc++.a(globals_io.o)
/tmp/cclrNV7j.o: in function `_GLOBAL__sub_I__Z2GGv':
bodyguard.cpp:(.text.startup+0xdcb): relocation truncated to fit: R_X86_64_PC32 against `.bss'
bodyguard.cpp:(.text.startup+0xde5): relocation truncated to fit: R_X86_64_PC32 against `.bss'
/usr/lib/gcc/x86_64-linux-gnu/10/libstdc++.a(vterminate.o): in function `__gnu_cxx::__verbose_terminate_handler()':
(.text._ZN9__gnu_cxx27__verbose_terminate_handlerEv+0x1e): relocation truncated to fit: R_X86_64_PC32 against `.bss._ZZN9__gnu_cxx27__verbose_terminate_handlerEvE11terminating'
(.text._ZN9__gnu_cxx27__verbose_terminate_handlerEv+0x2b): relocation truncated to fit: R_X86_64_PC32 against `.bss._ZZN9__gnu_cxx27__verbose_terminate_handlerEvE11terminating'
/usr/bin/ld: failed to convert GOTPCREL relocation; relink with --no-relax
collect2: error: ld returned 1 exit status
