Khối Phô Mai Của FJ

Đ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 có một khối phô mai hình lập phương nằm trong hệ tọa độ 3 chiều, kéo dài từ $(0, 0, 0)$ đến $(N, N, N)$ với $2 \leq N \leq 1000$ . FJ thực hiện $Q$ thao tác cắt ( $1 \leq Q \leq 2 \cdot 10^{5}$ ), mỗi thao tác loại bỏ một khối phô mai đơn vị $1 \times 1 \times 1$ tại tọa độ $(x, y, z)$ đến $(x + 1, y + 1, z + 1)$ với $0 \leq x, y, z < N$ .

Sau mỗi thao tác cắt, đếm số cách đặt một viên gạch $1 \times 1 \times N$ sao cho viên gạch không chồng lên phô mai còn lại. Viên gạch có thể xoay theo các trục và mọi đỉnh phải có tọa độ nguyên trong khoảng $[0, N]$ cho cả ba trục.

Dữ liệu vào

Dòng đầu: hai số nguyên $N$ và $Q$ .
$Q$ dòng tiếp theo, mỗi dòng chứa ba số nguyên $x$ , $y$ , $z$ - tọa độ khối cần cắt.

Dữ liệu ra

Sau mỗi thao tác cắt, in ra một số nguyên - số cách đặt viên gạch hợp lệ.

Ràng buộc

Test $2$ - $4$ : $N \leq 10$ , $Q \leq 1000$
Test $5$ - $7$ : $N \leq 100$ , $Q \leq 1000$
Test $8$ - $16$ : Không có ràng buộc thêm

Ví dụ

Input	Output	Giải thích
2 5 0 0 0 1 1 1 0 1 0 1 0 0 1 1 0	0 0 1 2 5	Với $N = 2$ , mỗi viên gạch có kích thước $1 \times 1 \times 2$ . Sau khi cắt 5 khối, có 5 vị trí đặt hợp lệ.

Bình luận

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