HackerEarth Mojtabas Array and Arpas Queries 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;   
}