問題一覧 > 通常問題

No.1558 Derby Live

レベル : / AI推定難易度 : 1350 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 75
作問者 : noya2 / テスター : nok0 magsta
お気に入りにしたユーザー ProblemId : 6433 / 自分の提出
問題文最終更新日: 2021-06-25 13:18:32
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 301 (順位表) の他の問題:

Problem Statement

A race among $N$ horses, numbered horse $1,2,\dots,N$, is about to be held.

The race follows the format below.

  • The $N$ horses run through sections $1$ to $M$ in order.
  • Each horse repeats: enter section $i$ $\rightarrow$ exit section $i$ $\rightarrow$ enter section $i+1$ $\rightarrow$ exit section $i+1$ $\dots$
  • Since the sections are contiguous, you may assume that the rankings do not change between exiting section $i$ and entering section $i+1$.
  • No $2$ horses are tied at the moment of entering or exiting any section.
  • The horses enter section $1$ in the order horse $1,2,\dots,N$.
  • Within each section, the rankings of the $N$ horses may change.

Here, for any $l,r$ with $1\le l\le r\le M$, the "excitement of the race" $E_{l,r}$ is defined as follows.

  • When the horse that entered section $l$ in the $i$-th place exits section $r$ in the $T_i$-th place, $E_{l,r} = \displaystyle\sum_{i=1}^{N} |i - T_i|$

  • After the race starts, $Q$ queries arrive to you in order. There are $3$ types of queries, described below.

    Process each query based on the information from the queries before it. (See also the constraints and samples for details.)

    • type $1$ : You receive the information that the horse that entered section $D$ in the $i$-th place exited section $D$ in the $P_i$-th place. Ignore any information about section $D$ from before this query.
    • type $2$ : Print all the horses that exited section $S$, in order starting from the $1$-st place.
    • type $3$ : Print the "excitement of the race" $E_{L,R}$ from section $L$ to section $R$.

    Constraints

  • All input values are integers.
  • $2\le N\le 18$
  • $2\le M\le 10^4$
  • $2\le Q\le 5\times 10^4$
  • $1\le D\le M$
  • $P=(P_1,P_2,\dots ,P_N)$ is a permutation of the sequence $(1,2,\dots ,N)$
  • $1\le S\le M$
  • $1\le L\le R\le M$
  • For type $1$: for a query on section $D$, there is at least $1$ type $1$ query on each of sections $1,2,\dots ,D-1$ among the queries before it.
  • For type $2$: among the queries before a query on section $S$, there is at least $1$ type $1$ query on each of sections $1,2,\dots ,S$.
  • For type $3$: among the queries before a query on sections $L,R$, there is at least $1$ type $1$ query on each of sections $1,2,\dots ,R$.
  • Each test case contains at least $1$ query of type $2$ or type $3$.
  • Input

    $N\ M\ Q$
    $Query_1$
    $\vdots$
    $Query_Q$
    

    $Query_i$ is one of the following $3$ forms.

    $1\ D\ P_1 \dots P_N$
    
    $2\ S$
    
    $3\ L\ R$
    

    Output

    For each query of type $2$, print the numbers of the horses from $1$-st place to $N$-th place on one line, separated by spaces, followed by a newline.

    For each query of type $3$, print $E_{L,R}$ on one line, followed by a newline.

    Sample

    Sample 1
    Input
    3 3 7
    1 1 1 3 2
    1 2 2 1 3
    1 3 2 3 1
    2 3
    3 1 3
    1 2 1 2 3
    2 3
    Output
    2 3 1
    4
    2 1 3

    After processing up to the $3$-rd query,
    the order of the horses exiting section $1$ is $1,3,2$,
    the order of the horses exiting section $2$ is $3,1,2$, and
    the order of the horses exiting section $3$ is $2,3,1$.
    Therefore, the $4$-th query prints 2 3 1.

    Also, at the moment of exiting section $3$, horses $1,2,3$ are in $3$-rd, $1$-st, and $2$-nd place, respectively.
    Therefore, noting that the order of the horses entering section $1$ is $1,2,3$, the $5$-th query prints $E_{1,3}= |1-3|+|2-1|+|3-2|=4$.

    After processing up to the $6$-th query,
    the order of the horses exiting section $1$ is $1,3,2$,
    the order of the horses exiting section $2$ is $1,3,2$, and
    the order of the horses exiting section $3$ is $2,1,3$.
    Therefore, the $7$-th query prints 2 1 3.

    Sample 2
    Input
    4 5 10
    1 1 3 4 2 1
    1 2 1 3 2 4
    2 2
    1 3 2 3 4 1
    3 1 3
    1 2 1 2 3 4
    1 4 2 1 4 3
    2 4
    1 5 3 2 4 1
    3 1 5
    Output
    4 1 3 2
    6
    4 2 1 3
    6

    提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。