結果
| 問題 | No.1099 Range Square Sum |
| ユーザー |
 shotoyoo
|
| 提出日時 | 2021-06-21 23:56:31 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 5,394 bytes |
| コンパイル時間 | 309 ms |
| コンパイル使用メモリ | 82,304 KB |
| 実行使用メモリ | 183,624 KB |
| 最終ジャッジ日時 | 2024-06-22 22:58:19 |
| 合計ジャッジ時間 | 6,791 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge4 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 39 ms
59,392 KB |
| testcase_01 | AC | 42 ms
53,760 KB |
| testcase_02 | WA | - |
| testcase_03 | AC | 37 ms
54,144 KB |
| testcase_04 | AC | 39 ms
54,016 KB |
| testcase_05 | AC | 39 ms
54,144 KB |
| testcase_06 | WA | - |
| testcase_07 | AC | 37 ms
54,016 KB |
| testcase_08 | AC | 42 ms
53,632 KB |
| testcase_09 | AC | 41 ms
53,888 KB |
| testcase_10 | WA | - |
| testcase_11 | AC | 217 ms
79,360 KB |
| testcase_12 | AC | 202 ms
79,360 KB |
| testcase_13 | AC | 206 ms
79,104 KB |
| testcase_14 | AC | 210 ms
78,976 KB |
| testcase_15 | AC | 211 ms
79,232 KB |
| testcase_16 | AC | 200 ms
79,360 KB |
| testcase_17 | AC | 208 ms
79,104 KB |
| testcase_18 | AC | 196 ms
79,360 KB |
| testcase_19 | AC | 207 ms
79,232 KB |
| testcase_20 | AC | 204 ms
79,872 KB |
| testcase_21 | TLE | - |
| testcase_22 | -- | - |
| testcase_23 | -- | - |
| testcase_24 | -- | - |
| testcase_25 | -- | - |
| testcase_26 | -- | - |
| testcase_27 | -- | - |
| testcase_28 | -- | - |
| testcase_29 | -- | - |
| testcase_30 | -- | - |
ソースコード
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(2*10**5+10)
write = lambda x: sys.stdout.write(x+"\n")
debug = lambda x: sys.stderr.write(x+"\n")
writef = lambda x: print("{:.12f}".format(x))
### 遅延評価セグメント木(はやい非DFS)
class LSG:
def __init__(self,n, a=None):
self._n = n
self._ninf = ninf
self._op = op
self._mapping = mapping
self._composition = composition
self._f0 = f0
x = 0
while (1 << x) < self._n:
x += 1
self._log = x
self._size = 1 << self._log
self._d = [self._ninf] * (2 * self._size)
self._lz = [self._f0] * self._size
if a is not None:
for i in range(self._n):
self._d[self._size + i] = a[i]
for i in range(self._size - 1, 0, -1):
self._update(i)
def check(self):
return [self.query_point(p) for p in range(self._n)]
def update_point(self, p, x):
p += self._size
for i in range(self._log, 0, -1):
self._push(p >> i)
self._d[p] = x
for i in range(1, self._log + 1):
self._update(p >> i)
def query_point(self, p):
p += self._size
for i in range(self._log, 0, -1):
self._push(p >> i)
return self._d[p]
def query(self, left, right):
if left == right:
return self._ninf
left += self._size
right += self._size
for i in range(self._log, 0, -1):
if ((left >> i) << i) != left:
self._push(left >> i)
if ((right >> i) << i) != right:
self._push(right >> i)
sml = self._ninf
smr = self._ninf
while left < right:
if left & 1:
sml = self._op(sml, self._d[left])
left += 1
if right & 1:
right -= 1
smr = self._op(self._d[right], smr)
left >>= 1
right >>= 1
return self._op(sml, smr)
def query_all(self):
return self._d[1]
def update(self, left, right, f):
if right is None:
p = left
p += self._size
for i in range(self._log, 0, -1):
self._push(p >> i)
self._d[p] = self._mapping(f, self._d[p])
for i in range(1, self._log + 1):
self._update(p >> i)
else:
if left == right:
return
left += self._size
right += self._size
for i in range(self._log, 0, -1):
if ((left >> i) << i) != left:
self._push(left >> i)
if ((right >> i) << i) != right:
self._push((right - 1) >> i)
l2 = left
r2 = right
while left < right:
if left & 1:
self._all_apply(left, f)
left += 1
if right & 1:
right -= 1
self._all_apply(right, f)
left >>= 1
right >>= 1
left = l2
right = r2
for i in range(1, self._log + 1):
if ((left >> i) << i) != left:
self._update(left >> i)
if ((right >> i) << i) != right:
self._update((right - 1) >> i)
def _update(self, k):
self._d[k] = self._op(self._d[2 * k], self._d[2 * k + 1])
def _all_apply(self, k, f) -> None:
self._d[k] = self._mapping(f, self._d[k])
if k < self._size:
self._lz[k] = self._composition(f, self._lz[k])
def _push(self, k):
self._all_apply(2 * k, self._lz[k])
self._all_apply(2 * k + 1, self._lz[k])
self._lz[k] = self._f0
def loc(self, l, r):
return self._lz[self._size+l : self._size+r]
def t2i(*vs):
n = len(vs)+1
nvs = [1]
val = 1
for v in vs[::-1]:
val *= v
nvs.append(val)
vs = nvs[::-1]
tos = "def to(%s):\n" % (",".join([f"v{i}" for i in range(n)]))
tos += " val = 0\n"
for i,v in enumerate(vs):
tos += f" val += {v} * v{i}\n"
tos += " return val"
frms = f"def frm(val):\n"
for i in range(n-1):
frms += f" v{i},val = divmod(val, {vs[i]})\n"
frms += " return %s" % ((", ".join([f"v{i}" for i in range(n-1)]) + ", val"))
return tos, frms
def op(x,y):
x = frm(x)
y = frm(y)
return to(x[0]+y[0], x[1]+y[1], x[2]+y[2])
def mapping(f,x):
x = frm(x)
return to(
x[0] + f*x[2],
x[1] + f*f*x[2] + f*x[0]*2,
x[2]
)
# composition: あとからきたクエリがf1に入る
def composition(f1,f2):
return f1+f2
n = int(input())
tos, frms = t2i(10**18,n)
exec(tos)
exec(frms)
ninf = to(0,0,0) # (和, 2乗和, 個数)
f0 = 0
a = list(map(int, input().split()))
sg = LSG(n, [to(v,v*v,1) for v in a])
q = int(input())
ans = []
for i in range(q):
s = input().split()
if s[0]=="1":
_,l,r,x = map(int, s)
l -= 1
r -= 1
sg.update(l,r+1,x)
else:
_,l,r = map(int, s)
l -= 1
r -= 1
val = sg.query(l,r+1)
val = frm(val)
ans.append(val[1])
# ans.append(val[0]**2-2*val[1])
write("\n".join(map(str, ans)))