Problem:


Score : 700 points

Problem Statement

There are N stones arranged in a row. The i-th stone from the left is painted in the color C_i.

Snuke will perform the following operation zero or more times:

Choose two stones painted in the same color. Repaint all the stones between them, with the color of the chosen stones.

Find the number of possible final sequences of colors of the stones, modulo 10^9+7.

Constraints

1 \leq N \leq 2\times 10^5

1 \leq C_i \leq 2\times 10^5(1\leq i\leq N)

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
C_1
:
C_N

Output

Print the number of possible final sequences of colors of the stones, modulo 10^9+7.

Sample Input 1

5
1
2
1
2
2

Sample Output 1

3

We can make three sequences of colors of stones, as follows:

(1,2,1,2,2), by doing nothing.

(1,1,1,2,2), by choosing the first and third stones to perform the operation.

(1,2,2,2,2), by choosing the second and fourth stones to perform the operation.

Sample Input 2

6
4
2
5
4
2
4

Sample Output 2

5

Sample Input 3

7
1
3
1
2
3
3
2

Sample Output 3

5



Sample input:
5
1
2
1
2
2


Sample output:
3

Submission status: Accepted

Solution code:
N = int(input())
MOD = 10 ** 9 + 7
memo = {}
prev_num = 1
prev = None
for _ in range(N):
  c = int(input())
  if prev == c:
    continue
  tmp = prev_num
  if c in memo:
    tmp += memo[c]
  tmp %= MOD
  memo[c] = tmp
  prev_num = tmp
  prev = c
print(prev_num % MOD)

Submission status: Accepted

Solution code:
# B
N = int(input())
C_list = [0]*N
for i in range(N):
    C_list[i] = int(input()) - 1
    
LARGE = 10**9+7

T = 1
DP = [0]*(max(C_list) + 1)

for i in range(N):
    c = C_list[i]
    if i > 0:
        if C_list[i] == C_list[i-1]:
            pass
        else:
            T, DP[c] = (T + DP[c]) % LARGE, (DP[c] + T) % LARGE
    else:
        T, DP[c] = (T + DP[c]) % LARGE, (DP[c] + T) % LARGE
print(T)

Submission status: Accepted

Solution code:
from sys import exit, setrecursionlimit, stderr, stdin
from functools import reduce
from itertools import *
from collections import defaultdict, Counter
from bisect import bisect

setrecursionlimit(10**7)

M = 10 ** 9 + 7

def input():
  return stdin.readline().strip()

def read():
  return int(input())

def reads():
  return [int(x) for x in input().split()]

def solve():
  N = read()
  C = [-1] * N
  p = 0
  for i in range(N):
    c = read() - 1
    if C[p-1] != c:
      C[p] = c
      p += 1
  N = p
  del C[N:]

  dp = [0] * (N+1)
  dp[0] = 1
  last = [0] * (2 * 10**5 + 10)
  for i in range(N):
    c = C[i]
    last[c] = (last[c] + dp[i]) % M
    dp[i+1] = last[c]
  # print('dp', dp)
  print(dp[-1])

solve()

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict

n = int(input())
stones = [-1]
for line in sys.stdin:
    c = int(line)
    if stones[-1] == c:
        continue
    stones.append(c)

dp = 1
prev = defaultdict(lambda: 0)
MOD = 10 ** 9 + 7
for s in stones[1:]:
    dp = (dp + prev[s]) % MOD
    prev[s] = dp
print(dp)

Submission status: Accepted

Solution code:
N = input()
C = [input()-1 for _ in range(N)]

P = [-1]*(2*10**5)
T = [0]*N
M = 10**9+7
T[0] = 1
P[C[0]] = 0
for i in range(1,N):
  T[i] = T[i-1]
  p = P[C[i]]
  if p>=0 and i-p>=2:
    T[i] += T[p]
    T[i] %= M
  P[C[i]] = i
print T[-1]

Submission status: Accepted

Solution code:
import collections
MOD = int(1e9 + 7)
n = int(input())
dic = {}
f = [0] * (n + 1)
f[0] = 1
for i in range(n):
	x = int(input())
	if x not in dic:
		f[i + 1] = f[i]
	elif dic[x] == i - 1:
		f[i + 1] = f[i]
	else:
		f[i + 1] = (f[i] + f[dic[x] + 1]) % MOD
	dic[x] = i

print(f[-1] % MOD)

Submission status: Runtime Error

