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;
}