CodePlus Long 2024

The problem boils down to finding the number of coordinates between $$$A_i$$$ and $$$A_{i+1}$$$ which are divisible by $$$k$$$ .Where $$$i$$$ is even considering $$$0$$$ based indexing.

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

#define ll long long

ll floor(ll x, ll m) {
    ll r = (x % m + m) % m;
    return (x - r) / m;
}

int main() {
    int t;
    cin >> t;
    while (t--)
    {
        ll n, k, ans = 0;
        cin >> n >> k;
        vector<ll>a(n);
        for (int i = 0; i < n; i++)
        {
            cin >> a[i];
        }
        for (int i = 0; i < n; i += 2)
        {
            ans += floor(a[i + 1] - 1, k) - floor(a[i] - 1, k);
        }
        cout << ans << endl;
    }
}

This is a modified version of a popular problem $$$Dungeon$$$ $$$Game$$$.Try to solve that first.

Leetcode

This problem has more than one solutions, here I want to mention 2 of them

1. Intuitive Solution Here one can see that if the man can accomplish the task with health $$$h$$$ than he can also accomplish the task with health more than h. This shows that we can do a binary search on the $$$ans$$$ , where predicate function will be, doing a bfs starting with a particular health and starting from every node with $$$indegree 0$$$, if we reach one of the nodes with $$$outdegree 0$$$, this health can work. Nirbhay's Solution

2. More Optimal dp solution $$$dp[node]$$$ will here denote minimum health required to reach a node with $$$outdegree 0$$$. Here base case will be for $$$outdegree 0$$$ node we will require $$$max(1,-val[node]+1)$$$ Than the transition will be $$$dp[node]$$$$$$=$$$$$$max(1,{{min-over-all-childs}(dp[child]-val[node])})$$$. This can be done in single dfs as shown in the code.

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

#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> os;
typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> oms;

// find_by_order to find the Kth element
// order_of_key to find number of elements smaller than x
// to erase from oms use order_of_key and than by its index find its iterator using find_by_order than erase it

#define MrRoamer() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define MOD 1000000007
#define MOD1 998244353
#define pb push_back
#define ppb pop_back
#define ff first
#define ss second
#define PI 3.141592653589793238462
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define chal(i,a,b) for(int i=a;i<=b;i++)
#define vi vector<int>
#define vvi vector<vector<int>>
#define prin(x) for(int i=0;i<x.size();i++)cout<<x[i]<<" ";cout<<endl;
#define take(x) for(int i=0;i<x.size();i++)cin>>x[i];

//---------------------------------------------------------------------------------------
typedef long long ll;
typedef unsigned long long ull;
typedef long double lld;

#ifndef ONLINE_JUDGE
#define debug(x) cerr << #x << " "; _print(x); cerr << endl;
#else
#define debug(x)
#endif

void _print(ll t) { cerr << t; }
void _print(int t) { cerr << t; }
void _print(string t) { cerr << t; }
void _print(char t) { cerr << t; }
void _print(lld t) { cerr << t; }
void _print(double t) { cerr << t; }
void _print(ull t) { cerr << t; }

template <class T, class V> void _print(pair <T, V> p);
template <class T> void _print(vector <T> v);
template <class T> void _print(set <T> v);
template <class T, class V> void _print(map <T, V> v);
template <class T> void _print(multiset <T> v);
template <class T, class V> void _print(pair <T, V> p) { cerr << "{"; _print(p.ff); cerr << ","; _print(p.ss); cerr << "}"; }
template <class T> void _print(vector <T> v) { cerr << "[ "; for (T i : v) { _print(i); cerr << " "; } cerr << "]"; }
template <class T> void _print(set <T> v) { cerr << "[ "; for (T i : v) { _print(i); cerr << " "; } cerr << "]"; }
template <class T> void _print(multiset <T> v) { cerr << "[ "; for (T i : v) { _print(i); cerr << " "; } cerr << "]"; }
template <class T, class V> void _print(map <T, V> v) { cerr << "[ "; for (auto i : v) { _print(i); cerr << " "; } cerr << "]"; }

