Submission #583430

#	Time	Username	Problem	Language	Result	Execution time	Memory
583430		AriaH	Bodyguard (JOI21_bodyguard)	C++17	100 / 100	13884 ms	1474896 KiB

bodyguard

#pragma GCC optimize("O3")

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair < int, int > pii;
typedef pair < ll, ll > pll;

#define F first
#define S second
#define all(x) x.begin(), x.end()
#define SZ(x) (int)x.size()
#define Mp make_pair
#define endl "\n"
#define fast_io ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define int ll

const int M = 3e3 + 10;
const int N = 2 * M;
const int N2 = 3e6 + 10;
const int LOG = 20;
const ll mod = 1e9 + 7;
const ll inf = 4e9;

typedef pair < ll , ll > Line;
struct CHT{
    set < pair < Line , ll > > S;
    set < pair < ll , Line > > I;
    ll INF = 4e18;
    inline void Add(Line X)
    {
        ll t = -INF;
        auto it = S.lower_bound({X, -INF});
        while ((int)S.size())
        {
            if (it == S.begin())
                {t = -INF; break;}
            it --; ll r = Intersection(it->first, X);
            if (r <= it->second)
                I.erase({it->second, it->first}), it = S.erase(it);
            else
                {t = r; break;}
        }
        it = S.lower_bound({X, -INF});
        while ((int)S.size())
        {
            if (it == S.end())
                break;
            ll r = Intersection(X, it->first);
            Line Y = it->first;
            I.erase({it->second, it->first});
            it = S.erase(it);
            if (r <= t)
            {
                r = -INF;
                if (it != S.begin())
                    it --, r = Intersection(it->first, Y);
                S.insert({Y, r}); I.insert({r, Y}); return ;
            }
            if (it != S.end() && it->second <= r)
                continue;
            S.insert({Y, r}); I.insert({r, Y}); break;
        }
        S.insert({X, t}); I.insert({t, X});
    }
    inline ll GetMax(ll X)
    {
        auto it = I.upper_bound({X, {INF, INF}}); it --;
        return (X * it->second.first + it->second.second);
    }
    inline ll Intersection(Line X, Line Y)
    {
        if (X.first == Y.first && X.second <= Y.second)
            return (-INF);
        if (X.first == Y.first)
            return (INF);
        return ((X.second - Y.second) / (Y.first - X.first)) + ((X.second - Y.second) % (Y.first - X.first) > 0);
    }
};
CHT row[N], col[N];

int n, q, T[M], T2[M], fir[M], sec[M], C[M], dp[N][N], R[N][N], U[N][N], Qa[N2], Qb[N2], Ans[N2], EX[N2], EY[N2];

vector < int > cmx, cmy;

vector < int > vec[N][N];

void Add(int a, int b)
{
    cmx.push_back(a);
    cmy.push_back(b);
}

inline int lwrx(int a) { return lower_bound(all(cmx), a) - cmx.begin(); }

inline int lwry(int a) { return lower_bound(all(cmy), a) - cmy.begin(); }

pii ask(int a, int b)
{
    return Mp(lwrx(a), lwry(b));
}

signed main()
{
    fast_io;
    cin >> n >> q;
    for(int i = 1; i <= n; i ++)
    {
        cin >> T[i] >> fir[i] >> sec[i] >> C[i];
        T2[i] = T[i] + abs(fir[i] - sec[i]);
        C[i] /= 2;
        Add(T[i] + fir[i], T[i] - fir[i]);
        Add(T2[i] + sec[i], T2[i] - sec[i]);
    }
    Add(inf, inf);
    Add(-inf, -inf);
    sort(all(cmx));
    sort(all(cmy));
    cmx.resize(unique(all(cmx)) - cmx.begin());
    cmy.resize(unique(all(cmy)) - cmy.begin());
    for(int i = 1; i <= q; i ++)
    {
        cin >> Qa[i] >> Qb[i];
        int a = lwrx(Qa[i] + Qb[i]), b = lwry(Qa[i] - Qb[i]);
        vec[a][b].push_back(i);
        EX[i] = cmx[a] - (Qa[i] + Qb[i]);
        EY[i] = cmy[b] - (Qa[i] - Qb[i]);
    }
    int sz1 = SZ(cmx), sz2 = SZ(cmy);
    for(int i = 1; i <= n; i ++)
    {
        pii A = ask(T[i] + fir[i], T[i] - fir[i]), B = ask(T2[i] + sec[i], T2[i] - sec[i]);
        if(A.F == B.F) /// going up
        {
            for(int j = A.S; j < B.S; j ++)
            {
                U[A.F][j] = max(U[A.F][j], C[i]);
            }
        }
        else /// going right
        {
            for(int j = A.F; j < B.F; j ++)
            {
                R[j][A.S] = max(R[j][A.S], C[i]);
            }
        }
    }
    for(int i = sz1 - 1; i > 0; i --)
    {
        for(int j = sz2 - 1; j > 0; j --)
        {
            if(i + 1 < sz1 && j + 1 < sz2)
            {
                dp[i][j] = max(dp[i][j], dp[i + 1][j] + R[i][j] * (cmx[i + 1] - cmx[i]));
                dp[i][j] = max(dp[i][j], dp[i][j + 1] + U[i][j] * (cmy[j + 1] - cmy[j]));
            }
            col[i].Add({R[i - 1][j], dp[i][j]});
            row[j].Add({U[i][j - 1], dp[i][j]});
            for(auto id : vec[i][j])
            {
                Ans[id] = max(row[j].GetMax(EY[id]), col[i].GetMax(EX[id]));
            }
        }
    }
    for(int i = 1; i <= q; i ++)
    {
        cout << Ans[i] << endl;
    }
	return 0;
}

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