fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long int ll;
  5. #define IOS ios_base::sync_with_stdio(0);  cin.tie(0); cout.tie(0);
  6.  
  7. #include <ext/pb_ds/assoc_container.hpp>
  8. #include <ext/pb_ds/tree_policy.hpp>
  9. using namespace __gnu_pbds;
  10.  
  11. typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>order_set;
  12. typedef pair<int, int>pr;
  13. #define all(i)     i.begin() , i.end()
  14. #define ft     first
  15. #define sn     second
  16. #define pb push_back
  17.  
  18. #define totalone(mask) __builtin_popcount(mask)
  19. #define chkbit(mask,bit) (mask&(1LL << bit))
  20. #define setbit(mask,bit) (mask|(1LL << bit))
  21. #define cngbit(mask,bit) (mask^(1LL << bit))
  22.  
  23. #define en "\n"
  24. #define dbg(x) cerr<<#x<<" is : "<<x<<en;
  25. #define yes cout<<"YES\n"
  26. #define no cout<<"NO\n"
  27. #define report cout<<-1<<en
  28. #define sum(n) ((1LL*(n)*(n+1))/ 2LL)
  29. #define sqr(n) (1LL*(n)*(n))
  30. #define vag(a,b) ((a + b - 1)/b)
  31. #define coutv(v) for(auto i: v) cout<<i<<" ";cout<<en;
  32. #define cinv(v) for(auto &i: v) cin >> i;
  33.  
  34. #define MAXN 100010
  35. #define inf 1e6+5
  36. const int mod = 1e9 + 7;
  37. int n;
  38. int a[MAXN];
  39.  
  40. struct segment_tree
  41. {
  42.     struct node {
  43.         int suru , ses, value;
  44.  
  45.         void init(int l, int r) {
  46.             suru = l, ses = r;
  47.             if (l == r) value = 0;
  48.         }
  49.     } g[4 * MAXN];
  50.  
  51.     void fill_cn(node &cn, node &ln, node &rn) // fill_current_node
  52.     {
  53.         cn.value = (1LL * (ln.value + rn.value)) % mod;
  54.     }
  55.  
  56.     void build(int cn, int l, int r)
  57.     {
  58.         g[cn].init(l, r);
  59.  
  60.         if (l == r ) return;
  61.         int md = l + (r - l) / 2;
  62.  
  63.         build(cn * 2, l, md);
  64.         build(cn * 2 + 1, md + 1, r);
  65.  
  66.         fill_cn (g[cn], g[cn * 2] , g[cn * 2 + 1]);
  67.     }
  68.  
  69.     void update(int cn, int pos, int val)
  70.     {
  71.         int x = g[cn].suru;
  72.         int y = g[cn].ses;
  73.  
  74.         if (y < pos || x > pos) return;
  75.         if (pos <= x && pos >= y ) {
  76.             g[cn].value = val;
  77.             return;
  78.         }
  79.  
  80.         update(cn * 2, pos, val);
  81.         update(cn * 2 + 1, pos, val);
  82.  
  83.         fill_cn(g[cn], g[cn * 2], g[cn * 2 + 1]);
  84.     }
  85.  
  86.     int query(int cn, int l, int r)
  87.     {
  88.         int x = g[cn].suru;
  89.         int y = g[cn].ses;
  90.         if (y < l || x > r) return 0;
  91.  
  92.         if (l <= x && r >= y ) return g[cn].value;
  93.  
  94.         ll A = query(cn * 2, l, r);
  95.         ll B =  query(cn * 2 + 1, l, r);
  96.         int ans = (1LL * (A + B)) % mod;
  97.         return ans;
  98.     }
  99.  
  100. } stre;
  101.  
  102. bool cmp(pr a, pr b)
  103. {
  104.     if (a.ft == b.ft) return a.sn > b.sn;
  105.     return a.ft < b.ft;
  106. }
  107. void solve()
  108. {
  109.  
  110.     cin >> n;
  111.     vector<pr>v;
  112.  
  113.     for (int i = 1; i <= n; i++) {
  114.         cin >> a[i];
  115.         v.pb({a[i], i});
  116.     }
  117.  
  118.     sort(all(v), cmp);
  119.     stre.build(1, 1, n);
  120.  
  121.     for (int i = 0; i < n; i++)
  122.     {
  123.         int cn = stre.query(1, 1, v[i].sn);
  124.         stre.update(1, v[i].sn, cn + 1);
  125.     }
  126.  
  127.     int an = stre.query(1, 1, n);
  128.     cout << an << en;
  129. }
  130. int main()
  131. {
  132.     IOS;
  133.     ll t;
  134.     t = 1;
  135.     cin >> t;
  136.  
  137.     int c = 0;
  138.     while ( t-- )
  139.     {
  140.         cout << "Case " << ++c << ": ";
  141.         solve();
  142.     }
  143.     return 0;
  144. }
Runtime error #stdin #stdout 0.01s 5472KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/H0x3qI
language:
C++14 (gcc 8.3)
created:
1 year ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!