{"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$ queries. In each query, you are given integers $l, r$ satisfying $1 \\leq l \\leq r \\leq N$, and you play the following game:\n\n*   Initially, your score is $0$, and integers $a, b$ are initialized as $a = 1, b = 1$.\n*   For $i = l, l+1, \\dots, r$ in this order, perform the following operation:\n    *   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).\n    *   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.\n\nFor each query, find the maximum possible value of your score when the game ends.\n\n## Constraints\n\n*   $1 \\le N, X, Q \\le 10^5$\n*   $1 \\le S_i \\le 10^5$\n*   $P_i = 1$ or $P_i = -1$.\n*   For each query, $1 \\le l \\le r \\le N$.\n*   All input values are integers.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$N$ $X$ $Q$\n$S_1$ $S_2$ $\\ldots$ $S_N$\n$P_1$ $P_2$ $\\ldots$ $P_N$\n$\\text{query}_1$\n$\\text{query}_2$\n$\\vdots$\n$\\text{query}_Q$\n\nEach query is given in the following format:\n\n$l$ $r$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc209_c","tags":[],"sample_group":[["9 4 4\n3 11 10 12 5 7 3 9 16\n1 1 -1 1 -1 1 -1 1 1\n5 9\n1 4\n5 5\n2 8","2\n3\n0\n1\n\nIn the first query, you can make the score $2$ when the game ends by the following procedure:\n\n$i$\n\nOperation\n\n$a$\n\n$b$\n\nScore\n\n\\-\n\n$1$\n\n$1$\n\n$0$\n\n$5$\n\nReplace the value of $b$ with $4$. Since $ab < S_5 \\, (= 5)$, the score does not change.\n\n$1$\n\n$4$\n\n$0$\n\n$6$\n\nReplace the value of $a$ with $2$. Since $ab \\geq S_6 \\, (= 7)$, add $P_6 \\, (= 1)$ to the score.\n\n$2$\n\n$4$\n\n$1$\n\n$7$\n\nReplace the value of $b$ with $3$. Since $ab \\geq S_7 \\, (= 3)$, add $P_7 \\, (= -1)$ to the score.\n\n$2$\n\n$3$\n\n$0$\n\n$8$\n\nReplace the value of $a$ with $4$. Since $ab \\geq S_8 \\, (= 9)$, add $P_8 \\, (= 1)$ to the score.\n\n$4$\n\n$3$\n\n$1$\n\n$9$\n\nReplace the value of $b$ with $4$. Since $ab \\geq S_9 \\, (= 16)$, add $P_9 \\, (= 1)$ to the score.\n\n$4$\n\n$4$\n\n$2$\n\nIt is impossible to make the score $3$ or more when the game ends, so output $2$."]],"created_at":"2026-03-03 11:01:14"}}