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: Memory Limit Exceeded

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

mod = 10**9+7



# (i, j, k+1)に置くのが、条件(l,x)に適しているか
def check(i, j, l, x):
    return (x == 3 and l <= i) or (x == 2 and i < l <= j) or (x == 1 and j < l)


def main():
    N, M = map(int, input().split())
    LRX = [list(map(int, input().split())) for _ in range(M)]

    LX = [[] for _ in range(N+2)]
    for l, r, x in LRX:
        LX[r].append((l, x))

    dp = [[[0]*(N+2) for _ in range(N+2)] for _ in range(N+2)]
    # dp[i][j][k] (i <= j <= k) 
    # 三色それぞれ、最後に使ったindex(1-indexed)がi,j,k

    dp[0][0][0] = 1

    for i in range(N+1):
        for j in range(i, N+1):
            for k in range(j, N+1):
                
                # 一番前の色を置く
                ok = True
                for l, x in LX[k+1]:
                    if not check(j, k, l, x):
                        ok = False
                        break
                if ok:
                    dp[j][k][k+1] = (dp[j][k][k+1] + dp[i][j][k]) % mod
                
                # 最後
                ok = True
                for l, x in LX[k+1]:
                    if not check(i, j, l, x):
                        ok = False
                        break
                if ok:
                    dp[i][j][k+1] = (dp[i][j][k+1] + dp[i][j][k]) % mod
                
                # 二番目
                ok = True
                for l, x in LX[k+1]:
                    if not check(i, k, l, x):
                        ok = False
                        break
                if ok:
                    dp[i][k][k+1] = (dp[i][k][k+1] + dp[i][j][k]) % mod
            

    ans = 0
    for a in range(N+1):
        for b in range(a,N+1):
            ans = (ans + dp[a][b][N]) % mod

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

mod = 10**9+7



# (i, j, k+1)に置くのが、条件(l,x)に適しているか
def check(i, j, l, x):
    return (x == 3 and l <= i) or (x == 2 and i < l <= j) or (x == 1 and j < l)


N, M = map(int, input().split())
LRX = [list(map(int, input().split())) for _ in range(M)]

LX = [[] for _ in range(N+2)]
for l, r, x in LRX:
    LX[r].append((l, x))

dp = [[[0]*(j+1) for j in range(i+1)] for i in range(N+2)]
# dp[i][j][k] (k <= j <= i) 
# 三色それぞれ、最後に使ったindex(1-indexed)がi,j,k

dp[0][0][0] = 1

for i in range(N+1):
    for j in range(i, N+1):
        for k in range(j, N+1):
            
            # 一番前の色を置く
            ok = True
            for l, x in LX[k+1]:
                if not check(j, k, l, x):
                    ok = False
                    break
            if ok:
                dp[k+1][k][j] = (dp[k+1][k][j] + dp[k][j][i]) % mod
            
            # 最後
            ok = True
            for l, x in LX[k+1]:
                if not check(i, j, l, x):
                    ok = False
                    break
            if ok:
                dp[k+1][j][i] = (dp[k+1][j][i] + dp[k][j][i]) % mod
            
            # 二番目
            ok = True
            for l, x in LX[k+1]:
                if not check(i, k, l, x):
                    ok = False
                    break
            if ok:
                dp[k+1][k][i] = (dp[k+1][k][i] + dp[k][j][i]) % mod
        

ans = 0
for a in range(N+1):
    for b in range(a,N+1):
        ans = (ans + dp[N][b][a]) % mod

print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
import sys
read = sys.stdin.read
readline = sys.stdin.readline

n,m = map(int,readline().split())
#lrx = [tuple(map(int,readline().split())) for _ in range(m)]
#lrx.sort(key=lambda x: x[1])
cond = [[] for _ in range(n+1)]
for _ in range(m):
    l,r,x = map(int,readline().split())
    cond[r].append((l,x))

"""
dp[i][j][k] = iまで見て 2 色目は j個前に、3 色目は k個前 に登場
1 <= j < k
"""
N = n+3
dp = [[0]*(N) for _ in range(N)]
dp[1][2] = 1

MOD = 10**9+7

