| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 583390 | AriaH | Bodyguard (JOI21_bodyguard) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 = 3 * M;
const int N2 = 3e6 + 10;
const int LOG = 20;
const ll mod = 1e9 + 7;
const ll inf = 4e9;
bool TYPE = 1;
struct Line
{///k -> shib m -> arz az mabda p -> noghte shoro baze mofid
mutable ll k, m, p;
bool operator<(const Line& o) const { return TYPE ? k < o.k : p < o.p; }
};
struct CHT : multiset<Line>
{
// (for doubles, use inf = 1/.0, div(a,b) = a/b)
static const ll inf = LLONG_MAX;
ll div(ll a, ll b) { /* floored division */ return a / b - ((a ^ b) < 0 && a % b); }
bool isect(iterator x, iterator y)
{
if (y == end()) return x->p = inf, 0;
if (x->k == y->k) x->p = x->m > y->m ? inf : -inf;
else x->p = div(y->m - x->m, x->k - y->k);
return x->p >= y->p;
}
void add(ll k, ll m)
{
auto z = insert({k, m, 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());
TYPE = 0 ; auto l = *lower_bound({0 , 0 , x}); TYPE = 1;
return l.k * x + l.m;
}
} row[N], col[N];
int n, q, T[M], T2[M], fir[M], sec[M], C[M], dp[N][N], R[N][N], U[N][N], Qa[N2], Qb[N2], Ans[N2], EX[N2], EY[N2];
vector < int > cmx, cmy;
vector < int > vec[N][N];
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]);
}
Add(inf, inf);
Add(-inf, -inf);
sort(all(cmx));
sort(all(cmy));
cmx.resize(unique(all(cmx)) - cmx.begin());
cmy.resize(unique(all(cmy)) - cmy.begin());
for(int i = 1; i <= q; i ++)
{
cin >> Qa[i] >> Qb[i];
int a = lwrx(Qa[i] + Qb[i]), b = lwry(Qa[i] - Qb[i]);
vec[a][b].push_back(i);
EX[i] = cmx[a] - (Qa[i] + Qb[i]);
EY[i] = cmy[b] - (Qa[i] - Qb[i]);
}
int sz1 = SZ(cmx), sz2 = SZ(cmy);
for(int i = 1; i <= n; i ++)
{
pii A = Mp(T[i] + fir[i], T[i] - fir[i]), B = Mp(T2[i] + sec[i], T2[i] - sec[i]);
A.F = lwrx(A.F);
A.S = lwry(A.S);
B.F = lwrx(B.F);
B.S = lwry(B.S);
if(A.F == B.F) /// going right
{
for(int j = A.S; j < B.S; j ++)
{
U[A.F][j] = max(U[A.F][j], C[i]);
}
}
else /// going up
{
for(int j = A.F; j < B.F; j ++)
{
R[j][A.S] = max(R[j][A.S], C[i]);
}
}
}
/*for(int i = 0; i < N; i ++)
{
row[i].add(0, 0);
col[i].add(0, 0);
}*/
for(int i = sz1 - 1; i > 0; i --)
{
for(int j = sz2 - 1; j > 0; j --)
{
if(i + 1 < sz1)
{
dp[i][j] = max(dp[i][j], dp[i + 1][j] + R[i][j] * (cmx[i + 1] - cmx[i]));
}
if(j + 1 < sz2)
{
dp[i][j] = max(dp[i][j], dp[i][j + 1] + U[i][j] * (cmy[j + 1] - cmy[j]));
}
col[i].add(R[i - 1][j], dp[i][j]);
row[j].add(U[i][j - 1], dp[i][j]);
for(auto id : vec[i][j])
{
Ans[id] = max(row[j].query(EY[id]), col[i].query(EX[id]));
}
}
}
for(int i = 1; i <= q; i ++)
{
cout << Ans[i] << endl;
}
return 0;
}