Solution code:
n = int(input())
mod = 10**9+7
count = [0]*(n+1)
l = [0]+[int(input()) for i in range(n)]
dp = [0]*(n+1)
dp[0] = 1
for i in range(1,n+1):
    if l[i] == l[i-1]:
        dp[i] = dp[i-1]
        continue
    dp[i] = (dp[i-1]+count[l[i]])%mod
    count[l[i]] = dp[i]
print(dp[-1])

Submission status: Runtime Error

Solution code:
# 解説 https://betrue12.hateblo.jp/entry/2019/03/17/011847

from collections import defaultdict

mod = 10 ** 9 + 7

N = int(input())
C = [int(input()) for _ in range(N)]
L = [-1] * (N + 10)  # 出たところ
dp = [-1] * (N + 10)
dp[0] = 1

for i in range(N):
    if L[C[i]] == -1:
        dp[i + 1] = dp[i]
    elif C[i] == C[i - 1]:
        dp[i + 1] = dp[i]
    else:
        dp[i + 1] = dp[i] + dp[L[C[i]]]
    
    dp[i + 1] %= mod
    L[C[i]] = i + 1

print(dp[N])

Submission status: Runtime Error

Solution code:
# 解説 https://betrue12.hateblo.jp/entry/2019/03/17/011847

from collections import defaultdict

mod = 10 ** 9 + 7

N = int(input())
C = [int(input()) for _ in range(N)]
L = [-1] * (N + 1)  # 出たところ
dp = [-1] * (N + 1)
dp[0] = 1

for i in range(N):
    if L[C[i]] == -1:
        dp[i + 1] = dp[i]
    elif C[i] == C[i - 1]:
        dp[i + 1] = dp[i]
    else:
        dp[i + 1] = dp[i] + dp[L[C[i]]]
    
    dp[i + 1] %= mod
    L[C[i]] = i + 1

print(dp[N])

Submission status: Runtime Error

Solution code:
# 解説 https://betrue12.hateblo.jp/entry/2019/03/17/011847

from collections import defaultdict

mod = 10 ** 9 + 7

N = int(input())
C = [int(input()) for _ in range(N)]
dp = [0] * (N + 1)
dp[0] = 1

for i in range(1, N):
    if C[i] == C[i - 1]:
        dp[i] = dp[i - 1]
    else:
        max_k = -1
        for k in range(i - 1):
            if C[k] == C[i]:
                max_k = max(max_k, k)
        if max_k == -1:
            dp[i] = dp[i - 1]
        else:
            dp[i] = dp[i - 1] + dp[max_k]

print(dp[N - 1])y

Submission status: Runtime Error

Solution code:
import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def dijkstra(G, s):
    que = []
    d = [INF]*len(G)
    d[s] = 0
    heapq.heappush(que, (d[s], s))

    while que:
        p = heapq.heappop(que)
        v = p[1]
        if d[v] < p[0]: continue
        for e in G[v]:
            if d[e[0]] > d[v] + e[1]:
                d[e[0]] = d[v] + e[1]
                heapq.heappush(que, (d[e[0]], e[0]))
    return d

def resolve():
    n, m = LI()
    s, t = LI_()
    G = collections.defaultdict(list)
    for _ in range(m):
        x, y, d = LI()
        G[x-1].append((y - 1, d))
        G[y-1].append((x - 1, d))

    # dist_s = dijkstra(G, s)
    # dist_t = dijkstra(G, t)

    # ans = [i + 1 for i in range(n) if dist_s[i] == dist_t[i]]
    # if ans:
    #     print(ans[0])
    # else:
    #     print(-1)

if __name__ == '__main__':
    resolve()

Submission status: Runtime Error

Solution code:
N = int(input())
C = [int(input()) for _ in range(N)]

L = [-1]*(10**5+10)
dp = [-1]*(10**5+10)
dp[0] = 1

for i in range(N):
    if L[C[i]] == -1:
        dp[i+1] = dp[i]
    elif C[i] == C[i-1]:
        dp[i+1] = dp[i]
    else:
        dp[i+1] = dp[i]+dp[L[C[i]]]
    L[C[i]] = i+1
print(dp[N])

Submission status: Runtime Error

Solution code:
n=int(input())
cc=[int(input()) for _ in range(n)]


c=[cc[0]]
for i in range(1,n):
    if cc[i]!=cc[i-1]:
        c.append(cc[i])

n=len(c)

right_index=[-1]*n
tmp_right_index=[-1]*n

for i in range(n):
    if tmp_right_index[c[i]]==-1:
        tmp_right_index[c[i]]=i
    else:
        right_index[i]=tmp_right_index[c[i]]
        tmp_right_index[c[i]]=i

