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

class SegmentTree():
    def __init__(self, init, unitX, unitA, f, g, h):
        self.f = f # (X, X) -> X
        self.g = g # (X, A, size) -> X
        self.h = h # (A, A) -> A
        self.unitX = unitX
        self.unitA = unitA
        self.f = f
        if type(init) == int:
            self.n = init
            self.n = 1 << (self.n - 1).bit_length()
            self.X = [unitX] * (self.n * 2)
            self.size = [1] * (self.n * 2)
        else:
            self.n = len(init)
            self.n = 1 << (self.n - 1).bit_length()
            self.X = [unitX] * self.n + init + [unitX] * (self.n - len(init))
            self.size = [0] * self.n + [1] * len(init) + [0] * (self.n - len(init))
            for i in range(self.n-1, 0, -1):
                self.X[i] = self.f(self.X[i*2], self.X[i*2|1])
    
        for i in range(self.n - 1, 0, -1):
            self.size[i] = self.size[i*2] + self.size[i*2|1]
        
        self.A = [unitA] * (self.n * 2)
        
    def update(self, i, x):
        i += self.n
        self.propagate_above(i)
        self.X[i] = x
        self.A[i] = unitA
        self.calc_above(i)
    
    def calc(self, i):
        return self.g(self.X[i], self.A[i], self.size[i])
    
    def calc_above(self, i):
        i >>= 1
        while i:
            self.X[i] = self.f(self.calc(i*2), self.calc(i*2|1))
            i >>= 1
    
    def propagate(self, i):
        self.X[i] = self.g(self.X[i], self.A[i], self.size[i])
        self.A[i*2] = self.h(self.A[i*2], self.A[i])
        self.A[i*2|1] = self.h(self.A[i*2|1], self.A[i])
        self.A[i] = self.unitA
        
    def propagate_above(self, i):
        H = i.bit_length()
        for h in range(H, 0, -1):
            self.propagate(i >> h)
    
    def propagate_all(self):
        for i in range(1, self.n):
            self.propagate(i)
    
    def getrange(self, l, r):
        l += self.n
        r += self.n
        l0, r0 = l // (l & -l), r // (r & -r) - 1
        self.propagate_above(l0)
        self.propagate_above(r0)
        
        al = self.unitX
        ar = self.unitX
        while l < r:
            if l & 1:
                al = self.f(al, self.calc(l))
                l += 1
            if r & 1:
                r -= 1
                ar = self.f(self.calc(r), ar)
            l >>= 1
            r >>= 1
        return self.f(al, ar)
    
    def getvalue(self, i):
        i += self.n
        self.propagate_above(i)
        return self.calc(i)
    
    def operate_range(self, l, r, a):
        l += self.n
        r += self.n
        l0, r0 = l // (l & -l), r // (r & -r) - 1
        self.propagate_above(l0)
        self.propagate_above(r0)
        while l < r:
            if l & 1:
                self.A[l] = self.h(self.A[l], a)
                l += 1
            if r & 1:
                r -= 1
                self.A[r] = self.h(self.A[r], a)
            l >>= 1
            r >>= 1
        
        self.calc_above(l0)
        self.calc_above(r0)
    
    def check(self, randX, randA, maxs, rep):
        from random import randrange
        for _ in range(rep):
            x = randX()
            y = randX()
            z = randX()
            a = randA()
            b = randA()
            c = randA()
            s = randrange(1, maxs + 1)
            t = randrange(1, maxs + 1)
            err = 0
            if not f(x, unitX) == f(unitX, x) == x:
                err = 1
                print("!!!!! unitX Error !!!!!")
                print("unitX =", unitX)
                print("x =", x)
                print("f(x, unitX) =", f(x, unitX))
                print("f(unitX, x) =", f(unitX, x))
            
            if not h(a, unitA) == h(unitA, a) == a:
                err = 1
                print("!!!!! unitA Error !!!!!")
                print("unitA =", unitA)
                print("a =", a)
                print("f(a, unitA) =", f(a, unitA))
                print("f(unitA, a) =", f(unitA, a))
                
            if not f(f(x, y), z) == f(x, f(y, z)):
                err = 1
                print("!!!!! Associativity Error X !!!!!")
                print("x, y, z, f(x, y), f(y, x) =", x, y, z, f(x, y), f(y, x))
                print("f(f(x, y), z) =", f(f(x, y), z))
                print("f(x, f(y, z)) =", f(x, f(y, z)))
            
            if not h(h(a, b), c) == h(a, h(b, c)):
                err = 1
                print("!!!!! Associativity Error A !!!!!")
                print("a, b, c, h(a, b), h(b, c) =", a, b, c, h(a, b), h(b, c))
                print("h(h(a, b), c) =", h(h(a, b), c))
                print("h(a, h(b, c)) =", h(a, h(b, c)))
            
            if not g(x, unitA, s) == x:
                err = 1
                print("!!!!! Identity Error !!!!!")
                print("unitA, x, s =", unitA, x, s)
                print("g(x, unitA, s) =", g(x, unitA, s))
            
            if not g(g(x, a, s), b, s) == g(x, h(a, b), s):
                err = 1
                print("!!!!! Act Error 1 !!!!!")
                print("x, a, b, s, g(x, a, s), h(a, b) =", x, a, b, s, g(x, a, s), h(a, b))
                print("g(g(x, a, s), b, s) =", g(g(x, a, s), b, s))
                print("g(x, h(a, b), s)    =", g(x, h(a, b), s))
            
            if not g(f(x, y), a, s + t) == f(g(x, a, s), g(y, a, t)):
                err = 1
                print("!!!!! Act Error 2 !!!!!")
                print("x, y, a, s, t, f(x, y), g(x, a, s), g(y, a, t) =", x, y, a, s, t, f(x, y), g(x, a, s), g(y, a, t))
                print("g(f(x, y), a, s + t)      =", g(f(x, y), a, s + t))
                print("f(g(x, a, s), g(y, a, t)) =", f(g(x, a, s), g(y, a, t)))
            
            if err:
                break
                assert f(x, unitX) == f(unitX, x) == x
                assert h(a, unitA) == h(unitA, a) == a
                assert f(f(x, y), z) == f(x, f(y, z))
                assert h(h(a, b), c) == h(a, h(b, c))
                assert g(x, unitA, s) == x
                assert g(g(x, a, s), b, s) == g(x, h(a, b), s)
                assert g(f(x, y), a, s + t) == f(g(x, a, s), g(y, a, t))
        else:
            pass
            print("Monoid Check OK!")
    
    def debug1(self):
        print("self.n =", self.n)
        deX = []
        deA = []
        deS = []
        a, b = self.n, self.n * 2
        while b:
            deX.append(self.X[a:b])
            deA.append(self.A[a:b])
            deS.append(self.size[a:b])
            a, b = a//2, a
        print("--- debug ---")
        for d in deX[::-1]:
            print(d)
        print("--- ---")
        for d in deA[::-1]:
            print(d)
        print("--- ---")
        for d in deS[::-1]:
            print(d)
        print("--- ---")
    
    def debug(self, k = 10):
        print("--- debug ---")
        print("point")
        for i in range(min(self.n - 1, k)):
            print(i, self.getvalue(i))
        print("prod")
        for i in range(min(self.n, k)):
            print(i, self.getrange(0, i))
        print("--- ---")


