大和証券プログラミングコンテスト2022 Spring (AtCoder Regular Contest 138) C - Rotate and Play Game (600)
うまくやることで値の大きい方から半分を取れそう
取る値の閾値を求めておく
閾値以下の値を1、それ以外を-1として累積和を取る
ある位置から見ていったときに途中で値が0未満にならなければOK
最小値を取れるセグ木を準備して累積和の値をそのまま入れる
それぞれの位置から以下を行う
自身の右側での値を取得する
最後の累積和から自身の右の累積和を引く
これが0未満なら不可能
左側の最小値を取得する
左右の和が0未満だったり右側の最小値が左の最小値未満だったりしたら不可能