trang chủ / đề bài / icpc26_mb_b

Máy quét lưới cổ đại

Đề bài

Mô tả

Để mở khóa căn phòng trung tâm của một phế tích ngoài hành tinh, đoàn thám hiểm phải giải mã một phiến đá cổ được mô hình hóa thành một ma trận hai chiều gồm N hàng và M cột chứa các số nguyên dương. Các hàng được đánh số từ 1 đến N (từ trên xuống dưới) và các cột được đánh số từ 1 đến M (từ trái sang phải).

Một mapat là một hình vuông có các cạnh song song với các trục, được xác định bởi ô ở góc dưới bên phải (i,j) (gọi là ô tiêu điểm) và một số nguyên L là độ dài cạnh (1≤L≤min(i,j)). Mapat này phủ tất cả các ô (x,y) thỏa mãn i−L+1≤x≤i và j−L+1≤y≤j.

Giá trị năng lượng của một mapat được tính bằng S×cell(i,j), trong đó S là tổng tất cả các phần tử trong hình vuông L×L và cell(i,j) là giá trị của ô tiêu điểm (i,j).

Với một hàng i cố định và một độ dài cạnh L cố định (i≥L), gọi Aj là giá trị năng lượng của mapat có ô tiêu điểm (i,j), với j≥L. Một dãy mapat liên tiếp dọc theo hàng i được xác định bởi hai biên [st,dr] với L≤st≤dr≤M, và tổng gộp của nó là Ast+Ast+1+⋯+Adr.

Bạn cần xử lý q truy vấn loại 1 và p truy vấn loại 2:

  • Loại 1 (L,i,maxVal): tìm độ dài lớn nhất (dr−st+1) của một dãy mapat liên tiếp có cạnh L trên hàng i có tổng gộp ≤maxVal. Nếu không có dãy nào như vậy, đáp án là 0.
  • Loại 2 (L,i,minVal,maxVal): đếm số cặp (st,dr) với L≤st≤dr≤M sao cho tổng gộp nằm trong đoạn [minVal,maxVal].

Dữ liệu vào

  • Dòng đầu tiên chứa bốn số nguyên N, M, q, p (1≤N,M≤1000; 1≤p+q≤8000).
  • N dòng tiếp theo, mỗi dòng chứa M số nguyên mô tả ma trận (các phần tử là số nguyên dương ≤400).
  • q dòng tiếp theo, mỗi dòng chứa 3 số nguyên L, i, maxVal mô tả một truy vấn loại 1 (0<maxVal<1015).
  • p dòng tiếp theo, mỗi dòng chứa 4 số nguyên L, i, minVal, maxVal mô tả một truy vấn loại 2 (0≤minVal<maxVal<1015).

Trong mọi truy vấn, 1≤L≤i≤N và L≤M.

Dữ liệu ra

Đầu tiên in ra q dòng: đáp án của từng truy vấn loại 1 theo thứ tự đã cho. Sau đó in ra p dòng: đáp án của từng truy vấn loại 2 theo thứ tự đã cho.

Ràng buộc

  • 1≤N,M≤1000.
  • 1≤p+q≤8000.
  • Các phần tử của ma trận là số nguyên dương ≤400.
  • 1≤L≤i≤N, L≤M.
  • Loại 1: 0<maxVal<1015.
  • Loại 2: 0≤minVal<maxVal<1015.

Ví dụ

Input Output Giải thích
4 4 2 0
1 3 5 2
4 3 1 2
7 8 1 1
2 2 3 1
2 4 20
1 4 16
1
3
Truy vấn 1: L=2, hàng 4: A2=(7+8+2+2)·2=38, A3=(8+1+2+3)·3=42, A4=(1+1+3+1)·1=6; chỉ dãy [4,4] có tổng 6≤20. Truy vấn 2: L=1, hàng 4: A=(4,4,9,1); dãy [2,4] có tổng 14≤16, còn [1,3] có tổng 17.
3 3 2 2
2 1 3
1 2 1
3 1 2
2 3 5
1 2 3
1 3 4 9
2 2 7 12
0
1
3
2
Ví dụ bổ sung (không có trong đề gốc). Loại 1, L=2, hàng 3: A2=7·1=7, A3=6·2=12, đều lớn hơn 5 nên đáp án 0. Loại 1, L=1, hàng 2: A=(1,4,1), đáp án 1. Loại 2, L=1, hàng 3: A=(9,1,4), các tổng gộp là 9,1,4,10,5,14, có 3 tổng (9,4,5) thuộc [4,9]. Loại 2, L=2, hàng 2: A2=6·2=12, A3=7·1=7, các tổng 12,7,19, có 2 tổng thuộc [7,12].

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