比赛场次 569
比赛名称 4043级2023省选模拟赛1
比赛状态 已结束比赛成绩
开始时间 2023-03-20 18:50:00
结束时间 2023-03-20 22:30:00
开放分组 全部用户
注释介绍 进入状态(统一用台式NOI linux)
题目名称 贪玩蓝月
输入输出 tanwan.in/out
时间限制 4000 ms (4 s)
内存限制 512 MiB
测试点数 20 简单对比
用户 结果 时间 内存 得分
Gravatarop_组撒头屯 AAAAAAAAAAAAAAAAAAAA
6.709 s 13.37 MiB 100
Gravataryrtiop WWWWWWWWWWWWWWWWWWWW
2.105 s 205.77 MiB 0

贪玩蓝月

★★★☆   输入文件:tanwan.in   输出文件:tanwan.out   简单对比
时间限制:4 s   内存限制:512 MiB

【题目描述】

   大渣好,我四渣渣辉,点一下,玩一年,装备不花一分钱,说话战斗,罩杯回收,找一基友,极限到手。


   $0$ 元 $VIP$,$3$ 天满级,一秒一刀 $999$,装备全爆 $666$,广告做得再牛,不如进服遛一遛!


   古天乐绿了,古天乐绿了,惊喜不断,月入上万!不花钱还赚钱的绿色游戏,等级能提现,装备换点钱!


《贪玩蓝月》是目前最火爆的网页游戏。在游戏中每个角色都有若干装备,每件装备有一个特征值 $w$ 和一个战斗力 $v$ 。在每种特定的情况下,你都要选出特征值的和对 p 取模后在一段范围内的装备,而角色死亡时自己的装备会爆掉。每个角色的物品槽可以看成一个双端队列,得到的装备会被放在两端,自己的装备爆掉也会在两端被爆。


现在我们有若干种事件和询问,如下所示:


   $IF\ w\ v$:在前端加入一件特征值为 $w$ 战斗力为 $v$ 的装备

   $IG\ w\ v$:在后端加入一件特征值为 $w$ 战斗力为 $v$ 的装备

   $DF:$删除最前端的装备

   $DG:$删除最后端的装备

   $QU\ l\ r:$在当前的装备中选取若干装备,他们的和对 $p$ 取模后在 $[l, r]$ 中,使得这些装备的战斗力之和最大


为了锻炼你的水平,请尽量使用在线做法。

【输入格式】

第一行一个整数表示测试点编号。

第二行两个整数 $m$ 和 $p$,分别表示操作数和模数。

接下来每一行一个操作,如题目描述中所述,有五种操作,在前后加或删一件物品或者询问。

【输出格式】

对于每个询问,输出一行,表示在当前装备中选取若干装备和对 $p$ 取模后在 $[l, r]$ 的装备,使得这些装备战斗力之和最大。如果没有合法方案,输出 $-1$。

【样例1输入】

0
11 10
QU 0 0
QU 1 9
IG 14 7
IF 3 5
QU 0 9
IG 1 8
DF
QU 0 4
IF 1 2
DG
QU 2 9

【样例1输出】

0
-1
12
8
9

【样例1说明】

一开始没有物品,那么可以不选,特征值价值为 $0$,不可能凑出非 $0$ 的特征值。


然后在后面加了一个特征值 $14$ 价值 $7$ 的装备,又在前面加了一个特征值 $3$ 价值 $5$ 的装备,询问特征值取模后为 $[0, 9]$ 的装备,那么全部选择价值为 $12$。


然后在后面加了一个特征值为 $1$ 价值为 $8$ 的装备,删除了最前面的装备(特征值 $3$ 价值 $5$),询问特征值取模后为 $[0, 4]$ 的装备,那么只选择特征值为 $1$ 价值为 $8$ 的装备,最大价值为 $8$。


最后又在前面加了一个特征值为 $1$ 价值为 $2$ 的装备,删除了最后面的装备(特征值 $1$ 价值 $8$),询问特征值取模后为 $[2, 9]$ 的装备,那么选择当前剩余的两件装备,价值和为 $9$。

【样例2/3】

点击下载样例2/3

【数据规模与约定】

【来源】