Problem:


Score : 800 points

Problem Statement

There are N squares arranged in a row.
The squares are numbered 1, 2, ..., N, from left to right.

Snuke is painting each square in red, green or blue.
According to his aesthetic sense, the following M conditions must all be satisfied.
The i-th condition is:

There are exactly x_i different colors among squares l_i, l_i + 1, ..., r_i.

In how many ways can the squares be painted to satisfy all the conditions?
Find the count modulo 10^9+7.

Constraints

1 ≤ N ≤ 300

1 ≤ M ≤ 300

1 ≤ l_i ≤ r_i ≤ N

1 ≤ x_i ≤ 3

Input

Input is given from Standard Input in the following format:

N M
l_1 r_1 x_1
l_2 r_2 x_2
:
l_M r_M x_M

Output

Print the number of ways to paint the squares to satisfy all the conditions, modulo 10^9+7.

Sample Input 1

3 1
1 3 3

Sample Output 1

6

The six ways are:

RGB

RBG

GRB

GBR

BRG

BGR

where R, G and B correspond to red, green and blue squares, respectively.

Sample Input 2

4 2
1 3 1
2 4 2

Sample Output 2

6

The six ways are:

RRRG

RRRB

GGGR

GGGB

BBBR

BBBG

Sample Input 3

1 3
1 1 1
1 1 2
1 1 3

Sample Output 3

0

There are zero ways.

Sample Input 4

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

Sample Output 4

108



Sample input:
3 1
1 3 3


Sample output:
6

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9 + 7
N, M = map(int, input().split())
S = [[N+1]*(N+1) for i in [0,1,2]]
T = [[0]*(N+1) for i in [0,1,2]]

C = [0]*(N+1)
for i in range(M):
    l, r, x = map(int, input().split())
    l, r = N-r+1, N-l+1
    S[x-1][r] = min(S[x-1][r], l)
    T[x-1][r] = max(T[x-1][r], l)
    C[r] = 1

S0, S1, S2 = S
T0, T1, T2 = T

ok = 1
for i in range(N+1):
    if not T2[i] < S1[i] or not T1[i] < S0[i]:
        ok = 0
        break

if not ok:
    print(0)
    exit(0)

RM = [N+1]*(N+1); GM = [N+1]*(N+1)
for i in range(N-1, -1, -1):
    RM[i] = min(RM[i+1], S1[i+1])
    GM[i] = min(GM[i+1], S0[i+1])


X = {(0, 0): 3}
R = [0]*(N+1); R[0] = 3
G = [0]*(N+1); G[0] = 3
for b in range(1, N):
    t2 = T2[b+1]; s1 = S1[b+1]; t1 = T1[b+1]; s0 = S0[b+1]

    if C[b+1]:
        Z = [0]*(N+1)
        if t1 <= b < s0:
            for z in range(t2, s1):
                Z[z] = R[z] + G[z]
        for (r, g), v in X.items():
            if not t2 <= r < s1 or not t1 <= g < s0:
                R[r] -= v
                G[g] -= v
        X = {(r, g): v for (r, g), v in X.items() if t2 <= r < s1 and t1 <= g < s0}
    else:
        Z = [R[z] + G[z] for z in range(N+1)]
    if b < GM[b]:
        rm = RM[b]
        for z, v in enumerate(Z):
            if v and z < rm:
                v %= MOD
                X[z, b] = v
                R[z] += v
                G[b] += v
print(sum(X.values()) % MOD)

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9 + 7
N, M = map(int, input().split())
S = [[N+1]*(N+1) for i in [0,1,2]]
T = [[0]*(N+1) for i in [0,1,2]]

C = [0]*(N+1)
for i in range(M):
    l, r, x = map(int, input().split())
    S[x-1][r] = min(S[x-1][r], l)
    T[x-1][r] = max(T[x-1][r], l)
    C[r] = 1

S0, S1, S2 = S
T0, T1, T2 = T

ok = 1
for i in range(N+1):
    if not T2[i] < S1[i] or not T1[i] < S0[i]:
        ok = 0
        break

if not ok:
    print(0)
    exit(0)

RM = [N+1]*(N+1); GM = [N+1]*(N+1)
for i in range(N-1, -1, -1):
    RM[i] = min(RM[i+1], S1[i+1])
    GM[i] = min(GM[i+1], S0[i+1])


X = {(0, 0): 3}
R = [0]*(N+1); R[0] = 3
G = [0]*(N+1); G[0] = 3
for b in range(1, N):
    t2 = T2[b+1]; s1 = S1[b+1]; t1 = T1[b+1]; s0 = S0[b+1]
    check = lambda r, g: t2 <= r < s1 and t1 <= g < s0

    if C[b+1]:
        Z = [0]*(N+1)
        if t1 <= b < s0:
            for z in range(t2, s1):
                Z[z] = R[z] + G[z]
        for (r, g), v in X.items():
            if not t2 <= r < s1 or not t1 <= g < s0:
                R[r] -= v
                G[g] -= v
        X = {(r, g): v for (r, g), v in X.items() if t2 <= r < s1 and t1 <= g < s0}
    else:
        Z = [R[z] + G[z] for z in range(N+1)]
    if b < GM[b]:
        rm = RM[b]
        for z, v in enumerate(Z):
            if v and z < rm:
                v %= MOD
                X[z, b] = v
                R[z] += v
                G[b] += v
