PHÁT MẠNG

Xem dạng PDF

Gửi bài giải

Điểm: 1,00 (OI)
Giới hạn thời gian: 2.0s
Giới hạn bộ nhớ: 256M
Input: stdin
Output: stdout

Dạng bài
Ngôn ngữ cho phép
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Thành phố T phát triển dựa trên hệ thống phủ sóng của các mạng 4G, thành phố hiện có n điểm phát mạng đánh số từ 1 đến n, khoảng cách giữa 2 điểm ij|ij|. Biết được rằng, điểm thứ i khi phát thì chỉ phát được đến những điểm j sao cho Ai|ij|Bi hay nói cách khác, điểm i chỉ phát được trong khoảng cách từ Ai đến Bi. Độ cao của điểm thứ iHi. 2 điểm phát mạng ij được xem là liên thông nếu điểm i có thể phát mạng cho j và ngược lại, chiều cao chênh lệch của 2 điểm liên thông càng lớn thì độ nhiễu càng cao. Vì thế chủ tịch thành phố muốn tính độ chênh lệch chiều cao lớn nhất giữa các cặp liên thông trong 1 đoạn bất kì. Cho q truy vấn, mỗi truy vấn gồm 2 số lr yêu cầu bạn tìm 2 số ij (li<jr) sao cho liên thông với nhau đồng thời |HiHj| đạt giá trị lớn nhất.

Input

  • Dòng đầu tiên ghi số n (1n2105);
  • n dòng tiếp theo, dòng thứ i chứa Hi Ai Bi (1Hi109 1AiBin)
  • Dòng tiếp theo là số q biểu thị số truy vấn (1q2105).
  • q dòng tiếp theo, dòng thứ i là các số liri biểu diễn truy vấn thứ i (1lirin).
  • Output

  • Gồm q dòng, dòng thứ i là cao chênh lệch lớn nhất giữa 1 cặp liên thông trong đoạn từ li đến ri (nếu không tồn tại thì in ra 1).

Sample Input

Copy
5
10 2 4
1 1 1
2 1 3
1 1 1
100 1 1
5
1 2
2 3
1 3
1 4
1 5

Sample Output

Copy
-1
1
8
8
99

SUBTASK

  • 50 số test có 1n,q300
  • 30 số test có 1n,q2000
  • 20 số test còn lại không có ràng buộc gì thêm.

Bình luận

Hãy đọc nội quy trước khi bình luận.


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