oj.uz

Submission #427860

# Submission time Handle Problem Language Result Execution time Memory
427860 2021-06-15T02:19:41 Z CodePlatina Bodyguard (JOI21_bodyguard) C++17
0 / 100
 25000 ms 1249880 KB 
#include <bits/stdc++.h>
#define pii pair<int, int>
#define pll pair<long long, long long>
#define piii pair<int, pii>
#define tiii tuple<int, int, int>
#define tiiii tuple<int, int, int, int>
#define ff first
#define ss second
#define ee ss.ff
#define rr ss.ss

using namespace std;

struct line
{
    long long a, b;
    line(void) : a(0), b(-(long long)8e18-7) {}
    long long eval(long long x) { return a * x + b; }
};

struct Node
{
    line x;
    int l, r;
    Node(void) : x(), l(-1), r(-1) {}
};
vector<Node> lct;

int ins(int ind, long long s, long long e, line val)
{
    if(ind == -1)
    {
        ind = (int)lct.size();
        lct.emplace_back();
    }

    long long mid = s + e >> 1;
    line up = lct[ind].x;
    line dn = val;
    if(up.eval(s) < dn.eval(s)) swap(up, dn);
    if(up.eval(e) > dn.eval(e))
    {
        lct[ind].x = up;
        return ind;
    }
    else if(up.eval(mid) < dn.eval(mid))
    {
        lct[ind].x = dn;
        lct[ind].l = ins(lct[ind].l, s, mid, up);
        return ind;
    }
    else
    {
        lct[ind].x = up;
        lct[ind].r = ins(lct[ind].r, mid + 1, e, dn);
        return ind;
    }
}

long long qry(int ind, long long s, long long e, long long x)
{
    if(ind == -1) return -(long long)8e18-7;
    long long mid = s + e >> 1;
    if(x < mid) return max(lct[ind].x.eval(x), qry(lct[ind].l, s, mid, x));
    else if(x > mid) return max(lct[ind].x.eval(x), qry(lct[ind].r, mid + 1, e, x));
    return lct[ind].x.eval(x);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

//    freopen("in.txt", "r", stdin);

    int n, T; cin >> n >> T;
    tiiii A[n];
    for(auto &[a, b, c, d] : A) cin >> a >> b >> c >> d;

    vector<long long> prX, prY;
    for(auto &[a, b, c, d] : A)
    {
        if(b < c)
        {
            prX.push_back(1ll * a + b);
            prX.push_back(1ll * a - b + 2 * c);
            prY.push_back(1ll * a - b);
        }
        else
        {
            prX.push_back(1ll * a + b);
            prY.push_back(1ll * a + b - 2 * c);
            prY.push_back(1ll * a - b);
        }
    }
    prX.push_back((long long)4e9+7);
    prX.push_back(-(long long)4e9-7);
    prX.push_back((long long)4e9+7);
    prY.push_back(-(long long)4e9-7);
    sort(prX.begin(), prX.end());
    sort(prY.begin(), prY.end());
    prX.resize(unique(prX.begin(), prX.end()) - prX.begin());
    prY.resize(unique(prY.begin(), prY.end()) - prY.begin());

    int N = prX.size(), M = prY.size();
    int CX[N + 1][M + 1]{}, CY[N + 1][M + 1]{};
    for(auto &[a, b, c, d] : A)
    {
        if(b < c)
        {
            int x1 = lower_bound(prX.begin(), prX.end(), 1ll * a + b) - prX.begin();
            int x2 = lower_bound(prX.begin(), prX.end(), 1ll * a - b + 2 * c) - prX.begin();
            int y = lower_bound(prY.begin(), prY.end(), 1ll * a - b) - prY.begin();
            for(int j = x1; j < x2; ++j) CX[j][y] = max(CX[j][y], d / 2);
        }
        else
        {
            int x = lower_bound(prX.begin(), prX.end(), 1ll * a + b) - prX.begin();
            int y1 = lower_bound(prY.begin(), prY.end(), 1ll * a - b) - prY.begin();
            int y2 = lower_bound(prY.begin(), prY.end(), 1ll * a + b - 2 * c) - prY.begin();
            for(int j = y1; j < y2; ++j) CY[x][j] = max(CY[x][j], d / 2);
        }
    }

    long long dp[N + 1][M + 1]{};
    for(int i = N; i >= 0; --i)
    {
        for(int j = M; j >= 0; --j)
        {
            if(i < N) dp[i][j] = max(dp[i][j], dp[i + 1][j] + 1ll * CX[i][j] * (prX[i + 1] - prX[i]));
            if(j < M) dp[i][j] = max(dp[i][j], dp[i][j + 1] + 1ll * CY[i][j] * (prY[j + 1] - prY[j]));
        }
    }

//    for(int i = 0; i <= N; ++i)
//    {
//        for(int j = 0; j <= M; ++j)
//            cout << dp[i][j] << ' ';
//        cout << endl;
//    }

    vector<pll> lsX[N + 1][M + 1], lsY[N + 1][M + 1];
    for(int i = 0; i < T; ++i)
    {
        int x, y; cin >> x >> y;
        int xi = lower_bound(prX.begin(), prX.end(), x + y) - prX.begin();
        int yi = lower_bound(prY.begin(), prY.end(), x - y) - prY.begin();
        lsX[xi][yi].push_back({prX[xi] - x - y, i});
        lsY[xi][yi].push_back({prY[yi] - x + y, i});
    }


    long long ans[T]{};
    for(int i = 1; i <= N; ++i)
    {
        lct.clear();
        lct.emplace_back();

        for(int j = M; j >= 0; --j)
        {
            line tmp;
            tmp.a = CX[i - 1][j];
            tmp.b = dp[i][j];
            ins(0, -(long long)4e9-7, (long long)4e9+7, tmp);
            for(auto [x, q] : lsX[i][j])
                ans[q] = max(ans[q], qry(0, -(long long)4e9-7, (long long)4e9+7, x));
        }
    }
    for(int j = 1; j <= M; ++j)
    {
        lct.clear();
        lct.emplace_back();

        for(int i = N; i >= 0; --i)
        {
            line tmp;
            tmp.a = CY[i][j - 1];
            tmp.b = dp[i][j];
            ins(0, -(long long)4e9-7, (long long)4e9+7, tmp);
            for(auto [x, q] : lsY[i][j])
                ans[q] = max(ans[q], qry(0, -(long long)4e9-7, (long long)4e9+7, x));
        }
    }

    for(auto i : ans) cout << i << '\n';
}

