记录编号	443536	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2012]开车旅行	最终得分	100
用户昵称	__stdcall	是否通过	通过
代码语言	C++	运行时间	1.286 s
提交时间	2017-08-31 10:39:46	内存使用	43.42 MiB

#include <cstring>
#include <algorithm>
#include <cstdio>
#include <set>
#include <utility>

using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
typedef set<pii>::iterator siter;
const int MAXN = 100010;
const int LOGN = 20;
const int MAXM = 100010;
int nowarn;

int n, h[MAXN], x0;
int m, si[MAXM], xi[MAXM];

void input() {
	nowarn = scanf( "%d", &n );
	for( int i = 1; i <= n; ++i )
		nowarn = scanf( "%d", h+i );
	nowarn = scanf( "%d", &x0 );
	nowarn = scanf( "%d", &m );
	for( int i = 0; i < m; ++i )
		nowarn = scanf( "%d%d", si+i, xi+i );
}

struct Info {
	int to;
	ll adis, bdis;
	Info():
		to(0), adis(0), bdis(0) {}
	Info( int to, ll adis, ll bdis ):
		to(to), adis(adis), bdis(bdis) {}
};

Info goa[MAXN], gob[MAXN], go[MAXN][LOGN];

set<pii> s;
bool better( pii a, pii b ) {
	if( a.first == b.first )
		return h[a.second] < h[b.second];
	return a.first < b.first;
}
pii find1( pii tmp[], int size ) {
	pii ans = tmp[0];
	for( int i = 1; i < size; ++i )
		if( better( tmp[i], ans ) )
			ans = tmp[i];
	return ans;
}
pii find2( pii tmp[], int size ) {
	pii ans1 = tmp[0], ans2 = tmp[1];
	if( better( ans2, ans1 ) )
		swap( ans1, ans2 );
	for( int i = 2; i < size; ++i )
		if( better( tmp[i], ans1 ) )
			ans2 = ans1, ans1 = tmp[i];
		else if( better( tmp[i], ans2 ) )
			ans2 = tmp[i];
	return ans2;
}
void prelude() {
	for( int i = n; i >= 1; --i ) {
		if( i <= n-1 ) {
			pii tmp[2];
			int size = 0;
			siter it = s.lower_bound( pii( h[i], i ) );
			if( it != s.end() )
				tmp[size++] = pii( abs( h[i] - it->first ), it->second );
			if( it != s.begin() ) {
				--it;
				tmp[size++] = pii( abs( h[i] - it->first ), it->second );
			}
			tmp[0] = find1( tmp, size );
			gob[i].to = tmp[0].second;
			gob[i].bdis = tmp[0].first;
		}
		if( i <= n-2 ) {
			pii tmp[4];
			int size = 0;
			siter it = s.lower_bound( pii( h[i], i ) );
			if( it != s.end() ) {
				tmp[size++] = pii( abs( h[i] - it->first ), it->second );
				++it;
				if( it != s.end() )
					tmp[size++] = pii( abs( h[i] - it->first ), it->second );
				--it;
			}
			if( it != s.begin() ) {
				--it;
				tmp[size++] = pii( abs( h[i] - it->first ), it->second );
				if( it != s.begin() ) {
					--it;
					tmp[size++] = pii( abs( h[i] - it->first ), it->second );
				}
			}
			tmp[0] = find2( tmp, size );
			goa[i].to = tmp[0].second;
			goa[i].adis = tmp[0].first;
		}
		s.insert( pii( h[i], i ) );
	}
	for( int i = 1; i <= n; ++i ) {
		int mid = goa[i].to;
		go[i][0].adis = goa[i].adis;
		go[i][0].bdis = gob[mid].bdis;
		go[i][0].to = gob[mid].to;
	}
	bool flag = true;
	for( int k = 0; flag; ++k ) {
		flag = false;
		for( int i = 1; i <= n; ++i ) {
			int mid = go[i][k].to;
			if( !mid ) continue;
			flag = true;
			go[i][k+1].to = go[mid][k].to;
			go[i][k+1].adis = go[i][k].adis + go[mid][k].adis;
			go[i][k+1].bdis = go[i][k].bdis + go[mid][k].bdis;
		}
	}
}

pii simulate( int s, int x ) {
	int adis = 0, bdis = 0;
	for( int k = LOGN-1; k >= 0; --k ) {
		if( !go[s][k].to ) continue;
		ll dis = go[s][k].adis + go[s][k].bdis;
		if( dis > x ) continue;
		x -= (int)dis;
		adis += (int)go[s][k].adis;
		bdis += (int)go[s][k].bdis;
		s = go[s][k].to;
	}
	if( goa[s].to && goa[s].adis <= x )
		adis += (int)goa[s].adis;
	return pii(adis, bdis);
}
void solve1() {
	double minv = 1e100;
	int from = int(max_element( h+1, h+n+1 ) - h);
	for( int i = 1; i <= n; ++i ) {
		pii tmp = simulate(i, x0);
		if( !tmp.second ) continue;
		double div = (double)tmp.first / tmp.second;
		if( div < minv )
			minv = div, from = i;
	}
	printf( "%d\n", from );
}
void solve2() {
	for( int i = 0; i < m; ++i ) {
		pii tmp = simulate( si[i], xi[i] );
		printf( "%d %d\n", tmp.first, tmp.second );
	}
}

int main() {
	freopen( "drive.in", "r", stdin );
	freopen( "drive.out", "w", stdout );
	input(), prelude(), solve1(), solve2();
	return 0;
}