思路是$f[j][k]$表示速度为$2^j*3^k$的最短时间，使用了滚动数组

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10;
int n,q;
long double f[5][100][100],t[N],p[N],x[N],pow2[100],pow3[100],ans[N];
struct kx{
	int id;
	long double v;
}y[N];
bool cmp(kx xx,kx yy){return xx.v<yy.v;}
signed main(){
	cin>>n>>q;
	//初始化
	for(int i=0;i<=3;i++)
		for(int j=0;j<=30;j++)
			for(int k=0;k<=30;k++)
			f[i][j][k]=3000000000;
	pow2[0]=pow3[0]=1;
	for(int i=1;i<=30;i++) pow2[i]=pow2[i-1]*2,pow3[i]=pow3[i-1]*3;
	for(int i=1;i<=n;i++){
		cin>>p[i]>>t[i]>>x[i];
		ans[i]=3000000000;
	}
	for(int i=1;i<=q;i++) {cin>>y[i].v;y[i].id=i;}
	sort(y+1,y+1+q,cmp);
	f[0][0][0]=0;
	int num=1;
	for(int i=1;i<=n;i++){
		int now=i&1,pre=now^1;
		for(int j=0;j<=30;j++){
			for(int k=0;k<=30;k++){
				f[now][j][k]=f[pre][j][k]+(p[i]-p[i-1])/(pow2[j]*pow3[k]);
				if(x[i]==1) continue;
				if(x[i]==2&&j) f[now][j][k]=min(f[pre][j-1][k]+(p[i]-p[i-1])/(pow2[j-1]*pow3[k])+t[i],f[now][j][k]);
				if(x[i]==3&&k)	f[now][j][k]=min(f[pre][j][k-1]+(p[i]-p[i-1])/(pow2[j]*pow3[k-1])+t[i],f[now][j][k]);
				if(x[i]==4&&j>=2) f[now][j][k]=min(f[pre][j-2][k]+(p[i]-p[i-1])/(pow2[j-2]*pow3[k])+t[i],f[now][j][k]);
			}
		}
		while(num<=q&&p[i]>y[num].v){
			for(int j=0;j<=30;j++){
				for(int k=0;k<=30;k++){
					ans[y[num].id]=min(ans[y[num].id],f[pre][j][k]+(y[num].v-p[i-1])/(pow2[j]*pow3[k]));
				}
			}
			num++;
		}
	}
	while(num<=q){
		for(int j=0;j<=30;j++){
				for(int k=0;k<=30;k++){
					ans[y[num].id]=min(ans[y[num].id],f[(n&1)][j][k]+(y[num].v-p[n])/(pow2[j]*pow3[k]));
				}
			}
			num++;
	}
	for(int i=1;i<=q;i++) printf("%Lf\n",ans[i]);
	return 0;
}
/*
考虑预处理f[i][j][k]是到第i个车站后，速度为2^j*3^k的最短时间
对于查询只需要二分+枚举硬算
考虑到会MLE，直接离线询问
*/