ABC214 C - Distribution - かんプリンの学習記録

問題概要
解説
提出プログラム
感想

問題概要

${N}$ 人が円周上に並んでいる． ${i}$ 番目の人は時刻 ${t}$ に宝石をもらうと ${S_i}$ 時間後にその宝石を ${(i+1)}$ 番目の人に渡す．ただし， ${(N+1)=1}$ とする．また，高橋君は時刻 ${T_i}$ に ${i}$ 番目の人に宝石を渡す．すべての ${i}$ について， ${i}$ 番目の人が初めて宝石をもらう時刻を求めよ．

${1\leq N\leq 2×10^5\\ 1\leq S_i,T_i\leq 10^9}$

解説

優先度付きキューを用います．

最初に優先度付きキューに ${(T_i,i)}$ を入れます(人 ${i}$ が時刻 ${T_i}$ に宝石をもらった)．キュー内の最小値 ${(t,i)}$ を取り出し，まだ人 ${i}$ が宝石をもらったことが無いならその ${t}$ が答えです．その後， ${(t+S_i,i+1)}$ をキューに入れます．これを繰り返すことですべての答えを求めることができます．