oj.uz

Submission #907952

# Submission time Handle Problem Language Result Execution time Memory
907952 2024-01-16T06:32:21 Z box Bodyguard (JOI21_bodyguard) C++17
100 / 100
 7198 ms 1067452 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;
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.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 5173 ms 569396 KB Output is correct
2 Correct 5012 ms 572800 KB Output is correct
3 Correct 1636 ms 238528 KB Output is correct
4 Correct 911 ms 99320 KB Output is correct
5 Correct 3221 ms 967876 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2955 ms 830036 KB Output is correct
2 Correct 2654 ms 829908 KB Output is correct
3 Correct 2540 ms 818712 KB Output is correct
4 Correct 3 ms 1112 KB Output is correct
5 Correct 2635 ms 830008 KB Output is correct
6 Correct 2637 ms 830008 KB Output is correct
7 Correct 2681 ms 828696 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2955 ms 830036 KB Output is correct
2 Correct 2654 ms 829908 KB Output is correct
3 Correct 2540 ms 818712 KB Output is correct
4 Correct 3 ms 1112 KB Output is correct
5 Correct 2635 ms 830008 KB Output is correct
6 Correct 2637 ms 830008 KB Output is correct
7 Correct 2681 ms 828696 KB Output is correct
8 Correct 2687 ms 830096 KB Output is correct
9 Correct 2755 ms 829932 KB Output is correct
10 Correct 2739 ms 817192 KB Output is correct
11 Correct 4 ms 1048 KB Output is correct
12 Correct 2480 ms 830120 KB Output is correct
13 Correct 2515 ms 830092 KB Output is correct
14 Correct 2525 ms 830104 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2955 ms 830036 KB Output is correct
2 Correct 2654 ms 829908 KB Output is correct
3 Correct 2540 ms 818712 KB Output is correct
4 Correct 3 ms 1112 KB Output is correct
5 Correct 2635 ms 830008 KB Output is correct
6 Correct 2637 ms 830008 KB Output is correct
7 Correct 2681 ms 828696 KB Output is correct
8 Correct 2687 ms 830096 KB Output is correct
9 Correct 2755 ms 829932 KB Output is correct
10 Correct 2739 ms 817192 KB Output is correct
11 Correct 4 ms 1048 KB Output is correct
12 Correct 2480 ms 830120 KB Output is correct
13 Correct 2515 ms 830092 KB Output is correct
14 Correct 2525 ms 830104 KB Output is correct
15 Correct 2590 ms 832684 KB Output is correct
16 Correct 2646 ms 832724 KB Output is correct
17 Correct 2567 ms 821828 KB Output is correct
18 Correct 13 ms 2608 KB Output is correct
19 Correct 2549 ms 832508 KB Output is correct
20 Correct 2524 ms 832628 KB Output is correct
21 Correct 2562 ms 832148 KB Output is correct

Subtask #5
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 5173 ms 569396 KB Output is correct
2 Correct 5012 ms 572800 KB Output is correct
3 Correct 1636 ms 238528 KB Output is correct
4 Correct 911 ms 99320 KB Output is correct
5 Correct 3221 ms 967876 KB Output is correct
6 Correct 2955 ms 830036 KB Output is correct
7 Correct 2654 ms 829908 KB Output is correct
8 Correct 2540 ms 818712 KB Output is correct
9 Correct 3 ms 1112 KB Output is correct
10 Correct 2635 ms 830008 KB Output is correct
11 Correct 2637 ms 830008 KB Output is correct
12 Correct 2681 ms 828696 KB Output is correct
13 Correct 2687 ms 830096 KB Output is correct
14 Correct 2755 ms 829932 KB Output is correct
15 Correct 2739 ms 817192 KB Output is correct
16 Correct 4 ms 1048 KB Output is correct
17 Correct 2480 ms 830120 KB Output is correct
18 Correct 2515 ms 830092 KB Output is correct
19 Correct 2525 ms 830104 KB Output is correct
20 Correct 2590 ms 832684 KB Output is correct
21 Correct 2646 ms 832724 KB Output is correct
22 Correct 2567 ms 821828 KB Output is correct
23 Correct 13 ms 2608 KB Output is correct
24 Correct 2549 ms 832508 KB Output is correct
25 Correct 2524 ms 832628 KB Output is correct
26 Correct 2562 ms 832148 KB Output is correct
27 Correct 7198 ms 1067344 KB Output is correct
28 Correct 6938 ms 1067452 KB Output is correct
29 Correct 4455 ms 1013264 KB Output is correct
30 Correct 770 ms 121996 KB Output is correct
31 Correct 3575 ms 961180 KB Output is correct
32 Correct 4581 ms 1053496 KB Output is correct
33 Correct 3268 ms 1003872 KB Output is correct