Khôi Phục Dãy Nhị Phân Từ Truy Vấn Đếm Bit

Buổi 63 — Interactive & Constructive Graphs
Points
60
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
Uncategorized
Submissions
Đề 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.

Draft saved