루미 알고리즘

#1400다이아Friends

PO 2016 훈련 캠프코딩출제 Johan Sannemo영어 원문이 문제가 어렵다면 — 배우는 순서 보기

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

Problem

N friends are playing a game. The game is played on a row of L squares, numbered from 0 to L - 1, where squares i and i+1 are adjacent to each other. At most one friend stand on each square at any given time. In each step of the game, one friend jumps from its current square to a new (non-occupied) square.

In any moment of the game, the score of a friend is the length of the longest contiguous segment of friends it is part of. This means that if a friend stands on some position x, and there are friends on positions a, a + 1, ..., x - 1, x, x + 1, ..., b - 1, b, the score of the friend is b - a + 1.

The total score of the game is the sum of scores for all friends. At various times during the game, the friends wonder what their current total score is.

Example

Assume that we have N = 3 friends playing on a strip of length L = 7. Initially, their locations are 1, 3, 4. The score of the friend on location 1 is just 1, since it has no friends to the left or to the right. However, the friends at locations 3 and 4 make a segment of length 2, so each of their scores are 2. The score of the game is thus 1 + 2 + 2 = 5.

The first jump is from position 4 to 2, making the new positions 1, 2, 3. Here, all friends make up a segment of length 3, so each of the friends have score 3, making the total score 9.

The second and final jump is from 3 to 0, resulting in the positions 0, 1, 2. All friends still make up a segment of length 3, so the score is unchanged from last time, i.e. it is still 9.

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

Figure 1: Illustration of the example

Task

You will get all the jumps in the game, one by one. At some points, the friends will ask what the current score is. Your task is to implement the functions init(N, L, P), jump(A, B), and score():

• init(N, L, P) - this function will be called exactly once by the judge, at the start of the game.

  • N: the number of friends playing.
  • L: the number of locations the game is being played on.
  • P: an array with N elements. P[i] (0 ≤ i < N) contains the original position of the i:th friend.
  • The function has no return value.

• jump(A, B) - this function will be called once for every jump, in the order they are made.

  • A: the position a friend is jumping from (0 ≤ A < L). This position will always contain a friend at the time of the jump.
  • B: the position a friend is jumping to (0 ≤ B < L). This position will never contain a friend at the time of the jump.
  • The function has no return value.

• score() - this function will be called when the friends wish to know their current score.

  • The function should return the current score in the game.

A code skeleton containing the functions to be implemented, together with a sample grader, can be found at http://progolymp.se/uploads/kattis-attachments/friends.zip.

Subtasks

The problem consists of a number of subtasks. Each subtask gives some amount of points, and to pass the subtask you must pass all the test cases in the subtask.

Let J be the number of calls to jump and S the number of calls to score.

SubtaskPointsLimits
191 ≤ N, L ≤ 1000, S + J ≤ 2000
2171 ≤ N, L ≤ 100000, J = 0, S = 1
3141 ≤ N ≤ 100000, 1 ≤ L ≤ 10^9, J = 0, S = 1
4381 ≤ N, L ≤ 100000, S + J ≤ 200000
5221 ≤ N ≤ 100000, 1 ≤ L ≤ 10^9, S + J ≤ 200000

Input format

The sample judge reads input in the following format:

  • line 1: N L Q
  • line 2: P[0] P[1] .. P[N - 1]
  • lines 3 to 3 + Q - 1: each line represents either a jump or a score question. If the line is 0 A B, a jump from A to B is to be made, and if the line is 1 a scoring question is to be made.

Output format

For each scoring question, the judge writes a line with the return value of score().

예제

예제 1

입력
3 7 5
1 3 4
1
0 4 2
1
0 3 0
1
출력
5
9
9

출처 표기

출처: Programmeringsolympiaden 2016년 훈련 캠프 · 원문 페이지 · 이용 조건 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). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.