print(sum(X.values()) % MOD)

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9 + 7
N, M = map(int, input().split())
S = [[N+1]*(N+1) for i in [0,1,2]]
T = [[0]*(N+1) for i in [0,1,2]]

C = [0]*(N+1)
for i in range(M):
    l, r, x = map(int, input().split())
    S[x-1][r] = min(S[x-1][r], l)
    T[x-1][r] = max(T[x-1][r], l)
    C[r] = 1

S0, S1, S2 = S
T0, T1, T2 = T

ok = 1
for i in range(N+1):
    if not T2[i] < S1[i] or not T1[i] < S0[i]:
        ok = 0
        break

if not ok:
    print(0)
    exit(0)


X = {(0, 0): 3}
R = [0]*(N+1); R[0] = 3
G = [0]*(N+1); G[0] = 3
for b in range(1, N):
    t2 = T2[b+1]; s1 = S1[b+1]; t1 = T1[b+1]; s0 = S0[b+1]
    check = lambda r, g: t2 <= r < s1 and t1 <= g < s0

    if C[b+1]:
        Z = [0]*(N+1)
        if t1 <= b < s0:
            for z in range(t2, s1):
                Z[z] = R[z] + G[z]
        for (r, g), v in X.items():
            if not t2 <= r < s1 or not t1 <= g < s0:
                R[r] -= v
                G[g] -= v
        X = {(r, g): v for (r, g), v in X.items() if t2 <= r < s1 and t1 <= g < s0}
    else:
        Z = [R[z] + G[z] for z in range(N+1)]
    for z, v in enumerate(Z):
        if v:
            v %= MOD
            X[z, b] = v
            R[z] += v
            G[b] += v
print(sum(X.values()) % MOD)

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9 + 7
N, M = map(int, input().split())
S = [[N]*(N+1) for i in [0,1,2]]
T = [[0]*(N+1) for i in [0,1,2]]

C = [0]*(N+1)
for i in range(M):
    l, r, x = map(int, input().split())
    S[x-1][r] = min(S[x-1][r], l)
    T[x-1][r] = max(T[x-1][r], l)
    C[r] = 1

S0, S1, S2 = S
T0, T1, T2 = T

ok = 1
for i in range(N+1):
    if not T2[i] < S1[i] or not T1[i] < S0[i]:
        ok = 0
        break

if not ok:
    print(0)
    exit(0)


X = {(0, 0): 3}
for b in range(1, N):
    t2 = T2[b+1]; s1 = S1[b+1]; t1 = T1[b+1]; s0 = S0[b+1]
    check = lambda r, g: t2 <= r < s1 and t1 <= g < s0

    Z = [0]*(N+1)
    if C[b+1]:
        if t1 <= b < s0:
            for (r, g), v in X.items():
                if t2 <= g < s1:
                    # r <- b+1
                    Z[g] += v
                if t2 <= r < s1:
                    # g <- b+1
                    Z[r] += v
        X = {(r, g): v for (r, g), v in X.items() if t2 <= r < s1 and t1 <= g < s0}
    else:
        Z = [0]*(N+1)
        for (r, g), v in X.items():
            # r <- b+1
            Z[g] += v
            # g <- b+1
            Z[r] += v;
    for z, v in enumerate(Z):
        if v:
            X[z, b] = v % MOD
print(sum(X.values()) % MOD)

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9 + 7
N, M = map(int, input().split())
S = [[N]*(N+1) for i in [0,1,2]]
T = [[0]*(N+1) for i in [0,1,2]]
for i in range(M):
    l, r, x = map(int, input().split())
    S[x-1][r] = min(S[x-1][r], l)
    T[x-1][r] = max(T[x-1][r], l)

S0, S1, S2 = S
T0, T1, T2 = T

ok = 1
for i in range(N+1):
    if not T2[i] < S1[i] or not T1[i] < S0[i]:
        ok = 0
        break

if not ok:
    print(0)
    exit(0)


X = {(0, 0): 1}
for b in range(N):
    t2 = T2[b+1]; s1 = S1[b+1]; t1 = T1[b+1]; s0 = S0[b+1]
    check = lambda r, g: t2 <= r < s1 and t1 <= g < s0

    Y = {}
    for (r, g), v in X.items():
        v %= MOD
        if check(g, b):
            # r <- b+1
            Y[g, b] = Y.get((g, b), 0) + v
        if check(r, b):
            # g <- b+1
            Y[r, b] = Y.get((r, b), 0) + v
        if check(r, g):
            # b <- b+1
            Y[r, g] = Y.get((r, g), 0) + v
    X = Y
print(sum(X.values()) % MOD)

Submission status: Time Limit Exceeded

