Submission #1075594

#	Time	Username	Problem	Language	Result	Execution time	Memory
1075594		MOUF_MAHMALAT	Treatment Project (JOI20_treatment)	C++14	4 / 100	135 ms	54356 KiB

treatment

#include <bits/stdc++.h>
#define all(v) v.begin(),v.end()
#define F first
#define S second
#define mid ((l+r)>>1)
using namespace std;
typedef long long ll;
typedef pair<ll,ll>pll;
const ll oo= 1e5+9;
const ll inf=1e18;
struct node
{
    ll t,l,r,c;
} a[oo];
struct seg
{
    seg *l=0,*r=0;
    ll mn=inf;
}*root;
bool cmp(const node&A,const node&B)
{
    return A.r < B.r;
}
ll n,m;
void up(seg*&d,ll l,ll r,ll id,ll val)
{
    if(l==r)
        return void(d-> mn = min(d->mn ,val));
    if(id<=mid)
    {
        if(d->l==0)
            d->l = new seg;
        up(d->l,l,mid,id,val);
    }
    else
    {
        if(d->r==0)
            d->r = new seg;
        up(d->r,mid+1,r,id,val);
    }
    d-> mn = inf;
    if(d->l!=0)
        d->mn = d->l->mn;
    if(d->r!=0)
        d->mn = min(d->mn,d->r->mn);
}
ll best(seg*&d,ll l,ll r,ll lx)
{
    if(d==0||r<lx)
        return inf;
    if(lx<=l)
        return d->mn;
    return min(best(d->l,l,mid,lx),best(d->r,mid+1,r,lx));
}
void solve()
{root = new seg();
    cin>>n>>m;
    for(ll i=0; i<m; i++)
    {
        cin>>a[i].t>>a[i].l>>a[i].r>>a[i].c;
    }
    sort(a,a+m,cmp);
    ll ans=inf;
    up(root,0,n,0,0);
    for(ll i=0; i<m; i++)
    {
         ll x= a[i].c + best(root,0,n,a[i].l-1);
         if(a[i].r==n)
            ans=min(ans,x);
         up(root,0,n,a[i].r,x);
    }
    if(ans>=inf)
        cout<<-1;
    else
        cout<<ans;
}
int main()
{
    ios::sync_with_stdio(0),cin.tie(0);
    ll tt=1;
//    cin>>tt;
    while(tt--)
        solve();
    return 0;
}

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