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 sys
def input(): return sys.stdin.readline().rstrip()

# SegmentTree
class SegmentTree:

  def __init__(self, n, p, unit, f, g, h):
    num = 2**((n-1).bit_length())
    seg = [unit]*(num*2)
    self.lazy = [None]*(num*2)
    for i in range(n):
      seg[num+i] = p[i]
    for i in range(num-1, 0, -1):
      seg[i] = f(seg[i << 1], seg[(i << 1)+1])
    self.num = num
    self.seg = seg
    self.unit = unit
    self.flag = False
    self.f = f
    self.g = g
    self.h = h

  def gindex(self, l, r):
    l += self.num
    r += self.num
    lm = (l//(l & -l)) >> 1
    rm = (r//(r & -r)) >> 1
    mm = max(lm, rm)
    r -= 1
    while l < r:
      if r <= rm:
        yield r
      if l <= lm:
        yield l
      l >>= 1
      r >>= 1
    while l:
      if l <= mm:
        yield l
      l >>= 1

  def propagates(self, ids):
    num = self.num
    g = self.g
    h = self.h
    for i in reversed(ids):
      v = self.lazy[i]
      if v is None:
        continue
      # ここ！！！！！！！！！！！！！
      # ここ！！！！！！！！！！！！！

      newv = v

      # ここ！！！！！！！！！！！！！
      # ここ！！！！！！！！！！！！！
      if (i << 1) < num:
        self.lazy[i << 1] = h(self.lazy[i << 1], newv)
        self.lazy[(i << 1)+1] = h(self.lazy[(i << 1)+1], newv)
      self.seg[i << 1] = g(self.seg[i << 1], newv,i<<1)
      self.seg[(i << 1)+1] = g(self.seg[(i << 1)+1], newv,(i<<1)+1)
      self.lazy[i] = None

  def query(self, l, r):
    f = self.f
    if self.flag:
      *ids, = self.gindex(l, r)
      self.propagates(ids)
    ansl = ansr = self.unit
    l += self.num
    r += self.num-1
    if l == r:
      return self.seg[l]
    while l < r:
      if l & 1:
        ansl = f(ansl, self.seg[l])
        l += 1
      if r & 1 == 0:
        ansr = f(self.seg[r], ansr)
        r -= 1
      l >>= 1
      r >>= 1
    if l == r:
      ansl = f(ansl, self.seg[l])
    return f(ansl, ansr)

  def update1(self, i, x):
    i += self.num
    f = self.f
    self.seg[i] = x
    while i:
      i >>= 1
      self.seg[i] = f(self.seg[i << 1], self.seg[(i << 1)+1])

  def update2(self, l, r, x):
    self.flag = True
    *ids, = self.gindex(l, r)
    self.propagates(ids)
    num = self.num
    f = self.f
    g = self.g
    h = self.h
    l += num
    r += num-1
    if l == r:
      self.seg[l] = g(self.seg[l], x,l)
      for i in ids:
        self.seg[i] = f(self.seg[i << 1], self.seg[(i << 1)+1])
      return
    while l < r:
      if l & 1:
        if l < num:
          self.lazy[l] = h(self.lazy[l], x)
        self.seg[l] = g(self.seg[l], x,l)
        l += 1
      if r & 1 == 0:
        if r < num:
          self.lazy[r] = h(self.lazy[r], x)
        self.seg[r] = g(self.seg[r], x,r)
        r -= 1
      l >>= 1
      r >>= 1
    if l == r:
      self.lazy[l] = h(self.lazy[l], x)
      self.seg[l] = g(self.seg[l], x,l)
    for i in ids:
      self.seg[i] = f(self.seg[i << 1], self.seg[(i << 1)+1])
  
  def update(self, i, x):
    if type(i) is int:
      self.update1(i, x)
    else:
      self.update2(i[0], i[1], x)

mod=998244353
n,q=map(int,input().split())
num=2**((n-1).bit_length())
d=[1]
for i in range(n-1):
  d.append(d[-1]*10%mod)
d=d[::-1]
d+=[0]*len(d)
e=[0]+d[:]
m=len(e)
for i in range(m-1):
  e[i+1]=(e[i]+e[i+1])%mod
def f(a,b):
  return a+b
def g(x,y,i):
  if y==None:return x
  b=1<<(i.bit_length()-1)
  i-=b
  l=(num//b)*i
  r=l+num//b
  return (e[r]-e[l])*y%mod
def h(x,y):
  if y==None:return x
  return y

seg=SegmentTree(n,d,0,f,g,h)
for _ in range(q):
  l,r,d=map(int,input().split())
  seg.update2(l-1,r,d)
  print(seg.query(0,n)%mod)

Submission status: Time Limit Exceeded

Solution code:
class LazySegmentTree:  # from https://atcoder.jp/contests/practice2/submissions/16598122
    __slots__ = ["n", "data", "lazy", "me", "oe", "fmm", "fmo", "foo"]

    def __init__(self, monoid_data, monoid_identity, operator_identity, func_monoid_monoid, func_monoid_operator,
                 func_operator_operator):
        self.me = monoid_identity
        self.oe = operator_identity
        self.fmm = func_monoid_monoid
        self.fmo = func_monoid_operator
        self.foo = func_operator_operator

        self.n = len(monoid_data)
        self.data = monoid_data*2
        for i in range(self.n-1, 0, -1):
            self.data[i] = self.fmm(self.data[2*i], self.data[2*i+1])
        self.lazy = [self.oe]*(self.n*2)

    def replace(self, index, value):
        index += self.n

        # propagation
        for shift in range(index.bit_length()-1, 0, -1):
            i = index>>shift
            self.lazy[2*i] = self.foo(self.lazy[2*i], self.lazy[i])
            self.lazy[2*i+1] = self.foo(self.lazy[2*i+1], self.lazy[i])
            self.data[i] = self.fmo(self.data[i], self.lazy[i])
            self.lazy[i] = self.oe

        # update
        self.data[index] = value
        self.lazy[index] = self.oe

        # recalculation
        i = index
        while i > 1:
            i //= 2
            self.data[i] = self.fmm(self.fmo(self.data[2*i], self.lazy[2*i]),
                                    self.fmo(self.data[2*i+1], self.lazy[2*i+1]))
            self.lazy[i] = self.oe

    def effect(self, l, r, operator):
        l += self.n
        r += self.n

        # preparing indices
        indices = []
        l0 = (l//(l&-l))//2
        r0 = (r//(r&-r)-1)//2
        while r0 > l0:
            indices.append(r0)
            r0 //= 2
        while l0 > r0:
            indices.append(l0)
            l0 //= 2
        while l0 and l0 != r0:
            indices.append(r0)
            r0 //= 2
            if l0 == r0:
                break
            indices.append(l0)
            l0 //= 2
        while r0:
            indices.append(r0)
            r0 //= 2

        # propagation
        for i in reversed(indices):
            self.lazy[2*i] = self.foo(self.lazy[2*i], self.lazy[i])
            self.lazy[2*i+1] = self.foo(self.lazy[2*i+1], self.lazy[i])
            self.data[i] = self.fmo(self.data[i], self.lazy[i])
            self.lazy[i] = self.oe

        # effect
        while l < r:
            if l%2:
                self.lazy[l] = self.foo(self.lazy[l], operator)
                l += 1
            if r%2:
                r -= 1
                self.lazy[r] = self.foo(self.lazy[r], operator)
            l //= 2
            r //= 2

        # recalculation
        for i in indices:
            self.data[i] = self.fmm(self.fmo(self.data[2*i], self.lazy[2*i]),
                                    self.fmo(self.data[2*i+1], self.lazy[2*i+1]))
            self.lazy[i] = self.oe

    def folded(self, l, r):
        l += self.n
        r += self.n

        # preparing indices
        indices = []
        l0 = (l//(l&-l))//2
        r0 = (r//(r&-r)-1)//2
        while r0 > l0:
            indices.append(r0)
            r0 //= 2
        while l0 > r0:
            indices.append(l0)
            l0 //= 2
        while l0 and l0 != r0:
            indices.append(r0)
            r0 //= 2
            if l0 == r0:
                break
            indices.append(l0)
            l0 //= 2
        while r0:
            indices.append(r0)
            r0 //= 2

        # propagation
        for i in reversed(indices):
            self.lazy[2*i] = self.foo(self.lazy[2*i], self.lazy[i])
            self.lazy[2*i+1] = self.foo(self.lazy[2*i+1], self.lazy[i])
            self.data[i] = self.fmo(self.data[i], self.lazy[i])
            self.lazy[i] = self.oe

        # fold
        left_folded = self.me
        right_folded = self.me
        while l < r:
            if l%2:
                left_folded = self.fmm(left_folded, self.fmo(self.data[l], self.lazy[l]))
                l += 1
            if r%2:
                r -= 1
                right_folded = self.fmm(self.fmo(self.data[r], self.lazy[r]), right_folded)
            l //= 2
            r //= 2
        return self.fmm(left_folded, right_folded)

import sys

mod = 998244353
p = 1
n = 0
p10 = []
n11 = []
for i in range(202020):
    p10.append(p)
    n11.append(n)
    p = p * 10 % mod
    n = (n * 10 + 1) % mod

def op(a, b):
    a_val, a_siz = a
    b_val, b_siz = b
    siz = a_siz + b_siz
    val = a_val * p10[b_siz] + b_val
    return val % mod, siz

e = (0, 0)

def mapping(a, f):
    if f == 0:
        return a
    siz = a[1]
    return f * n11[siz] % mod, siz

aaa = lambda g, f: f if f != 0 else g

i = 0

N, Q = map(int, sys.stdin.buffer.readline().split())

#seg = LazySegTree(op, e, mapping, aaa, i, [(1, 1) for _ in range(N)])
seg = LazySegmentTree([(1, 1) for _ in range(N)], e, i, op, mapping, aaa)

LRD = [list(map(int, input().split())) for _ in range(Q)]
Ans = []
for l, r, d in LRD:
    #seg.apply(l-1, r, d)
    seg.effect(l-1, r, d)
    #ans = seg.all_prod()[0]
    ans = seg.folded(0, N)[0]
    Ans.append(ans)
print("\n".join(map(str, Ans)))

Submission status: Time Limit Exceeded

Solution code:
def main():
    n, q = map(int, input().split())
    # s = [1 for _ in range(n)]
    s = "1" * n
    # query = [list(map(int, input().split()))]
    mod = 998244353

    for _ in range(q):
        left, right, d = map(int, input().split())
        left, right = left - 1, right - 1
        s = s[:left] + str(d) * (right - left + 1) + s[right + 1:]
        print(int(s) % mod)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python
# -*- coding: UTF-8 -*-

import sys


def get_ints():
    return map(int, sys.stdin.readline().strip().split())


def main():
    n, q = get_ints()
    s = "1" * n
    mod = 998244353

    lrd = [(0, 0, "")] * q
    for i in range(q):
        ll, rr, dd = map(int, input().split())
        lrd[i] = (ll-1, rr, str(dd))

    for i in range(q):
        l = lrd[i][0]
        r = lrd[i][1]
        d = lrd[i][2]

        s = s[0: l] + d * (r-l) + s[r:]
        print(int(s) % mod)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def ReplaceDigits():
    import copy
    n, q = map(int, input().split())
    mod = 998244353
    num = '1'*n
    for _ in range(q):
        a, b, c = map(int, input().split())
        num0 = copy.deepcopy(num)
        num = ''
        if a-1 != 0:
            num = num0[:a-1]
        num += str(c)*(b-a+1)
        if -n+b != 0:
            num += num0[-n+b:]
        print(int(num)%mod)
    
if __name__ == '__main__':
    ReplaceDigits()

Submission status: Time Limit Exceeded

Solution code:
import sys
 
sys.setrecursionlimit(10**6)
int1 = lambda x: int(x)-1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

n, q = MI()
s = "1" * n
for i in range(q):
    l, r, d = MI()
    if l < 2:
        if r > n - 1:
            s = str(d) * n
        else:
            s = str(d) * (r - l + 1) + s[r:]
    else:
        if r > n - 1:
            s = s[:l-1] + str(d) * (r - l + 1)
        else:
            s = s[:l-1] + str(d) * (r - l + 1) + s[r:]
    a = int(s) % 998244353
    print(a)

Submission status: Time Limit Exceeded

Solution code:
class LazySegmentTree:  # from https://atcoder.jp/contests/practice2/submissions/16598122
    __slots__ = ["n", "data", "lazy", "me", "oe", "fmm", "fmo", "foo"]

    def __init__(self, monoid_data, monoid_identity, operator_identity, func_monoid_monoid, func_monoid_operator,
                 func_operator_operator):
        self.me = monoid_identity
        self.oe = operator_identity
        self.fmm = func_monoid_monoid
        self.fmo = func_monoid_operator
        self.foo = func_operator_operator

        self.n = len(monoid_data)
        self.data = monoid_data*2
        for i in range(self.n-1, 0, -1):
            self.data[i] = self.fmm(self.data[2*i], self.data[2*i+1])
        self.lazy = [self.oe]*(self.n*2)

    def replace(self, index, value):
        index += self.n

        # propagation
        for shift in range(index.bit_length()-1, 0, -1):
            i = index>>shift
            self.lazy[2*i] = self.foo(self.lazy[2*i], self.lazy[i])
            self.lazy[2*i+1] = self.foo(self.lazy[2*i+1], self.lazy[i])
            self.data[i] = self.fmo(self.data[i], self.lazy[i])
            self.lazy[i] = self.oe

        # update
        self.data[index] = value
        self.lazy[index] = self.oe

        # recalculation
        i = index
        while i > 1:
            i //= 2
            self.data[i] = self.fmm(self.fmo(self.data[2*i], self.lazy[2*i]),
                                    self.fmo(self.data[2*i+1], self.lazy[2*i+1]))
            self.lazy[i] = self.oe

    def effect(self, l, r, operator):
        l += self.n
        r += self.n

        # preparing indices
        indices = []
        l0 = (l//(l&-l))//2
        r0 = (r//(r&-r)-1)//2
        while r0 > l0:
            indices.append(r0)
            r0 //= 2
        while l0 > r0:
            indices.append(l0)
            l0 //= 2
        while l0 and l0 != r0:
            indices.append(r0)
            r0 //= 2
            if l0 == r0:
                break
            indices.append(l0)
            l0 //= 2
        while r0:
            indices.append(r0)
            r0 //= 2

        # propagation
        for i in reversed(indices):
            self.lazy[2*i] = self.foo(self.lazy[2*i], self.lazy[i])
            self.lazy[2*i+1] = self.foo(self.lazy[2*i+1], self.lazy[i])
            self.data[i] = self.fmo(self.data[i], self.lazy[i])
            self.lazy[i] = self.oe

        # effect
        while l < r:
            if l%2:
                self.lazy[l] = self.foo(self.lazy[l], operator)
                l += 1
            if r%2:
                r -= 1
                self.lazy[r] = self.foo(self.lazy[r], operator)
            l //= 2
            r //= 2

        # recalculation
        for i in indices:
            self.data[i] = self.fmm(self.fmo(self.data[2*i], self.lazy[2*i]),
                                    self.fmo(self.data[2*i+1], self.lazy[2*i+1]))
            self.lazy[i] = self.oe

    def folded(self, l, r):
        l += self.n
        r += self.n

        # preparing indices
        indices = []
        l0 = (l//(l&-l))//2
        r0 = (r//(r&-r)-1)//2
        while r0 > l0:
            indices.append(r0)
            r0 //= 2
        while l0 > r0:
            indices.append(l0)
            l0 //= 2
        while l0 and l0 != r0:
            indices.append(r0)
            r0 //= 2
            if l0 == r0:
                break
            indices.append(l0)
            l0 //= 2
        while r0:
            indices.append(r0)
            r0 //= 2

        # propagation
        for i in reversed(indices):
            self.lazy[2*i] = self.foo(self.lazy[2*i], self.lazy[i])
            self.lazy[2*i+1] = self.foo(self.lazy[2*i+1], self.lazy[i])
            self.data[i] = self.fmo(self.data[i], self.lazy[i])
            self.lazy[i] = self.oe

        # fold
        left_folded = self.me
        right_folded = self.me
        while l < r:
            if l%2:
                left_folded = self.fmm(left_folded, self.fmo(self.data[l], self.lazy[l]))
                l += 1
            if r%2:
                r -= 1
                right_folded = self.fmm(self.fmo(self.data[r], self.lazy[r]), right_folded)
            l //= 2
            r //= 2
        return self.fmm(left_folded, right_folded)

import sys

mod = 998244353
p = 1
n = 0
p10 = []
n11 = []
for i in range(202020):
    p10.append(p)
    n11.append(n)
    p = p * 10 % mod
    n = (n * 10 + 1) % mod

def op(a, b):
    a_val, a_siz = a
    b_val, b_siz = b
    siz = a_siz + b_siz
    val = a_val * p10[b_siz] + b_val
    return val % mod, siz

e = (0, 0)

def mapping(a, f):
    if f == 0:
        return a
    siz = a[1]
    return f * n11[siz] % mod, siz

aaa = lambda g, f: f if f != 0 else g

i = 0

N, Q = map(int, sys.stdin.buffer.readline().split())

#seg = LazySegTree(op, e, mapping, aaa, i, [(1, 1) for _ in range(N)])
seg = LazySegmentTree([(1, 1) for _ in range(N)], e, i, op, mapping, aaa)


m = map(int, sys.stdin.buffer.read().split())
Ans = []
for l, r, d in zip(m, m, m):
    #seg.apply(l-1, r, d)
    seg.effect(l-1, r, d)
    #ans = seg.all_prod()[0]
    ans = seg.folded(0, N)[0]
    Ans.append(ans)
print("\n".join(map(str, Ans)))

Submission status: Time Limit Exceeded

Solution code:
n,q = map(int,input().split());
a = ['1']*n

for i in range(q):
    l,r,d = map(int,input().split());
    lr = r-l+1
    a[l-1:r] = str(d)*lr
    print(int("".join(a)) % 998244353)

Submission status: Time Limit Exceeded

Solution code:
n, q = map(int, input().split())
mod = 998244353
s = ['1'] * n

# print(s)

for i in range(q):
    l, r, d = map(int, input().split())
    # print("".join(s[l:r]))
    L = "".join(s[:l - 1])
    R = "".join(s[r:])
    C = str(d) * (r - l + 1)
    mix = L + C + R
    # print(mix)
    print(int(mix) % mod)

    s = [c for c in mix.strip()]
    # print(s)

Submission status: Time Limit Exceeded

Solution code:
[N, Q] = [int(i) for i in input().split()]
I = ['1'] * N
for i in range(Q):
    [L, R, D] = [str(i) for i in input().split()]
    for j in range(int(L)-1, int(R)):
        I[j] = D
#        print(I)
    S = int(''.join(I))
    print(S % 998244353)

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:
class LazySegmentTree:  # from https://atcoder.jp/contests/practice2/submissions/16598122
    __slots__ = ["n", "data", "lazy", "me", "oe", "fmm", "fmo", "foo"]

    def __init__(self, monoid_data, monoid_identity, operator_identity, func_monoid_monoid, func_monoid_operator,
                 func_operator_operator):
        self.me = monoid_identity
        self.oe = operator_identity
        self.fmm = func_monoid_monoid
        self.fmo = func_monoid_operator
        self.foo = func_operator_operator

        self.n = len(monoid_data)
        self.data = monoid_data*2
        for i in range(self.n-1, 0, -1):
            self.data[i] = self.fmm(self.data[2*i], self.data[2*i+1])
        self.lazy = [self.oe]*(self.n*2)

    def replace(self, index, value):
        index += self.n

        # propagation
        for shift in range(index.bit_length()-1, 0, -1):
            i = index>>shift
            self.lazy[2*i] = self.foo(self.lazy[2*i], self.lazy[i])
            self.lazy[2*i+1] = self.foo(self.lazy[2*i+1], self.lazy[i])
            self.data[i] = self.fmo(self.data[i], self.lazy[i])
            self.lazy[i] = self.oe

        # update
        self.data[index] = value
        self.lazy[index] = self.oe

        # recalculation
        i = index
        while i > 1:
            i //= 2
            self.data[i] = self.fmm(self.fmo(self.data[2*i], self.lazy[2*i]),
                                    self.fmo(self.data[2*i+1], self.lazy[2*i+1]))
            self.lazy[i] = self.oe

    def effect(self, l, r, operator):
        l += self.n
        r += self.n

        # preparing indices
        indices = []
        l0 = (l//(l&-l))//2
        r0 = (r//(r&-r)-1)//2
        while r0 > l0:
            indices.append(r0)
            r0 //= 2
        while l0 > r0:
            indices.append(l0)
            l0 //= 2
        while l0 and l0 != r0:
            indices.append(r0)
            r0 //= 2
            if l0 == r0:
                break
            indices.append(l0)
            l0 //= 2
        while r0:
            indices.append(r0)
            r0 //= 2

        # propagation
        for i in reversed(indices):
            self.lazy[2*i] = self.foo(self.lazy[2*i], self.lazy[i])
            self.lazy[2*i+1] = self.foo(self.lazy[2*i+1], self.lazy[i])
            self.data[i] = self.fmo(self.data[i], self.lazy[i])
            self.lazy[i] = self.oe

        # effect
        while l < r:
            if l%2:
                self.lazy[l] = self.foo(self.lazy[l], operator)
                l += 1
            if r%2:
                r -= 1
                self.lazy[r] = self.foo(self.lazy[r], operator)
            l //= 2
            r //= 2

        # recalculation
        for i in indices:
            self.data[i] = self.fmm(self.fmo(self.data[2*i], self.lazy[2*i]),
                                    self.fmo(self.data[2*i+1], self.lazy[2*i+1]))
            self.lazy[i] = self.oe

    def folded(self, l, r):
        l += self.n
        r += self.n

        # preparing indices
        indices = []
        l0 = (l//(l&-l))//2
        r0 = (r//(r&-r)-1)//2
        while r0 > l0:
            indices.append(r0)
            r0 //= 2
        while l0 > r0:
            indices.append(l0)
            l0 //= 2
        while l0 and l0 != r0:
            indices.append(r0)
            r0 //= 2
            if l0 == r0:
                break
            indices.append(l0)
            l0 //= 2
        while r0:
            indices.append(r0)
            r0 //= 2

        # propagation
        for i in reversed(indices):
            self.lazy[2*i] = self.foo(self.lazy[2*i], self.lazy[i])
            self.lazy[2*i+1] = self.foo(self.lazy[2*i+1], self.lazy[i])
            self.data[i] = self.fmo(self.data[i], self.lazy[i])
            self.lazy[i] = self.oe

        # fold
        left_folded = self.me
        right_folded = self.me
        while l < r:
            if l%2:
                left_folded = self.fmm(left_folded, self.fmo(self.data[l], self.lazy[l]))
                l += 1
            if r%2:
                r -= 1
                right_folded = self.fmm(self.fmo(self.data[r], self.lazy[r]), right_folded)
            l //= 2
            r //= 2
        return self.fmm(left_folded, right_folded)

import sys

def main():
    mod = 998244353
    p = 1
    n = 0
    p10 = []
    n11 = []
    for i in range(202020):
        p10.append(p)
        n11.append(n)
        p = p * 10 % mod
        n = (n * 10 + 1) % mod

    def op(a, b):
        a_val, a_siz = a
        b_val, b_siz = b
        siz = a_siz + b_siz
        val = a_val * p10[b_siz] + b_val
        return val % mod, siz

    e = (0, 0)

    def mapping(a, f):
        if f == 0:
            return a
        siz = a[1]
        return f * n11[siz] % mod, siz

    aaa = lambda g, f: f if f != 0 else g

    i = 0

    N, Q = map(int, sys.stdin.buffer.readline().split())

    #seg = LazySegTree(op, e, mapping, aaa, i, [(1, 1) for _ in range(N)])
    seg = LazySegmentTree([(1, 1) for _ in range(N)], e, i, op, mapping, aaa)


    m = map(int, sys.stdin.buffer.read().split())
    Ans = []
    for l, r, d in zip(m, m, m):
        #seg.apply(l-1, r, d)
        seg.effect(l-1, r, d)
        #ans = seg.all_prod()[0]
        ans = seg.folded(0, N)[0]
        Ans.append(ans)
    print("\n".join(map(str, Ans)))


main()

Submission status: Time Limit Exceeded

Solution code:
n,q=map(int,input().split())
lrd=[list(map(int,input().split())) for i in range(q)]

MOD = 998244353
s='1'*n
tmp = ['','','']
for i in range(q):
  left = lrd[i][0]
  right = lrd[i][1]
  num = lrd[i][2]
  tmp[0] = s[:left-1]
  tmp[1] = str(num) * (right-left+1)
  tmp[2] = s[right:]
  s = ''.join(tmp)
  print(int(s)%MOD)

Submission status: Time Limit Exceeded

Solution code:
N, Q=map(int, input().split())
waru = 998244353
s="1"*N
for _ in range(Q):
  l, r, d =map(int, input().split())
  s = s[:l-1] + str(d)*(r-l+1) + s[r:]
  s = str(int(s) % waru)
  print(s)

Submission status: Time Limit Exceeded

Solution code:
n,q = map(int,input().split())
s=["1"]*n
aa=[]
for i in range(q):
    l,r,d = map(int,input().split())
    for j in range(l-1,r):
        s[j] = str(d)
    ss="".join(s)
    a = int(ss)%998244353
    aa.append(a)
for i in range(q):
    print(aa[i])

Submission status: Time Limit Exceeded

Solution code:
import sys
readline = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
#mod = 998244353
INF = 10**18
eps = 10**-7

n,q=map(int,input().split())
s='1'*n
for i in range(q):
  l,r,d=map(int,input().split())
  l-=1
  r-=1
  newd=str(d)
  news=s[0:l]+newd*(r-l+1)+s[r+1:n+1]
  print(int(news)%998244353)
  s=news

Submission status: Time Limit Exceeded

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")



### 遅延評価セグメント木
class LazySegmentTree:
    def __init__(self, n, a=None):
        """初期化
        num : n以上の最小の2のべき乗
        """
        num = 1
        while num<=n:
            num *= 2
        self.num = num
        self.seg = [ninf] * (2*self.num-1)
        self.lazy = [f0] * (2*self.num-1)
        self.ls = [0]*(2*self.num-1)
        self.rs = [0]*(2*self.num-1)
        self.ls[0] = 0
        self.rs[0] = self.num
        for i in range(self.num-1):
            self.ls[2*i+1] = self.ls[i]
            self.rs[2*i+1] = (self.ls[i] + self.rs[i])//2
            self.ls[2*i+2] = (self.ls[i] + self.rs[i])//2
            self.rs[2*i+2] = self.rs[i]
        if a is not None:
            # O(n)で初期化
            assert len(a)==n
            for i in range(n):
                self.seg[num-1+i] = a[i]
            for k in range(num-2, -1, -1):
                self.seg[k] = op(self.seg[2*k+1], self.seg[2*k+2])
    def eval(self, k):
        if self.lazy[k]==f0:
            return 
        if k<self.num-1:
            self.lazy[k*2+1] = composition(self.lazy[k], self.lazy[k*2+1])
            self.lazy[k*2+2] = composition(self.lazy[k], self.lazy[k*2+2])
        self.seg[k] = mapping(self.lazy[k], self.seg[k])
        self.lazy[k] = f0
    def eval_all(self):
        for i in range(2*self.num-1):
            self.eval(i)
    def update(self,a,b,x=None,f=None):
        """A[a]...A[b-1]をxに更新する
        """
        if f is None:
            # 更新クエリ
            f = lambda y: x
        k = 0
        q = [k] # k>=0なら行きがけ順
        # 重なる区間を深さ優先探索
        while q:
            k = q.pop()
            l,r = self.ls[k], self.rs[k]
            if k>=0:
                self.eval(k)
                if r<=a or b<=l:
                    continue
                elif a<=l and r<=b:
                    self.lazy[k] = composition(f, self.lazy[k])
                    self.eval(k)
                else:
                    q.append(~k)
                    q.append(2*k+1)
                    q.append(2*k+2)
            else:
                k = ~k
                self.seg[k] = op(self.seg[2*k+1], self.seg[2*k+2])
    def query(self,a,b):
        k = 0
        l = 0
        r = self.num
        q = [k]
        ans = ninf
        # 重なる区間を深さ優先探索
        while q:
            k = q.pop()
            l,r = self.ls[k], self.rs[k]
            self.eval(k)
            if r<=a or b<=l:
                continue
            elif a<=l and r<=b:
                ans = op(ans, self.seg[k])
            else:
                q.append(2*k+2)
                q.append(2*k+1)
#             print(q, ans, l,r,a,b, self.seg[k])
        return ans

n,q = list(map(int, input().split()))
M = 998244353
vals = [1]
vals2 = [1]
v = 1
for i in range(n):
    v *= 10
    v %= M
    vals.append(v)
    vals2.append((1+vals2[-1]*10)%M)
    
ninf = (0,0) # (転倒数, #0, #1)
op = lambda x,y: ((x[0]*vals[y[1]] + y[0])%M, x[1]+y[1])
mapping = lambda f,x: x if f is None else ((f[0]*vals2[x[1]-1])%M, x[1])
def composition(f1,f2):
    if f1 is None:
        return f2
    elif f2 is None:
        return f1
    else:
        if f1[1]<f2[1]:
            return f2
        else:
            return f1
# composition = lambda f1, f2: f1 if f2 is None else 
f0 = None
sg = LazySegmentTree(n, [(1,1)]*n)
ans = [None]*q
for i in range(q):
    l,r,d = map(int, input().split())
    l -= 1
    r -= 1
#     print(l,r,d)
    sg.update(l,r+1,f=(d,i))
    ans[i] = sg.query(0,n+1)[0]
write("\n".join(map(str, ans)))

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int, input().split())
S = ["1"] * N
As = []
for _ in range(Q):
  L, R, D = map(int, input().split())
  S[L - 1 : R] = str(D) * (R - L + 1)
  _S = ''.join(S)
  print(int(_S) % 998_244_353)

Submission status: Time Limit Exceeded

Solution code:
r=input().split()
N=int(r[0])
Q=int(r[1])
data="1"*N
d=[[int(s) for s in input().split()] for i in range(Q)]
for i in range(Q):
    data=data[0:d[i][0]-1]+str(d[i][2])*(d[i][1]-d[i][0]+1)+data[d[i][1]:N]
    print(int(data)%998244353)

Submission status: Time Limit Exceeded

Solution code:
N, Q = list(map(int, input().split()))
_mod = 998244353
S = '1'*N
nCount = ['']
nCount.append(S)
for i in range(2, 10):
    nCount.append(str(i)*N)

for i in range(Q):
    L, R, D = list(map(int, input().split()))
    S = S[:L-1] + nCount[D][:R-L+1] + S[R:]
    print(int(S)%_mod)

Submission status: Time Limit Exceeded

Solution code:
mod = 998244353

N,Q = map(int, input().split())
S = "1"*N
L = [0 for i in range(Q)]
R = [0 for i in range(Q)]
D = [0 for i in range(Q)]

for i in range(Q):
    L[i],R[i],D[i] = map(int, input().split())


for i in range(Q):
    lst = list(S)

    lst[L[i]-1:R[i]] = [str(D[i]) for j in range(R[i]-L[i]+1)]

    S = "".join(lst)

    print((int(S))%mod)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N,Q=map(int,input().split())
S=np.array(['1']*N)
mod=998244353

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

Submission status: Time Limit Exceeded

Solution code:
N,Q =map(int,input().split())
S = "1"*N
mod = 998244353
for i in range(Q):
    l,r,d = map(int,input().split())
    if l == 1:
        S = str(d)*(r-l+1)+S[r:N]
    elif r == N:
        S = S[0:l-1] + str(d)*(r-l+1)
    else:
        S = S[0:l-1] + str(d)*(r-l+1) + S[r:N]
    print(int(S)%mod)