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: Wrong Answer

Solution code:
import sys
from bisect import bisect_right as br
input = sys.stdin.readline
N = int(input())
mod = 10 ** 9 + 7
res = 0
a = []
for _ in range(N): a.append(int(input()))
t = 0
table = [[] for _ in range(max(a) + 1)]
for i in range(N):
  if a[i] != t:
    t = a[i]
    table[a[i]].append(i)
dp = [0] * N
dp[0] = 1
#print(table)
#print(a)
for i in range(N):
  j = br(table[a[i]], i)
  if j < len(table[a[i]]):
    dp[table[a[i]][j]] += dp[i]
    dp[table[a[i]][j]] %= mod
    """
    for k in range(j, len(table[a[i]])):
      print(i, table[a[i]][k])
      dp[table[a[i]][k]] += dp[i]
      dp[table[a[i]][k]] %= mod
    """
  if i + 1 < N:
    dp[i + 1] += dp[i]
    dp[i + 1] %= mod
print(dp[-1])

Submission status: Wrong Answer

Solution code:
import sys
from bisect import bisect_right as br
input = sys.stdin.readline
N = int(input())
table = [[] for _ in range(2 * pow(10, 5) + 1)]
a = []
t = 0
mod = 10 ** 9 + 7
for i in range(N):
  x = int(input())
  if t != x:
    table[x].append(i)
    t = x
  a.append(x)
#print(table)
dp = [0] * N
dp[0] = 1
for i in range(N):
  j = br(table[a[i]], i)
  if j < len(table[a[i]]):
    dp[table[a[i]][j]] += dp[i]
    dp[table[a[i]][j]] %= mod
  if i + 1 < N: 
    dp[i + 1] += dp[i]
    dp[i + 1] %= mod
  #print(dp)
print(dp[-1])

Submission status: Wrong Answer

Solution code:
n=int(input())
cc=[int(input()) for _ in range(n)]
c=[cc[0]]
for i in range(1,n):
    if cc[i]!=c[-1]:
        c.append(cc[i])
n=len(c)
mod=10**9+7
dp=[0]*(n+1)
sm=[0]*(max(c)+1)
dp[0]=1
for i in range(n):
    x=c[i]
    dp[i+1]+=sm[x]+dp[i]
    sm[x]+=dp[i]
print(dp[n])

Submission status: Wrong Answer

Solution code:
def examB(mod):
    N = I(); C = [I() for _ in range(N)]
    dp = [0]*(N); dp[0] = 1
    cur = [0]*(max(C)+1); cur[C[0]] =1
    for i in range(1,N):
        if C[i]==C[i-1]:
            dp[i] = dp[i-1]
        else:
            dp[i] = cur[C[i]] + dp[i-1]
            cur[C[i]] = dp[i]
#    print(dp)
    ans = dp[-1]
    print(ans)

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

if __name__ == '__main__':
    examB(mod)

Submission status: Wrong Answer

Solution code:
n, *cs = map(int, open(0))
fwd = [0] * n
d = {}
for i, c in enumerate(cs[::-1], start=1):
	f = d.get(c, 0)
	if f:
		fwd[n - i] = f
	d[c] = n - i
dp = [0] * (n + 1)
dp[0] = 1
for i in range(1, n + 1):
	dp[i] = dp[i - 1] + dp[i]
    #隣だったら無視
	if fwd[i - 1] > i:
		dp[fwd[i - 1] + 1] += dp[i]
print(dp[-1])

Submission status: Wrong Answer

Solution code:
# dp
import sys
from collections import defaultdict

stdin = sys.stdin
 
ni = lambda:int(ns())
na = lambda:list(map(int,stdin.readline().split()))
ns = lambda:stdin.readline().rstrip()  # ignore trailing spaces

d = dict()

N = ni()
C = [ni() for _ in range(N)]
dp = [1] * N
d[C[0]] = 0

for i in range(1, N):
    c = C[i]
    dp[i] = dp[i-1]
    if c in d:
        if d[c] != i-1:
            dp[i] += dp[d[c]]
    d[c] = i

print(dp[N-1])

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")

def main():
    n = int(input())
    cc = [int(input()) for _ in range(n)]
    dp = [0] * (n + 1)
    dp[0] = 1
    ll = defaultdict(list)
    pc = -1
    for r, c in enumerate(cc):
        dp[r + 1] = dp[r]
        if c == pc: continue
        for l in ll[c]:
            if l == r - 1: continue
            dp[r + 1] += dp[l]
        ll[c].append(r)
        pc = c
    print(dp[n])

