fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. using ll = long long;
  5.  
  6. const int MAXN = 5e5 + 7;
  7. const int INF = 1e9 + 7;
  8. const int MOD = 998244353;
  9.  
  10. int n, k;
  11. int a[MAXN];
  12. int L[MAXN], R[MAXN];
  13. stack<int> st;
  14.  
  15. void solve() {
  16.     int sk;
  17.     cin >> sk;
  18.     cin >> n >> k;
  19.     for (int i = 1; i <= n; i++) {
  20.         cin >> a[i];
  21.     }
  22.  
  23.     a[0] = a[n + 1] = INF;
  24.     st = {};
  25.     st.push(0);
  26.     for (int i = 1; i <= n; i++) {
  27.         while (a[st.top()] < a[i]) {
  28.             st.pop();
  29.         }
  30.         L[i] = st.top() + 1;
  31.         st.push(i);
  32.     }
  33.  
  34.     st = {};
  35.     st.push(n + 1);
  36.     for (int i = n; i >= 1; i--) {
  37.         while (a[st.top()] <= a[i]) {
  38.             st.pop();
  39.         }
  40.         R[i] = st.top() - 1;
  41.         st.push(i);
  42.     }
  43.  
  44.     ll ans = 0;
  45.     int cnt = 0;
  46.     for (int i = 1; i <= n; i++) {
  47.         if (a[i] <= k) {
  48.             ans = (ans + 1LL * (i - L[i] + 1) * (R[i] - i + 1)) % MOD;
  49.             cnt++;
  50.         }
  51.     }
  52.  
  53.     int p = 1;
  54.     for (int i = 1; i <= cnt; i++) {
  55.         p = p * 2 % MOD;
  56.     }
  57.     cout << ans << " " << (p - 1 + MOD) % MOD << "\n";
  58. }
  59.  
  60. int main() {
  61.     ios_base::sync_with_stdio(false);
  62.     cin.tie(0);
  63.  
  64.     if (fopen("D:/elaina.inp", "r")) {
  65.         freopen("D:/elaina.inp", "r", stdin);
  66.         freopen("D:/elaina.out", "w", stdout);
  67.     }
  68.  
  69.     if (fopen("camax.inp", "r")) {
  70.         freopen("camax.inp", "r", stdin);
  71.         freopen("camax.out", "w", stdout);
  72.     }
  73.  
  74.     solve();
  75. }
Success #stdin #stdout 0.01s 5728KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0 0
https://ideone.com/M3C8VT
language:
C++14 (gcc 8.3)
created:
2 days 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!