Submission #369302

#	Time	Username	Problem	Language	Result	Execution time	Memory
369302		two_sides	Treatment Project (JOI20_treatment)	C++17	100 / 100	445 ms	53920 KiB

treatment

#include <bits/stdc++.h>

using namespace std;

struct project {
    int t, l, r, c;
};

struct path {
    int x; long long d;

    path(int x, long long d): x(x), d(d) {}

    bool operator < (const path &o) const {
        return d > o.d;
    }
};

const int N = 100005;

vector <int> tr1[N * 4], tr2[N * 4];
project prj[N]; long long dis[N];
priority_queue <path> pq;

bool cmp1(int x, int y) {
    return prj[x].r + prj[x].t >= prj[y].l + prj[y].t;
};

bool cmp2(int x, int y) {
    return prj[x].r - prj[x].t >= prj[y].l - prj[y].t;
};

void build(int i, int l, int r) {
    if (l == r) {
        tr1[i] = tr2[i] = {l}; return;
    }
    int m = (l + r) / 2;
    build(i * 2, l, m); build(i * 2 + 1, m + 1, r);
    merge(tr1[i * 2].begin(), tr1[i * 2].end(),
    tr1[i * 2 + 1].begin(), tr1[i * 2 + 1].end(),
    back_inserter(tr1[i]), [&](int x, int y) {
        return prj[x].l + prj[x].t >= prj[y].l + prj[y].t;
    });
    merge(tr2[i * 2].begin(), tr2[i * 2].end(),
    tr2[i * 2 + 1].begin(), tr2[i * 2 + 1].end(),
    back_inserter(tr2[i]), [&](int x, int y) {
        return prj[x].l - prj[x].t >= prj[y].l - prj[y].t;
    });
}

void trav1(int i, int l, int r, int lim, int x) {
    if (r < lim) return;
    if (l >= lim) {
        while (tr1[i].size()) {
            int y = tr1[i].back();
            if (cmp1(x, y)) {
                if (dis[y] < 0) {
                    dis[y] = dis[x] + prj[y].c;
                    pq.emplace(y, dis[y]);
                }
                tr1[i].pop_back();
            }
            else break;
        }
        return;
    }
    int m = (l + r) / 2;
    trav1(i * 2, l, m, lim, x);
    trav1(i * 2 + 1, m + 1, r, lim, x);
}

void trav2(int i, int l, int r, int lim, int x) {
    if (l > lim) return;
    if (r <= lim) {
        while (tr2[i].size()) {
            int y = tr2[i].back();
            if (cmp2(x, y)) {
                if (dis[y] < 0) {
                    dis[y] = dis[x] + prj[y].c;
                    pq.emplace(y, dis[y]);
                }
                tr2[i].pop_back();
            }
            else break;
        }
        return;
    }
    int m = (l + r) / 2;
    trav2(i * 2, l, m, lim, x);
    trav2(i * 2 + 1, m + 1, r, lim, x);
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int m, n; cin >> m >> n;
    for (int i = 1; i <= n; i++)
        cin >> prj[i].t >> prj[i].l >> prj[i].r >> prj[i].c;
    sort(prj + 1, prj + n + 1, [](project a, project b) {
        return a.t < b.t;
    });
    memset(dis, -1, sizeof dis); build(1, 1, n);
    for (int i = 1; i <= n; i++)
        if (--prj[i].l == 0)
            pq.emplace(i, dis[i] = prj[i].c);
    while (pq.size()) {
        path t = pq.top(); pq.pop();
        if (prj[t.x].r == m) {
            cout << t.d << '\n'; return 0;
        }
        int lim = lower_bound(prj + 1, prj + n + 1, prj[t.x],
        [](project a, project b) {return a.t < b.t;}) - prj;
        trav1(1, 1, n, lim, t.x);
        lim = upper_bound(prj + 1, prj + n + 1, prj[t.x],
        [](project a, project b) {return a.t < b.t;}) - prj;
        trav2(1, 1, n, lim - 1, t.x);
    }
    cout << "-1\n";
}

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