main()

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
n=int(input())
c=[int(input()) for _ in range(n)]
g=[[]for _ in range(2*(10**5)+1)]



for i in range(n):
    g[c[i]].append(i)

ans=1
for i in range(len(g)):
    if not g[i]:
        continue
    new=[]
    now=g[i][0]
    cnt=1
    m=1
    for j in range(1,len(g[i])):
        m+=1
        if now+1==g[i][j]:
            cnt+=1
            now+=1
        else:
            now=g[i][j]
            new.append(cnt)
            cnt=1
    new.append(cnt)
    ans2=m*(m-1)//2
    for k in new:
        ans2-=k*(k-1)//2
    ans+=ans2

print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
arr=[int(input()) for _ in range(n)]
tmp=[arr[0]]
for i in range(1,n):
  if arr[i]!=tmp[-1]:
    tmp.append(arr[i])
n=len(tmp)
arr=tmp
dp=[0]*n
dp[0]=1
g=[[] for _ in range(max(arr)+1)]
for i in range(n):
  g[arr[i]].append(i)
cnt=[0]*(max(arr)+1)
lim=[0]*(max(arr)+1)
for i in range(max(arr)+1):
  lim[i]=len(g[i])
for i in range(n-1):
  dp[i+1]+=dp[i]
  if cnt[arr[i]]+1<lim[arr[i]]:
    dp[g[arr[i]][cnt[arr[i]]+1]]+=dp[i]
    cnt[arr[i]]+=1
print(dp[-1])

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

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

d = defaultdict(int)

ans=0
for i,c in enumerate(C):
    if i>=1 and C[i-1]==C[i]:
        continue
    else:
        ans+=d[c]
        d[c]=ans
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
N = int(input())
dp = [0]*(N+1)
dp[0] = 1
dic = defaultdict(int)
p = -1
for i in range(N):
  c = int(input())
  if c==p:
    dp[i+1] = dp[i]
    continue
  dic[c] += dp[i]
  dp[i+1] = dic[c]
  p = c
#  print(dp)

print(dp[-1])

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
N = int(input())
dp = [0]*N
dic = defaultdict(int)
p = -1
for i in range(N):
  c = int(input())
  if c==p:
    dp[i] = dp[i-1]
    continue
  dic[c] += dp[i-1] if i>0 else 1
  dp[i] += dic[c]
  p = c
#  print(dp)

print(dp[-1])

Submission status: Wrong Answer

Solution code:
N = int(input())
MOD = 10**9+7
P2 = [1]
for i in range(N):
  P2 += [(P2[-1]*2)%MOD]
pre = [-1]*(2*(10**5)+1)
p = -1
end = 0
ans = 1
for i in range(N):
  c = int(input())
  if pre[c]!=-1:
    if p==c:
      continue
    ans += P2[pre[c]]
    pre[c] += 1
    end += 1
  else:
    pre[c] = end
  p = c
print(ans%MOD)

Submission status: Wrong Answer

Solution code:
N = int(input())
MOD = 10**9+7
P2 = [1]
for i in range(N):
  P2 += [(P2[-1]*2)%MOD]
pre = [-1]*(2*(10**5)+1)
p = -1
end = 0
ans = 1
for i in range(N):
  c = int(input())
  if pre[c]!=-1:
    if p==c:
      continue
    ans += P2[pre[c]]
    end += 1
    pre[c] = end
  else:
    pre[c] = end
  p = c
print(ans%MOD)

Submission status: Wrong Answer

Solution code:
N = int(input())
C = dict()
i, cp, r = 0, 0, ['x'] * N
for _ in range(N):
    c = int(input())
    if c != cp:
        if c in C.keys():
            r[C[c]] = i
        C[c], cp = i, c
        i += 1
length = i
hist, add, l, temp, ans = [0] * length, [0] * length, 0, 0, 0
for l in range(length):
    temp += add[l]
    hist[l] = temp
    if r[l] != 'x':
        add[r[l]] += temp + 1
        ans += temp + 1
#print((ans+1) % (10**9+7))

Submission status: Wrong Answer

