#P9404. [POI 2020/2021 R3] Surowa zima

    ID: 8675 远端评测题 5000ms 256MiB 尝试: 0 已通过: 0 难度: 7 上传者: 标签>模拟贪心平衡树POI2021构造分类讨论

[POI 2020/2021 R3] Surowa zima

题目背景

译自 XXVIII Olimpiada Informatyczna - III etap Surowa zima

d1t3。

题目描述

有一条长 ll 米的道路(数轴)。路上有 nn 个充电站。每天整条路上(坐标 [0,l][0,l])都会落满雪。

有一台机器能扫雪。充一次电可以扫至多 kk 米的雪。扫雪是和移动同时进行的,详见样例解释。机器一秒能移动一米,充电不消耗时间。

简单来说,移动不扫雪不消耗电,需要一秒;移动并扫雪消耗最大电量的 1k\bold{\frac1k},需要一秒;扫雪必须移动。

给出每天机器的初始位置,机器初始没电,问每天清除所有雪的最少时间。终点任意。

带修,即充电站可能损坏或修好(第一天之前都是好的),但保证每天都至少有一个好的充电站(所以不会无解)。

输入格式

第一行四个整数 n,l,k,dn,l,k,d

第二行 nn 个整数 x1,x2,,xnx_1,x_2,\dots,x_n,表示充电站的位置,保证 0x1<x2<<xnl0\leq x_1<x_2<\dots<x_n\leq l

接下来 3d3d 行,描述 dd 天的事件:

  • 第一行三个整数 z,u,pz,u,p,分别表示昨晚修好的充电站数量,损坏的数量,和机器的初始位置。
  • 第二行 zz 个整数,表示被修好的充电站编号。
  • 第三行 uu 个整数,表示损坏的充电站编号。

输出格式

dd 行,每行一个整数,表示每天的答案。

输入数据 1

3 5 2 1
2 3 5
0 1 3

2

输出数据 1

9

输入数据 2

5 12 1 5
1 3 6 9 11
0 1 1

1
1 1 3
1
2
1 1 6
2
3
1 1 9
3
4
1 1 11
4
5

输出数据 2

33
33
36
33
33

输入数据 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

输出数据 3

1090
1096
1098
1092
1094
1100
1094
1092
1098
1096
1090
1096
1098
1092
1094
1100
1094
1092
1098
1096
1090
1096
1098
1092
1094
1100

输入数据 4

见附件

输出数据 4

见附件

输入数据 5

见附件

输出数据 5

1000000000000000000
2001007996000

提示

样例解释:32充电02充电45充电43\rightarrow2_{充电}\Rightarrow0\rightarrow2_{充电}\Rightarrow4\rightarrow5_{充电}\Rightarrow4\rightarrow 表示移动,\Rightarrow 表示移动并扫雪。

对于所有数据,1n2500001\leq n\leq 2500001l1091\leq l\leq 10^91kl1\leq k\leq l1d2500001\leq d\leq 250000z,u500000\sum z,\sum u\leq 500000

子任务编号 附加限制 分数
1 l12l\leq 12d50d\leq 50 10
2 l500l\leq 500d50d\leq 50k=1k=1 12
3 l5000000l\leq 5000000d20d\leq 20 8
4 z=u=0z=u=0
5 z,u100z,u\leq 100k50k\leq 50 20
6 k=1k=1 18
7 24