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

Bóng bàn (bản dễ)

Đề bài

Mô tả

Bạn quản lý một tập các đoạn thẳng, ban đầu tập này rỗng. Các đoạn được đánh số theo thứ tự chúng được thêm vào: đoạn thêm vào đầu tiên có số hiệu 1, đoạn tiếp theo có số hiệu 2, v.v.

Từ đoạn (a,b) trong tập, ta có thể đi một bước sang đoạn (c,d) cũng thuộc tập khi và chỉ khi c<a<d hoặc c<b<d, tức là ít nhất một trong hai đầu mút của đoạn nguồn nằm hoàn toàn bên trong đoạn đích.

Tồn tại đường đi từ đoạn I1 tới đoạn I2 nếu có một dãy các bước đi liên tiếp bắt đầu từ I1 và kết thúc tại I2. Chú ý quan hệ này có hướng: đi được từ I1 sang I2 không có nghĩa là đi được theo chiều ngược lại.

Hãy xử lý n truy vấn thuộc hai loại:

  1. 1 x y (với x<y) — thêm đoạn (x,y) vào tập. Độ dài của đoạn mới được đảm bảo lớn hơn hẳn độ dài của mọi đoạn đã có trước đó.
  2. 2 a b (với ab) — trả lời: có đường đi từ đoạn số hiệu a tới đoạn số hiệu b hay không, xét trên tập các đoạn tại thời điểm truy vấn.

Dữ liệu vào

  • Dòng đầu chứa số nguyên n — số truy vấn.
  • n dòng tiếp theo, mỗi dòng chứa một truy vấn theo định dạng mô tả ở trên.

Dữ liệu ra

Với mỗi truy vấn loại 2, in ra YES hoặc NO trên một dòng riêng.

Ràng buộc

  • 1n100
  • Mọi số trong dữ liệu vào là số nguyên có giá trị tuyệt đối không vượt quá 109
  • Dữ liệu vào được đảm bảo hợp lệ: với truy vấn loại 2 thì ab và cả hai đoạn số hiệu a, b đều đã được thêm vào trước đó

Ví dụ

Input Output Giải thích
5
1 1 5
1 5 11
2 1 2
1 2 9
2 1 2
NO
YES
Với hai đoạn (1,5)(5,11): không có bước đi nào giữa chúng vì đầu mút 5 chung không nằm hoàn toàn bên trong đoạn kia, nên đáp án là NO. Sau khi thêm (2,9): từ (1,5) đi được sang (2,9)2<5<9, rồi từ (2,9) đi được sang (5,11)5<9<11, nên đáp án là YES.
9
1 1 4
1 5 20
1 11 30
1 29 60
1 59 100
1 100 200
2 1 5
2 1 6
2 2 5
NO
NO
YES
Đoạn (1,4) rời hẳn mọi đoạn khác nên không đi đâu được, hai truy vấn đầu cho NO. Từ đoạn 2=(5,20)11<20<30 nên sang được đoạn 3=(11,30); từ đó 29<30<60 nên sang được đoạn 4=(29,60); cuối cùng 59<60<100 nên tới được đoạn 5=(59,100), đáp án YES.

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