August Long Challenge Alternating LG Queries Solution

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define vi vector <int>
#define vll vector < ll >
#define pb push_back
#define endl '\n'
#define max3(a,b,c) max(max(a,b),c)
#define min3(a,b,c) min(min(a,b),c)
#define answer(ans) cout << ans << '\n' ;
#define ansyes cout << "YES\n" ;
#define ansno cout << "NO\n" ;
#define pll pair<ll,ll>
#define ff first.first
#define fs first.second

#define int ll





ll gcd(ll a ,ll b)
{
    if(b==0) return a;
    else return gcd(b,a%b);
}

ll lcm(ll a,ll b)
{
    return ((a*b)/gcd(a,b));
}


void find_prime(vll &v,int n,vll &reach,vector <bool> &flag)
{
    ll pre=gcd(v[0],v[1]),suff;
    for (ll i=0;i<n-2;i++)
    {
        suff=gcd(v[i+1],v[i+2]);
        if (pre==1 && suff==1 && gcd(v[i],v[i+2])==1)
        {
            flag[i]=true;
        }
        pre=suff;
    }
    int last=n;
    for (ll i=n-1;i>=0;i--)
    {
        if(flag[i]) last=i;

        reach[i]=last;
    }
}

void doGcd(vll &v,vll &reach,int n,vll &getgcd,vector <bool> &flag)
{
    ll i,ans=1,k=0;
    getgcd[n-1]=v[n-1];
    for (i=n-2;i>=0;i--)
    {
        if(k%2) 
        {
            ans = getgcd[i] = gcd(v[i],ans);
        }
        else 
        {
            ans = getgcd[i] = lcm(v[i],ans);
        }
        k++;
        if(flag[i])
        {
            k=0;
            ans=1;
        }
    }

}

void workgcd(vector < pair< pll,ll > > &vg , vll &v , int n,vll &sol,int h,vll &reach,vll &getgcd)
{
    int k=0,len=vg.size(),i,j,ans=1,l,s;

    while(k<len)
    {
        l=k+1;
        while(l<len && vg[l].ff==vg[l-1].ff) l++;
        l--;
        ans=v[vg[k].ff];
        s=k;
        while(vg[k].fs==vg[k].ff)
        {
            sol[vg[k].second]=ans;
            k++;
        }
        if(k==len) break;
        if(vg[k].ff==vg[s].ff)
        {
            
            for (i=vg[k].ff-1,j=h;i>=vg[l].fs;i--,j++)
            {
                
                if(j%2)
                {
                    ans = lcm(ans,v[i]);
                }
                else
                {
                    ans = gcd(ans,v[i]);
                }
                // if(reach[vg[k].fs]!=reach[vg[k].ff]) i=vg[k].fs,ans=v[i] ;
                if(i==vg[k].fs)
                {
                    sol[vg[k].second]=ans;
                    k++;
                }
            }
        }
    }
    return ;
}


ll f1(ll a, ll b, vll &v)
{
    ll ans=v[b],j=1;
    for (ll i=b;i>=a;i--)
    {
        if(j%2)
        {
            ans=gcd(ans,v[i]);
        }
        else
        {
            ans=lcm(ans,v[i]);
        }
        j++;
    }
    return ans;
}

void solve()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n,q,i,j;
    cin >> n >> q;
    vector <ll> v(n),sol(q),reach(n,n);
    vector < pair< pll,ll > > vg,vl;

    for (i=0;i<n;i++)
    {
        cin >> v[i];
    }
    vector <bool> flag(n,false);
    find_prime(v,n,reach,flag);
    vector <ll> getgcd(n);
    doGcd(v,reach,n,getgcd,flag);

    ll t,a,b;
    for (i=0;i<q;i++)
    {
        cin >> t >> a >> b ;
        if (t==1)
        {
            if((b-a )%2)
            {
                if(flag[a-1]) sol[i]=1;
                else if(reach[b-1]!=reach[a-1])
                {
                    ll k=reach[a-1];
                    if((k-a+1)%2==0) sol[i]=getgcd[a-1];
                    else vg.push_back({{b-1,a-1},i});
                }
                else vg.push_back({{b-1,a-1},i});
            }
            else
            {
                if(flag[a-1]) sol[i]=1;
                else if(reach[b-1]!=reach[a-1])
                {
                    ll k=reach[a-1];
                    if((k-a+1)%2==0) sol[i]=getgcd[a-1];
                    else vl.push_back({{b-1,a-1},i});
                }
                else 
                vl.pb({{b-1,a-1},i});
            }
        }
        else{
            if((b-a)%2==0)
            {
                if(flag[a]) sol[i]=lcm(v[a],v[a-1]);
                else if(reach[b-1]!=reach[a-1])
                {
                    ll k=reach[a-1];
                    if((k-a+1)%2) sol[i]=getgcd[a-1];
                    else vg.push_back({{b-1,a-1},i});
                }
                else vg.push_back({{b-1,a-1},i});
            }
            
            else
            {
                if(flag[a]) sol[i]=lcm(v[a],v[a-1]);
                else if(reach[b-1]!=reach[a-1])
                {
                    ll k=reach[a-1];
                    if((k-a+1)%2) sol[i]=getgcd[a-1];
                    else vl.push_back({{b-1,a-1},i});
                }
                else vl.pb({{b-1,a-1},i});
            }
        }
    }
    sort(vg.rbegin(),vg.rend());
    sort(vl.rbegin(),vl.rend());
    
   

    workgcd(vg,v,n,sol,0,reach,getgcd);
    workgcd(vl,v,n,sol,1,reach,getgcd);

    for (i=0;i<q;i++)
    {
        cout << sol[i] << "\n";
    }

  
    return ;
}


int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t=1;
    cin >> t;
    while(t--)
    {
        solve();
    }

    return 0;
}

Codechef Long Challenges

August Long Challenge 2021 Solutions

• Olympics Ranking
• Problem Difficulties
• Chef and Bulb Invention
• Array Filling
• Special Triplets
• Geometry 1
• Charge Scheduling
• Chef and Digits of Large Numbers
• Fat Hut
• Alternating LG Queries

July Long Challenge 2021 Solutions

• Maximum Production
• Relativity
• XxOoRr
• Optimal Denomination
• K Path Query
• Chef vs Bharat
• Chef and Pairs
• Even Odd Partition
• Dakimakura Distribition
• Madoka and Ladder Decomposition