#P18665. Game: Celeste

    ID: 18001 传统题 2500ms 1024MiB 尝试: 1 已通过: 1 难度: 9 上传者: 标签>CF2600省选/NOI-线性 DP单调队列优化 DP可持久化线段树路径复制哈希表离散化

Game: Celeste

Game: Celeste

“快乐地使用 wavedash 吧!”——《Wavedash and You》

Madeline 正在攀登 Celeste 山。当前路段有 nn 根柱子,位置分别为 x1,x2,…,xnx_1,x_2,\ldots,x_n。相邻柱子之间没有地面,因此 Madeline 只能从一根柱子移动到另一根柱子,不能停在两根柱子中间。第 ii 根柱子顶端有一颗大小为 aia_i 的草莓。每当 Madeline 站在一根柱子上,她都可以选择收取该柱子上的草莓。

原题中的 wavedash 示意图

Madeline 已经在第一根柱子上学会了 wavedash 技巧,希望在这段路上练习。然而受风力条件影响,当她当前位于 xx 时,一次 wavedash 只能将她带到区间 [x+L,x+R][x+L,x+R] 中的某个位置。落点必须是一根柱子。

到达第 nn 根柱子后,Madeline 会用收集到的草莓评价自己的技巧。比较两份草莓序列时,她会先将两份序列分别按草莓大小非递增排序,再比较排序后序列的字典序;字典序越大,她越满意。字典序按通常定义比较:先看第一个不同元素;如果一个序列是另一个的真前缀,则较长序列更大。

在实际尝试前,请帮助 Madeline 规划一条从第 11 根柱子到第 nn 根柱子的路线,使她获得的满意程度最大。

输入格式

输入包含多组测试数据。第一行包含整数 TT,表示测试数据的组数。

对于每组数据:

  • 第一行包含三个整数 n,L,Rn,L,R,满足 1≤n≤1061\le n\le10^6、1≤L≤R≤1091\le L\le R\le10^9,分别表示柱子数量和 wavedash 的参数。
  • 第二行包含 nn 个整数 x1,…,xnx_1,\ldots,x_n,满足 1≤xi≤1091\le x_i\le10^9。保证 xi<xi+1x_i<x_{i+1},其中 1≤i<n1\le i<n。
  • 第三行包含 nn 个整数 a1,…,ana_1,\ldots,a_n,满足 1≤ai≤n1\le a_i\le n,表示各根柱子上草莓的大小。

保证所有测试数据的 nn 之和不超过 10610^6。

输出格式

对于每组数据,如果 Madeline 无法到达第 nn 根柱子,输出一行 -1。

否则输出两行:第一行输出整数 kk,表示她收集的草莓数量;第二行输出 kk 个整数,按非递增顺序给出能获得最大满意程度的草莓大小序列。无需输出路线。

样例输入 1

2
5 2 3
1 2 3 4 5
5 2 3 1 4
3 1 2
1 4 7
3 3 3

样例输出 1

3
5 4 3
-1