Solution code:
N = int(input())
C = dict()
i, cp, lr = 0, 0, dict()
for _ in range(N):
    c = int(input())
    if c != cp:
        if c in C.keys():
            if C[c] in lr.keys():
                lr[C[c]] = [i]
        C[c], cp = i, c
        i += 1
length = i
hist, add, i, ans = [0] * length, [0] * length, 0, 0
for l in list(lr.keys()):
    for r in lr[l]:
        while i <= l:
            hist[i] = hist[i-1] + add[i]
            i += 1
        add[r] += hist[l] + 1
        ans += hist[l] + 1
print((ans+1) % (10**9+7))

Submission status: Wrong Answer

Solution code:
N = int(input())
C = dict()
i, cp, lr = 0, 0, dict()
for _ in range(N):
    c = int(input())
    if c != cp:
        if c in C.keys():
            if C[c] in lr.keys():
                lr[C[c]].append(i)
            else:
                lr[C[c]] = [i]
        C[c], cp = i, c
        i += 1
length = i
hist, add, i, ans = [0] * length, [0] * length, 0, 0
for l in list(lr.keys()):
    for r in lr[l]:
        while i <= l:
            hist[i] = hist[i-1] + add[i]
            i += 1
        add[r] += hist[l] + 1
        ans += hist[l] + 1
print((ans+1) % (10**9+7))

Submission status: Wrong Answer

Solution code:
N = int(input())
C = dict()
i, cp, lr = 0, 0, dict()
for _ in range(N):
    c = int(input())
    if c != cp:
        if c in C.keys():
            if C[c] in lr.keys():
                lr[C[c]].append(i)
            else:
                lr[C[c]] = [i]
        C[c], cp = i, c
        i += 1
length = i
hist, add, i, ans = [0] * length, [0] * length, 0, 0
for l in lr.keys():
    for r in lr[l]:
        while i <= l:
            hist[i] = hist[i-1] + add[i]
            ans += add[i]
            i += 1
        add[r] += hist[l] + 1
if len(lr) != 0:
    for i in range(l+1, length):
        ans += add[i]
print((ans+1) % (10**9+7))

Submission status: Wrong Answer

Solution code:
N=int(input())
C=[int(input()) for i in range(N)]
a=[0]*N
p={}
for i,c in enumerate(C):
    a[i]=a[i-1]
    if c in p and p[c]<i-1:
        a[i]+=a[p[c]]+1
    p[c]=i
print(a[-1]+1)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = []
ans = []
c = {}
for i in range(n):
    a.append(int(input()))
    ans.append(0)
ans[0] = 1
c[a[0]] = 0
for i in range(1,n):
    if a[i] not in c:
        c[a[i]] = i
    if a[i] == a[i-1]:
        ans[i] = ans[i-1]
    else:
        ans[i] = ans[i-1] + ans[c[a[i]]]
        c[a[i]] = i
print(ans[i])

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
n=int(input())
c=[]
tmp=0
num=0
for i in range(n):
    m=int(input())
    if m!=tmp:
        c.append(m)
        tmp=m
        num+=1
n=num
from collections import Counter
dp=Counter()
ans=1
for i in range(n):
    dp[c[i]]+=ans
    ans=dp[c[i]]
print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
L=[]
for i in range(N):
    n=int(input())
    L.append(n)

dp=[0 for i in range(N)]
dp[0]=1
D=dict()
D[L[0]]=1
for i in range(1,N):
    if L[i]==L[i-1]:
        dp[i]=dp[i-1]
    elif L[i] not in D:
        D[L[i]]=dp[i-1]
        dp[i]=dp[i-1]
    else:
        dp[i]=dp[i-1]+D[L[i]]
        D[L[i]]=dp[i]
    #print(dp)
print(dp[-1])
#print(D)

Submission status: Wrong Answer

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

dp = [0] * N
dp[0] = 1
d = {C[0]:0}

for i in range(1, N):
    if C[i] in d and C[i] != C[i-1]:
        dp[i] = dp[i-1] + dp[d[C[i]]]
    else:
        dp[i] = dp[i-1]
    d[C[i]] = i

print(dp[-1])

Submission status: Wrong Answer

Solution code:
n=int(input())
col={}
memo=0
for i in range(n):
    c=int(input())
    if c==memo:continue
    memo=c
    if c not in col:
        col[c]=1
    else:
        col[c]+=1