void printos(os v);
void printos(os v){ cerr << "[ "; for (ll i : v) { _print(i); cerr << " "; } cerr << "]"; cerr<<'\n';}
void printos(oms v);
void printos(oms v){ cerr << "[ "; for (ll i : v) { _print(i); cerr << " "; } cerr << "]"; cerr<<'\n';}

//--------------------------code toh yahan hai-----------------------------------

#define int long long

int dfs(int node ,int par,vector<vector<int>>&adj,vector<int>&a,vector<int>&dp)
{
    if(adj[node].size()==0)
    {
        if(a[node-1]<=0)
        {
            return -a[node-1]+1;
        }
        else return 1;
    }
    if(dp[node]!=INT_MAX)return dp[node];
    int ans=INT_MAX;
    for(auto ch:adj[node])
    {
        if(ch==par)continue;
        int tem=dfs(ch,node,adj,a,dp);
        ans=min(ans,tem);
    }
    ans-=a[node-1];
    if(ans<=0)return dp[node]=1;
    else return dp[node]=ans;
}

void theProgram() {
    int n,m;
    cin>>n>>m;
    vector<vector<int>>adj(n+1);
    vector<int>indeg(n+1);
    for(int i=0;i<m;i++)
    {
        int u,v;
        cin>>u>>v;
        adj[u].pb(v);
        indeg[v]++;
    }

    vi a(n);
    take(a);
    vi dp(n+1,INT_MAX);
    int ans=INT_MAX;
    for(int i=1;i<=n;i++)
    {
        if(!indeg[i])
        {
            ans=min(ans,dfs(i,-1,adj,a,dp));
        }
    }
    cout<<ans<<endl;
}

signed main() {
    MrRoamer();
    // jaldi mat karna varna galti karega 
    // constraints joi leje nakar penalty lagse
    // zyada time lage toh switch the question
#ifndef ONLINE_JUDGE
    freopen("Error.txt", "w", stderr);
#endif
    int t=1;
    cin>>t;
    while(t--){
        theProgram();
    }
    return 0;
}

Digit DP with a string twist!!

Now lets break the constraints and solve them one by one,

1. Lexicographically less can be maintained be a tight variable as a state of dp.

2. No vowel repeated: this can be achieved by maintaining a mask as a state of dp which shows which vowel has occurred,

3. No consecutive consonant more than twice: this can be achieved by keeping last character and its consecutive frequency as a state of dp.

So we total have 5 states of dp,

1. index of string.

2. Tight variable which indicates whether our string is already smaller or not.

3. Last character.

4. Last character's consecutive frequency.

5. Mask showing which vowels already came.

Also don't forget to add the strings less than the length of original string, which can be done by just adding one to dp on every intermediate step.

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

#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> os;
typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> oms;

// find_by_order to find the Kth element
// order_of_key to find number of elements smaller than x
// to erase from oms use order_of_key and than by its index find its iterator using find_by_order than erase it

#define MrRoamer() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define MOD 1000000007
#define MOD1 998244353
#define pb push_back
#define ppb pop_back
#define ff first
#define ss second
#define PI 3.141592653589793238462
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define chal(i,a,b) for(int i=a;i<=b;i++)
#define vi vector<int>
#define vvi vector<vector<int>>
#define prin(x) for(int i=0;i<x.size();i++)cout<<x[i]<<" ";cout<<endl;
#define take(x) for(int i=0;i<x.size();i++)cin>>x[i];

//---------------------------------------------------------------------------------------
typedef long long ll;
typedef unsigned long long ull;
typedef long double lld;

#ifndef ONLINE_JUDGE
#define debug(x) cerr << #x << " "; _print(x); cerr << endl;
#else
#define debug(x)
#endif

void _print(ll t) { cerr << t; }
void _print(int t) { cerr << t; }
void _print(string t) { cerr << t; }
void _print(char t) { cerr << t; }
void _print(lld t) { cerr << t; }
void _print(double t) { cerr << t; }
void _print(ull t) { cerr << t; }

template <class T, class V> void _print(pair <T, V> p);
template <class T> void _print(vector <T> v);
template <class T> void _print(set <T> v);
template <class T, class V> void _print(map <T, V> v);
template <class T> void _print(multiset <T> v);
template <class T, class V> void _print(pair <T, V> p) { cerr << "{"; _print(p.ff); cerr << ","; _print(p.ss); cerr << "}"; }
template <class T> void _print(vector <T> v) { cerr << "[ "; for (T i : v) { _print(i); cerr << " "; } cerr << "]"; }
template <class T> void _print(set <T> v) { cerr << "[ "; for (T i : v) { _print(i); cerr << " "; } cerr << "]"; }
template <class T> void _print(multiset <T> v) { cerr << "[ "; for (T i : v) { _print(i); cerr << " "; } cerr << "]"; }
template <class T, class V> void _print(map <T, V> v) { cerr << "[ "; for (auto i : v) { _print(i); cerr << " "; } cerr << "]"; }

void printos(os v);
void printos(os v){ cerr << "[ "; for (ll i : v) { _print(i); cerr << " "; } cerr << "]"; cerr<<'\n';}
void printos(oms v);
void printos(oms v){ cerr << "[ "; for (ll i : v) { _print(i); cerr << " "; } cerr << "]"; cerr<<'\n';}

//--------------------------code toh yahan hai-----------------------------------

#define int long long

int dp[105][2][26][3][32];

int func(int ind,int f,int lastcons,int frecons,int mask,string &str,set<int>&vow)
{
    if(frecons==3)return 0;
    if(ind==str.size())
    {
        return 1;
    }
    if(dp[ind][f][lastcons][frecons][mask]!=-1)return dp[ind][f][lastcons][frecons][mask];
    int lmt=25;
    if(f)lmt=str[ind]-'a';
    int j=0;
    int ans=0;
    for(int i=0;i<=lmt;i++)
    {
        if(vow.count(i))
        {
            if(((mask>>j)&1)==0)
            {
                ans+=func(ind+1,f&(lmt==i),-1,0,mask|(1<<j),str,vow);
            }
            j++;
        }
        else
        {
            if(i==lastcons)
            {
                ans+=func(ind+1,f&(lmt==i),lastcons,frecons+1,mask,str,vow);
            }
            else
            {
                ans+=func(ind+1,f&(lmt==i),i,1,mask,str,vow);
            }
        }
        ans%=MOD;
    }
    return dp[ind][f][lastcons][frecons][mask]=(ans+1)%MOD;
}

void theProgram() {
    string str;
    cin>>str;
    set<int>vow={'a'-'a','e'-'a','i'-'a','o'-'a','u'-'a'};
    memset(dp,-1,sizeof(dp));
    cout<<(func(0,1,-1,0,0,str,vow)-1+MOD)%MOD<<endl;
}

signed main() {
    MrRoamer();
    // jaldi mat karna varna galti karega 
    // constraints joi leje nakar penalty lagse
    // zyada time lage toh switch the question
#ifndef ONLINE_JUDGE
    freopen("Error.txt", "w", stderr);
#endif
    int t=1;
    // cin>>t;
    while(t--){
        theProgram();
    }
    return 0;
}

Dijkstra on the 2D matrix ?

Simple Dijkstra is enough to pass all test cases.

Just assign unique integer to every $$$(x,y)$$$ and then construct a graph such that there is edge from $$$(x,y)$$$ to $$$(x+1,y)$$$ and $$$(x,y)$$$ to $$$(x,y+1)$$$ of weight 1.Additionally we need to add edge with weight 0 from $$$(x1,y1)$$$ to $$$(x2,y2)$$$ for every portal.

finally run dijkstra from $$$(0,0)$$$ as the source.

Output distance of point $$$(N,N)$$$ as the answer.

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

#ifdef ONLINE_JUDGE
#define debug(...)
#else
#include "debug.h"
#endif

#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()
#define sz(x) (long long)(x).size()
#define pii pair<long long,long long>

long long N;
long long getcordinate(long long i, long long j) {
    return i * N + j;
}

void dijkstra(long long s, vector<long long> & d, vector<vector<pii>> &adj) {
    long long n = adj.size();
    d[s] = 0;
    set<pair<long long, long long>> q;
    q.insert({0, s});
    while (!q.empty()) {
        long long v = q.begin()->second;
        q.erase(q.begin());

        for (auto edge : adj[v]) {
            long long to = edge.first;
            long long len = edge.second;

            if (d[v] + len < d[to]) {
                q.erase({d[to], to});
                d[to] = d[v] + len;
                q.insert({d[to], to});
            }
        }
    }
}

