HackerEarth Mojtabas Array and Arpas Queries solution

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.

#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