dp=[0]*n

#print(0,c)
for i in range(n):
    if i==0:
        dp[i]=1
    else:
        if right_index[i]==-1:
            dp[i]+=dp[i-1]
        else:
            dp[i]+=dp[i-1]+dp[right_index[i]]

print(dp[-1])

Submission status: Runtime Error

Solution code:
import sys

input = sys.stdin.readline
P = 10 ** 9 + 7


def main():
    N = int(input())
    C = [None] * N
    for i in range(N):
        C[i] = int(input())

    C = [-1] + C
    D = [-1] * (N + 1)
    dp = [0] * (N + 1)
    dp[0] = 1
    for i in range(N):
        if C[i + 1] == C[i]:
            dp[i + 1] = dp[i]
        else:
            j = D[C[i + 1]]
            if j != -1:
                dp[i + 1] = dp[i] + dp[j]
            else:
                dp[i + 1] = dp[i]
        dp[i + 1] %= P
        D[C[i + 1]] = i + 1

    ans = dp[N]
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1
def solve_binary(mid,j):
    return pairs[mid][0] >= j
    pass

def binary_search(n,j):
    ok=n
    ng=0
    while abs(ok-ng)>1:
        mid=(ok+ng)//2
        if solve_binary(mid,j):
            ok=mid
        else:
            ng=mid
    return ok

n = int(input())
C = [int(input()) for i in range(n)]
pairs = []
data = [-1]*(n+1)
for i,ci in enumerate(C):
  if data[ci] != -1 and abs(i-data[ci]) != 1:
    pairs.append((data[ci],i))
  data[ci] = i
pairs.sort()
l = len(pairs)
for i,j in pairs:
  k = binary_search(l,j)
  # print(k,12345)
  ans += l-k+1
  ans %= mod
print(ans+1)
# print(pairs)

Submission status: Runtime Error

Solution code:
N = int(input())
C = [int(input()) for i in range(N)]
dp = [0] * (N+1)
dp_c = [0] * (N+1)
pred_ci = 0
dp[0] = 1
for i, ci in enumerate(C, 1):
    if pred_ci == ci:
        dp[i] += dp[i-1]
        continue
    dp[i] += dp[i-1] + dp_c[ci]
    dp_c[ci] = dp[i]
    pred_ci = ci

print(dp[N])

Submission status: Runtime Error

Solution code:
import sys

mod = 10**9 + 7
N = int(sys.stdin.readline())

stones = []
for _ in range(N):
    stones.append(int(sys.stdin.readline()) - 1)

left = [-1 for _ in range(N+5)]
dp = [0 for _ in range(N+5)]
dp[0] = 1
for i in range(N):
    dp[i+1] = dp[i]
    # 同じ色が前回出現した位置
    c = stones[i]
    if 0 <= left[c] < i - 1:
        dp[i+1] += dp[left[c] + 1]
    
    dp[i+1] %= mod
    left[c] = i

print(dp[N])

Submission status: Runtime Error

Solution code:
import sys

mod = 10**9 + 7
N = int(sys.stdin.readline())

stones = []
for _ in range(N):
    stones.append(int(sys.stdin.readline()) - 1)

left = [-1 for _ in range(N)]
dp = [0 for _ in range(N+1)]
dp[0] = 1
for i in range(N):
    dp[i+1] = dp[i]
    # 同じ色が前回出現した位置
    c = stones[i]
    if 0 <= left[c] < i - 1:
        dp[i+1] += dp[left[c] + 1]
    
    dp[i+1] %= mod
    left[c] = i

print(dp[N])

Submission status: Runtime Error

Solution code:
import sys

mod = 10**9 + 7
N = int(sys.stdin.readline())

stones = []
for _ in range(N):
    stones.append(int(sys.stdin.readline()))

left = [-1 for _ in range(N+1)] # 1-indexed
dp = [0 for _ in range(N+1)]
dp[0] = 1
for i in range(N):
    dp[i+1] = dp[i]
    # 同じ色が前回出現した位置
    c = stones[i]
    if 0 <= left[c] < i - 1:
        dp[i+1] += dp[left[c] + 1]
    
    dp[i+1] %= mod
    left[c] = i

print(dp[N])

Submission status: Runtime Error

Solution code:
import sys

mod = 10**9 + 7
N = int(sys.stdin.readline())

stones = []
for _ in range(N):
    stones.append(int(sys.stdin.readline()))

left = [-1] * (N+1) # 1-indexed
dp = [0] * (N+1)
dp[0] = 1
for i in range(N):
    dp[i+1] = dp[i]
    # 同じ色が前回出現した位置
    c = stones[i]
    if 0 <= left[c] < i - 1:
        dp[i+1] += dp[left[c] + 1]
    
    dp[i+1] %= mod
    left[stones[i]] = i

print(dp[N])

Submission status: Runtime Error

Solution code:
import sys

N = int(sys.stdin.readline())

stones = []
for _ in range(N):
    stones.append(int(sys.stdin.readline()))

left = [-1] * (N+1) # 1-indexed
dp = [0] * (N+1)
dp[0] = 1
for i in range(1, N+1):
    dp[i] = dp[i-1]
    # 同じ色が前回出現した位置
    if left[stones[i-1]] != -1 and left[stones[i-1]] != i - 1:
        dp[i] += dp[left[stones[i-1]]]
    
    left[stones[i-1]] = i

print(dp[-1])

Submission status: Runtime Error

Solution code:
import sys

N = int(sys.stdin.readline())

stones = []
for _ in range(N):
    stones.append(int(sys.stdin.readline()))

left = [-1] * N
dp = [0] * (N+1)
dp[0] = 1
for i in range(1, N+1):
    dp[i] = dp[i-1]
    # 同じ色が前回出現した位置
    if left[stones[i-1]] != -1 and left[stones[i-1]] != i - 1:
        dp[i] += dp[left[stones[i-1]]]
    
    left[stones[i-1]] = i

print(dp[-1])

Submission status: Runtime Error

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    N=I()
    C=[]
    
    #連番無視
    for i in range(N):
        c=I()
        c-=1
        if C==[]:
            C.append(c)
        else:
            if C[-1]!=c:
                C.append(c)         
            
    """
    i番目の通り数をf(i)とする．
    今，i番目までを見てて，i番目と同じ数はj,kにあるとする．
    f(i)=
         f(i-1) #iを使わない
        +f(j-1) #i-jのみ
        +f(k-1) #i-kのみ
    かな，各色ごとに，f(j-1)+f(k-1)みたいなのをまとめておく
    """    
    S=[0]*N
    
    ans=1
    for c in C:
        temp=ans
        ans=(ans+S[c])%mod
        S[c]=(S[c]+temp)%mod
        
    print(ans)
        
        
        
        
    

main()

Submission status: Runtime Error

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    N=I()
    C=[]
    
    #連番無視
    for i in range(N):
        c=I()
        c-=1
        if C==[]:
            C.append(c)
        else:
            if C[-1]!=c:
                C.append(c)
    N=len(C)            
            
    """
    i番目の通り数をf(i)とする．
    今，i番目までを見てて，i番目と同じ数はj,kにあるとする．
    f(i)=
         f(i-1) #iを使わない
        +f(j-1) #i-jのみ
        +f(k-1) #i-kのみ
    かな，各色ごとに，f(j-1)+f(k-1)みたいなのをまとめておく
    """    
    S=[0]*N
    
    ans=1
    for i in range(N):
        c=C[i]
        temp=ans
        ans=(ans+S[c])%mod
        S[c]=(S[c]+temp)%mod
        
    print(ans)
        
        
        
        
    

main()

Submission status: Runtime Error

