PAST4K

PAST4K

Thoughts.

Consider what happens when combined

The maximum n when calculated alone before combining is 10^5.

what to do about it

Samples came through, but WA.

I also do TLEs.

Test if WA disappears by shifting 1

no good

The much was 10^9!

WA gone but 3 TLE

Inline deployment, if this doesn't work, don't.

It didn't work.

What more can you do?

Why is there 5 seconds to time out when it's 3 x 10^5 to begin with?

So 300,000 is no good, but 100,000 each is OK?

Still, 3 TLE.

I tried Cython, but no luck.

Should it be written in C++?

Official Explanation

Good policy.

It's not a good idea to use a phoenix tree to find the number of overturns every time the same column is used repeatedly.

The number of falls and frequency table should have been preprocessed.

The reason why the sum of column lengths is kept small is that it is not TLE to use a phoenix tree in preprocessing, but the intention is not to use it for every query because the query may choose only long columns.

AC

code:python

def solve(K, seqs, Q, BS):

MOD = 10 ** 9

N = 20

invs = []

freqs = []

for i in range(K):

init(N)

inv = 0

bit_add(a, 1)

inv += bit_sum(N) - bit_sum(a)

invs.append(inv)

freqs.append(freq)

ret = 0

for b in BS:

for i in range(1, 21):

for j in range(i + 1, 21):

for i in range(1, 21):

ret %= MOD

return ret

---