DOJ logoDOJ
Problems
Recently added problemsSaved problemsWorkbooks
CategoriesDLCContestsGroupsTeamsBoard
Ranking
Solved Problem RankingStreak rankingDOJ Power ranking
Status
Call for TasksLoginRegister
DOJ logoDOJ

Community online judge with OI-style subtask scoring, Elo ratings, and Discord account linking.

Problems
ProblemsCategories
Community
ContestsRankingBoardNoticesHost an external contestGuide
Account
LoginRegisterJudge Status
Policy
Terms of ServiceDLC RulesPrivacyAPI documentationLanguage runtimesContest rank rewardsRating and performance
© 2026 DOJ
All rights reserved
Editorial

Sliding Window RMQ

Back to problem

Editorial

For subtask 111, generate the sequence and scan every window of length KKK. For subtask 222, overwrite the oldest value in a circular array of size KKK and read the root of a segment tree for the current minimum.

For the full problem, keep candidate indices in a deque. Remove the front index if it is outside the current window. Before appending a new value AiA_iAi​, remove all values at the back that are at least AiA_iAi​. Then append the new value. Deque values increase strictly from front to back, so the front gives the current minimum. A removed value can never be better than the newer value in a later window. Every element enters and leaves the deque at most once, giving O(N)O(N)O(N) time and O(K)O(K)O(K) space.

A0A_0A0​ itself is not part of any window. Compute aAi−1+caA_{i-1}+caAi−1​+c with 64-bit integers because it can exceed the 32-bit range.

Solution written by GPT6