ans=1
for i in col.values():
    ans+=i*(i-1)//2
print(ans)

Submission status: Wrong Answer

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

N=int(input())
L=[]
for i in range(N):
    n=int(input())
    L.append(n)
    
dp=[0 for i in range(N)]
dp[0]=1
D=dict()
D[L[0]]=1
for i in range(1,N):
    if L[i] not in D:
        D[L[i]]=1
        dp[i]=dp[i-1]
    else:
        if L[i]==L[i-1]:
            dp[i]=dp[i-1]
        else:
            dp[i]=dp[i-1]+D[L[i]]
            D[L[i]]+=1
print(dp[-1])

Submission status: Wrong Answer

Solution code:
n = int(input())
l = [int(input()) for _ in range(n)] + [0]
p = [0]
for i in range(n):
  if l[i] != l[i+1]:
    p.append(l[i])
lp = len(p)
l = [0]*lp
l[0] = 1
d = dict()
for x in p:
  d[x] = 0
for i in range(1,lp):
  d[p[i]] += l[i-1]
  l[i] += d[p[i]]
print(l[-1])

Submission status: Wrong Answer

Solution code:
n = int(input())
l = [int(input()) for _ in range(n)] + [0]
p = [0]
for i in range(n):
  if l[i] != l[i+1]:
    p.append(l[i])
lp = len(p)
l = [0]*lp
l[0] = 1
d = dict()
for x in p:
  d[x] = 0
for i in range(1,lp):
  d[p[i]] += l[i-1]
  l[i] = d[p[i]]
print(l[-1])

Submission status: Wrong Answer

Solution code:
n = int(input())
l = [int(input()) for _ in range(n)] + [0]
p = [0]
for i in range(n):
  if l[i] != l[i+1]:
    p.append(l[i])
lp = len(p)
l = [0]*lp
l[0] = 1
d = dict()
for i in range(1,lp):
  l[i] = l[i-1] + d.get(p[i],0)
  d[p[i]] = d.get(p[i],0) + l[i-1]
print(l[-1])

Submission status: Wrong Answer

Solution code:
n = int(input())
l = [int(input()) for _ in range(n)] + [0]
p = [0]
for i in range(n):
  if l[i] != l[i+1]:
    p.append(l[i])
lp = len(p)
l = [0]*lp
l[0] = 1
d = dict()
for i in range(1,lp):
  l[i] = l[i-1]
  if p[i] in d:
    l[i] += l[d[p[i]]]
  d[p[i]] = i
print(l[-1])

Submission status: Wrong Answer

Solution code:
N=int(input())
d = {}
pairs=[-1]*N

for i in range(N):
    c = int(input())
    if c in d and i-d[c]>1:
        pairs[d[c]] = i
    d[c]=i
    
dp1,dp2=[0]*N,[0]*N
prev=1
for src in range(N):
    dst = pairs[src]
    dp2[src]=prev+dp1[src]
    prev=dp2[src]
    if dst>0:
        dp1[dst] += dp2[src]
print(dp2[-1])

Submission status: Wrong Answer

Solution code:
N=int(input())
d = {}
pairs=[-1]*N

for i in range(N):
    c = int(input())
    if c in d and i-d[c]>1:
        pairs[d[c]] = i
    d[c]=i
    
dp1,dp2=[0]*(N+1),[0]*(N+1)
dp2[0]=1

for src in range(N):
    dst = pairs[src]
    if dst>0:
        dp1[dst] += dp2[src]
    dp2[src+1]+=(dp2[src]+dp1[src+1])

print(dp2[-1])

Submission status: Wrong Answer

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

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

dp = [0]*(N+1)
c_to_i = [-1]*(2*10**5+1)
dp[0] = 1
c_to_i[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]
    c_to_i[c] = i

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

Submission status: Wrong Answer

Solution code:
n = int(input())
cs = []
for i in range(n):
    cs.append(int(input()))
dp = [0] * n
last_num = [-1] * 2 * 10**5

for i, c in enumerate(cs):
    if i == 0:
        dp[i] = 1
        last_num[c-1] += 1
        continue
    # Fisrt color
    if(last_num[c-1] == -1):
        dp[i] += dp[i-1]
    # Previous color
    elif(last_num[c-1] == i-1):
        dp[i] += dp[i-1]
    # Reversi
    else:
        dp[i] += dp[i-1]
        dp[i] += dp[last_num[c-1]]
    last_num[c-1] = i
