oj.uz

Submission #402007

# Submission time Handle Problem Language Result Execution time Memory
402007 2021-05-11T07:28:55 Z doowey Bodyguard (JOI21_bodyguard) C++14
100 / 100
 8752 ms 1281160 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int N = 2810;
const int M = N * 2;
const ll inf = (ll)1e18;
ll X[N], Y[N];
ll XX[N], YY[N];
ll val[N];
vector<ll> xc, yc;
ll XI[M][M];
ll YI[M][M];
ll dp[M][M];

const int Q = (int)3e6 + 10;

struct query{
    ll xcor;
    ll ycor;
    int idx;
};

vector<query> qq[M][M];
ll outp[Q];

struct line{
    ll ai;
    ll bi;
    ll lim;
};


ll divv(ll x, ll y){
    return (x / y - (x%y != 0 && (x^y) < 0));
}

ll inter(line p1, line p2){
    return divv(p1.bi - p2.bi, p2.ai - p1.ai);
}

struct hull{
    vector<line> st;
    void add_line(line qq){
        while(!st.empty() && qq.ai >= st.back().ai)
            st.pop_back();
        // assume qq.ai < las.ai
        /*
        ll p1, p2;
        while(st.size() >= 2){
            p1 = inter(st[st.size() - 1], qq);
            p2 = inter(st[st.size() - 2], qq);
            if(p1 < p2)
                break;
            st.pop_back();
        }
        if(st.size() > 0)
            st[st.size() - 1].lim = inter(st[st.size() - 1], qq);
        */
        qq.lim = -(ll)1e18;
        st.push_back(qq);
    }
    ll bins(ll pp){
        ll soln = 0;
        for(auto x : st){
            soln = max(soln, x.ai * 1ll * pp + x.bi);
        }
        return soln;
    }
};

int main(){
    fastIO;
    int n, q;
    cin >> n >> q;
    ll start, en, tim;

    for(int i = 1; i <= n; i ++ ){
        cin >> tim >> start >> en >> val[i];
        start *= 2ll;
        tim *= 2ll;
        en *= 2ll;
        X[i] = tim + start;
        Y[i] = tim - start;
        tim += abs(en - start);
        XX[i] = tim + en;
        YY[i] = tim - en;
        xc.push_back(X[i]);
        yc.push_back(Y[i]);
        xc.push_back(XX[i]);
        yc.push_back(YY[i]);
    }
    sort(xc.begin(), xc.end());
    sort(yc.begin(), yc.end());
    xc.resize(unique(xc.begin(), xc.end()) - xc.begin());
    yc.resize(unique(yc.begin(), yc.end()) - yc.begin());
    int nn = xc.size();
    int mm = yc.size();
    int iq;
    for(int i = 1; i <= n; i ++ ){
        X[i] = lower_bound(xc.begin(), xc.end(), X[i]) - xc.begin();
        Y[i] = lower_bound(yc.begin(), yc.end(), Y[i]) - yc.begin();
        XX[i]= lower_bound(xc.begin(), xc.end(), XX[i]) - xc.begin();
        YY[i] = lower_bound(yc.begin(), yc.end(), YY[i]) - yc.begin();
        if(X[i] == XX[i]){
            for(int j = Y[i] + 1; j <= YY[i]; j ++ ){
                YI[X[i]][j] = max(YI[X[i]][j], val[i]);
            }
        }
        else{
            for(int j = X[i] + 1; j <= XX[i]; j ++ ){
                XI[j][Y[i]] = max(XI[j][Y[i]], val[i]);
            }
        }
    }
    for(int x = nn - 1; x >= 0 ; x -- ){
        for(int y = mm - 1; y >= 0; y -- ){
            if(x + 1 < nn)
                dp[x][y] = max(dp[x][y], dp[x + 1][y] + (xc[x + 1] - xc[x]) * 1ll * XI[x + 1][y]);
            if(y + 1 < mm)
                dp[x][y] = max(dp[x][y], dp[x][y + 1] + (yc[y + 1] - yc[y]) * 1ll * YI[x][y + 1]);
        }
    }
    ll xa, ya;
    int xlow, ylow;
    ll big;
    ll cc;
    for(int iq = 1; iq <= q; iq ++ ){
        cin >> tim >> start;
        tim *= 2ll;
        start *= 2ll;
        xa = tim + start;
        ya = tim - start;
        xlow = lower_bound(xc.begin(), xc.end(), xa) - xc.begin();
        ylow = lower_bound(yc.begin(), yc.end(), ya) - yc.begin();
        if(xlow == nn || ylow == mm){
            outp[iq] = 0;
            continue;
        }
        qq[xlow][ylow].push_back({xa, ya, iq});

        big = 0;
        /*
        for(int j = xlow; j < nn; j ++ ){
            big = max(big, dp[j][ylow] + (yc[ylow] - ya) * 1ll * YI[j][ylow]);
        }

        for(int j = ylow; j < mm ; j ++ ){
            big = max(big, dp[xlow][j] + (xc[xlow] - xa) * 1ll * XI[xlow][j]);
        }
        */

    }
    for(int qy = 0; qy < mm; qy ++ ){
        hull ash;
        for(int qx = nn - 1; qx >= 0; qx -- ){
            ash.add_line({YI[qx][qy],dp[qx][qy],-(ll)1e18});
            for(auto xx : qq[qx][qy]){
                outp[xx.idx] = max(outp[xx.idx], ash.bins(yc[qy] - xx.ycor));
            }
        }
    }
    for(int qx = 0; qx < nn; qx ++ ){
        hull ash;
        for(int qy = mm - 1; qy >= 0; qy -- ){
            ash.add_line({XI[qx][qy], dp[qx][qy], -(ll)1e18});
            for(auto xx : qq[qx][qy]){
                outp[xx.idx] = max(outp[xx.idx], ash.bins(xc[qx] - xx.xcor));
            }
        }
    }
    for(int iq = 1; iq <= q; iq ++ ){
        cout << outp[iq]/4ll << "\n";
    }
    return 0;
}

