Problem B
Absolute Cinema
Languages
en
sv
Winston works at the cinema “Absolute Cinema”, the peak cinema in the entire country. The auditorium has $N$ numbered seats, and Winston’s job is to keep exact track of which seats are available and which are already taken.
At the start of the day all seats are available. During the day, $Q$ events occur. Visitors line up and shout various requests to Winston.
Winston does not have much time, so he must answer quickly and correctly.
When a visitor says: “I want to sit at seat $i$”, Winston checks the system:
-
If seat $i$ is available, Winston replies “Ledig” (Swedish word for Available) and marks it as taken.
-
Otherwise Winston replies “Upptagen” (Swedish word for Occupied).
When a visitor says: “I want to move from seat $i$ to seat $j$”, Winston first checks seat $j$:
-
If seat $j$ is occupied, Winston replies “Upptagen” and nothing changes.
-
If seat $j$ is available, Winston moves the person: seat $i$ becomes available and seat $j$ becomes taken, and he replies “Ledig”.
After each request Winston must always report whether the relevant seat is available or not. This is how Absolute Cinema keeps its peak order, and it is thanks to Winston that the cinema runs so well.
Input
The input consists of two integers $N$ ($1 \le N \le 10^{9}$) and $Q$ ($1 \le Q \le 2 \cdot 10^{5}$), the number of seats in the auditorium and the number of events. All $N$ seats are initially available.
Then follow $Q$ lines describing events. Each line has one of the following formats:
-
1 i, a visitor wants to sit at seat $i$ $(1 \le i \le N)$.
-
2 i j, a visitor at seat $i$ wants to move to seat $j$ $(1 \le i, j \le N, i \ne j)$. For each such query it is guaranteed that seat $i$ is occupied.
Output
For each event, print exactly one line:
-
Print Ledig if the target seat was available (and perform the change).
-
Otherwise print Upptagen.
Scoring
Your solution will be tested on a set of test groups, each worth a number of points. Each test group contains a set of test cases. To get the points for a test group you need to solve all test cases in the test group.
|
Group |
Points |
Constraints |
|
$1$ |
$15$ |
$Q \le 10^3, N \le 10^4$ |
|
$2$ |
$25$ |
$N \le 10^4$ |
|
$3$ |
$20$ |
No move requests will occur. |
|
$4$ |
$40$ |
No additional constraints. |
Explanation of Sample 1
In the first example, there are $5$ seats and $3$ events:
-
A visitor wants to sit in seat $1$. Seat $1$ is free, so Winston replies “Ledig”.
-
A visitor wants to sit in seat $3$. Seat $3$ is free, so Winston replies “Ledig”.
-
A visitor wants to sit in seat $3$. Seat $3$ is occupied, so Winston replies “Upptagen”.
Explanation of Sample 2
In the second example, there are $5$ seats and $3$ events:
-
A visitor wants to sit in seat $1$. Seat $1$ is free, so Winston replies “Ledig”.
-
A visitor in seat $1$ wants to move to seat $2$. Seat $2$ is free, so Winston moves the person and replies “Ledig”.
-
A visitor wants to sit in seat $1$. Seat $1$ is free (since the previous visitor moved), so Winston replies “Ledig”.
| Sample Input 1 | Sample Output 1 |
|---|---|
5 3 1 1 1 3 1 3 |
Ledig Ledig Upptagen |
| Sample Input 2 | Sample Output 2 |
|---|---|
5 3 1 1 2 1 2 1 1 |
Ledig Ledig Ledig |
| Sample Input 3 | Sample Output 3 |
|---|---|
10 6 1 2 1 3 1 6 2 6 7 1 10 1 7 |
Ledig Ledig Ledig Ledig Ledig Upptagen |
| Sample Input 4 | Sample Output 4 |
|---|---|
100 10 1 14 1 51 1 93 1 9 1 52 2 9 93 1 14 2 14 93 1 22 2 51 14 |
Ledig Ledig Ledig Ledig Ledig Upptagen Upptagen Upptagen Ledig Upptagen |
