Problem:


Score : 500 points

Problem Statement

You have a string S of length N.
Initially, all characters in S are 1s.

You will perform queries Q times.
In the i-th query, you are given two integers L_i, R_i and a character D_i (which is a digit).
Then, you must replace all characters from the L_i-th to the R_i-th (inclusive) with D_i.

After each query, read the string S as a decimal integer, and print its value modulo 998,244,353.

Constraints

1 \leq N, Q \leq 200,000

1 \leq L_i \leq R_i \leq N

1 \leq D_i \leq 9

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N Q
L_1 R_1 D_1
:
L_Q R_Q D_Q

Output

Print Q lines.
In the i-th line print the value of S after the i-th query, modulo 998,244,353.

Sample Input 1

8 5
3 6 2
1 4 7
3 8 3
2 2 2
4 5 1

Sample Output 1

11222211
77772211
77333333
72333333
72311333

Sample Input 2

200000 1
123 456 7

Sample Output 2

641437905

Don't forget to take the modulo.



Sample input:
8 5
3 6 2
1 4 7
3 8 3
2 2 2
4 5 1


Sample output:
11222211
77772211
77333333
72333333
72311333

Submission status: Time Limit Exceeded

Solution code:
import typing

def _ceil_pow2(n: int) -> int:
    x = 0
    while (1 << x) < n:
        x += 1

    return x


def _bsf(n: int) -> int:
    x = 0
    while n % 2 == 0:
        x += 1
        n //= 2

    return x

class LazySegTree:
    def __init__(
            self,
            op: typing.Callable[[typing.Any, typing.Any], typing.Any],
            e: typing.Any,
            mapping: typing.Callable[[typing.Any, typing.Any], typing.Any],
            composition: typing.Callable[[typing.Any, typing.Any], typing.Any],
            id_: typing.Any,
            v: typing.Union[int, typing.List[typing.Any]]) -> None:
        self._op = op
        self._e = e
        self._mapping = mapping
        self._composition = composition
        self._id = id_

        if isinstance(v, int):
            v = [e] * v

        self._n = len(v)
        self._log = _ceil_pow2(self._n)
        self._size = 1 << self._log
        self._d = [e] * (2 * self._size)
        self._lz = [self._id] * self._size
        for i in range(self._n):
            self._d[self._size + i] = v[i]
        for i in range(self._size - 1, 0, -1):
            self._update(i)

    def set(self, p: int, x: typing.Any) -> None:
        assert 0 <= p < self._n

        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 get(self, p: int) -> typing.Any:
        assert 0 <= p < self._n

        p += self._size
        for i in range(self._log, 0, -1):
            self._push(p >> i)
        return self._d[p]

    def prod(self, left: int, right: int) -> typing.Any:
        assert 0 <= left <= right <= self._n

        if left == right:
            return self._e

        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._e
        smr = self._e
        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 all_prod(self) -> typing.Any:
        return self._d[1]

    def apply(self, left: int, right: typing.Optional[int] = None,
              f: typing.Optional[typing.Any] = None):
        assert f is not None

        if right is None:
            p = left
            assert 0 <= left < self._n

            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:
            assert 0 <= left <= right <= self._n
            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 max_right(
            self, left: int, g: typing.Callable[[typing.Any], bool]) -> int:
        assert 0 <= left <= self._n
        assert g(self._e)

        if left == self._n:
            return self._n

        left += self._size
        for i in range(self._log, 0, -1):
            self._push(left >> i)

        sm = self._e
        first = True
        while first or (left & -left) != left:
            first = False
            while left % 2 == 0:
                left >>= 1
            if not g(self._op(sm, self._d[left])):
                while left < self._size:
                    self._push(left)
                    left *= 2
                    if g(self._op(sm, self._d[left])):
                        sm = self._op(sm, self._d[left])
                        left += 1
                return left - self._size
            sm = self._op(sm, self._d[left])
            left += 1

        return self._n

    def min_left(self, right: int, g: typing.Any) -> int:
        assert 0 <= right <= self._n
        assert g(self._e)

        if right == 0:
            return 0

        right += self._size
        for i in range(self._log, 0, -1):
            self._push((right - 1) >> i)

        sm = self._e
        first = True
        while first or (right & -right) != right:
            first = False
            right -= 1
            while right > 1 and right % 2:
                right >>= 1
            if not g(self._op(self._d[right], sm)):
                while right < self._size:
                    self._push(right)
                    right = 2 * right + 1
                    if g(self._op(self._d[right], sm)):
                        sm = self._op(self._d[right], sm)
                        right -= 1
                return right + 1 - self._size
            sm = self._op(self._d[right], sm)

        return 0

    def _update(self, k: int) -> None:
        self._d[k] = self._op(self._d[2 * k], self._d[2 * k + 1])

    def _all_apply(self, k: int, f: typing.Any) -> 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: int) -> None:
        self._all_apply(2 * k, self._lz[k])
        self._all_apply(2 * k + 1, self._lz[k])
        self._lz[k] = self._id


D = [1,10]
E = [1,11]
mod = 998244353

def op(a : (int, int),b : (int, int)) -> (int, int):
    return (b[0]+a[0]*D[b[1]])%mod, a[1]+b[1]

e = (0,0)

def mapping(f,a :(int,int)) -> (int, int):
    if f is None:
        return a[0],a[1]
    if a[0]==0:
        return 0,0
    return (f*E[a[1]-1])%mod, a[1]

def composition(f,g):
    if f is None:
        return g
    else:
        return f

id = None

import sys

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

def main():
    N,Q = list(map(int,input().split()))
    a = 10
    for i in range(N+1):
        a*=10
        a%=mod
        D.append(a)
        E.append((E[-1]+a)%mod)

    lst = LazySegTree(op, e, mapping, composition, id, [(1,1) for i in range(N)])

    for i in range(Q):
        l,r,d = list(map(int,input().split()))
        l,r = l-1,r-1
        lst.apply(l,r+1,d)
        print(lst.all_prod()[0])


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n, q = (int(x) for x in input().split())

lrd = []
for i in range(q):
  lrd.append([int(x) for x in input().split()])

s = ""
for a in range(n):
  s = s + "1"

for j in lrd:
  s2 = s[:j[0]-1]
  s3 = s[j[1]:]

  for i in range(j[1]-j[0]+1):
    s2 = s2 + str(j[2])
  
  s = s2 + s3

  print(int(s) % 998244353)

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split(" "))
A=[1 for i in range(n)]

for i in range(m):
  a,b,x=map(int,input().split(" "))
  c=1
  g=0
  for j in range(a-1,b):
    A[j]=x
  for j in range(n):
    g=A[j]+g*10
  print(g%998244353)

Submission status: Time Limit Exceeded

Solution code:
N, Q = list(map(int, input().split()))

S = [1] * N
for i in range(Q):
    l, r, d = list(map(int, input().split()))
    for i in range(l, r + 1):
        S[i - 1] = d

    print(int("".join(list(map(str, S)))) % 998244353)

Submission status: Time Limit Exceeded

Solution code:

def to_int(target, MOD):
    result = target[0]
    for i in range(1, len(target)):
        result *= 10
        result += target[i]
        result %= MOD

    return result


def main():
    N, Q = [int(x) for x in input().split()]
    MOD = 998244353
    S = [1] * N

    for _ in range(Q):
        new_len = []
        l, r, d = [int(x) for x in input().split()]
        l -= 1
        r -= 1

        for i in range(N):
            if l <= i <= r:
                new_len.append(d)
            else:
                new_len.append(S[i])

        print(to_int(new_len, MOD))
        S = new_len


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**6)
INF = 10 ** 9 + 1  # sys.maxsize # float("inf")
MOD = 998244353


def set_depth(depth):
    global DEPTH, SEGTREE_SIZE, NONLEAF_SIZE
    DEPTH = depth
    SEGTREE_SIZE = 1 << DEPTH
    NONLEAF_SIZE = 1 << (DEPTH - 1)


def set_width(width):
    set_depth((width - 1).bit_length() + 1)


def get_size(pos):
    ret = pos.bit_length()
    return (1 << (DEPTH - ret))


def up(pos):
    pos += SEGTREE_SIZE // 2
    return pos // (pos & -pos)


