AtCoder Beginner Contest 188 D – Snuke Prime を解いた記録
問題の概要
高橋くんは株式会社すぬけが提供しているサービス群を利用しようとしている．
株式会社すぬけは「すぬけプライム」なる支払いプランを用意しており，これを使うと\(1\)日\(C\)円ですべてのサービスを追加料金なしで利用できる．
すぬけプライムの加入及び脱退は，どちらも1日の初めまたは終わりに自由に行える．また，すぬけプライムの加入及び脱退は何回でもできる．
高橋くんは\(N\)個のサービスを利用しようとしている．
\(i\)個目のサービスは，\(a_{i}\)日目のはじめから\(b_{i}\)日目の終わりまで利用する予定である．
すぬけプライムに加入していない間は，\(i\)個目のサービスを利用するときに\(1\)日\(c_{i}\)円支払う必要がある．
サービスを利用するために高橋くんが支払う金額の最小値を求めよ．
制約
- \(1 \leq N \leq 2 \times 10^{5}\)
- \(1 \leq C \leq 10^{9}\)
- \(1 \leq a_{i} \leq b_{i} \leq 10^{9}\)
- \(1 \leq c_{i} \leq 10^{9}\)
- 入力はすべて整数
解法
\(1 \leq a_{i} \leq b_{i} \leq 2 \times 10^{5}\)であればいもす法で一撃ですが，あいにく\(1 \leq a_{i} \leq b_{i} \leq 10^{9}\)となっているためいもす法をそのまま使うことはできません．
しかし，いもす法で使う配列を連想配列（C++ならstd::map）に置き換えれば，いもす法の要領で答えにたどり着けます．
具体的には，連想配列\(memo\)に対して
- \(memo[a_{i}] += c_{i}\)
- \(memo[b_{i}+1] -= c_{i}\)
とする処理をすべての\(i\)について行い，\(memo\)を先頭から順に確認して料金計算を行えばよいです．
実装例
感想
当初はmapに要素を追加するときの場合分け（\(a_{i}\)などをキーとする要素が連想配列にあるか否かで処理を分ける）をしていましたが，場合分けしているコードを投げている間はずっとWAが出ていました．
コンテスト中はPythonで無理やりACしましたが，4回もWAを出したせいもあってパフォーマンスがかなぐり犠牲になりました．かなしい