Kiểm soát dịch bệnh

Xem PDF



Tác giả:
Dạng bài
Ngôn ngữ cho phép
C#, C++, Clang, Clang++, Cobol, D, Groovy, Haskell, Java, JS, Kotlin, Lua, Node JS, ObjectiveC, OCaml, Output, Pascal, PHP, Prolog, Pypy, Pypy 3, Ruby, Rust, Scala, Scratch, Swift
Điểm: 600 (p) Thời gian: 1.0s Bộ nhớ: 1G Input: bàn phím Output: màn hình

Để phòng ngừa dịch cúm gia cầm mới, Bộ Nông nghiệp và phát triển nông thôn nghiên cứu,
tìm hiểu cách thức lây lan của một loại virus mới, làm cơ sở để lên phương án phòng chống.
Qua một thời gian nghiên cứu các nhà khoa học phát hiện ra cơ chế lây lan rất đơn giản sau
đây: Trước hết, vùng lãnh thổ khảo sát được biểu diễn bởi một bảng kích thước \(𝑛 × 𝑚\) được
chia thành lưới ô vuông đơn vị. Các cột của bảng được đánh số từ 1 tới \(𝑛\), từ trái qua phải và
các dòng của bảng được đánh số từ 1 tới \(𝑚\), từ dưới lên trên. Ô nằm trên giao của cột \(𝑖\)
dòng \(𝑗\) được gọi là ô (\(𝑖,𝑗\)). Khi tại ô (\(𝑖,𝑗\)) có virus thì sau một đơn vị thời gian virus sẽ lây lan
sang các ô chung cạnh và chung đỉnh với ô đó.

Trên vùng lãnh thổ khảo sát, người ta quy hoạch \(𝑘\) khu đất để nuôi gia cầm. Mỗi khu là một
hình chữ nhật chiếm trọn một số ô của bảng và các cạnh song song với cạnh của bảng. Khu
thứ \(𝑖\) xác định bởi ô trái dưới (\(𝑎_𝑖, 𝑏_𝑖\)) và ô phải trên (\(𝑐_𝑖, 𝑑_𝑖\)). Các hình chữ nhật này không nhất
thiết rời nhau vì có một số gia cầm có thể sống chung trên một vùng đất.

Yêu cầu: Với cơ chế lây lan của virus đã biết và bản đồ các khu đất đã quy hoạch để nuôi các
gia cầm, hãy viết một chương trình để trả lời nhanh câu hỏi: Sau thời điểm \(𝑡\) tính từ lúc phát
hiện virus tại ô (\(𝑥_0, 𝑦_0\)) có bao nhiêu ô trong các khu quy hoạch bị lây virus. Giả thiết rằng ô
(\(𝑥_0, 𝑦_0\)) không nằm trong bất kỳ khu đất quy hoạch nào và thời điểm xuất hiện virus được
tính là 0.

Input

  • Dòng đầu là 5 số \(𝑛, 𝑚, 𝑘, 𝑥_0\)\(𝑦_0\) (\(1 \leq 𝑥_0 \leq 𝑛; 1 \leq 𝑦_0 \leq 𝑚\));
  • Dòng thứ \(i\) trong \(k\) dòng tiếp theo chứa 4 số \(𝑎_𝑖, 𝑏_𝑖, 𝑐_𝑖, 𝑑_𝑖\) (\(1 \leq 𝑎_𝑖 \leq 𝑐_𝑖 \leq 𝑛; 1 \leq 𝑏_𝑖 \leq 𝑑_𝑖 \leq 𝑚\));
  • Dòng tiếp theo chứa số \(𝑞\) là số các câu hỏi cần trả lời (\(1 \leq 𝑞 \leq 𝑚𝑎𝑥(𝑛, 𝑚)\));
  • Dòng cuối cùng chứa \(q\) số \(𝑡_1,𝑡_2, … ,𝑡_𝑞\) là thời điểm tương ứng với các câu hỏi, mỗi số có giá trị không lớn hơn \(10^6\).

Output

  • Gồm một dòng chứa \(𝑞\) số lần lượt là kết quả trả lời của 𝑞 câu hỏi.

Scoring

  • Subtask \(1\) (\(50\%\) số điểm): \(𝑛, 𝑚 \leq 1000; 1 \leq 𝑘 \leq 100; 1 \leq 𝑞 \leq 100\);
  • Subtask \(2\) (\(50\%\) số điểm): \(𝑛, 𝑚 \leq 10^6; 1 \leq 𝑘 \leq 400\);

Example

Test 1

Input
6 6 2 1 1
2 2 4 4
4 4 6 6
3
2 5 4 
Output
4 17 12
Note


Bình luận


  • -4
    tranminhkhoi    9:16 p.m. 15 Tháng 10, 2020

    Ai giai bai nay giup minh voi


    • 6
      biot_ductoan    11:23 a.m. 28 Tháng 6, 2020

      cho mình xin sol bài này với ạ :((

      1 phản hồi

      • 5
        zipdang04    10:42 a.m. 28 Tháng 6, 2020 đã chỉnh sửa

        có một sự nhầm lẫn nhẹ về X và Y :))

        huhu đáng lẽ AC onsite 🙁

        1 phản hồi

        • 0
          SPyofgame    10:16 a.m. 28 Tháng 6, 2020

          Bài này có thuật \(O(k^2 + polylog(max(n, m)) + q)\) thì anh thêm 50 test \(k \leq 10^4\) luôn cho máu anh :))


          • 7
            cuom1999    9:55 a.m. 26 Tháng 6, 2020

            Bộ test đã được bổ sung. 6 bài đã chuyển từ AC sang TLE. Các bạn nộp lại nhé

            2 phản hồi