TLE-oj Cup Round 3 - Tổng bằng không

Điểm: 1700 (thành phần)

Thời gian: 0.5s

Bộ nhớ: 256M

Input: TRIPLE.inp

Output: TRIPLE.out

Tác giả:

Sunlight

Dạng bài

Cho một dãy số nguyên $a_1, a_2, ..., a_n$ và $q$ truy vấn, mỗi truy vấn gồm hai số nguyên dương $l, r$ , hãy tìm số bộ ba số nguyên $a_i, a_j, a_k$ sao cho $l \le i < j < k \le r$ và $a_i + a_j + a_k = 0$ .

Input, Output và Subtasks

Input: (TRIPLE.inp)

Dòng đầu tiên gồm hai số nguyên dương $n \le 5000$ và $q \le 10^5$ .
Dòng tiếp theo gồm $n$ số nguyên dương $a_1, a_2, ..., a_n$ ( $|a_i| \le 10^6$ ).
$q$ dòng tiếp theo, mỗi dòng gồm hai số nguyên dương $l, r$ mô tả mỗi truy vấn.

Output: (TRIPLE.out)

Gồm $q$ dòng, dòng thứ $i$ là kết quả truy vấn thứ $i$ .

Subtasks

Subtask 1 $(10\%)$ : $n, q \le 100$ .
Subtask 2 $(10\%)$ : $|a_i| \le 10$ .
Subtask 3 $(10\%)$ : $n, q \le 500$ .
Subtask 4 $(15\%)$ : $n \le 500$ .
Subtask 5 $(15\%)$ : $n, q \le 2000$ .
Subtask 6 $(15\%)$ : $n \le 2000$ .
Subtask 7 $(25\%)$ : Không có giới hạn gì thêm.

Sample

Input (TRIPLE.inp)

7 3
2 0 -1 1 -2 3 3
1 5
2 4
1 7

Output (TRIPLE.out)

2
1
4

Notes

Trong dãy có các bộ $(i, j, k)$ sau thỏa mãn $a_i + a_j + a_k = 0$ :
- $(1, 2, 5)$ .
- $(2, 3, 4)$ .
- $(3, 5, 6)$ .
- $(3, 5, 7)$ .

Bình luận

Không có bình luận nào.