Buggy python submission (verdict: Time Limit Exceeded):
import sys

read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7
M = 998244353


def main():
    N, K = map(int, readline().split())
    LR = list(list(map(int, readline().split())) for _ in range(K))
    LR.sort()
    dp = [0] *(N+1)
    dp[1] = 1
    for i in range(2, N + 1):
        for l,r in LR:
            if i-l>0:
                dp[i] += sum(dp[max(1,i-r):min(N,i-l+1)]) % M
                dp[i] %= M
            else:
                break
    print(dp[N])


if __name__ == '__main__':
    main()


Fixed submission:
import sys

read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7
M = 998244353


class SegTree:
    def __init__(self, init_val, segfunc, ide_ele):
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, k, x):
        k += self.num
        self.tree[k] = x
        while k > 1:
            self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1

    def query(self, l, r):
        res = self.ide_ele
        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res


def segfunc(x, y):
    return x + y


def main():
    N, K = map(int, readline().split())
    LR = list(list(map(int, readline().split())) for _ in range(K))
    LR.sort()

    A = [0] * (N + 1)
    A[1] = 1
    seg = SegTree(A, segfunc=segfunc, ide_ele=0)
    for i in range(2, N + 1):
        for l, r in LR:
            if i - l > 0:
                total = (seg.tree[i + seg.num] + seg.query(max(1, i - r), min(N, i - l + 1)) % M)
                seg.update(i, total)
            else:
                break
    print(seg.tree[seg.num + N] % M)


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys

read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7
M = 998244353


def main():
    N, K = map(int, readline().split())
    LR = list(list(map(int, readline().split())) for _ in range(K))
    LR.sort()
    S = []
    for l,r in LR:
        S += list(range(l,r+1))
    dp = [0] *(N+1)
    dp[1] = 1
    for i in range(1, N + 1):
        for s in S:
            if i - s > 0:
                dp[i] += dp[i - s]
                dp[i] %= M
            else:
                break
    print(dp[N])


if __name__ == '__main__':
    main()


Fixed submission:
import sys

read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7
M = 998244353


class SegTree:
    def __init__(self, init_val, segfunc, ide_ele):
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, k, x):
        k += self.num
        self.tree[k] = x
        while k > 1:
            self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1

    def query(self, l, r):
        res = self.ide_ele
        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res


def segfunc(x, y):
    return x + y


def main():
    N, K = map(int, readline().split())
    LR = list(list(map(int, readline().split())) for _ in range(K))
    LR.sort()

    A = [0] * (N + 1)
    A[1] = 1
    seg = SegTree(A, segfunc=segfunc, ide_ele=0)
    for i in range(2, N + 1):
        for l, r in LR:
            if i - l > 0:
                total = (seg.tree[i + seg.num] + seg.query(max(1, i - r), min(N, i - l + 1)) % M)
                seg.update(i, total)
            else:
                break
    print(seg.tree[seg.num + N] % M)


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys

read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7
M = 998244353


def main():
    N, K = map(int, readline().split())
    LR = list(list(map(int, readline().split())) for _ in range(K))
    LR.sort()
    dp = [0] *(N+1)
    dp[1] = 1
    for i in range(1, N + 1):
        for l,r in LR:
            for s in range(l,r+1):
                if i - s > 0:
                    dp[i] += dp[i - s]
                    dp[i] %= M
                else:
                    break
    print(dp[N])


if __name__ == '__main__':
    main()


Fixed submission:
import sys

read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7
M = 998244353


class SegTree:
    def __init__(self, init_val, segfunc, ide_ele):
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, k, x):
        k += self.num
        self.tree[k] = x
        while k > 1:
            self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1

    def query(self, l, r):
        res = self.ide_ele
        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res


def segfunc(x, y):
    return x + y


def main():
    N, K = map(int, readline().split())
    LR = list(list(map(int, readline().split())) for _ in range(K))
    LR.sort()

    A = [0] * (N + 1)
    A[1] = 1
    seg = SegTree(A, segfunc=segfunc, ide_ele=0)
    for i in range(2, N + 1):
        for l, r in LR:
            if i - l > 0:
                total = (seg.tree[i + seg.num] + seg.query(max(1, i - r), min(N, i - l + 1)) % M)
                seg.update(i, total)
            else:
                break
    print(seg.tree[seg.num + N] % M)


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys

read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7
M = 998244353


def main():
    N, K = map(int, readline().split())
    S = set()
    for k in range(K):
        L, R = map(int, readline().split())
        S |= set(range(L, R + 1))

    dp = [0] * (N + 1)
    dp[1] = 1
    S = list(S)
    S.sort()

    for i in range(1, N + 1):
        for s in S:
            if i - s > 0:
                dp[i] += dp[i - s]
                dp[i] %= M
            else:
                break
    print(dp[N])


if __name__ == '__main__':
    main()


Fixed submission:
import sys

read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7
M = 998244353


class SegTree:
    def __init__(self, init_val, segfunc, ide_ele):
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, k, x):
        k += self.num
        self.tree[k] = x
        while k > 1:
            self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1

    def query(self, l, r):
        res = self.ide_ele
        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res