def up_propagate(table, pos, binop):
    while pos > 1:
        pos >>= 1
        size = get_size(pos) // 2
        table[pos] = binop(
            table[pos * 2],
            table[pos * 2 + 1],
            size
        )


def full_up(table, binop):
    for pos in range(NONLEAF_SIZE - 1, 0, -1):
        size = get_size(pos) // 2
        table[pos] = binop(
            table[2 * pos],
            table[2 * pos + 1],
            size)


def force_down_propagate(
    action_table, value_table, pos,
    action_composite, action_force, action_unity
):
    max_level = pos.bit_length() - 1
    size = NONLEAF_SIZE
    for level in range(max_level):
        size //= 2
        i = pos >> (max_level - level)
        action = action_table[i]
        if action != action_unity:
            action_table[i * 2] = action_composite(
                action, action_table[i * 2])
            action_table[i * 2 + 1] = action_composite(
                action, action_table[i * 2 + 1])
            # old_action = action_table[i * 2]
            # if old_action == action_unity:
            #     action_table[i * 2] = action
            # else:
            #     b1, c1 = old_action
            #     b2, c2 = action
            #     action_table[i * 2] = (b1 * b2, b2 * c1 + c2)

            # old_action = action_table[i * 2 + 1]
            # if old_action == action_unity:
            #     action_table[i * 2 + 1] = action
            # else:
            #     b1, c1 = old_action
            #     b2, c2 = action
            #     action_table[i * 2 + 1] = (b1 * b2, b2 * c1 + c2)

            action_table[i] = action_unity

            value_table[i * 2] = action_force(
                action, value_table[i * 2], size)
            value_table[i * 2 + 1] = action_force(
                action, value_table[i * 2 + 1], size)
            # b, c = action
            # value = value_table[i * 2]
            # value_table[i * 2] = (value * b + c * size) % MOD
            # value = value_table[i * 2 + 1]
            # value_table[i * 2 + 1] = (value * b + c * size) % MOD


def force_range_update(
    value_table, action_table, left, right,
    action, action_force, action_composite, action_unity
):
    """
    action_force: action, value, cell_size => new_value
    action_composite: new_action, old_action => composite_action
    """
    left += NONLEAF_SIZE
    right += NONLEAF_SIZE
    while left < right:
        if left & 1:
            value_table[left] = action_force(
                action, value_table[left], get_size(left))
            action_table[left] = action_composite(action, action_table[left])
            left += 1
        if right & 1:
            right -= 1
            value_table[right] = action_force(
                action, value_table[right], get_size(right))
            action_table[right] = action_composite(action, action_table[right])

        left //= 2
        right //= 2


def range_reduce(table, left, right, binop, unity):
    ret_left = unity
    ret_right = unity
    left += NONLEAF_SIZE
    right += NONLEAF_SIZE
    right_size = 0
    while left < right:
        if left & 1:
            size = get_size(left)
            ret_left = binop(ret_left, table[left], size)
            # debug("size, ret_left", size, ret_left)
            left += 1
        if right & 1:
            right -= 1
            ret_right = binop(table[right], ret_right, right_size)
            right_size += get_size(right)
            # debug("right_size, ret_right", right_size, ret_right)
        left //= 2
        right //= 2
    return binop(ret_left, ret_right, right_size)


def lazy_range_update(
        action_table, value_table, start, end,
        action, action_composite, action_force, action_unity, value_binop):
    "update [start, end)"
    L = up(start)
    R = up(end)
    force_down_propagate(
        action_table, value_table, L,
        action_composite, action_force, action_unity)
    force_down_propagate(
        action_table, value_table, R,
        action_composite, action_force, action_unity)

    force_range_update(
        value_table, action_table, start, end,
        action, action_force, action_composite, action_unity)
    up_propagate(value_table, L, value_binop)
    up_propagate(value_table, R, value_binop)


def lazy_range_reduce(
    action_table, value_table, start, end,
    action_composite, action_force, action_unity,
    value_binop, value_unity
):
    "reduce [start, end)"
    force_down_propagate(
        action_table, value_table, up(start),
        action_composite, action_force,  action_unity)
    force_down_propagate(
        action_table, value_table, up(end),
        action_composite, action_force, action_unity)

    return range_reduce(value_table, start, end, value_binop, value_unity)


