I get WA on Tasks 15 and 16 and AC on the rest. I am not able to spot the bug. Could someone help. Thanks!
Headers included is bits stdc++.h
using namespace std;
long long min(long long a, long long b) {
if ( a <= b ) {
return a;
}
else {
return b;
}
}
long long max(long long a, long long b) {
if (a >= b ) {
return a;
}
else {
return b;
}
}
int main(void) {
long long n, l, r;
cin>>n>>l>>r;
vector<long long> a, left, right;
long long tmp;
for (int i = 0; i < n; i++ ) {
scanf("%lld", &tmp);
a.push_back(tmp);
}
sort(a.begin(), a.end());
long long le, ri;
for (int i = 0; i < (n - 1); i++ ) {
le = a[i+1] - a[i] + 1;
ri = a[i] + a[i+1] - 1;
left.push_back(le);
right.push_back(ri);
}
long long res = 0;
long long endIndex, startValue, currentIndex;
currentIndex = endIndex = n - 2;
bool shouldBreakOut = false;
while ( currentIndex > 0 ) {
if (right[endIndex] < l) {
shouldBreakOut = true;
break;
}
startValue = left[endIndex];
while( ( currentIndex > 0 ) && (startValue <= right[currentIndex-1]) ) {
currentIndex--;
if (startValue > left[currentIndex]) {
startValue = left[currentIndex];
}
}
if (currentIndex > 0) {
long long rightVal, leftVal;
rightVal = min(r,right[endIndex]);
if ( startValue <= l ) {
shouldBreakOut = true;
leftVal = l;
}
else {
leftVal = startValue;
}
res += (rightVal - leftVal + 1);
if (shouldBreakOut == true ) {
break;
}
else {
endIndex = currentIndex - 1;
currentIndex = endIndex;
}
}
}
if (n > 2 ) {
if ( shouldBreakOut == false ) {
long long leftVal = min(startValue, left[currentIndex]);
long long rightVal = right[endIndex];
if ( leftVal <= r && rightVal >= l) {
leftVal = max(leftVal, l);
rightVal = min(r, rightVal);
res += (rightVal - leftVal + 1);
}
}
}
else {
long long leftVal = left[0];
long long rightVal = right[0];
if ( leftVal <= r && rightVal >= l ) {
leftVal = max(leftVal, l);
rightVal = min(rightVal, r);
res += (rightVal - leftVal + 1);
}
}
printf("%lld\n", res);
return 0;
}