Solution code:
# seishin.py
from collections import deque
N, M = map(int, input().split())
r_min = [0]*(N+1); r_max = [N+1]*(N+1)
g_min = [0]*(N+1); g_max = [N+1]*(N+1)
free = [1]*(N+1)
C = [[] for i in range(N+1)]
for i in range(M):
    l, r, x = map(int, input().split())

    # 仮定: R < G < B を元に各r,gの値の範囲を絞り込む(B = rになるため計算しない)
    if x == 1:
        # x = 1の時、あるrに紐づく全てのl_iについて G < l_i を満たす必要がある
        # => G < min(l_i) を満たせばよい
        g_max[r] = min(g_max[r], l-1)
    elif x == 2:
        # x = 2の時、あるrに紐づく全てのl_iについて R < l_i, l_i <= G を満たす必要がある
        # => R < min(l_i), max(l_i) <= G を満たせばよい
        g_min[r] = max(g_min[r], l)
        r_max[r] = min(r_max[r], l-1)
    elif x == 3:
        # x = 3の時、あるrに紐づく全てのl_iについて l_i <= R を満たす必要がある
        # =>  max(l_i) <= R を満たせばよい
        r_min[r] = max(r_min[r], l)

        # r-1の時に満たすべき条件
        g_min[r-1] = max(g_min[r-1], l)

    for j in range(l, r+1):
        free[j] = 0
# rより小さいインデックスで制約が満たすべき条件を伝播して高速化
for r in range(N-1, -1, -1):
    r_max[r] = min(r_max[r], r_max[r+1])
    g_max[r] = min(g_max[r], g_max[r+1])

def check(k, r, g, b):
    return (r_min[k] <= r <= r_max[k] and g_min[k] <= g <= g_max[k])

MOD = 10**9 + 7

# 左からk個置いた時、各色の最右の位置を持ってメモ化dfs
# r < g < b を維持して計算していく
memo = {}
def dfs(k, r, g, b):
    key = r, g, b
    if key in memo:
        return memo[key]
    if not check(k, r, g, b):
        # 制約を満たさない場合 => 0通り
        memo[key] = 0
        return 0
    if k == N:
        memo[key] = 1
        return 1
    if free[k]:
        # N = 300, M = 0の場合等だと制約が少なすぎて定数が落ちない
        # => 制約が疎である場合は、制約がかかってない部分で切って高速化
        res = memo[key] = (3 * dfs(k+1, k, k, k+1)) % MOD
    else:
        # r < g < b < k+1 なので、この関係を元に次のdfs()を計算
        res = memo[key] = (dfs(k+1, g, b, k+1) + dfs(k+1, r, b, k+1) + dfs(k+1, r, g, k+1)) % MOD
    return res
print(dfs(0, 0, 0, 0))

Submission status: Time Limit Exceeded

Solution code:
# seishin.py
from collections import deque
N, M = map(int, input().split())
r_min = [0]*(N+1); r_max = [N+1]*(N+1)
g_min = [0]*(N+1); g_max = [N+1]*(N+1)
free = [1]*(N+1)
C = [[] for i in range(N+1)]
for i in range(M):
    l, r, x = map(int, input().split())

    # 仮定: R < G < B を元に各r,gの値の範囲を絞り込む(B = rになるため計算しない)
    if x == 1:
        # x = 1の時、あるrに紐づく全てのl_iについて G < l_i を満たす必要がある
        # => G < min(l_i) を満たせばよい
        g_max[r] = min(g_max[r], l-1)
    elif x == 2:
        # x = 2の時、あるrに紐づく全てのl_iについて R < l_i, l_i <= G を満たす必要がある
        # => R < min(l_i), max(l_i) <= G を満たせばよい
        g_min[r] = max(g_min[r], l)
        r_max[r] = min(r_max[r], l-1)
    elif x == 3:
        # x = 3の時、あるrに紐づく全てのl_iについて l_i <= R を満たす必要がある
        # =>  max(l_i) <= R を満たせばよい
        r_min[r] = max(r_min[r], l)
    for j in range(l, r+1):
        free[j] = 0
# rより小さいインデックスで制約が満たすべき条件を伝播して高速化
for r in range(N-1, -1, -1):
    r_max[r] = min(r_max[r], r_max[r+1])
    g_max[r] = min(g_max[r], g_max[r+1])

def check(k, r, g, b):
    return (r_min[k] <= r <= r_max[k] and g_min[k] <= g <= g_max[k])

MOD = 10**9 + 7

# 左からk個置いた時、各色の最右の位置を持ってメモ化dfs
# r < g < b を維持して計算していく
memo = {}
def dfs(k, r, g, b):
    key = r, g, b
    if key in memo:
        return memo[key]
    if not check(k, r, g, b):
        # 制約を満たさない場合 => 0通り
        memo[key] = 0
        return 0
    if k == N:
        memo[key] = 1
        return 1
    if free[k]:
        # N = 300, M = 0の場合等だと制約が少なすぎて定数が落ちない
        # => 制約が疎である場合は、制約がかかってない部分で切って高速化
        res = memo[key] = (3 * dfs(k+1, k, k, k+1)) % MOD
    else:
        # r < g < b < k+1 なので、この関係を元に次のdfs()を計算
        res = memo[key] = (dfs(k+1, g, b, k+1) + dfs(k+1, r, b, k+1) + dfs(k+1, r, g, k+1)) % MOD
    return res
