Skip to content
Programming101
Programming101

Learn everything about programming

  • Home
  • CS Subjects
    • IoT – Internet of Things
    • Digital Communication
    • Human Values
  • Programming Tutorials
    • C Programming
    • Data structures and Algorithms
    • 100+ Java Programs
    • 100+ C Programs
  • HackerRank Solutions
    • HackerRank Algorithms Solutions
    • HackerRank C problems solutions
    • HackerRank C++ problems solutions
    • HackerRank Java problems solutions
    • HackerRank Python problems solutions
Programming101
Programming101

Learn everything about programming

HackerEarth Counting the number of intervals solution

YASH PAL, 31 July 2024
In this HackerEarth Counting the number of intervals problem solution, You are given a sequence of N integers a1,a2,…,aN and an integer K. Your task is to count the number of intervals [l,r] such that al + ar + min(al,al+1,…,ar) <= K.
HackerEarth Counting the number of intervals problem solution

HackerEarth Counting the number of intervals problem solution.

#include <bits/stdc++.h>
using namespace std;

#define ms(s, n) memset(s, n, sizeof(s))
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define FORd(i, a, b) for (int i = (a) - 1; i >= (b); --i)
#define FORall(it, a) for (__typeof((a).begin()) it = (a).begin(); it != (a).end(); it++)
#define sz(a) int((a).size())
#define present(t, x) (t.find(x) != t.end())
#define all(a) (a).begin(), (a).end()
#define uni(a) (a).erase(unique(all(a)), (a).end())
#define pb push_back
#define pf push_front
#define mp make_pair
#define fi first
#define se second
#define prec(n) fixed<<setprecision(n)
#define bit(n, i) (((n) >> (i)) & 1)
#define bitcount(n) __builtin_popcountll(n)
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pi;
typedef vector<int> vi;
typedef vector<pi> vii;
const int MOD = (int) 1e9 + 7;
const int FFTMOD = 119 << 23 | 1;
const int INF = (int) 1e9 + 23111992;
const ll LINF = (ll) 1e18 + 23111992;
const ld PI = acos((ld) -1);
const ld EPS = 1e-9;
inline ll gcd(ll a, ll b) {ll r; while (b) {r = a % b; a = b; b = r;} return a;}
inline ll lcm(ll a, ll b) {return a / gcd(a, b) * b;}
inline ll fpow(ll n, ll k, int p = MOD) {ll r = 1; for (; k; k >>= 1) {if (k & 1) r = r * n % p; n = n * n % p;} return r;}
template<class T> inline int chkmin(T& a, const T& val) {return val < a ? a = val, 1 : 0;}
template<class T> inline int chkmax(T& a, const T& val) {return a < val ? a = val, 1 : 0;}
inline ull isqrt(ull k) {ull r = sqrt(k) + 1; while (r * r > k) r--; return r;}
inline ll icbrt(ll k) {ll r = cbrt(k) + 1; while (r * r * r > k) r--; return r;}
inline void addmod(int& a, int val, int p = MOD) {if ((a = (a + val)) >= p) a -= p;}
inline void submod(int& a, int val, int p = MOD) {if ((a = (a - val)) < 0) a += p;}
inline int mult(int a, int b, int p = MOD) {return (ll) a * b % p;}
inline int inv(int a, int p = MOD) {return fpow(a, p - 2, p);}
inline int sign(ld x) {return x < -EPS ? -1 : x > +EPS;}
inline int sign(ld x, ld y) {return sign(x - y);}
mt19937 mt(chrono::high_resolution_clock::now().time_since_epoch().count());
inline int myrand() {return abs((int) mt());}
#define db(x) cerr << #x << " = " << (x) << " ";
#define endln cerr << "n";

const int maxn = 5e5 + 5;
int n;
long long k;
long long a[maxn];
int l[maxn];
int r[maxn];
vii g[maxn];

int fen[maxn];
void upd(int p, int val) {
p++;
for (; p < maxn; p += p & -p) {
fen[p] += val;
}
}
int query(int p) {
p++;
int res = 0;
for (; p > 0; p -= p & -p) {
res += fen[p];
}
return res;
}

void chemthan() {
cin >> n >> k;
assert(1 <= n && n <= 5e5);
assert(1 <= k && k <= 1e18);
vector<long long> dc;
FOR(i, 0, n) {
cin >> a[i];
assert(1 <= a[i] && a[i] <= 1e18);
dc.pb(a[i]);
}
sort(all(dc)), uni(dc);
FOR(i, 0, n) l[i] = r[i] = i;
FOR(i, 1, n) {
int ptr = i;
while (ptr && a[i] < a[ptr - 1]) ptr = l[ptr - 1];
l[i] = ptr;
}
FORd(i, n - 1, 0) {
int ptr = i;
while (ptr + 1 < n && a[i] <= a[ptr + 1]) ptr = r[ptr + 1];
r[i] = ptr;
}
FOR(i, 0, n) {
if (i - l[i] <= r[i] - i) {
FOR(j, l[i], i + 1) {
int d = upper_bound(all(dc), k - a[i] - a[j]) - dc.begin() - 1;
g[r[i]].pb(mp(d, 1));
if (i) {
g[i - 1].pb(mp(d, -1));
}
}
}
else {
FOR(j, i, r[i] + 1) {
int d = upper_bound(all(dc), k - a[i] - a[j]) - dc.begin() - 1;
g[i].pb(mp(d, 1));
if (l[i]) {
g[l[i] - 1].pb(mp(d, -1));
}
}
}
}
long long res = 0;
FOR(i, 0, n) {
int k = lower_bound(all(dc), a[i]) - dc.begin();
upd(k, 1);
for (pi ev : g[i]) {
res += query(ev.fi) * ev.se;
}
}
cout << res << "n";
}

