Submission #612423

#	Time	Username	Problem	Language	Result	Execution time	Memory
612423		Loki_Nguyen	Treatment Project (JOI20_treatment)	C++14	100 / 100	377 ms	15060 KiB

treatment

#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push back
#define pii pair<int, int>
#define pll pair<ll, int>
using namespace std;
const int N = 1e6 + 6;
const int mod = 1e9 + 7;
const int inf = 2e9 + 7;
struct node
{
    int t, l, r, v;
    bool operator<(const node &u) const
    {
        return t < u.t;
    }
} d[N];
struct IT
{
    int n;
    vector<pii> st;
    IT(int _n)
    {
        n = _n;
        st.resize(n * 4 + 4, make_pair(inf, 0));
    }
    void build(int id, int l, int r, int pos, pii v)
    {
        if (l == r)
        {
            st[id] = v;
            return;
        }
        int mid = (l + r) >> 1;
        if (pos <= mid)
            build(id << 1, l, mid, pos, v);
        else
            build(id << 1 | 1, mid + 1, r, pos, v);
        st[id] = min(st[id << 1], st[id << 1 | 1]);
    }
    void build(int pos, pii v)
    {
        build(1, 1, n, pos, v);
    }
    pii get(int id, int l, int r, int u, int v)
    {
        if (u <= l && r <= v)
            return st[id];
        if (u > r || l > v)
            return make_pair(inf, 0);
        int mid = (l + r) >> 1;
        return min(get(id << 1, l, mid, u, v), get(id << 1 | 1, mid + 1, r, u, v));
    }
    pii get(int l, int r)
    {
        if (l > r)
            return make_pair(inf, 0);
        return get(1, 1, n, l, r);
    }
};
int n, m, k, t, a[N], b[N], l[N], r[N];
ll ans;
int main()
{
    cin.tie(0);
    cin >> n >> m;
    ans = -1;
    priority_queue<pll, vector<pll>, greater<pll>> pq;
    for (int i = 1; i <= m; i++)
        cin >> d[i].t >> d[i].l >> d[i].r >> d[i].v;
    sort(d + 1, d + 1 + m);
    IT L(m), R(m);
    for (int i = 1; i <= m; i++)
    {
        --d[i].l;
        //cout << d[i].t << " " << d[i].l << " " << d[i].r << " " << d[i].v << '\n';
        if (i > 1 && d[i].t == d[i - 1].t)
            l[i] = l[i - 1];
        else
            l[i] = i;        
        if (d[i].l == 0)
        {
            pq.push({d[i].v, i});
            continue;
        }

        L.build(i, make_pair(d[i].l - d[i].t, i));
        R.build(i, make_pair(d[i].l + d[i].t, i));
    }
    r[m] = m;
    for (int i = m - 1; i > 0; i--)
    {
        if (d[i].t == d[i + 1].t)
            r[i] = r[i + 1];
        else
            r[i] = i;
    }
    while (!pq.empty())
    {
        pll u = pq.top();
        pq.pop();
        //cout << u.se << " " << u.fi << '\n';
        if (d[u.se].r == n)
        {
            if (ans == -1 || ans > u.fi)
                ans = u.fi;
        }
        k = d[u.se].r - d[u.se].t;
        while (true)
        {
            pii v = L.get(1, r[u.se]);
            if (v.fi <= k)
            {
                L.build(v.se, make_pair(inf, 0));
                R.build(v.se, make_pair(inf, 0));
                pq.push({u.fi+d[v.se].v, v.se});
            }
            else
                break;
        }
        k = d[u.se].r + d[u.se].t;
        while (true)
        {
            pii v = R.get(l[u.se], m);
            if (v.fi <= k)
            {
                R.build(v.se, make_pair(inf, 0));
                L.build(v.se, make_pair(inf, 0));
                pq.push({u.fi+d[v.se].v, v.se});
            }
            else
                break;
        }
    }
    cout << ans;
}

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