print(dfs(0, 0, 0, 0))

Submission status: Time Limit Exceeded

Solution code:
# seishin.py
from collections import deque
N, M = map(int, input().split())
r_min = [0]*(N+1); r_max = [N+1]*(N+1)
g_min = [0]*(N+1); g_max = [N+1]*(N+1)
free = [1]*(N+1)
C = [[] for i in range(N+1)]
for i in range(M):
    l, r, x = map(int, input().split())

    # 仮定: R < G < B を元に各r,gの値の範囲を絞り込む(B = rになるため計算しない)
    if x == 1:
        # x = 1の時、あるrに紐づく全てのl_iについて G < l_i を満たす必要がある
        # => G < min(l_i) を満たせばよい
        g_max[r] = min(g_max[r], l-1)
    elif x == 2:
        # x = 2の時、あるrに紐づく全てのl_iについて R < l_i, l_i <= G を満たす必要がある
        # => R < min(l_i), max(l_i) <= G を満たせばよい
        g_min[r] = max(g_min[r], l)
        r_max[r] = min(r_max[r], l-1)
    elif x == 3:
        # x = 3の時、あるrに紐づく全てのl_iについて l_i <= R を満たす必要がある
        # =>  max(l_i) <= R を満たせばよい
        r_min[r] = max(r_min[r], l)
    for j in range(l, r+1):
        free[j] = 0

def check(k, r, g, b):
    return (r_min[k] <= r <= r_max[k] and g_min[k] <= g <= g_max[k])

MOD = 10**9 + 7

# 左からk個置いた時、各色の最右の位置を持ってメモ化dfs
# r < g < b を維持して計算していく
memo = {}
def dfs(k, r, g, b):
    key = r, g, b
    if key in memo:
        return memo[key]
    if not check(k, r, g, b):
        # 制約を満たさない場合 => 0通り
        memo[key] = 0
        return 0
    if k == N:
        memo[key] = 1
        return 1
    if free[k]:
        # N = 300, M = 0の場合等だと制約が少なすぎて定数が落ちない
        # => 制約が疎である場合は、制約がかかってない部分で切って高速化
        res = memo[key] = (3 * dfs(k+1, k, k, b+1)) % MOD
    else:
        # r < g < b < k+1 なので、この関係を元に次のdfs()を計算
        res = memo[key] = (dfs(k+1, g, b, k+1) + dfs(k+1, r, b, k+1) + dfs(k+1, r, g, k+1)) % MOD
    return res
print(dfs(0, 0, 0, 0))

Submission status: Time Limit Exceeded

Solution code:
# seishin.py
N, M = map(int, input().split())
r_min = [0]*(N+1); r_max = [N+1]*(N+1)
g_min = [0]*(N+1); g_max = [N+1]*(N+1)
for i in range(M):
    l, r, x = map(int, input().split())

    # 仮定: R < G < B を元に各r,gの値の範囲を絞り込む(B = rになるため計算しない)
    if x == 1:
        # x = 1の時、あるrに紐づく全てのl_iについて G < l_i を満たす必要がある
        # => G < min(l_i) を満たせばよい
        g_max[r] = min(g_max[r], l-1)
    elif x == 2:
        # x = 2の時、あるrに紐づく全てのl_iについて R < l_i, l_i <= G を満たす必要がある
        # => R < min(l_i), max(l_i) <= G を満たせばよい
        g_min[r] = max(g_min[r], l)
        r_max[r] = min(r_max[r], l-1)
    elif x == 3:
        # x = 3の時、あるrに紐づく全てのl_iについて l_i <= R を満たす必要がある
        # =>  max(l_i) <= R を満たせばよい
        r_min[r] = max(r_min[r], l)

MOD = 10**9 + 7

#def check(r, g, k):
#    return (r_min[k] <= r <= r_max[k] and g_min[k] <= g <= g_max[k])

# 左からk個置いた時、各色の最右の位置を持ってbfs
# r < g < b(= k) を維持して計算していく
que = [{} for i in range(N+1)]
que[0][0, 0] = 1
for k in range(N-1):
    cur = que[k]
    nxt = que[k+1]
    get = nxt.get
    rm = r_min[k+1]; rM = r_max[k+1]
    gm = g_min[k+1]; gM = g_max[k+1]
    for key, val in cur.items():
        # r < g < b < k+1 の関係を元に次の状態に伝播
        r, g = key
        val %= MOD

        # 制約を満たす場合のみに伝播
        if gm <= k <= gM:
            if rm <= g <= rM:
                nxt[g, k] = get((g, k), 0) + val
            if rm <= r <= rM:
                nxt[r, k] = get((r, k), 0) + val
        if rm <= r <= rM and gm <= g <= gM:
            nxt[key] = get(key, 0) + val

