UOJ Logo 黑暗爆炸OJ

DARKBZOJ

#4979. [Lydsy1708月赛]凌晨三点的宿舍

Statistics 下载数据

Description

小Q所在的学校QNU(Quailty Niubi University)的学生公寓由n栋楼组成,这些楼从左往右连成一排,编号依次为1
到n,其中第i栋楼有h_i层。现在已经凌晨三点了,但是小Q和他的队友们仍然在刻苦地刷题,从他们房间窗户透出
的亮光格外醒目。
这时,辛苦了一晚上的小Q饿了,正当他拆完泡面准备倒水的时候,他发现热水壶放在队友那忘记拿回来了。无奈
之下,他只好走路去向队友要回热水壶。在学生公寓里,小Q每分钟可以选择上楼或者下楼,或者往左往右移动到
相邻的房间外面的过道上。因为夜晚的门禁,他不能走出公寓,同时,他也不能登上天台思考人生。你可以认为从
房间到过道不需要任何时间。饥饿的小Q最多只能坚持走k分钟,再之后他就会因为饥饿而昏倒。他历尽艰险终于从
队友那拿回了热水壶,解决了燃眉之急。这时,吃着泡面的小Q开始思考一个问题:如果他和队友的房间距离并没
有那么近,那么他就不会这么走运了。于是现在他想知道有多少对队友的房间之间的最短路程不超过k分钟。小Q正
在吃泡面,于是他把这个问题交给了你。请写一个程序帮助小Q解决这个现实问题。

Input

第一行包含两个正整数n,k(1<=n<=200000,1<=k<=400000),分别表示宿舍楼的数量以及路程的上限。
第二行包含n个正整数h_1,h_2,...,h_n(1<=h_i<=200000),分别表示每栋楼的层数。
接下来一行包含一个正整数m(1<=m<=200000),表示亮着灯的房间个数。
接下来m行,每行两个正整数x_i,y_i(1<=x_i<=n,1<=y_i<=h_{x_i}),表示这个房间位于x_i号楼的第y_i层。
输入数据保证m个房间不会重复输入。

Output

输出一行一个整数,即最短路程不超过k的房间对数。

Sample Input

5 7
4 1 1 3 1
3
1 4
3 1
4 3

Sample Output

2
HINT
样例对应题目描述中的图,房间1和房间3之间的距离为8>7,因此不能计入答案。

Hint

Source

claris原创,本oj版权所有,翻版必究