trang chủ / đề bài / icpc25_mt_g

Vườn đá

Đề bài

Mô tả

Ngày xưa có một tu viện được bao quanh bởi một khu vườn đá rộng lớn. Các nhà sư sắp xếp khu vườn thành một lưới n×m: mỗi ô hoặc là một khoảnh cát trống (.), hoặc là một hòn đá nhỏ (#). Mỗi buổi sáng, họ quan sát từng phần của khu vườn để tìm sự hài hoà.

Với các nhà sư, một phần của khu vườn được gọi là cân bằng nếu ở mỗi cột của phần đó, số hòn đá không vượt quá một giới hạn thiêng k.

Cho sơ đồ hiện tại của khu vườn và q câu hỏi của các nhà sư. Mỗi câu hỏi gồm ba số nguyên w, h và k. Với câu hỏi đó, hãy đếm số phần hình chữ nhật kích thước w×h cân bằng, tức là số hình chữ nhật con gồm w hàng và h cột mà mỗi cột của nó có không quá k hòn đá.

Một hình chữ nhật con là một khối liên tiếp gồm w hàng liên tiếp và h cột liên tiếp.

Dữ liệu vào

  • Dòng đầu tiên gồm ba số nguyên n, m và q: kích thước khu vườn và số câu hỏi.
  • Mỗi dòng trong n dòng tiếp theo là một xâu độ dài m chỉ gồm các ký tự . và #.
  • Mỗi dòng trong q dòng tiếp theo gồm ba số nguyên w, h và k.

Dữ liệu ra

Với mỗi câu hỏi, in ra trên một dòng một số nguyên: số hình chữ nhật con cân bằng kích thước w×h.

Ràng buộc

  • 1≤n×m≤5×105, 1≤q≤105.
  • 1≤w≤n, 1≤h≤m, 0≤k≤5.

Ví dụ

Input Output Giải thích
3 3 6
..#
#..
...
1 1 0
1 2 1
2 1 1
3 1 1
2 2 0
3 3 1
7
6
6
3
1
1
Câu hỏi đầu tiên đếm các ô trống: có 7 ô. Với w=h=2, k=0 chỉ có hình vuông ở góc dưới bên phải là không chứa đá.
5 5 4
.#.##
..#..
...#.
#.#.#
.#...
3 3 2
2 2 1
3 1 0
2 3 2
9
16
2
12
Với k=2 mọi hình 3×3 đều cân bằng (9 hình). Với w=3, h=1, k=0 chỉ có 2 đoạn cột dài 3 không có đá.

Bình luận

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

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0