oj.uz

Submission #386893

# Submission time Handle Problem Language Result Execution time Memory
386893 2021-04-07T15:30:41 Z keko37 Bodyguard (JOI21_bodyguard) C++14
47 / 100
 25000 ms 495668 KB 
#include<bits/stdc++.h>

using namespace std;

typedef long long llint;
typedef pair <llint, llint> pi;

const int MAXN = 2805;
const int MAXQ = 3000005;

int n, q;
int cost[MAXN];
pi pa[MAXN], pb[MAXN];
int upp[MAXN*3][MAXN*3], rig[MAXN*3][MAXN*3];
llint dp[MAXN*3][MAXN*3];
llint qx[MAXQ], qy[MAXQ], sol[MAXQ];
vector <llint> vx, vy;
vector <pi> ux[MAXN*3], uy[MAXN*3];
deque <pi> hull;

void precompute () {
    for (int i = 1; i <= n; i++) {
        vx.push_back(pa[i].first); vy.push_back(pa[i].second);
        vx.push_back(pb[i].first); vy.push_back(pb[i].second);
    }
    sort(vx.begin(), vx.end());
    vx.erase(unique(vx.begin(), vx.end()), vx.end());
    sort(vy.begin(), vy.end());
    vy.erase(unique(vy.begin(), vy.end()), vy.end());

    for (int i = 1; i <= n; i++) {
        int ix = lower_bound(vx.begin(), vx.end(), pa[i].first) - vx.begin();
        int iy = lower_bound(vy.begin(), vy.end(), pa[i].second) - vy.begin();
        int jx = lower_bound(vx.begin(), vx.end(), pb[i].first) - vx.begin();
        int jy = lower_bound(vy.begin(), vy.end(), pb[i].second) - vy.begin();
        if (iy == jy) {
            for (int k = ix; k < jx; k++) {
                rig[k][iy] = max(rig[k][iy], cost[i]);
            }
        } else {
            for (int k = iy; k < jy; k++) {
                upp[ix][k] = max(upp[ix][k], cost[i]);
            }
        }
    }

    for (int i = (int)vx.size() - 1; i >= 0; i--) {
        for (int j = (int) vy.size() - 1; j >= 0; j--) {
            llint res = 0;
            if (i + 1 < vx.size()) res = max(res, dp[i + 1][j] + rig[i][j] * (vx[i + 1] - vx[i]));
            if (j + 1 < vy.size()) res = max(res, dp[i][j + 1] + upp[i][j] * (vy[j + 1] - vy[j]));
            dp[i][j] = res;
        }
    }
}

void obradi (int ind) {
    llint x = qx[ind], y = qy[ind];
    int i = lower_bound(vx.begin(), vx.end(), x) - vx.begin();
    int j = lower_bound(vy.begin(), vy.end(), y) - vy.begin();
    sol[ind] = dp[i][j];
    if (i - 1 >= 0 && i < vx.size() && x != vx[i]) ux[i].push_back({y, ind});
    if (j - 1 >= 0 && j < vy.size() && y != vy[j]) uy[j].push_back({x, ind});
}

llint ccw (pi a, pi b, pi c) {
    return a.first * (b.second - c.second) + b.first * (c.second - a.second) + c.first * (a.second - b.second);
}

llint f (pi pt, llint val) {
    return pt.first * val + pt.second;
}

void ubaci (pi pt) {
    //while (hull.size() >= 1 && pt.first >= hull[0].first) hull.pop_front();
    //while (hull.size() >= 2 && ccw(pt, hull[0], hull[1]) <= 0) hull.pop_front();
    hull.push_back(pt);
}

llint upit (llint val) {
    /*if (hull.empty()) return 0;
    int lo = 0, hi = hull.size() - 1;
    while (lo < hi) {
        int mid = (lo + hi) / 2;
        if (f(hull[mid], val) >= f(hull[mid + 1], val)) {
            hi = mid;
        } else {
            lo = mid + 1;
        }
    }
    return f(hull[lo], val);*/
    llint res = 0;
    for (auto pt : hull) res = max(res, f(pt, val));
    return res;
}

void calc_x (int pos) {
    hull.clear();
    int p = (int)vy.size() - 1;
    sort(ux[pos].begin(), ux[pos].end());
    for (int i = (int)ux[pos].size() - 1; i >= 0; i--) {
        int ind = ux[pos][i].second;
        llint val = vx[pos] - qx[ind];
        while (p >= 0 && vy[p] >= qy[ind]) {
            ubaci({rig[pos - 1][p], dp[pos][p]});
            p--;
        }
        sol[ind] = max(sol[ind], upit(val));
    }
}

void calc_y (int pos) {
    hull.clear();
    int p = (int)vx.size() - 1;
    sort(uy[pos].begin(), uy[pos].end());
    for (int i = (int)uy[pos].size() - 1; i >= 0; i--) {
        int ind = uy[pos][i].second;
        llint val = vy[pos] - qy[ind];
        while (p >= 0 && vx[p] >= qx[ind]) {
            ubaci({upp[p][pos - 1], dp[p][pos]});
            p--;
        }
        sol[ind] = max(sol[ind], upit(val));
    }
}

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        int t, a, b;
        cin >> t >> a >> b >> cost[i];
        cost[i] /= 2;

        llint x = t, y = a;
        pa[i] = {x - y, x + y};
        x = t + abs(a - b), y = b;
        pb[i] = {x - y, x + y};

        //cout << "bla " << pa[i].first << " " << pa[i].second << "  " << pb[i].first << " " << pb[i].second << "  " << cost[i] << endl;
    }
    precompute();
    for (int i = 1; i <= q; i++) {
        int x, y;
        cin >> x >> y;
        qx[i] = x - y; qy[i] = x + y;
        obradi(i);
    }
    for (int i = (int)vx.size() - 1; i >= 1; i--) calc_x(i);
    for (int i = (int)vy.size() - 1; i >= 1; i--) calc_y(i);
    for (int i = 1; i <= q; i++) {
        cout << sol[i] << '\n';
    }
    return 0;
}