Solution code:
def main():
    MOD = 10**9 + 7
    N = int(input())
    C = [int(input()) for _ in range(N)]
    if N == 1:
        print(1)
        return
    # |---|
    # 1-2-1-2-2
    #   |---|
    latest_indices = [-1] * (2 * (10**5))
    next_indices = [-1] * N
    for cur_index, c in enumerate(C):
        latest_index = latest_indices[c]
        if latest_index >= 0:
            next_indices[latest_index] = cur_index
        latest_indices[c] = cur_index
    dp = [0] * N
    dp[0] = 1
    for cur_index in range(N - 1):
        next_index = next_indices[cur_index]
        if next_index >= 0 and next_index > cur_index + 1:
            dp[next_index] += dp[cur_index]
            dp[next_index] %= MOD
        dp[cur_index + 1] += dp[cur_index]
        dp[cur_index + 1] %= MOD
    print(dp[N - 1])


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def main():
    MOD = 10**9 + 7
    N = int(input())
    C = [int(input()) for _ in range(N)]
    if N == 1:
        print(1)
        return
    # |---|
    # 1-2-1-2-2
    #   |---|
    latest_indices = [-1] * N
    next_indices = [-1] * N
    for cur_index, c in enumerate(C):
        latest_index = latest_indices[c]
        if latest_index >= 0:
            next_indices[latest_index] = cur_index
        latest_indices[c] = cur_index
    dp = [0] * N
    dp[0] = 1
    for cur_index in range(N - 1):
        next_index = next_indices[cur_index]
        if next_index >= 0 and next_index > cur_index + 1:
            dp[next_index] += dp[cur_index]
            dp[next_index] %= MOD
        dp[cur_index + 1] += dp[cur_index]
        dp[cur_index + 1] %= MOD
    print(dp[N - 1])


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def main():
    MOD = 10**9 + 7
    N = int(input())
    C = [int(input()) for _ in range(N)]
    # |---|
    # 1-2-1-2-2
    #   |---|
    latest_indices = [-1] * N
    next_indices = [-1] * N
    for cur_index, c in enumerate(C):
        latest_index = latest_indices[c]
        if latest_index >= 0:
            next_indices[latest_index] = cur_index
        latest_indices[c] = cur_index
    dp = [0] * N
    dp[0] = 1
    for cur_index in range(N - 1):
        next_index = next_indices[cur_index]
        if next_index >= 0 and next_index > cur_index + 1:
            dp[next_index] += dp[cur_index]
            dp[next_index] %= MOD
        dp[cur_index + 1] += dp[cur_index]
        dp[cur_index + 1] %= MOD
    print(dp[N - 1])


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
import math
import collections
import bisect
import copy

# import numpy as np

sys.setrecursionlimit(10 ** 9)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(input())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))
na1 = lambda: list(map(lambda x: int(x) - 1, sys.stdin.readline().split()))


# ===CODE===


def main():
    n = ni()
    idxlist = [[] for _ in range(n)]
    d = []
    dp = [INF for _ in range(n + 1)]
    dp[0] = 1

    for i in range(n):
        di = ni()
        di -= 1
        if i > 0:
            if d[-1] == di:
                d.append(-1)
                continue
        d.append(di)
        idxlist[di].append(i)

    for i, di in enumerate(d):
        dp[i + 1] = dp[i]
        if di == -1:
            continue
        bidx = bisect.bisect_left(idxlist[di], i)
        if bidx - 1 >= 0:
            dp[i + 1] += dp[idxlist[di][bidx - 1] + 1]
            dp[i + 1] %= MOD

    print(dp[n])


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
import math
import collections
import bisect
import copy

# import numpy as np

sys.setrecursionlimit(10 ** 9)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))
na1 = lambda: list(map(lambda x: int(x) - 1, sys.stdin.readline().split()))


# ===CODE===


def main():
    n = ni()
    idxlist = [[] for _ in range(n)]
    d = []
    dp = [INF for _ in range(n + 1)]
    dp[0] = 1

    for i in range(n):
        di = ni()
        di -= 1
        if i > 0:
            if d[-1] == di:
                d.append(-1)
                continue
        d.append(di)
        idxlist[di].append(i)

    for i, di in enumerate(d):
        dp[i + 1] = dp[i]
        if di == -1:
            continue
        bidx = bisect.bisect_left(idxlist[di], i)
        if bidx - 1 >= 0:
            dp[i + 1] += dp[idxlist[di][bidx - 1] + 1]
            dp[i + 1] %= MOD

    print(dp[n])


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
import math
import collections
import bisect
import copy

# import numpy as np

sys.setrecursionlimit(10 ** 9)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))
na1 = lambda: list(map(lambda x: int(x) - 1, sys.stdin.readline().split()))


# ===CODE===


def main():
    n = ni()
    idxlist = [[] for _ in range(n)]
    d = []
    dp = [INF for _ in range(n + 1)]
    dp[0] = 1

    for i in range(n):
        tmp = ni()
        tmp -= 1
        if i > 0 and d[-1] == tmp:
            d.append(-1)
            continue
        d.append(tmp)
        idxlist[tmp].append(i)

    for i, di in enumerate(d):
        dp[i + 1] = dp[i]
        if di == -1:
            continue
        bidx = bisect.bisect_left(idxlist[di], i)
        if bidx - 1 >= 0:
            dp[i + 1] += dp[idxlist[di][bidx - 1] + 1]
            dp[i + 1] %= MOD

    print(dp[n])


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
import math
import collections
import bisect
import copy

# import numpy as np

sys.setrecursionlimit(10 ** 9)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))
na1 = lambda: list(map(lambda x: int(x) - 1, sys.stdin.readline().split()))


# ===CODE===


