Submission #386905

#	Time	Username	Problem	Language	Result	Execution time	Memory
386905		keko37	Bodyguard (JOI21_bodyguard)	C++14	100 / 100	5270 ms	497724 KiB

bodyguard

#include<bits/stdc++.h>

using namespace std;

typedef long long llint;
typedef pair <llint, llint> pi;

const int MAXN = 2805;
const int MAXQ = 3000005;

int n, q;
int cost[MAXN];
pi pa[MAXN], pb[MAXN];
int upp[MAXN*3][MAXN*3], rig[MAXN*3][MAXN*3];
llint dp[MAXN*3][MAXN*3];
llint qx[MAXQ], qy[MAXQ], sol[MAXQ];
vector <llint> vx, vy;
vector <pi> ux[MAXN*3], uy[MAXN*3];
deque <pi> hull;

void precompute () {
    for (int i = 1; i <= n; i++) {
        vx.push_back(pa[i].first); vy.push_back(pa[i].second);
        vx.push_back(pb[i].first); vy.push_back(pb[i].second);
    }
    sort(vx.begin(), vx.end());
    vx.erase(unique(vx.begin(), vx.end()), vx.end());
    sort(vy.begin(), vy.end());
    vy.erase(unique(vy.begin(), vy.end()), vy.end());

    for (int i = 1; i <= n; i++) {
        int ix = lower_bound(vx.begin(), vx.end(), pa[i].first) - vx.begin();
        int iy = lower_bound(vy.begin(), vy.end(), pa[i].second) - vy.begin();
        int jx = lower_bound(vx.begin(), vx.end(), pb[i].first) - vx.begin();
        int jy = lower_bound(vy.begin(), vy.end(), pb[i].second) - vy.begin();
        if (iy == jy) {
            for (int k = ix; k < jx; k++) {
                rig[k][iy] = max(rig[k][iy], cost[i]);
            }
        } else {
            for (int k = iy; k < jy; k++) {
                upp[ix][k] = max(upp[ix][k], cost[i]);
            }
        }
    }

    for (int i = (int)vx.size() - 1; i >= 0; i--) {
        for (int j = (int) vy.size() - 1; j >= 0; j--) {
            llint res = 0;
            if (i + 1 < vx.size()) res = max(res, dp[i + 1][j] + rig[i][j] * (vx[i + 1] - vx[i]));
            if (j + 1 < vy.size()) res = max(res, dp[i][j + 1] + upp[i][j] * (vy[j + 1] - vy[j]));
            dp[i][j] = res;
        }
    }
}

void obradi (int ind) {
    llint x = qx[ind], y = qy[ind];
    int i = lower_bound(vx.begin(), vx.end(), x) - vx.begin();
    int j = lower_bound(vy.begin(), vy.end(), y) - vy.begin();
    sol[ind] = dp[i][j];
    if (i - 1 >= 0 && i < vx.size() && x != vx[i]) ux[i].push_back({y, ind});
    if (j - 1 >= 0 && j < vy.size() && y != vy[j]) uy[j].push_back({x, ind});
}

__int128 ccw (pi a, pi b, pi c) {
    return (__int128)a.first * (b.second - c.second) + (__int128)b.first * (c.second - a.second) + (__int128)c.first * (a.second - b.second);
}

llint f (pi pt, llint val) {
    return pt.first * val + pt.second;
}

void ubaci (pi pt) {
    while (hull.size() >= 1 && pt.first >= hull[0].first) hull.pop_front();
    while (hull.size() >= 2 && ccw(pt, hull[0], hull[1]) >= 0) hull.pop_front();
    hull.push_front(pt);
}

llint upit (llint val) {
    if (hull.empty()) return 0;
    int lo = 0, hi = hull.size() - 1;
    while (lo < hi) {
        int mid = (lo + hi) / 2;
        if (f(hull[mid], val) >= f(hull[mid + 1], val)) {
            hi = mid;
        } else {
            lo = mid + 1;
        }
    }
    return f(hull[lo], val);
}

void calc_x (int pos) {
    hull.clear();
    int p = (int)vy.size() - 1;
    sort(ux[pos].begin(), ux[pos].end());
    for (int i = (int)ux[pos].size() - 1; i >= 0; i--) {
        int ind = ux[pos][i].second;
        llint val = vx[pos] - qx[ind];
        while (p >= 0 && vy[p] >= qy[ind]) {
            ubaci({rig[pos - 1][p], dp[pos][p]});
            p--;
        }
        sol[ind] = max(sol[ind], upit(val));
    }
}

void calc_y (int pos) {
    hull.clear();
    int p = (int)vx.size() - 1;
    sort(uy[pos].begin(), uy[pos].end());
    for (int i = (int)uy[pos].size() - 1; i >= 0; i--) {
        int ind = uy[pos][i].second;
        llint val = vy[pos] - qy[ind];
        while (p >= 0 && vx[p] >= qx[ind]) {
            ubaci({upp[p][pos - 1], dp[p][pos]});
            p--;
        }
        sol[ind] = max(sol[ind], upit(val));
    }
}

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        int t, a, b;
        cin >> t >> a >> b >> cost[i];
        cost[i] /= 2;

        llint x = t, y = a;
        pa[i] = {x - y, x + y};
        x = t + abs(a - b), y = b;
        pb[i] = {x - y, x + y};
    }
    precompute();
    for (int i = 1; i <= q; i++) {
        int x, y;
        cin >> x >> y;
        qx[i] = x - y; qy[i] = x + y;
        obradi(i);
    }
    for (int i = (int)vx.size() - 1; i >= 1; i--) calc_x(i);
    for (int i = (int)vy.size() - 1; i >= 1; i--) calc_y(i);
    for (int i = 1; i <= q; i++) {
        cout << sol[i] << '\n';
    }
    return 0;
}

Compilation message (stderr)

bodyguard.cpp: In function 'void precompute()':
bodyguard.cpp:50:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |             if (i + 1 < vx.size()) res = max(res, dp[i + 1][j] + rig[i][j] * (vx[i + 1] - vx[i]));
      |                 ~~~~~~^~~~~~~~~~~
bodyguard.cpp:51:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |             if (j + 1 < vy.size()) res = max(res, dp[i][j + 1] + upp[i][j] * (vy[j + 1] - vy[j]));
      |                 ~~~~~~^~~~~~~~~~~
bodyguard.cpp: In function 'void obradi(int)':
bodyguard.cpp:62:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |     if (i - 1 >= 0 && i < vx.size() && x != vx[i]) ux[i].push_back({y, ind});
      |                       ~~^~~~~~~~~~~
bodyguard.cpp:63:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |     if (j - 1 >= 0 && j < vy.size() && y != vy[j]) uy[j].push_back({x, ind});
      |                       ~~^~~~~~~~~~~

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