Khôi Phục Dãy Nhị Phân Từ Truy Vấn Đếm Bit
Points
60
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
Uncategorized
Đề bài
Một mảng nhị phân bí mật $B[1..N]$ gồm $N$ phần tử thuộc ${0, 1}$. Bạn đã thực hiện $Q$ truy vấn cảm biến đoạn; truy vấn thứ $i$ cho biết tổng số bit 1 nằm trong đoạn chỉ số $[l_i, r_i]$ nằm trong khoảng $[a_i, b_i]$ (tức $a_i \le \sum_{j=l_i}^{r_i} B[j] \le b_i$).
Hãy xác định xem có tồn tại mảng nhị phân $B$ nào thỏa mãn toàn bộ $Q$ truy vấn hay không. Nếu có, hãy in ra số lượng bit 1 ít nhất và nhiều nhất có thể có trong mảng $B$; ngược lại in ra -1.
Dữ liệu vào
- Dòng đầu tiên chứa hai số nguyên $N$ và $Q$ ($1 \le N \le 400$, $1 \le Q \le 500$).
- $Q$ dòng tiếp theo, mỗi dòng chứa bốn số nguyên $l_i, r_i, a_i, b_i$ ($1 \le l_i \le r_i \le N$, $0 \le a_i \le b_i \le r_i - l_i + 1$).
Dữ liệu ra
Nếu tồn tại mảng nhị phân hợp lệ, in ra trên một dòng hai số nguyên là tổng số bit 1 tối thiểu và tối đa có thể. Nếu các truy vấn mâu thuẫn nhau, in ra -1.
Ví dụ
| Input | Output |
|---|---|
| 5 3 1 3 1 2 3 5 2 3 2 4 1 2 |
2 4 |
Giới hạn
Thời gian: 1.0s, Bộ nhớ: 256MB.
Community Discussion