def debug(*x):
    print(*x, file=sys.stderr)


def main():
    # parse input
    N, Q = map(int, input().split())
    set_width(N + 1)

    value_unity = 0
    value_table = [value_unity] * SEGTREE_SIZE
    value_table[NONLEAF_SIZE:NONLEAF_SIZE + N] = [1] * N

    action_unity = None
    action_table = [action_unity] * SEGTREE_SIZE

    cache = {}
    i = 1
    p = 1
    step = 10
    while i <= N:
        cache[i] = p
        p = (p * step + p) % MOD
        step = (step * step) % MOD
        i *= 2

    def action_force(action, value, size):
        if action == action_unity:
            return value
        # return int(str(action) * size)
        return (cache[size] * action) % MOD

    def action_composite(new_action, old_action):
        if new_action == action_unity:
            return old_action
        return new_action

    def value_binop(a, b, size):
        # debug("a, b, size", a, b, size)
        return (a * (10 ** size) + b) % MOD
    full_up(value_table, value_binop)

    ret = lazy_range_reduce(
        action_table, value_table, 0, N, action_composite, action_force, action_unity,
        value_binop, value_unity)

    for _q in range(Q):
        l, r, d = map(int, input().split())
        lazy_range_update(
            action_table, value_table, l - 1, r, d,
            action_composite, action_force, action_unity, value_binop)

        ret = lazy_range_reduce(
            action_table, value_table, 0, N, action_composite, action_force, action_unity,
            value_binop, value_unity)
        print(ret)


# tests
T1 = """
8 5
3 6 2
1 4 7
3 8 3
2 2 2
4 5 1
"""
TEST_T1 = """
>>> as_input(T1)
>>> main()
11222211
77772211
77333333
72333333
72311333
"""

T2 = """
200000 1
123 456 7
"""
TEST_T2 = """
>>> as_input(T2)
>>> main()
641437905
"""

T3 = """
4 4
1 1 2
1 2 3
1 3 4
1 4 5
"""
TEST_T3 = """
>>> as_input(T3)
>>> main()
2111
3311
4441
5555
"""

T4 = """
4 4
4 4 2
3 4 3
2 4 4
1 4 5
1112
1133
1444
5555
"""
TEST_T4 = """
>>> as_input(T4)
>>> main()
1112
1133
1444
5555
"""

T5 = """
9 3
1 9 1
1 9 5
1 9 9
"""
TEST_T5 = """
>>> as_input(T5)
>>> main()
111111111
555555555
1755646
"""


def _test():
    import doctest
    doctest.testmod()
    g = globals()
    for k in sorted(g):
        if k.startswith("TEST_"):
            doctest.run_docstring_examples(g[k], g, name=k)


def as_input(s):
    "use in test, use given string as input file"
    import io
    f = io.StringIO(s.strip())
    g = globals()
    g["input"] = lambda: bytes(f.readline(), "ascii")
    g["read"] = lambda: bytes(f.read(), "ascii")


input = sys.stdin.buffer.readline
read = sys.stdin.buffer.read

if sys.argv[-1] == "-t":
    print("testing")
    _test()
    sys.exit()

main()

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int, input().split())

S = '1'*N
for i in range(Q):
    L, R, D = map(int, input().split())
    S = S[:L-1] + str(D)*(R-L+1) + S[R:]
    print(int(S)%998244353)

Submission status: Time Limit Exceeded

Solution code:
n, q = map(int, input().split())
l = []
r = []
d = []
for i in range(q):
    inp = list(map(int,input().split()))
    l.append(inp[0])
    r.append(inp[1])
    d.append(inp[2])

#文字列作成
text = []
for i in range(n):
    text.append(1)

for i in range(q):
    cnt = l[i] - 1
    while 1:
        text[cnt] = d[i]
        cnt += 1
        if cnt == r[i]:
            break
    ans=0
    for j in range(n):
        ans += int(text[j])*10**(n-j-1)
        ans = ans%998244353
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,Q=map(int,input().split())
MOD=998244353
s=0
P=[]
X=[0]*N
for i in range(N):
  s+=pow(10,i,MOD)
  P.append(pow(10,i,MOD))
