Can't See the Blackboard

发布时间: 2018年8月14日 17:33   最后更新: 2018年8月14日 17:36   时间限制: 2000ms   内存限制: 256M

一天,OneDay在一个奇怪的教室上课,这个教室的座位排成竖着的一排,第$1$个同学坐最后面,第$n$个同学坐最前面,黑板在第$n$个同学的前面,并且相邻两个座位距离为$1$。

OneDay坐在中间,但是前面有一位身高严格比OneDay高的同学后脑勺挡住了他的视线。OneDay想知道,每位同学眼睛平视,能看到谁的后脑勺,或者能看到黑板。

第一行是一个整数$T$,表示测试数据的组数。
对于每组测试数据:
第一行是一个整数$n$,表示同学的人数。
第二行是$n$个整数$h_1,h_2,\ldots,h_n$,代表第$i$个同学坐到位置上的身高。
$T \leq 10$
$1 \le n \le 10 ^ {6}$
$1 \le h_i \le 10 ^ {5}$
$\sum n \le 2 \times 10 ^ {6}$

对于每组测试数据,在一行内输出$n$个整数(两个数之间用空格间开,行末无空格),第$i$个整数表示第$i$个同学眼睛平视,看到的后脑勺他有多远,如果他能看到黑板,请输出$0$。

复制
2
8
73 74 75 71 69 72 76 73
5
5 3 1 4 2
1 1 4 2 1 1 0 0
0 2 1 0 0

我们认为$a$同学看到的是$b$同学的后脑勺,当且仅当$b$同学坐在$a$同学前面且$b$同学的身高严格大于$a$同学。

data structure

ACM集训队暑期集训新生组队赛