COOLCHEF - help needed with TLE

1

https://www.codechef.com/viewsolution/24881704

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

2

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

2 Likes
3

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
4

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

5

Thanks, will optimise that.