Compilation message

bodyguard.cpp: In function 'void precompute()':
bodyguard.cpp:50:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |             if (i + 1 < vx.size()) res = max(res, dp[i + 1][j] + rig[i][j] * (vx[i + 1] - vx[i]));
      |                 ~~~~~~^~~~~~~~~~~
bodyguard.cpp:51:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |             if (j + 1 < vy.size()) res = max(res, dp[i][j + 1] + upp[i][j] * (vy[j + 1] - vy[j]));
      |                 ~~~~~~^~~~~~~~~~~
bodyguard.cpp: In function 'void obradi(int)':
bodyguard.cpp:62:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |     if (i - 1 >= 0 && i < vx.size() && x != vx[i]) ux[i].push_back({y, ind});
      |                       ~~^~~~~~~~~~~
bodyguard.cpp:63:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |     if (j - 1 >= 0 && j < vy.size() && y != vy[j]) uy[j].push_back({x, ind});
      |                       ~~^~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 9250 ms 295860 KB Output is correct
2 Correct 9089 ms 323588 KB Output is correct
3 Correct 5545 ms 225208 KB Output is correct
4 Correct 1999 ms 193392 KB Output is correct
5 Correct 1248 ms 348004 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 281 ms 240876 KB Output is correct
2 Correct 277 ms 240492 KB Output is correct
3 Correct 288 ms 239596 KB Output is correct
4 Correct 27 ms 35436 KB Output is correct
5 Correct 295 ms 209644 KB Output is correct
6 Correct 246 ms 194540 KB Output is correct
7 Correct 289 ms 209540 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 281 ms 240876 KB Output is correct
2 Correct 277 ms 240492 KB Output is correct
3 Correct 288 ms 239596 KB Output is correct
4 Correct 27 ms 35436 KB Output is correct
5 Correct 295 ms 209644 KB Output is correct
6 Correct 246 ms 194540 KB Output is correct
7 Correct 289 ms 209540 KB Output is correct
8 Correct 492 ms 241388 KB Output is correct
9 Correct 490 ms 240852 KB Output is correct
10 Correct 340 ms 238828 KB Output is correct
11 Correct 40 ms 35692 KB Output is correct
12 Correct 425 ms 209900 KB Output is correct
13 Correct 369 ms 194796 KB Output is correct
14 Correct 313 ms 209772 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 281 ms 240876 KB Output is correct
2 Correct 277 ms 240492 KB Output is correct
3 Correct 288 ms 239596 KB Output is correct
4 Correct 27 ms 35436 KB Output is correct
5 Correct 295 ms 209644 KB Output is correct
6 Correct 246 ms 194540 KB Output is correct
7 Correct 289 ms 209540 KB Output is correct
8 Correct 492 ms 241388 KB Output is correct
9 Correct 490 ms 240852 KB Output is correct
10 Correct 340 ms 238828 KB Output is correct
11 Correct 40 ms 35692 KB Output is correct
12 Correct 425 ms 209900 KB Output is correct
13 Correct 369 ms 194796 KB Output is correct
14 Correct 313 ms 209772 KB Output is correct
15 Correct 1061 ms 245868 KB Output is correct
16 Correct 1092 ms 245764 KB Output is correct
17 Correct 678 ms 242788 KB Output is correct
18 Correct 66 ms 38120 KB Output is correct
19 Correct 727 ms 213236 KB Output is correct
20 Correct 735 ms 198508 KB Output is correct
21 Correct 302 ms 211728 KB Output is correct

Subtask #5
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 9250 ms 295860 KB Output is correct
2 Correct 9089 ms 323588 KB Output is correct
3 Correct 5545 ms 225208 KB Output is correct
4 Correct 1999 ms 193392 KB Output is correct
5 Correct 1248 ms 348004 KB Output is correct
6 Correct 281 ms 240876 KB Output is correct
7 Correct 277 ms 240492 KB Output is correct
8 Correct 288 ms 239596 KB Output is correct
9 Correct 27 ms 35436 KB Output is correct
10 Correct 295 ms 209644 KB Output is correct
11 Correct 246 ms 194540 KB Output is correct
12 Correct 289 ms 209540 KB Output is correct
13 Correct 492 ms 241388 KB Output is correct
14 Correct 490 ms 240852 KB Output is correct
15 Correct 340 ms 238828 KB Output is correct
16 Correct 40 ms 35692 KB Output is correct
17 Correct 425 ms 209900 KB Output is correct
18 Correct 369 ms 194796 KB Output is correct
19 Correct 313 ms 209772 KB Output is correct
20 Correct 1061 ms 245868 KB Output is correct
21 Correct 1092 ms 245764 KB Output is correct
22 Correct 678 ms 242788 KB Output is correct
23 Correct 66 ms 38120 KB Output is correct
24 Correct 727 ms 213236 KB Output is correct
25 Correct 735 ms 198508 KB Output is correct
26 Correct 302 ms 211728 KB Output is correct
27 Execution timed out 25044 ms 495668 KB Time limit exceeded
28 Halted 0 ms 0 KB -