#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define F first
#define S second
#define all(x) (x).begin(), (x).end()
template<typename T, typename U>
ostream &operator<<(ostream &os, const pair<T, U> &p)
{
return os << "(" << p.F << "," << p.S << ")";
}
template<typename T>
void print(const T &v, int lim = 1e9)
{
for(auto x : v)
if(lim-- > 0) cout << x << " ";
cout << "\n";
}
const int mxN = 5000005;
tuple<ll, int, int> stk[3 * mxN];
int rg[mxN];
ll a[mxN];
int tp = 0;
void stk_push(ll f, int s, int t)
{
stk[tp] = {f, s, t};
tp++;
}
int main()
{
ios::sync_with_stdio(0); cin.tie(NULL);
int N, T;
cin >> N >> T;
for(int i = 0; i < N; i++)
{
cin >> a[i];
}
int l = -1, r = 1e9;
while(l + 1 < r)
{
int mid = (l + r) / 2;
tp = 0;
int cnt = 0, mx = 0;
for(int i = 0; i < N; i++)
{
ll y1 = a[i] % T, y2 = a[i] % T + T, y3 = a[i] % T - T;
stk_push(y1 - mid, 0, i);
stk_push(y1 + mid, 1, i);
stk_push(y2 - mid, 0, i);
stk_push(y2 + mid, 1, i);
stk_push(y3 - mid, 0, i);
stk_push(y3 + mid, 1, i);
}
sort(stk, stk + tp);
for(int i = 0; i < tp; i++)
{
auto &[_, flg, idx] = stk[i];
if(flg == 0)
{
if(rg[idx] == 0) cnt++;
rg[idx]++;
}
else
{
if(rg[idx] == 1) cnt--;
rg[idx]--;
}
mx = max(cnt, mx);
}
if(mx == N) r = mid;
else l = mid;
}
cout << r << "\n";
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |