← 返回题目列表

AtCoder · awc0106_d

D. 山脉景观

中文机器翻译题面 查看原题

分数: 400 分

问题陈述

高桥的爱好是拍摄山脉照片。

高桥面前,有 N 山脉排成一排,编号从 1 to N.

的 树的 i第一座山的海拔为 A_i 和一个美丽的 B_i.

当云在高处水平扩展时 X,仅具有海拔的山脉 X 或更高(即山脉 i 满意 A_i \geq X)出现在云层上方并且高桥可见。

高桥将可见的山脉数字集划分为连续数字的最大间隔(连续间隔,不能在两端进一步扩展),并将每个间隔拍摄为 山脉.

每一座山脉,最大的美丽 B_i 该范围内的山脉被定义为 查看值 那个山脉的 。

所有山脉的视野值之和称为 总观看价值 在云高度 X.

例如,如果可见的山脉编号是 2, 3, 4, 7, 8,那么有 2 山脉: \{2, 3, 4\} 和 \{7, 8\}.

总观看价值为 \max(B_2, B_3, B_4) + \max(B_7, B_8).

如果看不到山脉,则总视图值为 0.

你被给予 Q 查询。

在 j-th 查询,您将获得云高度 X_j。确定当时的总观看价值。

约束

  • 1 \leq N
  • 1 \leq Q
  • N + Q \leq 2 \times 10^5
  • 1 \leq A_i \leq 10^9 (1 \leq i \leq N)
  • 1 \leq B_i \leq 10^9 (1 \leq i \leq N)
  • 1 \leq X_j \leq 10^9 (1 \leq j \leq Q)
  • 所有输入均为整数

输入

N Q
A_1 B_1
A_2 B_2
\vdots
A_N B_N
X_1
X_2
\vdots
X_Q
  • 第一行包含 N,山脉数量,以及 Q,查询数量,以空格分隔。
  • 以下 N 行各包含, i第线,海拔 A_i 和美丽 B_i 的 i第一座山,相隔一个空格。
  • 以下 Q 行各包含, j第线,云高 X_j 为 j第一个查询。

输出

输出 Q 行。

关于 j第行,输出云高为时的总观看值 X_j.


示例输入 1

8 4
1 3
5 10
6 2
5 7
2 100
1 6
7 4
7 9
5
7
1
8

示例输出 1

19
9
100
0

示例输入 2

5 6
3 8
3 1
1 10
4 5
2 7
4
3
2
1
5
3

示例输出 2

5
13
15
10
0
13

示例输入 3

15 8
10 5
4 20
8 15
6 30
3 25
9 10
9 40
2 35
7 12
5 50
11 8
1 45
6 18
10 22
4 28
6
9
1
12
5
10
3
8

示例输出 3

117
75
50
0
147
35
118
90

示例输入 4

40 15
1 1000000000
1000000000 1
500000000 700
750000000 900
250000000 800
600000000 1200
600000000 1100
100 5000
999999999 300
400000000 400
800000000 2000
200000000 50
300000000 60
700000000 70
700000001 80
123456789 90
987654321 100
111111111 110
222222222 220
333333333 330
444444444 440
555555555 550
666666666 660
777777777 770
888888888 880
999999998 990
135791357 135
246802468 246
357913579 357
468024680 468
579135791 579
680246802 680
791357913 791
802468024 802
913579135 913
24 24
42 42
314159265 314
271828182 271
161803398 161
1
100
1000000000
999999999
800000000
700000000
600000000
500000000
400000000
300000000
200000000
123456789
50
100000001
900000000

示例输出 4

1000000000
5314
1
301
4304
5284
6484
6483
6183
6497
5517
4504
5314
3514
2304

示例输入 5

1 1
1 1000000000
1000000000

示例输出 5

0