loj#P6949. 「THUPC 2025 初赛」背向而行

「THUPC 2025 初赛」背向而行

题目描述

mm 堆积木,其中第 ii 堆积木位于坐标 xix_i 的位置,有 cic_i 块。

反复执行如下操作,直至无法操作:

  • 如果存在两块积木坐标相同,则找到满足条件的积木中坐标最小的两块,将一块坐标减 11,另一块坐标加 11

可以证明在有限次操作之后,所有积木的坐标都会不同,此时无法进行操作。

多次询问,每次给定正整数 kk,问最后左数第 kk 块积木的位置。保证询问的 kk 严格递增。

输入格式

第一行一个正整数 mm。保证 1m2×1061\le m \le 2\times 10^6

接下来 mm 行,其中第 ii 行两个正整数 xi,cix_i,c_i。保证 1xi1091\le x_i \le 10^91ci1091\le c_i \le 10^9。保证 xix_i 按照输入的顺序严格递增,即 xi<xi+1x_i<x_{i+1}

接下来一行一个正整数 qq,表示询问个数。保证 1q2×1061\le q\le 2\times 10^6

接下来 qq 行,每行一个正整数 kk,表示一次询问。保证 1ki=1mci1091\le k \le \sum\limits_{i=1}^{m} c_i \le 10^9。保证询问的 kk 严格递增。

输出格式

输出 qq 行,每行一个整数,其中第 ii 行表示第 ii 个询问的答案。

2
3 3
4 2
2
2
4
2
5

我们用长度为 5 的单调不降数字字符串描述从左往右五块积木的位置,那么操作过程如下所示:

$33344 \to 23444 \to 23345 \to 22445 \to 13445 \to 13355 \to 12455 \to 12446 \to 12356$

最终第二块积木坐标为 2,第四块积木坐标为 5。

题目使用协议

来自 THUPC2025(2025年清华大学学生程序设计竞赛暨高校邀请赛)初赛。

以下『本仓库』皆指 THUPC2025 初赛 官方仓库(https://gitlink.org.cn/thusaa/thupc2025pre

  1. 任何单位或个人都可以免费使用或转载本仓库的题目;

  2. 任何单位或个人在使用本仓库题目时,应做到无偿、公开,严禁使用这些题目盈利或给这些题目添加特殊权限;

  3. 如果条件允许,请在使用本仓库题目时同时提供数据、标程、题解等资源的获取方法;否则,请附上本仓库地址 或 算协公开仓库链接