Adjusting a Rectangle

AtCoder

IDarc209_c

Time3000ms

Memory256MB

Difficulty—

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$ [samples]

Samples

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

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$.

API Response (JSON)

{
  "problem": {
    "name": "Adjusting a Rectangle",
    "description": {
      "content": "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$ querie",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 3000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "arc209_c"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "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$.\nYou are given $Q$ querie...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments