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: Wrong Answer

Solution code:
MOD = 998244353

Ref = [[0 for _ in range(100)] for _ in range(10)]
pow_2_lv = [pow(2,lv) for lv in range(100)]
P = 4*10**5+1
pow_10_MOD = [1 for i in range(P)]
for i in range(1,P):
  pow_10_MOD[i] = (pow_10_MOD[i-1] * 10) % MOD

for i in range(1,10):
  Ref[i][0] = i
  for s in range(1,30):
    Ref[i][s] += (Ref[i][s-1] * (pow(10, pow_2_lv[s-1], MOD) + 1)) % MOD
    Ref[i][s] %= MOD
#print(Ref)  
#####segfunc#####
def segfunc(x, y):
    return [(x[0] * pow_10_MOD[y[1]] + y[0]) % MOD, x[1] + y[1]]
#################

#####ide_ele#####
ide_ele = [0,0]
#################

class LazySegmentTree:
    """
    init(init_val, ide_ele): 配列init_valで初期化 O(N)
    update(l, r, x): 区間[l, r)をxに更新 O(logN)
    query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)
    """
    def __init__(self, init_val, segfunc, ide_ele):
        """
        init_val: 配列の初期値
        segfunc: 区間にしたい操作
        ide_ele: 単位元
        num: n以上の最小の2のべき乗
        data: 値配列(1-index)
        lazy: 遅延配列(1-index)
        """
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.data = [ide_ele] * 2 * self.num
        self.lazy = [ide_ele] * 2 * self.num
        # 配列の値を葉にセット
        for i in range(n):
            self.data[self.num + i] = init_val[i]
        # 構築していく
        for i in range(self.num - 1, 0, -1):
            self.data[i] = self.segfunc(self.data[2 * i], self.data[2 * i + 1])

    def gindex(self, l, r):
            """
            伝搬する対象の区間を求める
            lm: 伝搬する必要のある最大の左閉区間
            rm: 伝搬する必要のある最大の右開区間
            """
            l += self.num
            r += self.num
            lm = l >> (l & -l).bit_length()
            rm = r >> (r & -r).bit_length()

            while r > l:
                if l <= lm:
                    yield l
                if r <= rm:
                    yield r
                r >>= 1
                l >>= 1
            while l:
                yield l
                l >>= 1

    def propagates(self, *ids):
        """
        遅延伝搬処理
        ids: 伝搬する対象の区間 
        """
        for i in reversed(ids):
            v = self.lazy[i]
            if v == ide_ele:
                continue
            lv = self.num.bit_length() - (2*i).bit_length() 
            upd = Ref[v[0]%10][lv]
            #print(v[0]%10, lv)
            self.lazy[2 * i] = [upd, pow_2_lv[lv]]
            self.lazy[2 * i + 1] = [upd, pow_2_lv[lv]]
            self.data[2 * i] = [upd, pow_2_lv[lv]]
            self.data[2 * i + 1] = [upd, pow_2_lv[lv]]
            self.lazy[i] = ide_ele

    def update(self, l, r, x):
        """
        区間[l, r)の値をxに更新
        l, r: index(0-index)
        x: update value
        """
        *ids, = self.gindex(l, r)
        #print(l, r, " ids = ", ids)
        self.propagates(*ids)
        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                lv = self.num.bit_length() - l.bit_length() 
                #print(l, lv)
                upd = Ref[x[0]][lv]
                self.lazy[l] = [upd, pow_2_lv[lv]]
                self.data[l] = [upd, pow_2_lv[lv]]
                l += 1
            if r & 1:
                lv = self.num.bit_length() - (r-1).bit_length()
                upd = Ref[x[0]][lv]
                #print(r, lv)
                self.lazy[r - 1] = [upd, pow_2_lv[lv]]
                self.data[r - 1] = [upd, pow_2_lv[lv]]
            r >>= 1
            l >>= 1
        for i in ids:
            self.data[i] = self.segfunc(self.data[2 * i], self.data[2 * i + 1])


    def query(self, l, r):
        """
        [l, r)のsegfuncしたものを得る
        l: index(0-index)
        r: index(0-index)
        """
        *ids, = self.gindex(l, r)
        self.propagates(*ids)

        res = self.ide_ele

        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(self.data[l], res)
                l += 1
            if r & 1:
                res = self.segfunc(res, self.data[r - 1])
            l >>= 1
            r >>= 1
        return res