def f(r,j,k,v,ndp):
    if j >= N or k >= N: return
    for l,x in cond[r]:
        if x==1 and l <= r-j: return
        if x==2 and (r-j < l or l <= r-k): return
        if x==3 and r-k < l: return
    ndp[j][k] += v
    ndp[j][k] %= MOD
    return

for i in range(1,n+1):
    ndp = [[0]*(N) for _ in range(N)]
    for q in range(1,N):
        for r in range(q+1,N):
            v = dp[q][r]
            if v:
                f(i,q+1,r+1,v,ndp)
                f(i,1,r+1,v,ndp)
                f(i,1,q+1,v,ndp)
    dp = ndp
    #print(dp)



ans = sum(sum(i) for i in dp)
print(ans%MOD)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
q=[[] for i in range(N+1)]
for i in range(M):
    l,r,x=map(int,input().split())
    q[r].append((l,x))
mod=10**9+7

dp=[[0 for i in range(N+1)] for i in range(N+1)]

i=N
for j in range(N+1):
    for k in range(N+1):
        check=7
        for l,x in q[i]:
            if i==l:
                check=(x==1)*check
            elif i-1>=l>j:
                check=(x==1)*(check%2)+(x==2)*(check&6)
            elif j>=l>k:
                check=(x==2)*(check&3)+(x==3)*(check&4)
            else:
                check*=(x==3)
        dp[j][k]=bin(check).count("1")

