Skip to content
Programmingoneonone
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
  • Work with US
Programmingoneonone
Programmingoneonone

HackerEarth Mojtabas Array and Arpas Queries solution

YASH PAL, 31 July 2024
In this HackerEarth Mojtabas Trees and Arpas Queries problem solution, Mojtba has an array a with n elements and an integer k. Arpa has q query in type [L,R], for i-th query print the length of the shortest segment [x,y] relate [Li,Ri], such that K | pi(y, j=x) aj.
HackerEarth Mojtaba's Array and Arpa's Queries problem solution

HackerEarth Mojtaba’s Array and Arpa’s Queries problem solution.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 5e5 + 17, lg = 19;

int n, k, q, fen[maxn], sp[lg][maxn], r[maxn], ans[maxn];
vector<int> vec[maxn];
void upd(int p, int x){
for(p++; p < maxn; p += p & -p)
fen[p] = min(x, fen[p]);
}
int get(int p){
int ans = maxn;
for(p++; p; p ^= p & -p)
ans = min(ans, fen[p]);
return ans;
}
int main(){
ios::sync_with_stdio(0), cin.tie(0);
memset(fen, 63, sizeof fen);
cin >> n >> k >> q;
for(int i = 0; i < n; i++){
cin >> sp[0][i];
sp[0][i] %= k;
}
for(int l = 1; l < lg; l++)
for(int i = 0; i + (1 << l) <= n; i++)
sp[l][i] = (ll) sp[l - 1][i] * sp[l - 1][i + (1 << l - 1)] % k;
for(int i = 0; i < q; i++){
int l;
cin >> l >> r[i];
r[i]--;
vec[l - 1].push_back(i);
}
for(int i = n - 1; i >= 0; i--){
int j = i, curz = 1; // catche some bug!
for(int lev = lg - 1; lev >= 0; lev--)
if(j + (1 << lev) < n && (ll) curz * sp[lev][j] % k){
curz = (ll) curz * sp[lev][j] % k;
j += 1 << lev;
}
if((ll) curz * sp[0][j] % k == 0)
upd(j, j - i + 1);
for(auto qi : vec[i])
ans[qi] = get(r[qi]);
}
for(int i = 0; i < q; i++)
cout << (ans[i] >= maxn ? -1 : ans[i]) << ' ';
cout << 'n';
}

Second solution

#include <bits/stdc++.h>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <utility>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <iomanip>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define f(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) f(i,0,n)
#define fd(i,a,b) for(i=a;i>=b;i--)
#define pb push_back
#define mp make_pair
#define vi vector< int >
#define vl vector< ll >
#define ss second
#define ff first
#define ll long long
#define pii pair< int,int >
#define pll pair< ll,ll >
#define sz(a) a.size()
#define inf (1000*1000*1000+5)
#define all(a) a.begin(),a.end()
#define tri pair<int,pii>
#define vii vector<pii>
#define vll vector<pll>
#define viii vector<tri>
#define mod (1000*1000*1000+7)
#define pqueue priority_queue< int >
#define pdqueue priority_queue< int,vi ,greater< int > >
#define flush fflush(stdout)
#define primeDEN 727999983
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

// find_by_order() // order_of_key
typedef tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;

ll seg[2123456],segmul[2123456];
ll a[512345];
ll k;
int build(int node,int s,int e){
seg[node]=inf;
if(s==e){
return 0;
}
int mid=(s+e)/2;
build(2*node,s,mid);
build(2*node+1,mid+1,e);
return 0;
}
int update(int node,int s,int e,int pos,int val){
if(s==e){
seg[node]=val;
return 0;
}
int mid=(s+e)/2;
if(pos<=mid)
update(2*node,s,mid,pos,val);
else
update(2*node+1,mid+1,e,pos,val);
seg[node]=min(seg[2*node],seg[2*node+1]);
return 0;
}

int query(int node,int s,int e,int l,int r){
if(e<l || r<s)
return inf;
if(l<=s && e<=r){
return seg[node];
}
int mid=(s+e)/2;
int ans=inf;
ans=min(ans,query(2*node,s,mid,l,r));
ans=min(ans,query(2*node+1,mid+1,e,l,r));
return ans;
}
vector<vi> gg(512345);
vector<vii> quer(512345);
int ans[512345],haha[512345];

ll buildmul(int node,int s,int e){
if(s==e){
segmul[node]=a[s]%k;
return 0;
}
int mid=(s+e)/2;
buildmul(2*node,s,mid);
buildmul(2*node+1,mid+1,e);
segmul[node]=segmul[2*node]*segmul[2*node+1];
segmul[node]%=k;
return 0;
}


ll getans(int node,int s,int e,int l,int r){
if(e<l || r<s){
return 1;
}
if(l<=s && e<=r){
//cout<<node<<" "<<s<<" "<<e<<endl;
return segmul[node];
}

int mid=(s+e)/2;
ll ans=1;
ans*=getans(2*node,s,mid,l,r);
ans*=getans(2*node+1,mid+1,e,l,r);
ans%=k;
return ans;

}
int main(){
std::ios::sync_with_stdio(false); cin.tie(NULL);
int n,q;
cin>>n>>k>>q;
int i;
rep(i,n){
cin>>a[i];
}
buildmul(1,0,n-1);
build(1,0,n-1);
int j;
i=0;
j=0;
//cout<<getans(1,0,n-1,1,1)<<endl;
//return 0;
while(i<n && j<n){
if(j<i)
j=i;
if(getans(1,0,n-1,i,j)==0){
ans[i]=j;
//cout<<ans[i]-i+1<<endl;
gg[j].pb(i);
i++;
}
else{
j++;
}
}
int l,r;
rep(i,q){
cin>>l>>r;
l--;
r--;
quer[r].pb(mp(l,i));
}
//return 0;
rep(i,n){
rep(j,gg[i].size()){
update(1,0,n-1,gg[i][j],i-gg[i][j]+1);
}
rep(j,quer[i].size()){
haha[quer[i][j].ss]=query(1,0,n-1,quer[i][j].ff,i);
}
}
rep(i,q){
if(haha[i]==inf)
haha[i]=-1;
cout<<haha[i]<<" ";
}
cout<<endl;

return 0;
}
coding problems solutions

Post navigation

Previous post
Next post

Related website

The Computer Science

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