trang chủ / bài tập / confvenue

Hội nghị năm mới

Đề bài

Mô tả

Một hội nghị gồm n bài giảng sắp được tổ chức. Ban tổ chức đang cân nhắc giữa hai địa điểm AB, và sẽ chọn đúng một địa điểm để tổ chức toàn bộ hội nghị.

Với mỗi bài giảng i, diễn giả đã đăng ký hai khung giờ: nếu hội nghị diễn ra ở địa điểm A thì bài giảng i kéo dài từ thời điểm sai đến eai, còn nếu ở địa điểm B thì bài giảng i kéo dài từ sbi đến ebi.

Hai bài giảng được gọi là chồng lấn nếu chúng có chung ít nhất một thời điểm. Chính xác hơn, bài giảng diễn ra trong khoảng [x,y] chồng lấn với bài giảng diễn ra trong khoảng [u,v] khi và chỉ khi max(x,u)min(y,v).

Một người tham dự có thể dự trọn vẹn một tập bài giảng s nếu không có hai bài giảng nào trong s chồng lấn nhau. Việc một tập bài giảng có dự được hay không phụ thuộc vào địa điểm được chọn.

Tập bài giảng s được gọi là nhạy cảm với địa điểm nếu ở một trong hai địa điểm thì người tham dự dự được trọn vẹn s, còn ở địa điểm còn lại thì không.

Ban tổ chức hài lòng khi và chỉ khi không tồn tại tập bài giảng nào nhạy cảm với địa điểm. Hãy xác định xem ban tổ chức có hài lòng hay không.

Dữ liệu vào

  • Dòng đầu chứa số nguyên n, số bài giảng của hội nghị.
  • n dòng tiếp theo, dòng thứ i chứa bốn số nguyên sai, eai, sbi, ebi.

Dữ liệu ra

In ra YES nếu ban tổ chức hài lòng, ngược lại in ra NO.

Ràng buộc

  • 1n100000
  • 1sai,eai,sbi,ebi109
  • saieaisbiebi

Ví dụ

Input Output Giải thích
2
1 2 3 6
3 4 7 8
YES Ở địa điểm A hai bài giảng là [1,2][3,4], ở địa điểm B[3,6][7,8]. Cả hai địa điểm đều cho cùng một kết luận: hai bài giảng không chồng lấn, nên mọi tập bài giảng đều dự được ở cả hai nơi.
3
1 3 2 4
4 5 6 7
3 4 5 5
NO Tập {1,3} là nhạy cảm với địa điểm: ở A hai bài giảng là [1,3][3,4], chúng chung thời điểm 3 nên không dự được cả hai; ở B chúng là [2,4][5,5], rời nhau nên dự được.
6
1 5 2 9
2 4 5 8
3 6 7 11
7 10 12 16
8 11 13 17
9 12 14 18
YES Mỗi cặp bài giảng chồng lấn ở A khi và chỉ khi chồng lấn ở B, nên không có tập nào nhạy cảm với địa điểm.

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.46 awk 1.3.4 gcc 16.1.0 csc 6.12.0.200 g++ 16.1.0 g++-themis 16.1.0 g++17 16.1.0 g++20 16.1.0 g++23 16.1.0 clang++ 22.1.6 dmd 2.112.0 dart 3.12.1 gforth 0.7.3 gfortran 12.2.0 go 1.26.3 groovyc 5.0.6 javac 25.0.3 node 26.2.0 kotlinc 2.3.21 sbcl 2.2.9 lua 5.4.8 nim 2.2.10 fpc 3.2.2 fpc-themis 3.2.2 perl 5.36.0 php 8.5.6 pike 8.0 pypy3 7.3.23 python3 3.14.5 racket 8.7 ruby 4.0.5 rustc 1.96.0 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 tclsh 8.6 bun 1.3.14 deno 2.8.1 v 0.5.1 zig 0.16.0