oj.uz

Submission #595805

# Submission time Handle Problem Language Result Execution time Memory
595805 2022-07-14T07:09:40 Z 반딧불(#8442) Bodyguard (JOI21_bodyguard) C++17
100 / 100
 4203 ms 628888 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const ll INF = 3e9;

int n, q, W, H;
ll sx[3002], sy[3002], ex[3002], ey[3002], w[3002];
ll qx[3000002], qy[3000002];
ll qcx[3000002], qcy[3000002];
ll wx[6004][6004], wy[6004][6004]; /// x�� �ٲ� / y�� �ٲ�
ll dist[6004][6004];
vector<ll> xVec, yVec;

ll ans[3000002];

void input();
void operate();
void output();

int main(){
    input();
    operate();
    output();
}

void input(){
    scanf("%d %d", &n, &q);
    for(int i=1; i<=n; i++){
        ll pt, pa, pb, pc, pl;
        scanf("%lld %lld %lld %lld", &pt, &pa, &pb, &pc);
        pt*=2, pa*=2, pb*=2, pc/=2;
        pl = pt+abs(pa-pb);
        sx[i] = (pt+pa)/2, sy[i] = (pt-pa)/2;
        ex[i] = (pl+pb)/2, ey[i] = (pl-pb)/2;
        w[i] = pc;
    }
    for(int i=1; i<=q; i++){
        ll pt, px;
        scanf("%lld %lld", &pt, &px);
        pt*=2, px*=2;
        qx[i] = (pt+px)/2, qy[i] = (pt-px)/2;
    }
}

void renumber(){
    xVec = yVec = vector<ll> (1, LLONG_MIN);
    for(int i=1; i<=n; i++){
        xVec.push_back(sx[i]), xVec.push_back(ex[i]);
        yVec.push_back(sy[i]), yVec.push_back(ey[i]);
    }
    sort(xVec.begin(), xVec.end()); xVec.erase(unique(xVec.begin(), xVec.end()), xVec.end());
    sort(yVec.begin(), yVec.end()); yVec.erase(unique(yVec.begin(), yVec.end()), yVec.end());
    for(int i=1; i<=n; i++){
        sx[i] = lower_bound(xVec.begin(), xVec.end(), sx[i]) - xVec.begin();
        sy[i] = lower_bound(yVec.begin(), yVec.end(), sy[i]) - yVec.begin();
        ex[i] = lower_bound(xVec.begin(), xVec.end(), ex[i]) - xVec.begin();
        ey[i] = lower_bound(yVec.begin(), yVec.end(), ey[i]) - yVec.begin();
//        printf("arr[i]: %lld %lld %lld %lld %lld\n", sx[i], sy[i], ex[i], ey[i], w[i]);
    }
    W = (int)xVec.size(), H = (int)yVec.size();
}

void makeEdges(){
    for(int i=1; i<=n; i++){
        if(sx[i] == ex[i]){
            for(int y=sy[i]+1; y<=ey[i]; y++)
                wy[sx[i]][y] = max(wy[sx[i]][y], w[i] * (yVec[y] - yVec[y-1]));
        }
        else{
            for(int x=sx[i]+1; x<=ex[i]; x++)
                wx[x][sy[i]] = max(wx[x][sy[i]], w[i] * (xVec[x] - xVec[x-1]));
        }
    }
}

void findDist(){
    for(int x=W; x>0; x--){
        for(int y=H; y>0; y--){
//            printf("Dist %d %d: %lld\n", x, y, dist[x][y]);
            dist[x-1][y] = max(dist[x-1][y], dist[x][y] + wx[x][y]);
            dist[x][y-1] = max(dist[x][y-1], dist[x][y] + wy[x][y]);
        }
    }
    for(int i=1; i<=q; i++){
        qcx[i] = lower_bound(xVec.begin(), xVec.end(), qx[i]) - xVec.begin();
        qcy[i] = lower_bound(yVec.begin(), yVec.end(), qy[i]) - yVec.begin();
        ans[i] = dist[qcx[i]][qcy[i]];
    }
}

struct Line{
    ll a, b;
    Line(){}
    Line(ll a, ll b): a(a), b(b){}

    ll get(ll x){
        return a*x+b;
    }
};

struct Node{
    Node *lc, *rc;
    ll s, e;
    Line d = Line(0, -INF);

    Node(){
        s = e = 0, lc = rc = nullptr;
    }
    Node(ll s, ll e): s(s), e(e){
        lc = rc = nullptr;
    }
    ~Node(){
        if(lc) delete lc;
        if(rc) delete rc;
    }

    void addLine(Line x){
        ll m = (s+e+INF+INF)/2-INF;
        if(d.get(m) < x.get(m)) swap(x, d);
        if(d.get(s) >= x.get(s) && d.get(e) >= x.get(e)) return;
        if(d.get(s) < x.get(s)){
            if(!lc) lc = new Node(s, m);
            lc->addLine(x);
        }
        else{
            if(!rc) rc = new Node(m+1, e);
            rc->addLine(x);
        }
    }

    ll query(ll x){
        ll m = (s+e+INF+INF)/2-INF;
        ll ret = d.get(x);
        if(x<=m && lc) ret = max(ret, lc->query(x));
        if(m<x && rc) ret = max(ret, rc->query(x));
        return ret;
    }
};

struct LiChao{
    Node* root;

    void init(){
        if(root) delete root;
        root = new Node(-INF, INF);
    }

    void addLine(Line x){
        root->addLine(x);
    }

    ll query(ll x){
        return root->query(x);
    }
} tree;

vector<ll> xqVec[6002];

void findAnsX(){ /// x�� �������δ� ������ �ְ�, y�� �������� ���� ���� ���� �� ���ϱ�
    for(int i=0; i<=W; i++) xqVec[i].clear();
    for(int i=1; i<=q; i++) xqVec[qcx[i]].push_back(i);
    for(int x=1; x<=W; x++){ /// [x-1, x] ������ �����ؾ� ��
        vector<pair<ll, int> > vec; /// ��: ���, ��: ����
        for(int i=1; i<=n; i++){
            if(x <= sx[i] || ex[i] <= x-1) continue;
            vec.push_back(make_pair(yVec[sy[i]], i));
        }
        for(auto key: xqVec[x]) vec.push_back(make_pair(qy[key], -key));
        sort(vec.rbegin(), vec.rend());
        tree.init();
        for(pair<ll, int> p: vec){
            if(p.second > 0){ /// �� �߰�
                int px = p.second;
                ll pa = -w[px], pb = dist[x][sy[px]] - pa * xVec[x];
                tree.addLine(Line(pa, pb));
            }
            else{ /// �� ����
                int px = -p.second;
                ans[px] = max(ans[px], tree.query(qx[px]));
            }
        }
    }
}

void flipAxis(){
    swap(H, W);
    swap(xVec, yVec);
    for(int i=1; i<=n; i++) swap(sx[i], sy[i]), swap(ex[i], ey[i]);
    for(int i=1; i<=q; i++) swap(qx[i], qy[i]), swap(qcx[i], qcy[i]);
    for(int i=0; i<=H || i<=W; i++) for(int j=i+1; j<=H || j<=W; j++) swap(dist[i][j], dist[j][i]);
}

void operate(){
    renumber();
    makeEdges();
    findDist();
    findAnsX();
    flipAxis();
    findAnsX();
}

void output(){
    for(int i=1; i<=q; i++){
        printf("%lld\n", ans[i]);
    }
}

Compilation message

bodyguard.cpp: In function 'void input()':
bodyguard.cpp:29:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |     scanf("%d %d", &n, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~
bodyguard.cpp:32:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |         scanf("%lld %lld %lld %lld", &pt, &pa, &pb, &pc);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bodyguard.cpp:41:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |         scanf("%lld %lld", &pt, &px);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3673 ms 360116 KB Output is correct
2 Correct 4099 ms 361484 KB Output is correct
3 Correct 2779 ms 293236 KB Output is correct
4 Correct 2163 ms 272548 KB Output is correct
5 Correct 3774 ms 447368 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 832 ms 303820 KB Output is correct
2 Correct 870 ms 302148 KB Output is correct
3 Correct 841 ms 344912 KB Output is correct
4 Correct 95 ms 73368 KB Output is correct
5 Correct 1258 ms 240384 KB Output is correct
6 Correct 817 ms 209628 KB Output is correct
7 Correct 874 ms 239844 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 832 ms 303820 KB Output is correct
2 Correct 870 ms 302148 KB Output is correct
3 Correct 841 ms 344912 KB Output is correct
4 Correct 95 ms 73368 KB Output is correct
5 Correct 1258 ms 240384 KB Output is correct
6 Correct 817 ms 209628 KB Output is correct
7 Correct 874 ms 239844 KB Output is correct
8 Correct 851 ms 303468 KB Output is correct
9 Correct 828 ms 304720 KB Output is correct
10 Correct 955 ms 347100 KB Output is correct
11 Correct 99 ms 73616 KB Output is correct
12 Correct 1362 ms 240584 KB Output is correct
13 Correct 894 ms 209784 KB Output is correct
14 Correct 1750 ms 240464 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 832 ms 303820 KB Output is correct
2 Correct 870 ms 302148 KB Output is correct
3 Correct 841 ms 344912 KB Output is correct
4 Correct 95 ms 73368 KB Output is correct
5 Correct 1258 ms 240384 KB Output is correct
6 Correct 817 ms 209628 KB Output is correct
7 Correct 874 ms 239844 KB Output is correct
8 Correct 851 ms 303468 KB Output is correct
9 Correct 828 ms 304720 KB Output is correct
10 Correct 955 ms 347100 KB Output is correct
11 Correct 99 ms 73616 KB Output is correct
12 Correct 1362 ms 240584 KB Output is correct
13 Correct 894 ms 209784 KB Output is correct
14 Correct 1750 ms 240464 KB Output is correct
15 Correct 909 ms 306756 KB Output is correct
16 Correct 920 ms 307060 KB Output is correct
17 Correct 876 ms 346620 KB Output is correct
18 Correct 124 ms 76384 KB Output is correct
19 Correct 1379 ms 243780 KB Output is correct
20 Correct 837 ms 212304 KB Output is correct
21 Correct 1611 ms 243696 KB Output is correct

Subtask #5
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 3673 ms 360116 KB Output is correct
2 Correct 4099 ms 361484 KB Output is correct
3 Correct 2779 ms 293236 KB Output is correct
4 Correct 2163 ms 272548 KB Output is correct
5 Correct 3774 ms 447368 KB Output is correct
6 Correct 832 ms 303820 KB Output is correct
7 Correct 870 ms 302148 KB Output is correct
8 Correct 841 ms 344912 KB Output is correct
9 Correct 95 ms 73368 KB Output is correct
10 Correct 1258 ms 240384 KB Output is correct
11 Correct 817 ms 209628 KB Output is correct
12 Correct 874 ms 239844 KB Output is correct
13 Correct 851 ms 303468 KB Output is correct
14 Correct 828 ms 304720 KB Output is correct
15 Correct 955 ms 347100 KB Output is correct
16 Correct 99 ms 73616 KB Output is correct
17 Correct 1362 ms 240584 KB Output is correct
18 Correct 894 ms 209784 KB Output is correct
19 Correct 1750 ms 240464 KB Output is correct
20 Correct 909 ms 306756 KB Output is correct
21 Correct 920 ms 307060 KB Output is correct
22 Correct 876 ms 346620 KB Output is correct
23 Correct 124 ms 76384 KB Output is correct
24 Correct 1379 ms 243780 KB Output is correct
25 Correct 837 ms 212304 KB Output is correct
26 Correct 1611 ms 243696 KB Output is correct
27 Correct 3799 ms 585636 KB Output is correct
28 Correct 3878 ms 585916 KB Output is correct
29 Correct 3651 ms 628888 KB Output is correct
30 Correct 2086 ms 353644 KB Output is correct
31 Correct 3037 ms 418600 KB Output is correct
32 Correct 4203 ms 453696 KB Output is correct
33 Correct 3721 ms 484276 KB Output is correct