print(dp[n-1])

Submission status: Wrong Answer

Solution code:
size=int(input())
number_list=[]
for i in range(0,size):
    number_list.append(int(input()))

count=1
for i in range(0,size):
    for j in range(i+1,size):
        if(number_list[j]==number_list[i]and i+1!=j):
            count+=1
print(count)

Submission status: Wrong Answer

Solution code:
# input
n = int(input())

mod = pow(10, 9) + 7
c = []
dp = [0] * (n + 1)
stone_history = dict()
for i in range(n):
    stone = int(input())
    if len(c) == 0:
        dp[i + 1] = 1
    else:
        if stone in stone_history and c[-1] is not stone:
            dp[i + 1] = dp[i] + stone_history[stone]
        else:
            dp[i + 1] = dp[i]

    stone_history[stone] = dp[i + 1]
    c.append(stone)

print(dp[-1] % mod)

Submission status: Wrong Answer

Solution code:
# input
n = int(input())

c = []
dp = [0] * (n + 1)
stone_history = dict()
for i in range(n):
    stone = int(input())
    if len(c) == 0:
        dp[i + 1] = 1
    else:
        if stone in stone_history and c[-1] is not stone:
            dp[i + 1] = dp[i] + stone_history[stone]
        else:
            dp[i + 1] = dp[i]

    stone_history[stone] = dp[i + 1]
    c.append(stone)

print(dp[-1])

Submission status: Wrong Answer

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

from itertools import groupby
x = [0] + [k for k, g in groupby(C)]

dp = [0]*(len(x)) # i個目までで何通りあるか
dp[0] = 1
memo = {}

for i in range(1, len(x)):
    c = x[i]
    dp[i] = dp[i-1] + memo.setdefault(c, 0)
    memo[c] += dp[i-1]

print(dp[-1])

Submission status: Wrong Answer

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

from itertools import groupby
x = [0] + [k for k, g in groupby(C)]

dp = [0]*(len(x)) # i個目までで何通りあるか
dp[0] = 1
memo = {}

for i in range(1, len(x)):
    c = x[i]
    dp[i] = dp[i-1] + memo.get(c, 0)
    memo[c] = dp[i-1]

print(dp[-1])

Submission status: Wrong Answer

Solution code:
N=int(input())
MOD=10**9+7
memo={}

#prev_numがその時点での組み合わせ数
prev_num=1
prev=None

for _ in range(N):
  c=int(input())
  if c==prev:
    continue
  tmp=prev_num
  if c in memo:
    tmp+=memo[c]
  #memo[c]にそれまでの組み合わせの数が入ることで、
  #次にcが出てきた時にどれぐらい通りが増えるかが分かる
  memo[c]=tmp
  prev_num=tmp
  prev=c
print(prev_num)

Submission status: Wrong Answer

Solution code:
N=int(input())
C=[int(input()) for _ in range(N)]
mod = int(1e9+7)

memo={}
new_C=[]

pre = 1.5
i=0
for c in C:
    if c!= pre:
        new_C.append(c)
        memo.setdefault(c,[]).append(i)
        i+=1
    pre=c

answer = [0]*len(new_C)
answer[0] = 1

c_i = {c:None for c in set(C)}
c_i[new_C[0]]=0

for i in range(1, len(new_C)):
    c = new_C[i]
    if c_i[c] is None:
        answer[i] = answer[i-1]
        c_i[c] = 0
    else:
        answer[i] = answer[i-1] + answer[memo[c][c_i[c]]]
        c_i[c] +=1

print(answer[-1])

Submission status: Wrong Answer

Solution code:
N=int(input())
C=[int(input()) for _ in range(N)]
mod = int(1e9+7)

cnt = 1
for i in range(N-1):
    if C[i] != C[i+1]:
        cnt+=1

def fibonatti(n):
    _l = [1]*n
    for i in range(n-2):
        _l[i+2] = (_l[i+1] + _l[i])%mod
    return _l[-1]

print(fibonatti(cnt))

Submission status: Wrong Answer

Solution code:
N=int(input())
C=[int(input()) for _ in range(N)]
cnt = 1
for i in range(N-1):
    if C[i] != C[i+1]:
        cnt+=1


