Kỳ thi HSG Duyên hải và Đồng bằng Bắc Bộ 2022 - Tin học - Khối 11

Cấu trúc dữ liệu là nội dung rất quan trọng trong khoa học máy tính. Trong chương trình giảng dạy cho các lớp chuyên Tin, nội dung cấu trúc dữ liệu được đưa vào nhiều chuyên đề. Một bài toán thao tác trên bảng được dùng để kiểm tra khả năng tổ chức dữ liệu và linh hoạt trong xử lí như sau: Cho một bảng số gồm \(m\) hàng và \(n\) cột, các hàng được đánh số từ trên xuống dưới từ \(1\) đến \(m\), các cột được đánh số từ trái sang phải từ \(1\) đến \(n\), ô nằm giao giữa hàng \(i\) (\(1 \leq i \leq m\)) và cột \(j\) (\(1 \leq j \leq n\)) gọi là ô \((i, j)\) và có giá trị ban đầu là \(a_{ij}\). Cần thực hiện \(Q\) thao tác trên bảng số, mỗi thao tác thuộc một trong hai loại:

• Thao tác loại \(1\) có dạng: \(1 \ x \ y \ u \ v \ w\) có nghĩa là với mỗi ô nằm trong hình chữ nhật có ô trái trên là ô \((x, y)\) và ô phải dưới là ô \((u, v)\) sẽ được cộng thêm \(w\);
• Thao tác loại \(2\) có dạng: \(2 \ x \ y \ u \ v\) có nghĩa là cần đưa ra tổng giá trị của các ô nằm trong hình chữ nhật có ô trái trên là ô \((x, y)\) và ô phải dưới là ô \((u, v)\).

Input

• Dòng đầu chứa ba số nguyên dương \(m\), \(n\), \(Q\) (\(m, n \leq 500\));
• Dòng thứ \(i\) (\(1 \leq i \leq m\)) trong \(m\) dòng sau chứa \(n\) số nguyên không âm \(a_{i1}, a_{i2}, \ldots, a_{in}\) (\(a_{ij} \leq 10 ^ 9\)).
• Dòng thứ \(k\) (\(1 \leq k \leq Q\)) trong \(Q\) dòng sau mô tả thao tác thứ \(k\). Nếu là thao tác loại \(1\), dòng gồm năm số nguyên \(1\), \(x\), \(y\), \(u\), \(v\), \(w\) (\(1 \leq x \leq u \leq m\); \(1 \leq y \leq v \leq n\); \(0 \leq w \leq 10 ^ 9\)), nếu là thao tác loại \(2\), dòng gồm bốn số nguyên \(2\), \(x\), \(y\), \(u\), \(v\) (\(1 \leq x \leq u \leq m\); \(1 \leq y \leq v \leq n\)).

Output

• Ghi ra thiết bị chuẩn một số dòng, mỗi dòng tương ứng là câu trả lời cho thao tác loại \(2\) lần lượt xuất hiện trong file dữ liệu vào.

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(Q \leq 100\);
• Subtask \(2\) (\(30\%\) số điểm): \(Q \leq 10 ^ 5\) và tất cả thao tác loại \(1\) xuất hiện trước các thao tác loại \(2\);
• Subtask \(3\) (\(20\%\) số điểm): \(Q \leq 10 ^ 4\);
• Subtask \(4\) (\(20\%\) số điểm): \(Q \leq 10 ^ 5\).

Example

2 3 3
0 0 0
0 0 0
2 1 1 2 3
1 1 1 2 3 1
2 1 1 2 2      

0
4        

Để trang trí hội trường cho buổi khai mạc Duyên Hải năm 2022, Ban tổ chức đã sử dụng \(n\) đèn, nếu coi mỗi đèn là một đỉnh của đồ thị và dây nối giữa các đèn là cạnh thì hệ thống đèn tương ứng như một cây. Ban tổ chức đã ghi chép lại dãy các thông tin \(b_{1},b_{2},…,b_{n}\), trong đó \(b_{i} (1\le i\le n)\) tương ứng là số dây nối với đèn thứ \(i\), hay nói một cách khác \(b_{i}\) là bậc của đỉnh \(i\). Vì một lí do nào đó, Ban tổ chức đã vô tình làm mất thông tin của một số phần tử trong dãy thông tin \(b_{1},b_{2},…,b_{n}\). Để khôi phục lại các thông tin, Ban tổ chức đã nhờ đến Đào Quang Thái Dương (là cựu học sinh Chuyên Trần Phú, Huy chương Đồng APIO 2020). Rất nhanh chóng, Dương đã đếm được số lượng cách khác nhau điền thông tin vào các phần tử bị khuyết để nhận được dãy vẫn là dãy bậc của một cây nào đó.