# ↓和を使うときはこっちの方が少し高速
# from operator import add
# f = lambda a, b: (a[0] * b[0] % P, (a[1] * b[0] + b[1]) % P) # 1次関数の合成


P = 998244353
inv9 = 443664157

# f = lambda x, y: (x[0] + y[0], x[1] + y[1])
def f(x, y):
    # print("f", x, y)
    l1, su1 = x
    l2, su2 = y
    # return (l1, (su1 + su2 * pow(10, l2 - l1, P)) % P) if l2 >= l1 else (l2, (su2 + su1 * pow(10, l1 - l2, P)) % P)
    return (min(l1, l2), (su1 + su2) % P)

# g = lambda x, a, s: (s, 0) if a == "A" else (0, s) if a == "B" else (x)
def g(x, a, s):
    # print("g", x, a, s)
    l, su = x
    return (l, (pow(10, s, P) - 1) * inv9 % P * pow(10, l, P) * a % P) if a else x
    
h = lambda a, b: b if b else a

unitX = (0, 0)
unitA = 0
N, Q = map(int, input().split())
x = 1
X = []
for i in range(N):
    X.append((i, x))
    x = x * 10 % P

st = SegmentTree(X, unitX, unitA, f, g, h)

if False:
    from random import randrange
    randX = lambda: (randrange(-10, 11), randrange(-10, 11))
    randA = lambda: ["", "A", "B"][randrange(3)]
    maxs = 10
    rep = 1000
    st.check(randX, randA, maxs, rep)

