Variation of problem B in div2 round 1063

Revision en4, by elizabeth_zou_fanboi, 2025-11-10 22:17:21

If the operation in this question (round 1063 B) is changed as follows: Choose any two integers l and r such that 1≤l≤r≤n. If, for ALL i in range (l,r) , min(pl,pr)<pi<max(pl,pr) holds true then set si to 1 for ALL i in range (l,r)

Is there solution to this variation. I spent whole contest on this variation (misread the question). I want to know whether solution exists in O(n) or not.

My O(n*5) solution that I am not sure is correct:

my code

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en6 English elizabeth_zou_fanboi 2025-11-11 12:11:21 1720
en5 English elizabeth_zou_fanboi 2025-11-10 22:19:30 8 (published)
en4 English elizabeth_zou_fanboi 2025-11-10 22:17:21 5 Tiny change: '+1]<maxx){//bug\n ' -> '+1]<maxx){\n '
en3 English elizabeth_zou_fanboi 2025-11-10 22:16:31 39
en2 English elizabeth_zou_fanboi 2025-11-10 22:14:52 2863 Tiny change: 's correct:' -> 's correct:\n<spoiler summary="my code">\n...\n\nhello \n</spoiler>'
en1 English elizabeth_zou_fanboi 2025-11-10 22:01:00 911 Initial revision (saved to drafts)