SHARE
TWEET

Untitled

a guest Jul 19th, 2019 65 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. #include <random>
  3.  
  4. using namespace std;
  5.  
  6. typedef unsigned long long ull;
  7. typedef long long ll;
  8. typedef long double ld;
  9. #define int ll
  10. //#define int __int128
  11. //#define ll __int128
  12. typedef pair<int, int> pii;
  13. typedef pair<ll, ll> pll;
  14. typedef vector<int> vi;
  15. typedef vector< vi > vvi;
  16. typedef vector< vvi > vvvi;
  17. typedef vector<short> vs;
  18. typedef vector<vs> vvs;
  19. typedef vector<vvs> vvvs;
  20. typedef vector<ll> vl;
  21. typedef vector<vl> vvl;
  22. typedef vector<vvl> vvvl;
  23. typedef vector<ld> vld;
  24. typedef vector<vld> vvld;
  25. typedef vector<vvld> vvvld;
  26. typedef vector<string> vst;
  27. typedef vector<vst> vvst;
  28. typedef pair<ld, ld> pld;
  29. typedef complex<double> base;
  30.  
  31. #define inmin(a, b) a = min(a, (b))
  32. #define inmax(a, b) a = max(a, (b))
  33. #define ALL(a) a.begin(),a.end()
  34. #define RALL(a) a.rbegin(),a.rend()
  35. #define sqr(x) ((x) * (x))
  36. #define fori(i, n) for(int i = 0; i < int(n); ++i)
  37. #define SZ(a) ((int)((a).size()))
  38. #define triple(T) tuple<T, T, T>
  39. #define quad(T) tuple<T, T, T, T>
  40. #define watch(x) cerr << (#x) << " = " << (x) << endl;
  41.  
  42. #ifdef MAX_HOME
  43. #define cerr cout
  44. #else
  45. #define cerr if (false) cerr
  46. #endif
  47.  
  48. const double PI = 2 * acos(0.0);
  49. #define rand shittttty_shit
  50. mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
  51. mt19937_64 rng_64(chrono::steady_clock::now().time_since_epoch().count());
  52.  
  53. const string DIGITS = "0123456789";
  54. const string ALPH = "abcdefghijklmnopqrstuvwxyz";
  55.  
  56. template <class T0, class T1>
  57. inline ostream & operator << (ostream &out, pair<T0, T1> &a) {
  58.     return out << "{" << a.first << ", " << a.second << "}";
  59. }
  60.  
  61. template <class T0, class T1, class T2>
  62. inline ostream & operator << (ostream &out, tuple<T0, T1, T2> &a) {
  63.     return out << "{" << get<0>(a) << ", " << get<1>(a) << ", " << get<2>(a) << "}";
  64. }
  65.  
  66. template <class T0, class T1, class T2, class T3>
  67. inline ostream & operator << (ostream &out, tuple<T0, T1, T2, T3> &a) {
  68.     return out << "{" << get<0>(a) << ", " << get<1>(a) << ", " << get<2>(a) << ", " <<  get<3>(a) << "}";
  69. }
  70.  
  71. template<class T>
  72. inline ostream & operator << (ostream &out, vector<T> &a) {
  73.     out << "[";
  74.     fori (i, a.size())
  75.         out << a[i] << vector<string>{", ", "]  "}[i + 1 == a.size()];
  76.     return out;
  77. }
  78.  
  79.  
  80.  
  81. void smain();
  82.  
  83. signed main() {
  84.     ios::sync_with_stdio(0);
  85.     cin.tie(0); cout.tie(0);
  86.  
  87. #ifdef MAX_HOME
  88.     freopen("input.txt", "r", stdin);
  89.     clock_t start = clock();
  90. #endif
  91.     cout << setprecision(12) << fixed;
  92.     smain();
  93. #ifdef MAX_HOME
  94.     cout << "\n\n\n\nTOTAL EXECUTION TIME: " << float( clock () - start ) /  CLOCKS_PER_SEC << endl;
  95. #endif
  96.     return 0;
  97. }
  98.  
  99. const int M = 1e9 + 7;
  100.  
  101. #ifdef MAX_HOME
  102. const int N = 10000;
  103. #else
  104. const int N = 3e5 + 100;
  105. #endif
  106.  
  107. struct SegTree {
  108.     pii t[N << 2];
  109.  
  110.     void build(int v, int tl, int tr) {
  111.         if (tl == tr) {
  112.             t[v] = {0, 0};
  113.             return;
  114.         }
  115.         int tm = tl + tr >> 1;
  116.         build(v << 1, tl, tm);
  117.         build(v << 1 | 1, tm + 1, tr);
  118.         t[v] = {0, 0};
  119.     }
  120.  
  121.     pii chose(pii a, pii b) {
  122.         if (a.first < b.first) return a;
  123.         if (b.first < a.first) return b;
  124.         return {a.first, (a.second + b.second) % M};
  125.     }
  126.  
  127.     int pushing[N << 2];
  128.  
  129.     void push(int v) {
  130.         if (pushing[v]) {
  131.             pushing[v << 1] += pushing[v];
  132.             pushing[v << 1 | 1] += pushing[v];
  133.             t[v << 1].first += pushing[v];
  134.             t[v << 1 | 1].first += pushing[v];
  135.             pushing[v] = 0;
  136.         }
  137.     }
  138.     void upd(int v, int tl, int tr, int pos, int new_dp) {
  139.         if (tl == tr) {
  140.             t[v].second = new_dp;
  141.             return;
  142.         }
  143.         int tm = tl + tr >> 1;
  144.         push(v);
  145.         if (pos <= tm) upd(v << 1, tl, tm, pos, new_dp);
  146.         else upd(v << 1 | 1, tm + 1, tr, pos, new_dp);
  147.         t[v] = chose(t[v << 1], t[v << 1 | 1]);
  148.     }
  149.  
  150.  
  151.  
  152.     void inc(int v, int tl, int tr, int l, int r, int val) {
  153.         if (l > r) return;
  154.         if (tl == l && tr == r) {
  155.             t[v].first += val;
  156.             pushing[v] += val;
  157.             return;
  158.         }
  159.         int tm = tl + tr >> 1;
  160.         push(v);
  161.         inc(v << 1, tl, tm, l, min(r, tm), val);
  162.         inc(v << 1 | 1, tm + 1, tr, max(l, tm + 1), r, val);
  163.         t[v] = chose(t[v << 1], t[v << 1 | 1]);
  164.     }
  165.  
  166. };
  167.  
  168.  
  169. int solve(vi a) {
  170.     int n = a.size();
  171.     vi  lst(n + 1, -1);
  172.     vi dp;
  173.     dp.resize(n + 1, 0);
  174.     vector<bool> dead(n + 1, false);
  175.     vi smaller(n + 1, -1);
  176.     vi bigger(n + 1, -1);
  177.     vi parent(n + 1, -1);
  178.     vi sz(n + 1, 0);
  179.     vi rf(n + 1);
  180.  
  181.     auto make_set = [&] (int v) -> void {
  182.         parent[v] = v;
  183.         sz[v] = 1;
  184.         rf[v] = v;
  185.     };
  186.  
  187.     function<int(int)> find_set;
  188.  
  189.     find_set = [&] (int v) -> int {
  190.         return v == parent[v] ? v : find_set(parent[v]);
  191.     };
  192.  
  193.     auto union_sets = [&] (int u, int v) -> void {
  194.         u = find_set(u);
  195.         v = find_set(v);
  196.         if (u == v) return;
  197.         if (sz[u] < sz[v]) swap(u, v);
  198.         parent[v] = u;
  199.         sz[u] += sz[v];
  200.         inmax(rf[u], rf[v]);
  201.     };
  202.  
  203.     SegTree tree;
  204.  
  205.     tree.build(1, 0, n);
  206.  
  207.     auto add_arc = [&] (int l, int r) -> void {
  208.         tree.inc(1, 0, n, lst[l] + 1, lst[r], 1);
  209.         smaller[r] = l;
  210.         bigger[l] = r;
  211.     };
  212.  
  213.  
  214.     auto kill = [&](int v) -> void {
  215.         dead[v] = true;
  216.         make_set(v);
  217.         if (v && dead[v - 1]) union_sets(v, v - 1);
  218.         if (dead[v + 1]) union_sets(v, v + 1);
  219.         int st = find_set(v);
  220.         tree.upd(1, 0, n, v, 0);
  221.         dp[rf[st]] = (dp[rf[st]] + (v ? dp[v - 1] : 1)) % M;
  222.         tree.upd(1, 0, n, rf[st] + 1, dp[rf[st]]);
  223.     };
  224.  
  225.     auto remove_arc = [&](int l, int r) -> void {
  226.         tree.inc(1, 0, n, lst[l] + 1, lst[r], -1);
  227.         smaller[r] = -1;
  228.         bigger[l] = -1;
  229.     };
  230.  
  231.     auto remove_arcs = [&](int x) -> void {
  232.         if (smaller[x] != -1) remove_arc(smaller[x], x);
  233.         if (bigger[x] != -1) remove_arc(x, bigger[x]);
  234.     };
  235.     tree.upd(1, 0, n, 0, 1);
  236.     fori (i, n) {
  237.         remove_arcs(a[i]);
  238.         int prev = lst[a[i]];
  239.         lst[a[i]] = i;
  240.         if (a[i] != 1)
  241.             add_arc(a[i] - 1, a[i]);
  242.         if (prev != -1) kill(prev);
  243.  
  244.         pii cur = tree.t[1];
  245.         if (cur.first == 0) {
  246.             dp[i] = cur.second;
  247.         }
  248.         tree.upd(1, 0, n, i + 1, dp[i]);
  249. //        cerr << "dp[" << i << "] = " << dp[i] << endl;
  250.     }
  251.     return dp[n - 1];
  252. }
  253.  
  254. int naive(vi a) {
  255.     int n = a.size();
  256.     vi dp(n + 1, 0);
  257.     dp[0] = 1;
  258.     for (int i = 1; i <= n; ++i) {
  259.         for (int j = 1; j <= i; ++j) {
  260.             int mx = -1;
  261.             for (int k = j; k <= i; ++k) inmax(mx, a[k - 1]);
  262.             vector<bool> used(mx + 1, false);
  263.             for (int k = j; k <= i; ++k) {
  264.                 used[a[k - 1]] = true;
  265.             }
  266.             if (accumulate(ALL(used), 0) == mx) {
  267.                 dp[i] = (dp[i] + dp[j - 1]) % M;
  268.             }
  269.         }
  270. //        cerr << "dp[" << i - 1 << "] = " << dp[i] << endl;
  271.     }
  272.     return dp[n];
  273. }
  274.  
  275. void stress() {
  276.     int cnt = -1;
  277.     while (true) {
  278.         if (++cnt % 20 == 0) watch(cnt);
  279.         int n = rng() % 3 + 1;
  280.         vi a(n);
  281.         for (int i = 0; i < n; ++i) {
  282.             a[i] = 1 + rng() % n;
  283.         }
  284.         int sl = solve(a);
  285.         int nv = naive(a);
  286.         if (sl != nv) {
  287.             cout << a.size() << '\n';
  288.             for (auto x : a) cout << x << ' ';
  289.             cout << endl;
  290.             watch(sl);
  291.             watch(nv);
  292.             watch(cnt);
  293.             return;
  294.         }
  295.     }
  296. }
  297.  
  298. void smain() {
  299.  
  300. //    stress();
  301.  
  302.     int n;
  303.     cin >> n;
  304.     vi a(n);
  305.     fori (i, n) cin >> a[i];
  306.     cout << solve(a) << '\n';
  307. //    watch(naive(a));
  308.  
  309.  
  310. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top