for _ in range(Q):
    l, r, d = map(int, input().split())
    l, r = N - r, N - l + 1
    st.operate_range(l, r, d)
    print(st.X[1][1])

Submission status: Time Limit Exceeded

Solution code:
n, q = map(int, input().split())
lrd_list = [list(map(int, input().split())) for _ in range(q)]
mod = 998244353

s = '1' * n
for l, r, d in lrd_list:
    s = s[:l - 1] + str(d) * (r - l + 1) + s[r:]
    print(int(s) % mod)

Submission status: Time Limit Exceeded

Solution code:
n, q = map(int, input().split())
ls=['1']*(n)
N = 998244353
ans=[]
for _ in range(q):
    l,r,d= map(int, input().split())
    #ls[l-1] = d
    #ls[r] = d*(-1)
    for i in range(l-1, r):
        ls[i]=str(d)
    p = int(''.join(ls))
    ans.append(p%N)

for i in ans:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    import sys

    input = sys.stdin.readline

    n, q = [int(x) for x in input().rstrip().split(" ")]

    s = "".join(["1" for _ in range(n)])
    for i in range(q):
        l, r, d = [x for x in input().rstrip().split(" ")]
        l = int(l) - 1
        r = int(r) - 1
        new_s = s[:l] + "".join([d for _ in range(r - l + 1)]) + s[r+1:]
        print(int(new_s) % 998244353)
        s = new_s

if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:
#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())

def resolve():
    mod =  998_244_353
    N, Q = iim()

    N1 = N+1 if N&1 else N
    M = 1<<N1.bit_length()
    NM = N1+M
    A = [(-1, 1)] * NM

    def set(a, i, j, x):
        i += M; j += M
        while i < j:
            if i & 1:
                A[i] = x
                i += 1
            if not j & 1:
                A[j] = x
                j -= 1
            i >>= 1; j >>= 1
        if i == j:
            A[i] = x

    def get(a, i):
        i += M
        ans = (-2, 1)
        while i > 0:
            ans = max(ans, A[i])
            i >>= 1
        return ans

    def calc(a):
        ans = 0
        for i in range(N):
            ans = (10*ans + get(A, i)[1]) % mod
        return ans

    it = map(int, sys.stdin.read().split())

    for i, (l, r, q) in enumerate(zip(it, it, it)):
        set(A, l-1, r-1, (i, q))
        print(calc(A))


if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:
N,Q = map(int,input().split())
LRD = [list(map(int,input().split())) for q in range(Q)]
S = N*"1"

for L,R,D in LRD:
  S = S[:L-1]+(R-L+1)*str(D)+S[R:]
  print(int(S)%998244353)

Submission status: Time Limit Exceeded

