Free Contest 147 - EVENTUPLES

View as PDF
Submit solution
Points: 0.70 (partial)
Time limit: 1.0s
Memory limit: 512M
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

Lưu ý: các bạn không nhập, xuất dữ liệu bằng file kể cả khi đề bài có yêu cầu. Đọc, ghi dữ liệu được thực hiện ở stdin và stdout.

Comments

Please read the guidelines before commenting.


  • 0
    vudinhlong  commented on Nov. 14, 2024, 8:00 a.m.

    Mình xin góp ý với người ra đề về bộ test một chút nhé, bài này với giới hạn n và q lên đến 1e5, để pass đc 1s thì mỗi truy vấn chỉ nên được trả lời trong thời gian O(1) (sử dụng tổng tiền tố tối ưu hoá tổ hợp bằng qhd), chứ hiện tại code for trâu l đến r đếm số chẵn số lẻ vẫn pass hết thì có vẻ như bộ test chưa chặt. (1 for cho số truy vấn, 1 for từ l đến r là đpt(n*q) đã đạt đến 10^10, vẫn pass 1s thì cá nhân mình thấy test hơi lỏng)

    Bài này để hài hoà thì ý kiến mình như thế này: Có thể chia theo 3 subtask với các hướng tiếp cận khác nhau:

    • Subtask 1 (30%): N, q <=100: for mỗi q, mỗi q thì làm 3 for (ĐPT O(N^3.Q) = 10^8)

    • Subtask 2 (40%): N, q <=10^4: Bắt buộc kéo giảm đpt về O(N*Q): Đếm số số chẵn, số lê trong đoạn [l; r] rồi áp dụng công thức tổ hợp

    • Subtask 3 (30%): N, q <=10^5: Bắt buộc xử lý mỗi truy vấn trong O(1): Sử dụng qhd tối ưu hoá sub2

    Rất mong nhận được ý kiến phản hồi từ người ra đề và các bạn cùng làm bài này nhé. Cảm ơn các bạn.


  • -1
    Ceaturs  commented on May 2, 2024, 3:10 p.m. ← edit 4

    mấy đứa sai test2 là do thiếu trường hợp ra 0

    hint:

    if(r - l <3 || even==0 || odd<2) => output = 0


  • 0
    DinhVantung0611  commented on March 7, 2024, 7:22 a.m. ← edit 2

    .


  • -1
    ving3011  commented on June 21, 2023, 3:24 a.m. ← edit 3

    mọi người cho mình hỏi, mình làm cứ bị sai test số 2 là sao v ạ. bài nộp của mình:

    enter image description here