void solve() {
    long long teleporters;
    cin >> N >> teleporters;
    N++;
    vector<pair<pii, pii>> portals;
    for (long long i = 0; i < teleporters; i++) {
        long long x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        portals.pb({{x1, y1}, {x2, y2}});
    }
    vector<vector<pii>> adj((N + 1) * (N + 1));
    for (long long i = 0; i < N; i++) {
        for (long long j = 0; j < N; j++) {
            adj[getcordinate(i, j)].pb({getcordinate(i + 1, j), 1});
            adj[getcordinate(i, j)].pb({getcordinate(i, j + 1), 1});
        }
    }
    for (long long i = 0; i < teleporters; i++) {
        auto [p1, p2] = portals[i];
        adj[getcordinate(p1.f, p1.s)].pb({getcordinate(p2.f, p2.s), 0});
    }
    vector<long long> dist((N + 1) * (N + 1) + 5, INT_MAX);
    dijkstra(0, dist, adj);
    cout << dist[getcordinate(N - 1, N - 1)] << '\n';
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    long long zz = 1;
    // cin >> zz;
    while (zz--) {
        solve();
    }
    return 0;
}

Minimum Segment Tree on a 2D range.

let $$$dp[i]$$$ is the minimum distance needed to walk to the starting point of the $$$i'th$$$ portal.

One way is that you walked directly to the portal i.e $$$dist=x_i+y_i$$$. Otherwise you took some other portal before this. For this possibility the endpoint of portal let $$$(X_j,Y_j)$$$ should have appeared before the start of $$$i'th$$$ portal. i.e $$$( X_j≤x_i)$$$ and $$$( Y_j≤y_i )$$$.Thus we need to calculate the minimum over all such portals for the value of $$$(dp[j]+ (x_i-X_j) + (y_i-Y_j) )$$$.

Observe that instead of storing the value of $$$dp$$$ corresponding to a portal we can store $$$value[i]=dp[i]-x_i-y_i$$$ so that when required by some other portal we can directly calculate $$$dp[i]=x_i+y_i+value[j]$$$.

So we will traverse starting from $$$(0,0)$$$ to $$$(N,N)$$$ in increasing $$$x’s$$$ and calculate the minimum over all the portals value that lie within.

i.e: We need to make a Segment tree on all the possible value of $$$y's$$$ in increasing order.

We put the initial value at all position of $$$y's$$$ in segment tree as $$$INF$$$. Now if we are at starting point $$$(x_i,y_i)$$$ it is guaranteed that all the visited $$$x's$$$ are less or equal to $$$x_i$$$.We just need to query the segment tree on range $$$(0-y_i)$$$ for minimum.

We update the segment tree on encountering a ending portal point $$$(X_j,Y_j)$$$.

For this we can use a minimum segment tree.

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

#ifdef ONLINE_JUDGE
#define debug(...)
#else
#include "debug.h"
#endif

#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()
#define sz(x) (long long)(x).size()
#define pii pair<long long,long long>

template <class T> class SegmentTree {
private:
    const T DEFAULT = 1e16;
    vector<T> segtree;
    long long len;

public:
    T f(T a, T b) { return min(a, b); }
    SegmentTree(long long len) : len(len), segtree(len * 2, DEFAULT) {}
    void set(long long ind, T val) {
        ind += len;
        segtree[ind] = val;
        for (; ind > 1; ind /= 2) {
            segtree[ind / 2] = f(segtree[ind], segtree[ind ^ 1]);
        }
    }
    T range(long long start, long long end) {
        T sum = DEFAULT;
        for (start += len, end += len; start < end; start /= 2, end /= 2) {
            if (start % 2 == 1) { sum = f(sum, segtree[start++]); }
            if (end % 2 == 1) { sum = f(sum, segtree[--end]); }
        }
        return sum;
    }
};

