Thống kê doanh thu theo đoạn

Arrays Buổi 03 — Mảng 1 Chiều Buổi 08 — Contest Chặng 1
Points
18
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
Uncategorized
Submissions
Đề bài

Một cửa hàng ghi lại lợi nhuận ròng trong $N$ ngày liên tiếp, ngày thứ $i$ đạt $a_i$ (có thể âm nếu lỗ). Quản lý muốn thực hiện $Q$ truy vấn, mỗi truy vấn cho hai ngày $L, R$ ($1 \le L \le R \le N$) và yêu cầu tính tổng lợi nhuận từ ngày $L$ đến ngày $R$ cùng số ngày có lãi ($a_i > 0$) trong khoảng đó.

Dữ liệu vào

Dòng đầu chứa $N$ và $Q$. Dòng thứ hai chứa $N$ số nguyên $a_1, a_2, \dots, a_N$. $Q$ dòng tiếp theo, mỗi dòng gồm hai số $L, R$.

Dữ liệu ra

$Q$ dòng, mỗi dòng in hai số: tổng lợi nhuận và số ngày có lãi trong $[L, R]$.

Ví dụ
Input Output
5 2
10 -5 20 0 15
1 3
2 5
25 2
30 2
3 1
-1 -2 -3
1 3
-6 0
Giới hạn
  • $1 \le N, Q \le 10^5$
  • $|a_i| \le 10^9$
Draft saved