rm = r_min[N]; rM = r_max[N]
gm = g_min[N]; gM = g_max[N]
ans = 0
for key, val in que[N-1].items():
    r, g = key
    if gm <= N-1 <= gM:
        ans += val*( (rm <= r <= rM) + (rm <= g <= rM) )
    if rm <= r <= rM and gm <= g <= gM:
        ans += val
    ans %= MOD

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# seishin.py
N, M = map(int, input().split())
r_min = [0]*(N+1); r_max = [N+1]*(N+1)
g_min = [0]*(N+1); g_max = [N+1]*(N+1)
for i in range(M):
    l, r, x = map(int, input().split())

    # 仮定: R < G < B を元に各r,gの値の範囲を絞り込む(B = rになるため計算しない)
    if x == 1:
        # x = 1の時、あるrに紐づく全てのl_iについて G < l_i を満たす必要がある
        # => G < min(l_i) を満たせばよい
        g_max[r] = min(g_max[r], l-1)
    elif x == 2:
        # x = 2の時、あるrに紐づく全てのl_iについて R < l_i, l_i <= G を満たす必要がある
        # => R < min(l_i), max(l_i) <= G を満たせばよい
        g_min[r] = max(g_min[r], l)
        r_max[r] = min(r_max[r], l-1)
    elif x == 3:
        # x = 3の時、あるrに紐づく全てのl_iについて l_i <= R を満たす必要がある
        # =>  max(l_i) <= R を満たせばよい
        r_min[r] = max(r_min[r], l)

MOD = 10**9 + 7

def check(r, g, k):
    return (r_min[k] <= r <= r_max[k] and g_min[k] <= g <= g_max[k])

# 左からk個置いた時、各色の最右の位置を持ってbfs
# r < g < b(= k) を維持して計算していく
que = [{} for i in range(N+1)]
que[0][0, 0] = 1
for k in range(N-1):
    cur = que[k]
    nxt = que[k+1]
    for key, val in cur.items():
        # r < g < b < k+1 の関係を元に次の状態に伝播
        r, g = key

        # 制約を満たす場合のみに伝播
        if check(g, k, k+1):
            nxt[g, k] = (nxt.get((g, k), 0) + val) % MOD
        if check(r, k, k+1):
            nxt[r, k] = (nxt.get((r, k), 0) + val) % MOD
        if check(r, g, k+1):
            nxt[r, g] = (nxt.get((r, g), 0) + val) % MOD
ans = 0
for key, val in que[N-1].items():
    r, g = key
    if check(g, N-1, N):
        ans += val
    if check(r, N-1, N):
        ans += val
    if check(r, g, N):
        ans += val
    ans %= MOD

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# seishin.py
N, M = map(int, input().split())
r_min = [0]*(N+1); r_max = [N+1]*(N+1)
g_min = [0]*(N+1); g_max = [N+1]*(N+1)
for i in range(M):
    l, r, x = map(int, input().split())

    # 仮定: R < G < B を元に各r,gの値の範囲を絞り込む(B = rになるため計算しない)
    if x == 1:
        # x = 1の時、あるrに紐づく全てのl_iについて G < l_i を満たす必要がある
        # => G < min(l_i) を満たせばよい
        g_max[r] = min(g_max[r], l-1)
    elif x == 2:
        # x = 2の時、あるrに紐づく全てのl_iについて R < l_i, l_i <= G を満たす必要がある
        # => R < min(l_i), max(l_i) <= G を満たせばよい
        g_min[r] = max(g_min[r], l)
        r_max[r] = min(r_max[r], l-1)
    elif x == 3:
        # x = 3の時、あるrに紐づく全てのl_iについて l_i <= R を満たす必要がある
        # =>  max(l_i) <= R を満たせばよい
        r_min[r] = max(r_min[r], l)

MOD = 10**9 + 7

def check(r, g, k):
    return +(r_min[k] <= r <= r_max[k] and g_min[k] <= g <= g_max[k])

# 左からk個置いた時、各色の最右の位置を持ってbfs
# r < g < b(= k) を維持して計算していく
que = [{} for i in range(N+1)]
que[0][0, 0] = 1
for k in range(N):
    cur = que[k]
    nxt = que[k+1]
    for r, g in cur:
        # r < g < b < k+1 の関係を元に次の状態に伝播

        # 制約を満たす場合のみに伝播
        if check(g, k, k+1):
            nxt[g, k] = (nxt.get((g, k), 0) + cur[r, g]) % MOD
        if check(r, k, k+1):
            nxt[r, k] = (nxt.get((r, k), 0) + cur[r, g]) % MOD
        if check(r, g, k+1):
            nxt[r, g] = (nxt.get((r, g), 0) + cur[r, g]) % MOD
print(sum(que[N].values()) % MOD)

Submission status: Time Limit Exceeded

