priority_queue lower_bound 遅い _GLIBCXX_DEBUG 

#ifdef LOCAL
    #define _GLIBCXX_DEBUG
    #define __clock__
#else
    #pragma GCC optimize("Ofast")
#endif
  • 私のコードは上記を定義している。基本的に便利だが、困ることもある
  • 以前、_GLIBCXX_DEBUGが有効だとpriority_queueが遅いことにハマったことがある
  • 今回はソート済みの配列Aをlower_boundするときも同様に遅くなることに出くわした
  • 具体的にはN=100000ほどのデータで2秒では終わらなくなる

コンテスト中に「なぜか遅い！？」時にすべきムーブ

  • 上記問題と出くわしたのはコンテスト外だったので助かった。コンテスト中だったら焦る
  • ローカルだけの問題だと断定するために、AtCoderのコードテストにコードとN=100000のデータを入力し、TLEしないことを確認する
  • または_GLIBCXX_DEBUGを消す（これは1度出会ってないと無理だろう）