RT 99 孩子吧

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL read()
{
	LL w=0;bool f=true;char c=getchar();
	while(!isdigit(c)){if(c=='-')f=false;c=getchar();}
	while(isdigit(c))w=(w<<1)+(w<<3)+(c^48),c=getchar();
	return f?w:~w+1;
}
const int N=1e5+66;
const LL INF=1e18;

LL n,m,x0,h[N];
struct city
{
	LL h,id;
	friend bool operator <(city n1,city n2){return n1.h<n2.h;}
}a[N];

LL dis[2][N][33],f[2][N][33];
int l[N],r[N];

void pre()
{
	sort(a+1,a+n+1);
	for(int i=1;i<=n;++i) l[a[i].id]=a[i-1].id,r[a[i].id]=a[i+1].id;
	
	for(int i=1;i<=n;++i)
	{
		LL sta[5],fir=INF,sec=INF,id_fir,id_sec;
		
		sta[1]=l[l[i]]? h[i]-h[l[l[i]]] :INF;
		sta[2]=l[i]? h[i]-h[l[i]] :INF;
		sta[3]=r[i]? h[r[i]]-h[i] :INF;
		sta[4]=r[r[i]]? h[r[r[i]]]-h[i] :INF;
		
		for(int j=1;j<=4;++j)
		  if(fir>sta[j]) fir=sta[j],id_fir=j;
		for(int j=1;j<=4;++j)
		  if(sec>sta[j]&&j!=id_fir) sec=sta[j],id_sec=j;
		
		if(id_fir==1) f[1][i][0]=l[l[i]];
		if(id_fir==2) f[1][i][0]=l[i];
		if(id_fir==3) f[1][i][0]=r[i];
		if(id_fir==4) f[1][i][0]=r[r[i]];
		
		if(id_sec==1) f[0][i][0]=l[l[i]];
		if(id_sec==2) f[0][i][0]=l[i];
		if(id_sec==3) f[0][i][0]=r[i];
		if(id_sec==4) f[0][i][0]=r[r[i]];
		
		if(f[1][i][0]) dis[1][i][0]=fir;
		if(f[0][i][0]) dis[0][i][0]=sec;
		
		if(l[i]) r[l[i]]=r[i];
		if(r[i]) l[r[i]]=l[i];
	}
}

void work()
{
	for(int i=1;i<=n;++i)
	{
		f[0][i][1]=f[1][f[0][i][0]][0];
		dis[0][i][1]=dis[0][i][0];
		dis[1][i][1]=dis[1][f[0][i][0]][0];
	}
	for(int j=2;j<=30;++j)
	  for(int i=1;i<=n;++i)
      {
      	f[0][i][j]=f[0][f[0][i][j-1]][j-1];
      	dis[0][i][j]=dis[0][i][j-1]+dis[0][f[0][i][j-1]][j-1];
      	dis[1][i][j]=dis[1][i][j-1]+dis[1][f[0][i][j-1]][j-1];
	  }
}

void solve1()
{
	x0=read();
	double Ans=0x7fffffff;
	int pos=0;
	for(int i=1;i<=n;++i)
	{
		LL s1=0,s2=0,x=x0;int s=i;
		for(int j=30;j>=0;--j)
		  if(f[0][s][j]!=0&&dis[0][s][j]+dis[1][s][j]<=x)
	  	  {
	  		s1+=dis[0][s][j];s2+=dis[1][s][j];
	  		x-=dis[0][s][j]+dis[1][s][j];
	  		s=f[0][s][j];
	      }
	    if(s2==0)
	    {
	    	if(pos==0) pos=i;
		}
		else
		{
			double temp=(s1*1.0)/(s2*1.0);
			if(Ans>temp) Ans=temp,pos=i;	
		}
	}  
	printf("%d\n",pos);
}

void solve2(int s,LL x)
{
	LL s1=0,s2=0;
	for(int i=30;i>=0;--i)
	  if(f[0][s][i]!=0&&dis[0][s][i]+dis[1][s][i]<=x)
	  {
	  	s1+=dis[0][s][i];s2+=dis[1][s][i];
	  	x-=dis[0][s][i]+dis[1][s][i];
	  	s=f[0][s][i];
	  }
	printf("%lld %lld\n",s1,s2);
}

int main()
{
	freopen("travel.out","w",stdout);
	
	n=read();
	for(int i=1;i<=n;++i) h[i]=read(),a[i]=(city){h[i],i};
	
	pre();
	
	work();
	
	solve1();
	
	m=read();
	for(int i=1;i<=m;++i)
	{
		int s=read();LL x=read();
		solve2(s,x);
	}
	
	fclose(stdin);
	fclose(stdout);
	return 0;
}