oj.uz

Submission #402011

# Submission time Handle Problem Language Result Execution time Memory
402011 2021-05-11T07:34:59 Z doowey Bodyguard (JOI21_bodyguard) C++14
7 / 100
 5068 ms 1059536 KB 
#include <bits/stdc++.h>

using namespace std;

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

#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;
    ld lim;
};


ld inter(line p1, line p2){
    return (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();
        ld 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 = -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],-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], -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:101:9: warning: unused variable 'iq' [-Wunused-variable]
  101 |     int iq;
      |         ^~
bodyguard.cpp:128:8: warning: variable 'big' set but not used [-Wunused-but-set-variable]
  128 |     ll big;
      |        ^~~
bodyguard.cpp:129:8: warning: unused variable 'cc' [-Wunused-variable]
  129 |     ll cc;
      |        ^~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 5068 ms 1059536 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 2343 ms 1044332 KB Output is correct
2 Correct 2333 ms 1043560 KB Output is correct
3 Correct 2360 ms 1047492 KB Output is correct
4 Correct 411 ms 742444 KB Output is correct
5 Correct 1891 ms 981564 KB Output is correct
6 Correct 1837 ms 950768 KB Output is correct
7 Correct 1789 ms 981432 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2343 ms 1044332 KB Output is correct
2 Correct 2333 ms 1043560 KB Output is correct
3 Correct 2360 ms 1047492 KB Output is correct
4 Correct 411 ms 742444 KB Output is correct
5 Correct 1891 ms 981564 KB Output is correct
6 Correct 1837 ms 950768 KB Output is correct
7 Correct 1789 ms 981432 KB Output is correct
8 Correct 2363 ms 1044124 KB Output is correct
9 Correct 2318 ms 1043684 KB Output is correct
10 Correct 2334 ms 1046724 KB Output is correct
11 Correct 406 ms 742724 KB Output is correct
12 Correct 1900 ms 981688 KB Output is correct
13 Incorrect 1840 ms 950896 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2343 ms 1044332 KB Output is correct
2 Correct 2333 ms 1043560 KB Output is correct
3 Correct 2360 ms 1047492 KB Output is correct
4 Correct 411 ms 742444 KB Output is correct
5 Correct 1891 ms 981564 KB Output is correct
6 Correct 1837 ms 950768 KB Output is correct
7 Correct 1789 ms 981432 KB Output is correct
8 Correct 2363 ms 1044124 KB Output is correct
9 Correct 2318 ms 1043684 KB Output is correct
10 Correct 2334 ms 1046724 KB Output is correct
11 Correct 406 ms 742724 KB Output is correct
12 Correct 1900 ms 981688 KB Output is correct
13 Incorrect 1840 ms 950896 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #5
0 / 53.0

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