for q in range(Q):
  l,r,d=map(int,input().split())
  for i in range(l,r+1):
    X[i-1]=((d-1)*P[N-i])%MOD
  print((s+sum(X)%MOD)%MOD)

Submission status: Time Limit Exceeded

Solution code:
import typing

def _ceil_pow2(n: int) -> int:
    x = 0
    while (1 << x) < n:
        x += 1

    return x


def _bsf(n: int) -> int:
    x = 0
    while n % 2 == 0:
        x += 1
        n //= 2

    return x

class LazySegTree:
    def __init__(
            self,
            op: typing.Callable[[typing.Any, typing.Any], typing.Any],
            e: typing.Any,
            mapping: typing.Callable[[typing.Any, typing.Any], typing.Any],
            composition: typing.Callable[[typing.Any, typing.Any], typing.Any],
            id_: typing.Any,
            v: typing.Union[int, typing.List[typing.Any]]) -> None:
        self._op = op
        self._e = e
        self._mapping = mapping
        self._composition = composition
        self._id = id_

        if isinstance(v, int):
            v = [e] * v

        self._n = len(v)
        self._log = _ceil_pow2(self._n)
        self._size = 1 << self._log
        self._d = [e] * (2 * self._size)
        self._lz = [self._id] * self._size
        for i in range(self._n):
            self._d[self._size + i] = v[i]
        for i in range(self._size - 1, 0, -1):
            self._update(i)

    def set(self, p: int, x: typing.Any) -> None:
        assert 0 <= p < self._n

        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 get(self, p: int) -> typing.Any:
        assert 0 <= p < self._n

        p += self._size
        for i in range(self._log, 0, -1):
            self._push(p >> i)
        return self._d[p]

    def prod(self, left: int, right: int) -> typing.Any:
        assert 0 <= left <= right <= self._n

        if left == right:
            return self._e

        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._e
        smr = self._e
        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 all_prod(self) -> typing.Any:
        return self._d[1]

    def apply(self, left: int, right: typing.Optional[int] = None,
              f: typing.Optional[typing.Any] = None):
        assert f is not None

        if right is None:
            p = left
            assert 0 <= left < self._n

            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:
            assert 0 <= left <= right <= self._n
            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 max_right(
            self, left: int, g: typing.Callable[[typing.Any], bool]) -> int:
        assert 0 <= left <= self._n
        assert g(self._e)

        if left == self._n:
            return self._n

        left += self._size
        for i in range(self._log, 0, -1):
            self._push(left >> i)

        sm = self._e
        first = True
        while first or (left & -left) != left:
            first = False
            while left % 2 == 0:
                left >>= 1
            if not g(self._op(sm, self._d[left])):
                while left < self._size:
                    self._push(left)
                    left *= 2
                    if g(self._op(sm, self._d[left])):
                        sm = self._op(sm, self._d[left])
                        left += 1
                return left - self._size
            sm = self._op(sm, self._d[left])
            left += 1

        return self._n

    def min_left(self, right: int, g: typing.Any) -> int:
        assert 0 <= right <= self._n
        assert g(self._e)

        if right == 0:
            return 0

        right += self._size
        for i in range(self._log, 0, -1):
            self._push((right - 1) >> i)

        sm = self._e
        first = True
        while first or (right & -right) != right:
            first = False
            right -= 1
            while right > 1 and right % 2:
                right >>= 1
            if not g(self._op(self._d[right], sm)):
                while right < self._size:
                    self._push(right)
                    right = 2 * right + 1
                    if g(self._op(self._d[right], sm)):
                        sm = self._op(self._d[right], sm)
                        right -= 1
                return right + 1 - self._size
            sm = self._op(self._d[right], sm)

        return 0

    def _update(self, k: int) -> None:
        self._d[k] = self._op(self._d[2 * k], self._d[2 * k + 1])

    def _all_apply(self, k: int, f: typing.Any) -> 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: int) -> None:
        self._all_apply(2 * k, self._lz[k])
        self._all_apply(2 * k + 1, self._lz[k])
        self._lz[k] = self._id


D = [1,10]
E = [1,11]
mod = 998244353

def op(a,b):
    return (b[0]+a[0]*D[b[1]])%mod, a[1]+b[1]

e = (0,0)

