Quick actions

cmd+k|ctrl+k

Navigation

Languages

CF_725_C

Snippet info

Language

Cpp

Visibility

public

Author

karthik.pasupulatei

Created

2021-06-17T05:17:24.948475Z

Updated

2021-06-17T06:38:09.292469Z

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