Submission #70438605

---

Source Code Expand

#include <bits/stdc++.h>
//#include <atcoder/all>
using namespace std;
//using namespace atcoder;
//using mint = modint1000000007;
//const int mod = 1000000007;
//using mint = modint998244353;
//const int mod = 998244353;
//const int INF = 1e9;
//const long long LINF = 1e18;
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep2(i,l,r)for(int i=(l);i<(r);++i)
#define rrep(i, n) for (int i = (n) - 1; i >= 0; --i)
#define rrep2(i,l,r)for(int i=(r) - 1;i>=(l);--i)
#define all(x) (x).begin(),(x).end()
#define allR(x) (x).rbegin(),(x).rend()
#define P pair<int,int>
template<typename A, typename B> inline bool chmax(A & a, const B & b) { if (a < b) { a = b; return true; } return false; }
template<typename A, typename B> inline bool chmin(A & a, const B & b) { if (a > b) { a = b; return true; } return false; }
template <class T, class F>
T binarySearch(T ok, T ng, const F &f) {
	while (abs(ok - ng) > 1) {
		T mid = (ok + ng) / 2;
		(f(mid) ? ok : ng) = mid;
	}
	return ok;
}
// 関数ver
template<typename T>
std::pair<std::vector<T>, int> compression(std::vector<T> org) {
	auto copy = org;
	std::sort(copy.begin(), copy.end());
	copy.erase(unique(copy.begin(), copy.end()), copy.end());
	for (auto &e : org) {
		e = std::lower_bound(copy.begin(), copy.end(), e) - copy.begin();
	}
	return { org,copy.size() };
}
int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	int n; cin >> n;
	long long m; cin >> m;
	int c; cin >> c;
	map<long long, int>mp;
	vector<long long>pos, eve;
	//	pos = { 0,m };
	rep(i, n) {
		long long a; cin >> a;
		pos.push_back(a);
		pos.push_back(a + m);
		eve.push_back(a);
	}
	sort(all(pos));

	//auto eve = pos;
	{
		eve.push_back(0);
		eve.push_back(m);
		std::sort(eve.begin(), eve.end());
		eve.erase(unique(eve.begin(), eve.end()), eve.end());
	}

	long long ans = 0;
	rep(i, eve.size() - 1) {
		long long l = eve[i];
		long long r = eve[i + 1];
		//以下の数
		int c0 = upper_bound(all(pos), l) - pos.begin();
		auto f = [&](const long long x)->bool {
			int c1 = upper_bound(all(pos), x) - pos.begin();
			return c1 - c0 >= c;
		};
		long long tar = binarySearch<long long>(2 * m + 1, 0, f);
		long long tmp = upper_bound(all(pos), tar) - pos.begin();
		tmp -= c0;
		//cout << l << " " << r << " " << tmp << endl;
		ans += (r - l) * tmp;
	}
	cout << ans << endl;
	return 0;
}

Submission Info

Compile Error

Main.cpp: In function ‘int main()’:
Main.cpp:11:37: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<long long int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   11 | #define rep(i, n) for (int i = 0; i < (n); ++i)
      |                                     ^
Main.cpp:65:9: note: in expansion of macro ‘rep’
   65 |         rep(i, eve.size() - 1) {
      |         ^~~

Judge Result