oj.uz

Submission #571359

# Submission time Handle Problem Language Result Execution time Memory
571359 2022-06-01T23:12:39 Z dnialh Simple game (IZhO17_game) PyPy 3
100 / 100
 563 ms 63452 KB 
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.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 43048 KB Output is correct
2 Correct 100 ms 44128 KB Output is correct
3 Correct 89 ms 44072 KB Output is correct
4 Correct 108 ms 43992 KB Output is correct
5 Correct 93 ms 43828 KB Output is correct
6 Correct 92 ms 44232 KB Output is correct
7 Correct 86 ms 44196 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 43048 KB Output is correct
2 Correct 100 ms 44128 KB Output is correct
3 Correct 89 ms 44072 KB Output is correct
4 Correct 108 ms 43992 KB Output is correct
5 Correct 93 ms 43828 KB Output is correct
6 Correct 92 ms 44232 KB Output is correct
7 Correct 86 ms 44196 KB Output is correct
8 Correct 214 ms 56208 KB Output is correct
9 Correct 267 ms 59780 KB Output is correct
10 Correct 262 ms 60136 KB Output is correct
11 Correct 196 ms 55296 KB Output is correct
12 Correct 244 ms 59324 KB Output is correct
13 Correct 225 ms 59620 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 43048 KB Output is correct
2 Correct 100 ms 44128 KB Output is correct
3 Correct 89 ms 44072 KB Output is correct
4 Correct 108 ms 43992 KB Output is correct
5 Correct 93 ms 43828 KB Output is correct
6 Correct 92 ms 44232 KB Output is correct
7 Correct 86 ms 44196 KB Output is correct
8 Correct 214 ms 56208 KB Output is correct
9 Correct 267 ms 59780 KB Output is correct
10 Correct 262 ms 60136 KB Output is correct
11 Correct 196 ms 55296 KB Output is correct
12 Correct 244 ms 59324 KB Output is correct
13 Correct 225 ms 59620 KB Output is correct
14 Correct 563 ms 63300 KB Output is correct
15 Correct 485 ms 62976 KB Output is correct
16 Correct 464 ms 63392 KB Output is correct
17 Correct 486 ms 63348 KB Output is correct
18 Correct 462 ms 63452 KB Output is correct