Submission #70438373

---

Source Code Expand

#include <bits/stdc++.h>
#define lb(x) (x&-x)
#define L(i,j,k) for(int i=(j);i<=(k);++i)
#define R(i,j,k) for(int i=(j);i>=(k);--i)
#define int long long

namespace luoyh {
using namespace std;
using i64 = long long;

typedef pair<int, int> pii;
typedef long long ll;
typedef unsigned long long ull;
void chmin(int &x, int c) { x = min(x, c); }
void chmax(int &x, int c) { x = max(x, c); }

const int maxn = 5e5 + 10, mod = 998244353;
int N, M, C, pcnt, A[maxn]; pii p[maxn];
int x[maxn], pos[maxn], v[maxn];

void solve() {
  cin >> N >> M >> C;
  L (i, 1, N) cin >> A[i];
  sort (A + 1, A + 1 + N);
  for (int i = 1; i <= N; ){
  	int j = i;
  	while (j <= N && A[i] == A[j]) j++;
  	p[pcnt++] = {A[i], j - i}, i = j;
  }
  if (pcnt == 1) return cout << N * M << '\n', void();
  L (i, 0, pcnt - 1) {
  	int pre = p[(i - 1 + pcnt) % pcnt].first, now = p[i].first;
  	x[i] = (now > pre ? now - pre : now - pre + M);
  }
  int S = 0, cur = -1;
  L (i, 0, pcnt - 1) {
  	while (S < C) cur++, S += p[cur % pcnt].second;
  	v[i] = S, S -= p[i % pcnt].second;
  }
  int res = 0; L (i, 0, pcnt - 1) res += v[i] * x[i];
  cout << res << '\n';
}

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int T = 1;
  while (T--)solve();
  return 0;
}
} signed main() {
  return luoyh::main();
}

Submission Info

Judge Result