Đếm số cặp có tổng bằng S bằng Bảng băm

Mục tiêu kiến thức

• Áp dụng cấu trúc ánh xạ std::map để đếm tần suất các giá trị số nguyên lớn trong thời gian O(N log N).
• Kỹ thuật quét một lượt (One-pass Counting) để đếm số cặp thỏa mãn điều kiện mà không cần xét lại.
• Tránh hiện tượng tràn số nguyên khi tổng số cặp có thể đạt tới N(N-1)2 ≈ 5 · 10⁹ (vượt quá kiểu int 32-bit).

Mô tả bài toán

Hệ thống cân bằng tải truyền thông của AI Empire Academy tiếp nhận N gói tín hiệu với cường độ A₁, A₂, …, A_N (1 ≤ N ≤ 10⁵, -10⁹ ≤ A_i ≤ 10⁹).

Một cặp tín hiệu (i, j) được gọi là tương thích nếu:

• 1 ≤ i < j ≤ N (hai gói tín hiệu ở vị trí khác nhau).
• Tổng cường độ của chúng bằng đúng một giá trị mục tiêu S: A_i + A_j = S.

Bạn hãy viết chương trình đếm xem có tổng cộng bao nhiêu cặp chỉ số (i, j) tương thích.

Quy ước nộp bài

• Chỉ cần viết một chương trình đọc stdin và in ra stdout. Bài này không yêu cầu viết hàm.
• Không dùng cout để in lời nhắc trước khi đọc dữ liệu. Lời nhắc sẽ lọt vào stdout và làm bài sai.
• Chỉ in đúng nội dung ở mục Output. Không in thêm nhãn, dòng trống hay ký tự thừa.
• Output được so khớp từng ký tự, phân biệt chữ hoa/thường và dấu câu.

Ràng buộc

• 1 ≤ N ≤ 10⁵.
• -10⁹ ≤ A_i ≤ 10⁹.
• -2 · 10⁹ ≤ S ≤ 2 · 10⁹.
• Thời gian chạy: 1000ms.
• Bộ nhớ tối đa: 256MB.