CF_725_C

Run Settings
LanguageC++
Language Version
Run Command
#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 ; }
Editor Settings
Theme
Key bindings
Full width
Lines