← 返回题目列表

AtCoder · awc0076_e

E. 图书馆借阅管理

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

分数: 466 分

问题陈述

高桥在一家大型图书馆担任图书管理员。图书馆有 N 书架上排成一排,编号为书 1,书 2, \ldots,书 N 从左到右。

目前,所有书籍均已借出,书架上没有任何书籍。预定还书日期 i (1 \leq i \leq N) 是一天 D_i。预订 i 当天被退回并放回货架 D_i,并从那时起一直保留在架子上。也就是说,书 i 当天上架 T 当且仅当 D_i \leq T.

高桥收到 Q 图书馆顾客的询问。的 j- 第一个查询 (1 \leq j \leq Q) 指定一天 T_j 和一系列书号 [L_j, R_j] (包括两端)。高桥需要确定范围内的书籍数量 [L_j, R_j] 截至当日已上架 T_j。具体来说,让 c_j 为书籍数量 i 满意 L_j \leq i \leq R_j 和 D_i \leq T_j.

不过图书馆的借阅车最多可容纳 K 书籍。如果 c_j \leq K,所有书籍都可以装入购物车并借出,但如果 c_j > K,无法处理请求,因为购物车无法容纳书籍。

对于每个查询,输出 c_j if c_j \leq K,或 -1 if c_j > K.

请注意,每个查询都是独立于其他查询的。任何查询实际上都不会签出任何书籍,并且每次查询的书架上书籍的状态都是相同的。

约束

  • 1 \leq N \leq 10^5
  • 1 \leq K \leq N
  • 1 \leq Q \leq 10^5
  • 1 \leq D_i \leq 10^9 (1 \leq i \leq N)
  • 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 K Q
D_1 D_2 \ldots D_N
L_1 R_1 T_1
L_2 R_2 T_2
\vdots
L_Q R_Q T_Q
  • 第一行包含三个空格分隔的整数: N 代表图书数量, K 代表借阅车可容纳的最大图书数量,以及 Q 代表查询数量。
  • 第二行包含空格分隔的整数 D_1, D_2, \ldots, D_N 代表每本书的预定归还日期。
  • 以下 Q 行包含每个查询的信息。
  • 的 (2 + j)- 第行 (1 \leq j \leq Q) 包含三个空格分隔的值:左端点 L_j,右端点 R_j,以及查询日期 T_j 为 j-第一个查询。

输出

输出 Q 行。的 j- 第行 (1 \leq j \leq Q)应包含以下问题的答案 j- 第一个查询。具体来说,如果书籍数量 c_j 在范围内 [L_j, R_j] 满意 D_i \leq T_j 最多是 K,输出 c_j;如果超过 K,输出 -1.


示例输入 1

5 3 3
3 1 4 1 5
1 5 2
2 4 4
1 3 3

示例输出 1

2
3
2

示例输入 2

5 2 3
3 1 4 1 5
1 5 4
1 2 3
3 5 1

示例输出 2

-1
2
1

示例输入 3

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

示例输出 3

-1
3
2
-1
-1

示例输入 4

20 5 8
15 3 20 7 12 1 18 9 4 11 6 14 2 17 8 19 5 10 16 13
1 20 10
1 10 5
5 15 12
11 20 15
1 5 3
8 14 9
3 18 7
1 20 20

示例输出 4

-1
3
-1
-1
1
4
-1
-1

示例输入 5

1 1 1
1000000000
1 1 1000000000

示例输出 5

1