Solution code:
# seishin.py
from collections import deque
N, M = map(int, input().split())
r_min = [0]*(N+1); r_max = [N+1]*(N+1)
g_min = [0]*(N+1); g_max = [N+1]*(N+1)
for i in range(M):
    l, r, x = map(int, input().split())

    # 仮定: R < G < B を元に各r,gの値の範囲を絞り込む(B = rになるため計算しない)
    if x == 1:
        # x = 1の時、あるrに紐づく全てのl_iについて G < l_i を満たす必要がある
        # => G < min(l_i) を満たせばよい
        g_max[r] = min(g_max[r], l-1)
    elif x == 2:
        # x = 2の時、あるrに紐づく全てのl_iについて R < l_i, l_i <= G を満たす必要がある
        # => R < min(l_i), max(l_i) <= G を満たせばよい
        g_min[r] = max(g_min[r], l)
        r_max[r] = min(r_max[r], l-1)
    elif x == 3:
        # x = 3の時、あるrに紐づく全てのl_iについて l_i <= R を満たす必要がある
        # =>  max(l_i) <= R を満たせばよい
        r_min[r] = max(r_min[r], l)

MOD = 10**9 + 7

# 左からk個置いた時、各色の最右の位置を持ってメモ化dfs
# r < g < b(= k) を維持して計算していく
memo = {}
for i in range(N):
    for j in range(i, N):
        # k = N を条件判定するコストが無駄なので事前計算
        memo[i, j, N] = +(r_min[N] <= i <= r_max[N] and g_min[N] <= j <= g_max[N])
def dfs(*key):
    r, g, k = key
    if key in memo:
        return memo[key]
    if not (r_min[k] <= r <= r_max[k] and g_min[k] <= g <= g_max[k]):
        # 制約を満たさない場合 => 0通り
        memo[key] = 0
        return 0
    # r < g < b < k+1 なので、この関係を元に次のdfs()を計算
    res = memo[key] = (dfs(g, k, k+1) + dfs(r, k, k+1) + dfs(r, g, k+1)) % MOD
    return res
print(dfs(0, 0, 0))

Submission status: Time Limit Exceeded

Solution code:
# seishin.py
from collections import deque
N, M = map(int, input().split())
r_min = [0]*(N+1); r_max = [N+1]*(N+1)
g_min = [0]*(N+1); g_max = [N+1]*(N+1)
C = [[] for i in range(N+1)]
for i in range(M):
    l, r, x = map(int, input().split())

    # 仮定: R < G < B を元に各r,gの値の範囲を絞り込む(B = rになるため計算しない)
    if x == 1:
        # x = 1の時、あるrに紐づく全てのl_iについて G < l_i を満たす必要がある
        # => G < min(l_i) を満たせばよい
        g_max[r] = min(g_max[r], l-1)
    elif x == 2:
        # x = 2の時、あるrに紐づく全てのl_iについて R < l_i, l_i <= G を満たす必要がある
        # => R < min(l_i), max(l_i) <= G を満たせばよい
        g_min[r] = max(g_min[r], l)
        r_max[r] = min(r_max[r], l-1)
    elif x == 3:
        # x = 3の時、あるrに紐づく全てのl_iについて l_i <= R を満たす必要がある
        # =>  max(l_i) <= R を満たせばよい
        r_min[r] = max(r_min[r], l)

def check(k, r, g, b):
    return (r_min[k] <= r <= r_max[k] and g_min[k] <= g <= g_max[k])

MOD = 10**9 + 7

# 左からk個置いた時、各色の最右の位置を持ってメモ化dfs
# r < g < b を維持して計算していく
memo = {}
def dfs(k, r, g, b):
    key = r, g, b
    if key in memo:
        return memo[key]
    if not check(k, r, g, b):
        # 制約を満たさない場合 => 0通り
        memo[key] = 0
        return 0
    if k == N:
        memo[key] = 1
        return 1
    # r < g < b < k+1 なので、この関係を元に次のdfs()を計算
    res = memo[key] = (dfs(k+1, g, b, k+1) + dfs(k+1, r, b, k+1) + dfs(k+1, r, g, k+1)) % MOD
    return res
print(dfs(0, 0, 0, 0))

Submission status: Time Limit Exceeded

Solution code:
# seishin.py
from collections import deque
N, M = map(int, input().split())
C = [[] for i in range(N+1)]
for i in range(M):
    l, r, x = map(int, input().split())
    C[r].append((l, x))

def check(k, r, g, b):
    # 仮定: r < g < b
    for l, x in C[k]:
        # 区間[l, k]内はx種類の色
        if x == 1:
            if not g < l:
                return 0
        elif x == 2:
            if not r < l or not l <= g:
                return 0
        else:
            if not l <= r:
                return 0
    return 1

MOD = 10**9 + 7

# 左からk個置いた時、各色の最右の位置を持ってメモ化dfs
# r < g < b を維持して計算していく
memo = {}
def dfs(k, r, g, b):
    key = r, g, b
    if key in memo:
        return memo[key]
    if not check(k, r, g, b):
        # 制約を満たさない場合 => 0通り
        memo[key] = 0
        return 0
    if k == N:
        memo[key] = 1
        return 1
    # r < g < b < k+1 の関係を元に次のdfs()を計算
    res = memo[key] = (dfs(k+1, g, b, k+1) + dfs(k+1, r, b, k+1) + dfs(k+1, r, g, k+1)) % MOD
    return res
print(dfs(0, 0, 0, 0))

Submission status: Time Limit Exceeded

