记录编号	199167	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2012]开车旅行	最终得分	100
用户昵称	thomount	是否通过	通过
代码语言	C++	运行时间	2.411 s
提交时间	2015-10-25 23:31:39	内存使用	52.17 MiB

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int read() {
	char ch = getchar();
	while ((ch < '0' || ch > '9') && ch != '-') ch = getchar();
	int ans = 0, flag = 1;
	if (ch == '-') flag = -1, ch = getchar();
	while (ch >= '0' && ch <= '9') ans = ans * 10 + ch - '0', ch = getchar();
	return ans * flag;
}
const int N = 100010;
int h[N];
struct point {
	int x, t, w, size;
	point * ls, * rs;
	point(int x = 0, int t = 0, int w = 0): t(t), w(w), x(x), ls(0), rs(0), size(1) {}
	void update() {
		size = 1;
		if (ls) size += ls->size;
		if (rs) size += rs->size;
	}
} d[5*N];
int tot = 0;
typedef point * link;
link head;
int aa = 1, bb = 2, cc = 509, mm = 1000000007;
link make(int x, int t) {
	d[++tot] = point(x, t, aa);
	aa = (aa * bb + cc) % mm;
	return &d[tot];
}
struct inf {
	int f, x, t;
	inf(int x = 0, int t = 0, int f = 0): x(x), t(t), f(f) {}
} q[10];
bool operator < (inf a, inf b) {return (a.x == b.x)? (a.f < b.f):(a.x < b.x);}

void split(link p, int x, link & p1, link & p2) {
	if (!p) {p1 = p2 = 0; return;}
	if (x <= p->x) {
		split(p->ls, x, p1, p->ls);
		p2 = p;
	} else {
		split(p->rs, x, p->rs, p2);
		p1 = p;
	}
	p->update();
}
link merge(link p1, link p2) {
	if (!p1) return p2; if (!p2) return p1;
	if (p1->w < p2->w) {
		p1->rs = merge(p1->rs, p2);
		p1->update();
		return p1;
	} else {
		p2->ls = merge(p1, p2->ls);
		p2->update();
		return p2;
	}
}
link getmax(link p) {
	if (!p) return 0;
	while (p->rs) p = p->rs;
	return p;
}
link getmin(link p) {
	if (!p) return 0;
	while (p->ls) p = p->ls;
	return p;
}

struct move {
	int d;
	long long x, y;
	move(int d = 0, long long x = 0, long long y = 0): d(d), x(x), y(y) {}
} a[N][20], b[N];
move operator + (move a, move b) {
	return move(b.d, a.x + b.x, a.y + b.y);
}
bool judge(long long a, long long b, long long c, long long d) {
	if (!d) return false;
	if (!b) return true; 
	return ((double)a / b > (double)c / d);
}
int main() {
	freopen("drive.in", "r", stdin);
	freopen("drive.out", "w", stdout);
	int n = read();
	for (int i = 1; i <= n; i++) h[i] = read();
	
	head = 0;
	for (int i = n; i; i--) {
		link p1, p2;
		split(head, h[i], p1, p2);
		int r = 0;
		if (p1) {
			link p11 = getmax(p1);
			q[++r] = inf(h[i]-p11->x, p11->t, 0);
			if (p1->size > 1) {
				link p3, p4;
				split(p1, p11->x, p3, p4);
				link p5 = getmax(p3);
				q[++r] = inf(h[i]-p5->x, p5->t, 0);
				p1 = merge(p3, p4);
			}
		}
		if (p2) {
			link p11 = getmin(p2);
			q[++r] = inf(p11->x-h[i], p11->t, 1);
			if (p2->size > 1) {
				link p3, p4;
				split(p2, p11->x+1, p3, p4);
				link p5 = getmin(p4);
				q[++r] = inf(p5->x-h[i], p5->t, 1);
				p2 = merge(p3, p4);
			}
		}
		
		sort(q+1, q+r+1);
		if (r >= 1) b[i] = move(q[1].t, 0, abs(h[q[1].t]-h[i]));
		if (r >= 2) a[i][0] = move(q[2].t, abs(h[q[2].t] - h[i]), 0);
		head = merge(p1, merge(make(h[i], i), p2));
		
	}
	
//	for (int i = 1; i <= n; i++) printf("%d %d\n", a[0][i][0], a[1][i][0]);
	
	for (int i = 1; i <= n; i++) if (a[i][0].d && b[a[i][0].d].d) a[i][1] = a[i][0] + b[a[i][0].d];
	int T = 0;
	for (int i = 2; (1 << i) <= n; i++) {
		for (int j = 1; j <= n; j++) if (a[j][i-1].d && a[a[j][i-1].d][i-1].d) a[j][i] = a[j][i-1] + a[a[j][i-1].d][i-1];
		T = i;
	}
	
	int X0 = read(), w;
	long long ansA = 1, ansB = 0;
	for (int i = 1; i <= n; i++) {
		long long s = 0;
		long long A = 0, B = 0;
		int st = i;
		for (int j = T; j >= 0; j--) {
			if (a[st][j].d && a[st][j].x + a[st][j].y + s <= X0) {
				s += a[st][j].x + a[st][j].y;
				A += a[st][j].x; B += a[st][j].y;
				st = a[st][j].d;
			}
		}
		if (judge(ansA, ansB, A, B)) ansA = A, ansB = B, w = i;
	}
	
	printf("%d\n", w);
	
	int m = read();
	for (int i = 1; i <= m; i++) {
		int st = read(), x = read();
		long long s = 0, A = 0, B = 0;
		for (int j = T; j >= 0; j--) {
			if (a[st][j].d && a[st][j].x + a[st][j].y + s <= x) {
				s += a[st][j].x + a[st][j].y;
				A += a[st][j].x; B += a[st][j].y;
				st = a[st][j].d;
			}
		}
		printf("%lld %lld\n", A, B);
	}
	
	return 0;
}