Solution code:
def main():
  n,q=map(int,input().split())
  s=["1"]*n
  for i in range(q):
    l,r,d=map(int,input().split())
    l=l-1
    lr=r-l
    #print(s[l:r])
    #print([str(d)]*lr)
    s[l:r]=[str(d)]*lr
    s1=int("".join(s))%  998244353
    print(s1)
main()

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
s = "1"*n
for i in range(m):
  l,r,k = map(int,input().split())
  s =  s[:l-1]+str(k)*(r-l+1)+s[r:]
  print(int(s)%998244353)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
N,Q=map(int,input().split())
MOD=998244353
s=0
dic=[1]*(N+1)
P=[]
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):
    s+=((d-dic[i])*P[N-i])
    dic[i]=d
  print(s%MOD)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
import string
import math
import sys
sys.setrecursionlimit(10**6) 
def array_int():
    return [int(i) for i in sys.stdin.readline().split()]
def vary(number_of_variables):
    if number_of_variables==1:
        return int(sys.stdin.readline())
    if number_of_variables>=2:
        return map(int,sys.stdin.readline().split()) 
def makedict(var):
    return dict(Counter(var))
import math
mod=998244353
n,q=vary(2)
ans='1'*n
for i in range(q):
    l,r,d=vary(3)
    pt=''
    pt+=ans[:l-1]+str(d)*(r-l+1)+ans[r:]
    sys.stdout.write(str((int(pt)%mod))+'\n')
    ans=pt
# print()

Submission status: Time Limit Exceeded

Solution code:
'''
Created on 2020/09/26

@author: harurun
'''

def main():
  import sys
  pin=sys.stdin.readline
  pout=sys.stdout.write
  perr=sys.stderr.write
  
  N,Q=map(int,pin().split())
  S=["1" for i in range(N)] 
  mod=998244353
  ansl=[]
  for _ in [0]*Q:
    L,R,D=pin().split()
    for i in range(int(L),int(R)+1):
      S[i-1]=D 
    ansl.append(int("".join(S))%mod)
  ans="\n".join(map(str,ansl))
  print(ans)
  return 
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())
    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:
n,q = map(int, input().split(' '))
data = [list(map(int, input().split(' '))) for _ in range(q)]

mod = 998244353
s = '1'*n
for i in range(q):
    org = s
    l = data[i][0]-1
    r = data[i][1]
    s = org[:l]
    s += str(data[i][2]) * (r-l)
    s += org[r:]
    print(int(s)%mod)

Submission status: Time Limit Exceeded

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

x="1"*N
ans=[0 for _ in range(Q)]

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

for i in ans:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
# FileName: 	E
# CreatedDate:  2020-09-26 21:43:06 +0900
# LastModified: 2020-09-26 21:52:14 +0900
#


import os
import sys
# import numpy as np
# import pandas as pd


def main():
    N, Q = map(int, input().split())
    S = "0" + "1"*N
    amari = 998244353

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



if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
n, q = map(int, input().split())
mod = 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:]
    print(int(s) % mod)

Submission status: Time Limit Exceeded

Solution code:
import bisect, collections, copy, heapq, itertools, math, string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int, sys.stdin.readline().rstrip().split())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())
from collections import deque, defaultdict, Counter
import heapq

def main():
    N, Q = MI()
    S = '1' * N
    mod = 998244353
    for i in range(Q):
        l, r, d = MI()
        l -= 1
        r -= 1
        S = S[0:l] + str(d) * (r - l + 1) + S[r + 1:]
        print(int(S) % mod)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
