Submission #414940

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
414940	2021-05-31T10:50:00 Z	Pro_ktmr	Bodyguard (JOI21_bodyguard)	C++17	100 / 100	7975 ms	1307600 KB

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

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

Subtask #1

5.0 / 5.0

#	Verdict	Execution time	Memory	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

Subtask #2

7.0 / 7.0

#	Verdict	Execution time	Memory	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

Subtask #3

15.0 / 15.0

#	Verdict	Execution time	Memory	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

Subtask #4

20.0 / 20.0

#	Verdict	Execution time	Memory	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

Subtask #5

53.0 / 53.0

#	Verdict	Execution time	Memory	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