結果
問題 | No.1891 Static Xor Range Composite Query |
ユーザー | Navier_Boltzmann |
提出日時 | 2024-03-12 08:04:12 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 2,120 bytes |
コンパイル時間 | 297 ms |
コンパイル使用メモリ | 81,572 KB |
実行使用メモリ | 341,904 KB |
最終ジャッジ日時 | 2024-03-12 08:05:12 |
合計ジャッジ時間 | 58,074 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 48 ms
63,640 KB |
testcase_01 | AC | 52 ms
63,640 KB |
testcase_02 | AC | 52 ms
63,640 KB |
testcase_03 | AC | 54 ms
63,640 KB |
testcase_04 | AC | 54 ms
63,640 KB |
testcase_05 | AC | 54 ms
63,640 KB |
testcase_06 | AC | 55 ms
63,640 KB |
testcase_07 | AC | 57 ms
63,640 KB |
testcase_08 | AC | 55 ms
63,640 KB |
testcase_09 | AC | 54 ms
63,640 KB |
testcase_10 | AC | 54 ms
63,640 KB |
testcase_11 | AC | 182 ms
79,680 KB |
testcase_12 | AC | 193 ms
79,892 KB |
testcase_13 | AC | 186 ms
79,792 KB |
testcase_14 | AC | 194 ms
79,788 KB |
testcase_15 | AC | 165 ms
79,652 KB |
testcase_16 | AC | 205 ms
80,480 KB |
testcase_17 | AC | 181 ms
79,792 KB |
testcase_18 | AC | 231 ms
79,812 KB |
testcase_19 | AC | 195 ms
79,856 KB |
testcase_20 | AC | 189 ms
79,676 KB |
testcase_21 | AC | 4,901 ms
341,768 KB |
testcase_22 | AC | 4,953 ms
341,892 KB |
testcase_23 | AC | 4,903 ms
341,900 KB |
testcase_24 | AC | 4,909 ms
341,772 KB |
testcase_25 | TLE | - |
testcase_26 | TLE | - |
testcase_27 | TLE | - |
testcase_28 | TLE | - |
testcase_29 | TLE | - |
testcase_30 | AC | 4,937 ms
341,904 KB |
ソースコード
# import pypyjit # pypyjit.set_param("max_unroll_recursion=-1") from collections import * from functools import * from itertools import * from heapq import * import sys, math,random,time # input = sys.stdin.readline class XorSegmentTree: def __init__(self, A, f, E): self.N = len(A) self.ST = [[] for _ in range(self.N * 2 - 1)] self.f = f self.E = E for i in range(self.N): self.ST[self.N - 1 + i].append(A[i]) for i in range(self.N - 2, -1, -1): cnt = len(self.ST[i * 2 + 1]) for j in range(cnt): self.ST[i].append(f(self.ST[i * 2 + 1][j], self.ST[i * 2 + 2][j])) for j in range(cnt): self.ST[i].append(f(self.ST[i * 2 + 2][j], self.ST[i * 2 + 1][j])) def _range_fold(self, L, R, x, i=0, l=0, r=None): if r is None: r = self.N if r <= L or R <= l: return self.E elif L <= l and r <= R: assert x < len(self.ST[i]) return self.ST[i][x] else: p = (r - l) // 2 m = (l + r) // 2 if (x & p) == 0: resL = self._range_fold(L, R, x, i * 2 + 1, l, m) resR = self._range_fold(L, R, x, i * 2 + 2, m, r) return self.f(resL, resR) else: resL = self.E if R >= m: resL = self._range_fold(max(L, m) - p, R - p, x ^ p, i * 2 + 1, l, m) resR = self.E if L < m: resR = self._range_fold(L + p, min(R, m) + p, x ^ p, i * 2 + 2, m, r) return self.f(resR, resL) def range_fold(self, L, R, x): return self._range_fold(L, R, x, 0, 0, self.N) N,Q = map(int,input().split()) mod = 998244353 def segfunc(y,x): return (x[0]*y[0]%mod,(x[0]*y[1]+x[1])%mod) ide_ele = (1,0) X = [] for _ in range(N): X.append(tuple(map(int,input().split()))) T = XorSegmentTree(X,segfunc,ide_ele) for _ in range(Q): l,r,p,x = map(int,input().split()) a,b = T.range_fold(l,r,p) print((a*x+b)%mod)