蒟蒻50ptsTLE求调

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+10,M = 32,K = 18;
int n,q,b[N],cnt,p[M],p2[K];
long double dp[2][M][K],ANS[N];
unordered_map<int,int> mp;
struct T{
    int p;
    int t;
    int x;
}a[N],d[N];
inline bool cmp(T y,T z){
    if(y.p!=z.p) return y.p<z.p;
    else return y.t>z.t;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>q;
    p[0]=1;
    for(int i=1;i<=M-1;i++){
        p[i]=p[i-1]*2;
    }
    p2[0]=1;
    for(int i=1;i<=K-1;i++){
        p2[i]=p2[i-1]*3;
    }
    for(int i=1;i<=n;i++){
        cin>>a[i].p>>a[i].t>>a[i].x;
    }
    cnt=n;
    for(int i=1;i<=q;i++){
        cin>>b[i];
        ANS[i]=1e18;
        if(mp[b[i]]) continue;
        mp[b[i]]=i;
        cnt++;
        a[cnt].p=b[i];
        a[cnt].x=1;
        a[cnt].t=0;
    }
    sort(a+1,a+cnt+1,cmp);
    int tot=0;
    for(int i=1;i<=cnt;i++){
        if(a[i].p!=a[i-1].p){
            ++tot;
            d[tot].p=a[i].p;
            d[tot].t=a[i].t;
            d[tot].x=a[i].x;
        }
    }
    for(int i=0;i<=M-1;i++){
        for(int j=0;j<=K-1;j++){
            dp[0][i][j]=1e18;
        }
    }
    dp[0][0][0]=0;
    for(int i=1;i<=tot;i++){
        int s=(i&1),w=((i-1)&1);
        for(int j=0;j<=M-1;j++){
            for(int k=0;k<=K-1;k++){
                dp[s][j][k]=1e18;
            }
        }
        for(int j=0;j<=M-1;j++){
            for(int k=0;k<=K-1;k++){
                if(d[i].x==1){
                    dp[s][j][k]=min(dp[s][j][k],dp[w][j][k]+(double)(d[i].p-d[i-1].p)/(double)(p[j]*p2[k]));
                }
                else if(d[i].x==2){
                    if(j==0) dp[s][j][k]=min(dp[s][j][k],dp[w][j][k]+(double)(d[i].p-d[i-1].p)/(double)(p[j]*p2[k]));
                    else dp[s][j][k]=min(dp[w][j][k]+(double)(d[i].p-d[i-1].p)/(double)(p[j]*p2[k]),dp[w][j-1][k]+(double)(d[i].p-d[i-1].p)/(double)(p[j-1]*p2[k])+(double)d[i].t);
                }
                else if(d[i].x==3){
                    if(k==0) dp[s][j][k]=min(dp[s][j][k],dp[w][j][k]+(double)(d[i].p-d[i-1].p)/(double)(p[j]*p2[k]));
                    else dp[s][j][k]=min(dp[w][j][k]+(double)(d[i].p-d[i-1].p)/(double)(p[j]*p2[k]),dp[w][j][k-1]+(double)(d[i].p-d[i-1].p)/(double)(p[j]*p2[k-1])+(double)d[i].t);
                }
                else{
                    if(j<=1) dp[s][j][k]=min(dp[s][j][k],dp[w][j][k]+(double)(d[i].p-d[i-1].p)/(double)(p[j]*p2[k]));
                    else dp[s][j][k]=min(dp[w][j][k]+(double)(d[i].p-d[i-1].p)/(double)(p[j]*p2[k]),dp[w][j-2][k]+(double)(d[i].p-d[i-1].p)/(double)(p[j-2]*p2[k])+(double)d[i].t);
                }
            }
        }
        if(mp[d[i].p]){
            for(int j=0;j<=M-1;j++){
                for(int k=0;k<=K-1;k++){
                    ANS[mp[d[i].p]]=min(ANS[mp[d[i].p]],dp[s][j][k]);
                }
            }
        }
    }
    for(int i=1;i<=q;i++){
        cout<<fixed<<setprecision(7);
        cout<<ANS[mp[b[i]]]<<endl;
    }
    return 0;
}