Compilation message

bodyguard.cpp: In function 'int ins(int, long long int, long long int, line)':
bodyguard.cpp:37:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   37 |     long long mid = s + e >> 1;
      |                     ~~^~~
bodyguard.cpp: In function 'long long int qry(int, long long int, long long int, long long int)':
bodyguard.cpp:63:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   63 |     long long mid = s + e >> 1;
      |                     ~~^~~

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 11400 ms 771524 KB Output is correct
2 Correct 11249 ms 802156 KB Output is correct
3 Correct 4916 ms 357168 KB Output is correct
4 Correct 2795 ms 203332 KB Output is correct
5 Execution timed out 25172 ms 1249880 KB Time limit exceeded

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7704 ms 1107132 KB Output is correct
2 Correct 8590 ms 1107136 KB Output is correct
3 Correct 13613 ms 1092124 KB Output is correct
4 Correct 133 ms 1868 KB Output is correct
5 Execution timed out 25144 ms 1107004 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7704 ms 1107132 KB Output is correct
2 Correct 8590 ms 1107136 KB Output is correct
3 Correct 13613 ms 1092124 KB Output is correct
4 Correct 133 ms 1868 KB Output is correct
5 Execution timed out 25144 ms 1107004 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7704 ms 1107132 KB Output is correct
2 Correct 8590 ms 1107136 KB Output is correct
3 Correct 13613 ms 1092124 KB Output is correct
4 Correct 133 ms 1868 KB Output is correct
5 Execution timed out 25144 ms 1107004 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 11400 ms 771524 KB Output is correct
2 Correct 11249 ms 802156 KB Output is correct
3 Correct 4916 ms 357168 KB Output is correct
4 Correct 2795 ms 203332 KB Output is correct
5 Execution timed out 25172 ms 1249880 KB Time limit exceeded