No.259 Segment Fishing +
タグ : / 解いたユーザー数 47
作問者 :
shimomire
Problem Statement
You go fishing in a fishing pond that is the interval $[0,N)$ of length $N$.
All fish move according to the following rules.
- A fish facing left at position $x$ at time $t$ moves to position $x−1$ at time $t+1$ without changing its direction.
However, a fish at $x = 0$ (a fish that cannot move to position $x−1$) stays at the same position and turns to face right. - Similarly, a fish facing right at position $x$ at time $t$ moves to position $x+1$ at time $t+1$ without changing its direction.
However, a fish at $x = N−1$ (a fish that cannot move to position $x+1$) stays at the same position and turns to face left.
Initially, at $t = 0$, there are no fish in the pond.
You are given $Q$ queries of the following $3$ types. Process them in order.
- 'L t y z' ー At time $t$, $z$ fish are released at position $y$ facing left. (All $z$ fish face left.)
- 'R t y z' ー At time $t$, $z$ fish are released at position $y$ facing right. (All $z$ fish face right.)
- 'C t y z' ー Output the total number of fish in the interval $[y,z)$ at time $t$.
Input
$N$ $Q$ $x_1$ $t_1$ $y_1$ $z_1$ $\cdots$ $x_i$ $t_i$ $y_i$ $z_i$ $\cdots$ $x_Q$ $t_Q$ $y_Q$ $z_Q$
The first line contains an integer $N$ ($2 \le N \le 2 \times 10^5$) representing the length of the interval and an integer $Q$ ($1 \le Q \le 8*10^4$) representing the number of queries.
The following $Q$ lines, starting from line 2, each give a query in one of the formats described in the problem statement.
The constraints on $t_i$,$x_i$,$y_i$,$z_i$ are as follows.
- $0 \le t_1 < \cdots < t_i < \cdots < t_Q \le 10^8$
- When $x_i = L$ or $x_i = R$, $0 \le y_i < N$ and $1 \le z_i \le 10^8$.
- When $x_i = C$, $0 \le y_i < z_i \le N$.
Output
For each query with $x_i = C$, output the answer, in the order the queries are given.
Print a newline after each output.
Sample
Sample 1
Input
10 3 R 1 2 1 L 2 5 1 C 3 4 5
Output
2
The movement of the fish at each time is as follows (L denotes a fish facing left, R denotes a fish facing right, {...} denotes the list of fish at that position, and - denotes that there are no fish at that position).
$t = 0$
----------
$t = 1$
--{R}-------
$t = 2$
---{R}-{L}----
$t = 3$
----{R,L}-----
Sample 2
Input
5 4 L 1 1 2 R 2 4 2 C 3 2 4 C 5 2 4
Output
0 4
The movement of the fish at each time is as follows.
$t = 0$
-----
$t = 1$
-{L,L}---
$t = 2$
{L,L}---{R,R}
$t = 3$
{R,R}---{L,L}
$t = 4$
-{R,R}-{L,L}-
$t = 5$
--{R,R,L,L}--
Sample 3
Input
10 10 C 1 3 8 L 2 1 2 R 3 7 3 C 4 1 5 C 5 0 6 L 6 2 3 R 7 3 5 C 8 2 10 R 9 7 1 L 10 6 1
Output
0 0 2 10
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。