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


Submit solution

Points: 600 (partial)
Time limit: 1.0s
Memory limit: 1G

Author:
Problem types
Allowed languages
C++, Pascal

Để 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 \(𝑖\) và 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.

Dữ liệu

  • Dòng đầu là 5 số \(𝑛, 𝑚, 𝑘, 𝑥_0\) và \(𝑦_0\) (\(1 \le 𝑥_0 \le 𝑛; 1 \le 𝑦_0 \le 𝑚\));
  • Dòng thứ \(i\) trong \(k\) dòng tiếp theo chứa 4 số \(𝑎_𝑖, 𝑏_𝑖, 𝑐_𝑖, 𝑑_𝑖\) (\(1 \le 𝑎_𝑖 \le 𝑐_𝑖 \le 𝑛; 1 \le 𝑏_𝑖 \le 𝑑_𝑖 \le 𝑚\));
  • Dòng tiếp theo chứa số \(𝑞\) là số các câu hỏi cần trả lời (\(1 \le 𝑞 \le 𝑚𝑎𝑥(𝑛, 𝑚)\));
  • 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\).

Kết quả

  • 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.

Sample input

6 6 2 1 1
2 2 4 4
4 4 6 6
3
2 5 4

Sample output

4 17 12

enter image description here

Ràng buộc

  • Có 50% số lượng test ứng với 50% số điểm thỏa mãn điều kiện: \(𝑛, 𝑚 \le 1000; 1 \le 𝑘 \le 100; 1 \le 𝑞 \le 100\);
  • Có 50% số lượng test còn lại ứng với 50% số điểm thỏa mãn điều kiện: \(𝑛, 𝑚 \le 10^6; 1 \le 𝑘 \le 400\);

Comments


  • 0
    tranminhkhoi  commented on Oct. 15, 2020, 9:16 p.m.

    Ai giai bai nay giup minh voi


  • 2
    biot_ductoan  commented on June 28, 2020, 11:23 a.m.

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


    • -1
      SPyofgame  commented on June 28, 2020, 4:36 p.m. edited

      Approach: Rời rạc hóa ma trận ạ :v

      Đpt tối ưu nhất em biết được hiện tại là \(O(k^2 + polylog(max(n, m)) + q)\) mà hình như opt thêm tí nữa được


      • 1
        HilG  commented on June 29, 2020, 11:19 a.m.

        Dạ anh giải thích chi tiết hơn được ko ạ? Rời rạc hóa ma trận là gì và em có thể đọc ở đâu ạ? Với lại polylog là như thế nào ạ? Em cảm ơn.


        • -2
          SPyofgame  commented on June 29, 2020, 2:32 p.m. edit 5

          Rời rạc hóa ma trận là việc mình chia nó thành các hình con nhỏ hơn để tiện xử lí tính toán (nhưng mình không có tài liệu ở đâu cả :'( )

          \(O(Polylog())\) ở đây mình chỉ một độ phức tạp có dạng đa thức logarit, ví dụ \(O(log^5(k) + log(k \times n))\)


          • 1
            HilG  commented on June 29, 2020, 3:16 p.m.

            Dạ anh có thể chi tiết về việc áp dụng cái rời rạc hóa ma trận vào bài này ko ạ? Hay share code cho em đọc tham khảo với được ko ạ? Em cảm ơn


            • -2
              SPyofgame  commented on June 29, 2020, 4:54 p.m.

              Mình không biết làm dạng tổng quát đâu :'(( riêng bài này mình mới học thuật rời rạc hóa và đang viết editorial cho anh em, nhưng đợi mình viết bài khác trước đã ạ :(


  • 0
    zipdang04  commented on June 28, 2020, 10:42 a.m. edited

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

    huhu đáng lẽ AC onsite :(


    • -3
      SPyofgame  commented on June 28, 2020, 10:44 a.m.

      :> ông muốn thi lại với tui để cảm thấy đỡ hơn không


  • -3
    SPyofgame  commented on June 28, 2020, 10:16 a.m.

    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 :))


  • 3
    cuom1999  commented on June 26, 2020, 9:55 a.m.

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


    • 0
      CQTshadow  commented on June 28, 2020, 4:21 p.m.

      hồi sáng anh có quay video lại ko , cho em xin với ạ


    • -6
      SPyofgame  commented on June 26, 2020, 9:56 a.m.

      This comment is hidden due to too much negative feedback. Click here to view it.