oj.uz

Submission #583430

# Submission time Handle Problem Language Result Execution time Memory
583430 2022-06-25T10:50:02 Z AriaH Bodyguard (JOI21_bodyguard) C++17
100 / 100
 13884 ms 1474896 KB 
#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.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 8188 ms 1236364 KB Output is correct
2 Correct 7830 ms 1238108 KB Output is correct
3 Correct 3102 ms 1089512 KB Output is correct
4 Correct 1676 ms 1028540 KB Output is correct
5 Correct 7998 ms 1280580 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 9826 ms 1160408 KB Output is correct
2 Correct 8575 ms 1160376 KB Output is correct
3 Correct 8337 ms 1163696 KB Output is correct
4 Correct 437 ms 853792 KB Output is correct
5 Correct 6904 ms 1335356 KB Output is correct
6 Correct 6344 ms 1124708 KB Output is correct
7 Correct 4577 ms 1094096 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 9826 ms 1160408 KB Output is correct
2 Correct 8575 ms 1160376 KB Output is correct
3 Correct 8337 ms 1163696 KB Output is correct
4 Correct 437 ms 853792 KB Output is correct
5 Correct 6904 ms 1335356 KB Output is correct
6 Correct 6344 ms 1124708 KB Output is correct
7 Correct 4577 ms 1094096 KB Output is correct
8 Correct 8858 ms 1160824 KB Output is correct
9 Correct 8699 ms 1160824 KB Output is correct
10 Correct 8507 ms 1162940 KB Output is correct
11 Correct 443 ms 854120 KB Output is correct
12 Correct 6929 ms 1335916 KB Output is correct
13 Correct 6276 ms 1125092 KB Output is correct
14 Correct 6509 ms 1097676 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9826 ms 1160408 KB Output is correct
2 Correct 8575 ms 1160376 KB Output is correct
3 Correct 8337 ms 1163696 KB Output is correct
4 Correct 437 ms 853792 KB Output is correct
5 Correct 6904 ms 1335356 KB Output is correct
6 Correct 6344 ms 1124708 KB Output is correct
7 Correct 4577 ms 1094096 KB Output is correct
8 Correct 8858 ms 1160824 KB Output is correct
9 Correct 8699 ms 1160824 KB Output is correct
10 Correct 8507 ms 1162940 KB Output is correct
11 Correct 443 ms 854120 KB Output is correct
12 Correct 6929 ms 1335916 KB Output is correct
13 Correct 6276 ms 1125092 KB Output is correct
14 Correct 6509 ms 1097676 KB Output is correct
15 Correct 8843 ms 1164240 KB Output is correct
16 Correct 8943 ms 1164860 KB Output is correct
17 Correct 8312 ms 1168420 KB Output is correct
18 Correct 463 ms 856816 KB Output is correct
19 Correct 6912 ms 1338444 KB Output is correct
20 Correct 6358 ms 1128076 KB Output is correct
21 Correct 6513 ms 1100504 KB Output is correct

Subtask #5
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 8188 ms 1236364 KB Output is correct
2 Correct 7830 ms 1238108 KB Output is correct
3 Correct 3102 ms 1089512 KB Output is correct
4 Correct 1676 ms 1028540 KB Output is correct
5 Correct 7998 ms 1280580 KB Output is correct
6 Correct 9826 ms 1160408 KB Output is correct
7 Correct 8575 ms 1160376 KB Output is correct
8 Correct 8337 ms 1163696 KB Output is correct
9 Correct 437 ms 853792 KB Output is correct
10 Correct 6904 ms 1335356 KB Output is correct
11 Correct 6344 ms 1124708 KB Output is correct
12 Correct 4577 ms 1094096 KB Output is correct
13 Correct 8858 ms 1160824 KB Output is correct
14 Correct 8699 ms 1160824 KB Output is correct
15 Correct 8507 ms 1162940 KB Output is correct
16 Correct 443 ms 854120 KB Output is correct
17 Correct 6929 ms 1335916 KB Output is correct
18 Correct 6276 ms 1125092 KB Output is correct
19 Correct 6509 ms 1097676 KB Output is correct
20 Correct 8843 ms 1164240 KB Output is correct
21 Correct 8943 ms 1164860 KB Output is correct
22 Correct 8312 ms 1168420 KB Output is correct
23 Correct 463 ms 856816 KB Output is correct
24 Correct 6912 ms 1338444 KB Output is correct
25 Correct 6358 ms 1128076 KB Output is correct
26 Correct 6513 ms 1100504 KB Output is correct
27 Correct 12042 ms 1463260 KB Output is correct
28 Correct 13884 ms 1456052 KB Output is correct
29 Correct 10401 ms 1409552 KB Output is correct
30 Correct 1491 ms 1072832 KB Output is correct
31 Correct 8125 ms 1474896 KB Output is correct
32 Correct 8175 ms 1364324 KB Output is correct
33 Correct 7585 ms 1318292 KB Output is correct