def mapping(f,a):
    if f is None:
        return a[0],a[1]
    if a[0]==0:
        return 0,0
    return (f*E[a[1]-1])%mod, a[1]

def composition(f,g):
    if f is None:
        return g
    else:
        return f

id = None
import sys

sys.setrecursionlimit(500000)
def input():
    return sys.stdin.readline()[:-1]

def main():
    N,Q = list(map(int,input().split()))
    a = 10
    for i in range(N+1):
        a*=10
        a%=mod
        D.append(a)
        E.append((E[-1]+a)%mod)

    lst = LazySegTree(op, e, mapping, composition, id, [(1,1) for i in range(N)])

    for i in range(Q):
        l,r,d = list(map(int,input().split()))
        l,r = l-1,r-1
        lst.apply(l,r+1,d)
        print(lst.all_prod()[0])


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
n, q = map(int, input().split())
# d = defaultdict(int)
# d[1] = n

# t = [[0, n-1, 1]]
t = ['1'] * n

mod = 998244353

for i in range(q):
    l, r, d = map(int, input().split())
    t = t[:l-1] + [str(d)] * (r - l + 1) + t[r:]
    print(int(''.join(t)) % mod)

Submission status: Time Limit Exceeded

Solution code:
def LI():
    return list(map(int, input().split()))


mod = 998244353

N, Q = LI()
S = "1"*N
ans = int(S) % mod
for _ in range(Q):
    L, R, D = LI()
    D = str(D)
    ans = (ans-int(S[L-1:R])*pow(10, N-R, mod)) % mod
    d = D*(R-L+1)
    S = S[:L-1]+d+S[R:N]
    d = int(d)
    ans = (ans+d*pow(10, N-R, mod)) % mod
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, Q = [int(i) for i in input().split()]
S = '1' * N
LRD = [[0] for _ in range(Q)]
for i in range(Q):
	LRD[i] = [int(i) for i in input().split()]

for i in range(Q):
	L = int(LRD[i][0]) - 1
	R = int(LRD[i][1]) - 1
	len = R - L + 1
	S = S[0:L] + str(LRD[i][2]) * len + S[R + 1:N]
	print(int(S) % 998244353)

Submission status: Time Limit Exceeded

Solution code:
n, q = (int(x) for x in input().split())

lrd = []
for i in range(q):
  lrd.append([int(x) for x in input().split()])

s = 0
for a in range(n):
  s += 10**a

s = str(s)

for j in lrd:
  s2 = s[:j[0]-1]
  s3 = s[j[1]:]

  for i in range(j[1]-j[0]+1):
    s2 = s2 + str(j[2])
  
  s = s2 + s3

  print(int(s) % 998244353)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = lambda: sys.stdin.readline()


def solve():
    def init(init_arr):
        global num, segfunc, ide_ele, seg
        segfunc = lambda x, y: y
        ide_ele = 0
        num = 2 ** (n - 1).bit_length()
        seg = [ide_ele] * 2 * num
        for i in range(n):
            seg[i + num - 1] = init_arr[i]
        for i in range(num - 2, -1, -1):
            seg[i] = segfunc(seg[2 * i + 1], seg[2 * i + 2])

    def update(k, x):
        k += num - 1
        seg[k] = x
        while k:
            k = (k - 1) // 2
            seg[k] = segfunc(seg[k * 2 + 1], seg[k * 2 + 2])

    def query(p, q):
        if q <= p:
            return ide_ele
        p += num - 1
        q += num - 2
        res = ide_ele
        while q - p > 1:
            if p & 1 == 0:
                res = segfunc(res, seg[p])
            if q & 1 == 1:
                res = segfunc(res, seg[q])
                q -= 1
            p = p // 2
            q = (q - 1) // 2
        if p == q:
            res = segfunc(res, seg[p])
        else:
            res = segfunc(segfunc(res, seg[p]), seg[q])
        return res

    n, q = map(int, input().split())
    a = [1] * n

    init(a)

    for _ in range(q):
        l, r, rep = map(int, input().split())
        for i in range(l - 1, r):
            update(i, rep)
        ans = ""
        for i in range(n):
            tmp = str(query(i, i + 1))
            ans = ans + tmp
        print(int(ans) % 998244353)
solve()