Submission #1009052

#	Time	Username	Problem	Language	Result	Execution time	Memory
1009052		imarn	Treatment Project (JOI20_treatment)	C++14	100 / 100	115 ms	9660 KiB

treatment

#include<bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC target("avx2")
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define plx pair<ll,int>
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()
#define vi vector<int>
using namespace std;
const int mxn=1e5+5;
int l[mxn],r[mxn],t[mxn],c[mxn],id[mxn],rid[mxn];
struct tree{
    pii a[2*mxn];
    void build(int sz,int x){
        for(int i=0;i<sz;i++)a[i+sz]={l[rid[i+1]]+x*t[rid[i+1]],rid[i+1]};
        for(int i=sz-1;i>0;i--)a[i]=min(a[2*i],a[2*i+1]);
    }
    void upd(int i,int amt,int sz){
        i+=sz;a[i]={amt,amt};for(i>>=1;i;i>>=1)a[i]=min(a[2*i],a[2*i+1]);
    }
    pii qr(int l,int r,int sz,pii res={2e9,2e9}){
        for(l+=sz,r+=sz;l<r;l>>=1,r>>=1){
            if(l&1)res=min(res,a[l++]);
            if(r&1)res=min(res,a[--r]);
        }return res;
    }
}tr[2];
ll dist[mxn]{0};
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    int n,m;cin>>n>>m;vector<pii>vec;
    for(int i=1;i<=m;i++)cin>>t[i]>>l[i]>>r[i]>>c[i],vec.pb({t[i],i});
    sort(vec.begin(),vec.end());for(int i=0;i<m;i++)id[vec[i].s]=i+1,rid[i+1]=vec[i].s;
    tr[0].build(m,-1);tr[1].build(m,1);priority_queue<plx,vector<plx>,greater<plx>>q;
    for(int i=1;i<=m;i++)dist[i]=1e18;
    for(int i=1;i<=m;i++){
        if(l[i]==1){
            dist[i]=c[i];q.push({dist[i],i});
            tr[0].upd(id[i]-1,2e9,m);tr[1].upd(id[i]-1,2e9,m);
        }
    }
    while(!q.empty()){
        auto u=q.top();q.pop();
        if(u.f>dist[u.s])continue;
        pii x=tr[0].qr(0,id[u.s],m);
        while(x.f<=r[u.s]-t[u.s]+1&&x.s!=2e9){
            if(dist[x.s]>u.f+c[x.s])dist[x.s]=u.f+c[x.s],q.push({dist[x.s],x.s});
            tr[0].upd(id[x.s]-1,2e9,m);
            x=tr[0].qr(0,id[u.s],m);
            if(x.s==2e9)break;
        }x=tr[1].qr(id[u.s]-1,m,m);
        while(x.f<=r[u.s]+t[u.s]+1&&x.s!=2e9){
            if(dist[x.s]>u.f+c[x.s])dist[x.s]=u.f+c[x.s],q.push({dist[x.s],x.s});
            tr[1].upd(id[x.s]-1,2e9,m);
            x=tr[1].qr(id[u.s]-1,m,m);
        }
    }ll ans=1e18;
    for(int i=1;i<=m;i++)if(r[i]==n)ans=min(ans,dist[i]);
    cout<<(ans==1e18?-1:ans);
}

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