fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define int              long long int
  4. #define double           long double
  5. #define print(a)         for(auto x : a) cout << x << " "; cout << endl
  6.  
  7.  
  8. const int M = 1000000007;
  9. const int N = 3e5+9;
  10. const int INF = 2e9+1;
  11. const int LINF = 2000000000000000001;
  12.  
  13. inline int power(int a, int b, int mod=M) {
  14.     int x = 1;
  15.     a %= mod;
  16.     while (b) {
  17.         if (b & 1) x = (x * a) % mod; 
  18.         a = (a * a) % mod;
  19.         b >>= 1;
  20.     }
  21.     return x;
  22. }
  23.  
  24.  
  25. //_ ***************************** START Below *******************************
  26.  
  27.  
  28.  
  29.  
  30. const int MOD = 998244353;
  31. vector<int> a;
  32.  
  33. int consistency(int n){
  34.  
  35.     unordered_map<int,int> mp;
  36.     mp.reserve(n*2);
  37.     mp.max_load_factor(0.25);
  38.  
  39.     vector<pair<int,int>> intervals;
  40.     intervals.reserve(n);
  41.  
  42.     intervals.push_back({0,0});
  43.     for(int i=0; i<n; i++){
  44.         if(mp.count(a[i])){
  45.             int l = mp[a[i]];
  46.             int r = i;
  47.             intervals.push_back({l, r});
  48.         }
  49.         mp[a[i]] = i;
  50.     }
  51.  
  52.     sort(begin(intervals), end(intervals));
  53.  
  54.     vector<pair<int,int>> merged;
  55.     int s = -1, e = -1;
  56.     int sz = intervals.size();
  57.     for(int i = 0; i<sz; i++){
  58.         int l = intervals[i].first;
  59.         int r = intervals[i].second;
  60.  
  61.         if(s==-1 && e==-1){
  62.             s = l, e=r;
  63.         }
  64.         else if(l <= e){
  65.             e = max(r, e);
  66.         }
  67.         else{
  68.             merged.push_back({s, e});
  69.             s = l, e = r;
  70.         }
  71.     }
  72.     merged.push_back({s, e});
  73.  
  74.     int ct = merged.size()-1;
  75.  
  76.     for(int i=1; i<merged.size(); i++){
  77.  
  78.         int gap = merged[i].first - merged[i-1].second - 1;
  79.         ct += gap;
  80.     }
  81.  
  82.     int gap = n-merged.back().second-1;
  83.     ct += gap;
  84.  
  85.     int ans = power(2, ct, MOD);
  86.  
  87.     return ans;
  88.  
  89. }
  90.  
  91.  
  92.  
  93.  
  94.  
  95. int consistency2(int n){
  96.  
  97.     map<int,int> mp;
  98.     for(int i=0; i<n; i++) mp[a[i]] = i;
  99.  
  100.     int ans = 1; 
  101.     int last = 0;
  102.  
  103.     for(int i=0; i<n-1; i++){
  104.         last = max(last, mp[a[i]]);
  105.         if(i==last) ans = (ans * 2)%MOD;
  106.     }
  107.  
  108.     return ans;
  109.  
  110. }
  111.  
  112.  
  113.  
  114.  
  115.  
  116.  
  117.  
  118.  
  119.  
  120.  
  121.  
  122.  
  123. int practice(int n){
  124.  
  125.  
  126.     return 0;
  127. }
  128.  
  129.  
  130.  
  131.  
  132.  
  133. void solve() {
  134.  
  135.     int n;
  136.     cin>> n;
  137.  
  138.     a.resize(n);
  139.     for(int i=0; i<n; i++) cin >> a[i];
  140.  
  141.     cout << consistency2(n) << endl;
  142.  
  143.  
  144. }
  145.  
  146.  
  147.  
  148.  
  149.  
  150. int32_t main() {
  151.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  152.  
  153.     int t = 1;
  154.     // cin >> t;
  155.     while (t--) {
  156.         solve();
  157.     }
  158.  
  159.     return 0;
  160. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
15
1 2 4 8 9 2 7 3 5 3 10 5 6 15 6
stdout
copy 
16
https://ideone.com/ecI7Ma
language:
C++14 (gcc 8.3)
created:
12 hours 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!