Bài A- Codeforces Round #453 (.Div 2)

Bài A:

Đề bài: Pig đang thăm 1 người bạn.

Nhà của Pig tọa lạc tại vị trí 0 và nhà của bạn Pig tọa lạc tại vị trí m trên trục tọa độ.

Pig có thể sử dụng teleport (một phương tiện di chuyển) để đi học trục tọa độ.

Để sử dụng teleport, Pig nên đi đến một điểm nhất định (cái điểm mà teleport đang tọa lạc) và chọn nơi đó để di chuyển ; mỗi lần teleport, có một điểm rightmost để nó có thể đưa Pig đến đó, điểm này được biết như là điểm giới hạn của teleport.

  Chính thức là, một teleport tọa lạc tại vị trí x với giới hạn y có thể chuyển Pig từ điểm x đến bất kỳ điểm nào trong đoạn [x;y]; bao gồm cả biên.

Xác định, liệu rằng Pig có thể thăm nhà bạn của anh ấy mà chỉ sử dụng teleport hay không, hay anh ấy nên sử dụng xe hơi của mình.

Đầu vào: 

+ Dòng đầu tiên chứa hai số nguyên n và m (1<=n<=100,1<=m<=100) , ở đây n và m lần lượt là số teleport và địa điểm nhà của bạn của Pig.

+ n dòng tiếp theo chứa thông tin về các teleport

+ Dòng thứ i chứa hai số nguyên a(i) và b(i) (0<=a(i)<=b(i)<=m), ở đây a(i) là vị trí của teleport thứ i và b(i) là giới hạn của nó.

Đảm bảo rằng a(i)>=a(i-1) với mỗi i (2<=i<=n).

Đầu ra:

+ In ra YES nếu có một đường đi từ nhà Pig đến nhà của bạn Pig mà chỉ sử dụng các teleport, và in ra NO trong trường hợp ngược lại.

Bạn có thể in ra các ký tự YES hay NO tùy ý. (tức là không phân biệt hoa hay thường).

Ví dụ 1:

Đầu vào:

3 5

0 2

2 4

3 5

Đầu ra:

YES

Ví dụ 2:

Đầu vào:

3 7

0 4

2 5

6 7

Đầu ra:

NO

Chú ý:

+Ví dụ đầu tiên được biểu diễn như hình vẽ dưới đây:

Pig có thể sử dụng teleport thứ nhất từ nhà cậu ấy (điểm 0) đến điểm 2, sau đó sử dụng teleport thứ hai đi từ điểm 2 đến điểm 3, và cuối cùng sử dụng teleport thứ 3 đi từ điểm 3 đến điểm 5, nơi mà anh bạn của Pig đang sống.

+ Ví dụ thứ 2 được biểu diễn như hình vẽ dưới đây:

Bạn có thể nhìn thấy rằng không có đường nào từ nhà của Pig đến nhà bạn của Pig mà chỉ sử dụng các teleports.

Hướng dẫn: Chú ý rằng nếu chúng ta có thể đến được một điểm x nào đó, thì tất cả những điểm chúng ta đến được phải <=x. Vì vậy, chúng ta có thể giả sử điểm rightmost, nơi mà chúng ta đến. Thế thì nếu điểm này có thể sử dụng teleport (nếu điểm này ở bên phải của teleport), chúng ta sẽ thử di chuyển nó (nếu giới hạn của teleport là điểm right của điểm hiện tại, thì di chuyển nó đến đó). Và cuối cùng chúng ta kiểm tra rằng điểm rightmost nơi mà chúng ta đến có bằng m hay không?

Lời giải:

#include <stdio.h>
int n,m,c,l,r;
int main(){
    scanf("%d%d",&n,&m);
    while(n--)scanf("%d%d",&l,&r),c=(l<=c&&r>c)?r:c;
    printf(c>=m?"YES":"NO");
    return 0;
}