3SUM trên đoạn

Điểm: 1,00 (OI)

Giới hạn thời gian: 2.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Cho mảng $A$ gồm $N$ phần tử. Trả lời $Q$ truy vấn: với đoạn $[a, b]$ , đếm số bộ ba $(i, j, k)$ với $a \leq i < j < k \leq b$ sao cho $A [i] + A [j] + A [k] = 0$ .

Dữ liệu vào

Dòng đầu: $N$ và $Q$ .
Dòng thứ hai: $N$ số nguyên.
$Q$ dòng tiếp: $a_{i}$ , $b_{i}$ .

Dữ liệu ra

$Q$ dòng, mỗi dòng số bộ ba thỏa mãn.

Ràng buộc

$1 \leq N \leq 5000$
$1 \leq Q \leq 10^{5}$
$| A_{i} | \leq 10^{6}$

Ví dụ

Input	Output	Giải thích
7 3 2 0 -1 1 -2 3 3 1 5 2 4 1 7	2 1 4	[1,5]: (2,0,-2) và (0,-1,1). [2,4]: (0,-1,1).

Bình luận

Không có bình luận tại thời điểm này.