Editorial for Trồng hoa
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
Gọi :
- \(f[i]\) là vị trí nhỏ nhất mà đoạn (\(f[i], i\)) là một khóm hoa đạt tiêu chuẩn
- \(g[i\)] là độ dài lớn nhất của khóm hoa đạt tiêu chuẩn từ nằm trong đoạn (\(1, i\))
Để tính \(f[i]\) tốn \(O(n ^ 2)\), chúng ta có thể giảm đpt xuống \(O(nlog)\) bằng IT hoặc RMQ nhưng time sẽ hơi chặt, \(O(n)\) nếu dùng deque
=> \(answer = max(i - f[i] + 1, g[f[i] - 1])\);
Comments