def main():
    n = ni()
    idxlist = [[] for _ in range(n)]
    d = []
    dp = [INF for _ in range(n + 1)]
    dp[0] = 1

    prev = -1
    for i in range(n):
        tmp = ni()
        tmp -= 1
        if tmp == prev:
            d.append(-1)
            continue
        d.append(tmp)
        idxlist[tmp].append(i)
        prev = tmp

    for i, di in enumerate(d):
        dp[i + 1] = dp[i]

        if di == -1:
            continue
        bidx = bisect.bisect_left(idxlist[di], i)
        if bidx - 1 >= 0:
            dp[i + 1] += dp[idxlist[di][bidx - 1] + 1]
            dp[i] %= MOD

    for i in range(n, -1, -1):
        if dp[i] != INF:
            print(dp[i])
            break


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
cs = [int(input()) for _ in range(n)]

from collections import defaultdict
prev = -1
c_comp = []
# 連続する色はまとめて良い
for c in cs:
    if prev != c:
        c_comp.append(c)
    prev = c

d = defaultdict(list)
for i,c in enumerate(c_comp):
    d[c].append(i)


dp = [0] * 110000
mod = 10**9 + 7

# 何個目まで見たか
inds = defaultdict(int)
ans = 0
dp[0] = 1
for i,c in enumerate(c_comp):
    i_prev = d[c][inds[c]-1]
    if inds[c] >= 1:
        # かぶっていないそれ以前の場合の数を足す
        dp[i+1] += dp[i] + dp[i_prev+1]
    else:
        # 前の色が無い or 異なる場合はなにもしない
        dp[i+1] = dp[i]
    dp[i+1] %= mod
    inds[c] += 1
print(dp[len(c_comp)])

Submission status: Runtime Error

Solution code:
n = int(input())
c = []
for _ in range(n):
    c.append(int(input()))

dp = [0] * n
dp[0] = 1

pre = [-1] * n
tmp = [-1] * n

for i in range(n):
    pre[i] = tmp[c[i]-1]
    tmp[c[i]-1] = i

for i in range(1,n):
    dp[i] = dp[i-1]
    if pre[i] != -1 and c[i] != c[i-1]:
        dp[i] += dp[pre[i]]

print(dp[-1])

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n = int(input())
    C = list(int(input()) for _ in range(n))

    dp = [0] * (n + 1)
    dp[0] = 1
    dp2 = [-1] * (n + 1)
    for i in range(n):
        c = C[i]
        if dp2[c] >= 0 and dp2[c] < i - 1:
            dp[i + 1] = dp[i] + dp[dp2[c] + 1]
        else:
            dp[i + 1] = dp[i]
        dp2[c] = i

    print(dp[-1])


if __name__ == '__main__':
    resolve()

Submission status: Runtime Error

Solution code:
n = int(input())
iro = [-1 for i in range(n+1)]
dp = [1 for i in range(n+1)]
mod = 10**9 + 7
for i in range(1,n+1):
    dp[i] = dp[i-1]
    now = int(input())
    if iro[now] != -1 and iro[now] != i-1:
        dp[i] += dp[iro[now]]
    iro[now] = i
    dp[i] %= mod
print(dp[-1])

Submission status: Runtime Error

Solution code:
n = int(input())
iro = [-1 for i in range(n+1)]
dp = [1 for i in range(n+1)]
mod = 10**9 + 7
for i in range(1,n+1):
    dp[i] = dp[i-1]
    now = int(input())
    if iro[now] == -1:
        iro[now] = i
    elif iro[now] != i-1:
        dp[i] += dp[iro[now]]
    iro[now] = i
    dp[i] %= mod
print(dp[-1])

Submission status: Runtime Error

Solution code:
n = int(input())
iro = [-1 for i in range(n+1)]
dp = [1 for i in range(n+1)]
mod = 10**9 + 7
for i in range(1,n+1):
    dp[i] = dp[i-1]
    now = int(input())
    if iro[now] == -1:
        iro[now] = i
    elif iro[now] != i-1:
        dp[i] += dp[iro[now]]
    iro[now] = i
    dp[i] %= mod
print(dp)

Submission status: Runtime Error

Solution code:
n = int(input())
iro = [-1 for i in range(n+1)]
dp = [1 for i in range(n+1)]
mod = 10**9 + 7
for i in range(1,n+1):
    dp[i] = dp[i-1]
    now = int(input())
    if iro[now] == -1:
        iro[now] = i
    elif iro[now] != i-1:
        dp[i] += dp[iro[now]]
        iro[now] = i
    dp[i] %= mod
print(dp[n])

Submission status: Runtime Error