N,Q=map(int,input().split())
MOD=998244353
s=0
dic=[1]*(N+1)
P=[]
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):
    s+=((d-dic[i])*P[N-i])%MOD
    dic[i]=d
  print(s%MOD)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline


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

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
class lazySegTree:
  #遅延評価セグメント木
  def __init__(s, op, e, mapping, composition, id, v):
    if type(v) is int: v = [e()] * v
    s._n = len(v)
    s.log = s.ceil_pow2(s._n)
    s.size = 1 << s.log
    s.d = [e()] * (2 * s.size)
    s.lz = [id()] * s.size
    s.e = e
    s.op = op
    s.mapping = mapping
    s.composition = composition
    s.id = id
    for i in range(s._n): s.d[s.size + i] = v[i]
    for i in range(s.size - 1, 0, -1): s.update(i)
  
  # 1点更新
  def set(s, p, x):
    p += s.size
    for i in range(s.log, 0, -1): s.push(p >> i)
    s.d[p] = x
    for i in range(1, s.log + 1): s.update(p >> i)
 
  # 1点取得
  def get(s, p):
    p += s.size
    for i in range(s.log, 0, -1): s.push(p >> i)
    return s.d[p]
 
  # 区間演算
  def prod(s, l, r):
    if l == r: return s.e()
    l += s.size
    r += s.size
    for i in range(s.log, 0, -1):
      if (((l >> i) << i) != l): s.push(l >> i)
      if (((r >> i) << i) != r): s.push(r >> i)
    sml, smr = s.e(), s.e()
    while (l < r):
      if l & 1: 
        sml = s.op(sml, s.d[l])
        l += 1
      if r & 1:
        r -= 1
        smr = s.op(s.d[r], smr)
      l >>= 1
      r >>= 1
    return s.op(sml, smr)
 
  # 全体演算
  def all_prod(s): return s.d[1]
 
  # 1点写像
  def apply(s, p, f):
    p += s.size
    for i in range(s.log, 0, -1): s.push(p >> i)
    s.d[p] = s.mapping(f, s.d[p])
    for i in range(1, s.log + 1): s.update(p >> i)
 
  # 区間写像
  def apply(s, l, r, f):
    if l == r: return
    l += s.size
    r += s.size
    for i in range(s.log, 0, -1):
      if (((l >> i) << i) != l): s.push(l >> i)
      if (((r >> i) << i) != r): s.push((r - 1) >> i)
    l2, r2 = l, r
    while l < r:
      if l & 1: 
        sml = s.all_apply(l, f)
        l += 1
      if r & 1:
        r -= 1
        smr = s.all_apply(r, f)
      l >>= 1
      r >>= 1
    l, r = l2, r2
    for i in range(1, s.log + 1):
      if (((l >> i) << i) != l): s.update(l >> i)
      if (((r >> i) << i) != r): s.update((r - 1) >> i)
   
  # L固定時の最長区間のR
  def max_right(s, l, g):
    if l == s._n: return s._n
    l += s.size
    for i in range(s.log, 0, -1): s.push(l >> i)
    sm = s.e()
    while True:
      while (l % 2 == 0): l >>= 1
      if not g(s.op(sm, s.d[l])):
        while l < s.size:
          s.push(l)
          l = 2 * l
          if g(s.op(sm, s.d[l])):
            sm = s.op(sm, s.d[l])
            l += 1
        return l - s.size
      sm = s.op(sm, s.d[l])
      l += 1
      if (l & -l) == l: break
    return s._n
 
  # R固定時の最長区間のL
  def min_left(s, r, g):
    if r == 0: return 0
    r += s.size
    for i in range(s.log, 0, -1): s.push((r - 1) >> i)
    sm = s.e()
    while True:
      r -= 1
      while r > 1 and (r % 2): r >>= 1
      if not g(s.op(s.d[r], sm)):
        while r < s.size:
          s.push(r)
          r = 2 * r + 1
          if g(s.op(s.d[r], sm)):
            sm = s.op(s.d[r], sm)
            r -= 1
        return r + 1 - s.size
      sm = s.op(s.d[r], sm)
      if (r & - r) == r: break
    return 0
 
  def update(s, k): s.d[k] = s.op(s.d[2 * k], s.d[2 * k + 1])
  def all_apply(s, k, f):
    s.d[k] = s.mapping(f, s.d[k])
    if k < s.size: s.lz[k] = s.composition(f, s.lz[k])
  def push(s, k):
    s.all_apply(2 * k, s.lz[k])
    s.all_apply(2 * k + 1, s.lz[k])
    s.lz[k] = s.id()
  def ceil_pow2(s, n):
    x = 0
    while (1 << x) < n: x += 1
    return x

