oj.uz

Submission #516124

# Submission time Handle Problem Language Result Execution time Memory
516124 2022-01-20T12:04:29 Z Jeff12345121 Pinball (JOI14_pinball) C++14
100 / 100
 980 ms 53228 KB 
#include <bits/stdc++.h>
#define ll long long
#define int long long
using namespace std;

#ifdef EVAL
#define in cin
#define out cout
#else
ifstream in("in.in");
ofstream out("out.out");
#endif

int n, m;
const ll inf = (1LL << 60);
struct Dev {
    int l, r, hole, cost;
};
vector<Dev> dev;

struct SegTree {
    vector<int> v;
    int N;
    SegTree(int l, int r) : N(r + 1), v(5 * r + 1, inf) {}
    SegTree() {}

   private:
    void update(int ind, int l, int r, int qpos, int newVal) {
        if (qpos == l && qpos == r) {
            v[ind] = min(v[ind], newVal);
            return;
        }

        int mij = (l + r) / 2;
        if (qpos <= mij) {
            update(2 * ind, l, mij, qpos, newVal);
        } else {
            update(2 * ind + 1, mij + 1, r, qpos, newVal);
        }
        v[ind] = min(v[2 * ind], v[2 * ind + 1]);
    }

    int query(int ind, int l, int r, int ql, int qr) {
        if (ql <= l && r <= qr) {
            return v[ind];
        }

        int mij = (l + r) / 2, opt1 = inf, opt2 = inf;
        if (ql <= mij) {
            opt1 = query(2 * ind, l, mij, ql, qr);
        }
        if (qr >= mij + 1) {
            opt2 = query(2 * ind + 1, mij + 1, r, ql, qr);
        }
        return min(opt1, opt2);
    }

   public:
    void update(int pos, int newVal) {
        update(1, 1, N, pos, newVal);
    }
    int query(int l, int r) {
        return query(1, 1, N, l, r);
    }
};

SegTree segTreeLeft, segTreeRight;

template <typename F>
void getDp(vector<ll> &dp, F f) {
    /// we want to have all the pinballs take it past left
    // dp[i] = minCost to get all balls to this device
    segTreeLeft = SegTree(1, n);
    dp.resize(m + 1);
    for (int i = 1; i <= m; i++) {
        dp[i] = inf;
    }
    ll ans = inf;
    for (int i = 1; i <= m; i++) {
        if (f(dev[i])) {
            dp[i] = dev[i].cost;
        }
        dp[i] = min(dp[i], dev[i].cost + segTreeLeft.query(dev[i].l, dev[i].r));
        segTreeLeft.update(dev[i].hole, dp[i]);
    }
}
set<int> values;
map<int, int> valToNorm;
int32_t main() {
    in >> m >> n;
    /// m is number of lines, n is number of collumns

    vector<pair<int, int>> sortDev;
    sortDev.resize(m + 1);
    dev.resize(m + 1);
    for (int i = 1; i <= m; i++) {
        int l, r, hole, cost;
        in >> l >> r >> hole >> cost;
        values.insert(l);
        values.insert(r);
        values.insert(hole);
        dev[i] = {l, r, hole, cost};

        sortDev[i] = {l, r};
    }

    sort(sortDev.begin(), sortDev.end());

    {
        int r = 1;
        for (int i = 1; i <= m; i++) {
            if (sortDev[i].first > r) {
                out << "-1\n";
                return 0;
            }
            r = max(r, sortDev[i].second);
        }

        if (r < n) {
            out << "-1\n";
            return 0;
        }
    }

    sortDev.clear();

    int nr = 0;
    for (auto k : values) {
        valToNorm[k] = ++nr;
    }

    for (int i = 1; i <= m; i++) {
        dev[i].l = valToNorm[dev[i].l];
        dev[i].r = valToNorm[dev[i].r];
        dev[i].hole = valToNorm[dev[i].hole];
    }

    valToNorm.clear();
    values.clear();

    n = nr;

    vector<ll> leftDp, rightDp;
    getDp(leftDp, [&](Dev x) {
        return x.l == 1;
    });

    getDp(rightDp, [&](Dev x) {
        return x.r == n;
    });

    segTreeLeft = SegTree(1, n);
    segTreeRight = SegTree(1, n);
    ll ans = inf;
    for (int i = 1; i <= m; i++) {
        /// i is middle
        ll leftCost = inf, rightCost = inf;
        if (dev[i].l > 1) {
            leftCost = segTreeLeft.query(dev[i].l, dev[i].r);
        } else {
            leftCost = 0;
        }

        if (dev[i].r < n) {
            rightCost = segTreeRight.query(dev[i].l, dev[i].r);
        } else {
            rightCost = 0;
        }

        segTreeLeft.update(dev[i].hole, leftDp[i]);
        segTreeRight.update(dev[i].hole, rightDp[i]);

        ans = min(ans, leftCost + rightCost + dev[i].cost);
        // cout << "\n";
    }

    if (ans == inf) {
        out << "-1\n";
    } else {
        out << ans << "\n";
    }
}

