Submission #402007

#	Time	Username	Problem	Language	Result	Execution time	Memory
402007		doowey	Bodyguard (JOI21_bodyguard)	C++14	100 / 100	8752 ms	1281160 KiB

bodyguard

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int N = 2810;
const int M = N * 2;
const ll inf = (ll)1e18;
ll X[N], Y[N];
ll XX[N], YY[N];
ll val[N];
vector<ll> xc, yc;
ll XI[M][M];
ll YI[M][M];
ll dp[M][M];

const int Q = (int)3e6 + 10;

struct query{
    ll xcor;
    ll ycor;
    int idx;
};

vector<query> qq[M][M];
ll outp[Q];

struct line{
    ll ai;
    ll bi;
    ll lim;
};


ll divv(ll x, ll y){
    return (x / y - (x%y != 0 && (x^y) < 0));
}

ll inter(line p1, line p2){
    return divv(p1.bi - p2.bi, p2.ai - p1.ai);
}

struct hull{
    vector<line> st;
    void add_line(line qq){
        while(!st.empty() && qq.ai >= st.back().ai)
            st.pop_back();
        // assume qq.ai < las.ai
        /*
        ll p1, p2;
        while(st.size() >= 2){
            p1 = inter(st[st.size() - 1], qq);
            p2 = inter(st[st.size() - 2], qq);
            if(p1 < p2)
                break;
            st.pop_back();
        }
        if(st.size() > 0)
            st[st.size() - 1].lim = inter(st[st.size() - 1], qq);
        */
        qq.lim = -(ll)1e18;
        st.push_back(qq);
    }
    ll bins(ll pp){
        ll soln = 0;
        for(auto x : st){
            soln = max(soln, x.ai * 1ll * pp + x.bi);
        }
        return soln;
    }
};

int main(){
    fastIO;
    int n, q;
    cin >> n >> q;
    ll start, en, tim;

    for(int i = 1; i <= n; i ++ ){
        cin >> tim >> start >> en >> val[i];
        start *= 2ll;
        tim *= 2ll;
        en *= 2ll;
        X[i] = tim + start;
        Y[i] = tim - start;
        tim += abs(en - start);
        XX[i] = tim + en;
        YY[i] = tim - en;
        xc.push_back(X[i]);
        yc.push_back(Y[i]);
        xc.push_back(XX[i]);
        yc.push_back(YY[i]);
    }
    sort(xc.begin(), xc.end());
    sort(yc.begin(), yc.end());
    xc.resize(unique(xc.begin(), xc.end()) - xc.begin());
    yc.resize(unique(yc.begin(), yc.end()) - yc.begin());
    int nn = xc.size();
    int mm = yc.size();
    int iq;
    for(int i = 1; i <= n; i ++ ){
        X[i] = lower_bound(xc.begin(), xc.end(), X[i]) - xc.begin();
        Y[i] = lower_bound(yc.begin(), yc.end(), Y[i]) - yc.begin();
        XX[i]= lower_bound(xc.begin(), xc.end(), XX[i]) - xc.begin();
        YY[i] = lower_bound(yc.begin(), yc.end(), YY[i]) - yc.begin();
        if(X[i] == XX[i]){
            for(int j = Y[i] + 1; j <= YY[i]; j ++ ){
                YI[X[i]][j] = max(YI[X[i]][j], val[i]);
            }
        }
        else{
            for(int j = X[i] + 1; j <= XX[i]; j ++ ){
                XI[j][Y[i]] = max(XI[j][Y[i]], val[i]);
            }
        }
    }
    for(int x = nn - 1; x >= 0 ; x -- ){
        for(int y = mm - 1; y >= 0; y -- ){
            if(x + 1 < nn)
                dp[x][y] = max(dp[x][y], dp[x + 1][y] + (xc[x + 1] - xc[x]) * 1ll * XI[x + 1][y]);
            if(y + 1 < mm)
                dp[x][y] = max(dp[x][y], dp[x][y + 1] + (yc[y + 1] - yc[y]) * 1ll * YI[x][y + 1]);
        }
    }
    ll xa, ya;
    int xlow, ylow;
    ll big;
    ll cc;
    for(int iq = 1; iq <= q; iq ++ ){
        cin >> tim >> start;
        tim *= 2ll;
        start *= 2ll;
        xa = tim + start;
        ya = tim - start;
        xlow = lower_bound(xc.begin(), xc.end(), xa) - xc.begin();
        ylow = lower_bound(yc.begin(), yc.end(), ya) - yc.begin();
        if(xlow == nn || ylow == mm){
            outp[iq] = 0;
            continue;
        }
        qq[xlow][ylow].push_back({xa, ya, iq});

        big = 0;
        /*
        for(int j = xlow; j < nn; j ++ ){
            big = max(big, dp[j][ylow] + (yc[ylow] - ya) * 1ll * YI[j][ylow]);
        }

        for(int j = ylow; j < mm ; j ++ ){
            big = max(big, dp[xlow][j] + (xc[xlow] - xa) * 1ll * XI[xlow][j]);
        }
        */

    }
    for(int qy = 0; qy < mm; qy ++ ){
        hull ash;
        for(int qx = nn - 1; qx >= 0; qx -- ){
            ash.add_line({YI[qx][qy],dp[qx][qy],-(ll)1e18});
            for(auto xx : qq[qx][qy]){
                outp[xx.idx] = max(outp[xx.idx], ash.bins(yc[qy] - xx.ycor));
            }
        }
    }
    for(int qx = 0; qx < nn; qx ++ ){
        hull ash;
        for(int qy = mm - 1; qy >= 0; qy -- ){
            ash.add_line({XI[qx][qy], dp[qx][qy], -(ll)1e18});
            for(auto xx : qq[qx][qy]){
                outp[xx.idx] = max(outp[xx.idx], ash.bins(xc[qx] - xx.xcor));
            }
        }
    }
    for(int iq = 1; iq <= q; iq ++ ){
        cout << outp[iq]/4ll << "\n";
    }
    return 0;
}

Compilation message (stderr)

bodyguard.cpp: In function 'int main()':
bodyguard.cpp:107:9: warning: unused variable 'iq' [-Wunused-variable]
  107 |     int iq;
      |         ^~
bodyguard.cpp:134:8: warning: variable 'big' set but not used [-Wunused-but-set-variable]
  134 |     ll big;
      |        ^~~
bodyguard.cpp:135:8: warning: unused variable 'cc' [-Wunused-variable]
  135 |     ll cc;
      |        ^~

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