C - Adjusting a Rectangle Editorial /

Time Limit: 3 sec / Memory Limit: 1024 MiB

配点 : 900 点

問題文

正の整数 N, X および長さ N の整数列 S = (S_1, S_2, \dots, S_N), P = (P_1, P_2, \dots, P_N) が与えられます。 ここで、P の各要素は 1 または -1 です。

クエリが Q 個与えられます。各クエリでは、1 \leq l \leq r \leq N を満たす整数 l, r が与えられ、あなたは以下のようなゲームを行います。

  • はじめ、あなたのスコアは 0 であり、整数 a, b が a = 1, b = 1 で初期化されている。
  • i = l, l+1, \dots, r の順に、以下の操作を行う。
    • i が偶数のときは a の値、i が奇数のときは b の値を、1 以上 X 以下の好きな整数に置き換える。
    • その後、ab \geq S_i ならあなたのスコアに P_i を加算する。そうでないとき、スコアは変動しない。P_i は負の値も取り得ることに注意せよ。

各クエリに対して、ゲームが終了した時点でのあなたのスコアとしてあり得る最大値を求めてください。

制約

  • 1 \le N, X, Q \le 10^5
  • 1 \le S_i \le 10^5
  • P_i = 1 または P_i = -1
  • 各クエリに対して 1 \le l \le r \le N
  • 入力される値は全て整数

入力

入力は以下の形式で標準入力から与えられる。

N X Q
S_1 S_2 \ldots S_N
P_1 P_2 \ldots P_N
\text{query}_1
\text{query}_2
\vdots
\text{query}_Q

各クエリは以下の形式で与えられる。

l r

出力

Q 行出力せよ。

i 行目には、i 番目のクエリにおいて、ゲームが終了した時点でのあなたのスコアとしてあり得る最大値を出力せよ。

入力例 1

9 4 4
3 11 10 12 5 7 3 9 16
1 1 -1 1 -1 1 -1 1 1
5 9
1 4
5 5
2 8

出力例 1

2
3
0
1

1 番目のクエリにおいて、以下の手順によってゲームが終了した時点でのスコアを 2 にすることができます。

i 操作 a b スコア
- 1 1 0
5 b の値を 4 に置き換える。ab < S_5 \, (= 5) のためスコアは変動しない。 1 4 0
6 a の値を 2 に置き換える。ab \geq S_6 \, (= 7) のためスコアに P_6 \, (= 1) を加算する。 2 4 1
7 b の値を 3 に置き換える。ab \geq S_7 \, (= 3) のためスコアに P_7 \, (= -1) を加算する。 2 3 0
8 a の値を 4 に置き換える。ab \geq S_8 \, (= 9) のためスコアに P_8 \, (= 1) を加算する。 4 3 1
9 b の値を 4 に置き換える。ab \geq S_9 \, (= 16) のためスコアに P_9 \, (= 1) を加算する。 4 4 2

ゲームが終了した時点でのスコアを 3 以上にすることはできないので、2 を出力します。

Score : 900 points

Problem Statement

You are given positive integers N, X and integer sequences of length N: S = (S_1, S_2, \dots, S_N), P = (P_1, P_2, \dots, P_N). Here, each element of P is 1 or -1.

You are given Q queries. In each query, you are given integers l, r satisfying 1 \leq l \leq r \leq N, and you play the following game:

  • Initially, your score is 0, and integers a, b are initialized as a = 1, b = 1.
  • For i = l, l+1, \dots, r in this order, perform the following operation:
    • If i is even, replace the value of a with any integer between 1 and X (inclusive); if i is odd, replace the value of b with any integer between 1 and X (inclusive).
    • After that, if ab \geq S_i, add P_i to your score. Otherwise, the score does not change. Note that P_i can be negative.

For each query, find the maximum possible value of your score when the game ends.

Constraints

  • 1 \le N, X, Q \le 10^5
  • 1 \le S_i \le 10^5
  • P_i = 1 or P_i = -1.
  • For each query, 1 \le l \le r \le N.
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N X Q
S_1 S_2 \ldots S_N
P_1 P_2 \ldots P_N
\text{query}_1
\text{query}_2
\vdots
\text{query}_Q

Each query is given in the following format:

l r

Output

Output Q lines.

The i-th line should contain the maximum possible value of your score when the game ends in the i-th query.

Sample Input 1

9 4 4
3 11 10 12 5 7 3 9 16
1 1 -1 1 -1 1 -1 1 1
5 9
1 4
5 5
2 8

Sample Output 1

2
3
0
1

In the first query, you can make the score 2 when the game ends by the following procedure:

i Operation a b Score
- 1 1 0
5 Replace the value of b with 4. Since ab < S_5 \, (= 5), the score does not change. 1 4 0
6 Replace the value of a with 2. Since ab \geq S_6 \, (= 7), add P_6 \, (= 1) to the score. 2 4 1
7 Replace the value of b with 3. Since ab \geq S_7 \, (= 3), add P_7 \, (= -1) to the score. 2 3 0
8 Replace the value of a with 4. Since ab \geq S_8 \, (= 9), add P_8 \, (= 1) to the score. 4 3 1
9 Replace the value of b with 4. Since ab \geq S_9 \, (= 16), add P_9 \, (= 1) to the score. 4 4 2

It is impossible to make the score 3 or more when the game ends, so output 2.