Submission #583016

#	Time	Username	Problem	Language	Result	Execution time	Memory
583016		elkernos	Treatment Project (JOI20_treatment)	C++17	0 / 100	105 ms	11532 KiB

treatment

#include <bits/stdc++.h>

using namespace std;

const int oo = 1e9;

struct Tree {
    typedef pair<int, int> T;
    static constexpr T unit = {-oo, -oo};
    T f(T a, T b) { return max(a, b); }
    vector<T> s;
    int n;
    Tree(int nn) : s(2 * nn, unit), n(nn) {}
    void update(int pos, T val)
    {
        for(s[pos += n] = val; pos /= 2;) {
            s[pos] = f(s[pos * 2], s[pos * 2 + 1]);
        }
    }
    T query(int b, int e)
    {
        T ra = unit, rb = unit;
        for(b += n, e += n + 1; b < e; b /= 2, e /= 2) {
            if(b % 2) ra = f(ra, s[b++]);
            if(e % 2) rb = f(s[--e], rb);
        }
        return f(ra, rb);
    }
};

struct treatment {
    int t, l, r, c;
    pair<int, int> pocz, kon;
    void read()
    {
        cin >> t >> l >> r >> c;
        r++;
        pocz.first = l + t;
        pocz.second = t - l;
        kon.first = r + t;
        kon.second = t - r;
    }
    bool operator<(const treatment &he) const
    {
        return pocz.first < he.pocz.first;
    }
};

int main()
{
    cin.tie(nullptr)->sync_with_stdio(0);
    int n, m;
    cin >> n >> m;
    vector<treatment> they(m + 1);
    for(int i = 1; i <= m; i++) {
        they[i].read();
    }
    sort(they.begin() + 1, they.end());
    Tree tree(m + 1);
#define T pair<long long, int>
    priority_queue<T, vector<T>, greater<T>> q;
    const long long ool = 1e18 + 5;
    vector<long long> d(m + 1);
    for(int i = 1; i <= m; i++) {
        if(they[i].l == 1) {
            d[i] = they[i].c;
            q.push({d[i], i});
        }
        else {
            d[i] = ool;
            tree.update(i, {they[i].pocz.second, i});
        }
    }
    while(!q.empty()) {
        pair<long long, int> t = q.top();
        q.pop();
        while(true) {
            int lo = 1, hi = m, ans = 0;
            while(lo <= hi) {
                int mid = (lo + hi) / 2;
                if(they[t.second].kon.first < they[mid].pocz.first) {
                    hi = mid - 1;
                }
                else {
                    lo = mid + 1;
                    ans = mid;
                }
            }
            pair<int, int> maybe = tree.query(1, ans);
            if(maybe.first < they[t.second].kon.second) {
                break;
            }
            assert(d[maybe.second] > they[maybe.second].c + t.first);
            q.emplace(d[maybe.second] = they[maybe.second].c + t.first, maybe.second);
            tree.update(maybe.second, {-oo, -oo});
        }
    }
    long long ans = ool;
    for(int i = 1; i <= m; i++) {
        if(they[i].r == n + 1) {
            ans = min(ans, d[i]);
        }
    }
    cout << (ans == ool ? -1 : ans) << '\n';
}

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