Truy vấn Tổng Thiếu

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.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 $n$ đồng xu với giá trị dương. Bạn cần trả lời $q$ truy vấn: với mỗi truy vấn $[a, b]$ , hỏi tổng nhỏ nhất không thể tạo thành bằng cách chọn một số đồng xu từ đoạn $[a, b]$ .

Dữ liệu vào

Dòng đầu chứa hai số nguyên $n$ và $q$ : số đồng xu và số truy vấn.

Dòng thứ hai chứa $n$ số nguyên $x_{1}, x_{2}, \dots, x_{n}$ : giá trị các đồng xu.

$q$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $a$ và $b$ : phạm vi đồng xu của truy vấn.

Dữ liệu ra

Với mỗi truy vấn, in ra một số nguyên: tổng nhỏ nhất không tạo được.

Ràng buộc

$1 \leq n, q \leq 2 \cdot 10^{5}$
$1 \leq x_{i} \leq 10^{9}$
$1 \leq a \leq b \leq n$

Ví dụ

Input	Output	Giải thích
5 3 2 9 1 2 7 2 4 4 4 1 5	4 1 6	Truy vấn 1: đồng xu [9,1,2], không tạo được 4. Truy vấn 2: đồng xu [2], không tạo được 1. Truy vấn 3: đồng xu [2,9,1,2,7], không tạo được 6.

Bình luận

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