← 返回题目

题库练习 Isla's Memory Thresholds

← 上一题下一题 →

A16533 | $Isla's Memory Thresholds$

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

我希望有一天，你能与那个你珍惜的人重逢。 —— Plastic Memories 在 Plastic Memories 的世界中，Isla 正在收集 $n$ 个记忆碎片。第 $i$ 个碎片的大小为 $a_i$，且这些大小是非增序排列的，即 $a_1 \ge a_2 \ge \cdots \ge a_n$。 在回收过程中，Isla 会处理一个范围内的碎片，并将它们的大小存储到缓冲区中。当缓冲区中的总大小达到某个给定的阈值 $x$ 时，会发生溢出：此时记录下一份胶囊，并将缓冲区清空为零。 共有 $q$ 个独立的查询，每个查询由三元组 $(l,r,x)$ 描述。对于每个查询，$x$ 表示 Isla 的记忆容量。然后 Isla 会依次收集第 $l$ 到 $r$ 个记忆碎片。任何时刻，当她当前持有的碎片的总大小不少于 $x$ 时，她会完全清空自己的记忆（不留下任何碎片）。你需要判断 Isla 清空记忆的次数，以及她最终持有的碎片大小之和。

输入格式

每个测试包含多组测试数据。第一行包含测试组数 $t$（$1 \le t \le 1000$）。接下来是每组测试数据的描述。 每组测试数据的第一行包含两个整数 $n$ 和 $q$（$1 \le n, q \le 150{,}000$）——数组 $a$ 的长度和查询数量。 第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$（$1 \le a_i \le 10^9$）——碎片的大小。保证 $a_1 \ge a_2 \ge \cdots \ge a_n$。 接下来 $q$ 行，每行包含三个整数 $l, r, x$（$1 \le l \le r \le n$，$1 \le x \le 10^9$），表示一个查询。 保证所有测试数据中 $n$ 的总和不超过 $150{,}000$。 保证所有测试数据中 $q$ 的总和不超过 $150{,}000$。

输出格式

对于每组测试数据中的每个查询，输出两整数——Isla 清空记忆的次数，以及她最终持有的碎片大小之和。

输入输出样例

输入 #1

3
5 4
7 5 5 2 1
1 3 10
2 5 6
1 5 7
3 5 4
6 5
6 6 5 3 2 2
1 6 2
1 6 7
2 6 7
2 5 4
2 5 3
11 7
938412006 792864920 746880066 729862150 704473377 550436315 381392172 326088331 316506801 301443698 190862681
1 3 417253102
9 11 857592497
1 11 344359921
1 7 408760015
8 8 544749974
7 10 361090133
3 11 888178376

输出 #1

1 5
1 3
2 3
1 3
6 0
2 4
2 0
3 0
3 2
3 0
0 808813180
9 0
6 381392172
0 326088331
2 301443698
3 492306379

C++ 编辑器

输入

输出