Submission #747151

#	Time	Username	Problem	Language	Result	Execution time	Memory
747151		piOOE	Treatment Project (JOI20_treatment)	C++17	100 / 100	252 ms	53772 KiB

treatment

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

struct Segment {
    int t, l, r, w;
};

constexpr ll inf = 3e18;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    vector<Segment> s(m);
    vector<int> tt;

    for (auto &[t, l, r, w] : s) {
        cin >> t >> l >> r >> w;
        tt.push_back(t);
    }

    sort(tt.begin(), tt.end());
    tt.resize(unique(tt.begin(), tt.end()) - tt.begin());
    const int siz = tt.size();

    vector<int> pnt1(siz + 1), pnt2(siz + 1), pos(m);
    vector<vector<pair<ll, int>>> fn1(siz + 1), fn2(siz + 1);
    vector<pair<ll, int>> val1(m), val2(m);

    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<>> pq;
    vector<ll> dp(m, inf);
    vector<bool> used(m);

    for (int i = 0; i < m; ++i) {
        pos[i] = lower_bound(tt.begin(), tt.end(), s[i].t) - tt.begin();
        val1[i] = {-s[i].l + s[i].t + 1, i};
        val2[i] = {-s[i].l - s[i].t + 1, i};
    }

    sort(val1.rbegin(), val1.rend());
    sort(val2.rbegin(), val2.rend());

    for (auto [v, i] : val1) {
        for (int x = pos[i] + 1; x <= siz; x += x & -x) {
            fn1[x].emplace_back(v, i);
        }
    }

    for (auto [v, i] : val2) {
        for (int x = pos[i] + 1; x > 0; x -= x & -x) {
            fn2[x].emplace_back(v, i);
        }
    }

    auto take = [&](int i, ll val) {
        if (used[i]) {
            return;
        }
        dp[i] = val + s[i].w;
        pq.emplace(dp[i], i);
        used[i] = true;
    };

    for (int i = 0; i < m; ++i) {
        if (s[i].l == 1) {
            take(i, 0);
        }
    }

    while (!pq.empty()) {
        auto [d, i] = pq.top();
        pq.pop();

        ll v1 = s[i].t - s[i].r, v2 = -s[i].r - s[i].t;
        for (int x = pos[i] + 1; x > 0; x -= x & -x) {
            while (pnt1[x] < size(fn1[x]) && fn1[x][pnt1[x]].first >= v1) {
                take(fn1[x][pnt1[x]++].second, d);
            }
        }
        for (int x = pos[i] + 1; x <= siz; x += x & -x) {
            while (pnt2[x] < size(fn2[x]) && fn2[x][pnt2[x]].first >= v2) {
                take(fn2[x][pnt2[x]++].second, d);
            }
        }
    }

    ll ans = inf;

    for (int i = 0; i < m; ++i) {
        if (s[i].r == n) {
            ans = min(ans, dp[i]);
        }
    }

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

    return 0;
}

Compilation message (stderr)

treatment.cpp: In function 'int main()':
treatment.cpp:81:28: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |             while (pnt1[x] < size(fn1[x]) && fn1[x][pnt1[x]].first >= v1) {
treatment.cpp:86:28: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |             while (pnt2[x] < size(fn2[x]) && fn2[x][pnt2[x]].first >= v2) {

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