P7582 - Fluctuation Limit

内存限制：128 MB 时间限制：1 S

题面：传统评测方式：文本比较上传者：

提交：7 通过：0

It is preferrable to read the pdf statment.

Cuber QQ has signed up for a gambling game, that challenges him to predict the stock price of Quber CC Limited, for the next following

n days. He shall make his prediction by filling a table with

n intervals, the

i-th of which is the predicted interval

[li,ri] at the

i-th day. If all

n prices lie in the corresponding interval, Cuber QQ will win 1 million dollars. Otherwise, he will not earn a single penny.

As is well known, the stock price has a fluctuation limit. For simplicity, we assume the limit up and the limit down are both

k, which is an integer. That means, if the stock price at the

i-th day is

x, the price at the

i+1-th day is at most

x+k and at least

x−k.

Cuber QQ wants to know whether it is possible to manipulate the stock price, without breaking the limitation above of course, so that he can have the

1 million dollars. Since his table has already been submitted, he cannot modify his predicted intervals any more. It has to be done secretly behind the scenes, and smartly cover it up so that no one will notice.

The input starts with an integer

T (

1≤T≤105), denoting the number of test cases.

For each test case, the first line contains two space-separated integers

n and

k (

2≤n≤105,

0≤k≤109), where

n is the number of days and

k is the fluctuation limit.

The

i-th line of the next

n lines contains two space-separated integers

li and

ri (

0≤li≤ri≤109), which is Cuber QQ's predicted interval in the

i-th day. A prediction is believed to be correct if the stock price

i-th day lies between

li and

ri, inclusive.

It is guaranteed that the sum of all

n does not exceed

106.

For each test case, first output a single line YES or NO, that states whether Cuber QQ will win the 1 million price.
If YES, in the next line, output a possible price series,

a1,a2,…,an, where

li≤ai≤ri (

1≤i≤n) and

|ai−ai+1|≤k (

1≤i≤n−1). The integers should be separated with space.

YES
2 3 3
NO

杭电多校8

7582: Fluctuation Limit

题目描述

输入格式

输出格式

输入样例复制

输出样例复制

分类标签