Submission #624573

#TimeUsernameProblemLanguageResultExecution timeMemory
624573maomao90Bodyguard (JOI21_bodyguard)C++17
0 / 100
7739 ms308528 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 = 2800; const int MAXQ = 3000000; using line = pair<int, ll>; int n, q; vector<tuple<int, int, ll, int>> hor, ver; vll vy, vx; int adj[MAXN * 3 + 5][MAXN * 3 + 5][2]; ll dist[MAXN * 3 + 5][MAXN * 3 + 5]; ii qry[MAXQ + 5]; ll ans[MAXQ + 5]; viii dqry[MAXN * 3 + 5]; vector<pair<line, int>> dupd; deque<line> hull; void insert(line l) { if (!hull.empty() && l.FI == hull.back().FI) { if (l.SE >= hull.back().SE) { hull.pop_back(); } else { return; } } int n = SZ(hull); auto isbad = [&] (line a, line b, line c) { ll p1 = (b.SE - a.SE) / (a.FI - b.FI), p2 = (c.SE - b.SE) / (b.FI - c.FI); return p1 <= p2; }; while (n >= 2 && isbad(l, hull[n - 1], hull[n - 2])) { hull.pop_back(); n--; } hull.pb(l); } ll ask(int x) { while (SZ(hull) >= 2 && hull[1].FI * x + hull[1].SE >= hull[0].FI * x + hull[0].SE) { hull.pop_front(); } return hull[0].FI * x + hull[0].SE; } 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); for (iii q : qry) { mxto(ans[get<2>(q)], upd[0].FI.FI * get<0>(q) + upd[0].FI.SE); } 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); auto [a, b, c] = q; } else { rqry.pb(q); } } for (pair<line, int> u : upd) { if (u.SE <= mid) { lupd.pb(u); } else { rupd.pb(u); } } for (pair<line, int> u : rupd) { insert(u.FI); } for (auto [x, _, id] : lqry) { mxto(ans[id], ask(x)); } hull.clear(); 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, (ll) b + t + (b - a), c / 2}); } else { ver.pb({a + t, t - a, (ll) 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) { mxto(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(); REP (i, ns, ne) { mxto(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}; } REP (i, 0, q) { auto [x, y] = qry[i]; int lby = lower_bound(ALL(vy), y) - vy.begin(), lbx = lower_bound(ALL(vx), x) - vx.begin(); if (lby >= SZ(vy) || lbx >= SZ(vx)) { continue; } dqry[lby].pb({vy[lby] - y, lbx, i}); /* 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)) { sort(ALL(dqry[i]), [&] (iii l, iii r) { return get<0>(l) < get<0>(r); }); dupd.clear(); REP (j, 0, SZ(vx)) { dupd.pb({line{i == 0 ? 0 : adj[i - 1][j][1], dist[i][j]}, j}); } sort(ALL(dupd), [&] (pair<line, int> l, pair<line, int> r) { return l.FI.FI < r.FI.FI; }); dnc(dqry[i], dupd, 0, SZ(vx) - 1); } REP (i, 0, SZ(vx)) { dqry[i].clear(); } REP (i, 0, q) { auto [x, y] = qry[i]; int lby = lower_bound(ALL(vy), y) - vy.begin(), lbx = lower_bound(ALL(vx), x) - vx.begin(); if (lbx >= SZ(vx) || lby >= SZ(vy)) { continue; } dqry[lbx].pb({vx[lbx] - x, lby, i}); /* 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(vx)) { sort(ALL(dqry[i]), [&] (iii l, iii r) { return get<0>(l) < get<0>(r); }); dupd.clear(); REP (j, 0, SZ(vy)) { dupd.pb({line{i == 0 ? 0 : adj[j][i - 1][0], dist[j][i]}, j}); } sort(ALL(dupd), [&] (pair<line, int> l, pair<line, int> r) { return l.FI.FI < r.FI.FI; }); dnc(dqry[i], dupd, 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<std::pair<int, long long int>, int> >&, int, int)':
bodyguard.cpp:92:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   92 |     int mid = lo + hi >> 1;
      |               ~~~^~~~
bodyguard.cpp:96:18: warning: structured binding declaration set but not used [-Wunused-but-set-variable]
   96 |             auto [a, b, c] = q;
      |                  ^~~~~~~~~
#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...