VOBIGNUM - Tính toán số lớn

Giới hạn
  • Thời gian: 1.0s
  • Bộ nhớ: 1536MB
  • Mã nguồn: 50000 bytes

Cho N số nguyên (có thể âm, N ≤ 1000). Các số được đánh số từ 0 đến N-1, số thứ i được ký hiệu là A(i). Mỗi số có không quá 1000 chữ số. Bạn cần trả lời Q truy vấn (Q ≤ 10 5 ). Mỗi truy vấn có dạng: X 1 Y 1 C 1 X 2 Y 2 C 2 , trong đó:

  • X 1 , Y 1 , X 2 , Y 2 là các số nguyên nằm trong khoảng [0, N-1].
  • C 1 , C 2 là các phép toán, có thể là +, - hoặc *

Nhiệm vụ của bạn là kiểm tra A(X 1 ) C 1 A(Y 1 ) có bằng A(X 2 ) C 2 A(Y 2 ) có bằng nhau hay không. Ví dụ:

  • N = 3
  • Dãy số: 10 20 30
  • Truy vấn: 0 2 + 1 1 +
  • Bạn cần kiểm tra A(0) + A(2) có bằng A(1) + A(1) hay không.

Input

  • Dòng đầu chứa 2 số nguyên dương N, Q.
  • N dòng tiếp theo, dòng thứ i chứa số nguyên A(i).
  • Q dòng tiếp theo, mỗi dòng chứa X 1 , Y 1 , C 1 , X 2 , Y 2 , C 2 mô tả truy vấn.

Output

Gồm Q dòng, mỗi dòng in ra YES nếu 2 số bằng nhau, và NO nếu 2 số khác nhau.

Giới hạn

  • Có 40% số test N ≤ 500, Q ≤ 5000, mỗi số trong input không quá 100 chữ số
  • Trong tất cả các test N ≤ 1000, Q ≤ 100,000; mỗi số trong input không quá 1000 chữ số
  • Thời gian chạy cho mỗi test: 1s, riêng test đề bài có giới hạn thời gian chạy là 0.5s.

Chú ý:

  • Trong thời gian thi, bài của bạn chỉ được chấm với test đề bài.
  • Nếu bài của bạn chạy đúng trên máy mình, nhưng sai khi nộp lên SPOJ, bạn có thể kiểm tra ở ideone . Chú ý khi submit lên ideone, để chế độ Secret để người khác không đọc được code của bạn.

Example

Input:

4 3
1
2
3
4 0 1 - 2 3 - 0 3 + 1 2 + 0 3 * 1 2 *

Output:

YES YES NO


  • Người up: voj
  • Nguồn bài: VO 2015