Submission #1138025

#	Time	Username	Problem	Language	Result	Execution time	Memory
1138025		pokmui9909	Bodyguard (JOI21_bodyguard)	C++17	42 / 100	10172 ms	2120852 KiB

bodyguard

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using lf = long double;

#define x first
#define y second

ll N, T;
vector<vector<ll>> P, Q, dp;
vector<ll> X, Y;
struct Input{
    ll t, a, b, c;
}A[5705];
struct Query{
    ll x, y, n;
};
vector<vector<vector<ll>>> ps, qs;
vector<Query> Qry[5605][5605];
ll Ans[3000005];

struct ConvexHullTrick{
    lf Cross(pair<ll, ll> p, pair<ll, ll> q){
        return (lf)(q.y - p.y) / (p.x - q.x);
    }
    vector<pair<ll, ll>> L;
    void Ins(pair<ll, ll> p){
        while(L.size() >= 2 && Cross(p, L.back()) <= Cross(p, L[L.size() - 2])) L.pop_back();
        if(!L.empty() && L.back().x == p.x && L.back().y <= p.y) L.pop_back();
        if(L.empty() || !(L.back().x == p.x && L.back().y >= p.y)) L.push_back(p);
    }
    ll qry(ll k){
        if(L.empty()) return 0;
        ll l = 1, r = L.size() - 1;
        while(l <= r){
            ll m = (l + r) / 2;
            if(Cross(L[m - 1], L[m]) <= k) l = m + 1;
            else r = m - 1;
        }
        return L[r].x * k + L[r].y;
    }
};

void dnc1(ll j, ll s, ll e){
    if(s >= e) return;
    ll m = (s + e) / 2;
    vector<pair<ll, ll>> L;
    for(ll i = m + 1; i <= e; i++){
        L.push_back({Q[i][j - 1], dp[i][j]});
    }
    sort(L.begin(), L.end());
    ConvexHullTrick cht;
    for(auto f : L){
        cht.Ins(f);
    }
    for(ll i = s; i <= m; i++){
        for(auto q : Qry[i][j]){
            Ans[q.n] = max(Ans[q.n], cht.qry(Y[j] - q.y));
        }
    }
    dnc1(j, s, m); dnc1(j, m + 1, e);
}

void dnc2(ll i, ll s, ll e){
    if(s >= e) return;
    ll m = (s + e) / 2;
    vector<pair<ll, ll>> L;
    for(ll j = m + 1; j <= e; j++){
        L.push_back({P[i - 1][j], dp[i][j]});
    }
    sort(L.begin(), L.end());
    ConvexHullTrick cht;
    for(auto f : L){
        cht.Ins(f);
    }
    for(ll j = s; j <= m; j++){
        for(auto q : Qry[i][j]){
            Ans[q.n] = max(Ans[q.n], cht.qry(X[i] - q.x));
        }
    }
    dnc2(i, s, m); dnc2(i, m + 1, e);
}

int main(){
    cin.tie(0) -> sync_with_stdio(0);

    cin >> N >> T;
    for(ll i = 1; i <= N; i++){
        cin >> A[i].t >> A[i].a >> A[i].b >> A[i].c;
        if(A[i].a < A[i].b){
            ll y = A[i].t - A[i].a, x1 = A[i].t + A[i].a, x2 = A[i].t + A[i].b + (A[i].b - A[i].a);
            X.push_back(x1); X.push_back(x2);
            Y.push_back(y);
        } else {
            ll x = A[i].t + A[i].a, y1 = A[i].t - A[i].a, y2 = A[i].t - A[i].b + (A[i].a - A[i].b);
            X.push_back(x);
            Y.push_back(y1); Y.push_back(y2);
        }
    }
    X.push_back(-1e18); Y.push_back(-1e18);
    sort(X.begin(), X.end()); X.erase(unique(X.begin(), X.end()), X.end());
    sort(Y.begin(), Y.end()); Y.erase(unique(Y.begin(), Y.end()), Y.end());

    P = Q = dp = vector<vector<ll>>(X.size() + 3, vector<ll>(Y.size() + 3, 0LL));
    ps = qs = vector<vector<vector<ll>>>(X.size() + 3, vector<vector<ll>>(Y.size() + 3));

    for(ll i = 1; i <= N; i++){
        if(A[i].a < A[i].b){
            ll y = A[i].t - A[i].a, x1 = A[i].t + A[i].a, x2 = A[i].t + A[i].b + (A[i].b - A[i].a);
            y = lower_bound(Y.begin(), Y.end(), y) - Y.begin();
            x1 = lower_bound(X.begin(), X.end(), x1) - X.begin();
            x2 = lower_bound(X.begin(), X.end(), x2) - X.begin();
            ps[x1][y].push_back(A[i].c); ps[x2][y].push_back(-A[i].c);
        } else {
            ll x = A[i].t + A[i].a, y1 = A[i].t - A[i].a, y2 = A[i].t - A[i].b + (A[i].a - A[i].b);
            x = lower_bound(X.begin(), X.end(), x) - X.begin();
            y1 = lower_bound(Y.begin(), Y.end(), y1) - Y.begin();
            y2 = lower_bound(Y.begin(), Y.end(), y2) - Y.begin();
            qs[x][y1].push_back(A[i].c); qs[x][y2].push_back(-A[i].c);
        }
    }
    for(ll j = 1; j < Y.size(); j++){
        multiset<ll> S;
        for(ll i = 1; i < X.size(); i++){
            for(auto e : ps[i][j]){
                if(e > 0) S.insert(e);
                else S.erase(S.find(-e));
            }
            P[i][j] = (S.empty() ? 0LL : *prev(S.end()));
        }
    }
    for(ll i = 1; i < X.size(); i++){
        multiset<ll> S;
        for(ll j = 1; j < Y.size(); j++){
            for(auto e : qs[i][j]){
                if(e > 0) S.insert(e);
                else S.erase(S.find(-e));
            }
            Q[i][j] = (S.empty() ? 0LL : *prev(S.end()));
        }
    }
    for(ll i = X.size() - 1; i >= 1; i--){
        for(ll j = Y.size() - 1; j >= 1; j--){
            ll dx = (i == X.size() - 1 ? 0LL : X[i + 1] - X[i]), dy = (j == Y.size() - 1 ? 0LL : Y[j + 1] - Y[j]);
            dp[i][j] = max(dp[i + 1][j] + P[i][j] * dx, dp[i][j + 1] + Q[i][j] * dy);
        }
    }
    for(ll i = 1; i <= T; i++){
        ll t, u; cin >> t >> u;
        ll e = lower_bound(X.begin(), X.end(), t + u) - X.begin();
        ll f = lower_bound(Y.begin(), Y.end(), t - u) - Y.begin();
        if(e < X.size() && f < Y.size()){
            Qry[e][f].push_back({t + u, t - u, i});
        }
    }
    for(ll i = 1; i < X.size(); i++){
        for(ll j = 1; j < Y.size(); j++){
            for(auto q : Qry[i][j]){
                Ans[q.n] = dp[i][j] + max(Q[i][j - 1] * (Y[j] - q.y), P[i - 1][j] * (X[i] - q.x));
            }
        }
    }
    for(ll j = 1; j < Y.size(); j++){
        dnc1(j, 1, X.size() - 1);
    }
    for(ll i = 1; i < X.size(); i++){
        dnc2(i, 1, Y.size() - 1);
    }
    for(ll i = 1; i <= T; i++){
        cout << Ans[i] / 2 << '\n';
    }
}

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