ndp=[[0 for j in range(N+1)] for k in range(N+1)]
for i in range(N-1,0,-1):
    for j in range(i):
        for k in range(j+1):
            check=7
            for l,x in q[i]:
                if i==l:
                    check=(x==1)*check
                elif i-1>=l>j:
                    check=(x==1)*(check%2)+(x==2)*(check&6)
                elif j>=l>k:
                    check=(x==2)*(check&3)+(x==3)*(check&4)
                else:
                    check*=(x==3)
            ndp[j][k]=(dp[j][k]*((check//1)%2)+dp[i-1][k]*((check//2)%2)+dp[i-1][j]*((check//4)%2))%mod

    dp=ndp

print(dp[0][0])

Submission status: Accepted

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

def viol(c2, c3, l, x):
    res = False
    if x == 1:
        if not c2 < l:
            res = True
    elif x == 2:
        if not c3 < l <= c2:
            res = True
    else:
        if not l <= c3:
            res = True
    return res
MOD = 10**9+7
N, M = map(int, readline().split())
limit = [[] for _ in range(N+3)]

for _ in range(M):
    l, r, x = map(int, readline().split())
    limit[r+2].append((l+2, x))

dp = [[0, 0], [1, 0]]

for i in range(2, N+2):    
    dp2 = [[0]*(i+1) for _ in range(i+1)]
    r = i
    for g in range(r):
        for b in range(g):
            d = dp[g][b]
            dp2[g][b] = (dp2[g][b] + d)%MOD
            dp2[r][b] = (dp2[r][b] + d)%MOD
            dp2[r][g] = (dp2[r][g] + d)%MOD
    for l, x in limit[i+1]:
        r = i+1
        for g in range(r):
            for b in range(g):
                if viol(g, b, l, x):
                    dp2[g][b] = 0
    dp = [d[:] for d in dp2]
    
res = 0
for g in range(N+2):
    for b in range(g):
        res = (res + dp[g][b]) % MOD
print(res)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np

# 右端を色1として、(色2の末尾、色3の末尾) -> 何通り
# よくわからなくなるので、0番：色3、1番：色2、2番：色1を置いた状態から始める。
# 本来のL,RをL+2,R+2に設定

MOD = 10 ** 9 + 7

N,M = map(int,readline().split())
m = map(int,read().split())
LRX = zip(m,m,m)

R_to_LX = [[] for _ in range(N+3)]
for l,r,x in LRX:
    R_to_LX[r+2].append((l+2,x))

dp = np.zeros((N+3,N+3),np.int64)
dp[1,0] = 1
for r in range(3,N+3):
    # まず、末尾に色を置く
    prev = dp
    dp = np.zeros((N+3,N+3),np.int64)
    # 末尾に色 1
    dp += prev
    # 末尾に色 2
    dp[r-1,:] += prev.sum(axis=0)
    # 末尾に色 3
    dp[r-1,:] += prev.sum(axis=1)
    # 禁止条件を処理
    for l,x in R_to_LX[r]:
        if x == 1:
            dp[l:] = 0
        elif x == 2:
            # 2つはある
            dp[:l] = 0
            # 3つはない
            dp[:,l:] = 0
        else:
            # 3つある
            dp[:,:l] = 0
    dp %= MOD

answer = dp.sum() % MOD
print(answer)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict

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

# 一番後ろの色を(赤に)固定した上で、もらうDPに書き換え
def main():
    md = 10 ** 9 + 7
    n, m = MI()
    rtol = defaultdict(list)
    for _ in range(m):
        l, r, x = MI()
        rtol[r].append([l, x])
    dp = [[0] * (n + 1) for _ in range(n + 1)]
    dp[0][0] = 1
    for k in range(1, n + 1):
        for i in range(k - 1):
            dp[i][k - 1] = dp[k - 1][i] = sum(dp[i][:k - 1]) % md
        for l, x in rtol[k]:
            if x == 1:
                for i in range(l, k):
                    for j in range(k):
                        dp[i][j] = dp[j][i] = 0
            if x == 2:
                for i in range(l, k):
                    for j in range(i + 1, k):
                        dp[i][j] = dp[j][i] = 0
                for i in range(l):
                    for j in range(i + 1):
                        dp[i][j] = dp[j][i] = 0
            if x == 3:
                for i in range(l):
                    for j in range(k):
                        dp[i][j] = dp[j][i] = 0

    # p2D(dp)
    print(sum(sum(dr) for dr in dp) * 3 % md)

main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
import numpy as np
from collections import defaultdict

# 最後に置いたものは赤とする（3倍）
# 青、緑を最後にいつ置いたのかを持ってdp

MOD = 10 ** 9 + 7
N,M = map(int,input().split())
LRX = [[int(x) for x in input().split()] for _ in range(M)]

R_to_LX = defaultdict(list)
for l,r,x in LRX:
    R_to_LX[r].append((l,x))

# 1個目を置いた時点
for n in range(1,N+1):
    if n == 1:
        dp = np.zeros((n,n), dtype = np.int64)
        dp[0,0] = 1
    else:
        prev = dp
        dp = np.zeros((n,n), dtype = np.int64)
        # 同色
        dp[:-1,:-1] = prev
        # 青から赤に
        dp[n-1,:-1] = prev.sum(axis = 0)
        # 緑から赤に
        dp[:-1,n-1] = prev.sum(axis = 1)
    # ルール違反を除外する
    for l,x in R_to_LX[n]:
        if x == 1:
            dp[l:,:] = 0
            dp[:,l:] = 0
        elif x == 2:
            dp[l:,l:] = 0
            dp[:l,:l] = 0
        elif x == 3:
            dp[:l,:] = 0
            dp[:,:l] = 0
    dp %= MOD

answer = dp.sum() * 3 % MOD
print(answer)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
Q=[[int(i) for i in input().split()] for i in range(M)]
Q.sort(key=lambda x:x[1])
mod=10**9+7
dp=[[[0]*max(1,c) for c in range(max(1,b+1))] for b in range(N+1)]
dp[0][0][0]=1
k=0
for a in range(N+1):
  check=[]
  if k<=M-1:
    while a==Q[k][1]:
      l,r,x=Q[k]
      check.append((l,r,x))
      k+=1
      if k==M:
        break
  for b in range(max(1,a)):
    for c in range(max(1,b)):
      for l,r,x in check:
        if x==1:
          if not b<l:
            dp[a][b][c]=0
            continue
        elif x==2:
          if not (b>=l and c<l):
            dp[a][b][c]=0
            continue
        elif x==3:
          if not c>=l:
            dp[a][b][c]=0
            continue
      dp[a][b][c]%=mod
      if a<=N-1:
        dp[a+1][b][c]+=dp[a][b][c]
        dp[a+1][a][c]+=dp[a][b][c]
        dp[a+1][a][b]+=dp[a][b][c]
ans=0
for b in range(N):
  for c in range(max(1,b)):
    ans+=dp[N][b][c]
    ans%=mod
print(ans)

Submission status: Accepted

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())
    if r-l < x-1:
        print(0)
        exit(0)
    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}
D = [0]*(N+1); D[0] = 6
B = [{} for i in range(N+1)]
B[0][0] = 3
bb = 0
for b in range(1, N):
    t2 = T2[b+1]; s1 = S1[b+1]; t1 = T1[b+1]; s0 = S0[b+1]

    rm = RM[b]
    gm = GM[b]
    if t1 <= b < gm:
        F = B[b]
        for z in range(t2, min(rm, b)):
            v = D[z] % MOD
            if v:
                F[z] = v; D[z] += v; D[b] += v
    if C[b+1]:
        for g in range(bb, min(t1, b)):
            for r, v in B[g].items():
                D[r] -= v; D[g] -= v
            B[g] = None
        bb = max(t1, bb)
        for g in range(bb, b):
            for r, v in B[g].items():
                if not t2 <= r < s1:
                    D[r] -= v; D[g] -= v
            B[g] = {r: v for r, v in B[g].items() if t2 <= r < s1}
ans = 0
for b in range(bb, N+1):
    if B[b]:
        ans += sum(B[b].values())
print(ans % MOD)

Submission status: Accepted

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-1))

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

