Submission #3900718


Source Code Expand

#include<bits/stdc++.h>
#define MAX_N 100001
#define INF_INT 2147483647
#define INF_LL 9223372036854775807
#define REP(i,n) for(int i=0;i<(int)(n);i++)
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> P;
ll bpow(ll,ll,ll);
const ll MOD = 1000000007;

ll dp[200001] = {0};
int main()
{
  ll N,M,f[200002],res=0,n=0,tr=1,back[200002],lo[200002],sum[200002]={0};
  cin >> N >> M;
  REP(i,N)cin >> f[i+1];
  REP(i,N+1){
    dp[i] = 0;
    back[i] = 0;
    lo[i] = 0;
    sum[i] = 0;
  }
  REP(i,N){
    back[i+1] = lo[f[i+1]];
    lo[f[i+1]] = i+1;
  }
  dp[0] = 1;
  sum[0] = 1;
  int ind=0;
  for(int i=0;i<N;i++){
    if(ind < back[i+1]){
      ind = back[i+1];
    }
    dp[i+1] = (MOD+sum[i] - (ind == 0 ? 0 : sum[ind-1]))%MOD;
    sum[i+1] = (sum[i] + dp[i+1])%MOD;
 
  }
  cout << dp[N] << endl;
  return 0;
}

Submission Info

Submission Time
Task D - サプリメント
User makss
Language C++14 (GCC 5.4.1)
Score 100
Code Size 874 Byte
Status AC
Exec Time 33 ms
Memory 7296 KB

Judge Result

Set Name Sample Subtask1 Subtask2
Score / Max Score 0 / 0 30 / 30 70 / 70
Status
AC × 2
AC × 22
AC × 42
Set Name Test Cases
Sample subtask0-sample01.txt, subtask0-sample02.txt
Subtask1 subtask0-sample01.txt, subtask0-sample02.txt, subtask1-01.txt, subtask1-02.txt, subtask1-03.txt, subtask1-04.txt, subtask1-05.txt, subtask1-06.txt, subtask1-07.txt, subtask1-08.txt, subtask1-09.txt, subtask1-10.txt, subtask1-11.txt, subtask1-12.txt, subtask1-13.txt, subtask1-14.txt, subtask1-15.txt, subtask1-16.txt, subtask1-17.txt, subtask1-18.txt, subtask1-19.txt, subtask1-20.txt
Subtask2 subtask0-sample01.txt, subtask0-sample02.txt, subtask1-01.txt, subtask1-02.txt, subtask1-03.txt, subtask1-04.txt, subtask1-05.txt, subtask1-06.txt, subtask1-07.txt, subtask1-08.txt, subtask1-09.txt, subtask1-10.txt, subtask1-11.txt, subtask1-12.txt, subtask1-13.txt, subtask1-14.txt, subtask1-15.txt, subtask1-16.txt, subtask1-17.txt, subtask1-18.txt, subtask1-19.txt, subtask1-20.txt, subtask2-01.txt, subtask2-02.txt, subtask2-03.txt, subtask2-04.txt, subtask2-05.txt, subtask2-06.txt, subtask2-07.txt, subtask2-08.txt, subtask2-09.txt, subtask2-10.txt, subtask2-11.txt, subtask2-12.txt, subtask2-13.txt, subtask2-14.txt, subtask2-15.txt, subtask2-16.txt, subtask2-17.txt, subtask2-18.txt, subtask2-19.txt, subtask2-20.txt
Case Name Status Exec Time Memory
subtask0-sample01.txt AC 3 ms 5632 KB
subtask0-sample02.txt AC 2 ms 4736 KB
subtask1-01.txt AC 3 ms 4736 KB
subtask1-02.txt AC 3 ms 4992 KB
subtask1-03.txt AC 3 ms 5888 KB
subtask1-04.txt AC 4 ms 5888 KB
subtask1-05.txt AC 3 ms 4992 KB
subtask1-06.txt AC 3 ms 4736 KB
subtask1-07.txt AC 4 ms 5632 KB
subtask1-08.txt AC 4 ms 6016 KB
subtask1-09.txt AC 4 ms 4992 KB
subtask1-10.txt AC 4 ms 5888 KB
subtask1-11.txt AC 3 ms 5120 KB
subtask1-12.txt AC 4 ms 6016 KB
subtask1-13.txt AC 4 ms 5248 KB
subtask1-14.txt AC 4 ms 4736 KB
subtask1-15.txt AC 4 ms 4608 KB
subtask1-16.txt AC 4 ms 4992 KB
subtask1-17.txt AC 4 ms 4992 KB
subtask1-18.txt AC 4 ms 5888 KB
subtask1-19.txt AC 4 ms 4736 KB
subtask1-20.txt AC 3 ms 4608 KB
subtask2-01.txt AC 8 ms 4992 KB
subtask2-02.txt AC 13 ms 6528 KB
subtask2-03.txt AC 20 ms 6144 KB
subtask2-04.txt AC 26 ms 7040 KB
subtask2-05.txt AC 20 ms 6784 KB
subtask2-06.txt AC 20 ms 7040 KB
subtask2-07.txt AC 20 ms 6912 KB
subtask2-08.txt AC 27 ms 7296 KB
subtask2-09.txt AC 29 ms 7296 KB
subtask2-10.txt AC 32 ms 7296 KB
subtask2-11.txt AC 33 ms 7168 KB
subtask2-12.txt AC 32 ms 7296 KB
subtask2-13.txt AC 32 ms 7296 KB
subtask2-14.txt AC 28 ms 7168 KB
subtask2-15.txt AC 32 ms 7296 KB
subtask2-16.txt AC 26 ms 7168 KB
subtask2-17.txt AC 32 ms 7168 KB
subtask2-18.txt AC 32 ms 6528 KB
subtask2-19.txt AC 28 ms 7296 KB
subtask2-20.txt AC 32 ms 6528 KB