Competitive-programming/cf.cpp at master · piyushK52/Competitive-programming · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <iostream>
#include <algorithm>

using namespace std;
typedef long long ll;

ll n, x, k;
ll a[100100];
ll ans;

ll solve(ll le, ll ri)
{
	if (le > a[n - 1] || ri < a[0])
		return 0;
	ll res = 0;
	int l = 0;
	int r = n - 1;
	int m;
	while (r - l > 1)
	{
		m = (l + r) / 2;
		if (a[m] >= le)
			r = m;
		else
			l = m;
	}
	if (a[l] >= le)
		m = l;
	else
		m = r;
	res = m;
	l = 0;
	r = n - 1;
	while (r - l > 1)
	{
		m = (l + r) / 2;
		if (a[m] <= ri)
			l = m;
		else
			r = m;
	}
	if (a[r] <= ri)
		m = r;
	else
		m = l;
	return m - res + 1;
}

int main()
{
	cin >> n >> x >> k;
	for (int i = 0; i < n; i++)
		cin >> a[i];
	sort(a, a + n);
	for (int i = 0; i < n; i++)
	{
		ll y = a[i] - 1;
		y /= x;
		ll le = max(x*(k + y), a[i]);
		ll ri = x*(k + y + 1) - 1;
		ans += solve(le, ri);
	}
	cout << ans << endl;
}