Submission #907952

#	Time	Username	Problem	Language	Result	Execution time	Memory
907952		box	Bodyguard (JOI21_bodyguard)	C++17	100 / 100	7198 ms	1067452 KiB

bodyguard

#include <bits/stdc++.h>
using namespace std;
 
#ifndef LOCAL
#define cerr if (0) cerr
#endif
 
#define ar array
#define sz(v) int(std::size(v))
#define all(v) std::begin(v), std::end(v)
typedef long long i64;
typedef vector<int> vi;
typedef long double db;

void maxi(i64 &a, i64 b) {
    a = max(a, b);
}
 
const db INF = 1e18;
 
struct hull {
    struct line {
        i64 m, b; db bet = INF;
        i64 f(i64 x) { return m*x+b; }
    };
    db isect(line u, line v) {
        assert(u.m^v.m);
        return db(u.b-v.b)/db(v.m-u.m);
    }
    vector<line> L;
    void add(line l) {
        while (sz(L) && end(L)[-1].m <= l.m) L.pop_back();
        if (sz(L) && L.back().b >= l.b) return;
        while (sz(L) > 1 && isect(l, end(L)[-2]) >= end(L)[-1].bet) L.pop_back();
        l.bet = sz(L) ? isect(l, end(L)[-1]) : INF;
        L.push_back(l);
    }
    i64 qry(i64 x) {
        if (sz(L) == 0) return 0;
        int low = 0, hi = sz(L)-1;
        while (low < hi) {
            int m = (low+hi)/2+1;
            if (L.at(m).bet >= x) low = m;
            else hi = m-1;
        }
        // cerr << "GOT " << low << " / " << sz(L) << endl;
        return L.at(low).f(x);
    }
};
 
int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int N, Q; cin >> N >> Q;
    vector<ar<i64, 4>> segx, segy;
    for (int i = 0; i < N; i++) {
        i64 t, a, b, c; cin >> t >> a >> b >> c;
        c /= 2;
        if (a > b) segy.push_back({t+a, t-a, t-2*b+a, c});
        else segx.push_back({t-a, t+a, t+2*b-a, c});
    }
    vector<i64> X, Y;
    for (auto [y, x1, x2, c] : segx) {
        Y.push_back(y);
        X.push_back(x1);
        X.push_back(x2);
    }
    for (auto [x, y1, y2, c] : segy) {
        X.push_back(x);
        Y.push_back(y1);
        Y.push_back(y2);
    }
    sort(all(X)), sort(all(Y));
    X.erase(unique(all(X)), end(X)), Y.erase(unique(all(Y)), end(Y));
    vector cx(sz(X), vector<i64>(sz(Y))), cy(sz(X), vector<i64>(sz(Y)));
    for (auto [y, x1, x2, c] : segx) {
        int a = lower_bound(all(Y), y) - begin(Y);
        int bl = lower_bound(all(X), x1) - begin(X);
        int br = lower_bound(all(X), x2) - begin(X);
        for (int i = bl; i < br; i++) maxi(cx.at(i).at(a), c);
    }
    for (auto [x, y1, y2, c] : segy) {
        int a = lower_bound(all(X), x) - begin(X);
        int bl = lower_bound(all(Y), y1) - begin(Y);
        int br = lower_bound(all(Y), y2) - begin(Y);
        for (int i = bl; i < br; i++) maxi(cy.at(a).at(i), c);
    }
    vector dp(sz(X), vector<i64>(sz(Y)));
    for (int i = sz(X)-1; i >= 0; i--) for (int j = sz(Y)-1; j >= 0; j--) {
        if (i+1 < sz(X)) maxi(dp.at(i).at(j), dp.at(i+1).at(j) + cx.at(i).at(j)*(X.at(i+1)-X.at(i)));
        if (j+1 < sz(Y)) maxi(dp.at(i).at(j), dp.at(i).at(j+1) + cy.at(i).at(j)*(Y.at(j+1)-Y.at(j)));
    }
    vector qry(sz(X), vector<vector<tuple<int, i64, i64>>>(sz(Y)));
    vector<i64> ans(Q);
    for (int i = 0; i < Q; i++) {
        i64 p, a; cin >> p >> a;
        i64 x = p+a, y = p-a;
        int xp = lower_bound(all(X), x) - begin(X);
        int yp = lower_bound(all(Y), y) - begin(Y);
        if (xp == sz(X) || yp == sz(Y)) continue;
        qry.at(xp).at(yp).push_back({i,x,y});
    }
    for (int i = sz(X)-1; i >= 0; i--) {
        hull T;
        for (int j = sz(Y)-1; j >= 0; j--) {
            T.add({i?cx.at(i-1).at(j):0, dp.at(i).at(j)});
            for (auto [p,x,y] : qry.at(i).at(j)) maxi(ans.at(p), T.qry(X.at(i)-x));
        }
    }
    for (int j = sz(Y)-1; j >= 0; j--) {
        hull T;
        for (int i = sz(X)-1; i >= 0; i--) {
            T.add({j?cy.at(i).at(j-1):0, dp.at(i).at(j)});
            for (auto [p,x,y] : qry.at(i).at(j)) maxi(ans.at(p), T.qry(Y.at(j)-y));
        }
    }
    for (auto v : ans) cout << v << '\n';
}

• Subtask 1: 6 / 6
• Subtask 2: 7 / 7
• Subtask 3: 15 / 15
• Subtask 4: 20 / 20
• Subtask 5: 52 / 52