oj.uz

Submission #624576

# Submission time Handle Problem Language Result Execution time Memory
624576 2022-08-08T13:38:23 Z maomao90 Bodyguard (JOI21_bodyguard) C++17
100 / 100
 10802 ms 808888 KB 
// 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 && (ll) hull[1].FI * x + hull[1].SE >= (ll) hull[0].FI * x + hull[0].SE) {
        hull.pop_front();
    }
    return (ll) 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)], (ll) 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

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;
      |                  ^~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 7129 ms 293232 KB Output is correct
2 Correct 7125 ms 321040 KB Output is correct
3 Correct 3629 ms 295148 KB Output is correct
4 Correct 1914 ms 199552 KB Output is correct
5 Correct 6020 ms 808888 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1375 ms 279356 KB Output is correct
2 Correct 1368 ms 278800 KB Output is correct
3 Correct 1384 ms 287716 KB Output is correct
4 Correct 17 ms 24144 KB Output is correct
5 Correct 1151 ms 204188 KB Output is correct
6 Correct 1094 ms 154436 KB Output is correct
7 Correct 1131 ms 188596 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1375 ms 279356 KB Output is correct
2 Correct 1368 ms 278800 KB Output is correct
3 Correct 1384 ms 287716 KB Output is correct
4 Correct 17 ms 24144 KB Output is correct
5 Correct 1151 ms 204188 KB Output is correct
6 Correct 1094 ms 154436 KB Output is correct
7 Correct 1131 ms 188596 KB Output is correct
8 Correct 1947 ms 280100 KB Output is correct
9 Correct 1910 ms 278732 KB Output is correct
10 Correct 1518 ms 287192 KB Output is correct
11 Correct 21 ms 24532 KB Output is correct
12 Correct 1287 ms 204656 KB Output is correct
13 Correct 1278 ms 154672 KB Output is correct
14 Correct 1373 ms 204924 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1375 ms 279356 KB Output is correct
2 Correct 1368 ms 278800 KB Output is correct
3 Correct 1384 ms 287716 KB Output is correct
4 Correct 17 ms 24144 KB Output is correct
5 Correct 1151 ms 204188 KB Output is correct
6 Correct 1094 ms 154436 KB Output is correct
7 Correct 1131 ms 188596 KB Output is correct
8 Correct 1947 ms 280100 KB Output is correct
9 Correct 1910 ms 278732 KB Output is correct
10 Correct 1518 ms 287192 KB Output is correct
11 Correct 21 ms 24532 KB Output is correct
12 Correct 1287 ms 204656 KB Output is correct
13 Correct 1278 ms 154672 KB Output is correct
14 Correct 1373 ms 204924 KB Output is correct
15 Correct 3300 ms 282960 KB Output is correct
16 Correct 3347 ms 282960 KB Output is correct
17 Correct 2181 ms 290624 KB Output is correct
18 Correct 34 ms 26728 KB Output is correct
19 Correct 1314 ms 207968 KB Output is correct
20 Correct 1300 ms 156840 KB Output is correct
21 Correct 1391 ms 213152 KB Output is correct

Subtask #5
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 7129 ms 293232 KB Output is correct
2 Correct 7125 ms 321040 KB Output is correct
3 Correct 3629 ms 295148 KB Output is correct
4 Correct 1914 ms 199552 KB Output is correct
5 Correct 6020 ms 808888 KB Output is correct
6 Correct 1375 ms 279356 KB Output is correct
7 Correct 1368 ms 278800 KB Output is correct
8 Correct 1384 ms 287716 KB Output is correct
9 Correct 17 ms 24144 KB Output is correct
10 Correct 1151 ms 204188 KB Output is correct
11 Correct 1094 ms 154436 KB Output is correct
12 Correct 1131 ms 188596 KB Output is correct
13 Correct 1947 ms 280100 KB Output is correct
14 Correct 1910 ms 278732 KB Output is correct
15 Correct 1518 ms 287192 KB Output is correct
16 Correct 21 ms 24532 KB Output is correct
17 Correct 1287 ms 204656 KB Output is correct
18 Correct 1278 ms 154672 KB Output is correct
19 Correct 1373 ms 204924 KB Output is correct
20 Correct 3300 ms 282960 KB Output is correct
21 Correct 3347 ms 282960 KB Output is correct
22 Correct 2181 ms 290624 KB Output is correct
23 Correct 34 ms 26728 KB Output is correct
24 Correct 1314 ms 207968 KB Output is correct
25 Correct 1300 ms 156840 KB Output is correct
26 Correct 1391 ms 213152 KB Output is correct
27 Correct 10802 ms 481900 KB Output is correct
28 Correct 10779 ms 480496 KB Output is correct
29 Correct 7564 ms 538276 KB Output is correct
30 Correct 1328 ms 169208 KB Output is correct
31 Correct 3011 ms 337264 KB Output is correct
32 Correct 4464 ms 320684 KB Output is correct
33 Correct 6195 ms 797004 KB Output is correct