oj.uz

Submission #907891

# Submission time Handle Problem Language Result Execution time Memory
907891 2024-01-16T05:53:20 Z box Bodyguard (JOI21_bodyguard) C++17
42 / 100
 25000 ms 972052 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);
}

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.0

# Verdict Execution time Memory Grader output
1 Correct 15543 ms 596172 KB Output is correct
2 Correct 15173 ms 600148 KB Output is correct
3 Correct 4744 ms 265200 KB Output is correct
4 Correct 3297 ms 126480 KB Output is correct
5 Execution timed out 25075 ms 972052 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1999 ms 830104 KB Output is correct
2 Correct 2143 ms 830036 KB Output is correct
3 Correct 2094 ms 818928 KB Output is correct
4 Correct 3 ms 1112 KB Output is correct
5 Correct 2149 ms 830092 KB Output is correct
6 Correct 2089 ms 830220 KB Output is correct
7 Correct 2163 ms 828888 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1999 ms 830104 KB Output is correct
2 Correct 2143 ms 830036 KB Output is correct
3 Correct 2094 ms 818928 KB Output is correct
4 Correct 3 ms 1112 KB Output is correct
5 Correct 2149 ms 830092 KB Output is correct
6 Correct 2089 ms 830220 KB Output is correct
7 Correct 2163 ms 828888 KB Output is correct
8 Correct 2045 ms 830404 KB Output is correct
9 Correct 2294 ms 830364 KB Output is correct
10 Correct 2072 ms 817336 KB Output is correct
11 Correct 7 ms 1368 KB Output is correct
12 Correct 2288 ms 830480 KB Output is correct
13 Correct 2278 ms 830500 KB Output is correct
14 Correct 2198 ms 830180 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1999 ms 830104 KB Output is correct
2 Correct 2143 ms 830036 KB Output is correct
3 Correct 2094 ms 818928 KB Output is correct
4 Correct 3 ms 1112 KB Output is correct
5 Correct 2149 ms 830092 KB Output is correct
6 Correct 2089 ms 830220 KB Output is correct
7 Correct 2163 ms 828888 KB Output is correct
8 Correct 2045 ms 830404 KB Output is correct
9 Correct 2294 ms 830364 KB Output is correct
10 Correct 2072 ms 817336 KB Output is correct
11 Correct 7 ms 1368 KB Output is correct
12 Correct 2288 ms 830480 KB Output is correct
13 Correct 2278 ms 830500 KB Output is correct
14 Correct 2198 ms 830180 KB Output is correct
15 Correct 2625 ms 834256 KB Output is correct
16 Correct 2577 ms 833180 KB Output is correct
17 Correct 2329 ms 822108 KB Output is correct
18 Correct 28 ms 2892 KB Output is correct
19 Correct 2588 ms 833164 KB Output is correct
20 Correct 2612 ms 832792 KB Output is correct
21 Correct 2552 ms 832392 KB Output is correct

Subtask #5
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 15543 ms 596172 KB Output is correct
2 Correct 15173 ms 600148 KB Output is correct
3 Correct 4744 ms 265200 KB Output is correct
4 Correct 3297 ms 126480 KB Output is correct
5 Execution timed out 25075 ms 972052 KB Time limit exceeded
6 Halted 0 ms 0 KB -