Difference Sum Query

AtCoder

IDarc159_e

Time4000ms

Memory256MB

Difficulty—

You are given a positive integer $N$, and $M$ pairs of positive integers: $(a_0,b_0),\ldots,(a_{M-1},b_{M-1})$ (note that $a_i$ and $b_i$ start with index $0$). We have the following sequence of non-negative integers $X=(x_1,\ldots,x_N)$. * $x_i$ is determined as follows. 1. Let $l=1$, $r=N$, and $t=0$. 2. Let $m=\left \lfloor \dfrac{a_{t \bmod M} \times l + b_{t \bmod M} \times r}{a_{t \bmod M} +b_{t \bmod M}} \right \rfloor $ ($\lfloor x \rfloor$ is the greatest integer not exceeding $x$). If $m=i$, let $x_i=t$ and terminate. 3. If $l \leq i \lt m$, let $r=m-1$; otherwise, let $l=m+1$. Increment $t$ by $1$ and return to step 2. Find $\sum_{j=c_i}^{d_i-1} |x_j - x_{j+1}|$ for $i=1,2,\ldots,Q$. It can be proved that the answers are at most $10^{18}$ under the constraints of this problem. ## Constraints * $2 \leq N \leq 10^{15}$ * $1 \leq M \leq 100$ * $1 \leq a_i,b_i \leq 1000$ * $\max \left (\dfrac{a_i}{b_i},\dfrac{b_i}{a_i}\right ) \leq 2$ * $1 \leq Q \leq 10^4$ * $1 \leq c_i \lt d_i \leq N$ * All values in the input are integers. ## Input The input is given from Standard Input in the following format: $N$ $M$ $a_0$ $b_0$ $\vdots$ $a_{M-1}$ $b_{M-1}$ $Q$ $c_1$ $d_1$ $\vdots$ $c_Q$ $d_Q$ [samples]

Samples

Input #1

Output #1

1
3
2

We have $X=(1,2,0,1,2)$. For example, $x_1$ is determined as follows.

*   Let $l=1$, $r=5(=N)$, and $t=0$.
*   Let $m=3(=\left \lfloor \dfrac{1 \times 1 + 1 \times 5}{1+1} \right \rfloor)$.
*   Since $l \leq 1 \lt m$, let $r=2(=m-1)$. Increment $t$ by $1$ to $1$.
*   Let $m=1(= \left \lfloor \dfrac{1 \times 1 + 1 \times 2}{1+1} \right \rfloor )$. Since $m=1$, let $x_1=1(=t)$ and terminate.

The answer to the question for $(c_1,d_1)$, for example, is $\sum_{j=c_i}^{d_i-1} |x_j - x_{j+1}| = |x_1-x_2| = 1$.

Input #2

1000000000000000 2
15 9
9 15
3
100 10000
5000 385723875
150 17095708

Output #2

19792
771437738
34191100

API Response (JSON)

{
  "problem": {
    "name": "Difference Sum Query",
    "description": {
      "content": "You are given a positive integer $N$, and $M$ pairs of positive integers: $(a_0,b_0),\\ldots,(a_{M-1},b_{M-1})$ (note that $a_i$ and $b_i$ start with index $0$). We have the following sequence of non-n",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 4000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "arc159_e"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given a positive integer $N$, and $M$ pairs of positive integers: $(a_0,b_0),\\ldots,(a_{M-1},b_{M-1})$ (note that $a_i$ and $b_i$ start with index $0$).\nWe have the following sequence of non-n...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments