CF_725_C
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647
#include "bits/stdc++.h"
#define pb emplace_back
#define lwb lower_bound
#define upb upper_bound
#define I insert
#define all(x) x.begin(), x.end()
#define FIO ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace std ;
using ll = long long;
/*
the below code gives
TLE on Testcase 4
time complexity : 3nlogn
another solution : 2nlogn is been submitted check it out here
https://codeforces.com/contest/1538/submission/119684655
*/
ll solve(vector<ll>&v ,ll &n , ll &l , ll &r){
vector<ll> sa ;
ll retVal = 0 ;
sa.pb(v[n-1]) ;
for (ll i = n-2 ; i >= 0 ; i-- ){
auto Left = lwb(all(sa) , l-v[i]) ;
auto Right = upb(all(sa) ,r-v[i]) ;
retVal += (Right-Left) ;
sa.I(lwb(all(sa) , v[i]) , v[i]) ;
}
return retVal ;
}
int main(){
FIO
ll t ; cin >> t ;
while(t--){
ll n , l ,r ; cin >> n >> l >> r ;
vector<ll> v(n , 0 ) ;
for(auto &c : v)cin >> c ;
cout << solve(v,n,l,r) <<"\n" ;
}
return 0 ;
}
Cpp
INFO