记录编号	135328	评测结果	WWWWWWWWWWWWWWEEEEEE
题目名称	[NOIP 2012]开车旅行	最终得分	0
用户昵称	Asm.Def	是否通过	未通过
代码语言	C++	运行时间	1.426 s
提交时间	2014-10-31 22:40:42	内存使用	7.55 MiB

#include <cstdio>
#include <iostream>
#include <cctype>
#include <queue>
#include <algorithm>
#include <cstring>
#include <ctime>
#include <set>
#define iter(v) v::iterator
using namespace std;
#if defined DEBUG
FILE *in = fopen("test", "r");
#define out stdout
#else 
FILE *in = fopen("drive.in", "r");
FILE *out = fopen("drive.out", "w");
#endif
template<typename T>inline void getint(T &x){
	char c = fgetc(in);
	while(!isdigit(c))c = fgetc(in);
	x = c - '0';
	while(isdigit(c = fgetc(in)))x = x * 10 - '0' + c;
}
typedef long long LL;
inline void putLL(const LL&x){
	if(x < 1000000000){fprintf(out, "%d ", x);return;}
	int l = x / 1000000000, r = x % 1000000000;
	fprintf(out, "%d%09d ", l, r);
}
/*==================================================*/
const int maxn = 100000 + 3;
struct V{
	int son[2], len[2], id, H;
	LL dis[2][2], S;
	V():S(0){
		son[1] = son[0] = dis[0][0] = dis[0][1] = dis[1][0] = dis[1][1] = 0;
	}
	bool operator < (const V &b)const{
		return H > b.H;
	}
}Node[maxn];

struct E{
	int len, id, H;
	LL dis[2], S;
	void init(const V &base, bool AB){
		len = base.len[AB], id = base.id;
		H = base.H, S = base.H;
		dis[0] = base.dis[AB][0], dis[1] = base.dis[AB][1];
	}
};

inline bool cmp(const E &a, const E &b){
	return a.S > b.S;
}

struct List{
	E *begin, *end, *exbegin;
	List *extra;
	List():begin(0), end(0), exbegin(0), extra(0){}
	void init(List *L, int i){
		const int &l = Node[i].len[0];
		int j = i, AB = 0, cnt = 0, t;
		E *k;
		while(j != 0){//第一轮
			if(L[j].begin != NULL && (!cnt || ((t = l >> 3) <= cnt && (l - t) >= cnt))){
				extra = L + j;
				exbegin = L[j].begin;
				break;
			}
			++cnt;j = Node[j].son[AB];AB ^= 1;
			if(!j)break;
			++cnt;j = Node[j].son[AB];AB ^= 1;
		}
		begin = new E[cnt + 1];
		end = begin + cnt;
		for(j=i,AB=0,k=begin;k != end; ++k){
			k->init(Node[j], AB);
			j = Node[j].son[AB];
			AB ^= 1;
		}
	}
	E *find(LL S){
		E temp;temp.S = S;
		return find(temp);
	}
	E *find(E &temp){//返回最后一个距离尾端不低于S的节点,无解返回NULL
		E *i1 = upper_bound(begin, end, temp, cmp);
		if(i1 == end && extra){
			E *i2 = extra->find(temp);
			if(i2 < exbegin || i2 == extra->end)return i1 - 1;
			return i2;
		}
		if(i1 == end)return i1 - 1;
		if(i1 < begin)return 0;
		return i1;
	}
}L[maxn];

int N, M, X0, Si, Xi;
typedef long double LLD;
typedef iter(set<V>) it_S;

inline void setdis(V &n, it_S &a, it_S &b){
	int disa = abs(n.H - a->H), disb = abs(n.H - b->H);
	if(disa < disb){//小A选b,小B选a
		n.son[1] = a->id;n.son[0] = b->id;
		n.dis[1][0] = a->dis[0][0], n.dis[0][1] = b->dis[1][1];
		n.dis[1][1] = a->dis[0][1] + disa;
		n.dis[0][0] = b->dis[1][0] + disb;
		n.len[0] = b->len[1] + 1;
		n.len[1] = a->len[0] + 1;
	}
	else {
		n.son[1] = b->id;n.son[0] = a->id;
		n.dis[1][0] = b->dis[0][0], n.dis[0][1] = a->dis[1][1];
		n.dis[1][1] = b->dis[0][1] + disb;
		n.dis[0][0] = a->dis[1][0] + disa;
		n.len[0] = a->len[1] + 1;
		n.len[1] = b->len[0] + 1;
	}
	n.S = n.dis[0][0] + n.dis[0][1];
}

const LLD eps = (LLD)1e-5;
LL Mina = 0x7fffffffffffffffLL, Maxb = 0;

inline void ask1(){
	int i, S, ans = 0;
	bool AB;
	LL a, b;
	E *tmp;
	for(i = 1;i <= N;++i){
		S = Node[i].S - X0;
		tmp = L[i].find(S);
		AB = (Node[i].len[0] - tmp->len) & 1;
		a = Node[i].dis[0][0] - tmp->dis[0];
		b = Node[i].dis[0][1] - tmp->dis[1];
		if(!Maxb){
			if(Maxb == b){
				if(!ans || Node[i].H > Node[ans].H)
					ans = i;
				continue;
			}
			Mina = a, Maxb = b, ans = i;
		}
		else if(b){
			if(a / b - Mina / Maxb > eps)
				Mina = a, Maxb = b, ans = i;
		}
	}
	fprintf(out, "%d\n", ans);
}

inline void ask2(){
	LL S = Node[Si].S - Xi;
	E *tmp = L[Si].find(S);
	putLL(Node[Si].dis[0][0] - tmp->dis[0]);
	putLL(Node[Si].dis[0][1] - tmp->dis[1]);
	fputc('\n', out);
}

inline void init(){
	int i;
	for(i = 1;i <= N;++i)
		getint(Node[i].H), Node[i].id = i;
	set<V> SET;
	it_S it1, it2;
	Node[N].id = N, Node[N-1].id = N-1;
	Node[N].len[0] = Node[N].len[1] = Node[N-1].len[0] = 1;
	Node[N-1].len[1] = 2;
	Node[N-1].son[1] = 1;
	Node[N-1].S = Node[N-1].dis[1][1] = abs(Node[N].H - Node[N-1].H);
	Node[N-1].son[1] = N;
	SET.insert(Node[N]), SET.insert(Node[N-1]);
	for(i = N-2;i;--i){
		it1 = SET.lower_bound(Node[i]);
		it2 = it1--;
		if(it1 == SET.end())it1 = it2++;
		else if(it2 == SET.end())it2 = it1--;
		setdis(Node[i], it1, it2);
		SET.insert(Node[i]);
	}
	for(i = N;i;--i)
		L[i].init(L, i);
}

int main(){
	getint(N);
	init();
	getint(X0);getint(M);
	ask1();
	while(M--){
		getint(Si), getint(Xi);
		ask2();
	}
	#if defined DEBUG
	cout << endl << (double)clock() / CLOCKS_PER_SEC << endl;
	#endif
	return 0;
}