trang chủ / đề bài / icpcwf17_h

Phong cảnh

Đề bài

Mô tả

Bạn quyết định dành một ngày trong chuyến đi tới Rapid City để chụp ảnh vùng Badlands ở South Dakota, nơi nổi tiếng với những dạng địa hình ngoạn mục và kỳ lạ. Bạn chỉ là nhiếp ảnh gia nghiệp dư, nhưng lại rất khắt khe về điều kiện ánh sáng.

Sau khi tìm hiểu kỹ, bạn đã chọn được một địa điểm tuyệt đẹp ở Badlands, xung quanh là những phong cảnh đáng chụp. Bạn đã xác định một số cảnh muốn chụp từ địa điểm này. Với mỗi cảnh, bạn biết thời điểm sớm nhất và muộn nhất trong ngày mà vị trí của mặt trời là lý tưởng. Tuy nhiên, chụp mỗi bức ảnh mất khá nhiều thời gian, vì phải đặt lại chân máy và máy ảnh, cộng thêm tính cầu toàn của bạn. Bạn tự hỏi liệu có thể chụp được tất cả các cảnh này trong một ngày hay không.

Cụ thể, có n bức ảnh cần chụp, mỗi bức mất đúng t đơn vị thời gian và bạn chỉ chụp được một bức tại một thời điểm. Bức ảnh thứ i có thể bắt đầu chụp từ thời điểm ai trở đi và phải chụp xong không muộn hơn thời điểm bi. Thời điểm bắt đầu chụp mỗi bức có thể là số thực bất kỳ.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên n và t, trong đó n là số bức ảnh cần chụp và t là thời gian chụp mỗi bức ảnh.

Mỗi dòng trong n dòng tiếp theo mô tả khoảng thời gian dành cho một bức ảnh, gồm hai số nguyên không âm a và b: a là thời điểm sớm nhất có thể bắt đầu chụp bức ảnh đó, và b là thời điểm mà bức ảnh phải được chụp xong.

Dữ liệu ra

In ra yes nếu có thể chụp được cả n bức ảnh, ngược lại in ra no.

Ràng buộc

  • 1≤n≤104, 1≤t≤105.
  • 0≤a, a+t≤b≤109.

Ví dụ

Input Output Giải thích
2 10
0 15
5 20
yes Chụp bức thứ nhất trong [0,10], bức thứ hai trong [10,20].
2 10
1 15
0 20
no Bức thứ nhất phải bắt đầu trong [1,5]. Chụp bức thứ hai trước thì nó phải xong không muộn hơn 5, nhưng sớm nhất nó xong lúc 10; chụp sau thì nó bắt đầu từ 11 trở đi và xong từ 21>20.
2 10
5 30
10 20
yes Chụp bức thứ hai trong [10,20], rồi bức thứ nhất trong [20,30]. Nếu bắt đầu ngay bức thứ nhất ở thời điểm 5 thì sẽ không kịp chụp bức thứ hai.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0