Solution code:
n = int(input())
iro = [-1 for i in range(n+1)]
dp = [1 for i in range(n+1)]

for i in range(1,n+1):
    dp[i] = dp[i-1]
    now = int(input())
    if iro[now] == -1:
        iro[now] = i
    elif iro[now] != i-1:
        dp[i] += dp[iro[now]]
        iro[now] = i
print(dp[-1])

Submission status: Runtime Error

Solution code:
n = int(input())
c = [int(input()) for _ in range(n)]
v_c = []
for i,v in enumerate(c):
    if i > 0 and v == c[i-1]:
        continue
    v_c.append(v)

dp = [1]*(n+1)
color_cnt = [-1]*(2*10**5)
for i in range(len(v_c)-1, -1, -1):
    color = v_c[i]
    if color_cnt[color] > 0:
        # 増やす
        dp[i] = dp[i+1] + dp[color_cnt[color]]
    else:
        dp[i] = dp[i+1]
    color_cnt[color] = i
print(dp[0])

Submission status: Runtime Error

Solution code:
n = int(input())
c = [-1] + [int(input()) for i in range(n)]

count = [0]*(n+2)
dp = [0]*(n+1)
dp[0] = 1
mod = 10**9+7
#dp[i]: i番目までの場合の数
for i in range(n):
    dp[i+1] = dp[i]
    if c[i+1] != c[i]:
        dp[i+1] += count[c[i+1]]
        dp[i+1] %= mod
    count[c[i+1]] += dp[i]
    count[c[i+1]] %= mod

print(dp[n])

Submission status: Runtime Error

Solution code:
mod = 10 ** 9 + 7
import copy
cc = copy.deepcopy(c)
color_sum = {i: 0 for i in range(10 ** 6)}
dp = [1 for _ in range(n)]
color_sum[cc[0]] = 1
for i in range(1, n):
    dp[i] = dp[i - 1]
    if cc[i - 1] == cc[i]:
        continue
    dp[i] += color_sum[cc[i]]
    dp[i] %= mod
    color_sum[c[i]] += dp[i]
    color_sum[c[i]] %= mod
print(dp[n - 1])

Submission status: Runtime Error

Solution code:
mod = 10 ** 9 + 7

import copy
cc = copy.deepcopy(c)
color_sum = {i: 0 for i in range(10 ** 6)}
dp = [1 for _ in range(n + 1)]
color_sum[cc[0]] = 1
for i in range(2, n + 1):
    dp[i] = dp[i - 1]
    if cc[i - 2] == cc[i - 1]:
        continue
    dp[i] += color_sum[cc[i - 1]]
    dp[i] %= mod
    color_sum[c[i - 1]] += dp[i - 1]
    color_sum[c[i - 1]] %= mod
print(dp[n])

Submission status: Runtime Error

Solution code:
N = int(input())
C = [int(input()) for _ in range(N)]
MOD = 10**9 + 7

if N <= 2:
    print(1)
    exit()

dp = [1,1]
last_idx = [-1]*(N+2)
last_idx[C[0]] = 0
last_idx[C[1]] = 1

for i in range(2, N):
    if C[i-1] == C[i] or last_idx[C[i]] == -1:
        dp.append(dp[-1] % MOD)
    else:
        dp.append((dp[-1] + dp[last_idx[C[i]]]) % MOD)
    last_idx[C[i]] = i

print(dp[-1])

Submission status: Runtime Error

Solution code:
N = int(input())
C = [int(input()) for _ in range(N)]
MOD = 10**9 + 7

if N <= 2:
    print(1)
    exit()

dp = [1,1]
last_idx = [-1]*(N+1)
last_idx[C[0]] = 0
last_idx[C[1]] = 1

for i in range(2, N):
    if C[i-1] == C[i] or last_idx[C[i]] == -1:
        dp.append(dp[-1] % MOD)
    else:
        dp.append((dp[-1] + dp[last_idx[C[i]]]) % MOD)
    last_idx[C[i]] = i

print(dp[-1])

Submission status: Runtime Error

Solution code:
N = int(input())
C = [int(input()) for _ in range(N)]
MOD = 10**9 + 7

dp = [1,1]
last_idx = [-1]*(N+10)
last_idx[C[0]] = 0
last_idx[C[1]] = 1

for i in range(2, N):
    if C[i-1] == C[i] or last_idx[C[i]] == -1:
        dp.append(dp[-1] % MOD)
    else:
        dp.append((dp[-1] + dp[last_idx[C[i]]]) % MOD)
    last_idx[C[i]] = i

print(dp[-1])

