제출 #1252436

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1252436		antonn	Bodyguard (JOI21_bodyguard)	C++20	100 / 100	5225 ms	1660024 KiB

bodyguard

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

template<typename T>
bool assign_min(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

template<typename T>
bool assign_max(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

const int INF = 2'000'000'000;

struct Line {
    ll a;
    ll b;
    
    ll eval(ll x) {
        return a * x + b;
    }
};

struct Node {
    Line val;
    Node* lson;
    Node* rson;
    
    Node(Line l = {0, 0}) {
        val = l;
        lson = rson = nullptr;
    }
};

struct LiChao {
    vector<ll> v, dp, dp1;
    Node *root = nullptr;
    int n;
    
    void update(Node* &root, ll tl, ll tr, Line l) {
        if (root == nullptr) {
            root = new Node(l);
        } else {
            ll tm = (tl + tr) / 2;
            if (l.eval(tm - 1e9) > root->val.eval(tm - 1e9)) {
                swap(root->val, l);
            }
            if (l.eval(tl - 1e9) > root->val.eval(tl - 1e9)) {
                update(root->lson, tl, tm, l);
            }
            if (l.eval(tr - 1e9) > root->val.eval(tr - 1e9)) {
                update(root->rson, tm + 1, tr, l);
            }
        }
    }
    
    vector<Line> funcs;
    
    void add(int id, bool print = 0) {
        Line l = {dp1[v[id]], dp[v[id]]};
        funcs.push_back(l);
        update(root, 0, 2e9, l);
    }
    
    void init(vector<ll> v_, vector<ll> dp_, vector<ll> dp1_) {
        v = v_;
        dp = dp_;
        dp1 = dp1_;
        root = nullptr;
    }
    
    ll query(Node *root, ll tl, ll tr, ll x) {
        if (root == nullptr) {
            return -1e18;
        } else {
            ll tm = (tl + tr) / 2;
            if (x <= tm) {
                return max(query(root->lson, tl, tm, x), root->val.eval(x - 1e9));
            } else {
                return max(query(root->rson, tm + 1, tr, x), root->val.eval(x - 1e9));
            }
        }
    }
    
    ll get(ll x) {
        x += 1e9;
        return query(root, 0, 2e9, x);
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, q;
    cin >> n >> q;
    vector<array<ll, 5>> vips;
    vector<ll> l = {-INF, INF}, c = {-INF, INF}, v1, v2;
    for (int i = 1; i <= n; i++) {
        ll t, a, b, cost;
        cin >> t >> a >> b >> cost;
        ll len = abs(a - b);
        ll e = t - a;
        ll f = t + a;
        ll g = t + len - b;
        ll h = t + len + b;
        l.push_back(e);
        l.push_back(g);
        c.push_back(f);
        c.push_back(h);
        vips.push_back({e, f, g, h, cost / 2});
        if (a < b) {
            v1.push_back(e);
        } else {
            v2.push_back(f);
        }
    }
    sort(l.begin(), l.end());
    sort(c.begin(), c.end());
    sort(v1.begin(), v1.end());
    sort(v2.begin(), v2.end());
    l.resize(unique(l.begin(), l.end()) - l.begin());
    c.resize(unique(c.begin(), c.end()) - c.begin());
    v1.resize(unique(v1.begin(), v1.end()) - v1.begin());
    v2.resize(unique(v2.begin(), v2.end()) - v2.begin());
    auto idl = [&](ll x) {
        return lower_bound(l.begin(), l.end(), x) - l.begin();
    };
    auto idc = [&](ll x) {
        return lower_bound(c.begin(), c.end(), x) - c.begin();
    };
    for (int i = 0; i < v1.size(); i++) {
        v1[i] = idl(v1[i]);
    }
    for (int i = 0; i < v2.size(); i++) {
        v2[i] = idc(v2[i]);
    }
    vector<vector<ll>> dp1(l.size(), vector<ll>(c.size()));
    vector<vector<ll>> dp2(l.size(), vector<ll>(c.size()));
    vector<vector<ll>> dp(l.size(), vector<ll>(c.size()));
    for (auto [a, b, c, d, z] : vips) {
        if (a == c) {
            for (int j = idc(b); j < idc(d); j++) {
                assign_max(dp1[idl(a)][j], z);
            }
        } else {
            for (int i = idl(a); i < idl(c); i++) {
                assign_max(dp2[i][idc(b)], z);
            }
        }
    }
    for (int i = l.size() - 2; i >= 0; i--) {
        for (int j = c.size() - 2; j >= 0; j--) {
            assign_max(dp[i][j], dp[i + 1][j] + dp2[i][j] * (l[i + 1] - l[i]));
            assign_max(dp[i][j], dp[i][j + 1] + dp1[i][j] * (c[j + 1] - c[j]));
        }
    }
    vector<LiChao> t1(c.size()), t2(l.size());
    for (int i = 1; i < c.size(); i++) {
        vector<ll> dp_here(l.size()), dp1_here(l.size());
        for (int j = 0; j < l.size(); j++) {
            dp_here[j] = dp[j][i];
            dp1_here[j] = dp1[j][i - 1];
        }
        t1[i].init(v1, dp_here, dp1_here);
    }
    for (int i = 1; i < l.size(); i++) {
        t2[i].init(v2, dp[i], dp2[i - 1]);
    }
    vector<array<ll, 5>> qs;
    for (int i = 0; i < q; i++) {
        ll a, b;
        cin >> a >> b;
        ll h = a - b;
        ll w = a + b;
        ll ans = 0;
        ll ind_h = idl(h);
        ll ind_w = idc(w);
        qs.push_back({ind_w, ind_h, l[ind_h] - h, i, 2});
        qs.push_back({ind_h, ind_w, c[ind_w] - w, i, 1});
    }
    vector<ll> sol(q);
    sort(qs.rbegin(), qs.rend());
    int ptr1 = v1.size() - 1, ptr2 = v2.size() - 1;
    for (auto [ind, ask, x, id, type] : qs) {
        while (ptr1 >= 0 && v1[ptr1] >= ind) {
            for (int i = 1; i < c.size(); i++) {
                t1[i].add(ptr1);
            }
            ptr1--;
        }
        while (ptr2 >= 0 && v2[ptr2] >= ind) {
            for (int i = 1; i < l.size(); i++) {
                t2[i].add(ptr2);
            }
            ptr2--;
        }
        if (type == 1) {
            assign_max(sol[id], t1[ask].get(x));
        } else {
            assign_max(sol[id], t2[ask].get(x));
        }
    }
    for (int i = 0; i < q; i++) {
        cout << sol[i] << "\n";
    }
}

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