fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #include <ext/pb_ds/assoc_container.hpp>
  5. #include <ext/pb_ds/tree_policy.hpp>
  6. using namespace __gnu_pbds;
  7. #define ordered_set                                                            \
  8.   tree<pair<int, int>, null_type, less<pair<int, int>>, rb_tree_tag,           \
  9.        tree_order_statistics_node_update>
  10.  
  11. #define ll long long
  12. #define all(a) (a).begin(), (a).end()
  13. #define rall(a) (a).rbegin(), (a).rend()
  14. #define el '\n'
  15. #define sz(a) (int)(a).size()
  16. #define pi acos(-1)
  17. // #define int ll
  18.  
  19. #ifdef LOCAL
  20. #include "debug.hpp"
  21. #else
  22. #define debug(...) 0
  23. #define debug_itr(...) 0
  24. #define debug_bits(...) 0
  25. #endif
  26.  
  27. const ll mod = 998244353, N = 3e5 + 5;
  28.  
  29. void solve() {
  30.   int n;
  31.   cin >> n;
  32.   vector<int> a(n), pre(n + 1);
  33.   for (int &i : a)
  34.     cin >> i;
  35.   vector<int> cnt(n);
  36.   ordered_set s;
  37.   for (int i = n - 1; i >= 0; --i) {
  38.     cnt[i] = sz(s) - s.order_of_key({a[i], i});
  39.     s.insert({a[i], i});
  40.   }
  41.   debug(cnt);
  42.  
  43.   for (int i = 1; i <= n; ++i) {
  44.     pre[i] = pre[i - 1] * 2 + 1;
  45.     pre[i] %= mod;
  46.   }
  47.   sort(all(a));
  48.   debug(a);
  49.  
  50.   ll ans = 0;
  51.   for (int &i : cnt) {
  52.     ans = (ans % mod + pre[i] % mod) % mod;
  53.   }
  54.   cout << ans << el;
  55. }
  56.  
  57. int32_t main() {
  58.   cin.tie(0)->sync_with_stdio(0);
  59.   int t = 1;
  60.   // cin >> t;
  61.   while (t--)
  62.     solve();
  63. #ifdef LOCAL
  64.   debug((float)clock() / CLOCKS_PER_SEC);
  65. #endif
  66.   return 0;
  67. }
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
222747430
https://ideone.com/rudeEy
language:
C++14 (gcc 8.3)
created:
1 day ago
visibility:
public

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!