oj.uz

Submission #402010

# Submission time Handle Problem Language Result Execution time Memory
402010 2021-05-11T07:31:41 Z doowey Bodyguard (JOI21_bodyguard) C++14
7 / 100
 4954 ms 1059596 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();
        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:104:9: warning: unused variable 'iq' [-Wunused-variable]
  104 |     int iq;
      |         ^~
bodyguard.cpp:131:8: warning: variable 'big' set but not used [-Wunused-but-set-variable]
  131 |     ll big;
      |        ^~~
bodyguard.cpp:132:8: warning: unused variable 'cc' [-Wunused-variable]
  132 |     ll cc;
      |        ^~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 4954 ms 1059596 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2358 ms 1044444 KB Output is correct
2 Correct 2342 ms 1043668 KB Output is correct
3 Correct 2303 ms 1047492 KB Output is correct
4 Correct 410 ms 742472 KB Output is correct
5 Correct 1762 ms 981520 KB Output is correct
6 Correct 1711 ms 950848 KB Output is correct
7 Correct 1724 ms 981388 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2358 ms 1044444 KB Output is correct
2 Correct 2342 ms 1043668 KB Output is correct
3 Correct 2303 ms 1047492 KB Output is correct
4 Correct 410 ms 742472 KB Output is correct
5 Correct 1762 ms 981520 KB Output is correct
6 Correct 1711 ms 950848 KB Output is correct
7 Correct 1724 ms 981388 KB Output is correct
8 Correct 2356 ms 1044292 KB Output is correct
9 Correct 2338 ms 1043972 KB Output is correct
10 Correct 2293 ms 1046872 KB Output is correct
11 Correct 413 ms 742596 KB Output is correct
12 Correct 1778 ms 981560 KB Output is correct
13 Incorrect 1729 ms 950936 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2358 ms 1044444 KB Output is correct
2 Correct 2342 ms 1043668 KB Output is correct
3 Correct 2303 ms 1047492 KB Output is correct
4 Correct 410 ms 742472 KB Output is correct
5 Correct 1762 ms 981520 KB Output is correct
6 Correct 1711 ms 950848 KB Output is correct
7 Correct 1724 ms 981388 KB Output is correct
8 Correct 2356 ms 1044292 KB Output is correct
9 Correct 2338 ms 1043972 KB Output is correct
10 Correct 2293 ms 1046872 KB Output is correct
11 Correct 413 ms 742596 KB Output is correct
12 Correct 1778 ms 981560 KB Output is correct
13 Incorrect 1729 ms 950936 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #5
0 / 53.0

# Verdict Execution time Memory Grader output
1 Incorrect 4954 ms 1059596 KB Output isn't correct
2 Halted 0 ms 0 KB -