Submission #583318

#	Time	Username	Problem	Language	Result	Execution time	Memory
583318		AriaH	Bodyguard (JOI21_bodyguard)	C++17	22 / 100	784 ms	827896 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 N = 9e3 + 10;
const int LOG = 20;
const ll mod = 1e9 + 7;
const ll inf = 2e9;

int n, q, T[N], T2[N], fir[N], sec[N], Qa[N], Qb[N], C[N], dp[N][N], R[N][N], U[N][N];

vector < int > cmx, cmy;

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(); }

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] >>= 1;
        Add(T[i] + fir[i], T[i] - fir[i]);
        Add(T2[i] + sec[i], T2[i] - sec[i]);
    }
    for(int i = 1; i <= q; i ++)
    {
        cin >> Qa[i] >> Qb[i];
        Add(Qa[i] + Qb[i], Qa[i] - Qb[i]);
    }
    Add(inf, inf);
    sort(all(cmx));
    sort(all(cmy));
    cmx.resize(unique(all(cmx)) - cmx.begin());
    cmy.resize(unique(all(cmy)) - cmy.begin());
    int sz1 = SZ(cmx), sz2 = SZ(cmy);
    for(int i = 1; i <= n; i ++)
    {
        if(fir[i] < sec[i]) /// going up
        {
            int y = lwry(T[i] - fir[i]);
            int l = lwrx(T[i] + fir[i]), r = lwrx(T2[i] + sec[i]);
            for(int j = l; j < r; j ++)
            {
                U[j][y] = max(U[j][y], C[i]);
            }
        }
        else /// going right
        {
            int x = lwrx(T[i] + fir[i]);
            int l = lwry(T[i] - fir[i]), r = lwry(T2[i] - sec[i]);
            for(int j = l; j < r; j ++)
            {
                R[x][j] = max(R[x][j], C[i]);
            }
        }
    }
    for(int i = sz1 - 1; ~i; i --)
    {
        for(int j = sz2 - 1; ~j; j --)
        {
            if(i + 1 < sz1)
            {
                dp[i][j] = max(dp[i][j], dp[i + 1][j] + U[i][j] * (cmx[i + 1] - cmx[i]));
            }
            if(j + 1 < sz2)
            {
                dp[i][j] = max(dp[i][j], dp[i][j + 1] + R[i][j] * (cmy[j + 1] - cmy[j]));
            }
        }
    }
    for(int i = 1; i <= q; i ++)
    {
        cout << dp[lwrx(Qa[i] + Qb[i])][lwry(Qa[i] - Qb[i])] << endl;
    }
	return 0;
}

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