分数: 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