拿球的总时间是固定的，这个可以不考虑。

一个朴素的想法是，设 $f_{S,i}$ 表示已经拿了 $S$ 的球，现在在第 $i$ 个球的位置所用的最短时间，转移是朴素的，可以获得 24 分。

我们可以发现一个比较显然的性质：位于 $G$ 同一侧的球，离 $G$ 较远的球必然先于较近的被拿。

那么实际上有效状态 $S$ 只有 $O(N^2)$ 个。设 $f_{l,r,0/1}$ 表示拿了编号范围 $[1,l)\cup(r,N]$ 的球，现在在第 $l/r$ 个球的位置所需的最短时间，转移是朴素的。初始有 $f_{1,N,0}=\lvert S-X_1\rvert,f_{1,N,1}=\lvert S-X_N\rvert$。

设 $G$ 左右两边的小球编号分别为 $p_1,p_2$（也可能只有一个），所需时间为 $\min(f_{p_1,p_1,0}+(N+1)\lvert X_{p_1}-G\rvert,f_{p_2,p_2,0}+(N+1)\lvert X_{p_2}-G\rvert)$。

对于多次询问，我们不妨直接设另一个数组 $g$，含义与 $f$ 相同，初始有 $f_{1,N,0}=g_{1,N,1}=0$，那么所需时间为 $\min(\lvert S-X_1\rvert+f_{p_1,p_1,0}+(N+1)\lvert X_{p_1}-G\rvert,\lvert S-X_N\rvert+g_{p_2,p_2,0}+(N+1)\lvert X_{p_2}-G\rvert)$。$f,g$ 可以预处理，时间复杂度为 $O(N^2+Q)$（$Q$ 带不带 $\log$ 都行）。

看起来似乎没有优化空间了？

注意到 $T\leq5\times10^5$。若去重后不同的球的位置有 $n$ 个，在最理想的情况下，所需的时间也得是 $2+3+4+\cdots+(n+1)$（每捡一个球后走一米）。若理恵能完赛，至少要求 $\frac{(n+2)(n+1)}{2}-1\leq T$，也就是说 $n\geq10^3$ 时答案全是 No。

去重不影响我们的算法正确性，时间复杂度 $O(n^2+Q)$（最后记得加上拿球的总时间 $N$）。

Code，你怎么知道我 $Q$ 带了个 $\log$。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
    int x=0;char ch=getchar();
    while(!isdigit(ch)) ch=getchar();
    while(isdigit(ch)) x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
    return x;
}
const int N=5e5+10,M=1010;
int n,q,L,S,a[N],b[N];
ll f[2][M][M][2];
inline void Min(ll &x,ll y) {x=x>y?y:x;}
int main()
{
    n=read(),L=read();
    for(int i=1;i<=n;i++)
        a[i]=read(),++b[a[i]];
    for(int i=0;i<=L;i++) if(b[i]) ++S;
    q=read();
    if(S>999)
    {
        while(q--) puts("No");
        return 0;
    }
    memset(f,0x3f,sizeof(f));
    sort(a+1,a+n+1);
    n=unique(a+1,a+n+1)-a-1;
    for(int i=1;i<=L;i++) b[i]+=b[i-1];
    f[0][1][n][0]=f[1][1][n][1]=0;
    for(int i=0;i<2;i++)
        for(int len=n-1;len;len--)
            for(int l=1,r;(r=l+len-1)<=n;l++)
            {
                int num=b[L]-b[a[r]]+1;
                if(a[l]) num+=b[a[l]-1];
                Min(f[i][l][r][0],f[i][l-1][r][0]+1ll*num*(a[l]-a[l-1]));
                Min(f[i][l][r][0],f[i][l][r+1][1]+1ll*num*(a[r+1]-a[l]));
                Min(f[i][l][r][1],f[i][l-1][r][0]+1ll*num*(a[r]-a[l-1]));
                Min(f[i][l][r][1],f[i][l][r+1][1]+1ll*num*(a[r+1]-a[r]));
            }
    int u,v,T;
    while(q--)
    {
        u=read(),v=read(),T=read();
        ll ans=1e18;
        int x=lower_bound(a+1,a+n+1,v)-a;
        if(v<a[1])
            ans=f[1][1][1][1]+abs(u-a[n])+1ll*(b[L]+1)*(a[1]-v);
        else if(v>a[n])
            ans=f[0][n][n][0]+abs(u-a[1])+1ll*(b[L]+1)*(v-a[n]);
        else
            for(int i=0;i<2;i++)
            Min(ans,f[0][x-i][x-i][0]+abs(u-a[1])+1ll*(b[L]+1)*abs(v-a[x-i])),
            Min(ans,f[1][x-i][x-i][1]+abs(u-a[n])+1ll*(b[L]+1)*abs(v-a[x-i]));
        puts(ans+b[L]<=T?"Yes":"No");
    }
    return 0;
}