Submission #1178396

#	Time	Username	Problem	Language	Result	Execution time	Memory
1178396		12345678	Treatment Project (JOI20_treatment)	C++20	100 / 100	105 ms	10624 KiB

treatment

#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int nx=1e5+5;

ll n, m, vs[nx], res=1e18;
priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> pq;

struct info
{
    ll t, l, r, c;
    info(ll t=0, ll l=0, ll r=0, ll c=0): t(t), l(l), r(r), c(c){}
    bool operator<(const info &o) const {return t<o.t;}
} d[nx];

struct segtree
{
    ll mn[4*nx];
    void update(int l, int r, int i, int idx, ll vl)
    {
        if (idx<l||r<idx) return;
        if (l==r) return mn[i]=vl, void();
        int md=(l+r)/2;
        update(l, md ,2*i, idx, vl);
        update(md+1, r, 2*i+1, idx, vl);
        mn[i]=min(mn[2*i], mn[2*i+1]);
    }
    void query(int l, int r, int i, int ql, int qr, ll vl, ll cw)
    {
        if (qr<l||r<ql||qr<ql||mn[i]>vl) return;
        if (l==r)
        {
            if (!vs[l]) pq.push({cw+d[l].c, l});
            vs[l]=1;
            mn[i]=1e18;
            return;
        }
        int md=(l+r)/2;
        query(l, md, 2*i, ql, qr, vl ,cw);
        query(md+1, r, 2*i+1, ql, qr, vl, cw);
        mn[i]=min(mn[2*i], mn[2*i+1]);
    }
} ls, mr;

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>m;
    for (int i=1; i<=m; i++) cin>>d[i].t>>d[i].l>>d[i].r>>d[i].c;
    sort(d+1, d+m+1);
    for (int i=1; i<=m; i++) ls.update(1, m, 1, i, d[i].l-d[i].t), mr.update(1, m, 1, i, d[i].l+d[i].t);
    for (int i=1; i<=m; i++) if (d[i].l==1) pq.push({d[i].c, i}), vs[i]=1;
    while (!pq.empty())
    {
        auto [cw, i]=pq.top();
        pq.pop();
        //cout<<"debug "<<i<<' '<<d[i].l<<' '<<d[i].r<<' '<<cw<<'\n';
        if (d[i].r==n) res=min(res, cw);
        ls.query(1, m ,1, 1, i-1, d[i].r-d[i].t+1, cw);
        mr.query(1, m, 1, i+1, m, d[i].r+d[i].t+1, cw);
    }
    if (res==1e18) cout<<-1;
    else cout<<res;
}

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