ARC149 B - Two LIS Sum (500)
$ AのLISを最大化するためにソートするときの操作を考えると、$ BのLISは最大でも1しか減らないので全体としても減ることはない
なのでこの時の$ BのLISを求めるだけで良い
$ (A_i,B_i)のペアを昇順でソートする
この時の$ B側のLISを通常通りに求め、$ nを足したのが答え
ソートや各$ iでのLISを求める際の二分探索がボトルネックで$ \mathcal{O}(N \log N)
問題: https://atcoder.jp/contests/arc149/tasks/arc149_b
提出: https://atcoder.jp/contests/arc149/submissions/35347931
#ARC149 #500pt #B #ARC #AtCoder
#LIS #O(NlogN)