Wa on #44 求调

#include<bits/stdc++.h>
#define int long long
#define mp make_pair
#define fi first
#define se second
#define lb lower_bound
#define fr front()
#define pii pair<int,int>
#define INF 1e18
using namespace std;

int n,l,a[200005],b[200005],c[200005],lst[200005],used[200005],t[200005],top,top2;
int dis[200005],vis[200005];
vector<pii> g[200005];
map<pii,int> cp;
vector<int> in;

void lsh(){
    sort(c+1,c+top+1);int len=0;
    len=unique(c+1,c+top+1)-c-1;top=len;
    for(int i=1;i<=n;i++){
        int num=lower_bound(c+1,c+top+1,a[i])-c;a[i]=num;
        num=lower_bound(c+1,c+top+1,b[i])-c;b[i]=num;
    }
}

struct node{
    int u,dis;
    friend bool operator<(node a,node b){
        return a.dis>b.dis;
    }
};
priority_queue<node> q;

void dijkstra(){
    for(int i=1;i<=top;i++)dis[i]=INF;
    dis[1]=0;q.push({1,0});
    while(!q.empty()){
        int u=q.top().u;
        vis[u]=1;q.pop();
        for(auto i:g[u]){
            if(vis[i.fi])continue;
            if(dis[i.fi]>dis[u]+i.se){
                dis[i.fi]=dis[u]+i.se;
                lst[i.fi]=u;if(i.se<abs(c[i.fi]-c[u]))used[i.fi]=1;
                else used[i.fi]=0;q.push({i.fi,dis[i.fi]});
            }
        }
    }
}

signed main(){
    ios::sync_with_stdio(false);
    cin>>n>>l;
    c[++top]=0;c[++top]=l;
    for(int i=1;i<=n;i++){
        int x,d,ti,p;
        cin>>x>>d>>ti>>p;
        if(x-p<0)continue;top2++;
        a[top2]=x-p;b[top2]=x+d;t[top2]=ti+p;
        c[++top]=a[top2];c[++top]=b[top2];
        cp.insert(pair<pii,int>(mp(x-p,x+d),i));
    }
    lsh();
    for(int i=1;i<top;i++){
        g[i].push_back(mp(i+1,c[i+1]-c[i]));
        g[i+1].push_back(mp(i,c[i+1]-c[i]));
    }
    for(int i=1;i<=top2;i++){
        if(a[i]==0&&b[i]==0)continue;
        g[a[i]].push_back(mp(b[i],t[i]));
    }
    dijkstra();
    cout<<dis[top]<<"\n";int ans=0;
    for(int i=top;i!=0;i=lst[i]){
        if(used[i]){
            auto k=cp.find(mp(c[lst[i]],c[i]));
            if(k!=cp.end())in.push_back(k->se),ans++;
        }
    }
    cout<<ans<<"\n";
    reverse(in.begin(),in.end());
    for(auto i:in)cout<<i<<" ";
}