记录编号	262888	评测结果	AAAAAAAAAAAA
题目名称	1986.[USACO Mar09] 向右看齐	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	0.098 s
提交时间	2016-05-21 22:07:28	内存使用	11.73 MiB

#include<cstdio>
#include<algorithm>
using namespace std;

const int maxl=1000010;
int h[maxl],ans[maxl],n,i,j,q[maxl],head,tail;

int find(int x,int l,int r){
	if (l==r) return q[l];
	int m=(l+r)/2;
	if (h[q[m+1]]>x) return find(x,m+1,r);
		else return find(x,l,m);
}

int main()
{
	freopen("lookup.in","r",stdin);
	freopen("lookup.out","w",stdout);
	scanf("%d",&n);
	for (i=1;i<=n;i++) scanf("%d",&h[i]);
	head=1;tail=0;
	for (i=n;i>0;i--){
		ans[i]=(h[i]<h[q[head]]?find(h[i],head,tail):0);
		for (;head<=tail&&h[i]>=h[q[tail]];tail--);
		q[++tail]=i;
	}
	for (i=1;i<=n;i++) printf("%d\n",ans[i]);
	return 0;
}