← 返回题目列表

AtCoder · awc0100_k

K. 选择购物街的街区

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

分数: 466 分

问题陈述

高桥正计划租用商业街的连续路段来设立活动场地。

商店街有 N 部分从左到右排成一排。

租金 i左起第节 (1 \leq i \leq N) is A_i 日元。

另外,对于 i左起第节, C_i = 1 如果有停车位,并且 C_i = 0 如果没有。

高桥正在考虑租房 K 连续部分。

也就是说,他选择一个整数 l (1 \leq l \leq N-K+1) 并租用 K 部分 l-第 (l+K-1)从左起第一个。

Q 操作将按顺序执行。的 j第次操作 (1 \leq j \leq Q) 由整数确定 T_j 并且是以下之一:

  • T_j = 1 (租金变化):整数 给出了 X_j, Y_j 。改变租金 X_j从左到右的第节 Y_j 日元。此更改会影响所有后续操作。
  • T_j = 2 (查询):整数 给出了 X_j 。在所有方法中准确选择 K 连续的部分,考虑那些选择的 K 部分至少包含 X_j 有停车位的路段(有停车位的路段) C_i = 1)。如果存在这样的选择,则输出所选选项的最小可能总租金 K 部分。如果不存在这样的选择,则输出 IMPOSSIBLE.

请注意这些值 C_i 代表停车位的存在或不存在,不会通过操作而改变。

对于每个操作 T_j = 2,输出答案。

约束

  • 1 \leq K \leq N \leq 10^5
  • 1 \leq Q \leq 5 \times 10^4
  • 1 \leq A_i \leq 10^9
  • C_i \in \{0, 1\}
  • T_j \in \{1, 2\}
  • 当 T_j = 1: 1 \leq X_j \leq N, 1 \leq Y_j \leq 10^9
  • 当 T_j = 2: 0 \leq X_j \leq K, Y_j = 0
  • 至少有一项操作 T_j = 2
  • 所有输入均为整数

输入

N K Q
A_1 A_2 \cdots A_N
C_1 C_2 \cdots C_N
T_1 X_1 Y_1
T_2 X_2 Y_2
\vdots
T_Q X_Q Y_Q

每个操作都以整数三元组的形式给出 (T_j, X_j, Y_j)。当 给出了 T_j = 2, Y_j = 0 ,但这只是为了统一输入格式,并没有在解决方案中使用。

输出

对于每个操作 T_j = 2,如果有效选择,则在单行上输出最低总租金 K 存在满足条件的连续部分,或者 IMPOSSIBLE 如果不存在这样的选择。


示例输入 1

5 3 5
10 20 5 7 8
1 0 1 0 1
2 1 0
2 2 0
1 2 1
2 1 0
2 2 0

示例输出 1

20
20
13
16

示例输入 2

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

示例输出 2

IMPOSSIBLE
IMPOSSIBLE

示例输入 3

12 4 10
15 3 22 8 7 13 5 19 11 2 17 6
1 0 1 1 0 0 1 0 1 1 0 1
2 2 0
2 3 0
1 5 4
2 2 0
1 10 20
2 1 0
1 1 30
2 4 0
1 8 1
2 3 0

示例输出 3

33
36
30
30
IMPOSSIBLE
37

示例输入 4

25 7 20
31 12 45 7 23 18 60 5 14 39 27 8 50 16 22 41 9 33 11 28 6 19 35 24 10
1 0 0 1 1 0 1 0 1 0 0 1 1 0 1 0 1 1 0 0 1 0 1 0 1
2 3 0
2 5 0
1 7 4
2 4 0
1 14 3
2 2 0
1 1 100
2 5 0
1 20 2
2 1 0
1 25 70
2 6 0
1 12 1
2 4 0
1 18 55
2 3 0
1 9 40
2 0 0
1 4 9
2 5 0

示例输出 4

133
179
110
110
166
107
IMPOSSIBLE
110
108
114
181

示例输入 5

1 1 5
1000000000
0
2 0 0
2 1 0
1 1 1
2 0 0
2 1 0

示例输出 5

1000000000
IMPOSSIBLE
1
IMPOSSIBLE