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 2017-12-15 23:11:18+0900 D - サプリメント keidaroo C++14 (GCC 5.4.1) 100 1390 Byte AC 31 ms 2560 KB

Test Cases

Set Name Score / Max Score Test Cases
Case Name Status Exec Time Memory