Submission #571359

#TimeUsernameProblemLanguageResultExecution timeMemory
571359dnialhSimple game (IZhO17_game)Pypy 3
100 / 100
563 ms63452 KiB
class SegmentTree: def __init__(self, data, default=0, func=lambda x, y: x + y): """initialize the segment tree with data""" self._default = default self._func = func self._len = len(data) self._size = _size = 1 << (self._len - 1).bit_length() self.data = [default] * (2 * _size) self.data[_size:_size + self._len] = data for i in reversed(range(_size)): self.data[i] = func(self.data[i + i], self.data[i + i + 1]) def __delitem__(self, idx): self[idx] = self._default def __getitem__(self, idx): return self.data[idx + self._size] def __setitem__(self, idx, value): idx += self._size self.data[idx] = value idx >>= 1 while idx: self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1]) idx >>= 1 def __len__(self): return self._len def query(self, start, stop): """func of data[start, stop)""" start += self._size stop += self._size res_left = res_right = self._default while start < stop: if start & 1: res_left = self._func(res_left, self.data[start]) start += 1 if stop & 1: stop -= 1 res_right = self._func(self.data[stop], res_right) start >>= 1 stop >>= 1 return self._func(res_left, res_right) def __repr__(self): return "SegmentTree({0})".format(self.data) import sys input = sys.stdin.readline N, M = map(int, input().split()) seg = SegmentTree([0] * 1000100) l = list(map(int, input().split())) for i in range(N - 1): v1, v2 = l[i], l[i + 1] v1, v2 = min(v1, v2), max(v1, v2) seg[v1] += 1 seg[v2] -= 1 out = [] for _ in range(M): t = tuple(map(int, input().split())) if t[0] == 1: p, v = t[1], t[2] p -= 1 if p > 0: v1, v2 = l[p], l[p - 1] v1, v2 = min(v1, v2), max(v1, v2) seg[v1] -= 1 seg[v2] += 1 if p < N - 1: v1, v2 = l[p], l[p + 1] v1, v2 = min(v1, v2), max(v1, v2) seg[v1] -= 1 seg[v2] += 1 l[p] = v if p > 0: v1, v2 = l[p], l[p - 1] v1, v2 = min(v1, v2), max(v1, v2) seg[v1] += 1 seg[v2] -= 1 if p < N - 1: v1, v2 = l[p], l[p + 1] v1, v2 = min(v1, v2), max(v1, v2) seg[v1] += 1 seg[v2] -= 1 else: out.append(seg.query(0, t[1])) print('\n'.join(map(str, out)))
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...