Submission #624415

#TimeUsernameProblemLanguageResultExecution timeMemory
624415maomao90Bodyguard (JOI21_bodyguard)C++17
0 / 100
8683 ms704048 KiB
// Hallelujah, praise the one who set me free // Hallelujah, death has lost its grip on me // You have broken every chain, There's salvation in your name // Jesus Christ, my living hope #include <bits/stdc++.h> using namespace std; #define REP(i, s, e) for (int i = (s); i < (e); i++) #define RREP(i, s, e) for (int i = (s); i >= (e); i--) template <class T> inline bool mnto(T& a, T b) {return a > b ? a = b, 1 : 0;} template <class T> inline bool mxto(T& a, T b) {return a < b ? a = b, 1: 0;} typedef long long ll; typedef long double ld; #define FI first #define SE second typedef pair<int, int> ii; typedef pair<ll, ll> pll; typedef tuple<int, int, int> iii; #define ALL(_a) _a.begin(), _a.end() #define SZ(_a) (int) _a.size() #define pb push_back typedef vector<int> vi; typedef vector<ll> vll; typedef vector<ii> vii; typedef vector<iii> viii; #ifndef DEBUG #define cerr if (0) cerr #endif const int INF = 1000000005; const ll LINF = 1000000000000000005ll; const int MAXN = 2805; const int MAXQ = 3000005; struct thing { int a, s, e, c; }; struct line { ll m, c; bool operator< (const line &o) const { return m < o.m; } ll isect(const line &o) const { return (c - o.c) / (o.m - m); } ll eval(ll x) { return m * x + c; } }; int n, q; vector<thing> hor, ver; vi vy, vx; int adj[MAXN * 3][MAXN * 3][2]; ll dist[MAXN * 3][MAXN * 3]; iii qry[MAXQ]; ll ans[MAXQ]; viii dqry[MAXN * 3]; vector<pair<line, int>> dupd[MAXN * 3]; void dnc(viii qry, vector<pair<line, int>> upd, int lo, int hi) { if (qry.empty()) { return; } assert(!upd.empty()); if (lo == hi) { assert(SZ(upd) == 1); mxto(ans[get<2>(qry[0])], upd[0].FI.eval(get<0>(qry[0]))); return; } viii lqry, rqry; vector<pair<line, int>> lupd, rupd; int mid = lo + hi >> 1; for (iii q : qry) { if (get<1>(q) <= mid) { lqry.pb(q); } else { rqry.pb(q); } } for (pair<line, int> u : upd) { if (u.SE <= mid) { lupd.pb(u); } else { rupd.pb(u); } } deque<line> hull; auto insert = [&] (line l) { if (!hull.empty() && l.m == hull.back().m) { if (l.c >= hull.back().c) { hull.pop_back(); } else { return; } } int n = SZ(hull); while (n >= 2 && l.isect(hull[n - 1]) <= hull[n - 1].isect(hull[n - 2])) { hull.pop_back(); n--; } hull.pb(l); }; auto ask = [&] (ll x) { while (SZ(hull) >= 2 && hull[1].eval(x) >= hull[0].eval(x)) { hull.pop_front(); } return hull[0].eval(x); }; for (pair<line, int> u : rupd) { insert(u.FI); } for (auto [x, _, id] : lqry) { mxto(ans[id], ask(x)); } dnc(lqry, lupd, lo, mid); dnc(rqry, rupd, mid + 1, hi); } int main() { #ifndef DEBUG ios::sync_with_stdio(0), cin.tie(0); #endif cin >> n >> q; REP (i, 0, n) { int t, a, b, c; cin >> t >> a >> b >> c; if (a < b) { hor.pb({t - a, a + t, b + t + (b - a), c / 2}); } else { ver.pb({a + t, t - a, t + (a - b) - b, c / 2}); } } for (auto [a, s, e, c] : ver) { vy.pb(s); vy.pb(e); } for (auto [a, s, e, c] : hor) { vy.pb(a); } sort(ALL(vy)); vy.resize(unique(ALL(vy)) - vy.begin()); for (auto [a, s, e, c] : hor) { vx.pb(s); vx.pb(e); } for (auto [a, s, e, c] : ver) { vx.pb(a); } sort(ALL(vx)); vx.resize(unique(ALL(vx)) - vx.begin()); for (auto [a, s, e, c] : hor) { int na = lower_bound(ALL(vy), a) - vy.begin(), ns = lower_bound(ALL(vx), s) - vx.begin(), ne = lower_bound(ALL(vx), e) - vx.begin(); REP (i, ns, ne) { adj[na][i][0] = c; } } for (auto [a, s, e, c] : ver) { int na = lower_bound(ALL(vx), a) - vx.begin(), ns = lower_bound(ALL(vy), s) - vy.begin(), ne = lower_bound(ALL(vy), e) - vy.begin(); cerr << s << ' ' << e << ' ' << ns << ' ' << ne << '\n'; REP (i, ns, ne) { adj[i][na][1] = c; } } RREP (i, SZ(vy) - 1, 0) { RREP (j, SZ(vx) - 1, 0) { if (j + 1 < SZ(vx)) { mxto(dist[i][j], dist[i][j + 1] + (ll) adj[i][j][0] * (vx[j + 1] - vx[j])); } if (i + 1 < SZ(vy)) { mxto(dist[i][j], dist[i + 1][j] + (ll) adj[i][j][1] * (vy[i + 1] - vy[i])); } cerr << vy[i] << ' ' << vx[j] << ": " << dist[i][j] << '\n'; } } REP (i, 0, q) { int t, x; cin >> t >> x; qry[i] = {t + x, t - x, i}; } REP (i, 0, q) { auto [x, y, id] = qry[i]; int lby = lower_bound(ALL(vy), y) - vy.begin(), lbx = lower_bound(ALL(vx), x) - vx.begin(); if (lby >= SZ(vy)) { continue; } dqry[lby].pb({vy[lby] - y, lbx, id}); /* while (ptr[lby] >= lbx) { hulls[lby].insert({adj[lby][ptr[lby]][1], dist[lby][ptr[lby]]}); ptr[lby]--; } mxto(ans[id], hulls[lby].qry(vy[lby] - y)); */ } REP (i, 0, SZ(vy)) { REP (j, 0, SZ(vx)) { dupd[i].pb({line{i == 0 ? 0 : adj[i - 1][j][1], dist[i][j]}, j}); } } REP (i, 0, SZ(vy)) { sort(ALL(dqry[i])); sort(ALL(dupd[i])); dnc(dqry[i], dupd[i], 0, SZ(vx) - 1); } REP (i, 0, SZ(vx)) { dqry[i].clear(); dupd[i].clear(); } REP (i, 0, q) { auto [x, y, id] = qry[i]; int lby = lower_bound(ALL(vy), y) - vy.begin(), lbx = lower_bound(ALL(vx), x) - vx.begin(); if (lbx >= SZ(vx)) { continue; } dqry[lbx].pb({vx[lbx] - x, lby, id}); /* while (ptr[lbx] >= lby) { hulls[lbx].insert({adj[lbx][ptr[lbx]][0], dist[lbx][ptr[lbx]]}); ptr[lbx]--; } mxto(ans[id], hulls[lbx].qry(vx[lbx] - x)); */ } REP (i, 0, SZ(vy)) { REP (j, 0, SZ(vx)) { dupd[j].pb({line{j == 0 ? 0 : adj[i][j - 1][0], dist[i][j]}, i}); } } REP (i, 0, SZ(vx)) { sort(ALL(dqry[i])); sort(ALL(dupd[i])); dnc(dqry[i], dupd[i], 0, SZ(vy) - 1); } REP (i, 0, q) { cout << ans[i] << '\n'; } return 0; } /* 2 2 1 2 1 4 3 1 3 2 1 2 3 3 */

Compilation message (stderr)

bodyguard.cpp: In function 'void dnc(viii, std::vector<std::pair<line, int> >, int, int)':
bodyguard.cpp:77:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   77 |     int mid = lo + hi >> 1;
      |               ~~~^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...