Submission #876297

#	Time	Username	Problem	Language	Result	Execution time	Memory
876297		vjudge1	Treatment Project (JOI20_treatment)	C++17	100 / 100	161 ms	45892 KiB

treatment

#include<bits/stdc++.h>
#define pb push_back
#define pli pair<ll,ll>
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
using namespace std;
using ll=long long;
const ll maxn=2e5;
const ll inf=1e18;
const ll mod=1e9+7;
ll n,m,t[maxn],l[maxn],r[maxn],c[maxn],d[maxn];
priority_queue<pli,vector<pli>,greater<pli>>pq;
struct node
{
    ll fi,se;
    node ()
    {
        fi=inf,se=0;
    }
    node operator+(const node&o)
    {
        node ans;
        if(fi<o.fi) ans.se=se;
        else ans.se=o.se;
        ans.fi=min(fi,o.fi);
        return ans;
    }
};
struct segtree
{
    node st[4*maxn];
    void update(ll pos,ll v,ll id=1,ll l=1,ll r=m)
    {
        if(l==r)
        {
            st[id].fi=v;
            st[id].se=l;
            return;
        }
        ll mid=l+r>>1;
        if(pos<=mid) update(pos,v,id*2,l,mid);
        else update(pos,v,id*2+1,mid+1,r);
        st[id]=st[id*2]+st[id*2+1];
    }
    node get(ll i,ll j,ll id=1,ll l=1,ll r=m)
    {
        if(j<l||r<i) return node();
        if(i<=l&&r<=j) return st[id];
        ll mid=l+r>>1;
        return get(i,j,id*2,l,mid)+get(i,j,id*2+1,mid+1,r);
    }
}seg[2];
pli b[maxn];
ll pos[maxn],vv[maxn];
void solve()
{
    cin >> n >> m;
    for(int i=1;i<=m;i++)
    {
        cin >> t[i] >> l[i] >> r[i] >> c[i];
        b[i]={t[i],i};
    }
    sort(b+1,b+m+1);
    for(int i=1;i<=m;i++)
    {
        ll id=b[i].se;
        seg[0].update(i,l[id]+t[id]);
        seg[1].update(i,l[id]-t[id]);
        pos[id]=i;
        vv[i]=id;
    }
    for(int i=1;i<=m;i++)
    {
        d[i]=inf;
        if(l[i]==1)
        {
            d[i]=c[i];
            pq.push({d[i],i});
            seg[0].update(pos[i],inf);
            seg[1].update(pos[i],inf);
        }
    }
    while(!pq.empty())
    {
        ll u=pq.top().se;
        ll W=pq.top().fi;
        //cout<<u<<":\n";
        pq.pop();
        if(W>d[u]) continue;
        if(r[u]==n) {cout << W;return;}
        while(seg[0].get(pos[u]+1,m).fi<=r[u]+t[u]+1)
        {
            ll v=vv[seg[0].get(pos[u]+1,m).se];
            d[v]=d[u]+c[v];
            pq.push({d[v],v});
            seg[0].update(pos[v],inf);
            seg[1].update(pos[v],inf);
            //cout <<"phai "<< v << '\n';
        }
        while(seg[1].get(1,pos[u]-1).fi<=r[u]-t[u]+1)
        {
            ll v=vv[seg[1].get(1,pos[u]-1).se];
            d[v]=d[u]+c[v];
            pq.push({d[v],v});
            seg[0].update(pos[v],inf);
            seg[1].update(pos[v],inf);
            //cout << "trai "<<v << '\n';
        }
    }
    cout << -1;
}
int main()
{
    fastio
    //freopen("c.INP","r",stdin);
    //freopen("c.OUT","w",stdout);
    solve();
}

Compilation message (stderr)

treatment.cpp: In member function 'void segtree::update(ll, ll, ll, ll, ll)':
treatment.cpp:41:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   41 |         ll mid=l+r>>1;
      |                ~^~
treatment.cpp: In member function 'node segtree::get(ll, ll, ll, ll, ll)':
treatment.cpp:50:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   50 |         ll mid=l+r>>1;
      |                ~^~

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