Submission #907891

#	Time	Username	Problem	Language	Result	Execution time	Memory
907891		box	Bodyguard (JOI21_bodyguard)	C++17	42 / 100	25075 ms	972052 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;

void maxi(i64 &a, i64 b) {
    a = max(a, b);
}

struct hull {
    struct line {
        i64 a, b;
        i64 f(i64 x) { return a*x+b; }
    };
    vector<line> L;
    void add(line l) {
        L.push_back(l);
    }
    i64 qry(i64 x) {
        i64 v = 0;
        for (auto l : L) maxi(v, l.f(x));
        return v;
    }
};

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)[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[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[i+1].at(j) + cx.at(i).at(j)*(X[i+1]-X.at(i)));
        if (j+1 < sz(Y)) maxi(dp.at(i).at(j), dp.at(i)[j+1] + cy.at(i).at(j)*(Y[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[i-1].at(j):0, dp.at(i).at(j)});
            for (auto [p,x,y] : qry.at(i).at(j)) maxi(ans[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)[j-1]:0, dp.at(i).at(j)});
            for (auto [p,x,y] : qry.at(i).at(j)) maxi(ans[p], T.qry(Y.at(j)-y));
        }
    }
    for (auto v : ans) cout << v << '\n';
}

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