void solve() {
    long long N, M;
    cin >> N >> M;
    vector<array<long long, 4>> portals;
    for (long long i = 0; i < M; i++) {
        long long x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        portals.pb({x1, y1, i, -1});
        portals.pb({x2, y2, i, 1});
    }
    vector<long long> Ans(M);
    sort(all(portals));
    vector<long long> Ys;
    for (auto &i : portals) {
        if (i[3] == 1) {
            Ys.pb(i[1]);
        }
    }
    auto it = unique(all(Ys));
    Ys.resize(distance(Ys.begin(), it));
    sort(all(Ys));
    SegmentTree<long long> seg(sz(Ys));
    map<long long, long long> Y_ans;
    for (auto [x1, y1, index, type] : portals) {
        if (type == -1) {
            long long ans = x1 + y1;
            long long ind = upper_bound(all(Ys), y1) - Ys.begin();
            long long mnn = seg.range(0, ind);
            ans = min(ans, mnn + ans);
            Ans[index] = ans;
        }
        if (type == 1) {
            long long ans = Ans[index];
            long long ind = lower_bound(all(Ys), y1) - Ys.begin();
            if (seg.range(ind, ind + 1) > ans - x1 - y1) {
                seg.set(ind, ans - x1 - y1);
            }
        }
    }
    cout << N + N + seg.range(0, sz(Ys)) << endl;
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    long long zz = 1;
    // cin >> zz;
    while (zz--) {
        solve();
    }
    return 0;
}

Let $$$N$$$ denote total number of lines that are present in a triangle. Then the number of triangle that can be formed is $$$^{N}C_{3}$$$

But you need to observe that if we select 3 of lines from the lines that pass through vertex $$$B$$$ or $$$C$$$ then they do not contribute a triangle thus we need to remove them.

So final ans will be $$$ANS$$$ $$$=$$$ $$$^{N}C_{3}$$$ $$$-$$$ $$$^{P}C_{3}$$$ $$$-$$$ $$$^{Q}C_{3}$$$

Here,

$$$P =$$$ Number of lines passing from $$$B$$$.

$$$Q =$$$ Number of lines passing from $$$C$$$.

We will precompute all the factorials & inverses and then answer queries in $$$O(1)$$$.

(Note: For some people who were getting TLE in $$$O(1)$$$ solution is because they were using $$$endl$$$ instead of '\n' .As number of times $$$endl$$$ is called is of order $$$100000$$$.)

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

#define f first
#define s second

const long long MAXN = 1e6;
const long long MOD = 1e9 + 7;

long long fac[MAXN + 1];
long long inv[MAXN + 1];

long long exp(long long x, long long n, long long m) {
    x %= m;
    long long res = 1;
    while (n > 0) {
        if (n % 2 == 1) { res = res * x % m; }
        x = x * x % m;
        n /= 2;
    }
    return res;
}

void factorial() {
    fac[0] = 1;
    for (long long i = 1; i <= MAXN; i++) { fac[i] = fac[i - 1] * i % MOD; }
}

void inverses() {
    inv[MAXN] = exp(fac[MAXN], MOD - 2, MOD);
    for (long long i = MAXN; i >= 1; i--) { inv[i - 1] = inv[i] * i % MOD; }
}

long long choose(long long n, long long r) { return (fac[n] * inv[r] % MOD * inv[n - r] % MOD) % MOD; }

void solve() {
    long long queries;
    cin >> queries;
    while (queries--) {
        long long a, c;
        cin >> a >> c;
        long long no_of_lines_from_B = c + 2;
        long long no_of_lines_from_C = a + 2;
        long long total_no_lines = a + c + 3;
        long long ansfinal = ((choose(total_no_lines, 3) - choose(no_of_lines_from_B, 3) + MOD) % MOD - choose(no_of_lines_from_C, 3) + MOD) % MOD;
        cout << ansfinal << '\n';
    }
}

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

    long long zz = 1;
    factorial();
    inverses();
    while (zz--) {
        solve();
    }

    return 0;
}

Precomputation : Run a Sieve of Eratosthenes for $$$10^5$$$ elements and add function of factorization in $$$O(log(n))$$$.

If we are able to keep array for each possible prime factor and do the operations on each of the array we are done. But it is impractical to keep all the array corresponding to prime factors so instead we keep a journal ( map<int,vector<pair<int,int>>>) to store $$$L$$$,$$$R$$$ for each prime factor.

