oj.uz

Submission #907943

# Submission time Handle Problem Language Result Execution time Memory
907943 2024-01-16T06:26:29 Z box Bodyguard (JOI21_bodyguard) C++17
6 / 100
 5216 ms 968004 KB 
#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);
}
 
const double INF = 1e18;
 
struct hull {
    struct line {
        i64 m, b; double bet = INF;
        i64 f(i64 x) { return m*x+b; }
    };
    double isect(line u, line v) {
        assert(u.m^v.m);
        return double(u.b-v.b)/double(v.m-u.m);
    }
    vector<line> L;
    void add(line l) {
        if (sz(L)) assert(end(L)[-1].b <= l.b);
        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.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 5173 ms 569052 KB Output is correct
2 Correct 5216 ms 572812 KB Output is correct
3 Correct 1634 ms 237108 KB Output is correct
4 Correct 906 ms 99396 KB Output is correct
5 Correct 3187 ms 968004 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2656 ms 829928 KB Output is correct
2 Correct 2522 ms 829804 KB Output is correct
3 Incorrect 2470 ms 818600 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2656 ms 829928 KB Output is correct
2 Correct 2522 ms 829804 KB Output is correct
3 Incorrect 2470 ms 818600 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2656 ms 829928 KB Output is correct
2 Correct 2522 ms 829804 KB Output is correct
3 Incorrect 2470 ms 818600 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 5173 ms 569052 KB Output is correct
2 Correct 5216 ms 572812 KB Output is correct
3 Correct 1634 ms 237108 KB Output is correct
4 Correct 906 ms 99396 KB Output is correct
5 Correct 3187 ms 968004 KB Output is correct
6 Correct 2656 ms 829928 KB Output is correct
7 Correct 2522 ms 829804 KB Output is correct
8 Incorrect 2470 ms 818600 KB Output isn't correct
9 Halted 0 ms 0 KB -