Overkill solution


#1

It can be solved using binary search and sparse table in NLOGN, but i think this solution is an overkill as compared to the solution provided in the editorial.

#define ll long long int
const int N = 1e5 + 5;

vector a;
ll RMQ[20][N], RMQ1[20][N], floorlog[N], n;
void pre(){
for(int i = 0; (1<<i) < N; i++){
for(int j = (1<<i); j < N & j < (1<<(i+1)); j++)
floorlog[j] = i;
}
for(int i = n; i >= 1; i–){
RMQ[0][i] = a[i];
ll mxj = floorlog[n - i + 1];
ll pw = 1;
for(int j = 1; j <= mxj; j++){
RMQ[j][i] = max(RMQ[j - 1][i], RMQ[j - 1][i + pw]);
pw <<= 1;
}
}
}

void pre1(){
for(int i = n; i >= 1; i–){
RMQ1[0][i] = a[i];
ll mxj = floorlog[n - i + 1];
ll pw = 1;
for(int j = 1; j <= mxj; j++){
RMQ1[j][i] = min(RMQ1[j - 1][i], RMQ1[j - 1][i + pw]);
pw <<= 1;
}
}
}

ll querry(ll l, ll r){
ll k = floorlog[r - l + 1];
return max(RMQ[k][l], RMQ[k][r - (1 << k) + 1]);
}

ll querry1(ll l, ll r){
ll k = floorlog[r - l + 1];
return min(RMQ1[k][l], RMQ1[k][r - (1 << k) + 1]);
}

int Solution::solve(vector &A, int B) {
memset(RMQ, 0, sizeof RMQ);
memset(RMQ1, 0, sizeof RMQ1);
memset(floorlog, 0, sizeof floorlog);
a.clear();
a = A;
reverse(a.begin(), a.end());
a.push_back(0);
reverse(a.begin(), a.end());
n = a.size() - 1;
pre();
pre1();
int lo = 0, hi = n + 1;
while(hi - lo > 1){
int mid = (hi + lo) >> 1LL;
bool flag = 0;
for(int i = 1; i + mid - 1 <= n; i++){
int mx = querry(i, i + mid - 1);
int mn = querry1(i, i + mid - 1);
if(mx - mn < B){
flag = 1;
break;
}
}
if(flag) lo = mid;
else hi = mid;
}
return lo;
}