[PA 2021] Areny

Luogu

IDLGP9052

Time7000ms

Memory1024MB

DifficultyP7

2021PA（波兰）

Bajtek 在圣诞节收到了父母送的最新电脑游戏 Byte Defence 4。他兴致勃勃地打开游戏开始玩。游戏里操控的角色叫 Bajtonator，需要通过打怪、完成任务和升级装备来变强。地图上有 $n$ 个特殊的竞技场，里面有很稀有的掉落品。但有 $n$ 种通行证，想进某个竞技场必须持有对应的通行证。这个游戏的规则如下： 1. 如果你有某个竞技场的通行证，就可以进入该竞技场与怪物战斗。进入竞技场不会消耗通行证，怪物会在你离开后复活，所以同一张通行证可以反复使用，反复挑战同一竞技场。 2. 每个竞技场都有一个事先公开、固定不变的通行证池，池里的通行证不会被移出或改变。击败竞技场里的怪物后，除了可能掉落稀有物品外，还会从该竞技场的通行证池里随机抽取一张通行证，复制一份交给你。所以你可能在多次胜利后拥有相同类型的多张通行证副本。看了攻略后，Bajtek 得知竞技场编号越大越难。他的实力可以用一个整数 $k$ 来表示：他一定能在编号小于等于 $k$ 的竞技场获胜，而对编号大于 $k$ 的竞技场他一定无法获胜。开始时他没有任何通行证，只能花钱买**一张**。买哪一张最划算呢？他认为，如果买了竞技场 $A$ 的通行证，凭借这个起始通行证和之后的战斗所得通行证，**无论如何**他最终都能进入竞技场 $B$ 并获胜，那这张通行证就是值得买的。所以他想知道，对于某个固定的 $k$，有多少有序竞技场对 $(A,B)$ 满足： 1. $A\neq B$。 2. 如果只买了竞技场 $A$ 的通行证，凭借这个起始通行证和之后的战斗所得通行证，无论如何他最终都能进入竞技场 $B$ 并获胜。你需要对于 $k=1,2,\cdots,n$ 计算这样的有序对 $(A,B)$ 的个数。 ## Input 第一行，一个整数 $n\;(2\le n\le 2\cdot 10^5)$，表示竞技场的数量。接下来 $n$ 行，其中第 $i$ 行先是一个整数 $l_i\;(1\le l_i)$，表示第 $i$ 个竞技场的通行证池大小。随后给出 $l_i$ 个整数，表示该池中每种通行证能进入的竞技场编号。所有 $l_i$ 的总和不超过 $5\cdot10^5$。 ## Output 一行，$n$ 个整数，其中第 $i$ 个整数表示 $k = i$ 时的答案。 [samples]

Samples

Input #1

Output #1

0 1 4 4 5 6 7 7 7

API Response (JSON)

{
  "problem": {
    "name": "[PA 2021] Areny",
    "description": {
      "content": "Bajtek 在圣诞节收到了父母送的最新电脑游戏 Byte Defence 4。他兴致勃勃地打开游戏开始玩。游戏里操控的角色叫 Bajtonator，需要通过打怪、完成任务和升级装备来变强。地图上有 $n$ 个特殊的竞技场，里面有很稀有的掉落品。但有 $n$ 种通行证，想进某个竞技场必须持有对应的通行证。 这个游戏的规则如下： 1. 如果你有某个竞技场的通行证，就可以进入该竞技场与怪物战斗。进",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 7000,
      "memory_limit": 1048576
    },
    "difficulty": {
      "LuoguStyle": "P7"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9052"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Bajtek 在圣诞节收到了父母送的最新电脑游戏 Byte Defence 4。他兴致勃勃地打开游戏开始玩。游戏里操控的角色叫 Bajtonator，需要通过打怪、完成任务和升级装备来变强。地图上有 $n$ 个特殊的竞技场，里面有很稀有的掉落品。但有 $n$ 种通行证，想进某个竞技场必须持有对应的通行证。\n\n这个游戏的规则如下：\n\n1. 如果你有某个竞技场的通行证，就可以进入该竞技场与怪物战斗。进...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments