Submission #1872705


Source Code Expand

Copy
#include <bits/stdc++.h>
typedef long long int ll;
#define FOR(i, a, b) for (ll i = (signed)(a); i < (b); ++i)
#define REP(i, n) FOR(i, 0, n)
#define EREP(i, n) for (int i = (n)-1; i >= 0; --i)
#define MOD 1000000007
#define pb push_back
#define INF 93193111451418101
#define MIN -93193111451418101
#define EPS 1e-11
#define tp(a, b, c) make_tuple(a, b, c)
#define lb(a, b) lower_bound((a).begin(), (a).end(), (b))
#define ub(a, b) upper_bound((a).begin(), (a).end(), (b))
using namespace std;
typedef pair<ll, ll> P;
typedef tuple<ll, ll, ll> T;
template <typename T> void fill_all(T &arr, const T &v) { arr = v; }
template <typename T, typename ARR> void fill_all(ARR &arr, const T &v) {
  for (auto &i : arr) {
    fill_all(i, v);
  }
}
//------------------変数-----------------------//
ll n, m, f[114514];
ll flag[114514];
//-------------------関数----------------------//
ll dp[114514];
int main() {
  cin >> n >> m;
  REP(i, n) { cin >> f[i]; }
  ll itr = 0, sum = 1;
  dp[0] = 1;
  REP(i, n) {
    flag[f[i]]++;
    while (flag[f[i]] > 1) {
      flag[f[itr]]--;
      sum -= dp[itr++]; //もう使えないやつを引いている

      if (sum < 0)
        sum += MOD;
      sum %= MOD;
    }
    dp[i + 1] = sum % MOD; // dpに保存
    sum *= 2;
    sum %= MOD; //分けるか、含めるか
  }

  cout << dp[n] << endl;
}

Submission Info

Submission Time
Task D - サプリメント
User keidaroo
Language C++14 (GCC 5.4.1)
Score 100
Code Size 1390 Byte
Status
Exec Time 31 ms
Memory 2560 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 subtask0-sample01.txt, subtask0-sample02.txt
Subtask1 30 / 30 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 70 / 70 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 1 ms 256 KB
subtask0-sample02.txt 1 ms 256 KB
subtask1-01.txt 2 ms 256 KB
subtask1-02.txt 2 ms 384 KB
subtask1-03.txt 2 ms 256 KB
subtask1-04.txt 2 ms 384 KB
subtask1-05.txt 2 ms 256 KB
subtask1-06.txt 2 ms 256 KB
subtask1-07.txt 2 ms 384 KB
subtask1-08.txt 2 ms 384 KB
subtask1-09.txt 2 ms 384 KB
subtask1-10.txt 2 ms 384 KB
subtask1-11.txt 2 ms 384 KB
subtask1-12.txt 2 ms 384 KB
subtask1-13.txt 2 ms 384 KB
subtask1-14.txt 2 ms 384 KB
subtask1-15.txt 2 ms 384 KB
subtask1-16.txt 2 ms 384 KB
subtask1-17.txt 2 ms 384 KB
subtask1-18.txt 2 ms 384 KB
subtask1-19.txt 2 ms 384 KB
subtask1-20.txt 2 ms 384 KB
subtask2-01.txt 6 ms 640 KB
subtask2-02.txt 11 ms 1024 KB
subtask2-03.txt 19 ms 1920 KB
subtask2-04.txt 26 ms 2176 KB
subtask2-05.txt 19 ms 1792 KB
subtask2-06.txt 18 ms 1792 KB
subtask2-07.txt 18 ms 1792 KB
subtask2-08.txt 25 ms 1792 KB
subtask2-09.txt 27 ms 1792 KB
subtask2-10.txt 31 ms 2560 KB
subtask2-11.txt 30 ms 1792 KB
subtask2-12.txt 31 ms 2560 KB
subtask2-13.txt 30 ms 2560 KB
subtask2-14.txt 27 ms 2560 KB
subtask2-15.txt 30 ms 2560 KB
subtask2-16.txt 23 ms 1792 KB
subtask2-17.txt 31 ms 2560 KB
subtask2-18.txt 30 ms 2560 KB
subtask2-19.txt 27 ms 2560 KB
subtask2-20.txt 30 ms 2560 KB