Now we traverse over the journal for each prime seen and update a prefix array like for $$$(L,R)$$$ set $$$pref[L]$$$++ and $$$pref[R+1]$$$--. Finally do the prefix sum to get frequency for each position in prefix array.

Now the for each prime seen $$$Ans$$$$$$=$$$$$$Ans$$$ $$$*$$$ $$$prime^{min(all(prefix)}$$$.

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

#ifdef ONLINE_JUDGE
#define debug(...)
#else
#include "debug.h"
#endif

#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()
#define sz(x) (long long)(x).size()
#define pii pair<long long,long long>

const long long mod = 1e9 + 7;

#define MAXN 100001
long long spf[MAXN];
void sieve() {
    spf[0] = -1;
    spf[1] = -1;
    for (long long i = 2; i < MAXN; i++)
        spf[i] = i;
    for (long long i = 4; i < MAXN; i += 2)
        spf[i] = 2;

    for (long long i = 3; i * i < MAXN; i++) {
        if (spf[i] == i) {
            for (long long j = i * i; j < MAXN; j += i)
                if (spf[j] == j)
                    spf[j] = i;
        }
    }
}
vector<long long> getFactorization(long long x) {
    vector<long long> ret;
    while (x != 1) {
        ret.push_back(spf[x]);
        x = x / spf[x];
    }
    return ret;
}

long long binpow(long long a, long long b) {
    long long res = 1;
    while (b > 0) {
        if (b & 1) {
            res = (res * a) % mod;
        }
        a = (a * a) % mod;
        b >>= 1;
    }
    return res;
}

void solve() {
    long long n, q;
    cin >> n >> q;
    unordered_map<long long, vector<pii>> journal;
    vector<long long> pref(n, 0);
    while (q--) {
        long long l, r, x;
        cin >> l >> r >> x;
        l--;
        vector<long long> fact = getFactorization(x);
        for (auto x : fact) {
            journal[x].pb({l, r});
        }
    }
    long long ans = 1;
    for (auto [x, y] : journal) {
        for (auto z : y) {
            pref[z.f]++;
            if (z.s < n) pref[z.s]--;
        }
        for (long long i = 1; i < n; i++) {
            pref[i] += pref[i - 1];
        }
        long long mini = *min_element(all(pref));
        ans = (ans * binpow(x, mini)) % mod;
        fill(all(pref), 0);
    }
    cout << ans % mod << endl;
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    long long zz = 1;
    cin >> zz;
    sieve();
    while (zz--) {
        solve();
    }
    return 0;
}

First question is how to you factor a number around $$$1e9$$$ quickly!

Store all the primes less than $$$\sqrt{n} +1 $$$.The size of such array is around $$$\approx{3500}$$$. For factoring check for all the primes in $$$\approx{3500}$$$ and if still $$$num>1$$$ then num itself is a prime factor. So $$$Q*(3500)$$$ is quick enough to pass.

Observe that we need not keep the entire array of size $$$n$$$ in memory.We only want $$$(L,R)$$$.So we traverse over them only and keep the minimum while traversing the journal.

#include <bits/stdc++.h>
 
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
 
#ifndef ONLINE_JUDGE
    #include "debug.h"
#else
    #define debug(x) 
#endif
 
#define MOD 1000000007
#define INF INT_MAX
#define endl "\n"
#define pb push_back
#define ppb pop_back
#define ff first
#define ss second
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
// #define int long long
 
const int X = 1e9 + 100000;
const int N = sqrtl(X);
vector<bool> isPrime(N, true);
vector<int> primes;
 
bool checkPrime(int n) {
    if(n < 2)
        return false;
 
    for(int i = 2; i * i <= n; i++) {
        if(n % i == 0)
            return false;
    }
 
    return true;
}
 
int binExp(int a, int b, int M){
    a %= M;
    int ans = 1;
    while(b){
        if(b & 1)
            ans = (ans * 1LL * a) % M;
        a = (a * 1LL * a) % M;
        b >>= 1;
    }
    return ans;
}
 
map<int, int> factorise(int n) {
    map<int, int> factors;
    for(auto &p: primes) {
        while(n % p == 0) {
            factors[p]++;
            n /= p;
        }
    }
 
    if(n > 1) factors[n]++;
    return factors;
}
 
void solve() {
    int n, q;
    cin >> n >> q;
 
    map<int, map<int, int>> mp;
 
    while(q--) {
        int l, r, x;
        cin >> l >> r >> x;
 
        auto factors = factorise(x);
 
        for(auto &[p, e]: factors) {
            mp[p][r + 1] -= e;
            mp[p][l] += e;
        }
    }
 
    int gcd = 1;
    for(auto &[p, v]: mp) {
        int e = INF;
 
        int sum = 0;
        int first = n + 1;
 
        for(auto &[i, val]: v) {
            first = min(first, i);
 
            sum += val;
            if(i <= n) e = min(e, sum);
        }
 
        if(first > 1) e = 0;
 
        gcd = (gcd * 1ll * binExp(p, e, MOD)) % MOD;
    }
 
    cout << gcd << endl;
}
 
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
 
    isPrime[0] = isPrime[1] = false;
    for(int i = 2; i < N; i++){
        if(isPrime[i]){
            primes.push_back(i);
            for(int j = 2 * i; j < N; j += i){
                isPrime[j] = false;
            }
        }
    }
    
    int tt = 1;
    cin >> tt;
    while(tt--) {
        solve();       
    }
    return 0;
}

