Setter : Ekansh Saxena

Tester: Ujjawal Gupta

Editorial: Apoorv Dixit

*Difficulty:*

Easy.

*Prerequisite:*

Array, binary search

*Explanation & Algorithm:*

The basic idea of this approach is to use the concept of the lower bound and upper bound. Since we are given the sorted array, so we can easily perform the binary search to find the index of the numbers equal or greater than ‘L’ and ‘R’. After that, on subtracting those numbers we can easily get the required ‘X’.

The steps are as follows:

Create a vector named ‘ANS’ to store the maximum value of F(X) for every ‘Q’ query.

Run a loop from 0 to ‘Q’.

Create a variable ‘IND1’ and hold the lower bound of ‘L’ in ‘ARR’.

Create a variable ‘IND2’ and hold the upper bound of ‘R’ in ‘ARR’.

The required ‘X’ will be ‘IND2’ - ‘IND1’.

Now, calculate the F(X) and push it into the ‘ANS’.

Return the maximum value of F(X).

Time Complexity:

O(Q*log(N)), Where ‘N’ is the length of ‘ARR’ and ‘Q’ is the total number of queries.

Since we are applying binary search for every query to find the required ‘X’ which reduces the search space by 50% after each iteration and so, the overall time complexity will be O(Q*log(N)).

Space Complexity :

O(1)

Since constant extra space is required and so, the overall space complexity will be O(1).

*Solution:*

## Setter's Code

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

void solve(){

ll n,k;

cin>>n>>k;

vll arr;

FILL(n, arr)

while(k–){

ll x,y;

cin>>x>>y;

ll i1 = lower_bound(all(arr), x) - arr.begin();

ll i2 = upper_bound(all(arr), y) - arr.begin();

i2–;

cout<<10*(i2-i1+1) - (y - x)<<" ";

}

cout<<endl;

}

int main(){

#ifndef ONLINE_JUDGE

freopen(“input.txt”, “r”, stdin);

freopen(“output.txt”, “w”, stdout);

#endif

FIO;

ll t;

cin>>t;

while(t–){

solve();

}

return 0;

}

## Tester's Code

#include <bits/stdc++.h>

using namespace std;

int main() {

int t;

cin>>t;

while (t–){

long n, q;

cin>>n>>q;

vector a;

for (long i=0; i<n; i++){

long x;

cin>>x;

a.push_back(x);

}

sort(a.begin(), a.end());

long l, r;

while (q–){

cin>>l>>r;

auto left = lower_bound(a.begin(), a.end(), l);

auto right = upper_bound(a.begin(), a.end(), r);

long x = (right-a.begin()-1) - (left-a.begin()) + 1;

cout<<10*x-r+l<<" ";

}

cout<<endl;

}

return 0;

}