def segfunc(x, y):
    return x + y


def main():
    N, K = map(int, readline().split())
    LR = list(list(map(int, readline().split())) for _ in range(K))
    LR.sort()

    A = [0] * (N + 1)
    A[1] = 1
    seg = SegTree(A, segfunc=segfunc, ide_ele=0)
    for i in range(2, N + 1):
        for l, r in LR:
            if i - l > 0:
                total = (seg.tree[i + seg.num] + seg.query(max(1, i - r), min(N, i - l + 1)) % M)
                seg.update(i, total)
            else:
                break
    print(seg.tree[seg.num + N] % M)


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys

read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7
M = 998244353


def main():
    N, K = map(int, readline().split())
    S = set()
    for k in range(K):
        L, R = map(int, readline().split())
        S |= set(range(L, R + 1))

    dp = [0] * (N + 1)
    dp[1] = 1
    S = list(S)

    for i in range(1, N + 1):
        for s in S:
            if i - s > 0:
                dp[i] += dp[i - s]
                dp[i] %= M
            else:
                continue
    print(dp[N])


if __name__ == '__main__':
    main()


Fixed submission:
import sys

read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7
M = 998244353


class SegTree:
    def __init__(self, init_val, segfunc, ide_ele):
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, k, x):
        k += self.num
        self.tree[k] = x
        while k > 1:
            self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1

    def query(self, l, r):
        res = self.ide_ele
        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res


def segfunc(x, y):
    return x + y


def main():
    N, K = map(int, readline().split())
    LR = list(list(map(int, readline().split())) for _ in range(K))
    LR.sort()

    A = [0] * (N + 1)
    A[1] = 1
    seg = SegTree(A, segfunc=segfunc, ide_ele=0)
    for i in range(2, N + 1):
        for l, r in LR:
            if i - l > 0:
                total = (seg.tree[i + seg.num] + seg.query(max(1, i - r), min(N, i - l + 1)) % M)
                seg.update(i, total)
            else:
                break
    print(seg.tree[seg.num + N] % M)


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys

read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
# MOD = 10 ** 9 + 7
MOD = 998244353


def main():
    N, K = map(int, readline().split())
    S = set()
    for k in range(K):
        L, R = map(int, readline().split())
        S |= set(range(L, R + 1))

    dp = [0] * (N + 20)
    dp[1] = 1
    S = list(S)
    S.sort()

    for i in range(1, N + 5):
        for s in S:
            if i - s > 0:
                dp[i] += dp[i - s]
                dp[i] %= MOD
            else:
                continue
    print(dp[N])


if __name__ == '__main__':
    main()


Fixed submission:
import sys

read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7
M = 998244353


class SegTree:
    def __init__(self, init_val, segfunc, ide_ele):
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, k, x):
        k += self.num
        self.tree[k] = x
        while k > 1:
            self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1

    def query(self, l, r):
        res = self.ide_ele
        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res


def segfunc(x, y):
    return x + y


def main():
    N, K = map(int, readline().split())
    LR = list(list(map(int, readline().split())) for _ in range(K))
    LR.sort()

    A = [0] * (N + 1)
    A[1] = 1
    seg = SegTree(A, segfunc=segfunc, ide_ele=0)
    for i in range(2, N + 1):
        for l, r in LR:
            if i - l > 0:
                total = (seg.tree[i + seg.num] + seg.query(max(1, i - r), min(N, i - l + 1)) % M)
                seg.update(i, total)
            else:
                break
    print(seg.tree[seg.num + N] % M)


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys

read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
# MOD = 10 ** 9 + 7
MOD = 998244353


def main():
    N, K = map(int, readline().split())
    S = set()
    for k in range(K):
        L, R = map(int, readline().split())
        S |= set(range(L, R + 1))

    dp = [0] * (N + 20)
    dp[1] = 1
    S = list(S)

    for i in range(1, N + 5):
        for s in S:
            if i - s > 0:
                dp[i] += dp[i - s] % MOD
                dp[i] %= MOD
    print(dp[N])


if __name__ == '__main__':
    main()


Fixed submission:
import sys

read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7
M = 998244353


class SegTree:
    def __init__(self, init_val, segfunc, ide_ele):
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, k, x):
        k += self.num
        self.tree[k] = x
        while k > 1:
            self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1

    def query(self, l, r):
        res = self.ide_ele
        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res


def segfunc(x, y):
    return x + y


def main():
    N, K = map(int, readline().split())
    LR = list(list(map(int, readline().split())) for _ in range(K))
    LR.sort()

    A = [0] * (N + 1)
    A[1] = 1
    seg = SegTree(A, segfunc=segfunc, ide_ele=0)
    for i in range(2, N + 1):
        for l, r in LR:
            if i - l > 0:
                total = (seg.tree[i + seg.num] + seg.query(max(1, i - r), min(N, i - l + 1)) % M)
                seg.update(i, total)
            else:
                break
    print(seg.tree[seg.num + N] % M)


if __name__ == '__main__':
    main()