You still keep the prefix array in memory but make it sparce. Only take in prefix array indexes which are accesed.

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

#ifdef ONLINE_JUDGE
#define debug(...)
#else
#include "debug.h"
#endif

#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()
#define sz(x) (long long)(x).size()
#define pii pair<long long,long long>

const long long mod = 1e9 + 7;
long long binpow(long long a, long long b) {
    long long res = 1;
    while (b) {
        if (b & 1) {
            res = (res * 1ll * a) % mod;
        }
        a = (a * 1ll * a) % mod;
        b >>= 1;
    }
    return res;
}

long long inv(long long x) {
    return binpow(x, mod - 2);
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    long long zz = 1;
    bool prime[100000];
    memset(prime, true, sizeof(prime));
    prime[0] = prime[1] = false;
    for (long long i = 2; i <= sqrt(1e5); i++) {
        if (prime[i]) {
            for (long long j = i * i; j <= 1e5; j += i) {
                prime[j] = false;
            }
        }
    }
    vector<long long> facs;
    for (long long i = 2; i <= sqrt(1e9); i++) {
        if (prime[i]) {
            facs.pb(i);
        }
    }
    cin >> zz;
    while (zz--) {
        long long n, q;
        cin >> n >> q;
        unordered_map<long long, vector<array<long long, 3>>> ranges;
        while (q--) {
            long long l, r, x;
            cin >> l >> r >> x;
            for (auto y : facs) {
                if (x < y)break;
                long long cnt = 0;
                while (x % y == 0) {
                    cnt++;
                    x /= y;
                }
                if (cnt) {
                    ranges[y].pb({l, r, cnt});
                }
            }
            if (x > 1) {
                ranges[x].pb({l, r, 1});
            }
        }
        long long ans = 1;
        for (auto x : ranges) {
            vector<long long> prefs;
            prefs.pb(1);
            for (auto y : x.s) {
                prefs.pb(y[0]);
                prefs.pb(min(n, y[0] + 1));
                prefs.pb(y[1]);
                prefs.pb(min(n, y[1] + 1));
            }
            prefs.pb(n);
            sort(all(prefs));
            auto it = unique(all(prefs));
            prefs.resize(distance(prefs.begin(), it));
            unordered_map<long long, long long> pos;
            for (long long i = 0; i < sz(prefs); i++) {
                pos[prefs[i]] = i;
            }
            for (long long i = 0; i < sz(prefs); i++) {
                prefs[i] = 0;
            }
            for (auto y : x.s) {
                prefs[pos[y[0]]] += y[2];
                prefs[pos[y[1]] + 1] -= y[2];
            }
            for (long long i = 1; i < sz(prefs); i++) {
                prefs[i] += prefs[i - 1];
            }
            long long val = *min_element(all(prefs));
            ans = (ans * binpow(x.f, val)) % mod;
        }
        cout << ans << '\n';
    }
    return 0;
}

