VNU OLYMPIAD INFORMATICS 2022 - Post

View as PDF

Submit solution

Points: 1.00 (partial)
Time limit: 1.0s
Memory limit: 512M
Input: stdin
Output: stdout

Problem source:
VNUOI 2022
Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

In case the statement didn't load correctly, you can download the statement here: Statement


Comments

Please read the guidelines before commenting.



  • -13
    xero2409  commented on April 28, 2023, 5:03 a.m. edit 5

    This comment is hidden due to too much negative feedback. Show it anyway.


    • -5
      PM  commented on July 23, 2023, 2:39 a.m.

      This comment is hidden due to too much negative feedback. Show it anyway.


  • 30
    marvinthang  commented on March 19, 2022, 2:38 p.m. edited

    Thuật chuẩn:

    ~Binary Search~

    Check bằng quy hoạch động

    ~F_i~: có tồn tại trạng thái 1 người ở nhà thứ i không, nếu có tìm j lớn nhất thỏa mãn khoảng cách từ ~X_{i + 1}, .. X_j~ đến ~X_i \leq D~ thì ~ F_{i + 1}, .., F_j = true~.

    ĐPT: ~O(N^2 * \log_2 N~)

    Cải tiến:

    Sử dụng ~Sparse Table~ kết hợp ~Binary Search~ để tìm j, j thỏa mãn khi khoảng cách từ ~max(X_{i + 1}, .., X_j)~ và ~min(X_{i + 1}, .., X_j)~ đến ~X_i \leq D~.

    ĐPT ~O(N * log_2^2 N~)

    Code mẫu: Ideone