Submission #915620

#	Time	Username	Problem	Language	Result	Execution time	Memory
915620		vjudge1	Treatment Project (JOI20_treatment)	C++17	100 / 100	316 ms	71756 KiB

treatment

// https://oj.uz/problem/view/JOI20_treatment

#include <bits/stdc++.h>
using namespace std;

namespace std {

template <int D, typename T>
struct Vec : public vector<Vec<D - 1, T>> {
        static_assert(D >= 1, "Dimension must be positive");
        template <typename... Args>
        Vec(int n = 0, Args... args) : vector<Vec<D - 1, T>>(n, Vec<D - 1, T>(args...)) {}
};

template <typename T>
struct Vec<1, T> : public vector<T> {
        Vec(int n = 0, T val = T()) : std::vector<T>(n, val) {}
};

/* Example
    Vec<4, int64_t> f(n, k, 2, 2); // = f[n][k][2][2];
    Vec<2, int> adj(n); // graph
*/

template <class Fun>
class y_combinator_result {
        Fun fun_;

       public:
        template <class T>
        explicit y_combinator_result(T &&fun) : fun_(std::forward<T>(fun)) {}

        template <class... Args>
        decltype(auto) operator()(Args &&...args) {
                return fun_(std::ref(*this), std::forward<Args>(args)...);
        }
};

template <class Fun>
decltype(auto) y_combinator(Fun &&fun) {
        return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun));
}

/* Example
    auto fun = y_combinator([&](auto self, int x) -> void {
        self(x + 1);
    });
*/

}  // namespace std

vector<int> c;
vector<int64_t> d;
priority_queue<pair<int64_t, int>> pq;

struct segment_tree {
        int n;
        vector<vector<pair<int, int>>> val;
        vector<int> done;
        segment_tree(int n, const vector<pair<int, int>> &a) : n(n), val(n * 4), done(n, 0) {
                build(1, 0, n - 1, a);
                rev(1, 0, n - 1);
        }

        void build(int v, int l, int r, const vector<pair<int, int>> &a) {
                if (l == r) {
                        val[v] = {a[l]};
                        return;
                }
                int mid = (l + r) / 2;
                build(v * 2, l, mid, a);
                build(v * 2 + 1, mid + 1, r, a);
                merge(val[v * 2].begin(), val[v * 2].end(), val[v * 2 + 1].begin(), val[v * 2 + 1].end(),
                      back_inserter(val[v]));
        }

        void rev(int v, int l, int r) {
                reverse(val[v].begin(), val[v].end());
                if (l == r) return;
                int mid = (l + r) / 2;
                rev(v * 2, l, mid);
                rev(v * 2 + 1, mid + 1, r);
        }

        void update(int l, int r, int x, int64_t du) {
                update(1, 0, n - 1, l, r, x, du);
        }

        void update(int v, int l, int r, int s, int t, int x, int64_t du) {
                if (l > t || r < s) return;
                if (s <= l && r <= t) {
                        while (val[v].size() && val[v].back().first <= x) {
                                auto [value, index] = val[v].back();
                                val[v].pop_back();
                                if (done[index]) continue;
                                done[index] = 1;
                                if (d[index] > du + c[index]) {
                                        d[index] = du + c[index];
                                        pq.emplace(-d[index], index);
                                }
                        }
                        return;
                }
                int mid = (l + r) / 2;
                update(v * 2, l, mid, s, t, x, du);
                update(v * 2 + 1, mid + 1, r, s, t, x, du);
        }
};

int32_t main() {
        ios_base::sync_with_stdio(0);
        cin.tie(0);

        int n, m;
        cin >> n >> m;
        vector<int> l(m), r(m), t(m);
        c.resize(m);
        for (int i = 0; i < m; i++) cin >> t[i] >> l[i] >> r[i] >> c[i];
        for (int i = 0; i < m; i++) l[i]--;
        d.assign(m, 1e18);
        for (int i = 0; i < m; i++) {
                if (l[i] == 0) {
                        d[i] = c[i];
                        pq.emplace(-d[i], i);
                }
        }

        vector<pair<int, int>> tmp(m);

        for (int i = 0; i < m; i++) tmp[i] = make_pair(l[i] + t[i], i);
        sort(tmp.begin(), tmp.end(), [&](auto a, auto b) { return t[a.second] < t[b.second]; });
        segment_tree seg_less(m, tmp);

        for (int i = 0; i < m; i++) tmp[i] = make_pair(l[i] - t[i], i);
        sort(tmp.begin(), tmp.end(), [&](auto a, auto b) { return t[a.second] < t[b.second]; });
        segment_tree seg_greater(m, tmp);

        vector<int> ord(m);
        iota(ord.begin(), ord.end(), 0);
        sort(ord.begin(), ord.end(), [&](auto a, auto b) { return t[a] < t[b]; });
        vector<int> p(m);
        for (int i = 0; i < m; i++) p[ord[i]] = i;

        // if t[j] >= t[i] : l[j] <= r[i] - (t[j] - t[i])
        // l[j] + t[j] <= r[i] + t[i]
        // if t[j] <= t[i] : l[j] <= r[i] - (t[i] - t[j])
        // l[j] - t[j] <= r[i] - t[i]

        while (pq.size()) {
                auto [du, j] = pq.top();
                pq.pop();
                du = -du;
                if (du != d[j]) continue;
                if (r[j] == n) {
                        cout << du;
                        return 0;
                }
                seg_less.update(p[j], m - 1, r[j] + t[j], du);
                seg_greater.update(0, p[j], r[j] - t[j], du);
        }
        cout << -1;
}

• Subtask 1: 4 / 4
• Subtask 2: 5 / 5
• Subtask 3: 30 / 30
• Subtask 4: 61 / 61