记录编号	197010	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2012]开车旅行	最终得分	100
用户昵称	mikumikumi	是否通过	通过
代码语言	C++	运行时间	1.863 s
提交时间	2015-10-23 07:16:46	内存使用	60.98 MiB

#include<cstdio>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<set>
using namespace std;
typedef long long LL;
int g[100010][30]={0};//从i地走2^j轮后所在的位置
LL f[100010][30][2]={0};//A，B所走的距离
int N,M;
int next[100010][2]={0};//[0]代表最近的，[1]代表次近的
LL dist[100010][2]={0};
LL X;
int S;
int t;
class miku
{
public:
	LL H;
	int id;
	miku(){}
	bool operator < (const miku &b) const
	{
		return H<b.H;
	}
}H[100010];
set<miku> tr;
set<miku>::iterator it;
inline void update(miku x,miku y)
{
	LL tem=abs(x.H-y.H);
	int w=x.id,p=y.id;
	if(!next[w][0])
	{
		next[w][0]=p;
		dist[w][0]=tem;
	}
	else if(tem<dist[w][0]||(tem==dist[w][0]&&y.H<x.H))
	{
		next[w][1]=next[w][0];
		dist[w][1]=dist[w][0];
		next[w][0]=p;
		dist[w][0]=tem;
	}
	else if(!next[w][1]||tem<dist[w][1]||(tem==dist[w][1]&&y.H<x.H))
	{
		next[w][1]=p;
		dist[w][1]=tem;
	}
}
void work()
{
	for(int i=N;i>=1;i--)
	{
		tr.insert(H[i]);
		it=tr.find(H[i]);
		if(it!=tr.begin())
		{
			it--;
			update(H[i],*it);
			if(it!=tr.begin())
			{
				it--;
				update(H[i],*it);
				it++;
			}
			it++;
		}
		if(it!=tr.end())
		{
			it++;
			update(H[i],*it);
			if(it!=tr.end())
			{
				it++;
				update(H[i],*it);
			}
		}
	}
	for(int i=1;i<=N;i++)
	{
		g[i][0]=next[next[i][1]][0];
		f[i][0][0]=dist[i][1];
		f[i][0][1]=dist[next[i][1]][0];
	}
	t=int(trunc(log2(N)));
	for(int j=1;j<=t;j++)
		for(int i=1;i<=N;i++)
		{
			g[i][j]=g[g[i][j-1]][j-1];
			f[i][j][0]=f[i][j-1][0]+f[g[i][j-1]][j-1][0];
			f[i][j][1]=f[i][j-1][1]+f[g[i][j-1]][j-1][1];
		}
}
void get(int s,LL x,LL& dista,LL& distb)
{
	for(int i=t;i>=0;i--)
	{
		if(f[s][i][0]+f[s][i][1]<=x&&g[s][i])
		{
			dista+=f[s][i][0];
			distb+=f[s][i][1];
			x-=f[s][i][0]+f[s][i][1];
			s=g[s][i];
		}
	}
	if(next[s][1]&&dist[s][1]<=x)
		dista+=dist[s][1];
}
int main()
{
	freopen("drive.in","r",stdin);
	freopen("drive.out","w",stdout);
	scanf("%d",&N);
	int ans=0;
	for(int i=1;i<=N;i++)
	{
		scanf("%lld",&H[i].H);//提交时修改为lld
		H[i].id=i;
	}
	work();
	scanf("%lld",&X);//提交时修改为lld
	LL a=1e15,b=0;
	for(int i=1;i<=N;i++)
	{
		LL dista=0,distb=0;
		get(i,X,dista,distb);
		if(distb&&(ans==0||a*distb>b*dista))
		{
			ans=i;
			a=dista;
			b=distb;
		}
	}
	printf("%d\n",ans);
	scanf("%d",&M);
	//cout<<M<<endl;
	for(int i=1;i<=M;i++)
	{
		scanf("%d%lld",&S,&X);
		LL dista=0,distb=0;
		get(S,X,dista,distb);
		printf("%lld %lld\n",dista,distb);
		//if(i==14712) cout<<"*********************************"<<endl;
	}
	return 0;
}