int main(int argc, char* argv[]) {
ios_base::sync_with_stdio(0), cin.tie(0);
if (argc > 1) {
assert(freopen(argv[1], "r", stdin));
}
if (argc > 2) {
assert(freopen(argv[2], "wb", stdout));
}
chemthan();
cerr << "nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "msn";
return 0;
}

Second solution

#include<bits/stdc++.h>
#define rep(i,start,lim) for(lld i=start;i<lim;i++)
#define repd(i,start,lim) for(lld i=start;i>=lim;i--)
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define sz(a) (lld)((a).size())
#define all(c) (c).begin(),(c).end()
typedef long double ldb;
typedef long long lld;
const lld MOD = 1e9+7;
const lld INF = 1011111111;
const lld LLINF = 1000111000111000111LL;
const ldb EPS = 1e-10;
const ldb PI = 3.14159265358979323;
using namespace std;
lld powm(lld base,lld exp,lld mod=MOD) {lld ans=1;while(exp){if(exp&1) ans=(ans*base)%mod;exp>>=1,base=(base*base)%mod;}return ans;}
#define endl 'n'
#define fre freopen("1.in","r",stdin); freopen("1.out","w",stdout);
const lld N = 500005;
long long a[N],k;
vector<long long> comp;
int new_a[N];
#define LOGN 20
int n,log_base_2[N];
struct SparseTable{
int m[N][LOGN];
void pre() {
rep(i,2,N) log_base_2[i]=log_base_2[i>>1]+1;
rep(i,1,n+1) m[i][0]=i;
for(int j=1;(1<<j)<=n;j++) for(int i=1;i+(1<<j)-1<=n;i++) {
if(a[m[i][j-1]] > a[m[i+(1<<(j-1))][j-1]]) m[i][j] = m[i+(1<<(j-1))][j-1];
else m[i][j] = m[i][j-1];
}
}
int getmin(int l,int r) {
int tmp=log_base_2[r-l+1];
if(a[m[l][tmp]] > a[m[r-(1<<tmp)+1][tmp]]) return m[r-(1<<tmp)+1][tmp];
else return m[l][tmp];
}
} st;
int ft[N];
void update(int x,int val) {
for(;x<N;x+=(x&-x)) ft[x] += val;
}
int query(int x) {
int ret = 0;
for(;x>0;x-=(x&-x)) ret += ft[x];
return ret;
}

long long ans;
void go(int l,int r) {
if(r < l) return ;
int idx = st.getmin(l,r);
int lft = (idx-l+1), rgt = (r-idx+1);
if(lft <= rgt) {
go(l, idx-1);
rep(i,l,idx) update(new_a[i],-1);
go(idx+1, r);
update(new_a[idx],1);
rep(i,l,idx+1) {
if(k < a[idx] + a[i]) continue;
auto tmp = upper_bound(all(comp), k - a[idx] - a[i]);
if(tmp == comp.begin()) continue;
tmp--;
ans += query(tmp - comp.begin() + 1);
}
rep(i,l,idx) update(new_a[i],1);
}
else {
go(idx+1, r);
rep(i,idx+1,r+1) update(new_a[i],-1);
go(l, idx-1);
update(new_a[idx],1);
rep(i,idx,r+1) {
if(k < a[idx] + a[i]) continue;
auto tmp = upper_bound(all(comp), k - a[idx] - a[i]);
if(tmp == comp.begin()) continue;
tmp--;
ans += query(tmp - comp.begin() + 1);
}
rep(i,idx+1,r+1) update(new_a[i],1);
}
}
long long b[N];
int32_t main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin>>n>>k;
rep(i,1,n+1) {
cin>>a[i];
comp.push_back(a[i]);
}
sort(all(comp));
comp.erase(unique(all(comp)), comp.end());
rep(i,1,n+1) new_a[i] = lower_bound(all(comp), a[i]) - comp.begin() + 1;
st.pre();
go(1,n);
cout<<ans;
return 0;
}
coding problems

Post navigation

Previous post
Next post
  • HackerRank Separate the Numbers solution
  • How AI Is Revolutionizing Personalized Learning in Schools
  • GTA 5 is the Game of the Year for 2024 and 2025
  • Hackerrank Day 5 loops 30 days of code solution
  • Hackerrank Day 6 Lets Review 30 days of code solution
How to download udemy paid courses for free

Pages

  • About US
  • Contact US
  • Privacy Policy

Programing Practice

  • C Programs
  • java Programs

HackerRank Solutions

  • C
  • C++
  • Java
  • Python
  • Algorithm

Other

  • Leetcode Solutions
  • Interview Preparation

Programming Tutorials

  • DSA
  • C

CS Subjects

  • Digital Communication
  • Human Values
  • Internet Of Things
©2025 Programming101 | WordPress Theme by SuperbThemes