結果
問題 | No.2327 Inversion Sum |
ユーザー |
![]() |
提出日時 | 2023-05-09 18:35:48 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 1,583 bytes |
コンパイル時間 | 149 ms |
コンパイル使用メモリ | 81,748 KB |
実行使用メモリ | 92,428 KB |
最終ジャッジ日時 | 2024-11-26 07:39:55 |
合計ジャッジ時間 | 5,298 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 WA * 1 |
other | AC * 6 WA * 24 |
ソースコード
class segt:def __init__(self, n, ele, calc):self.num = 2 ** (n - 1).bit_length()self.el = eleself.data = [ele] * (2 * self.num)self.calc = calcdef update(self, idx, x):idx += self.num - 1self.data[idx] = xwhile idx > 0:idx = (idx - 1) // 2self.data[idx] = self.calc(self.data[2*idx+1], self.data[2*idx+2])def renew(self, idx, x):self.update(idx, self.calc(self.get(idx), x))def prod(self, left, right):l = left + self.numr = right + self.numres = self.elwhile l < r:if l % 2:res = self.calc(res, self.data[l-1])l += 1if r % 2:r -= 1res = self.calc(res, self.data[r-1])l //= 2r //= 2return resdef get(self, idx):return self.data[idx+self.num-1]def add(x, y):return x + yn, m = map(int, input().split())mod = 998244353fac = [1]for i in range(n):fac.append(fac[i]*(i+1)%mod)idx = [-1] * nst1 = segt(n, 0, add)for _ in range(m):p, k = map(lambda x: int(x)-1, input().split())st1.update(k, 1)idx[p] = kst2 = segt(n, 0, add)st3 = segt(n, 0, add)s = 0ans = 0for i in range(n):if idx[i] == -1:ans += s * fac[n-m-1] % modcnd = i - st2.prod(0, i)ans += cnd * ((n - m) * (n - m - 1) // 2) * fac[n-m-2] % modelse:st2.update(i, 1)st3.update(idx[i], 1)ans += st1.prod(idx[i]+1, n) * fac[n-m] % modcnd = i - st2.prod(0, i)ans += cnd * ((n - idx[i]) - st1.prod(idx[i], n)) * fac[n-m-1] % mods += idx[i] - st3.prod(0, idx[i])ans %= modprint(ans)