Solution code:
# seishin.py
from collections import deque
N, M = map(int, input().split())
C = [[] for i in range(N+1)]
for i in range(M):
    l, r, x = map(int, input().split())
    C[r].append((l, x))
dp = [[[0]*N for i in range(N)] for j in range(N)]

def check(k, *L):
    # r < g < b として扱う
    r, g, b = sorted(L)
    for l, x in C[k]:
        # 区間[l, k]内はx種類の色
        if x == 1:
            if not g < l:
                return 0
        elif x == 2:
            if not r < l or not l <= g:
                return 0
        else:
            if not l <= r:
                return 0
    return 1

MOD = 10**9 + 7

# 左からk個置いた時の各色の最右の位置を持ってメモ化dfs
memo = {}
def dfs(k, r, g, b):
    key = r, g, b
    if key in memo:
        return memo[key]
    if not check(k, r, g, b):
        # 制約を満たさない場合 => 0通り
        memo[key] = 0
        return 0
    if k == N:
        memo[key] = 1
        return 1
    res = memo[key] = (dfs(k+1, k+1, g, b) + dfs(k+1, r, k+1, b) + dfs(k+1, r, g, k+1)) % MOD
    return res
print(dfs(0, 0, 0, 0))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import numpy as np

MOD = 1000000007
iist = lambda: map(int,input().split())

N,M = iist()
Q = defaultdict(list)
for i in range(M):
  l,r,x = iist()
  Q[r].append((l,x-1))

if any(x != 0 for l,x in Q[1]):
  print(0)
  exit(0)

dp = np.zeros((N,N), dtype='i8')
dp[0,0] = 3
memo = np.zeros(N, dtype='i8')
memo[0] = 6
s = 3

indices = {(0,0)}

for pk in range(1,N):
  k = pk+1
  dp[:pk,pk] = memo[:pk]
  memo[:pk] *= 2

  memo[pk] = 2*s%MOD
  s = 3*s%MOD
  subQ = Q[k]

  indices.update((i,pk) for i in range(pk))
  removes = []

  for i,j in indices:
    for l,x in subQ:
      if x != int(l<=i)+int(l<=j):
        c = dp[i,j]
        memo[i] -= c
        memo[j] -= c
        s -= c
        removes.append((i,j))
        break

  indices.difference_update(removes)

  memo[:pk] %= MOD
  s %= MOD

print(s)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import numpy as np

MOD = 1000000007
iist = lambda: map(int,input().split())

N,M = iist()
Q = defaultdict(list)
for i in range(M):
  l,r,x = iist()
  Q[r].append((l,x-1))

if any(x != 0 for l,x in Q[1]):
  print(0)
  exit(0)

dp = np.zeros((N,N), dtype='i8')
dp[0,0] = 3
memo = np.zeros(N, dtype='i8')
memo[0] = 6
s = 3

for pk in range(1,N):
  k = pk+1
  dp[:pk,pk] = memo[:pk]
  memo[:pk] *= 2

  memo[pk] = 2*s%MOD
  s = 3*s%MOD
  subQ = Q[k]

  for i,j in zip(*np.nonzero(dp[:pk,:k])):
    for l,x in subQ:
      if x != int(l<=i)+int(l<=j):
        c = dp[i,j]
        memo[i] -= c
        memo[j] -= c
        s -= c
        dp[i,j] = 0
        break

  memo[:pk] %= MOD
  s %= MOD

print(s)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

MOD = 1000000007
iist = lambda: map(int,input().split())

N,M = iist()
Q = defaultdict(list)
for i in range(M):
  l,r,x = iist()
  Q[r].append((l,x))

if any(x != 1 for l,x in Q[1]):
  print(0)
  exit(0)

dp = defaultdict(int)
dp[0,0] = 3

x_sum = [3]
y_sum = [3]
s = 3

for pk in range(1,N):
  k = pk+1

  dp.update(((i,pk),s%MOD) for i,s in enumerate(map(sum, zip(x_sum,y_sum))))

  for i in range(pk):
    x_sum[i] += dp[i,pk]
  x_sum.append(0)
  y_sum.append((2*s)%MOD)
  s *= 3

  removes = [(i,j) for i,j in dp.keys()
            if any(x != (l<=i)+(l<=j)+1 for l,x in Q[k])]

  for i,j in removes:
    c = dp[i,j]
    del dp[i,j]
    x_sum[i] -= c
    y_sum[j] -= c
    s -= c

  for i in range(pk):
    x_sum[i] %= MOD
    y_sum[i] %= MOD
  s %= MOD

print(s)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

MOD = 1000000007
iist = lambda: map(int,input().split())

N,M = iist()
Q = defaultdict(list)
for i in range(M):
  l,r,x = iist()
  Q[r].append((l,x))

if any(x != 1 for l,x in Q[1]):
  print(0)
  exit(0)

dp = defaultdict(int)
dp[0,0] = 3

x_sum = [3]
y_sum = [3]
s = 3

