K - Choosing Blocks in a Shopping Street Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 466 点

問題文

高橋君は、商店街の連続する区画を借りてイベント会場を設営する計画を立てています。

商店街には N 個の区画が左から右に一列に並んでいます。

左から i 番目 (1 \leq i \leq N) の区画の賃料は A_i 円です。

また、左から i 番目の区画について、駐車スペースがあれば C_i = 1、なければ C_i = 0 です。

高橋君は、連続するちょうど K 個の区画を選んで借りることを考えています。

すなわち、ある整数 l (1 \leq l \leq N-K+1) を選び、左から l 番目から l+K-1 番目までの K 個の区画を借ります。

これから 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 個の区画に駐車スペースのある区画（C_i = 1 である区画）が X_j 個以上含まれるものを考える。そのような選び方が存在する場合は、選んだ 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 である操作が少なくとも 1 つ存在する
  • 入力はすべて整数である

入力

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

各操作は 3 つの整数の組 (T_j, X_j, Y_j) として与えられます。T_j = 2 のとき Y_j = 0 が与えられますが、これは入力形式を統一するためのもので、解答には使用しません。

出力

T_j = 2 の各操作について、条件を満たす連続する K 個の区画の選び方が存在する場合はその賃料の合計の最小値を、存在しない場合は IMPOSSIBLE を、それぞれ 1 行に出力してください。

入力例 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

Score : 466 pts

Problem Statement

Takahashi is planning to rent consecutive sections of a shopping street to set up an event venue.

The shopping street has N sections lined up in a row from left to right.

The rent for the i-th section from the left (1 \leq i \leq N) is A_i yen.

Also, for the i-th section from the left, C_i = 1 if it has a parking space, and C_i = 0 if it does not.

Takahashi is considering renting exactly K consecutive sections.

That is, he chooses an integer l (1 \leq l \leq N-K+1) and rents the K sections from the l-th to the (l+K-1)-th from the left.

Q operations will be performed in order. The j-th operation (1 \leq j \leq Q) is determined by the integer T_j and is one of the following:

  • T_j = 1 (rent change): Integers X_j, Y_j are given. Change the rent of the X_j-th section from the left to Y_j yen. This change affects all subsequent operations.
  • T_j = 2 (query): An integer X_j is given. Among all ways to choose exactly K consecutive sections, consider those where the chosen K sections contain at least X_j sections with parking spaces (sections where C_i = 1). If such a choice exists, output the minimum possible total rent of the chosen K sections. If no such choice exists, output IMPOSSIBLE.

Note that the values C_i representing the presence or absence of parking spaces do not change through operations.

For each operation with T_j = 2, output the answer.

Constraints

  • 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\}
  • When T_j = 1: 1 \leq X_j \leq N, 1 \leq Y_j \leq 10^9
  • When T_j = 2: 0 \leq X_j \leq K, Y_j = 0
  • There is at least one operation with T_j = 2
  • All inputs are integers

Input

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

Each operation is given as a triple of integers (T_j, X_j, Y_j). When T_j = 2, Y_j = 0 is given, but this is only to unify the input format and is not used in the solution.

Output

For each operation with T_j = 2, output on a single line the minimum total rent if a valid choice of K consecutive sections satisfying the condition exists, or IMPOSSIBLE if no such choice exists.

Sample Input 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

Sample Output 1

20
20
13
16

Sample Input 2

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

Sample Output 2

IMPOSSIBLE
IMPOSSIBLE

Sample Input 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

Sample Output 3

33
36
30
30
IMPOSSIBLE
37

Sample Input 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

Sample Output 4

133
179
110
110
166
107
IMPOSSIBLE
110
108
114
181

Sample Input 5

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

Sample Output 5

1000000000
IMPOSSIBLE
1
IMPOSSIBLE