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