Phá Rừng

Đ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

Farmer John đang phát triển đất nông nghiệp trong Khu Rừng Đỏ-Đen chứa $N$ cây trên trục số. Mỗi cây $i$ nằm tại vị trí $x_{i}$ . Các quy định môi trường đặt ra $K$ ràng buộc: mỗi ràng buộc yêu cầu ít nhất $t_{i}$ cây phải còn lại trong đoạn $[l_{i}, r_{i}]$ . Khu rừng ban đầu thỏa mãn tất cả ràng buộc. Tìm số cây tối đa có thể chặt mà vẫn đảm bảo tất cả ràng buộc.

Dữ liệu vào

Dòng đầu: $T$ ( $1 \leq T \leq 10$ ) là số test case.
Mỗi test case:
- Dòng $1$ : Hai số nguyên $N$ và $K$ .
- Dòng $2$ : $N$ số nguyên $x_{1}, x_{2}, \dots, x_{N}$ - vị trí các cây.
- $K$ dòng tiếp theo: Ba số nguyên $l_{i}$ , $r_{i}$ , $t_{i}$ .
$1 \leq N \leq 10^{5}$ , $1 \leq K \leq 10^{5}$ , $- 10^{9} \leq x_{i}, l_{i}, r_{i} \leq 10^{9}$ .
Tổng $N$ và tổng $K$ qua tất cả test case $\leq 3 \cdot 10^{5}$ .

Dữ liệu ra

Mỗi test case in ra một số nguyên - số cây tối đa có thể chặt.

Ràng buộc

Test $2$ - $3$ : $N, K \leq 16$
Test $4$ - $5$ : $N, K \leq 1000$
Test $6$ - $7$ : Tất cả $t_{i} = 1$
Test $8$ - $11$ : Không có ràng buộc thêm

Ví dụ

Input	Output	Giải thích
3 7 1 8 4 10 1 2 6 7 2 9 3 7 2 8 4 10 1 2 6 7 2 9 3 1 10 1 7 2 8 4 10 1 2 6 7 2 9 3 1 10 4	4 4 3	Test 1: Cần giữ ít nhất 3 cây trong $[2, 9]$ , nên chặt tối đa 4 cây.

Bình luận

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