COOLCHEF - help needed with TLE

Performed several optimisations but couldn’t manage to get AC.
Any kind of help is appreciated.

Try running ur query block in Qlog(N) without using lower/upper_bound, it’s easy to think


First few things I can see:

  1. Change ll mul(ll x,ll y) to inline ll mul(ll x,ll y)
  2. Remove the redundant if statement in mul
  3. Precompute factorials and their inverses more efficiently and also precompute modular inverses for each element.
    My code for this:
fact[0] = 1;
for( int i=1; i<=n; ++i )
	fact[i] = 1ll*i*fact[i-1] %m;
ifac[n] = power(fact[n], m-2);
for( int i=n; i>0; --i )
	ifac[i-1] = 1ll*i*ifac[i] %m;
for( int i=1; i<=n; ++i )
	modinv[i] = 1ll*ifac[i]*fact[i-1] %m;

I will edit this if I see more.

1 Like

Thanks, will try to remove lower/upper bound and precompute them.

Thanks, will optimise that.