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

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.

Link đọc đề trên VNOJ

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