[POI 2020/2021 R3] Les Bitérables

Luogu
IDLGP9403
Time1000ms
Memory256MB
DifficultyP5
2020POI(波兰)差分双指针 two-pointer
有 $t$ 个时刻,第 $i$ 个时刻给出了局面 $p_1,p_2,\dots,p_{s_i}$,表示在数轴的 $(0,d)$ 范围内,有且仅有 $p_1,p_2,\dots,p_{s_i}$ 这些位置上有物品。 在 $0$ 位置和 $d$ 位置有无穷多个物品。 你可以花费一个代价,将一个物品向左移动一个位置或向右移动一个位置。 问你在相邻两个时刻之间,把前一个局面转化为后一个局面,最少需要多少代价。 ## Input 第一行两个正整数 $n,d$。 接下来 $n$ 行,每行描述一个时刻的局面,首先是一个非负整数 $s_i$,接下来是 $s_i$ 个正整数,分别为 $p_1,p_2,\dots,p_{s_i}$。保证 $0<p_1<p_2<\dots<p_{s_i}<d$。 ## Output $n-1$ 行,每行一个整数,你的答案。 [samples] ## Background 译自 [XXVIII Olimpiada Informatyczna - III etap](https://sio2.mimuw.edu.pl/c/oi28-3/dashboard/) [Les Bitérables](https://szkopul.edu.pl/problemset/problem/Lpz563_ATiESIrNZxiT5bwIx/statement/)。 d1t2。 ## Note 对于所有数据,$2\leq n\leq 500000$,$2\leq d\leq 10^{12}$,$\sum s_i\leq 500000$。 | 子任务编号 | 附加限制 | 分数 | | :----------: | :----------: | :----------: | | 1 | $s_i\leq 1$ | 5 | | 2 | $s_i\leq 3$ | 10 | | 3 | $d\leq 7$ | 12 | | 4 | $\sum s_i\leq 5000$ | 27 | | 5 | 如果 $s_i>0$,那么 $p_{s_i}=p_1+s_i-1$ | 11 | | 6 | | 35 |
Samples
Input #1
3 10
2 4 7
3 3 6 8
1 5
Output #1
4
6
Input #2
见附件
Output #2
6252500
6252500
Input #3
见附件
Output #3
999990000
999990000
999990000
999990000
Input #4
生成器:/paste/3igmip11
Output #4
生成器:/paste/fusadpm0
API Response (JSON)
{
  "problem": {
    "name": "[POI 2020/2021 R3] Les Bitérables",
    "description": {
      "content": "有 $t$ 个时刻,第 $i$ 个时刻给出了局面 $p_1,p_2,\\dots,p_{s_i}$,表示在数轴的 $(0,d)$ 范围内,有且仅有 $p_1,p_2,\\dots,p_{s_i}$ 这些位置上有物品。 在 $0$ 位置和 $d$ 位置有无穷多个物品。 你可以花费一个代价,将一个物品向左移动一个位置或向右移动一个位置。 问你在相邻两个时刻之间,把前一个局面转化为后一个局面,最少需要",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": {
      "LuoguStyle": "P5"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9403"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "有 $t$ 个时刻,第 $i$ 个时刻给出了局面 $p_1,p_2,\\dots,p_{s_i}$,表示在数轴的 $(0,d)$ 范围内,有且仅有 $p_1,p_2,\\dots,p_{s_i}$ 这些位置上有物品。\n\n在 $0$ 位置和 $d$ 位置有无穷多个物品。\n\n你可以花费一个代价,将一个物品向左移动一个位置或向右移动一个位置。\n\n问你在相邻两个时刻之间,把前一个局面转化为后一个局面,最少需要...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments