Submission #770708

#	Time	Username	Problem	Language	Result	Execution time	Memory
770708		PurpleCrayon	Treatment Project (JOI20_treatment)	C++17	100 / 100	307 ms	36412 KiB

treatment

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

#define sz(v) int(v.size())
#define ar array
typedef long long ll;
const int N = 2e5+10, MOD = 998244353;
const ll INF = 1e18+10;

template <class T>
using min_pq = priority_queue<T, vector<T>, greater<T>>;

struct FT {
    vector<int> a;
    vector<vector<pair<int, int>>> bit;

    void upd(int i, pair<int, int> x) {
        for (; i < sz(bit); i |= i+1) {
            bit[i].push_back(x);
        }
    }

    FT() {}
    FT(vector<pair<int, int>> v) {
        for (auto p : v) a.push_back(p.first);
        sort(a.begin(), a.end());
        a.resize(unique(a.begin(), a.end()) - a.begin());

        bit.resize(sz(a));
        for (int i = 0; i < sz(v); i++) {
            int idx = lower_bound(a.begin(), a.end(), v[i].first) - a.begin();
            upd(idx, {v[i].second, i});
        }

        for (auto& v : bit) {
            sort(v.rbegin(), v.rend());
        }
    }



    vector<int> qry(int x, int y) {
        int i = upper_bound(a.begin(), a.end(), x) - a.begin() - 1;
        vector<int> ans;
        for (++i; i > 0; i &= i-1) {
            while (sz(bit[i-1]) && bit[i-1].back().first <= y) {
                ans.push_back(bit[i-1].back().second);
                bit[i-1].pop_back();
            }
        }
        return ans;
    }
};

void solve() {
    int n, m; cin >> n >> m;
    vector<ar<int, 4>> a(m);
    for (auto& [t, l, r, x] : a) cin >> t >> l >> r >> x, --l, --r;

    min_pq<pair<ll, int>> q;
    vector<ll> dist(m, INF);
    for (int i = 0; i < m; i++) {
        auto [t, l, r, x] = a[i];
        if (l == 0) {
            dist[i] = x;
            q.push({dist[i], i});
        }
    }

    vector<pair<int, int>> v1(m), v2(m);
    for (int i = 0; i < m; i++) {
        auto [t, l, r, x] = a[i];
        v1[i] = {t, l - t - 1};
        v2[i] = {-t, t + l - 1};
    }

    FT one(v1), two(v2);
    while (!q.empty()) {
        auto [d_c, c] = q.top(); q.pop();
        if (dist[c] != d_c) continue;

        auto f = [&](int i) {
            auto [t, l, r, x] = a[i];
            if (dist[c] + x < dist[i]) {
                dist[i] = dist[c] + x;
                q.push({dist[i], i});
            }
        };

        for (int x : one.qry(a[c][0], a[c][2] - a[c][0]))
            f(x);

        for (int x : two.qry(-a[c][0], a[c][0] + a[c][2]))
            f(x);
    }

    ll ans = INF;
    for (int i = 0; i < m; i++) {
        auto [t, l, r, x] = a[i];
        if (r == n-1) {
            ans = min(ans, dist[i]);
        }
    }

    if (ans >= INF) {
        cout << -1 << '\n';
        return;
    }
    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int T = 1;
    // cin >> T;
    while (T--) solve();
}

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