def fibonatti(n):
    _l = [1]*n
    for i in range(n-2):
        _l[i+2] = _l[i+1] + _l[i]
    return _l[-1]

print(fibonatti(cnt))

Submission status: Wrong Answer

Solution code:
MOD=10**9+7

N=int(input())
a=[int(input()) for i in range(N)]
last={}
tmp={}

ans=1
x=a[0]
last[x]=0
tmp[x]=1

for i in range(1,N):
    x=a[i]
    last.setdefault(x,i)
    tmp.setdefault(x,0)
    if last[x]!=i-1: ans+=tmp[x]
    last[x]=i
    tmp[x]=ans%MOD
    ans%MOD
    
print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
a=[int(input()) for i in range(N)]
last={}
tmp={}

ans=1
x=a[0]
last[x]=0
tmp[x]=1

for i in range(1,N):
    x=a[i]
    last.setdefault(x,-2)
    tmp.setdefault(x,0)
    if last[x]!=i-1: ans+=tmp[x]
    last[x]=i
    tmp[x]=ans

print(ans)

Submission status: Wrong Answer

Solution code:
# /usr/bin/python
# -*- coding: utf-8 -*-
#
import sys


n = int(input())
c = [0] * n
for i in range(n):
  c[i] = int(input())

dct = {c[0]:0}
dp = [1] * n
for i in range(1,n):
  if c[i] == c[i-1] or c[i] not in dct:
    dp[i] = dp[i-1]
  else:
    dp[i] = dp[i-1] + dp[dct[c[i]]]
  dct[c[i]] = i
print(dp[-1])

Submission status: Wrong Answer

Solution code:
n = int(input())

dp = [1 for i in range(0,n+1)]
c = list()
c.append(-1)
d = {}
for i in range(1,n+1):
    c.append(int(input()))

for i in range(1,n+1):
    if c[i] in d:
        j = d[c[i]]
        d[c[i]] = i
        if c[i-1] != c[i] == c[j] != c[j-1]:
            dp[i] = dp[i-1]+dp[j]
            continue
    else:
        d[c[i]] = i
    dp[i] = dp[i-1]
print(dp[-1])

Submission status: Wrong Answer

Solution code:
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from collections import Counter, defaultdict

def compress(c: list) -> list:
    pre = 0
    ret = []
    for ci in c:
        if ci != pre:
            ret.append(ci)
            
        pre = ci
        
    return ret

def rem_alone(c: list) -> list:
    cnt = Counter(c)
    aln = set()
    for k, v in cnt.items():
        if v == 1:
            aln.add(k)
        
    ret = []
    for ci in c:
        if ci in aln:
            continue
        
        ret.append(ci)
        
    return ret

def find_prev_idx(c: list) -> dict:
    idx = defaultdict(list)
    prev = defaultdict(int)
    for i, ci in enumerate(c):
        prev[i] = idx[ci][-1] if len(idx[ci]) > 0 else -1
        idx[ci].append(i)

    
    return prev
 
n = ni()
c = [ni() for _ in range(n)]
mod = 10**9+7

c = rem_alone(compress(c))

prev = find_prev_idx(c)

dp = [0]*(len(c)+1)
dp[0] = 1
for i in range(1, len(c)+1):
    dp[i] = dp[i-1] if prev[i-1] == -1 else dp[i-1] + dp[prev[i]+1]
    dp[i] %= mod

    
print(dp[len(c)])

Submission status: Wrong Answer

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

MOD = 1000000007  # type: int

def solve(N, C):
    last = [-1] * (N + 1)
    pairs = []
    for i, c in enumerate(C):
        try:
            prev = last[c - 1]
        except:
            if c > N:
                return
            else:
                raise Exception()
        if prev >= 0 and prev < i - 1:
            pairs.append((prev, i))
        last[c - 1] = i
    print(0)
    return
    pairs.sort()
    count = [0] * N
    count[0] = 1
    idx = 0
    for i in range(N):
        if i > 0:
            count[i] += count[i - 1]
            count[i] %= MOD
        while idx < len(pairs) and pairs[idx][0] == i:
            count[pairs[idx][1]] += count[i]
            count[pairs[idx][1]] %= MOD
            idx += 1
    print(count[N - 1])
    return


# Generated by 1.1.3 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    C = [ int(next(tokens)) for _ in range(N) ]  # type: "List[int]"
    solve(N, C)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

MOD = 1000000007  # type: int

