In this HackerEarth Cocktail Range Query problem solution Vikas0706 is an awesome bar tender. He has never failed is satisfying his customers. One fine evening, after getting frustrated and tired a programmer came to his bar. He thought to remove all his frustration on Vikas0706.
There are N different types of drink kept in a line on the table. Every drink can be of different quantity (in ml) . Now programmer asked Vikas0706 to make a cocktail of quantity k ml using only 2 drinks. Also he has to completely consume the drink he selects. Vikas0706 is really confused which two drink to select. Now programmer didn't stop here. He further told him to select drinks only from a range l to r (both l and r inclusive) . Vikas0706 is in a big trouble now. You are his last hope. Tell him how many different type of cocktails he can make in the specified range satisfying the conditions of the programmer.


HackerEarth Cocktail Range Query problem solution


HackerEarth Cocktail Range Query problem solution.

#include<bits/stdc++.h>
#define endl '\n'
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int ui;
typedef std::vector<int> vi;
typedef std::vector<long long> vl;
#define all(v) v.begin(),v.end()
#define MAX 1000005
#define MOD 1000000007
#define FAST_IN_OUT ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

using namespace std;
vector<int> has[2002];

ll search(int l,int r,int x){

ll k1= upper_bound(all(has[x]),r)-has[x].begin();
ll k2=lower_bound(all(has[x]),l)-has[x].begin();
return (k1-k2)>0?(k1-k2):0;
}

int main(){
FAST_IN_OUT

int n,q;
cin>>n>>q;
int *a=new int[MAX];
for (int i = 0; i < n; ++i)
{
cin>>a[i];
has[a[i]].pb(i);
}

while(q--) {
int l,r,x;
cin>>l>>r>>x;
ll ans=0;
l--;
r--;
for (int i = 1; i <=x ; ++i){
ll aa=0;
if(i==(x-i)){
ll v= search(l,r,i);
aa += v*(v-1);
}else{
aa=search(l,r,i)*search(l,r,x-i);
}
ans+=aa;
}
cout<<ans/2<<endl;
}
}