for pk in range(1,N):
  k = pk+1

  dp.update(((i,pk),s) for i,s in enumerate(map(sum, zip(x_sum,y_sum))))

  for i in range(pk):
    x_sum[i] += dp[i,pk]
  x_sum.append(0)
  y_sum.append((2*s))
  s *= 3

  removes = [(i,j) for i,j in dp.keys()
            if any(x != (l<=i)+(l<=j)+1 for l,x in Q[k])]

  for i,j in removes:
    c = dp[i,j]
    del dp[i,j]
    x_sum[i] -= c
    y_sum[j] -= c
    s -= c

  for i in range(pk):
    x_sum[i] %= MOD
    y_sum[i] %= MOD
  s %= MOD

print(s)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from itertools import permutations, chain
import numpy as np

MOD = 1000000007
iist = lambda: map(int,input().split())

N,M = iist()
Q = defaultdict(list)
for i in range(M):
  l,r,x = iist()
  Q[r].append((l,x))

dp = np.zeros((N,N), dtype='u8')
dp[0,0] = 1

for pk in range(N):
  k = pk+1
  dp[:,pk] += np.sum(dp,axis=0)+np.sum(dp,axis=1)

  for i,j in chain(permutations(range(k), r=2), [(0,0)]):
    for l,x in Q[k]:
      if x != (l <= i) + (l <= j) + 1:
        dp[i,j] = 0
        break
  dp %= MOD

print(np.sum(dp, dtype=int)%MOD)

Submission status: Time Limit Exceeded

Solution code:
# 最後のr,g,bでDP

from collections import defaultdict
from itertools import permutations

MOD = 1000000007

iist = lambda: map(int,input().split())
N,M = iist()
Q = list(tuple(iist()) for i in range(M))
dp = defaultdict(int)
dp[(0,0)] = 1

for pk in range(N):
  k = pk+1
  ndp = defaultdict(int)

  for (i,j),cnt in dp.items():
    cnt %= MOD
    ndp[(i,j)] += cnt 
    ndp[(i,pk)] += cnt
    ndp[(j,pk)] += cnt
  dp = ndp


  subQ = [(l,x) for l,r,x in Q if r==k]

  for (i,j) in list(dp.keys()):
    for (l,x) in subQ:
      if x != (l <= i) + (l <= j) + 1:
        del dp[(i,j)]
        break


print(sum(dp.values())%MOD)

Submission status: Time Limit Exceeded

Solution code:
import sys

mod = 10**9 + 7

def solve():
    n, m = map(int, input().split())
    cond = [[] for i in range(n + 1)]

    for i in range(m):
        li, ri, xi = map(int, input().split())
        cond[ri].append((li, xi))

    dp = [[[0]*(n + 1) for i in range(n + 1)] for j in range(n + 1)]
    dp[0][0][0] = 1

    ans = 0

    for r in range(n + 1):
        for g in range(n + 1):
            for b in range(n + 1):
                if not dp[r][g][b]:
                    continue

                k = max(r, g, b)
                flag = False

                for (li, xi) in cond[k]:
                    v = (li <= r) + (li <= g) + (li <= b)

                    if v != xi:
                        flag = True
                        break

                if flag:
                    dp[r][g][b] = 0
                    continue

                if k == n:
                    ans = (ans + dp[r][g][b]) % mod
                    continue

                dp[k + 1][g][b] = (dp[k + 1][g][b] + dp[r][g][b]) % mod
                dp[r][k + 1][b] = (dp[r][k + 1][b] + dp[r][g][b]) % mod
                dp[r][g][k + 1] = (dp[r][g][k + 1] + dp[r][g][b]) % mod

    print(ans)

if __name__ == '__main__':  
    solve()

Submission status: Time Limit Exceeded

Solution code:
import sys

mod = 10**9 + 7

def solve():
    n, m = map(int, input().split())
    cond = [[] for i in range(n + 1)]

    for i in range(m):
        li, ri, xi = map(int, input().split())
        cond[ri].append((li, xi))

    dp = [[[0]*(n + 1) for i in range(n + 1)] for j in range(n + 1)]
    dp[0][0][0] = 1

    for r in range(n + 1):
        for g in range(n + 1):
            for b in range(n + 1):
                k = max(r, g, b)
                flag = False

                for (li, xi) in cond[k]:
                    v = (li <= r) + (li <= g) + (li <= b)

                    if v != xi:
                        flag = True
                        break

                if flag:
                    dp[r][g][b] = 0
                    continue

                if k + 1 <= n:
                    dp[k + 1][g][b] = (dp[k + 1][g][b] + dp[r][g][b]) % mod
                    dp[r][k + 1][b] = (dp[r][k + 1][b] + dp[r][g][b]) % mod
                    dp[r][g][k + 1] = (dp[r][g][k + 1] + dp[r][g][b]) % mod

    ans = 0

    for r in range(n + 1):
        for g in range(n + 1):
            ans = (ans + dp[r][g][n]) % mod

    for r in range(n + 1):
        for b in range(n + 1):
            ans = (ans + dp[r][n][b]) % mod

    for g in range(n + 1):
        for b in range(n + 1):
            ans = (ans + dp[n][g][b]) % mod

    print(ans)

if __name__ == '__main__':  
    solve()