Submission #70542871

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

/////////////////// メイン ///////////////////

int main () {
  
  //////////////////// 入力 ////////////////////

  int n, c;
  long long m;
  cin >> n >> m >> c;

  // あとでデータを高速で追加できるように、
  // 2*n+1個分メモリ確保をしてからサイズをnにしておく
  vector<long long> a;
  a.reserve(2*n+1);
  a.resize(n);
  for (int i=0; i<n; i++) {
    cin >> a.at(i);
  }

  //////////////// 出力変数定義 ////////////////

  long long result = 0;

  //////////////////// 処理 ////////////////////

  // ソートして、小屋から2周分、人がいる位置を記録しておく、+3周目の1人目まで（番兵）
  sort(a.begin(),a.end());
  for (int i=0; i<n; i++) a.emplace_back(a.at(i)+m);
  a.emplace_back(a.at(0)+2*m);
  
  // この人の先からスタート、という人の番号
  int l = 0;

  // 最後に合う人の番号
  int r = c;

  // 1周をどこから初めても結果は同じはずなので、
  // 0スタートで1周ではなく、1人目の少し先スタートで1周する
  while (l<n) {
    
    // 最後に合う人の番号を求める
    r = max(r,l+c);
    while (a.at(r+1)==a.at(l+c)) r++;

    // l人目がいる位置とl+1人目がいる位置の間から出発したら、r-l人と会う
    // これをまとめてresultに加算
    result += (a.at(l+1)-a.at(l))*(r-l);

    // 次のlを調査
    l++;

    // 同じところにもう1人いる場合はスキップ
    // （やっても0を足す結果になるだけなので、スキップする必要もないが……）
    while (a.at(l)==a.at(l+1)) l++;

  }

  //////////////////// 出力 ////////////////////

  cout << result << endl;

  //////////////////// 終了 ////////////////////

  return 0;

}

Submission Info

Judge Result