# return a・e = a となる e
def e():
  return [0, 0]

# return a・b
def op(a, b):
  return [(a[0] * pow(10, b[1]) + b[0]) % MOD, a[1] + b[1]]

# return f(a)
def mapping(f, a):
  if f == 0: return a
  return [D[f][a[1]], a[1]]

# return f・g
# gを写像した後にfを写像した結果
def composition(f, g):
  if f == 0: return g
  return f

# return f(id) = id となる id
def id():
  return 0

N, Q = list(map(int, input().split()))
LRD = [list(map(int, input().split())) for _ in range(Q)]
MOD = 998244353

D = [[0]]
for i in range(1, 10):
  D.append([0])
  for j in range(N):
    D[i].append((D[i][-1] * 10 + i) % MOD)

a = [[1] * 2 for _ in range(N)]
seg = lazySegTree(op, e, mapping, composition, id, a)
for l, r, d in LRD:
  seg.apply(l - 1, r, d)
  ans = seg.all_prod()
  print(ans[0])

Submission status: Time Limit Exceeded

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

S = "1"*N

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

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3

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


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int, input().split())
S = ["1"] * N
As = []

def str_join(args):
    return ''.join(map(str, args))

for _ in range(Q):
  L, R, D = map(int, input().split())
  S[L - 1 : R] = str(D) * (R - L + 1)
  _S = str_join(S)
  print(int(_S) % 998_244_353)

Submission status: Time Limit Exceeded

Solution code:
n, q = map(int, input().split())

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

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
import string
import math
import sys
sys.setrecursionlimit(10**6) 
def array_int():
    return [int(i) for i in sys.stdin.readline().split()]
def vary(number_of_variables):
    if number_of_variables==1:
        return int(sys.stdin.readline())
    if number_of_variables>=2:
        return map(int,sys.stdin.readline().split()) 
def makedict(var):
    return dict(Counter(var))
import math
mod=998244353
n,q=vary(2)
ans='1'*n
for i in range(q):
    l,r,d=vary(3)
    pt=''
    pt+=ans[:l-1]+str(d)*(r-l+1)+ans[r:]
    print(int(pt)%mod)
    ans=pt
# print()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
# SHRI GANESHA    author: Kunal Verma#

import os,sys
from collections import defaultdict
from io import BytesIO, IOBase
mod=998244353
def t(a):
    if a>mod:
        a-=mod
    return a





def main():
    n,q=map(int,input().split())
    x='1'*n
    for j in range(q):
        a,b,c= map(int,input().split())
        x= x[:a-1] + str(c)*(b-a+1)+x[b:]
        print(int(x)%mod)

BUFSIZE = 8192
class FastIO(IOBase):
    newlines = 0
    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None
    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()
    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()
    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)
class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")
sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

x="1"*N
ans=[0 for _ in range(Q)]

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

for i in ans:
    print(i)

Submission status: Time Limit Exceeded

Solution code:


N,M=map(int,input().split())
s="1"*N
mod=998244353
for i in range(M):
    l,r,d=map(int,input().split())
    s=s[:l-1]+str(d)*(r-l+1)+s[r:]
    print(int(s)%mod)

Submission status: Time Limit Exceeded

Solution code:
mod = 998244353
eps = 10**-9