dp = {(0,0):3}
memo = [6]
s = 3

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

  for i,c in enumerate(memo):
    c %= MOD
    dp[i,pk] = c
    memo[i] *= 2
    memo[i] %= MOD

  memo.append(2*s%MOD)
  s = 3*s%MOD
  subQ = Q[k]

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

  s %= MOD

print(s)

Submission status: Accepted

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

  for i,(a,b) in enumerate(zip(x_sum,y_sum)):
    c = (a+b)%MOD
    dp[i,pk] = c
    x_sum[i] += c

  x_sum.append(0)
  y_sum.append((2*s)%MOD)
  s *= 3
  subQ = Q[k]

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

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

print(s)

Submission status: Runtime Error

Solution code:
from itertools import permutations
n,m = map(int,input().split())
lrx = [list(map(int,input().split())) for i in range(m)]
lrx.sort(key = lambda x:x[1])
mod = 10**9+7
dp = [[[0 for i in range(n+1)] for j in range(n+1)] for k in range(n+1)]
dp[0][0][0] = 1
for l,r,t in lrx:
  if t != 1:
    for g in range(l):
      for b in range(max(1,g)):
        dp[r][g][b] = -1
  if t != 2:
    for g in range(l,r):
      for b in range(l):
        dp[r][g][b] = -1
  if t != 3:
    for g in range(l,r):
      for b in range(l,g):
        dp[r][g][b] = -1

