LRUD Instructions

AtCoder

IDabc273_d

Time3000ms

Memory256MB

Difficulty—

There is a grid with $H$ horizontal rows and $W$ vertical columns. $(i, j)$ denotes the square at the $i$\-th row from the top and $j$\-th column from the left. $N$ squares, $(r_1, c_1), (r_2, c_2), \ldots, (r_N, c_N)$, have walls. Takahashi is initially at square $(r_\mathrm{s}, c_\mathrm{s})$. $Q$ instructions are given to Takahashi. For $i = 1, 2, \ldots, Q$, the $i$\-th instruction is represented by a pair of a character $d_i$ and a positive integer $l_i$. $d_i$ is one of `L`, `R`, `U`, and `D`, representing the directions of left, right, up, and down, respectively. Given the $i$\-th direction, Takahashi repeats the following action $l_i$ times: > If a square without a wall is adjacent to the current square in the direction represented by $d_i$, move to that square; otherwise, do nothing. For $i = 1, 2, \ldots, Q$, print the square where Takahashi will be after he follows the first $i$ instructions. ## Constraints * $2 \leq H, W \leq 10^9$ * $1 \leq r_\mathrm{s} \leq H$ * $1 \leq c_\mathrm{s} \leq W$ * $0 \leq N \leq 2 \times 10^5$ * $1 \leq r_i \leq H$ * $1 \leq c_i \leq W$ * $i \neq j \Rightarrow (r_i, c_i) \neq (r_j, c_j)$ * $(r_\mathrm{s}, c_\mathrm{s}) \neq (r_i, c_i)$ for all $i = 1, 2, \ldots, N$. * $1 \leq Q \leq 2 \times 10^5$ * $d_i$ is one of the characters `L`, `R`, `U`, and `D`. * $1 \leq l_i \leq 10^9$ * All values in the input other than $d_i$ are integers. ## Input The input is given from Standard Input in the following format: $H$ $W$ $r_\mathrm{s}$ $c_\mathrm{s}$ $N$ $r_1$ $c_1$ $r_2$ $c_2$ $\vdots$ $r_N$ $c_N$ $Q$ $d_1$ $l_1$ $d_2$ $l_2$ $\vdots$ $d_Q$ $l_Q$ [samples]

Samples

Input #1

Output #1

4 2
3 2
3 1
3 5

The given grid and the initial position of Takahashi are as follows, where `#` denotes a square with a wall, `T` a square where Takahashi is, and `.` the other squares:

...#.
.#...
.....
...T.
..#..

Given the $1$\-st instruction, Takahashi moves $2$ squares to the left, ending up in square $(4, 2)$ as follows:

...#.
.#...
.....
.T...
..#..

Given the $2$\-nd instruction, Takahashi first moves $1$ square upward, then he "does nothing" twice because the adjacent square in his direction has a wall. As a result, he ends up in square $(3, 2)$ as follows:

...#.
.#...
.T...
.....
..#..

Given the $3$\-rd instruction, Takahashi first moves $1$ square to the left, then he "does nothing" once because there is no square in his direction. As a result, he ends up in square $(3, 1)$ as follows:

...#.
.#...
T....
.....
..#..

Given the $4$\-th instruction, Takahashi moves $4$ squares to the right, ending up in square $(3, 5)$ as follows:

...#.
.#...
....T
.....
..#..

Input #2

Output #2

API Response (JSON)

{
  "problem": {
    "name": "LRUD Instructions",
    "description": {
      "content": "There is a grid with $H$ horizontal rows and $W$ vertical columns. $(i, j)$ denotes the square at the $i$\\-th row from the top and $j$\\-th column from the left.   $N$ squares, $(r_1, c_1), (r_2, c_2),",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 3000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "abc273_d"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "There is a grid with $H$ horizontal rows and $W$ vertical columns. $(i, j)$ denotes the square at the $i$\\-th row from the top and $j$\\-th column from the left.  \n$N$ squares, $(r_1, c_1), (r_2, c_2),...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments