SHARE
TWEET

Untitled

lalalalalalalaalalla Nov 13th, 2019 81 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <vector>
  3. #include <string>
  4. #include <iomanip>
  5. #include <queue>
  6. #include <cmath>
  7. #include <algorithm>
  8. #include <tuple>
  9. #include <iomanip>
  10. #include <stdio.h>
  11. #include <numeric>
  12. #include <map>
  13. #include <bitset>
  14. #include <set>
  15. #include <stack>
  16. #include <queue>
  17. #include <unordered_set>
  18. #include <cassert>
  19.  
  20.  
  21. //#pragma GCC optimize("Ofast,no-stack-protector")
  22. //#pragma GCC optimize("O3")
  23. //#pragma GCC target("avx2")
  24. //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,tune=native")
  25. //#pragma GCC optimize("unroll-loops")
  26. //#pragma GCC optimize("fast-math")
  27. //#pragma GCC optimize("section-anchors")
  28. //#pragma GCC optimize("profile-values,profile-reorder-functions,tracer")
  29. //#pragma GCC optimize("vpt")
  30. //#pragma GCC optimize("rename-registers")
  31. //#pragma GCC optimize("move-loop-invariants")
  32. //#pragma GCC optimize("unswitch-loops")
  33. //#pragma GCC optimize("function-sections")
  34. //#pragma GCC optimize("data-sections")
  35. //#pragma GCC optimize("branch-target-load-optimize")
  36. //#pragma GCC optimize("branch-target-load-optimize2")
  37. //#pragma GCC optimize("btr-bb-exclusive")
  38. //#pragma GCC optimize("O0")
  39.  
  40.  
  41. #define int long long
  42. #define ll long long
  43. #define ull unsigned long long
  44. #define all(a) a.begin(), a.end()
  45. #define pii pair<int, int>
  46. #define pb push_back
  47. #define ld long double
  48.  
  49.  
  50. using namespace std;
  51.  
  52. //const int INF = 1e13;
  53. //const int mod = 2600000069;
  54. //const int p = 179;
  55.  
  56. const int mod = 1000000007;
  57.  
  58. struct node {
  59.     int max, sum;
  60.     node() {
  61.         max = 1;
  62.         sum = 0;
  63.     }
  64.     node(int max_ , int sum_) {
  65.         max = max_;
  66.         sum = sum_;
  67.     }
  68. };
  69.  
  70. int n;
  71. vector<node> t;
  72.  
  73. node merge(node a, node b) {
  74.     node c;
  75.     if (a.max > b.max) c = a;
  76.     else if (a.max < b.max) c = b;
  77.     else {
  78.         c.max = a.max;
  79.         c.sum = (a.sum + b.sum) % mod;
  80.     }
  81.     return c;
  82. }
  83.  
  84. node get_ans(int v, int l, int r, int askr) {
  85.     if (l >= askr) return node();
  86.     if (r <= askr) return t[v];
  87.     int m = (l + r) / 2;
  88.     return merge(get_ans(2 * v + 1, l, m, askr), get_ans(2 * v + 2, m, r, askr));
  89. }
  90.  
  91. void update(int v, int l, int r, int pos, node val) {
  92.     if (r - l == 1) {
  93.         val.max++;
  94.         if (val.sum == 0) {
  95.             t[v].max = 1;
  96.             t[v].sum++;
  97.         } else t[v] = merge(t[v], val);
  98.         return;
  99.     }
  100.     int m = (l + r) / 2;
  101.     if (pos < m) {
  102.         update(2 * v + 1, l, m, pos, val);
  103.     } else {
  104.         update(2 * v + 2, m, r, pos, val);
  105.     }
  106.     t[v] = merge(t[2 * v + 1], t[2 * v + 2]);
  107. }
  108.  
  109. void build(int v, int l, int r) {
  110.     if (r - l == 1) {
  111.         t[v] = node();
  112.         return;
  113.     }
  114.     int m = (l + r) / 2;
  115.     build(2 * v + 1, l, m);
  116.     build(2 * v + 2, m, r);
  117.     t[v] = merge(t[2 * v + 1], t[2 * v + 2]);
  118. }
  119.  
  120. signed main() {
  121.     ios_base::sync_with_stdio(0);
  122.     cin.tie(0);
  123.     cout.tie(0);
  124.     cin >> n;
  125.     vector<int> a(n);
  126.     for (int i = 0; i < n; i++) cin >> a[i];
  127.     vector<int> b = a;
  128.     b.resize(unique(all(b)) - b.begin());
  129.     int q = b.size();
  130.     map<int, int> ind;
  131.     sort(all(b));
  132.     for (int i = 0; i < q; i++) {
  133.         ind[b[i]] = i;
  134.     }
  135. //    vector<int> cnt(q, 0);
  136.     t.assign(4 * n, node());
  137. //    build(0, 0, n);
  138.     for (int i = 0; i < n; i++) {
  139. //        cnt[ind[a[i]]]++;
  140. //        for (auto k : cnt) cout << k << " ";
  141. //        cout << "\n";
  142. //        cout << "t[0]: " << t[0].max << " " << t[0].sum << "\n";
  143. //        node pref = get_ans(0, 0, n, ind[a[i]]);
  144. //        cout << "pref: " << pref.max << " " << pref.sum << "\n";
  145.         update(0, 0, n, ind[a[i]], get_ans(0, 0, n, ind[a[i]]));
  146.     }
  147.     cout << t[0].sum << "\n";
  148. }
  149. /*
  150. 5
  151. 1 2 3 4 5
  152.  
  153. 6
  154. 1 1 2 2 3 3
  155. */
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
 
Top