らての精進日記

修行をします

aoj2317:Class Representative Witch

解法

まず、日本語の問題文のはずなのにまったく題意が分からないので、サンプルから察する。

S>Tとなるケースがめんどくさそうでいやだなあとなるが、よく考えたら負の方向にも糸を伸ばしてS*=-1,T*=-1とすれば、S< Tのケースにできる。

あとは、偶奇で分けて累積和をとる。
upper_boundとかも組み合わせていい感じにやると答えが求めまる。正直、図を描いて実際にどのような式を立てればいいのか実験してみるのが一番楽。


問題文が最悪だし、そもそも問題自体がバグが出やすくてコーナーケースも生えやすいので、控えめに言って二度とこういう問題はやりたくない。

コード