AtCoderBeginnerContest426 C問題300点 「Upgrade Required」
https://gyazo.com/83df7a2ec990e4b4f64f261c77fc730d
問題概要
制約
気持ち
解法
ある $ i番目の操作 において、 $ X_i 以下のバージョンの PC をすべて $ Y_i にしたときを考えます。
このとき、 $ N個の PC のバージョンはすべて $ X_i より真に大きいことがわかります。
$ j ( > i) 番目以降の操作において、 $ X_j < X_i となるような操作はおこなわなくてよいことがわかります。
そもそもすべてのパソコンが $ X_iより大きくなっているためです。
このことから、 $ i回目までの操作において、最小の OS バージョンを $ mとしたとき
$ mは操作を重ねていくにつれ単調に増加し、かつ $ m > X_j となるような操作 $ jは気にしなくてよいことがわかります。
よって、実際にバージョンアップをシミュレーションしてしまえばいいです。
$ m は単調に増加し、かつ $ m \leq N となるため、計算量は $ O(N+Q) で済みます。
計算量
$ O(N+Q)
新たな学び
反省点
コード
code: cpp
func solve() {
N, Q := mio.NextInt(), mio.NextInt()
dp := make([]int, N+1)
for i := 0; i <= N; i++ {
}
l := 1
for q := 0; q < Q; q++ {
x, y := mio.NextInt(), mio.NextInt()
if x < l {
mio.PrintLn(0)
continue
}
ans := 0
for j := l; j <= x; j++ {
}
l = x
mio.PrintLn(ans)
}
}
// ------------------------------------------------------------
// ------------------------------------------------------------
func main() {
solve()
defer mio.Flush()
}