CAKE (TS10 PTNK 2023)

Điểm: 1500 (thành phần)

Thời gian: 1.0s

Bộ nhớ: 256M

Input: CAKE.INP

Output: CAKE.OUT

Dạng bài

Cho một bánh có kích thước $N\times M$ ô vuông. Trên bánh có $4\times K$ quả dâu. Bạn được biết vị trí của các quả dâu. Được phép cắt $2$ nhát, $1$ nhát ngang, $1$ nhát dọc sao cho chia bánh thành $4$ phần. Mà $4$ phần này phải có số lượng dâu bằng nhau. Có bao nhiêu cách cắt như thế?

Input, output and subtasks:

Input CAKE.INP:

Dòng đầu tiên ghi $3$ số nguyên dương $N,M,K$ ( $2\leq M,N\leq 10^9,1\leq K\leq 5\cdot 10^5$ )
$4 \cdot K$ dòng tiếp theo chứa tọa độ của các quả dâu.

Output CAKE.OUT:

Gồm $1$ dòng ghi số nguyên là số cách cắt thõa mãn.

Subtask:

$60\%$ số test có giới hạn $N,M\leq 10^4, K\leq 4\cdot 10^4$ .
$40\%$ số test còn lại không có giới hạn gì thêm.

Sample:

Sample input CAKE.INP:

Sample output CAKE.OUT:

Giải thích:

Mô tả input mẫu (mỗi ô đánh dấu dựa vào các ký tự $1,0$ , ô ghi số $1$ là ô có chứa dâu):

0001
0100
0101

Bình luận

Không có bình luận nào.