I - school competition 1

Quiz

https://atcoder.jp/contests/tkppc4-1/tasks/tkppc4_1_i

AC Code

https://atcoder.jp/contests/tkppc4-1/submissions/6601047

解法

• editorialの通り
  • https://drive.google.com/file/d/1CApCqwK7Hfgu81nqysUaPxSU2INI7l6R/view
• ただ、配列D, Uの定義は
• D[i] = 数列B内にあるA[i]「未満」の個数
• U[i] = 数列B内にあるA[i]「を越える」の個数
• が正しい。P<Q<R<Sに等号は含まないため

学び

• 1点固定の全探索
• 事前準備によるさらなる高速化 (D, U, Uの累積和)

Note

手で書くと分かってくる