Submission #574665

#	Time	Username	Problem	Language	Result	Execution time	Memory
574665		balbit	Bodyguard (JOI21_bodyguard)	C++14	100 / 100	7736 ms	1290400 KiB

bodyguard

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll
#define y1 zck_is_king
#define pii pair<int, int>
#define ull unsigned ll
#define f first
#define s second
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
#define SQ(x) (x)*(x)
#define MN(a,b) a = min(a,(__typeof__(a))(b))
#define MX(a,b) a = max(a,(__typeof__(a))(b))
#define pb push_back
#define REP(i,n) for (int i = 0; i<n; ++i)
#define RREP(i,n) for (int i = n-1; i>=0; --i)
#define REP1(i,n) for (int i = 1; i<=n; ++i)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#ifdef BALBIT
#define IOS()
#define bug(...) fprintf(stderr,"#%d (%s) = ",__LINE__,#__VA_ARGS__),_do(__VA_ARGS__);
template<typename T> void _do(T &&x){cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T &&x, S &&...y){cerr<<x<<", ";_do(y...);}
#else
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);
#define endl '\n'
#define bug(...)
#endif

const int iinf = 1e9+10;
const ll inf = 1ll<<60;
const ll mod = 1e9+7 ;


void GG(){cout<<"0\n"; exit(0);}

ll mpow(ll a, ll n, ll mo = mod){ // a^n % mod
    ll re=1;
    while (n>0){
        if (n&1) re = re*a %mo;
        a = a*a %mo;
        n>>=1;
    }
    return re;
}

ll inv (ll b, ll mo = mod){
    if (b==1) return b;
    return (mo-mo/b) * inv(mo%b,mo) % mo;
}

const int maxn = 2800*2+5;

//ll xat[maxn], yat[maxn];
ll rt[maxn][maxn], dw[maxn][maxn]; // right (m++), down (n++)
ll dp[maxn][maxn];

struct seg{
    ll l,r,h,c;
};

vector<seg> dseg, rseg;
vector<ll> dax, rax; // axis lines

ll ans[3000005];
//struct ask{
//    signed df, i;
//};

vector<signed> ha[maxn][maxn];

bool QTYPE=0;
struct Line {
    mutable ll m, b, p;
    bool operator<(const Line& o) const {
        if (QTYPE) return p<o.p;
        return m < o.m;
    }
};

struct LineContainer : multiset<Line > {
    const ll INF = LLONG_MAX;
    ll div(ll A, ll B) {
        return A / B - ((A ^ B) < 0 && A % B); }
    bool isect(iterator x, iterator y) {
        if (y == end()) { x->p = INF; return false; }
        if (x->m == y->m) x->p = x->b > y->b ? INF : -INF;
        else x->p = div(y->b - x->b, x->m - y->m);
        return x->p >= y->p;}
    void add(ll m, ll b) {
        auto z = insert({m, b, 0}), y = z++, x = y;
        while (isect(y, z)) z = erase(z);
        if (x != begin() && isect(--x, y)) isect(x, y = erase(y));
        while ((y = x) != begin() && (--x)->p >= y->p)
            isect(x, erase(y));}
    ll query(ll x) {
        assert(!empty());
        QTYPE=1; auto l = *lower_bound({0,0,x}); QTYPE = 0;
        return l.m * x + l.b; }
};


signed main(){
    IOS();

    int n,q; cin>>n>>q;

    REP(i,n) {
        int t,a,b,c; cin>>t>>a>>b>>c;
        if (a < b) {
            // down segment
            dseg.pb({t+a, t+b-a+b, t-a, c});
            bug("down", t-a, t+a, t+b-a+b);
            bug(c);
        }else{
            // right seg
            rseg.pb({t-a, t+(a-b)-b, t+a, c});
            bug("right", t+a, t-a, t+(a-b)-b);
            bug(c);
        }
    }
    for (auto s : dseg) {
        dax.pb(s.h);
        rax.pb(s.l);
        rax.pb(s.r);
    }
    for (auto s : rseg) {
        rax.pb(s.h);
        dax.pb(s.l);
        dax.pb(s.r);
    }

    SORT_UNIQUE(rax);
    SORT_UNIQUE(dax);

    auto getr = [&](ll x) {return lower_bound(ALL(rax), x) - rax.begin();};
    auto getd = [&](ll x) {return lower_bound(ALL(dax), x) - dax.begin();};

    for (auto s : dseg) {
        // work on dw array
        int L = getr(s.l), R = getr(s.r);
        int H = getd(s.h);
        for (int i = L; i<R; ++i) {
            MX(dw[i][H], s.c);
        }
    }

    for (auto s : rseg) {
        // work on rt array
        int L = getd(s.l), R = getd(s.r);
        int H = getr(s.h);
        for (int i = L; i<R; ++i) {
            MX(rt[H][i], s.c);
        }
    }

    int N = SZ(rax), M = SZ(dax);

    for (int i = N-1; i>=0; --i) for (int j = M-1; j>=0; --j) {
        if (i + 1 < N) {
            MX(dp[i][j], dp[i+1][j] + (rax[i+1] - rax[i])*dw[i][j]);
        }
        if (j + 1 < M) {
            MX(dp[i][j], dp[i][j+1] + (dax[j+1] - dax[j])*rt[i][j]);
        }
        bug(i,j,rax[i],dax[j],dp[i][j]);
    }

    vector<int> qR(q), qC(q);

    REP(i, q) {
        int t,x; cin>>t>>x;
        int r = t+x, c = t-x;
        tie(qR[i], qC[i]) = {r,c};
        int dpos = getd(c), rpos = getr(r);
        if (dpos >= M || rpos >= N) continue;
        bug(r,c,dpos,rpos);
        ha[rpos][dpos].pb(i);
//        dask[rpos][dpos].pb({dax[dpos] - c, i});
//        rask[rpos][dpos].pb({rax[rpos] - r, i});
    }

    REP(i,N) {
        LineContainer hull;
        for (int j = M-1; j>=0; --j) {
            hull.add(i?dw[i-1][j]:0, dp[i][j]);
            for (int it : ha[i][j]) {
                int df = rax[i] - qR[it];
//                bug(aa.i, aa.df, hull.query(aa.df));
                MX(ans[it], hull.query(df));
            }
        }
    }

    REP(j,M) {
        LineContainer hull;
        for (int i = N-1; i>=0; --i) {
            hull.add(j?rt[i][j-1]:0, dp[i][j]);
            for (int it : ha[i][j]) {
                int df = dax[j] - qC[it];
//                bug(aa.i, aa.df, hull.query(aa.df));
                MX(ans[it], hull.query(df));
            }
        }
    }


    REP(i,q) {
        cout<<ans[i]/2<<endl;
    }
}

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