[POI 2020/2021 R3] 扫雪波特 / Surowa zima

Luogu

IDLGP9404

Time5000ms

Memory256MB

DifficultyP7

模拟贪心2020平衡树POI（波兰）构造分类讨论

有一条长 $l$ 米的道路（数轴）。路上有 $n$ 个充电站。每天整条路上（坐标 $[0,l]$）都会落满雪。有一台机器能扫雪。充一次电可以扫至多 $k$ 米的雪。扫雪是和移动同时进行的，详见样例解释。机器一秒能移动一米，充电不消耗时间。简单来说，**移动不扫雪不消耗电，需要一秒；移动并扫雪消耗最大电量的 $\bold{\frac1k}$，需要一秒；扫雪必须移动。** 给出每天机器的初始位置，机器初始没电，问每天清除所有雪的最少时间。终点任意。带修，即充电站可能损坏或修好（第一天之前都是好的），但保证每天都至少有一个好的充电站（所以不会无解）。 ## Input 第一行四个整数 $n,l,k,d$。第二行 $n$ 个整数 $x_1,x_2,\dots,x_n$，表示充电站的位置，保证 $0\leq x_1<x_2<\dots<x_n\leq l$。接下来 $3d$ 行，描述 $d$ 天的事件： - 第一行三个整数 $z,u,p$，分别表示昨晚修好的充电站数量，损坏的数量，和机器的初始位置。 - 第二行 $z$ 个整数，表示被修好的充电站编号。 - 第三行 $u$ 个整数，表示损坏的充电站编号。 ## Output $d$ 行，每行一个整数，表示每天的答案。 [samples] ## Background 译自 [XXVIII Olimpiada Informatyczna - III etap](https://sio2.mimuw.edu.pl/c/oi28-3/dashboard/) [Surowa zima](https://szkopul.edu.pl/problemset/problem/QCCQf92wAoWAOoJ3tHoypvp3/statement/)。 d1t3。 ## Note 样例解释：$3\rightarrow2_{充电}\Rightarrow0\rightarrow2_{充电}\Rightarrow4\rightarrow5_{充电}\Rightarrow4$。$\rightarrow$ 表示移动，$\Rightarrow$ 表示移动并扫雪。对于所有数据，$1\leq n\leq 250000$，$1\leq l\leq 10^9$，$1\leq k\leq l$，$1\leq d\leq 250000$，$\sum z,\sum u\leq 500000$。 | 子任务编号 | 附加限制 | 分数 | | :----------: | :----------: | :----------: | | 1 | $l\leq 12$，$d\leq 50$ | 10 | | 2 | $l\leq 500$，$d\leq 50$，$k=1$ | 12 | | 3 | $l\leq 5000000$，$d\leq 20$ | 8 | | 4 | $z=u=0$ | 8 | | 5 | $z,u\leq 100$，$k\leq 50$ | 20 | | 6 | $k=1$ | 18 | | 7 | | 24 |

Samples

Input #1

Output #1

Input #2

Output #2

Input #3

11 100 1 26
0 10 20 30 40 50 60 70 80 90 100
0 5 0

2 4 6 8 10
5 6 4
2 4 6 8 10
1 3 5 7 9 11
6 5 8
1 3 5 7 9 11
2 4 6 8 10
5 6 12
2 4 6 8 10
1 3 5 7 9 11
6 5 16
1 3 5 7 9 11
2 4 6 8 10
5 6 20
2 4 6 8 10
1 3 5 7 9 11
6 5 24
1 3 5 7 9 11
2 4 6 8 10
5 6 28
2 4 6 8 10
1 3 5 7 9 11
6 5 32
1 3 5 7 9 11
2 4 6 8 10
5 6 36
2 4 6 8 10
1 3 5 7 9 11
6 5 40
1 3 5 7 9 11
2 4 6 8 10
5 6 44
2 4 6 8 10
1 3 5 7 9 11
6 5 48
1 3 5 7 9 11
2 4 6 8 10
5 6 52
2 4 6 8 10
1 3 5 7 9 11
6 5 56
1 3 5 7 9 11
2 4 6 8 10
5 6 60
2 4 6 8 10
1 3 5 7 9 11
6 5 64
1 3 5 7 9 11
2 4 6 8 10
5 6 68
2 4 6 8 10
1 3 5 7 9 11
6 5 72
1 3 5 7 9 11
2 4 6 8 10
5 6 76
2 4 6 8 10
1 3 5 7 9 11
6 5 80
1 3 5 7 9 11
2 4 6 8 10
5 6 84
2 4 6 8 10
1 3 5 7 9 11
6 5 88
1 3 5 7 9 11
2 4 6 8 10
5 6 92
2 4 6 8 10
1 3 5 7 9 11
6 5 96
1 3 5 7 9 11
2 4 6 8 10
5 6 100
2 4 6 8 10
1 3 5 7 9 11

Output #3

Input #4

见附件

Output #4

见附件

Input #5

见附件

Output #5

1000000000000000000
2001007996000

API Response (JSON)

{
  "problem": {
    "name": "[POI 2020/2021 R3] 扫雪波特 / Surowa zima",
    "description": {
      "content": "有一条长 $l$ 米的道路（数轴）。路上有 $n$ 个充电站。每天整条路上（坐标 $[0,l]$）都会落满雪。 有一台机器能扫雪。充一次电可以扫至多 $k$ 米的雪。扫雪是和移动同时进行的，详见样例解释。机器一秒能移动一米，充电不消耗时间。 简单来说，**移动不扫雪不消耗电，需要一秒；移动并扫雪消耗最大电量的 $\\bold{\\frac1k}$，需要一秒；扫雪必须移动。** 给出每天机器的初始",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 5000,
      "memory_limit": 262144
    },
    "difficulty": {
      "LuoguStyle": "P7"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9404"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "有一条长 $l$ 米的道路（数轴）。路上有 $n$ 个充电站。每天整条路上（坐标 $[0,l]$）都会落满雪。\n\n有一台机器能扫雪。充一次电可以扫至多 $k$ 米的雪。扫雪是和移动同时进行的，详见样例解释。机器一秒能移动一米，充电不消耗时间。\n\n简单来说，**移动不扫雪不消耗电，需要一秒；移动并扫雪消耗最大电量的 $\\bold{\\frac1k}$，需要一秒；扫雪必须移动。**\n\n给出每天机器的初始...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments