Submission #1008419

#	Time	Username	Problem	Language	Result	Execution time	Memory
1008419		iee	Treatment Project (JOI20_treatment)	C++17	100 / 100	97 ms	19144 KiB

treatment

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define x first
#define y second
#define bg begin()
#define ed end()
#define pb push_back
#define mp make_pair
#define sz(a) int((a).size())
#define R(i,n) for(int i(0);i<(n);++i)
#define L(i,n) for(int i((n)-1);i>=0;--i)
const int iinf=0x3f3f3f3f;
const ll linf=0x3f3f3f3f3f3f3f3f;

//Data
const int N=1e5;
int m,n;
ll f[N];
struct info{
    int t,l,r,c;
    info(){}
    info(int t,int l,int r,int c):
        t(t),l(l),r(r),c(c){}
}a[N];

//Graph
/*
    思考：什么时候 i 后面可以接 j？
        a[i].r-a[j].l>=abs(a[i].t-a[j].t)
    如果 a[j].t<a[i].t，要求就是
        a[i].r-a[i].t>=a[j].l-a[j].t ->up
    如果 a[j].t>a[i].t，要求就是
        a[i].r+a[i].t>=a[j].l+a[j].t ->dn
    
    这题有个关键点：权在点上，所以 dijkstra 可以爽一点
*/
vector<int> adj; // 记得清空
priority_queue<pair<ll,int>> q;

//SegmentTree
struct tree{
    int l,r,mid,ma,mb; tree *ls,*rs;
    tree(int l,int r):l(l),r(r),ma(iinf*2),mb(iinf*2){
        if(r-l==1) return;
        mid=(l+r)>>1,ls=new tree(l,mid),rs=new tree(mid,r);
    }
    void pushup(){
        ma=min(ls->ma,rs->ma);
        mb=min(ls->mb,rs->mb);
    }
    void fix(int i,int a,int b){
        if(r-l==1) return ma=a,mb=b,void();
        i<mid?ls->fix(i,a,b):rs->fix(i,a,b),pushup();
    }
    void adde(int x,int y,int mx,bool t){
        if((t?ma:mb)>mx) return;
        if(r-l==1) return ma=mb=iinf*2,adj.pb(l);
        if(x<mid) ls->adde(x,y,mx,t);
        if(y>mid) rs->adde(x,y,mx,t);
        pushup();
    }
};

//Function

//Main
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>m>>n;
    R(i,n) cin>>a[i].t>>a[i].l>>a[i].r>>a[i].c,--a[i].t,--a[i].l;
    sort(a,a+n,[&](info p,info q){return p.t<q.t;});
    tree *rt=new tree(0,n);
    R(i,n){
        if(a[i].l==0) f[i]=a[i].c,
            q.push(mp(-f[i],i)),rt->fix(i,iinf*2,iinf*2);
        else rt->fix(i,a[i].l-a[i].t,a[i].l+a[i].t),f[i]=linf;
    }
    vector<int> vis(n + 1);
    while(sz(q)){
        int u=q.top().y; q.pop(),adj.clear();
        vis[u] = 1;
        rt->adde(0,u,a[u].r-a[u].t,true);
        rt->adde(u+1,n,a[u].r+a[u].t,false);
        for(int v:adj) assert(!vis[v]), f[v]=f[u]+a[v].c,q.push(mp(-f[v],v));
    }
    ll ns=linf;
    R(i,n)if(a[i].r==m) ns=min(ns,f[i]);
    if(ns==linf) ns=-1;
    cout<<ns<<'\n';
    return 0;
}

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