PAST4K

PAST4K

考えたこと

結合した時にどうなるか考察

結合する前に単独で計算する時のnが最大で10^5だ

どうするのか

サンプルは通ったがWA

TLEもしてる

1ずらしてWAが消えるかテスト

だめ

あまりが10^9だった！

WA消えたが3TLE

インライン展開した、これでだめならダメ

ダメだった

これ以上に何ができるのか

そもそも3×10^5なのに、なぜ5秒もあるのがタイムアウトするのか

30万だとダメだが10万ずつだとOKなのか？

それでも3TLE

Cythonにしてみたけどダメ

C++で書くべきか？

公式解説

方針は良い

同じ列が繰り返し使われる時に毎回フェニック木で転倒数を求めていたのがよくない

転倒数と頻度表を前処理すべきだった

列の長さの和が小さく抑えられているのは、前処理でフェニック木を使うのはTLEしないが、クエリのたびに使うとクエリが長い列ばかり選ぶ場合があってNGという意図

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