Quiz
https://atcoder.jp/contests/agc005/tasks/agc005_b
Submit
https://atcoder.jp/contests/agc005/submissions/4611400
Note
- 解説放送の通り「値aを最小値とする区間をいくつ作れるか」と捉え直す
- ここの解説も詳しい https://misteer.hatenablog.com/entry/AGC005-B
setをほぼ初めて使った
- 要素を入れていくと、入れる度に内部でソートされる
- 値1のindex, 値2のindex... と順にsetに入れつつ答えを計算していく
- 賢い
- 途中でlower_boundを使う箇所がある
- vectorと同様にlower_bound(ALL(A), val) と書いたら手元で通ったが、提出後にTLE
- なんとsetにはlower_boundというメソッドが生えている
//auto it = lower_bound(ALL(se), index); auto it = se.lower_bound(index);
- こちらを使えばTLEせずに通った
学び
- set
