답안 #414940

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
414940 2021-05-31T10:50:00 Z Pro_ktmr Bodyguard (JOI21_bodyguard) C++17
100 / 100
7975 ms 1307600 KB
#include <bits/stdc++.h>

#include <random>
#include <unordered_map>
#include <unordered_set>
using namespace std;
#pragma GCC target("avx2")
#pragma GCC optimize("O3,unroll-loops")
using ll = long long;
using ull = unsigned long long;
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define _overload3(_1, _2, _3, name, ...) name
#define _rep(i, n) for (int(i) = 0; (i) < int(n); (i)++)
#define repi(i, a, b) for (int(i) = (a); (i) < int(b); (i)++)
#define rep(...) _overload3(__VA_ARGS__, repi, _rep)(__VA_ARGS__)
template <class T>
bool chmax(T& a, const T& b) {
    if (a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
bool chmin(T& a, const T& b) {
    if (b < a) {
        a = b;
        return 1;
    }
    return 0;
}
constexpr int dy[4] = {-1, 0, 1, 0};
constexpr int dx[4] = {0, -1, 0, 1};
constexpr ll MOD = 1'000'000'007LL; /*998'244'353LL;*/

struct LiChaoTree {
    struct Line {
        long long a, b;
        Line(long long a, long long b) : a(a), b(b) {}
        long long f(long long x) { return a * x + b; }
    };
    struct Node {
        Line L;
        long long l, m, r;
        Node *lc, *rc;
        Node(long long l, long long r)
            : L(0, 1LL << 62), l(l), r(r), lc(nullptr), rc(nullptr) {
            m = (l + r) >> 1;
        }
    };
    long long n, l, r;
    Node* root;
    LiChaoTree(long long _l, long long _r) {
        n = 1;
        while (n < _r - _l) n <<= 1;
        l = _l, r = _l + n;
        root = new Node(l, r);
    }
    void add(long long a, long long b) { add(root, Line(a, b)); }
    void add(Node* p, Line l) {
        if (l.f(p->m) < p->L.f(p->m)) swap(l, p->L);
        if (p->r - p->l == 1) return;
        if (l.f(p->l) < p->L.f(p->l)) {
            if (p->lc == nullptr) {
                p->lc = new Node(p->l, p->m);
            }
            add(p->lc, l);
        }
        if (l.f(p->r) < p->L.f(p->r)) {
            if (p->rc == nullptr) {
                p->rc = new Node(p->m, p->r);
            }
            add(p->rc, l);
        }
    }
    long long query(long long x) {
        Node* p = root;
        long long ret = 1LL << 62;
        while (p != nullptr) {
            ret = min(ret, p->L.f(x));
            if ((p->l + p->r) / 2 <= x)
                p = p->rc;
            else
                p = p->lc;
        }
        return ret;
    }
};

int N, Q;
ll T[3000], A[3000], B[3000], C[3000];
ll P[3'000'000], X[3'000'000];

vector<ll> zx, zy;
ll costX[5605][5605], costY[5605][5605];
ll dp[5605][5605];

vector<int> query[5605][5605];
ll ans[3'000'000];

signed main() {
    scanf("%d%d", &N, &Q);
    rep(i, N) { scanf("%d%d%d%d", T + i, A + i, B + i, C + i); }
    rep(i, Q) { scanf("%d%d", P + i, X + i); }

    rep(i, N) {
        if (A[i] < B[i]) {
            zx.pb(T[i] + A[i]);
            zx.pb(T[i] + 2 * B[i] - A[i]);
            zy.pb(T[i] - A[i]);
        } else {
            zx.pb(T[i] + A[i]);
            zy.pb(T[i] - A[i]);
            zy.pb(T[i] - 2 * B[i] + A[i]);
        }
    }
    zx.pb(LLONG_MIN);
    zy.pb(LLONG_MIN);
    sort(all(zx));
    zx.erase(unique(all(zx)), zx.end());
    sort(all(zy));
    zy.erase(unique(all(zy)), zy.end());

    rep(i, N) {
        if (A[i] < B[i]) {
            int l = lower_bound(all(zx), T[i] + A[i]) - zx.begin();
            int r = lower_bound(all(zx), T[i] + 2 * B[i] - A[i]) - zx.begin();
            int y = lower_bound(all(zy), T[i] - A[i]) - zy.begin();
            rep(j, l, r) chmax(costX[j][y], C[i] / 2);
        } else {
            int x = lower_bound(all(zx), T[i] + A[i]) - zx.begin();
            int u = lower_bound(all(zy), T[i] - A[i]) - zy.begin();
            int d = lower_bound(all(zy), T[i] - 2 * B[i] + A[i]) - zy.begin();
            rep(j, u, d) chmax(costY[x][j], C[i] / 2);
        }
    }
    for (int i = zx.size() - 1; i >= 0; i--) {
        for (int j = zy.size() - 1; j >= 0; j--) {
            if (i != zx.size() - 1)
                chmax(dp[i][j],
                      dp[i + 1][j] + costX[i][j] * (zx[i + 1] - zx[i]));
            if (j != zy.size() - 1)
                chmax(dp[i][j],
                      dp[i][j + 1] + costY[i][j] * (zy[j + 1] - zy[j]));
        }
    }

    rep(i, Q) {
        int x = lower_bound(all(zx), P[i] + X[i]) - zx.begin();
        int y = lower_bound(all(zy), P[i] - X[i]) - zy.begin();
        query[x][y].pb(i);
    }
    rep(x, 1, zx.size()) {
        LiChaoTree lct(-4e9L, 4e9L);
        for (int y = zy.size() - 1; y > 0; y--) {
            lct.add(-costX[x - 1][y], -dp[x][y]);
            for (auto i : query[x][y]) {
                chmax(ans[i], -lct.query(zx[x] - (P[i] + X[i])));
            }
        }
    }
    rep(y, 1, zy.size()) {
        LiChaoTree lct(-4e9L, 4e9L);
        for (int x = zx.size() - 1; x > 0; x--) {
            lct.add(-costY[x][y - 1], -dp[x][y]);
            for (auto i : query[x][y]) {
                chmax(ans[i], -lct.query(zy[y] - (P[i] - X[i])));
            }
        }
    }
    rep(i, Q) printf("%lld\n", ans[i]);
}

Compilation message

bodyguard.cpp: In function 'int main()':
bodyguard.cpp:15:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   15 | #define _rep(i, n) for (int(i) = 0; (i) < int(n); (i)++)
      |                            ^
bodyguard.cpp:14:43: note: in expansion of macro '_rep'
   14 | #define _overload3(_1, _2, _3, name, ...) name
      |                                           ^~~~
bodyguard.cpp:17:18: note: in expansion of macro '_overload3'
   17 | #define rep(...) _overload3(__VA_ARGS__, repi, _rep)(__VA_ARGS__)
      |                  ^~~~~~~~~~
bodyguard.cpp:105:5: note: in expansion of macro 'rep'
  105 |     rep(i, N) { scanf("%d%d%d%d", T + i, A + i, B + i, C + i); }
      |     ^~~
bodyguard.cpp:105:25: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'll*' {aka 'long long int*'} [-Wformat=]
  105 |     rep(i, N) { scanf("%d%d%d%d", T + i, A + i, B + i, C + i); }
      |                        ~^         ~~~~~
      |                         |           |
      |                         int*        ll* {aka long long int*}
      |                        %lld
bodyguard.cpp:105:27: warning: format '%d' expects argument of type 'int*', but argument 3 has type 'll*' {aka 'long long int*'} [-Wformat=]
  105 |     rep(i, N) { scanf("%d%d%d%d", T + i, A + i, B + i, C + i); }
      |                          ~^              ~~~~~
      |                           |                |
      |                           int*             ll* {aka long long int*}
      |                          %lld
bodyguard.cpp:105:29: warning: format '%d' expects argument of type 'int*', but argument 4 has type 'll*' {aka 'long long int*'} [-Wformat=]
  105 |     rep(i, N) { scanf("%d%d%d%d", T + i, A + i, B + i, C + i); }
      |                            ~^                   ~~~~~
      |                             |                     |
      |                             int*                  ll* {aka long long int*}
      |                            %lld
bodyguard.cpp:105:31: warning: format '%d' expects argument of type 'int*', but argument 5 has type 'll*' {aka 'long long int*'} [-Wformat=]
  105 |     rep(i, N) { scanf("%d%d%d%d", T + i, A + i, B + i, C + i); }
      |                              ~^                        ~~~~~
      |                               |                          |
      |                               int*                       ll* {aka long long int*}
      |                              %lld
bodyguard.cpp:15:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   15 | #define _rep(i, n) for (int(i) = 0; (i) < int(n); (i)++)
      |                            ^
bodyguard.cpp:14:43: note: in expansion of macro '_rep'
   14 | #define _overload3(_1, _2, _3, name, ...) name
      |                                           ^~~~
bodyguard.cpp:17:18: note: in expansion of macro '_overload3'
   17 | #define rep(...) _overload3(__VA_ARGS__, repi, _rep)(__VA_ARGS__)
      |                  ^~~~~~~~~~
bodyguard.cpp:106:5: note: in expansion of macro 'rep'
  106 |     rep(i, Q) { scanf("%d%d", P + i, X + i); }
      |     ^~~
bodyguard.cpp:106:25: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'll*' {aka 'long long int*'} [-Wformat=]
  106 |     rep(i, Q) { scanf("%d%d", P + i, X + i); }
      |                        ~^     ~~~~~
      |                         |       |
      |                         int*    ll* {aka long long int*}
      |                        %lld
bodyguard.cpp:106:27: warning: format '%d' expects argument of type 'int*', but argument 3 has type 'll*' {aka 'long long int*'} [-Wformat=]
  106 |     rep(i, Q) { scanf("%d%d", P + i, X + i); }
      |                          ~^          ~~~~~
      |                           |            |
      |                           int*         ll* {aka long long int*}
      |                          %lld
bodyguard.cpp:15:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   15 | #define _rep(i, n) for (int(i) = 0; (i) < int(n); (i)++)
      |                            ^
bodyguard.cpp:14:43: note: in expansion of macro '_rep'
   14 | #define _overload3(_1, _2, _3, name, ...) name
      |                                           ^~~~
bodyguard.cpp:17:18: note: in expansion of macro '_overload3'
   17 | #define rep(...) _overload3(__VA_ARGS__, repi, _rep)(__VA_ARGS__)
      |                  ^~~~~~~~~~
bodyguard.cpp:108:5: note: in expansion of macro 'rep'
  108 |     rep(i, N) {
      |     ^~~
bodyguard.cpp:15:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   15 | #define _rep(i, n) for (int(i) = 0; (i) < int(n); (i)++)
      |                            ^
bodyguard.cpp:14:43: note: in expansion of macro '_rep'
   14 | #define _overload3(_1, _2, _3, name, ...) name
      |                                           ^~~~
bodyguard.cpp:17:18: note: in expansion of macro '_overload3'
   17 | #define rep(...) _overload3(__VA_ARGS__, repi, _rep)(__VA_ARGS__)
      |                  ^~~~~~~~~~
bodyguard.cpp:126:5: note: in expansion of macro 'rep'
  126 |     rep(i, N) {
      |     ^~~
bodyguard.cpp:16:31: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   16 | #define repi(i, a, b) for (int(i) = (a); (i) < int(b); (i)++)
      |                               ^
bodyguard.cpp:14:43: note: in expansion of macro 'repi'
   14 | #define _overload3(_1, _2, _3, name, ...) name
      |                                           ^~~~
bodyguard.cpp:17:18: note: in expansion of macro '_overload3'
   17 | #define rep(...) _overload3(__VA_ARGS__, repi, _rep)(__VA_ARGS__)
      |                  ^~~~~~~~~~
bodyguard.cpp:131:13: note: in expansion of macro 'rep'
  131 |             rep(j, l, r) chmax(costX[j][y], C[i] / 2);
      |             ^~~
bodyguard.cpp:16:31: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   16 | #define repi(i, a, b) for (int(i) = (a); (i) < int(b); (i)++)
      |                               ^
bodyguard.cpp:14:43: note: in expansion of macro 'repi'
   14 | #define _overload3(_1, _2, _3, name, ...) name
      |                                           ^~~~
bodyguard.cpp:17:18: note: in expansion of macro '_overload3'
   17 | #define rep(...) _overload3(__VA_ARGS__, repi, _rep)(__VA_ARGS__)
      |                  ^~~~~~~~~~
bodyguard.cpp:136:13: note: in expansion of macro 'rep'
  136 |             rep(j, u, d) chmax(costY[x][j], C[i] / 2);
      |             ^~~
bodyguard.cpp:141:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  141 |             if (i != zx.size() - 1)
      |                 ~~^~~~~~~~~~~~~~~~
bodyguard.cpp:144:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  144 |             if (j != zy.size() - 1)
      |                 ~~^~~~~~~~~~~~~~~~
bodyguard.cpp:15:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   15 | #define _rep(i, n) for (int(i) = 0; (i) < int(n); (i)++)
      |                            ^
bodyguard.cpp:14:43: note: in expansion of macro '_rep'
   14 | #define _overload3(_1, _2, _3, name, ...) name
      |                                           ^~~~
bodyguard.cpp:17:18: note: in expansion of macro '_overload3'
   17 | #define rep(...) _overload3(__VA_ARGS__, repi, _rep)(__VA_ARGS__)
      |                  ^~~~~~~~~~
bodyguard.cpp:150:5: note: in expansion of macro 'rep'
  150 |     rep(i, Q) {
      |     ^~~
bodyguard.cpp:16:31: warning: unnecessary parentheses in declaration of 'x' [-Wparentheses]
   16 | #define repi(i, a, b) for (int(i) = (a); (i) < int(b); (i)++)
      |                               ^
bodyguard.cpp:14:43: note: in expansion of macro 'repi'
   14 | #define _overload3(_1, _2, _3, name, ...) name
      |                                           ^~~~
bodyguard.cpp:17:18: note: in expansion of macro '_overload3'
   17 | #define rep(...) _overload3(__VA_ARGS__, repi, _rep)(__VA_ARGS__)
      |                  ^~~~~~~~~~
bodyguard.cpp:155:5: note: in expansion of macro 'rep'
  155 |     rep(x, 1, zx.size()) {
      |     ^~~
bodyguard.cpp:16:31: warning: unnecessary parentheses in declaration of 'y' [-Wparentheses]
   16 | #define repi(i, a, b) for (int(i) = (a); (i) < int(b); (i)++)
      |                               ^
bodyguard.cpp:14:43: note: in expansion of macro 'repi'
   14 | #define _overload3(_1, _2, _3, name, ...) name
      |                                           ^~~~
bodyguard.cpp:17:18: note: in expansion of macro '_overload3'
   17 | #define rep(...) _overload3(__VA_ARGS__, repi, _rep)(__VA_ARGS__)
      |                  ^~~~~~~~~~
bodyguard.cpp:164:5: note: in expansion of macro 'rep'
  164 |     rep(y, 1, zy.size()) {
      |     ^~~
bodyguard.cpp:15:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   15 | #define _rep(i, n) for (int(i) = 0; (i) < int(n); (i)++)
      |                            ^
bodyguard.cpp:14:43: note: in expansion of macro '_rep'
   14 | #define _overload3(_1, _2, _3, name, ...) name
      |                                           ^~~~
bodyguard.cpp:17:18: note: in expansion of macro '_overload3'
   17 | #define rep(...) _overload3(__VA_ARGS__, repi, _rep)(__VA_ARGS__)
      |                  ^~~~~~~~~~
bodyguard.cpp:173:5: note: in expansion of macro 'rep'
  173 |     rep(i, Q) printf("%lld\n", ans[i]);
      |     ^~~
bodyguard.cpp:104:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  104 |     scanf("%d%d", &N, &Q);
      |     ~~~~~^~~~~~~~~~~~~~~~
bodyguard.cpp:105:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  105 |     rep(i, N) { scanf("%d%d%d%d", T + i, A + i, B + i, C + i); }
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bodyguard.cpp:106:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  106 |     rep(i, Q) { scanf("%d%d", P + i, X + i); }
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 7088 ms 1106420 KB Output is correct
2 Correct 6802 ms 1118968 KB Output is correct
3 Correct 2960 ms 953256 KB Output is correct
4 Correct 2047 ms 877428 KB Output is correct
5 Correct 4218 ms 1145596 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 2416 ms 1060804 KB Output is correct
2 Correct 2438 ms 1059964 KB Output is correct
3 Correct 2418 ms 1068204 KB Output is correct
4 Correct 459 ms 738844 KB Output is correct
5 Correct 2592 ms 1089868 KB Output is correct
6 Correct 2205 ms 970924 KB Output is correct
7 Correct 1789 ms 948004 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 2416 ms 1060804 KB Output is correct
2 Correct 2438 ms 1059964 KB Output is correct
3 Correct 2418 ms 1068204 KB Output is correct
4 Correct 459 ms 738844 KB Output is correct
5 Correct 2592 ms 1089868 KB Output is correct
6 Correct 2205 ms 970924 KB Output is correct
7 Correct 1789 ms 948004 KB Output is correct
8 Correct 2490 ms 1060756 KB Output is correct
9 Correct 2461 ms 1060508 KB Output is correct
10 Correct 2417 ms 1067040 KB Output is correct
11 Correct 453 ms 739140 KB Output is correct
12 Correct 2542 ms 1089908 KB Output is correct
13 Correct 2154 ms 971052 KB Output is correct
14 Correct 2991 ms 994388 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 2416 ms 1060804 KB Output is correct
2 Correct 2438 ms 1059964 KB Output is correct
3 Correct 2418 ms 1068204 KB Output is correct
4 Correct 459 ms 738844 KB Output is correct
5 Correct 2592 ms 1089868 KB Output is correct
6 Correct 2205 ms 970924 KB Output is correct
7 Correct 1789 ms 948004 KB Output is correct
8 Correct 2490 ms 1060756 KB Output is correct
9 Correct 2461 ms 1060508 KB Output is correct
10 Correct 2417 ms 1067040 KB Output is correct
11 Correct 453 ms 739140 KB Output is correct
12 Correct 2542 ms 1089908 KB Output is correct
13 Correct 2154 ms 971052 KB Output is correct
14 Correct 2991 ms 994388 KB Output is correct
15 Correct 2582 ms 1063540 KB Output is correct
16 Correct 2566 ms 1064160 KB Output is correct
17 Correct 2490 ms 1071164 KB Output is correct
18 Correct 482 ms 741104 KB Output is correct
19 Correct 2542 ms 1091928 KB Output is correct
20 Correct 2202 ms 973192 KB Output is correct
21 Correct 3085 ms 995916 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 7088 ms 1106420 KB Output is correct
2 Correct 6802 ms 1118968 KB Output is correct
3 Correct 2960 ms 953256 KB Output is correct
4 Correct 2047 ms 877428 KB Output is correct
5 Correct 4218 ms 1145596 KB Output is correct
6 Correct 2416 ms 1060804 KB Output is correct
7 Correct 2438 ms 1059964 KB Output is correct
8 Correct 2418 ms 1068204 KB Output is correct
9 Correct 459 ms 738844 KB Output is correct
10 Correct 2592 ms 1089868 KB Output is correct
11 Correct 2205 ms 970924 KB Output is correct
12 Correct 1789 ms 948004 KB Output is correct
13 Correct 2490 ms 1060756 KB Output is correct
14 Correct 2461 ms 1060508 KB Output is correct
15 Correct 2417 ms 1067040 KB Output is correct
16 Correct 453 ms 739140 KB Output is correct
17 Correct 2542 ms 1089908 KB Output is correct
18 Correct 2154 ms 971052 KB Output is correct
19 Correct 2991 ms 994388 KB Output is correct
20 Correct 2582 ms 1063540 KB Output is correct
21 Correct 2566 ms 1064160 KB Output is correct
22 Correct 2490 ms 1071164 KB Output is correct
23 Correct 482 ms 741104 KB Output is correct
24 Correct 2542 ms 1091928 KB Output is correct
25 Correct 2202 ms 973192 KB Output is correct
26 Correct 3085 ms 995916 KB Output is correct
27 Correct 7892 ms 1307140 KB Output is correct
28 Correct 7975 ms 1307600 KB Output is correct
29 Correct 5061 ms 1261916 KB Output is correct
30 Correct 1933 ms 897796 KB Output is correct
31 Correct 4364 ms 1196352 KB Output is correct
32 Correct 5565 ms 1147048 KB Output is correct
33 Correct 4377 ms 1153824 KB Output is correct