Submission #571359

#	Time	Username	Problem	Language	Result	Execution time	Memory
571359		dnialh	Simple game (IZhO17_game)	Pypy 3	100 / 100	563 ms	63452 KiB

game

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)))

• Subtask 1: 22 / 22
• Subtask 2: 27 / 27
• Subtask 3: 51 / 51