Dotcpp  >  编程题库  >  蓝桥杯2021年第十二届国赛真题-冰山
题目 2614:

蓝桥杯2021年第十二届国赛真题-冰山

时间限制: 1s 内存限制: 128MB 提交: 535 解决: 12

题目描述

一片海域上有一些冰山,第 i 座冰山的体积为 Vi。
随着气温的变化,冰山的体积可能增大或缩小。第 i 天,每座冰山的变化量都是 Xi。当 Xi > 0 时,所有冰山体积增加 Xi;当 Xi < 0 时,所有冰山体积减少 ቁ Xi;当 Xi = 0 时,所有冰山体积不变。

如果第 i 天某座冰山的体积变化后小于等于 0,则冰山会永远消失。

冰山有大小限制 k。如果第 i 天某座冰山 j 的体积变化后 Vj 大于 k,则它会分裂成一个体积为 k 的冰山和 Vj 赗? k 座体积为 1 的冰山。第 i 天结束前(冰山增大、缩小、消失、分裂完成后),会漂来一座体积为Yi 的冰山(Yi = 0 表示没有冰山漂来)。

小蓝在连续的 m 天对这片海域进行了观察,并准确记录了冰山的变化。小蓝想知道,每天结束时所有冰山的体积之和(包括新漂来的)是多少。
由于答案可能很大,请输出答案除以 998244353 的余数。

输入格式

输入的第一行包含三个整数 n, m, k,分别表示初始时冰山的数量、观察的
天数以及冰山的大小限制。
第二行包含 n 个整数 V1, V2, · · · , Vn,表示初始时每座冰山的体积。
接下来 m 行描述观察的 m 天的冰山变化。其中第 i 行包含两个整数 Xi, Yi,
意义如前所述。

输出格式

输出 m 行,每行包含一个整数,分别对应每天结束时所有冰山的体积之和
除以 998244353 的余数。

样例输入

1 3 6
1
6 1
2 2
-1 1

样例输出

8
16
11

提示

【样例说明】
在本样例说明中,用 [a1, a2, · · · , an] 来表示每座冰山的体积。
初始时的冰山为 [1]。 第 1 天结束时,有 3 座冰山:[1, 1, 6]。 第 2 天结束时,有 6 座冰山:[1, 1, 2, 3, 3, 6]。 第 3 天结束时,有 5 座冰山:[1, 1, 2, 2, 5]。
【评测用例规模与约定】
对于 40% 的评测用例,n, m, k ≤ 2000;
对于 60% 的评测用例,n, m, k ≤ 20000;
对于所有评测用例,1 ≤ n, m ≤ 100000, 1 ≤ k ≤ 109, 1 ≤ Vi ≤ k, 0 ≤ Yi ≤ k,쇋? k ≤ Xi ≤ k。

标签