ABC060: C - Sentou

問題

C: Sentou - AtCoder Beginner Contest 060 | AtCoder

解答

順に回見ていき、お湯を出す時間が前の人と重なる場合と重ならない場合があるので、その2通りの場合分けが生じる。 前の人がお湯を出した区間をstd::pairで管理する。 出す時刻がとなることに注意して、

1. 今の人がお湯を出す区間が前の人と重なる場合は、区間を]で更新する。
2. 重ならない場合は、前の人の区間分を答えに加算してから、区間を]で更新する。

一番最後に残った区間を答えに加算する。

int main() {
  int N; ll T; cin >> N >> T;

  ll d;
  cin >> d;
  assert(d == 0);

  pair<ll, ll> p {0, T};
  ll ans = 0;  
  rep(i, N - 1) {
    ll t; cin >> t;
    if (p.second < t) {
      // Split
      ans += p.second - p.first;
      p = std::make_pair(t, t + T);
    } else {
      // Merge
      p = std::make_pair(p.first, t + T);
    }
  }

  ans += p.second - p.first;

  std::cout << ans << "\n";
  
  return 0;
}