def solve(N, C):
    last = [-1] * (N + 1)
    pairs = []
    for i, c in enumerate(C):
        try:
            prev = last[c - 1]
        except:
            if c >= N:
                return
            else:
                raise Exception()
        if prev >= 0 and prev < i - 1:
            pairs.append((prev, i))
        last[c - 1] = i
    print(0)
    return
    pairs.sort()
    count = [0] * N
    count[0] = 1
    idx = 0
    for i in range(N):
        if i > 0:
            count[i] += count[i - 1]
            count[i] %= MOD
        while idx < len(pairs) and pairs[idx][0] == i:
            count[pairs[idx][1]] += count[i]
            count[pairs[idx][1]] %= MOD
            idx += 1
    print(count[N - 1])
    return


# Generated by 1.1.3 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    C = [ int(next(tokens)) for _ in range(N) ]  # type: "List[int]"
    solve(N, C)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

MOD = 1000000007  # type: int

def solve(N, C):
    last = [-1] * (N + 1)
    pairs = []
    for i, c in enumerate(C):
        try:
            prev = last[c - 1]
        except:
            return
        if prev >= 0 and prev < i - 1:
            pairs.append((prev, i))
        last[c - 1] = i
    print(0)
    return
    pairs.sort()
    count = [0] * N
    count[0] = 1
    idx = 0
    for i in range(N):
        if i > 0:
            count[i] += count[i - 1]
            count[i] %= MOD
        while idx < len(pairs) and pairs[idx][0] == i:
            count[pairs[idx][1]] += count[i]
            count[pairs[idx][1]] %= MOD
            idx += 1
    print(count[N - 1])
    return


# Generated by 1.1.3 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    C = [ int(next(tokens)) for _ in range(N) ]  # type: "List[int]"
    solve(N, C)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

N = int(input())
c = []
for _ in range(N):
    c.append(int(input()))

dp = [0] * N
dp[0] = 1
dpc = [0] * (max(c) + 1)
dpc[c[0]] = 1

for i in range(1, N):
    dp[i] = dp[i - 1]
    if c[i] != c[i - 1]:
        dp[i] += dpc[c[i]]
        dpc[c[i]] += dp[i - 1]

print(dp[N - 1])

Submission status: Wrong Answer

Solution code:
N=int(input())
l=[]
l_value=[]
i=0
stack=-1
for i in range(N):
    if i < N:
        l.append(input())
list_simple=[]
for i in l:
    if stack != i:
        list_simple.append(i)
    stack = i
dp_dict=[0]*200001
dp=1
for i in list_simple:
    i=int(i)
    dp = dp_dict[i] +dp
    dp_dict[i] = dp
print(dp)

Submission status: Wrong Answer

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

dp = [0] * N
dp[0] = 1

for i in range(1, N):
    dp[i] = dp[i - 1]
    if c[i] == c[i - 1]:
        continue
    for j in range(i):
        if c[i] == c[j] and c[j] != c[j + 1]:
            dp[i] += 1

print(dp[N - 1])

Submission status: Wrong Answer

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

CDict = {}
for i, C in enumerate(CList):
    if i == 0 or CList[i - 1] != C:
        if C in CDict:
            CDict[C] += 1
        else:
            CDict[C] = 1

ans = 1
for C in CDict:
    ans *= CDict[C]

ans -= 1

print(ans)

Submission status: Wrong Answer

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

for i in range(1,n+1):
  c[i]=int(input())
  for j in range(1,i-1):
    if c[i]==c[i-1]:
      continue
    if c[j]==c[i] and c[j-1]!=c[j]:
      res+=1
      res%=(10^9+7)
print(res)

Submission status: Wrong Answer

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

N = int(readline())
MOD = 10**9 + 7
last = [-1]*(3*10**5)
dp = [0]*(N+1)
dp[0] = 1
for i in range(1, N+1):
    c = int(readline())
    if last[c] != -1 and last[c]+1 < i:
        dp[i] = dp[last[c]] + dp[i-1]
    else:
        dp[i] = dp[i-1]
    last[c] = i
print(dp[N])

Submission status: Wrong Answer

Solution code:
import sys
n=int(input())
c=[int(i) for i in sys.stdin]
#連続した数を除去したlist
d=[]
#前の数を保存する変数
stack=0
for i in c:
  if i!=stack:
    d.append(i)
  stack=i
