Submission #431764

#	Time	Username	Problem	Language	Result	Execution time	Memory
431764		CodePlatina	Bodyguard (JOI21_bodyguard)	C++17	0 / 100	7048 ms	1106852 KiB

bodyguard

#include <bits/stdc++.h>
#define pii pair<int, int>
#define pll pair<long long, long long>
#define piii pair<int, pii>
#define tiii tuple<int, int, int>
#define tiiii tuple<int, int, int, int>
#define ff first
#define ss second
#define ee ss.ff
#define rr ss.ss

using namespace std;

const long long INF = (long long)1e9 + 7;

struct line
{
    long long a, b;
    line(void) : a(0), b(0) {}
    long long eval(long long x) { return a * x + b; }
};

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

//    freopen("in.txt", "r", stdin);

    int n, T; cin >> n >> T;
    tiiii A[n];
    for(auto &[a, b, c, d] : A) cin >> a >> b >> c >> d;

    vector<long long> prX, prY;
    for(auto &[a, b, c, d] : A)
    {
        if(b < c)
        {
            prX.push_back(1ll * a + b);
            prX.push_back(1ll * a - b + 2 * c);
            prY.push_back(1ll * a - b + INF);
        }
        else
        {
            prX.push_back(1ll * a + b);
            prY.push_back(1ll * a - b + INF);
            prY.push_back(1ll * a + b - 2 * c + INF);
        }
    }
    prX.push_back(INF * 3);
    prX.push_back(-1);
    prY.push_back(INF * 3);
    prY.push_back(-1);
    sort(prX.begin(), prX.end());
    sort(prY.begin(), prY.end());
    prX.resize(unique(prX.begin(), prX.end()) - prX.begin());
    prY.resize(unique(prY.begin(), prY.end()) - prY.begin());

    int N = prX.size(), M = prY.size();
    int CX[N + 1][M + 1]{}, CY[N + 1][M + 1]{};
    for(auto &[a, b, c, d] : A)
    {
        if(b < c)
        {
            int x1 = lower_bound(prX.begin(), prX.end(), 1ll * a + b) - prX.begin();
            int x2 = lower_bound(prX.begin(), prX.end(), 1ll * a - b + 2 * c) - prX.begin();
            int y = lower_bound(prY.begin(), prY.end(), 1ll * a - b + INF) - prY.begin();
            for(int j = x1; j < x2; ++j) CX[j][y] = max(CX[j][y], d / 2);
        }
        else
        {
            int x = lower_bound(prX.begin(), prX.end(), 1ll * a + b) - prX.begin();
            int y1 = lower_bound(prY.begin(), prY.end(), 1ll * a - b + INF) - prY.begin();
            int y2 = lower_bound(prY.begin(), prY.end(), 1ll * a + b - 2 * c + INF) - prY.begin();
            for(int j = y1; j < y2; ++j) CY[x][j] = max(CY[x][j], d / 2);
        }
    }

    long long dp[N + 1][M + 1]{};
    for(int i = N; i >= 0; --i)
    {
        for(int j = M; j >= 0; --j)
        {
            if(i < N) dp[i][j] = max(dp[i][j], dp[i + 1][j] + 1ll * CX[i][j] * (prX[i + 1] - prX[i]));
            if(j < M) dp[i][j] = max(dp[i][j], dp[i][j + 1] + 1ll * CY[i][j] * (prY[j + 1] - prY[j]));
        }
    }

//    for(int i = 0; i <= N; ++i)
//    {
//        for(int j = 0; j <= M; ++j)
//            cout << dp[i][j] << ' ';
//        cout << endl;
//    }

    vector<pll> lsX[N + 1][M + 1], lsY[N + 1][M + 1];
    for(int i = 0; i < T; ++i)
    {
        int x, y; cin >> x >> y;
        int xi = lower_bound(prX.begin(), prX.end(), x + y) - prX.begin();
        int yi = lower_bound(prY.begin(), prY.end(), x - y + INF) - prY.begin();
        lsX[xi][yi].push_back({prX[xi] - x - y, i});
        lsY[xi][yi].push_back({prY[yi] - x + y - INF, i});
    }

    vector<line> S;

    long long ans[T]{};
    for(int i = 1; i <= N; ++i)
    {
        S.clear();
        S.emplace_back();

        for(int j = M; j >= 0; --j)
        {
            line tmp;
            tmp.a = CX[i - 1][j];
            tmp.b = dp[i][j];
            while(S.size() >= 2)
            {
                long long x = S[S.size() - 1].b - S[S.size() - 2].b;
                long long y = S[S.size() - 2].a - S[S.size() - 1].a;
                long long z = tmp.b - S[S.size() - 1].b;
                long long w = S[S.size() - 1].a - tmp.a;
                if(w <= 0 || x * w > y * z) S.pop_back();
                else break;
            }
            if(S.back().b == tmp.b) S.back().a = max(S.back().a, tmp.a);
            else if(S.back().a <= tmp.a) S.back() = tmp;
            else S.push_back(tmp);

            for(auto [x, q] : lsX[i][j])
            {
                int s = 0, e = S.size();
                while(s + 1 < e)
                {
                    int mid = s + e >> 1;
                    long long y = S[mid].b - S[mid - 1].b;
                    long long z = S[mid - 1].a - S[mid].a;
                    if(x * z < y) e = mid;
                    else s = mid;
                }
                ans[q] = max(ans[q], S[s].eval(x));
            }
        }
    }
    for(int j = 1; j <= M; ++j)
    {
        S.clear();
        S.emplace_back();

        for(int i = N; i >= 0; --i)
        {
            line tmp;
            tmp.a = CY[i][j - 1];
            tmp.b = dp[i][j];
            while(S.size() >= 2)
            {
                long long x = S[S.size() - 1].b - S[S.size() - 2].b;
                long long y = S[S.size() - 2].a - S[S.size() - 1].a;
                long long z = tmp.b - S[S.size() - 1].b;
                long long w = S[S.size() - 1].a - tmp.a;
                if(w <= 0 || x * w > y * z) S.pop_back();
                else break;
            }
            if(S.back().b == tmp.b) S.back().a = max(S.back().a, tmp.a);
            else if(S.back().a <= tmp.a) S.back() = tmp;
            else S.push_back(tmp);

            for(auto [x, q] : lsY[i][j])
            {
                int s = 0, e = S.size();
                while(s + 1 < e)
                {
                    int mid = s + e >> 1;
                    long long y = S[mid].b - S[mid - 1].b;
                    long long z = S[mid - 1].a - S[mid].a;
                    if(x * z < y) e = mid;
                    else s = mid;
                }
                ans[q] = max(ans[q], S[s].eval(x));
            }
        }
    }

    for(auto i : ans) cout << i << '\n';
}

Compilation message (stderr)

bodyguard.cpp: In function 'int main()':
bodyguard.cpp:137:33: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  137 |                     int mid = s + e >> 1;
      |                               ~~^~~
bodyguard.cpp:175:33: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  175 |                     int mid = s + e >> 1;
      |                               ~~^~~

• Subtask 1: 0 / 6
• Subtask 2: 0 / 7
• Subtask 3: 0 / 15
• Subtask 4: 0 / 20
• Subtask 5: 0 / 52