← 返回题目列表

AtCoder · awc0039_e

E. 图书馆图书搜索

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

分数: 466 分

问题陈述

高桥是某图书馆的图书管理员。这个图书馆有 N 架子,每个架子编号为 1 to N.

图书馆拥有 M 其收藏中的书籍。多本书可以放在同一个书架上。对于每本书 i (1 \leq i \leq M),货架号 S_i 书籍的放置位置及其页数 记录了 D_i 。

Aoki 是一名图书馆用户。青木表演 Q 搜索。对于每个搜索 j (1 \leq j \leq Q),他指定一个货架编号范围 [L_j, R_j] 和最小页数 T_j,并且想要查找“书架上放置的数字介于 L_j 和 R_j (含)页数至少为 T_j."

然而,图书馆的搜索系统有一个bug:搜索结果显示的图书数量是实际数量减去非负整数 K。如果结果是否定的, 而是显示 0 。

对于每次搜索,确定系统显示的值。

也就是说,让 C_j 是放置在书架上的图书数量,数字介于 L_j 和 R_j (含)且页数至少为 T_j,输出 \max(C_j - K, 0).

约束

  • 1 \leq N \leq 10^5
  • 1 \leq M \leq 10^5
  • 1 \leq Q \leq 10^5
  • 0 \leq K \leq M
  • 1 \leq S_i \leq N (1 \leq i \leq M)
  • 1 \leq D_i \leq 10^9 (1 \leq i \leq M)
  • 1 \leq L_j \leq R_j \leq N (1 \leq j \leq Q)
  • 1 \leq T_j \leq 10^9 (1 \leq j \leq Q)
  • 所有输入值均为整数。

输入

N M Q K
S_1 D_1
S_2 D_2
\vdots
S_M D_M
L_1 R_1 T_1
L_2 R_2 T_2
\vdots
L_Q R_Q T_Q
  • 第一行包含货架数量 N, 书籍数量 M,搜索次数 Q,以及非负整数 K 被系统减去,用空格分隔。
  • 的 i- 以下各项 M 行 (1 \leq i \leq M) 包含货架号 S_i 其中 i第本书已放置及其页数 D_i,用空格分隔。
  • 的 j- 以下各项 Q 行 (1 \leq j \leq Q) 包含左端点 L_j 和右端点 R_j 书架编号范围,以及最小页数 T_j 为 j第一个搜索,以空格分隔。

输出

输出 Q 行。的 j第行 (1 \leq j \leq Q) 应包含系统显示的值 j-次搜索。


示例输入 1

3 4 3 1
1 100
1 50
2 200
3 150
1 2 100
2 3 150
1 3 10

示例输出 1

1
1
3

示例输入 2

4 3 4 0
4 120
2 80
4 200
1 1 50
1 3 100
3 4 150
2 2 1

示例输出 2

0
0
1
1

示例输入 3

8 12 8 2
1 300
2 120
2 500
3 450
3 200
4 600
5 50
5 700
6 400
7 800
8 10
8 900
1 8 400
2 5 200
5 8 600
1 3 1000
4 4 1
6 8 350
3 7 750
8 8 5

示例输出 3

5
3
1
0
0
1
0
0

示例输入 4

20 30 15 3
1 100
1 500
2 250
2 800
3 150
3 900
4 400
4 50
5 1000
5 300
6 600
6 610
7 200
7 700
8 720
9 330
9 340
10 100
10 10000
11 450
12 460
12 470
13 480
14 490
15 5000
16 510
17 520
18 530
19 540
20 550
1 20 500
1 5 200
6 10 600
10 10 1000
11 15 460
16 20 525
3 7 700
8 12 50
13 17 480
2 2 1
4 9 1000
15 15 4999
1 20 10001
9 14 335
5 16 510

示例输出 4

12
4
2
0
2
0
0
5
2
0
0
0
0
4
5

示例输入 5

1 1 5 1
1 1000000000
1 1 1
1 1 999999999
1 1 1000000000
1 1 1000000000
1 1 1000000000

示例输出 5

0
0
0
0
0