結果

問題 No.1234 典型RMQ
ユーザー anagohirameanagohirame
提出日時 2020-09-19 03:52:05
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 4,352 bytes
コンパイル時間 330 ms
コンパイル使用メモリ 87,152 KB
実行使用メモリ 94,504 KB
最終ジャッジ日時 2023-09-27 06:52:36
合計ジャッジ時間 5,092 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 70 ms
71,456 KB
testcase_01 AC 70 ms
71,448 KB
testcase_02 AC 75 ms
71,412 KB
testcase_03 AC 68 ms
71,308 KB
testcase_04 AC 69 ms
71,320 KB
testcase_05 AC 68 ms
71,616 KB
testcase_06 TLE -
testcase_07 AC 796 ms
87,508 KB
testcase_08 TLE -
testcase_09 AC 1,341 ms
90,420 KB
testcase_10 AC 1,965 ms
92,348 KB
testcase_11 AC 1,993 ms
91,192 KB
testcase_12 AC 1,158 ms
88,824 KB
testcase_13 AC 804 ms
86,760 KB
testcase_14 AC 1,136 ms
89,668 KB
testcase_15 AC 1,058 ms
90,052 KB
testcase_16 AC 1,784 ms
93,812 KB
testcase_17 AC 1,093 ms
89,488 KB
testcase_18 AC 473 ms
85,688 KB
testcase_19 AC 1,744 ms
94,008 KB
testcase_20 AC 1,433 ms
93,156 KB
testcase_21 TLE -
testcase_22 AC 1,753 ms
94,504 KB
testcase_23 AC 1,655 ms
94,336 KB
testcase_24 AC 1,689 ms
94,408 KB
testcase_25 AC 1,690 ms
94,188 KB
testcase_26 AC 1,648 ms
94,328 KB
testcase_27 AC 69 ms
71,472 KB
testcase_28 AC 69 ms
71,372 KB
testcase_29 AC 67 ms
71,488 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
def input():
	return sys.stdin.buffer.readline()[:-1]

class LazySegTree():
	def __init__(self, a, func, unit, oper, comp, idem):
		#the number of nodes is 2n-1
		self.hght = len(a).bit_length()
		self.n = 1 << self.hght
		self.size = len(a)
		self.func = func #(ele, ele) -> ele
		self.unit = unit #ele
		self.oper = oper #(ele, op) -> ele
		self.comp = comp #(op, op) -> op
		self.idem = idem #op
		self.node = [unit] * (2 * self.n)
		#immediate evaluation enables size reduction
		self.lazy = [idem] * self.n
		for i in range(self.size + self.n - 1, 0, -1):
			if i >= self.n:
				self.node[i] = a[i - self.n]
			else:
				self.update(i)

	def update(self, k):
		self.node[k] = self.func(self.node[2 * k], self.node[2 * k + 1])
		return

	def apply_node_lazy(self, k, op):
		self.node[k] = self.oper(op, self.node[k])
		if k < self.n:
			self.lazy[k] = self.comp(op, self.lazy[k])
		return

	def push(self, k):
		self.apply_node_lazy(2 * k, self.lazy[k])
		self.apply_node_lazy(2 * k + 1, self.lazy[k])
		self.lazy[k] = self.idem
		return

	def set(self, k, x):
		k += self.n
		for i in range(self.hght, 0, -1):
			self.push(k >> i)

		self.node[k] = x
		
		while k > 1:
			k >>= 1
			self.update(k)
		return

	def get(self, k):
		k += self.n
		for i in range(self.hght, 0, -1):
			self.push(k >> i)
		
		return self.node[k]

	#[l, r)
	def prod(self, l, r):
		if l == r:
			return self.unit
		l += self.n
		r += self.n
		
		for i in range(self.hght, 0, -1):
			if ((l >> i) << i) != l:
				self.push(l >> i)
			if ((r >> i) << r) != r:
				self.push(r >> i)

		s_l, s_r = self.unit, self.unit
		while l < r:
			if l & 1:
				s_l = self.func(s_l, self.node[l])
				l += 1
			if r & 1:
				r -= 1
				s_r = self.func(self.node[r], s_r)
			l >>= 1
			r >>= 1
		return self.func(s_l, s_r)

	def all_prod(self):
		return self.node[1]

	def point_apply(self, k, op):
		k += self.n
		for i in range(self.hght, 0, -1):
			self.push(k >> i)
		
		self.node[k] = self.oper(op, self.node[k])
		
		while k > 1:
			k >>= 1
			self.update(k)
		return

	#operate to [l, r)
	def apply(self, l, r, op):
		if l == r:
			return
		l += self.n
		r += self.n
		
		for i in range(self.hght, 0, -1):
			if ((l >> i) << i != l):
				self.push(l >> i)
			if ((r >> i) << i != r):
				self.push((r - 1) >> i)

		l_pres, r_pres = l, r
		while l < r:
			if l & 1:
				self.apply_node_lazy(l, op)
				l += 1
			if r & 1:
				r -= 1
				self.apply_node_lazy(r, op)
			l >>= 1
			r >>= 1
		l, r = l_pres, r_pres

		for i in range(1, self.hght+1):
			if ((l >> i) << i != l):
				self.update(l >> i)
			if ((r >> i) << i != r):
				self.update((r - 1) >> i)
		return

	#maximum of r (within [l, n)) which satisfies val(prod(l, r))
	def max_right(self, l, val):
		if l == self.size:
			return self.size
		l += self.n
		for i in range(self.hght, 0, -1):
			self.push(l >> i)

		s = self.unit
		while True:
			while l % 2 == 0:
				l >>= 1
			if not val(self.func(s, self.node[l])):
				while l < self.n:
					self.push(l) #before descending
					l <<= 1
					if val(self.func(s, self.node[l])):
						s = self.func(s, self.node[l])
						l += 1
				return l - self.n
			s = self.func(s, self.node[l])
			l += 1
			if (l & -l) == l:
				return self.size

	#minimum of l (within [0, r)) which satisfies val(prod(l, r))
	def min_left(self, r, val):
		if r == 0:
			return 0
		r += self.n
		for i in range(self.hght, 0, -1):
			self.push((r - 1) >> i)

		s = self.unit
		while True:
			r -= 1
			while r > 1 and r % 2:
				r >>= 1
			if not val(self.func(self.node[r], s)):
				while r < self.n:
					self.push(r) #before descending
					r = (r << 1) + 1
					if val(self.func(self.node[r], s)):
						s = self.func(self.node[r], s)
						r -= 1
				return r + 1 - self.n
			s = self.func(self.node[r], s)
			if (r & -r) == r:
				return 0

"""
node: (value, size)
lazy: value
"""
from operator import add
"""
def func(x, y):
	return min(x, y)

unit = 2 * (10 ** 10)

def oper(value, x):
	return x + value

def comp(f1, f2):
	return f1 + f2

idem = 0
"""
n = int(input())
a = list(map(int, input().split()))
st = LazySegTree(a, min, 22000000000, add, add, 0)
ans = []
for _ in range(int(input())):
	k, l, r, c = map(int, input().split())
	if k == 1:
		if l == r:
			st.point_apply(l-1, c)
		else:
			st.apply(l-1, r, c)
	else:
		ans.append(st.prod(l-1, r))
print(*ans, sep="\n")
0