Yêu cầu: Gọi s là số lượng cách điền thỏa mãn, hãy tính \(s\) % \((10^{9}+7)\), trong đó % là phép chia lấy dư để kiểm tra kết quả của Dương.

Input

• Dòng đầu chứa số nguyên dương \(n\);
• Dòng thứ hai chứa n số nguyên \(b_{1},b_{2},…,b_{n}\), trong đó \(1 \leq b_{i} \leq n-1\) hoặc \(b_{i}=-1\) cho biết thông tin đỉnh \(i\) bị mất.

Output

• In ra một số nguyên là giá trị \(s \% (10^9+7)\).

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(n\le 6\);
• Subtask \(2\) (\(20\%\) số điểm): \(n\le 10\);
• Subtask \(3\) (\(20\%\) số điểm): \(n\le 100\);
• Subtask \(4\) (\(20\%\) số điểm): \(n\le 10^{4}\);
• Subtask \(5\) (\(20\%\) số điểm): \(n\le 10^{6}\).

Example

3
-1 -1 1

2

Các nhà khảo cổ mới phát hiện ra một khu Hoàng Thành được xây dựng từ nhiều thế kỷ trước. Theo nhận định ban đầu, Hoàng Thành gồm nhiều căn phòng khép kín bởi bốn bức tường song song hoặc vuông góc với nhau. Để tiến hành nghiên cứu, các nhà khảo cổ đã xây dựng bản đồ các bức tường của khu Hoàng Thành. Cụ thể, bản đồ được mô tả trên mặt phẳng toạ độ Đề các vuông góc \(Oxy\), trong đó các bức tường là các đoạn thẳng song song với một trong hai trục tọa độ. Theo các dữ liệu thu thập được, có \(n\) căn phòng được đánh số từ \(1\) đến \(n\), căn phòng thứ \(i\) (\(1\le i\le n\)) là một hình chữ nhật có tọa độ trái dưới là \((x_{i},y_{i})\) và tọa độ phải trên là \((u_{i},v_{i})\). Bốn bức tường tương ứng là các đoạn thẳng nối tọa độ \((x_{i},y_{i})\) với \((x_{i},v_{i})\), \((x_{i},v_{i})\) với \((u_{i},v_{i})\), \((u_{i},v_{i})\) với \((u_{i},y_{i})\) và \((u_{i},y_{i})\) với \((x_{i},y_{i})\). Hai đoạn thẳng mô tả hai bức tường của hai phòng khác nhau không có điểm chung. Một thiết bị đặc biệt được các nhà khảo cổ sử dụng để khảo sát khu Hoàng Thành. Thiết bị nhỏ gọn nhưng mỗi khi cần điều khiển thiết bị để vượt qua một bức tường là rất khó khăn. Với một giả định, ban đầu thiết bị được đặt tại tọa độ \((x_{s},y_{s})\) và cần di chuyển tới tọa độ \((x_{f},y_{f})\), các nhà khảo cổ muốn tính toán số bức tường ít nhất cần vượt qua khi điều khiển thiết bị.

Yêu cầu: Cho các thông tin về khu Hoàng Thành và \(m\) giả định, với mỗi giả định hãy giúp các nhà khảo cổ tính toán số bức tường ít nhất cần vượt qua khi điều khiển thiết bị.

Input

• Dòng đầu gồm hai số nguyên dương \(n, m\).
• Dòng thứ \(i\) (\(1\le i\le n\)) trong \(n\) dòng tiếp theo gồm bốn số \(x_{i},y_{i},u_{i},v_{i}\) mô tả căn phòng thứ \(i\) (\(-10^{9}<x_{i}<u_{i}<10^{9};-10^{9}<y_{i}<v_{i}<10^{9}\)).
• Dòng thứ \(j\) (\(1\le j\le m\)) trong \(m\) dòng tiếp theo, mỗi dòng mô tả một giả định gồm bốn số nguyên \(x_{s},y_{s},x_{f},y_{f}\) (\(-10^{9}<x_{s},y_{s},x_{f},y_{f}<10^{9}\)). Điểm \((x_{s},y_{s})\), \((x_{f},y_{f})\) không nằm trên bất kì đoạn thẳng nào mô tả các bức tường của khu Hoàng Thành.

Output

• Ghi ra thiết bị ra chuẩn gồm \(m\) số, mỗi số là đáp án cho truy vấn tương ứng trong dữ liệu vào.

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(n,m\le 10^{2}\).
• Subtask \(2\) (\(40\%\) số điểm): \(n,m\le 10^{4}\).
• Subtask \(3\) (\(30\%\) số điểm): \(n,m\le 10^{6}\).

Example

3 2
1 0 6 4
2 1 4 3
7 2 9 5
3 2 8 3
8 3 0 0

3
1