Рамазан quyết định bắt đầu một công việc kinh doanh nghiêm túc: trồng bắp cải.
Cánh đồng trồng bắp cải là một lưới ô vuông vô hạn. Mỗi ô có thể được trồng một cây bắp cải.
Рамазан chỉ trồng một phần cánh đồng. Anh dự định sử dụng một số khu đất hình chữ nhật, và hóa ra một số khu đất có thể giao nhau. Một ô thuộc vùng trồng nếu nó nằm trong ít nhất một hình chữ nhật.
Cụ thể, Рамазан chọn $n$ khu đất hình chữ nhật $(x_i^L,y_i^L,x_i^R,y_i^R)$, với $x_i^L\le x_i^R$, $y_i^L\le y_i^R$, $1\le i\le n$. Ô $(x,y)$ chứa bắp cải nếu tồn tại ít nhất một hình chữ nhật được chọn $i$, với $1\le i\le n$, sao cho $x_i^L\le x\le x_i^R$ và $y_i^L\le y\le y_i^R$.
Trước đây Рамазан từng là lập trình viên (và là người chiến thắng), nên anh quyết định sử dụng robot có trí tuệ nhân tạo để chăm sóc định kỳ vùng trồng. Một robot có thể phục vụ một đoạn ô nằm ngang tùy ý $(x_1^{robot},x_2^{robot},y^{robot})$, tức là tất cả các ô $(x,y)$ thỏa mãn $x_1^{robot}\le x\le x_2^{robot}$ và $y=y^{robot}$.
Điều quan trọng là robot chỉ di chuyển trên vùng trồng. Anh nhận ra rằng để giảm thiểu số robot, cần sử dụng những đoạn nằm ngang không thể mở rộng thêm. Рамазан sẽ sử dụng một robot trên đoạn ô $(x_1^{robot},x_2^{robot},y^{robot})$ nếu:
- Tất cả các ô $(x,y)$ thỏa mãn $x_1^{robot}\le x\le x_2^{robot}$ và $y=y^{robot}$ đều thuộc vùng trồng.
- Ô $(x_1^{robot}-1,y^{robot})$ không thuộc vùng trồng.
- Ô $(x_2^{robot}+1,y^{robot})$ không thuộc vùng trồng.
Nhiệm vụ của bạn là thu thập những thống kê quan trọng về các robot sẽ làm việc trên đồn điền. Ta nói rằng cặp $(x_1,x_2)$ được phục vụ ở hàng $y$ nếu tồn tại một robot làm việc đúng trên đoạn $(x_1,x_2,y)$.
- Tìm tất cả các cặp $(x_1,x_2)$ được phục vụ ở một hàng nào đó.
- Với mỗi cặp $(x_1,x_2)$ như vậy, tìm số hàng mà cặp đó được phục vụ.
- Với mỗi cặp $(x_1,x_2)$ như vậy, tìm số hàng liên tiếp lớn nhất mà cặp đó được phục vụ. Nói cách khác, tìm số $k$ lớn nhất sao cho tồn tại một đoạn gồm $k$ hàng liên tiếp $[y_1,y_2]$, với $y_2-y_1+1=k$, và với mọi hàng $y_1\le y\le y_2$, cặp $(x_1,x_2)$ được phục vụ ở hàng $y$.
Dữ liệu vào
Mỗi bộ kiểm thử gồm nhiều bộ dữ liệu. Dòng đầu tiên chứa một số nguyên $t$, với $1\le t\le200\,000$: số bộ dữ liệu. Tiếp theo là mô tả các bộ dữ liệu.
Dòng đầu tiên của mỗi bộ dữ liệu chứa một số nguyên $n$, với $1\le n\le200\,000$: số khu đất hình chữ nhật được chọn.
Mỗi dòng trong $n$ dòng tiếp theo chứa bốn số nguyên $x_i^L,y_i^L,x_i^R,y_i^R$, với $1\le x_i^L\le x_i^R\le10^9$ và $1\le y_i^L\le y_i^R\le10^9$: mô tả các khu đất hình chữ nhật được chọn.
Gọi $N$ là tổng các giá trị $n$ trên tất cả các bộ dữ liệu trong một bộ kiểm thử. Đảm bảo rằng $N\le200\,000$.
Dữ liệu ra
Với mỗi bộ dữ liệu, trước tiên in ra một số nguyên $p$, với $p\ge1$: số cặp $(x_1,x_2)$ được phục vụ ở một hàng nào đó.
Trong $p$ dòng tiếp theo, mỗi dòng in bốn số nguyên $x_1,x_2,cnt,k$, với $1\le x_1\le x_2\le10^9$ và $0\le cnt,k\le10^9$. Số $cnt$ phải bằng số hàng mà cặp $(x_1,x_2)$ được phục vụ. Số $k$ phải bằng số hàng liên tiếp lớn nhất mà cặp $(x_1,x_2)$ được phục vụ.
Tất cả các cặp $(x_1,x_2)$ phải khác nhau. Mỗi cặp được phục vụ ở một hàng nào đó phải được in đúng một lần. Có thể in các cặp theo thứ tự tùy ý.
Nhiệm vụ con
Với một bộ dữ liệu, gọi $w$ là chiều rộng cánh đồng, tức là $w=\max_{i=1}^{n}x_i^R$, và $h$ là chiều cao cánh đồng, tức là $h=\max_{i=1}^{n}y_i^R$.
| Nhiệm vụ con | Điểm | Giới hạn trên $n,N$ | Giới hạn trên $w,h$ | Giới hạn bổ sung | Nhiệm vụ con bắt buộc |
|---|---|---|---|---|---|
| $1$ | $4$ | $n=1$ | |||
| $2$ | $8$ | $h=1$ | |||
| $3$ | $8$ | $n\le30$, $N\le3000$ | $w,h\le10$ | $t\le100$ | Ví dụ |
| $4$ | $4$ | $w,h\le5000$, $\sum wh\le25\cdot10^6$ | Ví dụ, $3$ | ||
| $5$ | $8$ | $N\le3000$ | Ví dụ, $3$ | ||
| $6$ | $4$ | $N\le10\,000$ | Ví dụ, $3,5$ | ||
| $7$ | $8$ | Tất cả các $[x_i^L,x_i^R]$ giao nhau | $1$ | ||
| $8$ | $8$ | $y_i^L=1$ | $2$ | ||
| $9$ | $8$ | Các hình chữ nhật không giao nhau | $1$ | ||
| $10$ | $8$ | Với mọi $1\le i,j\le n$ và mọi $y\in[y_i^L,y_i^R]\cap[y_j^L,y_j^R]$, ta có $[x_i^L,x_i^R]\nsubseteq[x_j^L,x_j^R]$ | $1,9$ | ||
| $11$ | $8$ | Tất cả các đoạn $[x_i^L,x_i^R+1]$ hoặc lồng nhau, hoặc không giao nhau | $1$ | ||
| $12$ | $8$ | $N\le50\,000$ | Ví dụ, $3,5$–$6$ | ||
| $13$ | $8$ | $N\le100\,000$ | Ví dụ, $3,5$–$6,12$ | ||
| $14$ | $8$ | $N\le200\,000$ | Ví dụ, $1$–$13$ |
- Nếu trong một bộ kiểm thử, lời giải của bạn xác định sai tập các cặp $(x_1,x_2)$ được phục vụ ở một hàng nào đó, lời giải nhận kết quả “Sai đáp án”.
Nếu trong tất cả các bộ kiểm thử của nhiệm vụ con và các nhiệm vụ con bắt buộc, lời giải:
- Xác định đúng tập các cặp nhưng không phải tất cả các giá trị $cnt$ đều đúng, lời giải nhận $50\%$ số điểm của nhiệm vụ con.
- Xác định đúng tập các cặp và tất cả các giá trị $cnt$, nhưng không phải tất cả các giá trị $k$ đều đúng, lời giải nhận $75\%$ số điểm của nhiệm vụ con.
- Xác định đúng tập các cặp, tất cả các giá trị $cnt$ và tất cả các giá trị $k$, lời giải nhận $100\%$ số điểm của nhiệm vụ con.
Lưu ý rằng để nhận điểm một phần của nhiệm vụ con, vẫn cần in ra các giá trị $cnt$ và $k$ nào đó cho mỗi cặp $(x_1,x_2)$, nhưng chúng không nhất thiết phải đúng.
Ví dụ
Dữ liệu vào 1
4 2 2 2 3 3 3 3 4 4 2 2 1 2 3 1 2 3 2 4 2 2 4 5 3 4 9 7 2 9 9 10 7 1 9 7 7 2 1 2 9 5 1 6 8 4 5 7 6 1 8 4 10 1 6 3 6 1 2 7 3 4 1 7 1
Dữ liệu ra 1
3 2 3 1 1 2 4 1 1 3 4 1 1 2 1 3 1 1 2 2 2 1 4 2 4 2 2 2 9 4 2 3 9 2 2 7 9 3 3 6 1 4 2 2 1 6 1 1 1 7 3 2 2 2 4 2 4 7 2 1 5 6 2 1
Ghi chú
Bộ dữ liệu thứ nhất và thứ hai trong bộ kiểm thử của đề bài
Trong bộ dữ liệu thứ nhất, các robot sẽ được sử dụng trên những đoạn $(2,3,2)$, $(2,4,3)$, $(3,4,4)$. Vì vậy, các cặp $(2,3)$, $(2,4)$, $(3,4)$ được phục vụ ở một hàng nào đó, và mỗi cặp được phục vụ đúng một hàng.
Trong bộ dữ liệu thứ hai, các robot sẽ được sử dụng trên những đoạn $(2,2,1)$, $(2,4,2)$, $(2,2,3)$. Vì vậy, các cặp $(2,2)$, $(2,4)$ được phục vụ ở một hàng nào đó. Cặp $(2,2)$ được phục vụ ở các hàng $1,3$, còn cặp $(2,4)$ được phục vụ ở hàng $2$.
Bộ dữ liệu thứ ba và thứ tư trong bộ kiểm thử của đề bài