루미 알고리즘

#1646골드Absolute Cinema

PO 2026 온라인 예선코딩출제 Harry Zhang영어 원문이 문제가 어렵다면 — 배우는 순서 보기

영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)

Problem

(그림은 원문 저장소에서 볼 수 있습니다)

cc by-sa

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 ≤ N ≤ 10^9) and Q (1 ≤ Q ≤ 2 · 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 ≤ i ≤ N).
  • 2 i j, a visitor at seat i wants to move to seat j (1 ≤ i, j ≤ N, i ≠ 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. To earn points for a group, you must pass all test cases in that group.

GroupPointsConstraints
115Q ≤ 10^3, N ≤ 10^4
225N ≤ 10^4
320No move requests will occur.
440No 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”.

예제

예제 1

입력
5 3
1 1
1 3
1 3
출력
Ledig
Ledig
Upptagen

예제 2

입력
5 3
1 1
2 1 2
1 1
출력
Ledig
Ledig
Ledig

예제 3

입력
10 6
1 2
1 3
1 6
2 6 7
1 10
1 7
출력
Ledig
Ledig
Ledig
Ledig
Ledig
Upptagen

예제 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

출처 표기

출처: Programmeringsolympiaden 2026년 온라인 예선 · 원문 페이지 · 이용 조건 CC BY-SA · LaTeX 원문을 화면용 글로 옮겼습니다(수식·표의 모양이 다를 수 있습니다). 내용은 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-동일조건변경허락.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.