样例都过，数据只有5分

不仅WA，而且TLE。。

代码：

#include<bits/stdc++.h>
using namespace std;
#define ads(k) (abs(h[i]-(k)))
#define zm(p) (p==inf?0:zm[p])
const int N=1e6+10;const inf=0x3fffffff;
int h[N],n,g[N][2],f[N][23][3];
struct node
{ int id,dt;
  friend bool operator <(node x,node y)
  {
    return x.dt<y.dt;
  }
}ans[7];
void init()
{ set<node>s; //默认从小到大排序 
  set<node> :: iterator  it,il;
  //需要用一个数组g[i][0/1]分别描述离i第1/2近的城市
  //set中存的是高度 需要用数组zm[i]得到城市编号
  s.insert(node{n,h[n]}); h[0]=inf;
  for(int i=n-1;i>0;--i)
  { int mini=inf,tl=0,tl2=0;
    ans[0].dt=inf,ans[1].dt=inf,ans[2].dt=inf,ans[3].dt=inf,ans[4].dt=inf,ans[5].dt=inf;
    it=s.upper_bound(node{i,h[i]}); il=it;
    if(it!=s.end())ans[1]=*it;
    if(it!=s.end()&&(++it)!=s.end())ans[2]=*it;it=il;
    if(it!=s.begin())ans[3]=*(--it);
    if(it!=s.begin())ans[4]=*(--it);
    sort(ans+1,ans+4+1);
    for(int j=1;ans[j].dt!=inf;++j)
    {
      if(tl==0||abs(ans[j].dt-h[i])<mini||((abs(ans[j].dt-h[i])==mini)&&ans[j].dt<h[tl]))
      {
        tl2=tl,tl=ans[j].id,mini=abs(ans[j].dt-h[i]);
      }
      else if(tl2==0||abs(ans[j].dt-h[i])<abs(h[tl2]-h[i])||((abs(ans[j].dt-h[i])==abs(h[tl2]-h[i]))&&ans[j].dt<h[tl]))
      {
        tl2=ans[j].id;
      }
    }
    g[i][0]=tl,g[i][1]=tl2;
    
    s.insert(node{i,h[i]});
  }
  for(int i=n;i>0;--i)
  { if(g[i][0]==0||g[i][1]==0)continue;
    f[i][0][0]=g[g[i][1]][0];
    f[i][0][1]=abs(h[i]-h[g[i][1]]);
    f[i][0][2]=abs(h[f[i][0][0]]-h[g[i][1]]);
    for(int j=1;i+(j<<1)<=n;++j)
    { if(f[i][j-1][0]==0)continue;
      f[i][j][0]=f[f[i][j-1][0]][j-1][0]; 
      if(f[i][j][0]==0)continue;
      f[i][j][1]=f[i][j-1][1]+f[f[i][j-1][0]][j-1][1];
      f[i][j][2]=f[i][j-1][2]+f[f[i][j-1][0]][j-1][2];
    }
  }
}
int main()
{
  int xr,m; //freopen("P1081.in","r",stdin); freopen("P1081.out","w",stdout);
  cin>>n;
  for(int i=1;i<=n;++i)cin>>h[i];
  cin>>xr>>m;
  init(); int ansx=0,ansy=0,t;
  for(int i=1;i<=n;++i)
  { int tl=i,lx=0,ly=0,xi=xr;
    for(int j=20;j>=0;--j)
    { if(f[tl][j][0]==0)continue;
      if(xr-f[tl][j][1]-f[tl][j][2]>=0)
      {
        xr-=f[tl][j][1]+f[tl][j][2];
        lx+=f[tl][j][1],ly+=f[tl][j][2];
        tl=f[tl][j][0];
      }
    }
    if(abs(h[g[tl][1]]-h[tl])<=xr)lx+=abs(h[g[tl][1]]-h[tl]);
    if(ly==0)continue;
    if((ansx==0&&ansy==0)||ansx*ly>ansy*lx||(ansx*ly==ansy*lx&&h[i]>h[t]))
    {
      ansx=lx,ansy=ly,t=i;
    }
    xr=xi;
  }
  printf("%d\n",t);
  for(int i=1;i<=m;++i)
  { int s,x;
    scanf("%d%d",&s,&x);
    int tl=s,lx=0,ly=0,xr=x;
    for(int j=20;j>=0;--j)
    { if(f[tl][j][0]==0)continue;
      if(xr-f[tl][j][1]-f[tl][j][2]>=0)
      {
        xr-=f[tl][j][1]+f[tl][j][2];
        lx+=f[tl][j][1],ly+=f[tl][j][2];
        tl=f[tl][j][0];
      }
    }
    if(abs(h[g[tl][1]]-h[tl])<=xr)lx+=abs(h[g[tl][1]]-h[tl]);
    printf("%d %d\n",lx,ly);
  }
  return 0;
}