Compilation message

bodyguard.cpp: In function 'int main()':
bodyguard.cpp:107:9: warning: unused variable 'iq' [-Wunused-variable]
  107 |     int iq;
      |         ^~
bodyguard.cpp:134:8: warning: variable 'big' set but not used [-Wunused-but-set-variable]
  134 |     ll big;
      |        ^~~
bodyguard.cpp:135:8: warning: unused variable 'cc' [-Wunused-variable]
  135 |     ll cc;
      |        ^~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4518 ms 1059620 KB Output is correct
2 Correct 4561 ms 1088800 KB Output is correct
3 Correct 2189 ms 940256 KB Output is correct
4 Correct 2044 ms 867944 KB Output is correct
5 Correct 2707 ms 1143336 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1578 ms 1044480 KB Output is correct
2 Correct 1570 ms 1043780 KB Output is correct
3 Correct 1540 ms 1047644 KB Output is correct
4 Correct 410 ms 742720 KB Output is correct
5 Correct 1560 ms 981588 KB Output is correct
6 Correct 1511 ms 950896 KB Output is correct
7 Correct 1557 ms 981388 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1578 ms 1044480 KB Output is correct
2 Correct 1570 ms 1043780 KB Output is correct
3 Correct 1540 ms 1047644 KB Output is correct
4 Correct 410 ms 742720 KB Output is correct
5 Correct 1560 ms 981588 KB Output is correct
6 Correct 1511 ms 950896 KB Output is correct
7 Correct 1557 ms 981388 KB Output is correct
8 Correct 1591 ms 1044332 KB Output is correct
9 Correct 1586 ms 1043920 KB Output is correct
10 Correct 1545 ms 1046980 KB Output is correct
11 Correct 423 ms 742724 KB Output is correct
12 Correct 1585 ms 981672 KB Output is correct
13 Correct 1520 ms 951048 KB Output is correct
14 Correct 1557 ms 981652 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1578 ms 1044480 KB Output is correct
2 Correct 1570 ms 1043780 KB Output is correct
3 Correct 1540 ms 1047644 KB Output is correct
4 Correct 410 ms 742720 KB Output is correct
5 Correct 1560 ms 981588 KB Output is correct
6 Correct 1511 ms 950896 KB Output is correct
7 Correct 1557 ms 981388 KB Output is correct
8 Correct 1591 ms 1044332 KB Output is correct
9 Correct 1586 ms 1043920 KB Output is correct
10 Correct 1545 ms 1046980 KB Output is correct
11 Correct 423 ms 742724 KB Output is correct
12 Correct 1585 ms 981672 KB Output is correct
13 Correct 1520 ms 951048 KB Output is correct
14 Correct 1557 ms 981652 KB Output is correct
15 Correct 1632 ms 1047268 KB Output is correct
16 Correct 1626 ms 1047016 KB Output is correct
17 Correct 1578 ms 1050756 KB Output is correct
18 Correct 449 ms 744212 KB Output is correct
19 Correct 1636 ms 984356 KB Output is correct
20 Correct 1593 ms 953908 KB Output is correct
21 Correct 1573 ms 983808 KB Output is correct

Subtask #5
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 4518 ms 1059620 KB Output is correct
2 Correct 4561 ms 1088800 KB Output is correct
3 Correct 2189 ms 940256 KB Output is correct
4 Correct 2044 ms 867944 KB Output is correct
5 Correct 2707 ms 1143336 KB Output is correct
6 Correct 1578 ms 1044480 KB Output is correct
7 Correct 1570 ms 1043780 KB Output is correct
8 Correct 1540 ms 1047644 KB Output is correct
9 Correct 410 ms 742720 KB Output is correct
10 Correct 1560 ms 981588 KB Output is correct
11 Correct 1511 ms 950896 KB Output is correct
12 Correct 1557 ms 981388 KB Output is correct
13 Correct 1591 ms 1044332 KB Output is correct
14 Correct 1586 ms 1043920 KB Output is correct
15 Correct 1545 ms 1046980 KB Output is correct
16 Correct 423 ms 742724 KB Output is correct
17 Correct 1585 ms 981672 KB Output is correct
18 Correct 1520 ms 951048 KB Output is correct
19 Correct 1557 ms 981652 KB Output is correct
20 Correct 1632 ms 1047268 KB Output is correct
21 Correct 1626 ms 1047016 KB Output is correct
22 Correct 1578 ms 1050756 KB Output is correct
23 Correct 449 ms 744212 KB Output is correct
24 Correct 1636 ms 984356 KB Output is correct
25 Correct 1593 ms 953908 KB Output is correct
26 Correct 1573 ms 983808 KB Output is correct
27 Correct 5696 ms 1280664 KB Output is correct
28 Correct 5665 ms 1281160 KB Output is correct
29 Correct 3560 ms 1240536 KB Output is correct
30 Correct 2727 ms 861404 KB Output is correct
31 Correct 6292 ms 1112292 KB Output is correct
32 Correct 8752 ms 1172688 KB Output is correct
33 Correct 2889 ms 1153792 KB Output is correct