Skip to content
Programming101
Programmingoneonone
  • Home
  • CS Subjects
    • Internet of Things (IoT)
    • 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
Programmingoneonone

HackerEarth Rhezo and his array problem solution

YASH PAL, 31 July 2024
In this HackerEarth Rhezo and his array problem solution, Rhezo got an array A as a gift from his friend Tanya. Along with this array, she also gave him a list of operations to perform on the array. The operations that are present in the list are the following.
  1. Three integers L, R, and X are known, and Rhezo multiplies all numbers in the range [L, R] by X.
  2. Four integers L, R, X, and Y are known, and Rhezo needs to find out the count of integers in the range [L, R] whose product with X gives a number greater than or equal to Y.
Now, you being Rhezo’s friend, have to help him in simulating the Q operations and report the answer to any operation of type 2. Please help poor Rhezo!
HackerEarth Rhezo and his array problem solution

HackerEarth Rhezo and his array problem solution.

#include<bits/stdc++.h>

using namespace std;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;

#define ordered_set tree<pair<ll,int>, null_type, less< pair<ll,int> >, rb_tree_tag, tree_order_statistics_node_update>
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define all(x) x.begin(),x.end()
#define sz(x) ((int)x.size())
#define eps 1e-9

const int MOD = 1e9+7;

typedef long long ll;
typedef pair<int,int> pii;

ll POWER[65];
ll power(ll a, ll b) {ll ret=1;while(b) {if(b&1) ret*=a;a*=a;if(ret>=MOD) ret%=MOD;if(a>=MOD) a%=MOD;b>>=1;}return ret;}
ll inv(ll x) {return power(x,MOD-2);}

void precompute() {
POWER[0]=1;
for(int i=1;i<63;i++) POWER[i]=POWER[i-1]<<1LL;
}
const int MAXN = 1e5+5;
bool is[4*MAXN];
ll ar[MAXN];
ordered_set v[4*MAXN];
const ll INF = 1000005000;
bool overflow(ll x, ll y) {
ll val = (INF+y-1)/y;
if(x>=val) return true;
return false;
}

void go(int idx, pair<ll,int> f1, pair<ll,int> f2) {
while(idx) {
v[idx].erase(f1);
v[idx].insert(f2);
idx/=2;
}
}
void build(int node, int start, int end) {
v[node].clear();
is[node]=false;
if(start==end) {
v[node].insert(mp(ar[start],start));
return;
}
int mid=(start+end)>>1;
build(2*node,start,mid);
build(2*node+1,mid+1,end);
int oth=2*node,prim=2*node+1;
if(sz(v[prim])<sz(v[oth])) swap(prim,oth);
v[node]=v[prim];
for(auto it:v[oth]) v[node].insert(it);
}
void multiply(int node, int start, int end, int qs, int qe, ll val) {
if(start>end or qe<start or qs>end) return;
if(is[node]) return;
if(start==end) {
if(overflow(ar[start],val)) {
is[node]=true;
go(node,mp(ar[start],start),mp(INF,start));
ar[start]=INF;
return;
}
go(node,mp(ar[start],start),mp(ar[start]*val,start));
ar[start]*=val;
return;
}
int mid=(start+end)>>1;
multiply(2*node,start,mid,qs,qe,val);
multiply(2*node+1,mid+1,end,qs,qe,val);
is[node]=is[2*node]&is[2*node+1];
}
int query(int node, int start, int end, int qs, int qe, ll val) {
if(start>end or qe<start or qs>end) return 0;
if(start>=qs and end<=qe) return end-start+1-v[node].order_of_key(mp(val,0));
int mid=(start+end)>>1;
return query(2*node,start,mid,qs,qe,val)+
query(2*node+1,mid+1,end,qs,qe,val);
}
int main() {
precompute();
int n,q;
cin>>n>>q;
assert(n>=1 and n<=50000);
assert(q>=1 and q<=100000);
for(int i=1;i<=n;i++) scanf("%lld",&ar[i]);
build(1,1,n);
while(q--) {
int type,l,r;
scanf("%d%d%d",&type,&l,&r);
assert(type==1 or type==2);
assert(l>=1 and l<=n);
assert(r>=1 and r<=n);
ll x,y;
scanf("%lld",&x);
assert(x>=2 and x<=1000000000);
if(type==1) multiply(1,1,n,l,r,x);
if(type==2) {
ll y;
scanf("%lld",&y);
assert(y>=1 and y<=1000000000);
printf("%dn",query(1,1,n,l,r,(y+x-1)/x));
}
}
return 0;
}
coding problems solutions

Post navigation

Previous post
Next post

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
  • YouTube
  • LinkedIn
  • Facebook
  • Pinterest
  • Instagram
©2025 Programmingoneonone | WordPress Theme by SuperbThemes