Look at Nirbhay's Solution.

He has hardcoded the factorization of number.Although it is not the intended Solution it works!!

Relevant link to why this works.

Store a 2D array $$$pref[33][n]$$$ where for each $$$i$$$ , $$$pref[i]$$$ represent array where $$$i'th$$$ bit is checked.Initialize a sieve and while traversing the array if $$$arr[j]$$$ is not a prime then for all bits from $$$0$$$ to $$$32$$$ set $$$pref[i][j]$$$ as $$$1$$$ if $$$arr[j]$$$ is not prime and $$$i'th$$$ bit is set in $$$arr[j]$$$.

To quickly answer queries on range $$$(L,R)$$$ we will calculate prefix sum for each bits.

#include <bits/stdc++.h>
 
using namespace std;
 
#ifndef ONLINE_JUDGE
    #include "debug.h"
#else
    #define debug(...) 
#endif
 
#define MOD 1000000007
#define INF 1e18
#define endl "\n"
#define pb push_back
#define ppb pop_back
#define ff first
#define ss second
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define int long long
 
const int N = 1e5 + 10;
std::vector<int> isPrime(N, true);
 
void solve() {
    int n, q;
    cin >> n >> q;
 
    vector<int> a(n + 1);
    vector<vector<int>> psum(40, vector<int>(n + 1));
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
 
        for(int j = 0; j < 40; j++) {
            psum[j][i] = psum[j][i - 1] + (!isPrime[a[i]] and ((1ll << j) & a[i]));
        }
    }
 
    while(q--) {
        int l, r, k;
        cin >> l >> r >> k;
 
        k--;
        cout << psum[k][r] - psum[k][l - 1] << endl;
    }
}
 
signed main() {
    ios::sync_with_stdio(false); cin.tie(0);
 
    isPrime[0] = isPrime[1] = false;
    for(int i = 2; i < N; i++){
        if(isPrime[i])
            for(int j = 2 * i; j < N; j += i){
                isPrime[j] = false;
            }
    }
    
    int tt = 1;
    // cin >> tt;
    while(tt--) {
        solve();       
    }
    return 0;
}

First, we track the quantities of white and black cards offered by individuals(in order of their arrival) in two separate vectors of pairs(one for black and one for white) — $$$q1$$$ and $$$q2$$$, where each pair stores a person's ID and the quantity of cards they offer. While black(or white or both) cards are not exhausted, and there is a scope of exchange, we run a loop to check the quantities of cards each person offers and pair them with available cards of the opposite type. The loop ensures that partial exchanges are possible. The total quantity exchanged between each pair of individuals is tracked in a map by keeping smaller value first and the larger second in each pair, ensuring that the order of IDs doesn't matter.

#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main() {
    ios::sync_with_stdio(false);
    int t; cin >> t;
    while (t--) {
        int n, q; cin >> n >> q;
        vector<pair<int, int>> q1, q2;
        map<pair<int, int>, int> m;
        while (n--) {
            int id;
            string s;
            int qnt;
            cin >> id >> s >> qnt;
            if (s[0] == 'W')q1.push_back({id, qnt});
            else q2.push_back({id, qnt});
        }
        int i = 0, j = 0;
        while (true) {
            if (i == q1.size() || j == q2.size())break;
            int id1 = q1[i].first;
            int id2 = q2[j].first;
            int qnt1 = q1[i].second;
            int qnt2 = q2[j].second;
            if (qnt1 > qnt2) {
                m[ {min(id1, id2), max(id1, id2)}] += qnt2;
                q1[i].second -= qnt2;
                j++;
            }
            else if (qnt2 > qnt1) {
                m[ {min(id1, id2), max(id1, id2)}] += qnt1;
                q2[j].second -= qnt1;
                i++;
            }
            else {
                m[ {min(id1, id2), max(id1, id2)}] += qnt1;
                i++;
                j++;
            }
        }
        while (q--) {
            int id1, id2; cin >> id1 >> id2;
            if (m.find({min(id1, id2), max(id1, id2)}) != m.end())cout << m[ {min(id1, id2), max(id1, id2)}] << "\n";
            else cout << 0 << "\n";
        }
    }
    return 0;
}