CF2271D.Target Infection
普及+/提高
通过率:0%
时间限制:2.00s
内存限制:256MB
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
You are given n pairwise disjoint infection intervals on the number line. The i-th interval is [li,ri], meaning that every integer position x such that li≤x≤ri is infected. All integer positions not covered by any of the intervals are not infected.
There are m people standing in a row. If the first person stands at position s, then the people stand at positions s,s+1,…,s+m−1. A person is infected if the position they stand at is infected.
For an integer s, let f(s) be the number of infected people when the first person stands at position s.
You are given an integer k. Find any integer s such that f(s)=k, or determine that no such s exists.
给定数轴上的 n 个两两不相交的感染区间。第 i 个区间为 [li,ri],表示所有满足 li≤x≤ri 的整数位置 x 均被感染。所有未被任何区间覆盖的整数位置均未被感染。
有 m 个人排成一列。若第一个人站在位置 s,则这些人的位置依次为 s, s+1, …, s+m−1。若某人所站位置被感染,则该人被感染。
对任意整数 s,定义 f(s) 为当第一个人站在位置 s 时被感染的人数。
给定整数 k,请找出任意一个满足 f(s)=k 的整数 s;若不存在这样的 s,则判定其不存在。
输入格式
Each test contains multiple test cases. The first line contains the number of test cases t (1≤t≤104). The description of the test cases follows.
The first line of each test case contains three integers n, m, and k (1≤n≤2⋅105, 1≤m≤109, 0≤k≤m) — the number of infection intervals, the number of people, and the required number of infected people.
The i-th of the following n lines contains two integers li and ri (1≤li≤ri≤1015) — the endpoints of the i-th infection interval. It is guaranteed that ri+1<li+1 for every i from 1 to n−1, so the intervals are pairwise disjoint, no two of them are adjacent, and they are given from left to right.
It is guaranteed that the sum of n over all test cases does not exceed 2⋅105.
每个测试包含多个测试用例。第一行包含测试用例的数量 t(1≤t≤104)。随后是各测试用例的描述。
每个测试用例的第一行包含三个整数 n、m 和 k(1≤n≤2⋅105,1≤m≤109,0≤k≤m)——分别表示感染区间的数量、总人数以及所需的被感染者人数。
接下来的 n 行中,第 i 行包含两个整数 li 和 ri(1≤li≤ri≤1015)——表示第 i 个感染区间的左右端点。保证对每个 i(从 1 到 n−1)均有 ri+1<li+1,因此这些区间两两不相交、互不相邻,且按从左到右的顺序给出。
保证所有测试用例的 n 值之和不超过 2⋅105。
输出格式
For each test case, if there is no integer s such that f(s)=k, output −1.
Otherwise, output a single integer s (1≤s≤1018) — a position such that f(s)=k. It can be shown that if at least one such position exists, then a position within these bounds exists as well.
If there are multiple valid positions, output any of them.
对于每个测试用例,若不存在整数 s 使得 f(s)=k,则输出 −1。
否则,输出一个整数 s(1≤s≤1018),使得 f(s)=k。可以证明:若至少存在一个满足条件的位置,则必存在一个在该范围内的位置。
若存在多个合法的位置,输出其中任意一个即可。
输入输出样例
输入#1
6 1 5 5 7 11 2 4 3 1 2 5 6 3 5 4 1 3 5 6 8 8 1 3 2 10 12 3 6 0 1 1 4 5 10 12 1 1000000000 1 1000000000000000 1000000000000000
输出#1
7 -1 2 9 42 999999876543210
说明/提示
In the first example, one valid position is s=7. The people then stand at the positions 7,8,9,10,11, all of which are infected, so f(7)=5.
In the second example, it can be shown that there is no suitable position.
In the third example, one valid position is s=2. The people then stand at the positions 2,3,4,5,6. Positions 2, 3, 5, and 6 are infected, while position 4 is not, so f(2)=4.
在第一个例子中,一个合法的位置是 s=7。此时人们站在位置 7,8,9,10,11,这些位置均被感染,因此 f(7)=5。
在第二个例子中,可以证明不存在合适的位置。
在第三个例子中,一个合法的位置是 s=2。此时人们站在位置 2,3,4,5,6。其中位置 2、3、5 和 6 被感染,而位置 4 未被感染,因此 f(2)=4。
输入解题思路,AI测评打分。不知道怎么写?