VMMIRROR - Đuổi bắt trong thế giới gương huyền thoại
Giới hạn- Thời gian: 1.0s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
Là lập trình viên xuất sắc nhất của đất nước 1D, bạn được tin tưởng giao phó nhiệm vụ vô cùng quan trọng và nguy hiểm: Truy bắt tên tội phạm quốc gia TSZ.
Theo những nguồn tin mới nhất mà bạn nhận được, TSZ đã đặt chân đến vùng đất của những chiếc gương huyền thoại và đang lẩn trốn ở đó. Vùng đất những chiếc gương huyền thoại có thể tưởng tượng giống như một đường thẳng (bạn đang ở trên đất nước 1D mà), tại một số vị trí trên vùng đất, có đặt những chiếc gương thần kỳ. Trong khoảnh khắc (có thể coi như 0 đơn vị thời gian), bạn có thể di chuyển từ 1 điểm bất kỳ trên vùng đất, đến ảnh của nó qua 1 gương bất kỳ (Chú ý rằng tại vùng đất huyền thoại, ảnh của một vật luôn là điểm đối xứng với vật đó qua gương, các gương khác không làm ảnh hưởng hay che vị trí của ảnh của vật). Vì vậy, vùng đất này là một nơi lý tưởng để TSZ có thể lẩn trốn, do chỉ trong 0 đơn vị thời gian, TSZ có thể di chuyển từ A, đến B (B là ảnh của A qua gương G), rồi từ B đến C (C là ảnh của B qua gương G')... (với G, G' là 2 gương nào đó trong số N gương trên vùng đất huyền thoại).
Trong hình minh họa, có 5 gương:
- Gương g1 ở tọa độ 3
- Gương g2 ở tọa độ 4
- Gương g3 ở tọa độ 9
- Gương g4 ở tọa độ 12
- Gương g5 ở tọa độ 13
Trong 0 đơn vị thời gian, TSZ có thể di chuyển từ A đến D như sau: từ A đến B (ảnh của A qua g1), rồi từ B đến C (ảnh của B qua g3), rồi từ C đến D (ảnh của C qua g4).
Bạn đã có trong tay bản đồ của vùng đất những chiếc gương huyền thoại. Vì vậy bạn đã biết được vị trí chính xác của tất cả N chiếc gương. Để lên kế hoạch bắt TSZ, bạn cần phải biết được TSZ có thể di chuyển như thế nào. Bạn đã chuẩn bị sẵn Q câu hỏi, mỗi câu hỏi cho biết TSZ có thể di chuyển từ vị trí start đến vị trí target trong 0 đơn vị thời gian hay không.
Input
- Dòng 1: Số nguyên dương N - số gương.
- Dòng 2: N số nguyên dương x i , số thứ i cho biết vị trí của gương thứ i.
- Dòng 3: Số nguyên dương Q - số câu hỏi
- Q dòng tiếp theo, dòng thứ i chứa 2 số nguyên start i và target i
Output
Với mỗi câu hỏi, in ra 1 dòng duy nhất. Dòng thứ i in ra YES nếu TSZ có thể di chuyển từ start i đến target i , ngược lại in ra NO.
Chấm điểm
- Bài của bạn sẽ được chấm trên thang điểm 100. Điểm mà bạn nhận được sẽ tương ứng với % test mà bạn giải đúng.
- Trong quá trình thi, bài của bạn sẽ chỉ được chấm với 1 test ví dụ có trong đề bài.
- Khi vòng thi kết thúc, bài của bạn sẽ được chấm với bộ test đầy đủ.
Giới hạn
- 1 ≤ N ≤ 10^5
- 0 ≤ x i ≤ 10^9
- 1 ≤ Q ≤ 10^5
- 0 ≤ start i , target i ≤ 10^9.
- Trong 20% test đầu tiên, N ≤ 5, Q ≤ 10
- Trong 40% test tiếp theo, N ≤ 100, Q ≤ 100
Example
Input: 5 3 4 9 12 13 4 1 11 5 13 6 7 7 7 Output: YES YES NO YES
- Người up: voj
- Nguồn bài: VM13 - Lãng Trung Hiếu