def main():
    import sys
    input = sys.stdin.buffer.readline

    def op(a, b, seg_len):
        return (a * pow(10, seg_len, mod) + b)%mod

    e = 0
    inv9 = pow(9, mod - 2, mod)

    def mapping(a, x, seg_len):
        return ((x * inv9)%mod * (pow(10, seg_len, mod) - 1))%mod

    def composition(x, y):
        return y

    id = -1

    class LazySegTree:
        # Range update query
        def __init__(self, A, op=op, e=e, mapping=mapping, composition=composition, id=id, initialize=True):
            self.N = len(A)
            self.LV = (self.N - 1).bit_length()
            self.N0 = 1 << self.LV
            self.op = op
            self.e = e
            self.mapping = mapping
            self.composition = composition
            self.id = id
            if initialize:
                self.data = [self.e] * self.N0 + A + [self.e] * (self.N0 - self.N)
                seg_len = 1
                beki = self.N0 // 2
                for i in range(self.N0 - 1, 0, -1):
                    self.data[i] = op(self.data[i * 2], self.data[i * 2 + 1], seg_len)
                    if i == beki:
                        seg_len <<= 1
                        beki >>= 1
            else:
                self.data = [self.e] * (self.N0 * 2)
            self.lazy = [id] * (self.N0 * 2)

        def _ascend(self, i, seg_len):
            for _ in range(i.bit_length() - 1):
                i >>= 1
                self.data[i] = self.op(self.data[i * 2], self.data[i * 2 + 1], seg_len)
                seg_len <<= 1

        def _descend(self, idx):
            lv = idx.bit_length()
            seg_len = 1 << self.LV
            for j in range(lv - 1, 0, -1):
                seg_len >>= 1
                i = idx >> j
                x = self.lazy[i]
                if x == self.id:
                    continue
                self.lazy[i * 2] = self.composition(self.lazy[i * 2], x)
                self.lazy[i * 2 + 1] = self.composition(self.lazy[i * 2 + 1], x)
                self.lazy[i] = self.id
                self.data[i * 2] = self.mapping(self.data[i * 2], x, seg_len)
                self.data[i * 2 + 1] = self.mapping(self.data[i * 2 + 1], x, seg_len)

        # open interval [l, r)
        def apply(self, l, r, x):
            l += self.N0 - 1
            r += self.N0 - 1
            self._descend(l // (l & -l))
            self._descend(r // (r & -r) - 1)
            l_ori = l
            r_ori = r
            seg_len = 1
            while l < r:
                if l & 1:
                    self.data[l] = self.mapping(self.data[l], x, seg_len)
                    self.lazy[l] = self.composition(self.lazy[l], x)
                    l += 1
                if r & 1:
                    r -= 1
                    self.data[r] = self.mapping(self.data[r], x, seg_len)
                    self.lazy[r] = self.composition(self.lazy[r], x)
                l >>= 1
                r >>= 1
                seg_len <<= 1
            self._ascend(l_ori // (l_ori & -l_ori), l_ori & -l_ori)
            self._ascend(r_ori // (r_ori & -r_ori) - 1, r_ori & -r_ori)

        # open interval [l, r)
        def query(self, l, r):
            l += self.N0 - 1
            r += self.N0 - 1
            self._descend(l // (l & -l))
            self._descend(r // (r & -r) - 1)
            ret_l = self.e
            ret_r = self.e
            seg_len = 1
            while l < r:
                if l & 1:
                    ret_l = self.op(ret_l, self.data[l], seg_len)
                    l += 1
                if r & 1:
                    ret_r = self.op(self.data[r - 1], ret_r, seg_len)
                    r -= 1
                l >>= 1
                r >>= 1
                seg_len <<= 1
            return self.op(ret_l, ret_r, 1)

    N, Q = map(int, input().split())
    N0 = 1 << (N - 1).bit_length()
    ST = LazySegTree([0] * (N0-N) + [1] * N)
    inv10 = pow(10, mod-2, mod)
    ans = [0] * Q
    for q in range(Q):
        l, r, d = map(int, input().split())
        ST.apply(N0 - N + l, N0 - N + r + 1, d)
        ans[q] = (ST.query(N0 - N + 1, N0+1) * inv10)%mod
    print(*ans, sep="\n")


if __name__ == '__main__':
    main()