Compilation message

pinball.cpp: In constructor 'SegTree::SegTree(long long int, long long int)':
pinball.cpp:23:9: warning: 'SegTree::N' will be initialized after [-Wreorder]
   23 |     int N;
      |         ^
pinball.cpp:22:17: warning:   'std::vector<long long int> SegTree::v' [-Wreorder]
   22 |     vector<int> v;
      |                 ^
pinball.cpp:24:5: warning:   when initialized here [-Wreorder]
   24 |     SegTree(int l, int r) : N(r + 1), v(5 * r + 1, inf) {}
      |     ^~~~~~~
pinball.cpp: In instantiation of 'void getDp(std::vector<long long int>&, F) [with F = main()::<lambda(Dev)>]':
pinball.cpp:146:6:   required from here
pinball.cpp:78:8: warning: unused variable 'ans' [-Wunused-variable]
   78 |     ll ans = inf;
      |        ^~~
pinball.cpp: In instantiation of 'void getDp(std::vector<long long int>&, F) [with F = main()::<lambda(Dev)>]':
pinball.cpp:150:6:   required from here
pinball.cpp:78:8: warning: unused variable 'ans' [-Wunused-variable]

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 332 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 1 ms 292 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 5 ms 460 KB Output is correct
18 Correct 3 ms 356 KB Output is correct
19 Correct 3 ms 460 KB Output is correct
20 Correct 4 ms 424 KB Output is correct
21 Correct 2 ms 460 KB Output is correct
22 Correct 4 ms 672 KB Output is correct
23 Correct 3 ms 588 KB Output is correct
24 Correct 4 ms 716 KB Output is correct

Subtask #4
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 1 ms 292 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 5 ms 460 KB Output is correct
18 Correct 3 ms 356 KB Output is correct
19 Correct 3 ms 460 KB Output is correct
20 Correct 4 ms 424 KB Output is correct
21 Correct 2 ms 460 KB Output is correct
22 Correct 4 ms 672 KB Output is correct
23 Correct 3 ms 588 KB Output is correct
24 Correct 4 ms 716 KB Output is correct
25 Correct 42 ms 3480 KB Output is correct
26 Correct 131 ms 10632 KB Output is correct
27 Correct 392 ms 20920 KB Output is correct
28 Correct 320 ms 10220 KB Output is correct
29 Correct 278 ms 17900 KB Output is correct
30 Correct 381 ms 12908 KB Output is correct
31 Correct 706 ms 33372 KB Output is correct
32 Correct 557 ms 26544 KB Output is correct
33 Correct 82 ms 8200 KB Output is correct
34 Correct 319 ms 26644 KB Output is correct
35 Correct 486 ms 41412 KB Output is correct
36 Correct 980 ms 53120 KB Output is correct
37 Correct 726 ms 53132 KB Output is correct
38 Correct 654 ms 53228 KB Output is correct