import sys
input = sys.stdin.readline

N, Q = map(int,input().split()) #3*10**5+5, 10**5 
lst = LazySegmentTree([[1, 1] for _ in range(N)], segfunc, ide_ele)
#print(lst.data)
for i in range(Q):
  L, R, D = map(int,input().split()) # i, N-1, i**2 % 9 + 1
  L -= 1
  R -= 1
  lst.update(L, R+1, [D,1])
  print(lst.data[1][0])

Submission status: Wrong Answer

Solution code:
def numba_compile(numba_config):
    import os, sys
    if sys.argv[-1] == "ONLINE_JUDGE":
        from numba import njit
        from numba.pycc import CC
        cc = CC("my_module")
        for func, signature in numba_config:
            globals()[func.__name__] = njit(signature)(func)
            cc.export(func.__name__, signature)(func)
        cc.compile()
        exit()
    elif os.name == "posix":
        exec(f"from my_module import {','.join(func.__name__ for func, _ in numba_config)}")
        for func, _ in numba_config:
            globals()[func.__name__] = vars()[func.__name__]
    else:
        from numba import njit
        for func, signature in numba_config:
            globals()[func.__name__] = njit(signature, cache=True)(func)
        print("compiled!", file=sys.stderr)


import sys
import numpy as np


def solve(N, Q, LRD):
    mod = 998244353
    p = 1
    n = 0
    p10 = np.empty(202020, dtype=np.int64)
    n11 = np.empty(202020, dtype=np.int64)
    for i in range(202020):
        p10[i] = p
        n11[i] = n
        p = p*10%mod
        n = (n*10+1)%mod

    identity = 0
    sqrtN = 512
    n_buckets = N//sqrtN+1
    Data_val = np.ones(n_buckets*sqrtN, dtype=np.int64)
    Data_val[N:] = 0
    Bucket_val = np.full(n_buckets, n11[sqrtN], dtype=np.int64)
    Lazy = np.full(n_buckets, identity, dtype=np.int64)
    M = N % sqrtN
    Bucket_val[n_buckets-1] = n11[M]

    def eval_data(k):
        if Lazy[k] != identity:
            l, r = k*sqrtN, (k+1)*sqrtN
            for i in range(l, r):
                Data_val[i] = Lazy[k]
            Lazy[k] = identity

    def apply(s, t, f):
        for k in range(s//sqrtN, (t-1)//sqrtN+1):
            l, r = k*sqrtN, (k+1)*sqrtN
            if s <= l and r <= t:
                Bucket_val[k] = f * n11[sqrtN] % mod
                Lazy[k] = f
            else:
                eval_data(k)
                for i in range(max(l, s), min(r, t)):
                    Data_val[i] = f
                Bucket_val[k] = 0
                for i in range(l, min(r, N)):
                    Bucket_val[k] = Bucket_val[k] * 10 + Data_val[i]

    def get(i):
        k = i//sqrtN
        eval_data(k)
        return Data_val[i]

    def all_prod():
        res = 0
        for k in range(n_buckets-1):
            res = (res * p10[sqrtN] + Bucket_val[k]) % mod
        res = (res * p10[M] + Bucket_val[n_buckets-1]) % mod
        return res

    Ans = np.zeros(Q, dtype=np.int64)
    for i in range(Q):
        l, r, d = LRD[i]
        apply(l-1, r, d)
        ans = all_prod()
        Ans[i] = ans
        # print(Lazy)
        # print(Bucket_val)
        # print(Data_val)
        # print()

    return Ans


numba_compile([
    [solve, "i8[:](i8,i8,i8[:,:])"]
])


def main():
    N, Q = map(int, sys.stdin.buffer.readline().split())
    LRD = np.array(sys.stdin.buffer.read().split(), dtype=np.int64).reshape(Q, 3)
    Ans = solve(N, Q, LRD)
    print("\n".join(map(str, Ans.tolist())))


main()

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    input = sys.stdin
    N,Q = map(int,input().split())
    squr = int(N**0.5)+1
    mod = 998244353
    """
    前処理
    """
    memo = [[0]*(N) for _ in range(10)]
    for i in range(10):
        for j in range(N):
            memo[i][j] = i*pow(10,N-j-1,mod)%mod

    memo2 = [[0]*(N) for _ in range(10)]
    for i in range(10):
        for j in range(N-2,-1,-1):
            memo2[i][j] += memo2[i][j+1]+memo[i][j]
            memo2[i][j] %= mod


    array = [memo[1][i] for i in range(N)]
    #bucket[i][0] => そのバケットの合計値
    #bucket[i][1] => そのバケットでの遅延評価値
    bucket = [[0,0] for _ in range(squr)]
    for i in range(N):
        belong = i//squr
        bucket[belong][0] += array[i]
        bucket[belong][1] %= mod

    for _ in range(Q):
        l,r,d = map(int,input().split())
        l -= 1
        r -= 1
        #lの所属している区間でbucketの遅延評価値のクリアを行う。
        LBelong = l//squr
        if bucket[LBelong][1] > 0:
            for i in range(LBelong*squr,(LBelong+1)*squr):
                array[i] = memo[bucket[LBelong][1]][i]
            bucket[LBelong][1] = 0

        #rの所属している区間でbucketの遅延評価値のクリアを行う。
        RBelong = r//squr
        if bucket[RBelong][1] > 0:
            for i in range(RBelong*squr,min((RBelong+1)*squr,N)):
                array[i] = memo[bucket[RBelong][1]][i]
            bucket[RBelong][1] = 0
        
        #クエリ区間の左端の余った部分を処理。
        while l//squr != l/squr and l <= r:
            #bucket更新
            bucket[l//squr][0] -= array[l]
            if bucket[l//squr][0] < 0:
                bucket[l//squr][0] += mod
            bucket[l//squr][0] += memo[d][l]
            bucket[l//squr][0] %= mod
            
            #array更新
            array[l] = memo[d][l]
            
            l += 1
        
        #クエリ区間の右端の余った部分を処理。
        while r != (r//squr+1)*squr-1 and l <= r:
            #bucket更新
            bucket[r//squr][0] -= array[r]
            if bucket[r//squr][0] < 0:
                bucket[r//squr][0] += mod
            bucket[r//squr][0] += memo[d][r]
            bucket[r//squr][0] %= mod
            
            #array更新
            array[r] = memo[d][r]
            
            r -= 1
        
        if l < r:
            bucketLeft = l//squr
            bucketRight = r//squr
            for belong in range(bucketLeft,bucketRight+1):
                belongLeft = belong*squr
                belongRight = belong*squr+squr-1
                if bucketRight != N-1:
                    tmp = memo2[d][belongLeft] - memo2[d][belongRight+1]
                else:
                    tmp = memo2[d][belongLeft]
                if tmp < 0:
                    tmp += mod
                bucket[belong][0] = tmp
                bucket[belong][1] = d
        ans = 0
        for i in range(squr):
            ans += bucket[i][0]
            ans %= mod
        print(ans)

Submission status: Wrong Answer

Solution code:
n, q = map(int, input().split())
s = ["1" for _ in range(n)]

for i in range(q):
  l, r, d = map(int, input().split())
  for j in range(l-1, r):
    s[j] = str(d)
  a = ""
  for i in range(n):
    a+=s[i]
  ans = int(a)%98244353
  print(ans)

Submission status: Wrong Answer

Solution code:
# N: 処理する区間の長さ
class SegmentTree:
  def __init__(self,N,lis):
    self.LV = (N-1).bit_length()
    self.N0 = 2**self.LV
    self.data = [0]*(2*self.N0)
    self.lazy = [None]*(2*self.N0)
    self.lis = [0]*self.N0+lis+[0]*(self.N0-N)
    for i in range(self.N0-1,-1,-1):
      self.lis[i] = self.lis[2*i] + self.lis[2*i+1]
      


  def gindex(self, l, r):
    L = (l + self.N0) >> 1; R = (r + self.N0) >> 1
    lc = 0 if l & 1 else (L & -L).bit_length()
    rc = 0 if r & 1 else (R & -R).bit_length()
    for i in range(self.LV):
      if rc <= i:
        yield R
      if L < R and lc <= i:
        yield L
      L >>= 1; R >>= 1

  # 遅延伝搬処理
  def propagates(self, *ids):
    for i in reversed(ids):
      v = self.lazy[i-1]
      if v is None:
        continue
      self.lazy[2*i-1] = self.lazy[2*i] = self.data[2*i-1] = self.data[2*i] = v >> 1
      self.lazy[i-1] = None

  # 区間[l, r)をxに更新
  def update(self, l, r, x):
    *ids, = self.gindex(l, r)
    self.propagates(*ids)

    L = self.N0 + l; R = self.N0 + r
    v = x
    while L < R:
      if R & 1:
        R -= 1
        self.lazy[R-1] = self.data[R-1] = v
      if L & 1:
        self.lazy[L-1] = self.data[L-1] = v
        L += 1
      L >>= 1; R >>= 1; v <<= 1
    for i in ids:
      self.data[i-1] = self.data[2*i-1]*self.lis[2*i-1] + self.data[2*i]*self.lis[2*i]

  # 区間[l, r)内の合計を求める
  def query(self, l, r):
    self.propagates(*self.gindex(l, r))
    L = self.N0 + l; R = self.N0 + r

    s = 0
    while L < R:
      if R & 1:
        R -= 1
        s += self.data[R-1]*self.lis[R-1]
      if L & 1:
        s += self.data[L-1]*self.lis[L-1]
        L += 1
      L >>= 1; R >>= 1
      s %= mod
    return s

import sys
input = sys.stdin.buffer.readline

N, Q = map(int, input().split())
mod = 998244343
lis = [1]*N
for i in range(N-2,-1,-1):
  lis[i] = lis[i+1]*10%mod
st = SegmentTree(N,lis)
ans = [0]*Q
st.update(0,N,1)
for i in range(Q):
  L,R,D = map(int, input().split())
  st.update(L-1,R,D)
  ans[i] = st.query(L-1,R)
print(*ans, sep='\n')

Submission status: Wrong Answer

Solution code:
N,Q=map(int,input().split())
num='1'*N
ans=0
for _ in range(Q):
    L,R,D=map(int,input().split())
    D=str(D)
    num1=D*(R-L+1)+'0'*(N-R)
    num2=num[L:R+1]
    num=num[:L-1]+D*(R-L+1)+num[R:]

    ans=ans+(int(num1)-int(num2))%998244353
    print(ans)

Submission status: Wrong Answer

Solution code:
n,q=map(int,input().split())
s=int("1"*n)
mod=998244353
for i in range(q):
    l,r,d=map(int,input().split())
    d=str(d)
    dif=int(d*(r-l+1))*10**r-int(str(s)[l-1:r])
    ans=s%mod+dif%mod
    s+=dif
    print(ans)

Submission status: Wrong Answer

Solution code:
import types

#!/usr/bin/env python3

#import
#import math
#import numpy as np
#= int(input())
#= input()
N, Q = map(int, input().split())
LRD = [list(map(int, input().split())) for _ in range(Q)]
#= [int(input()) for _ in range(N)]
#= {i:[] for i in range(N)}

def mod(num):
    return num % (998244353)

dp = [0] * N

t = 1
for i in range(N - 1, -1, -1):
    dp[i] = t    
    t *= 10
    t %= 998244353

li = []

for l, r, d in LRD:
    l -= 1
    r -= 1
    for i in range(len(li)):
        a = li[i][0]
        b = li[i][1]

        if l <= a <= r and l <= b <= r:
            li[i][0] = r + 1
            li[i][1] = l - 1
        elif l <= a <= r:
            li[i][0] = r + 1
        elif l <= b <= r:
            li[i][1] = l - 1

    li.append([l, r, d])
    li.sort()
    ans = 0
    c = 0
    for i in range(len(li)):
        if li[i][1] >= 0:
            c = i
            break

    for i in range(N):
        t = dp[i]
        if c < len(li):
            if li[c][0] <= i <= li[c][1]:
                t *= li[c][2]

            if li[c][1] == i:
                c += 1
        
        ans += t
        ans %= 998244353

    print(ans)

Submission status: Wrong Answer

Solution code:
n , q = map(int, input().split())
string = "1"*n
strin = int("1"*n)%998244353
for i in range(q):
  l, r, d = map(int, input().split())
  string = "".join([string[:l-1], str(d)*(r-l+1), string[r:]])
  x = (int(str(d-1)*(r-l+1))* 10**(n-r))%998244353
  print((strin+x)%998244353)

Submission status: Wrong Answer

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

S = ""
mod = 998244353
  
for _ in range(N):
  S += "1"

for _ in range(Q):
  L, R, D = map(int, input().split())
  pre = S[:L-1]
  middle = S[L-1:R]
  after = S[R:]
  str_list = list(middle)
  for i in range(len(middle)):
    str_list[i] = str(D)
  middle = "".join(str_list)
  S = str((int(pre+middle+after)%mod))
  print(S)

Submission status: Wrong Answer

Solution code:
N,Q = map(int,input().split())
s = "1"*N
for _ in range(Q):
  start,stop,i = map(int,input().split())
  s = s[:start-1]+str(i)*(stop-start)+s[stop-1:]
  print(int(s)%998244343)

Submission status: Wrong Answer

Solution code:
n, q = map(int, input().split())
_string = ""
for i in range(n):
    _string = _string + "1"

for i in range(q):
    l, r, d = map(int, input().split())
    tmp = ""
    for i in range(r-l+1):
        tmp = tmp + str(d)
    _string = _string[0:l-1] + tmp + _string[r:]
    print(_string)

Submission status: Wrong Answer

Solution code:
N, Q = map(int, input().split())
N_list = [1]* N
num_list = []
temp = 0
num = 0
num_mod = 0
for i in range(Q):
    num_list.append(list(map(int, input().split())))
for j in range(Q):
    keta = 1
    for k in range(num_list[j][0]-1, num_list[j][1]):
        N_list[k] = num_list[j][2]
        print(N_list)
    num = 0
    temp = 0
    for l in range(N):
        temp = N_list[N-l-1] * keta
        num += temp
        keta *= 10
    num_mod = num % 998244353
    print(num_mod)

Submission status: Wrong Answer

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

S = ""
mod = 998244353
  
for _ in range(N):
  S += "1"

for _ in range(Q):
  L, R, D = map(int, input().split())
  pre = S[:L-1]
  middle = S[L-1:R]
  after = S[R:]
  middle = middle.replace("1", str(D))
  str_list = list(middle)
  for i in range(len(middle)):
    str_list[i] = str(D)
  middle = "".join(str_list)
  S = str((int(pre+middle+after)%mod))
  print(S)

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    def input():
        return sys.stdin.readline()[:-1]
    X=list(map(int,input().split()))
    N=X[0]
    Q=X[1]
    LRD=[list(map(int,input().split())) for _ in range(Q)]
    S=0
    ss=0
    mod=998244353
    S=(10**N-1)//9
    for x in LRD:
        L=S-S%(10**(N-x[0]+1))
        L=L%mod
        R=S%(10**(N-x[1]))
        R=R%mod
        ss=(10**(x[1]-x[0]+1)-1)//9
        D=x[2]*ss*(10**(N-x[1]))
        D=D%mod
        ss=0
        S=L+R+D
        print(S%mod)

Submission status: Wrong Answer

Solution code:
# N: 処理する区間の長さ
mod=998244353
N,q=map(int,input().split())
lrd=[list(map(int,input().split())) for _ in range(q)]

INF = float('inf')#2**31-1
LV = (N-1).bit_length()
N0 = 2**LV
data = [0]*(2*N0)
lazy = [0]*(2*N0)

# 伝搬対象の区間を求める
def gindex(l, r):
    L = (l + N0) >> 1; R = (r + N0) >> 1
    lc = 0 if l & 1 else (L & -L).bit_length()
    rc = 0 if r & 1 else (R & -R).bit_length()
    for i in range(LV):
        if rc <= i:
            yield R
        if L < R and lc <= i:
            yield L
        L >>= 1; R >>= 1

# 遅延伝搬処理
def propagates(*ids):
    for i in reversed(ids):
        v = lazy[i-1]
        if v is None:continue
        lazy[2*i-1] = data[2*i-1] = lazy[2*i] = data[2*i] = v
        lazy[i-1] = None

# 区間[l, r)をxで更新
def update(l, r, x):
    *ids, = gindex(l, r)
    propagates(*ids)
    L = N0 + l; R = N0 + r
    while L < R:
        if R & 1:
            R -= 1
            lazy[R-1] = data[R-1] = x * pow(10,N-R%N,mod)
        if L & 1:
            lazy[L-1] = data[L-1] = x * pow(10,N-L%N,mod)
            L += 1
        L >>= 1; R >>= 1
    for i in ids:
        data[i-1] = data[2*i-1] + data[2*i]

# 区間[l, r)内の最小値を求める
def query(l, r):
    propagates(*gindex(l, r))
    L = N0 + l; R = N0 + r
    s = 0
    while L < R:
        if R & 1:
            R -= 1
            s = s + data[R-1]
        if L & 1:
            s = s + data[L-1]
            L += 1
        L >>= 1; R >>= 1
    return s
s=0
ss=[]
tmp=1
for i in range(N):
  ss.append(tmp)
  s+=tmp
  s%=mod
  tmp*=10
  tmp%=mod
ss.reverse()
update(0,N,1)
#print(query(0,N))
for l,r,d in lrd:
  update(l-1,r,d)
  print(query(0,N))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
n,q = list(map(int, input().split()))
num=0
nl=[1]*n
for i in range(n):
    num+=10**i
for i in range(q):
    l,r,d=list(map(int, input().split()))
    tem=0
    for j in range(l-1,r):
        t=nl[j]
        nl[j]=d
        tem+=(d-t)*10**i
    num-=tem
    print(num)
        
ans=num%998244353
print(ans)

Submission status: Wrong Answer

Solution code:
a = None

if (a is None) or (a<12):
  print('Yes')
else:
  print('No')

Submission status: Wrong Answer

Solution code:
if __name__=="__main__":
  N,Q=map(int,input().split())
  s=['1']*N
  while Q:
    l,r,d=map(int,input().split())
    s[l-1:r-1]=[str(d)]*(r-l)
    print(int(''.join(s))%998244353)
    Q-=1

Submission status: Wrong Answer

Solution code:
#E
n,q = list(map(int, input().split()))
nl=[0]*n
for i in range(q):
    l,r,d=list(map(int, input().split()))
    for j in range(l-1,r):
        nl[j]=d
    li = map(str, nl)
    s=''.join(li)
    print(s)

num=int(s)
ans=num%998244353
print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from fractions import Fraction
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations, accumulate
from operator import add, mul, sub, itemgetter, attrgetter


import sys
# sys.setrecursionlimit(10**6)
# readline = sys.stdin.buffer.readline
readline = sys.stdin.readline

INF = 1 << 60


def read_int():
    return int(readline())


def read_int_n():
    return list(map(int, readline().split()))


def read_float():
    return float(readline())


def read_float_n():
    return list(map(float, readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def ep(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.perf_counter()
        ret = f(*args, **kwargs)
        e = time.perf_counter()

        ep(e - s, 'sec')
        return ret

    return wrap


class LazySegmentTree():
    def __init__(self, op, e, mapping, composition, im, init_array):
        self.op = op
        self.e = e
        self.mapping = mapping
        self.composition = composition
        self.im = im

        l = len(init_array)

        def ceil_pow2(n):
            x = 0
            while (1 << x) < n:
                x += 1
            return x
        self.log = ceil_pow2(l)
        self.size = 1 << self.log
        self.d = [e() for _ in range(2*self.size)]
        self.lz = [im() for _ in range(self.size)]

        for i, a in enumerate(init_array):
            self.d[i+self.size] = a

        for i in range(self.size-1, 0, -1):
            self.__update(i)

    def set(self, p, x):
        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 __getitem__(self, p):
        p += self.size
        for i in range(self.log, 0, -1):
            self.__push(p >> i)
        return self.d[p]

    def prod(self, l, r):
        if l == r:
            return self.e()

        l += self.size
        r += self.size

        for i in range(self.log, 0, -1):
            if ((l >> i) << i) != l:
                self.__push(l >> i)
            if ((r >> i) << i) != r:
                self.__push(r >> i)

        sml = self.e()
        smr = self.e()

        while l < r:
            if l & 1:
                sml = self.op(sml, self.d[l])
                l += 1
            if r & 1:
                r -= 1
                smr = self.op(self.d[r], smr)
            l >>= 1
            r >>= 1

        return self.op(sml, smr)

    def apply(self, l, r, f):
        if l == r:
            return

        l += self.size
        r += self.size

        for i in range(self.log, 0, -1):
            if ((l >> i) << i) != l:
                self.__push(l >> i)
            if ((r >> i) << i) != r:
                self.__push((r-1) >> i)

        l2, r2 = l, r
        while l < r:
            if l & 1:
                self.__all_apply(l, f)
                l += 1
            if r & 1:
                r -= 1
                self.__all_apply(r, f)
            l >>= 1
            r >>= 1
        l, r = l2, r2

        for i in range(1, self.log+1):
            if ((l >> i) << i) != l:
                self.__update(l >> i)
            if ((r >> i) << i) != r:
                self.__update((r-1) >> i)

    def __update(self, k):
        self.d[k] = self.op(self.d[2*k], self.d[2*k+1])

    def __all_apply(self, k, f):
        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):
        self.__all_apply(2*k, self.lz[k])
        self.__all_apply(2*k+1, self.lz[k])
        self.lz[k] = self.im()


M = 998244353

def e():
    # (v, b)
    return (0, 0)

def op(sl, sr):
    # print(sl, sr)
    return ((sl[0] + sr[0]) % M, (sl[1] + sr[1]) % M)

def mapping(fl, sr):
    if fl == 0:
        return sr
    return ((sr[1]*fl) % M, sr[1])

def composition(fl, fr):
    return max(fl, fr)

def im():
    return 0

@mt
def slv(N, Q, LRQ):
    A = [(pow(10, N-i-1, M), pow(10, N-i-1, M)) for i in range(N)]

    st = LazySegmentTree(op, e, mapping, composition, im, A)

    ans = []
    for l, r, d in LRQ:
        l -= 1
        st.apply(l, r, d)
        ans.append(st.prod(0, N)[0])
    return ans


def main():
    N, Q = read_int_n()
    LRQ = [read_int_n() for _ in range(Q)]
    print(*slv(N, Q, LRQ), sep='\n')


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from fractions import Fraction
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations, accumulate
from operator import add, mul, sub, itemgetter, attrgetter


import sys
# sys.setrecursionlimit(10**6)
# readline = sys.stdin.buffer.readline
readline = sys.stdin.readline

INF = 1 << 60


def read_int():
    return int(readline())


def read_int_n():
    return list(map(int, readline().split()))


def read_float():
    return float(readline())


def read_float_n():
    return list(map(float, readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def ep(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.perf_counter()
        ret = f(*args, **kwargs)
        e = time.perf_counter()

        ep(e - s, 'sec')
        return ret

    return wrap


class LazySegmentTree():
    def __init__(self, op, e, mapping, composition, im, init_array):
        self.op = op
        self.e = e
        self.mapping = mapping
        self.composition = composition
        self.im = im

        l = len(init_array)

        def ceil_pow2(n):
            x = 0
            while (1 << x) < n:
                x += 1
            return x
        self.log = ceil_pow2(l)
        self.size = 1 << self.log
        self.d = [e() for _ in range(2*self.size)]
        self.lz = [im() for _ in range(self.size)]

        for i, a in enumerate(init_array):
            self.d[i+self.size] = a

        for i in range(self.size-1, 0, -1):
            self.__update(i)

    def set(self, p, x):
        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 __getitem__(self, p):
        p += self.size
        for i in range(self.log, 0, -1):
            self.__push(p >> i)
        return self.d[p]

    def prod(self, l, r):
        if l == r:
            return self.e()

        l += self.size
        r += self.size

        for i in range(self.log, 0, -1):
            if ((l >> i) << i) != l:
                self.__push(l >> i)
            if ((r >> i) << i) != r:
                self.__push(r >> i)

        sml = self.e()
        smr = self.e()

        while l < r:
            if l & 1:
                sml = self.op(sml, self.d[l])
                l += 1
            if r & 1:
                r -= 1
                smr = self.op(self.d[r], smr)
            l >>= 1
            r >>= 1

        return self.op(sml, smr)

    def apply(self, l, r, f):
        if l == r:
            return

        l += self.size
        r += self.size

        for i in range(self.log, 0, -1):
            if ((l >> i) << i) != l:
                self.__push(l >> i)
            if ((r >> i) << i) != r:
                self.__push((r-1) >> i)

        l2, r2 = l, r
        while l < r:
            if l & 1:
                self.__all_apply(l, f)
                l += 1
            if r & 1:
                r -= 1
                self.__all_apply(r, f)
            l >>= 1
            r >>= 1
        l, r = l2, r2

        for i in range(1, self.log+1):
            if ((l >> i) << i) != l:
                self.__update(l >> i)
            if ((r >> i) << i) != r:
                self.__update((r-1) >> i)

    def __update(self, k):
        self.d[k] = self.op(self.d[2*k], self.d[2*k+1])

    def __all_apply(self, k, f):
        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):
        self.__all_apply(2*k, self.lz[k])
        self.__all_apply(2*k+1, self.lz[k])
        self.lz[k] = self.im()


M = 998244353


@mt
def slv(N, Q, LRQ):
    A = [(pow(10, N-i-1, M), pow(10, N-i-1, M)) for i in range(N)]
    # print(A)

    def e():
        # (v, b)
        return (0, 0)

    def op(sl, sr):
        # print(sl, sr)
        return ((sl[0] + sr[0]) % M, (sl[1] + sr[1]) % M)

    def mapping(fl, sr):
        if fl == 0:
            return sr
        return ((sr[1]*fl) % M, sr[1])

    def composition(fl, fr):
        return max(fl, fr)

    def im():
        return 0

    st = LazySegmentTree(op, e, mapping, composition, im, A)
    # print(st.d)

    ans = []
    for l, r, d in LRQ:
        l -= 1
        st.apply(l, r, d)
        ans.append(st.prod(0, N)[0])
        # print(st.d)
    return ans


def main():
    N, Q = read_int_n()
    LRQ = [read_int_n() for _ in range(Q)]
    print(*slv(N, Q, LRQ), sep='\n')


if __name__ == '__main__':
    main()