제출 #414940

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
414940		Pro_ktmr	Bodyguard (JOI21_bodyguard)	C++17	100 / 100	7975 ms	1307600 KiB

bodyguard

#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]);
}

컴파일 시 표준 에러 (stderr) 메시지

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); }
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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