#0で初期化
x=[0]*200001
sum=1
p=10**9+7
for i in range(1,len(d)):
  x[d[i]]= (x[d[i]]+sum)%p
  sum=x[d[i]]%p
print(sum)

Submission status: Wrong Answer

Solution code:
import sys
n=int(input())
c=[int(i) for i in sys.stdin]
#連続した数を除去したlist
d=[]
#前の数を保存する変数
stack=0
for i in c:
  if i!=stack:
    d.append(i)
  stack=i
#0で初期化
x=[0]*200001
sum=1
for i in range(1,len(d)):
  x[d[i]]+= sum
  sum=x[d[i]]
print(sum)

Submission status: Wrong Answer

Solution code:
import sys
c=[int(i) for i in sys.stdin]
#連続した数を除去したlist
d=[]
#前の数を保存する変数
stack=0
for i in c:
  if i!=stack:
    d.append(i)
  stack=i
#0で初期化
x=[0]*200001
sum=1
for i in range(1,len(d)):
  x[d[i]]+= sum
  sum=x[d[i]]
print(sum)

Submission status: Wrong Answer

Solution code:
N=int(input())
o_list=[]
for i in range(N):
    o_list.append(int(input()))

def reversi(o_list):
    p_list = []
    p_list.append(o_list)
    n_list = list(set(o_list))
    if len(n_list)==1:
            return [1]
    for num in n_list:
        num_indexes=[i for i, x in enumerate(o_list) if x == num]
        for i in range(len(num_indexes)-1):
            if num_indexes[i]+1 < num_indexes[i+1]:                
                tmp_list =o_list.copy()
                change_list = [num]*(num_indexes[i+1]-num_indexes[i]+1)
                tmp_list[num_indexes[i]:num_indexes[i+1]+1]=change_list
                p_list.append(tmp_list)
                p_list+=reversi(tmp_list)
    return (p_list)
rev_list=reversi(o_list)
rev_list = [l for l in rev_list if l!=1]
len(set(tuple(row) for row in rev_list))

Submission status: Wrong Answer

Solution code:
def reversi(o_list):
    p_list = []
    p_list.append(o_list)
    n_list = list(set(o_list))
    if len(n_list)==1:
            return [1]
    for num in n_list:
        num_indexes=[i for i, x in enumerate(o_list) if x == num]
        for i in range(len(num_indexes)-1):
            if num_indexes[i]+1 < num_indexes[i+1]:                
                tmp_list =o_list.copy()
                change_list = [num]*(num_indexes[i+1]-num_indexes[i]+1)
                tmp_list[num_indexes[i]:num_indexes[i+1]+1]=change_list
                p_list.append(tmp_list)
                p_list+=reversi(tmp_list)
    return (p_list)
rev_list=reversi([4,2,5,4,2,4])
rev_list = [l for l in rev_list if l!=1]
len(set(tuple(row) for row in rev_list))

Submission status: Wrong Answer

Solution code:
n = int(input())
c = [int(input()) for i in range(n)]
num,x = 1,[0]*(200001)
c.append(0)
x[c[0]]+=1
for i in range(1,n):
    x[c[i]] = (x[c[i]]+num)%(10**9+7)
    if c[i]-c[i+1]: num = x[c[i]]
    else: num = 0
print(num)

Submission status: Wrong Answer

Solution code:
N = int(input())
pre_stone = 0
div = 10**9+7
dp = 1
dp_dict = {}
for _ in range(N):
    c = int(input())
    if pre_stone != c:
        pre_stone = c
        if c not in dp_dict:
            dp_dict[c] = 0
        dp += dp_dict[c]
        dp_dict[c] = dp

print(dp)

Submission status: Wrong Answer

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

ret = 0
l_store = []
l_store.append(l)
for n in set(l):
    indexes = [i for i, x in enumerate(l) if x == n]
    if len(indexes) < 2:
        continue
#    print(indexes)
    for i in range(len(indexes)-1):
      	for j in range(i+1, len(indexes)):
#            print(i, j)
            lidx = indexes[i]
            ridx = indexes[j]
            val = l[lidx]
            tmp_l = l[::]
            for k in range(lidx, ridx):
                tmp_l[k] = val
            if tmp_l not in l_store:
                l_store.append(tmp_l)
#print(l_store)
print(len(l_store))