for r in range(n):
  for g in range(r):
    for b in range(max(1,g)):
      v = dp[r][g][b]
      if v == -1:
        continue
      if dp[r+1][g][b] >= 0:
        dp[r+1][g][b] += v
        dp[r+1][g][b] %= mod
      if dp[r+1][r][b] >= 0:
        dp[r+1][r][b] += v
        dp[r+1[r][b] %= mod
      if dp[r+1][g][b] >= 0:
        dp[r+1][g][b] += v
        dp[r+1][g][b] %= mod
ans = 0
for i in range(n):
  for j in range(max(1,i)):
    if dp[n][i][j] >= 0:
      ans += dp[n][i][j]
      ans %= mod
print(ans*6%mod)

Submission status: Runtime Error

Solution code:
from itertools import permutations
n,m = map(int,input().split())
lrx = [list(map(int,input().split())) for i in range(m)]
lrx.sort(key = lambda x:x[1])
mod = 10**9+7
dp = [[[0 for i in range(n+1)] for j in range(n+1)] for k in range(n+1)]
dp[0][0][0] = 1
for l,r,t in lrx:
  if t != 1:
    for g in range(l):
      for b in range(max(1,g)):
        for x,y,z in permutations((r,g,b)):
          dp[x][y][z] = -1
  if t != 2:
    for g in range(l,r):
      for b in range(l):
        for x,y,z in permutations((r,g,b)):
          dp[x][y][z] = -1
  if t != 3:
    for g in range(l,r):
      for b in range(l,g):
        for x,y,z in permutations((r,g,b)):
          dp[x][y][z] = -1

for r in range(n):
  for g in range(r):
    for b in range(max(1,g)):
      v = dp[r][g][b]
      if v == -1:
        continue
      if dp[mx+1][g][b] >= 0:
        dp[mx+1][g][b] += v
        dp[mx+1][g][b] %= mod
      if dp[r][mx+1][b] >= 0:
        dp[r][mx+1][b] += v
        dp[r][mx+1][b] %= mod
      if dp[r][g][mx+1] >= 0:
        dp[r][g][mx+1] += v
        dp[r][g][mx+1] %= mod
ans = 0
for i in range(n):
  for j in range(max(1,i)):
    for x,y,z in permutations((n,i,j)):
      if dp[x][y][z] >= 0:
        ans += dp[x][y][z]
        ans %= mod
print(ans*6%mod)
"""

Submission status: Runtime Error

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, k, k+1):
        ans += val
    if check(r, k, k+1):
        ans += val
    if check(r, g, k+1):
        ans += val
    ans %= MOD

print(ans)

Submission status: Runtime Error

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+1, 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: Runtime Error

Solution code:
#include <bits/stdc++.h>
#define REP(i,a,b) for(int i=(a);i<(b);i++)
#define RREP(i,a,b) for(int i=(a);i>=(b);i--)
#define pq priority_queue
#define P pair<int,int>
#define P2 pair<int,P>
#define P3 pair<int,P2>
typedef long long ll; typedef long double ld;
using namespace std;
const int INF=1e9, MOD=1e9+7, around[]={0,1,1,-1,-1,0,-1,1,0,0};
const ll LINF=1e18;
const ld PI=abs(acos(-1));
int n,m,a,b,c;
ll dp[310][310][310]; //最右のindex
vector<P> vec[310];

bool ch(int i,int j,int k){
	int r=max(i,max(j,k));
	for(auto s:vec[r]){
		if(((s.first<i)+(s.first<j)+(s.first<k))!=s.second) return 0;
	}
	
	return 1;
}

int main(){
	cin >> n >> m;
	REP(i,0,m) cin >> a >> b >> c,vec[b].push_back(P(a-1,c));
	
	dp[0][0][0]=1;
	REP(i,0,n){
		REP(j,0,n){
			REP(k,0,n){
				int ma=max(i,max(j,k));
				if(ch(i,j,ma+1)) (dp[i][j][ma+1]+=dp[i][j][k])%=MOD;
				if(ch(i,ma+1,k)) (dp[i][ma+1][k]+=dp[i][j][k])%=MOD;
				if(ch(ma+1,j,k)) (dp[ma+1][j][k]+=dp[i][j][k])%=MOD;
			}
		}
	}
	
	ll s=0;
	REP(i,0,n+1){
		REP(j,0,n+1){
			s+=dp[n][i][j];
			s+=dp[i][n][j];
			s+=dp[i][j][n];
		}
	}
	cout << s%MOD << endl;
	return 0;
}

Submission status: Runtime Error

Solution code:
x_sum = [3]
y_sum = [3]
s = 3

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

  for i,c in enumerate(map(sum,zip(x_sum,y_sum))):
    c %= MOD
    dp[i,pk] = c
    x_sum[i] += c

  x_sum.append(0)
  y_sum.append(2*s%MOD)
  s = 3*s%MOD
  subQ = Q[k]

  for i,j in list(dp.keys()):
    for l,x in subQ:
      if x != (l<=i)+(l<=j):
        c = dp[i,j]
        x_sum[i] -= c
        y_sum[j] -= c
        y_sum[j] %= MOD
        s -= c
        del dp[i,j]
        break

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

print(s)

Submission status: Runtime Error

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,j in range(pk):
    x_sum[i] %= MOD
    y_sum[i] %= MOD
  s %= MOD

print(s)