Đếm cặp có tổng bằng 0

Xem PDF
Tác giả:
nvatuan
Dạng bài
Điểm: 200 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Cho dãy số \(A\) có \(N\) số nguyên. Hãy đếm số cặp \((i,j)\) sao cho \(A_i + A_j = 0\), với \(i < j\).

Input

  • Dòng đầu tiên chứa một số nguyên dương \(N\) \((1 \leq N \leq 2*10^5)\)
  • Dòng thứ hai chứa dãy số \(A\) gồm \(N\) số nguyên cách nhau bởi một ký tự khoảng trống. \((|A_i| \leq 10^9)\)

Output

  • In ra một số nguyên duy nhất, là số cặp phần tử trong dãy \(A\) mà có tổng là 0.

Scoring

  • Subtask \(1\) (\(25\%\) số điểm): \(N \leq 10^4\), \(|A_i| \leq 10^6\).
  • Subtask \(2\) (\(60\%\) số điểm): \(N \leq 2*10^5\), \(|A_i| \leq 10^6\).
  • Subtask \(3\) (\(100\%\) số điểm): \(N \leq 2*10^5\), \(|A_i| \leq 10^9\).

Example

Test 1

Input 
3
-2 0 2
Output 
1
Note

Chỉ tồn tại một cặp phần tử \((1, 3)\) tương ứng với \(A_1 + A_3 = -2 + 2 = 0\).

Test 2

Input 
6
-2 -1 0 0 1 2
Output 
3

Bình luận


  • 0
    trantrikien69    11:42 a.m. 16 Tháng 5, 2022

    Đếm phân phối như này đúng không ạ, toàn bị segmentation fault

    || Code
    var n,i:longint; ans:qword;
    f,t:array [-2000000..2000000] of longint;
    begin
    readln(n);
    for i:=1 to n do
    begin
    read(f[i]);
    if t[-f[i]] > 0 then
    begin
    inc(ans,t[-f[i]]);
    end;
    inc(t[f[i]]);
    end;
    writeln(ans);
    end.
    ||

    • 2 bình luận nữa