记录编号	303598	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2012]开车旅行	最终得分	100
用户昵称	Fmuckss	是否通过	通过
代码语言	C++	运行时间	3.602 s
提交时间	2016-09-06 08:03:07	内存使用	43.96 MiB

#include <iostream>
#include <cstdio>
#include <set>
#include <cmath>
using namespace std;
typedef long long LL;
const int maxn = 1e5 + 10;
const int inf = 2e9;
const double eps = 1e-7;
 
#define A (1)
#define B (0)
 
int n, m;
int to_end, end_pos;
int x0;
 
#define is_num(x) (x <= '9' and x >= '0')
int get_num() {
	char tmp = getchar();
	int res = 0;
	bool mul = false;
	while(not is_num(tmp)) { if(tmp == '-') mul = true; tmp = getchar(); }
	while(    is_num(tmp)) {
		res = res * 10 + tmp - '0';
		tmp = getchar();
	}
	return mul ? -res : res;
}
 
int to_ne[2][maxn];
int to_v[2][maxn];
 
int mul_to[maxn][20];
LL disa[maxn][20];
LL disb[maxn][20]; 
 
inline void add_edge(int fr, int to, int v, int type) {
	to_ne[type][fr] = to;
	to_v[type][fr] = v;
}
 
class Node {
public:
	int pos;
	LL hi;
	Node() {}
	Node(int pos_, int hi_) { pos = pos_, hi = (LL)hi_; }
	
	bool operator < (const Node &b) const{
		return hi == b.hi ? pos < b.pos : hi < b.hi; 
	}
	void print() {
		printf("%d %lld\n", pos, hi);
	}
}ns[maxn];
 
set<Node> s;
 
inline int get_min(int i) {
	set<Node> :: iterator now;
	Node la, ne, del;
	now = s.find(ns[i]);
	// out_s();
	// printf("\n");
	if(now != s.begin()) {
		now--;
		la = *(now);
		now = s.lower_bound(Node(0, la.hi));
		la = *(now);
	} else {
		la = Node(inf, inf);
	}
 
	now = s.upper_bound(ns[i]);
	if(now != s.end()) ne = *(now);
	else ne = Node(inf, inf);
	
	if(abs(ns[i].hi - la.hi) <= abs(ne.hi - ns[i].hi)) return la.pos;
	else return ne.pos;
}
 
inline void build() {
	int del, pos;
	for(int i = 1; i <= n - 2; i++) {
		pos = get_min(i);
		if(pos != inf) add_edge(i, pos, abs(ns[i].hi - ns[pos].hi), B);
		
		if(pos != inf) s.erase(s.find(ns[pos]));
		del = pos;
		
		pos = get_min(i);
		if(pos != inf) add_edge(i, pos, abs(ns[i].hi - ns[pos].hi), A);
		
		if(pos != inf) s.insert(ns[del]);
		s.erase(ns[i]);
	}
	
	add_edge(n - 1, n, abs(ns[n - 1].hi - ns[n].hi), B);
}
 
 
LL da, db;
int ans_tar;
LL ans_a, ans_b, ans_hi; 
 
void read() {
	n = get_num();
	int x, hi;
	for(int i = 1; i <= n; i++) {
		hi = get_num();
		ns[i] = Node(i, hi);
				
		s.insert(ns[i]);
	}
	x0 = get_num();
}
 
inline void get_ne() {
	for(int i = 1; i <= n; i++) {
		mul_to[i][0] = to_ne[B][to_ne[A][i]]; // target which start with A end by two step
		
		disa[i][0] = to_v[A][i]; // the dis of driver a 
		disb[i][0] = to_v[B][to_ne[A][i]]; // the dis of driver b 
	}
	
	for(int j = 1; j <= 17; j++) {
		for(int i = 1; i <= n; i++) {
			mul_to[i][j] = mul_to[mul_to[i][j - 1]][j - 1];
			
			disa[i][j] = disa[i][j - 1] + disa[mul_to[i][j - 1]][j - 1];
			disb[i][j] = disb[i][j - 1] + disb[mul_to[i][j - 1]][j - 1];
		}
	}
}
 
void query(int s, int lim, LL &da, LL &db) {
	for(int i = 17; i >= 0; i--) {
		if(disa[s][i] + disb[s][i] > lim) continue;
		lim -= disa[s][i] + disb[s][i];
		
		da += disa[s][i];
		db += disb[s][i];
		
		s = mul_to[s][i];
	}
	
	if(to_v[A][s] <= lim) da += to_v[A][s];
}
 
void solve() {
	build();
	// out();
	get_ne();
	ans_a = 1;
	
	for(int i = 1; i <= n; i++) {
		da = 0, db = 0;
		query(i, x0, da, db);
		
		if(db == 0) da = inf;
		
		if(da * ans_b < db * ans_a)
			ans_a = da, ans_b = db, ans_tar = i, ans_hi = ns[i].hi;
		else if(da * ans_b == db * ans_a and ans_hi < ns[i].hi) 
			ans_a = da, ans_b = db, ans_tar = i, ans_hi = ns[i].hi;
 
	}
	
	printf("%d\n", ans_tar);
	
	m = get_num();
	int x, hi;
	for(int i = 1; i <= m; i++) {
		x = get_num();
		hi = get_num();
		
		da = db = 0;
		query(x, hi, da, db);
		printf("%lld %lld\n", da, db);
	}
}
 
int main() {
	freopen("drive.in", "r", stdin);
	freopen("drive.out", "w", stdout);
	read();
	solve();
	return 0;
}