Submission status: Runtime Error

Solution code:
N = int(input())
C = [int(input()) for _ in range(N)]
MOD = 10**9 + 7

dp = [1,1]
last_idx = [-1]*(N+1)
last_idx[C[0]] = 0
last_idx[C[1]] = 1

for i in range(2, N):
    if C[i-1] == C[i] or last_idx[C[i]] == -1:
        dp.append(dp[-1] % MOD)
    else:
        dp.append((dp[-1] + dp[last_idx[C[i]]]) % MOD)
    last_idx[C[i]] = i

print(dp[-1])

Submission status: Runtime Error

Solution code:
N = int(input())
C = [int(input()) for _ in range(N)]

dp = [1,1]
last_idx = [-1]*(N+1)
last_idx[C[0]] = 0
last_idx[C[1]] = 1

for i in range(2, N):
    if C[i-1] == C[i] or last_idx[C[i]] == -1:
        dp.append(dp[-1])
    else:
        dp.append(dp[-1] + dp[last_idx[C[i]]])
    last_idx[C[i]] = i

print(dp[-1])

Submission status: Runtime Error

Solution code:
import sys
import numpy as np
from collections import defaultdict

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


def main():
    N = int(input())
    C = [int(input()) for _ in range(N)] + [None]
    C = [C[i] for i in range(N) if C[i] != C[i + 1]]

    colors = defaultdict(list)
    for i, c in enumerate(C):
        colors[c].append(i)

    N = len(C)
    # dp[i] := i個までの色の塗り方の総和
    dp = [0] * (N + 1)
    dp[0] = 1
    for i in range(N):
        # i個目を塗らない
        dp[i + 1] += dp[i]
        dp[i + 1] %= MOD
        for j in colors[C[i]]:
            if j <= i:
                continue

            # ぬる
            dp[j + 1] += dp[i]
            dp[j + 1] %= MOD

    print(dp[-1])


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
from collections import Counter
def main():
    n=int(input())
    mod=10**9+7
    C=[int(input())for _ in range(n)]
    places=[[] for _ in range(n)]
    for i in range(n):
        places[C[i]].append(i)
    dp=[0]*(n+1)
    dp[0]=1
    for i in range(1,n+1):
        dp[i]=(dp[i]+dp[i-1])%mod
        color=C[i-1]
        it=places[color].index(i-1)
        if it>0:
            j=places[color][it-1]
            if i-1-j>1:
                dp[i]=(dp[i]+dp[j+1])%mod
    print(dp[-1])


if __name__=='__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**18
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()

    N = NI()
    A = [0 for _ in range(N+1)]
    S = [1 for _ in range(N+1)]
    C = [NI() for _ in range(N)]
    P = 1
    A[C[0]] = 1
    for i in range(1,N):
        if C[i] != C[i-1] and A[C[i]] > 0:
            S[C[i]] = S[C[i]] + P
        else:
            S[C[i]] = P
        A[C[i]] = 1
        P = S[C[i]]
    print(P)




if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
MOD = 10**9 + 7

N = int(input())
C = [int(input()) for _ in range(N)]

dp = [0]*(N+1)
lis = [-1] * (2 * 10**5 + 1)
dp[0] = 1
lis[C[0]] = 0
for i,c in enumerate(C[1:],1):
    prev_i = c_to_i[c]
    dp[i] = dp[i-1]
    if prev_i != i-1:
        dp[i] += dp[prev_i]
        dp[i] %= MOD
    lis[c] = i

answer = dp[N-1]
print(answer)

Submission status: Runtime Error

Solution code:
from collections import defaultdict
from bisect import *
def solve():
  mod = 10**9+7
    d = defaultdict(lambda: [])
    N = int(input())
    for i in range(N):
        a = int(input())
        d[a].append(i)
    selist = []
    for l in d.values():
        for i in range(len(l)-1):
            if l[i+1]-1>l[i]:
                selist.append([l[i],l[i+1]-1])
    start_sort = sorted(selist)
    e_ind = {}
    for i,(s,e) in enumerate(start_sort):
        e_ind[e] = i
    ends = list(e_ind.keys())
    ends.sort()
    dp = [0]*(len(selist)+1)
    for i in range(1,len(selist)+1):
        dp[i] = dp[i-1]+1
        ind = bisect_left(ends,selist[i-1][0])
        if ind>0:
            j = e_ind[ends[ind-1]]
            dp[i] += dp[j+1]
            dp[i] %= mod
    ans = dp[-1]+1
    ans %= mod
    return ans
print(solve())