fork download
copy 
  1. #include "bits/stdc++.h"
  2. using namespace std;
  3. using ll = long long;
  4.  
  5. #ifdef JASPER
  6. #include "debug.h"
  7. #else
  8. #define debug(...) 166
  9. #endif
  10.  
  11. const int N = 666666 + 100;
  12.  
  13. int mod = 998244353;
  14. int lst[N], good[N], a[N];
  15. int ways[N], f[N], cnt[N], pr[N];
  16. vector <int> occ;
  17.  
  18. void add(int &a, int b) {
  19.     a += b;
  20.     while (a >= mod)
  21.         a -= mod;
  22.  
  23.     while (a < 0)
  24.         a += mod;
  25. }
  26.  
  27. void solve() {
  28.     int n, q;
  29.     cin >> n >> q;
  30.  
  31.     for (int i = 1; i <= n; i++) {
  32.         cin >> a[i];
  33.         occ.push_back(a[i]);
  34.     }
  35.  
  36.     sort(occ.begin(), occ.end());
  37.  
  38.     for (int i = 1; i <= n; i++) {
  39.         a[i] = lower_bound(occ.begin(), occ.end(), a[i]) - occ.begin();
  40.         good[i] = max(good[i - 1], lst[a[i]]);
  41.         lst[a[i]] = i;
  42.     }
  43.  
  44.     for (int i = 0; i < q; i++) {
  45.         int k;
  46.         cin >> k;
  47.  
  48.         deque <int> dq;
  49.         f[0] = 0;
  50.         cnt[0] = 1;
  51.  
  52.         for (int j = 1; j <= n; j++) {
  53.             if (j >= k) {
  54.                 while ((int)dq.size() && f[dq.back()] < f[j - k]) {
  55.                     int t = dq.back();
  56.                     add(ways[f[t]], -cnt[t]);
  57.                     dq.pop_back();
  58.                 }
  59.  
  60.                 dq.push_back(j - k);
  61.                 add(ways[f[j - k]], cnt[j - k]);
  62.             }
  63.  
  64.             while ((int)dq.size() && dq.front() < good[j]) {
  65.                 int t = dq.front();
  66.                 add(ways[f[t]], -cnt[t]);
  67.                 dq.pop_front();
  68.             }
  69.  
  70.             if ((int)dq.size()) {
  71.                 int t = dq.front();
  72.                 f[j] = f[t] + 1;
  73.                 pr[j] = max(pr[j - 1], f[j]);
  74.  
  75.                 if (pr[j - 1] == f[j]) {
  76.                     cnt[j] = (ways[f[t]] + cnt[j - 1]) % mod;
  77.                 } 
  78.  
  79.                 if (pr[j - 1] < f[j]) {
  80.                     cnt[j] = ways[f[t]];
  81.                 }
  82.  
  83.                 if (pr[j - 1] > f[j]) {
  84.                     cnt[j] = cnt[j - 1];
  85.                 }
  86.             } else {
  87.                 f[j] = 0;
  88.                 cnt[j] = 1;
  89.             }
  90.         }
  91.  
  92.         int ans = cnt[n], mx = pr[n];
  93.  
  94.         for (int j = 0; j <= n; j++) {
  95.             f[j] = cnt[j] = ways[j] = pr[j] = 0;
  96.         }
  97.  
  98.         //if (mx == 0)
  99.             //ans = 1;
  100.         cout << mx << " " << ans << '\n';
  101.     }
  102.  
  103.     for (int i = 0; i <= n + 1; i++) {
  104.         good[i] = lst[i] = 0;
  105.     }
  106. }
  107.  
  108. signed main() {
  109.     cin.tie(0) -> sync_with_stdio(0);
  110.     int t;
  111.     cin >> t;
  112.  
  113.     while (t--) {
  114.         solve();
  115.     }
  116.  
  117.     return 0;
  118. }
  119.  
  120. /*
  121. 2
  122. 5 2
  123. 1 2 1 2 1
  124. 2 3
  125. 6 2
  126. 1 2 3 4 5 6
  127. 3 5
  128. */
Success #stdin #stdout 0.01s 7652KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/q7Pqsm
language:
C++14 (gcc 8.3)
created:
5 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!