Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #include <random>
- using namespace std;
- typedef unsigned long long ull;
- typedef long long ll;
- typedef long double ld;
- #define int ll
- //#define int __int128
- //#define ll __int128
- typedef pair<int, int> pii;
- typedef pair<ll, ll> pll;
- typedef vector<int> vi;
- typedef vector< vi > vvi;
- typedef vector< vvi > vvvi;
- typedef vector<short> vs;
- typedef vector<vs> vvs;
- typedef vector<vvs> vvvs;
- typedef vector<ll> vl;
- typedef vector<vl> vvl;
- typedef vector<vvl> vvvl;
- typedef vector<ld> vld;
- typedef vector<vld> vvld;
- typedef vector<vvld> vvvld;
- typedef vector<string> vst;
- typedef vector<vst> vvst;
- typedef pair<ld, ld> pld;
- typedef complex<double> base;
- #define inmin(a, b) a = min(a, (b))
- #define inmax(a, b) a = max(a, (b))
- #define ALL(a) a.begin(),a.end()
- #define RALL(a) a.rbegin(),a.rend()
- #define sqr(x) ((x) * (x))
- #define fori(i, n) for(int i = 0; i < int(n); ++i)
- #define SZ(a) ((int)((a).size()))
- #define triple(T) tuple<T, T, T>
- #define quad(T) tuple<T, T, T, T>
- #define watch(x) cerr << (#x) << " = " << (x) << endl;
- #ifdef MAX_HOME
- #define cerr cout
- #else
- #define cerr if (false) cerr
- #endif
- const double PI = 2 * acos(0.0);
- #define rand shittttty_shit
- mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
- mt19937_64 rng_64(chrono::steady_clock::now().time_since_epoch().count());
- const string DIGITS = "0123456789";
- const string ALPH = "abcdefghijklmnopqrstuvwxyz";
- template <class T0, class T1>
- inline ostream & operator << (ostream &out, pair<T0, T1> &a) {
- return out << "{" << a.first << ", " << a.second << "}";
- }
- template <class T0, class T1, class T2>
- inline ostream & operator << (ostream &out, tuple<T0, T1, T2> &a) {
- return out << "{" << get<0>(a) << ", " << get<1>(a) << ", " << get<2>(a) << "}";
- }
- template <class T0, class T1, class T2, class T3>
- inline ostream & operator << (ostream &out, tuple<T0, T1, T2, T3> &a) {
- return out << "{" << get<0>(a) << ", " << get<1>(a) << ", " << get<2>(a) << ", " << get<3>(a) << "}";
- }
- template<class T>
- inline ostream & operator << (ostream &out, vector<T> &a) {
- out << "[";
- fori (i, a.size())
- out << a[i] << vector<string>{", ", "] "}[i + 1 == a.size()];
- return out;
- }
- void smain();
- signed main() {
- ios::sync_with_stdio(0);
- cin.tie(0); cout.tie(0);
- #ifdef MAX_HOME
- freopen("input.txt", "r", stdin);
- clock_t start = clock();
- #endif
- cout << setprecision(12) << fixed;
- smain();
- #ifdef MAX_HOME
- cout << "\n\n\n\nTOTAL EXECUTION TIME: " << float( clock () - start ) / CLOCKS_PER_SEC << endl;
- #endif
- return 0;
- }
- const int M = 1e9 + 7;
- #ifdef MAX_HOME
- const int N = 10000;
- #else
- const int N = 3e5 + 100;
- #endif
- struct SegTree {
- pii t[N << 2];
- void build(int v, int tl, int tr) {
- if (tl == tr) {
- t[v] = {0, 0};
- return;
- }
- int tm = tl + tr >> 1;
- build(v << 1, tl, tm);
- build(v << 1 | 1, tm + 1, tr);
- t[v] = {0, 0};
- }
- pii chose(pii a, pii b) {
- if (a.first < b.first) return a;
- if (b.first < a.first) return b;
- return {a.first, (a.second + b.second) % M};
- }
- int pushing[N << 2];
- void push(int v) {
- if (pushing[v]) {
- pushing[v << 1] += pushing[v];
- pushing[v << 1 | 1] += pushing[v];
- t[v << 1].first += pushing[v];
- t[v << 1 | 1].first += pushing[v];
- pushing[v] = 0;
- }
- }
- void upd(int v, int tl, int tr, int pos, int new_dp) {
- if (tl == tr) {
- t[v].second = new_dp;
- return;
- }
- int tm = tl + tr >> 1;
- push(v);
- if (pos <= tm) upd(v << 1, tl, tm, pos, new_dp);
- else upd(v << 1 | 1, tm + 1, tr, pos, new_dp);
- t[v] = chose(t[v << 1], t[v << 1 | 1]);
- }
- void inc(int v, int tl, int tr, int l, int r, int val) {
- if (l > r) return;
- if (tl == l && tr == r) {
- t[v].first += val;
- pushing[v] += val;
- return;
- }
- int tm = tl + tr >> 1;
- push(v);
- inc(v << 1, tl, tm, l, min(r, tm), val);
- inc(v << 1 | 1, tm + 1, tr, max(l, tm + 1), r, val);
- t[v] = chose(t[v << 1], t[v << 1 | 1]);
- }
- };
- int solve(vi a) {
- int n = a.size();
- vi lst(n + 1, -1);
- vi dp;
- dp.resize(n + 1, 0);
- vector<bool> dead(n + 1, false);
- vi smaller(n + 1, -1);
- vi bigger(n + 1, -1);
- vi parent(n + 1, -1);
- vi sz(n + 1, 0);
- vi rf(n + 1);
- auto make_set = [&] (int v) -> void {
- parent[v] = v;
- sz[v] = 1;
- rf[v] = v;
- };
- function<int(int)> find_set;
- find_set = [&] (int v) -> int {
- return v == parent[v] ? v : find_set(parent[v]);
- };
- auto union_sets = [&] (int u, int v) -> void {
- u = find_set(u);
- v = find_set(v);
- if (u == v) return;
- if (sz[u] < sz[v]) swap(u, v);
- parent[v] = u;
- sz[u] += sz[v];
- inmax(rf[u], rf[v]);
- };
- SegTree tree;
- tree.build(1, 0, n);
- auto add_arc = [&] (int l, int r) -> void {
- tree.inc(1, 0, n, lst[l] + 1, lst[r], 1);
- smaller[r] = l;
- bigger[l] = r;
- };
- auto kill = [&](int v) -> void {
- dead[v] = true;
- make_set(v);
- if (v && dead[v - 1]) union_sets(v, v - 1);
- if (dead[v + 1]) union_sets(v, v + 1);
- int st = find_set(v);
- tree.upd(1, 0, n, v, 0);
- dp[rf[st]] = (dp[rf[st]] + (v ? dp[v - 1] : 1)) % M;
- tree.upd(1, 0, n, rf[st] + 1, dp[rf[st]]);
- };
- auto remove_arc = [&](int l, int r) -> void {
- tree.inc(1, 0, n, lst[l] + 1, lst[r], -1);
- smaller[r] = -1;
- bigger[l] = -1;
- };
- auto remove_arcs = [&](int x) -> void {
- if (smaller[x] != -1) remove_arc(smaller[x], x);
- if (bigger[x] != -1) remove_arc(x, bigger[x]);
- };
- tree.upd(1, 0, n, 0, 1);
- fori (i, n) {
- remove_arcs(a[i]);
- int prev = lst[a[i]];
- lst[a[i]] = i;
- if (a[i] != 1)
- add_arc(a[i] - 1, a[i]);
- if (prev != -1) kill(prev);
- pii cur = tree.t[1];
- if (cur.first == 0) {
- dp[i] = cur.second;
- }
- tree.upd(1, 0, n, i + 1, dp[i]);
- // cerr << "dp[" << i << "] = " << dp[i] << endl;
- }
- return dp[n - 1];
- }
- int naive(vi a) {
- int n = a.size();
- vi dp(n + 1, 0);
- dp[0] = 1;
- for (int i = 1; i <= n; ++i) {
- for (int j = 1; j <= i; ++j) {
- int mx = -1;
- for (int k = j; k <= i; ++k) inmax(mx, a[k - 1]);
- vector<bool> used(mx + 1, false);
- for (int k = j; k <= i; ++k) {
- used[a[k - 1]] = true;
- }
- if (accumulate(ALL(used), 0) == mx) {
- dp[i] = (dp[i] + dp[j - 1]) % M;
- }
- }
- // cerr << "dp[" << i - 1 << "] = " << dp[i] << endl;
- }
- return dp[n];
- }
- void stress() {
- int cnt = -1;
- while (true) {
- if (++cnt % 20 == 0) watch(cnt);
- int n = rng() % 3 + 1;
- vi a(n);
- for (int i = 0; i < n; ++i) {
- a[i] = 1 + rng() % n;
- }
- int sl = solve(a);
- int nv = naive(a);
- if (sl != nv) {
- cout << a.size() << '\n';
- for (auto x : a) cout << x << ' ';
- cout << endl;
- watch(sl);
- watch(nv);
- watch(cnt);
- return;
- }
- }
- }
- void smain() {
- // stress();
- int n;
- cin >> n;
- vi a(n);
- fori (i, n) cin >> a[i];
- cout << solve(a) << '\n';
- // watch(naive(a));
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement